Two Phase Method

Question 1

phase 1 of two phase method

Answer 1

1. add artificial variables to constraints to force an identity matrix (immediate BFS in the form x=0, xₐ=b)
2. solve the following LP problem
   min eᵀxₐ s.t. Ax + xₐ = b x,xₐ≥0
3. if at optimality xₐ is not equal to zero then the problem has no feasible solution. Otherwise the optimal soltuion for the phase 1 problem is (x,0) so x is feasible for the original.

Question 2

phase 2 of two phase method

Answer 2

1. x* is feasible for the original problem. Split x* into basic and non basic.
2. remove the artificial variables from the table
3. restore the simplex tableu by replacing the zero row with zⱼ-cⱼ
4. carry out the simplex algorithm

Question 3

Big M method

Answer 3

1. introduce artificial variables to force an identity matrix
2. solve the following LP problem
   min cᵀx + M(eᵀxₐ) s.t. Ax + xₐ = b x,xₐ≥0
   -> if an optimal solution is found and xₐ=0 then x is the optimal solution to the original problem
   -> if an optimal solution is found and xₐ/= 0. The the original problem is infeasible
   -> if an optimal solution is unbounded and xₐ=0 then the original problem is unbounded
   -> if an optimal solution is unbounded amd x*ₐ/=0 then the original problem is unbounded

Question 4

if xₐ/=0 in two phase and big M

Answer 4

the original problem is unbounded

Question 5

Big M: if xₐ=0 and there is a optimal solution

Answer 5

x* is the optimal solution of the original LP problem

Question 6

Big M: if xₐ=0 and the optimal solution is unbounded

Answer 6

the original problem is also unbounded

Question 7

Two Phase: if xₐ=0 and all the artificial variables are out of the basis

Answer 7

remove xₐs, restore the simplex tableu and carry out simplex

Question 8

Two phase: if xₐ=0 and some of the artificial variables are still in the basis

Answer 8

just remove the row corresponding to the artificial variable (if its value in the RHS column if zero)

Question 9

How can you tell if xₐ=0

Answer 9

xₐ=0 if the corresponding value in the RHS is 0

if xₐ not in the basis then it automatically has xₐ=0