Simplex Method + Algorithm Flashcards

1
Q

zᵀ=

A

zᵀ=cbᵀB-¹N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

yʲ =

A

yʲ = [B-¹N]ʲ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

reduced cost coefficiant

A

-(zⱼ-cⱼ)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

reformulated LP using the current BFS

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

the current BFS is optimal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

zⱼ-cⱼ≤0 for all j

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Then the LP is unbounded

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Check the optimality of the BFS. LP is unbounded

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

the LP can be optimised further

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

f₀ =

A

cbᵀB-¹b

the objective value for the BFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How to check if an objective value is optimal

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Simplex algorithm:

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Theorem. Convergence.

A

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,

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

degeneracy

A

components of the BFS are zero.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Initial Tableu:

col: xb
row: zero

17
Q

Initial Tableu:

col: xn
row: zero

18
Q

Initial Tableu:

col: RHS
row: zero

A

cbᵀB-¹b

19
Q

Initial Tableu:

col: xn
row: xb

20
Q

Initial Tableu:

col: RHS
row: xb

21
Q

Initial Tableu:

col: xb
row: xb

22
Q

How to pivot

A
  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
23
Q

minimum ratio test for r

A

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

24
Q

simplex algorithm (tableu format):

A
  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.
25
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
26
Blands Rule
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.
27
maximum number of simplex iterations needed to reach the final tableu
2ⁿ
28
How to extract B from the initial tableu (basis of initial BFS)
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
29
How to extract B from an optimal tableu (with knowledge of slacks) (basis of optimal BFS)
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
30
How to extract A from an optimal tableu (with knowledge of slacks)
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
31
How to extract b from an optimal tableu (with knowledge of slacks)
read b* from tableu noting B-¹b=b*
32
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ᵢ
33
How to extract c from the optimal tableu.
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
34
Dual complementary slack condition
w*ᵀt*=x*ᵀs*
35
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
36
The dual simplex method
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