Simplex Method + Algorithm

Question 1

zᵀ=

Answer 1

zᵀ=cbᵀB-¹N

Question 2

yʲ =

Answer 2

yʲ = [B-¹N]ʲ

Question 3

reduced cost coefficiant

Answer 3

-(zⱼ-cⱼ)

Question 4

reformulated LP using the current BFS

Answer 4

min f₀ - (zᵀ - cnᵀ)xn

s.t. B-¹Nxn + xb = B-¹b

Question 5

Check the optimality of the BFS. zⱼ-cⱼ≤0 for all j

Answer 5

the current BFS is optimal

Question 6

Check the optimality of the BFS. the current BFS is optimal

Answer 6

zⱼ-cⱼ≤0 for all j

Question 7

Check the optimality of the BFS. zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ≤0

Answer 7

Then the LP is unbounded

Question 8

Check the optimality of the BFS. LP is unbounded

Answer 8

zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ≤0

Question 9

Check the optimality of the BFS. zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ has a positive component

Answer 9

the LP can be optimised further

Question 10

Check the optimality of the BFS. LP can be optimised further

Answer 10

zⱼ-cⱼ>0 for some j and yʲ=B-¹aⱼ has a positive component

Question 11

f₀ =

Answer 11

cbᵀB-¹b

the objective value for the BFS

Question 12

How to check if an objective value is optimal

Answer 12

1. identity m,n
2. compute f₀
3. determine cb and cn
4. define the columns y
5. calculate z and zₙ-cₙ check if zₙ-cₙ is greater than zero for each n
6. if neccessary check yₙ aswell

Question 13

Simplex algorithm:

Answer 13

1. find a starting BFS with basis B
2. set xb = B-¹b, xn=0, f=cbᵀxb, z=cbᵀB-¹N
3. calculate zⱼ-cⱼ for all non basic variables i∈R (R is the current set of indices associated with the non-basic variables)
4. choose k such that zₖ-cₖ = max {zⱼ-cⱼ}
   - if zₖ-cₖ≤0 the solution is optimal so stop
5. calculate yₖ = B-¹aₖ.
   - if yₖ≤0 the optimal value is unbounded
6. find r bᵣ/yᵣₖ = min {bᵢ/yᵢₖ: yᵢₖ>0}
7. remove xᵣ and replace it with xₖ in the basis

Question 14

Theorem. Convergence.

Answer 14

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,

Question 15

degeneracy

Answer 15

components of the BFS are zero.

Question 16

Initial Tableu:

col: xb
row: zero

Answer 16

0

Question 17

Initial Tableu:

col: xn
row: zero

Answer 17

zⱼ-cⱼ

Question 18

Initial Tableu:

col: RHS
row: zero

Answer 18

cbᵀB-¹b

Question 19

Initial Tableu:

col: xn
row: xb

Answer 19

B-¹N

Question 20

Initial Tableu:

col: RHS
row: xb

Answer 20

B-¹b=b*

Question 21

Initial Tableu:

col: xb
row: xb

Answer 21

Identity

Question 22

How to pivot

Answer 22

1. find k by finding the maximum zₖ-cₖ
2. find r via the minimum ratio test
3. update the rth row by dividing it by yᵣₖ xᵣ->xₖ
4. update the zero row
5. update all remaining rows

Question 23

minimum ratio test for r

Answer 23

bᵣ/yᵣₖ = min {bᵢ/yᵢₖ: yᵢₖ>0}

Question 24

simplex algorithm (tableu format):

Answer 24

1. find an initial BFS with basis B. write the inital tableu.
2. Let zₖ-cₖ = max{zⱼ-cⱼ: j∈R}
   - > zₖ-cₖ≤0 the solution is optimal. stop.
   - > otherwise xₖ will enter the basis
3. if yₖ≤0 the LP is unbounded. Stop. Otherwise go to next step.
4. determine r by the minimum ratio test
5. pivot at yᵣₖ
6. update the basic variables where xᵣ leaves and xₖ enters.

Question 25

If A already has an identity part of the matrix what does the tableu look like?

Answer 25

the zero row is just c
the main body is just A
the RHS is 0 followed by b

Question 26

Blands Rule

Answer 26

if B-¹b is degenerate it will cause cycling hence,

1. if more than one choice for maximum zⱼ-cⱼ chose the lowest numbered (i.e. left most) non-basic column with negative reduced cost
2. if more than one row satisfies the minimum ratio test. chose the row with the lowest numbered column basic variable in it.

Question 27

maximum number of simplex iterations needed to reach the final tableu

Answer 27

2ⁿ

Question 28

How to extract B from the initial tableu (basis of initial BFS)

Answer 28

1. the order of the xbᵢs down the side gives the order of the aᵢs in A
2. read the aᵢs from the tableu

Question 29

How to extract B from an optimal tableu (with knowledge of slacks)
(basis of optimal BFS)

Answer 29

1. B-¹ is the block under where the slacks are (would’ve originally been the identity)
2. find the inverse of this to get B

Question 30

How to extract A from an optimal tableu (with knowledge of slacks)

Answer 30

1. the first part of A can be found by extracting B
2. The second part can be found by
   B-¹aʲ = yᵢ where yᵢ is column i in the tableu and B-¹ can be found

Question 31

How to extract b from an optimal tableu (with knowledge of slacks)

Answer 31

read b* from tableu noting B-¹b=b*

Question 32

Theorem. optimal solution of the dual.

Answer 32

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ᵢ

Question 33

How to extract c from the optimal tableu.

Answer 33

1. find the optimal solution for the dual
2. use theorem wᵀ= cbᵀB-¹ to calculate cb
3. to find cn use the non basic part of the zero row cbᵀB-¹N-cnᵀ to calculate cn

Question 34

Dual complementary slack condition

Answer 34

wᵀt=xᵀs

Question 35

Lemma

Answer 35

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

Question 36

The dual simplex method

Answer 36

1. find a basis B of the primal s.t. zⱼ-cⱼ≤0 for all j
2. if B-¹b≥0 STOP the current solution is optimal
3. if B-¹b<0 select the pivot row r with bᵣ<0 bᵣ = min{b*i}
4. if yᵣⱼ ≥ 0 for al j STOP the dual is unbounded => primal is infeasible
5. find the element k which is entering via the minimum ratio test
6. pivot at yᵣₖ
7. repeat until RHS all >0