Notes11_16 - Saint Mary's College



Key ideas for proving correctness of the simplex algorithm

We name the following matrices and vectors associated to the simplex tableau:

Names based on the original set-up of the tableaus:

A is the initial coefficient matrix (including columns for slack/surplus variables)

b is the vector of constants from the right hand side of the constraints

CT is the row vector [thus the "T"] of coefficients in the objective function

Our initial tableau is

[pic]

At any basic feasible solution (for any basis matrix):

B is the basis matrix – the submatrix of A made up of the columns in A which are in the basis [identified by the current basisc feasible solution – but is in the original matrix]

CBT is the row vector of coefficients (from the objective function) for the variables in the basis

When we have the tableau representing any basic feasible solution, there is a basis matrix B from A which has been reduced, by a series of row operations, to an identity (possibly scrambled). The row operations can be reperesented in the matrix (the top part [pic] of the tableau) as multiplication by B-1 [that is B-1, =EjEj-1 . . . E1 where the Ek’s represent the elementary matricces performing the row operations] so [pic] - each part is multiplied by B-1.

The bottom row is obtained by adding each row (from the current tableau) containing a pivot, times the appropriate coefficient from CT , to the bottom row [to cancel the negative coefficient there and give a 0] so we are adding [pic] to the first part of the row, 0 to the z-column, and [pic] to the last entry. Thus our tableau, at any stage, is represented by

[pic]

It is convenient to further divide up the original matrix A:

D is the submatrix of A consisting of the columns that do not have pivots in the current tableau [the rest of the columns]

CDT is the row vector of coefficients [from the objective function] for the variables not in the final basis.

The initial tableau can be rewritten [by listing the variables in a different order]

[pic]

[That is, we can rearrange the columns to write A = [D B] and -CT = [-CDT -CBT ] - This could be done for each possible basis – it’s not practically useful, but is theoretically possible.

If we start from this form (for the basis we care about), the tableau corresponding to the basis, is:

[pic] and the value of the objective function is given by CBT B-1b

We want to show that our "stopping criterion" [stop when there are no positive entries in the coefficient portion of the bottom row ] really does give us a minimal solution. [a feasible solution X0 with the property that , for any feasible solution X we have

CTX0 ≤ CTX - no other feasible solution X gives a smaller value for the objective function]. The key is that we find X0 [the solution of [B-1D B-1B] X = B-1b with all the variables for the D matrix - the free variables - set equal to 0 ] using a particular basis matrix B which is selected by the fact that no component of the vector CBT B-1D is larger than the corresponding component of CDT [so CBT B-1D – CDT contains no positive numbers]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download