Simplex Method + Algorithm Flashcards
zᵀ=
zᵀ=cbᵀB-¹N
yʲ =
yʲ = [B-¹N]ʲ
reduced cost coefficiant
-(zⱼ-cⱼ)
reformulated LP using the current BFS
min f₀ - (zᵀ - cnᵀ)xn
s.t. B-¹Nxn + xb = B-¹b
Check the optimality of the BFS. zⱼ-cⱼ≤0 for all j
the current BFS is optimal
Check the optimality of the BFS. the current BFS is optimal
zⱼ-cⱼ≤0 for all j
Check the optimality of the BFS. zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ≤0
Then the LP is unbounded
Check the optimality of the BFS. LP is unbounded
zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ≤0
Check the optimality of the BFS. zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ has a positive component
the LP can be optimised further
Check the optimality of the BFS. LP can be optimised further
zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ has a positive component
f₀ =
cbᵀB-¹b
the objective value for the BFS
How to check if an objective value is optimal
- identity m,n
- compute f₀
- determine cb and cn
- define the columns y
- calculate z and zₙ-cₙ check if zₙ-cₙ is greater than zero for each n
- if neccessary check yₙ aswell
Simplex algorithm:
- find a starting BFS with basis B
- set xb = B-¹b, xn=0, f=cbᵀxb, z=cbᵀB-¹N
- calculate zⱼ-cⱼ for all non basic variables i∈R (R is the current set of indices associated with the non-basic variables)
- choose k such that zₖ-cₖ = max {zⱼ-cⱼ}
- if zₖ-cₖ≤0 the solution is optimal so stop - calculate yₖ = B-¹aₖ.
- if yₖ≤0 the optimal value is unbounded - find r bᵣ/yᵣₖ = min {bᵢ/yᵢₖ: yᵢₖ>0}
- remove xᵣ and replace it with xₖ in the basis
Theorem. Convergence.
In the absence of degeneracy and assuming feasibility the simplex method stops in a finite number of iteration, either with an optimal BFS or with the conclusion that the optimal value is unbounded,
degeneracy
components of the BFS are zero.
Initial Tableu:
col: xb
row: zero
0
Initial Tableu:
col: xn
row: zero
zⱼ-cⱼ
Initial Tableu:
col: RHS
row: zero
cbᵀB-¹b
Initial Tableu:
col: xn
row: xb
B-¹N
Initial Tableu:
col: RHS
row: xb
B-¹b=b*
Initial Tableu:
col: xb
row: xb
Identity
How to pivot
- find k by finding the maximum zₖ-cₖ
- find r via the minimum ratio test
- update the rth row by dividing it by yᵣₖ xᵣ->xₖ
- update the zero row
- update all remaining rows
minimum ratio test for r
bᵣ/yᵣₖ = min {bᵢ/yᵢₖ: yᵢₖ>0}
simplex algorithm (tableu format):
- find an initial BFS with basis B. write the inital tableu.
- Let zₖ-cₖ = max{zⱼ-cⱼ: j∈R}
- > zₖ-cₖ≤0 the solution is optimal. stop.
- > otherwise xₖ will enter the basis - if yₖ≤0 the LP is unbounded. Stop. Otherwise go to next step.
- determine r by the minimum ratio test
- pivot at yᵣₖ
- update the basic variables where xᵣ leaves and xₖ enters.