Table of contents
5.1 Foundations of the Simplex Method
5.2 The Simplex Method in Matrix Form
5.3 A Fundamental Insight
After any iteration, the makeup of the tableau is as follows:
Row 0 = [ -c, 0, 0 ] + cbB-1[A, I, b]
Rows 1 to m = B-1[A, I, b]
Fundamental Insight
When B is the basis matrix for the optimal solution found, let
S* = B-1 = coefficients of the slack variables, rows 1 to m
A* = B-1A = coefficients of the original variables, rows 1 to m
y* = cbB-1 = coefficients of the slack variables in row 0
z* = cbB-1A, so z* - c = coefficients of the original variables in row 0
Z* = cbB-1B = optimal value of the objective function
b* = B-1B = optimal right-hand sides of rows 1 to m
Then the fundamental insight is:
1) t* = t+y*T = [ y*A-c | y* | y*b ]
2) T* = S*T = [ S*A | S* | S*b ]
Example
Initial Tableau
Row 0:
Other rows:
Combined:
Final Tableau
Row 0:
Other rows:
Combined:
Adapting to Other Model Forms
Applications
The fundamental insight reveals that Z* is
5.4 The Revised Simplex Method
Comments