Optimization by Richard Weber

Author:Richard Weber
Language: eng
Format: epub
Tags: Optimization,

Compare these values with the basic solutions of the dual problem (on page 15). You will see that the objective row of the simplex tableau corresponding to each b.f.s. of problem P contains the values of the variables for a complementary slack basic solution to problem D (after a sign change).

The simplex algorithm can (and should) be viewed as searching amongst basic feasible solutions of P, for a complementary-slack basic solution of D which is also feasible.

At the optimum of P the shadow prices (which we can read off in the bottom row) are also the dual variables for the optimal solution of D.

7.2 Algebra of the simplex method

It is convenient to divide the variables into two sets, and to split the matrix A accordingly. For example, given

/ an a\2 ai3

\ CL2\ CL22 CL23

we can partition the variables into two disjoint subsets (basic and non-basic) B = {1, 2} and A = {3} and rewrite the equation

/ an «i2

V a 2l &22

or

AbXb + A N x N = 6,

where xb = ( Xl I contains the variables in B and xn = ( x^) contains the vari-\X2 J v '

ables in A, and Ab has the columns of A corresponding to variables in B (columns 1 and 2) and An has columns corresponding to variables from A (column 3).

You should convince yourself that the two forms of the linear equations are equivalent and that the same trick would work for general m x n matrices A and partition of variables into two sets. If A = (ai,..., a n ), where is the ith column, then

Ax = diXi + diXi = AbXb + A^xn = b.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.