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.
If A already has an identity part of the matrix what does the tableu look like?
the zero row is just c
the main body is just A
the RHS is 0 followed by b
Blands Rule
if B-¹b is degenerate it will cause cycling hence,
- if more than one choice for maximum zⱼ-cⱼ chose the lowest numbered (i.e. left most) non-basic column with negative reduced cost
- if more than one row satisfies the minimum ratio test. chose the row with the lowest numbered column basic variable in it.
maximum number of simplex iterations needed to reach the final tableu
2ⁿ
How to extract B from the initial tableu (basis of initial BFS)
- the order of the xbᵢs down the side gives the order of the aᵢs in A
- read the aᵢs from the tableu
How to extract B from an optimal tableu (with knowledge of slacks)
(basis of optimal BFS)
- B-¹ is the block under where the slacks are (would’ve originally been the identity)
- find the inverse of this to get B
How to extract A from an optimal tableu (with knowledge of slacks)
- the first part of A can be found by extracting B
- The second part can be found by
B-¹aʲ = yᵢ where yᵢ is column i in the tableu and B-¹ can be found
How to extract b from an optimal tableu (with knowledge of slacks)
read b* from tableu noting B-¹b=b*
Theorem. optimal solution of the dual.
At optimality of the primal minimisation problem in canonical form wᵀ:=cbᵀB-¹ is an optimal solution to the dual problem and has the following components wᵢ
How to extract c from the optimal tableu.
- find the optimal solution for the dual
- use theorem wᵀ= cbᵀB-¹ to calculate cb
- to find cn use the non basic part of the zero row cbᵀB-¹N-cnᵀ to calculate cn
Dual complementary slack condition
wᵀt=xᵀs
Lemma
A primal dual pair of optimal solutions is unique iff its a strictly complementary pair of basic solutions i.e. x=0 iff s>0
The dual simplex method
- find a basis B of the primal s.t. zⱼ-cⱼ≤0 for all j
- if B-¹b≥0 STOP the current solution is optimal
- if B-¹b<0 select the pivot row r with bᵣ<0 bᵣ = min{b*i}
- if yᵣⱼ ≥ 0 for al j STOP the dual is unbounded => primal is infeasible
- find the element k which is entering via the minimum ratio test
- pivot at yᵣₖ
- repeat until RHS all >0
