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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- who paid obama s college tuition
- saint joseph s regional high school
- roget s college thesaurus
- obama s college records released
- who paid for obama s college education
- saint joseph s high school metuchen
- obama s college years
- 2019 women s college softball
- ncaa women s college softball schedule
- saint joseph s school
- king s college student portal
- 2019 women s college world series