Linear Programming Two-Phase Simplex Method Learning Outcomes

Solving LP problems using the Two-Phase Method

ECS716: Operational Research Pn Paezah Hamzah

Introduction

When a basic feasible solution is not readily available, the two-phase simplex method may be used as an alternative to the big M method. In the two-phase simplex method, we add artificial variables to the same constraints as we did in big M method. Then we find a bfs to the original LP by solving the Phase I LP. In the Phase I LP, the objective function is to minimize the sum of all artificial variables. At the completion of Phase I, we reintroduce the original LPs objective function and in Phase II, we determine the optimal solution to the original LP.

Phase I
Step 1: Express the given LP problem in a standard form by introducing slack, surplus and artificial variables. Step 2: Formulate an artificial objective function.

Min Z= A1 + A2 +...+An

Do not assign coefficient M to the artificial variables; this is not the big-M method.

For now, ignore the original LPs objective function. Instead , solve an LP whose objective function is Min Z=(sum of all the artificial variables). This is called the Phase I LP. The act of solving the Phase I LP will force the artificial variables to be zero. The optimal solution obtained at the end of phase 1 will be a bfs for the real problem which is solved in Phase II.

Phase I LP is always a minimization problem, even if the original LP is a maximization problem.

Outcome of Phase I
Since each artificial variable Ai0, solving the Phase I LP will result in one of the following three cases: Case 1: The optimal value of Z, i.e. min Z > 0. In this case, the original LP has no feasible solution. Hence, the original LP is infeasible. Case 2: Min Z =0, and no artificial variables are in the optimal Phase I basis. In this case, we drop all artificial variable columns in the optimal Phase I tableau. We now combine the original objective function with the constraints from the optimal Phase I tableau. This yields the Phase II LP. The optimal solution to the Phase II LP is the optimal solution to the original LP. Case 3: Min Z=0 and at least one artificial variable is in the optimal Phase I basis. In this case, we can find the optimal solution to the original LP if at the end of Phase I we drop all nonbasic artificial variables, and any variable from the original problem that has a negative coefficient in Cj-Zj from the optimal Phase I tableau.

Phase II

The bfs found at the end of Phase I is used as the starting solution for Phase II. The final simplex tableau of Phase I is taken as the initial tableau of Phase II. The atticial objective function is replaced by the original (real) objective function.

Example: Refer to Marys Radiation Therapy [Hillier & Lieberman textbook,Chp. 3] Min Z = 0.4X1 s.t. 0.3X1 0.5X1 0.6X1 + 0.5X2 + 0.1X2 + 0.5X2 + 0.4X2 X1, X2 2.7 = 6 6 0

The Real Problem

Phase I: Obj: Min Z= A1+A2 The Artificial Problem in the standard form

Min Z = A1 + A2 s.t. 0.3X1 + 0.1X2 + S1 = 2.7 0.5X1 + 0.5X2 +A1 =6 0.6X1 +0.4X2 -S2 + A2 = 6 X1, X2, S1, S2 , A1, A2 0

In canonical form

Min Z = 0X1+

0X2 + 0S1 + + 0S2 2 + 1A 1 2 0 X11A ,X ,A 2 , S1 , S 1

0.3X1+ 0.1X2 + 1S1 + 0A1 + 0S2 + 0A2 = 2.7 0.5X1+ 0.5X2 + 0S1 + 1A1 + 0S2 + 0A2 = 6 0.6X1+ 0.4X2 + 0S1 + 0A1 - 1S2 + 1A2 = 6 Next, we construct the initial tableau. Iteration 1 Basis Cj 0 S1 1 1 A1 A2 Zj Cj-Zj X1 0 0.3 0.5 0.6 1.1 -1.1 X2 0 0.1 0.5 0.4 0.9 -0.9 S1 0 1 0 0 0 0 X1, X2, S1, S2, A1 0 A1 S2 A2 1 0 1 0 0 0 1 0 1 0 0 -1 -1 1 0 1 1 0

RHS 2.7 6 6 12

ratio SMALLEST 9 positive ratio 12 10

MOST NEGATIVE Cj-Zj

(a minimization problem) Iteration 2 Cj 0 1 1 Basis X1 A1 A2 Zj Cj-Zj X1 0 1 0 0 0 0 X2 0 1/3 1/3 0.2 16/30 -16/30 S1 0 10/3 -5/3 -2 -11/3 11/3 A1 1 0 1 0 0 0 S2 0 0 0 -1 -1 1 A2 1 0 0 1 1 0 RHS 9 1.5 0.6 2.1 ratio 27 4.5 3

MOST NEGATIVE Cj-Zj

Iteration 3 Cj 0 1 0 Basis X1 A1 X2 Zj Cj-Zj X1 0 1 0 0 0 0 X2 0 0 0 1 0 0 S1 0 20/3 5/3 -10 5/3 -5/3 A1 1 0 1 0 0 0 S2 0 5/3 5/3 -5 5/3 -5/3 A2 1 -5/3 -5/3 5 -5/3 8/3 RHS 8 0.5 3 0.5 ratio 1.5 0.3 ---

Iteration 4 Cj 0 0 0 Basis X1 S1 X2 Zj Cj-Zj X1 0 1 0 0 0 0 X2 0 0 0 1 0 0 S1 0 0 1 0 0 0 A1 1 -4 3/5 6 0 1 S2 0 -5 1 5 0 0 A2 1 5 -1 -5 0 0 RHS 6 0.3 6 0

All Cj-Zj 0 optimal Case 2 solution Phase I optimal solution: Min Z=0 and no artificial variable appears in the basis. Phase II Use the original objective function: Min Z = 0.4X1 + 0.5X2 Since Phase I optimal solution is Case 2 solution, we drop all artificial variables. The following is the LP model for phase II. Min Z = 0.4X1+0.5X2 + 0S1 + 0S2 0.3X1+ 0.1X2 + 1S1 + 0S2 = 2.7 0.5X1+ 0.5X2 + 0S1 + 0S2 = 6 0.6X1+ 0.4X2 + 0S1 + 1S2 = 6 Basically, the initial tableau for Phase II is developed as follows: use the final tableau from Phase I, and X1, X2, S1, S2, A1 0 drop all the artificial variable columns

Cj 0 0 0

Basis X1 S1 X2 Zj Cj-Zj

X1 0 1 0 0 0 0

X2 0 0 0 1 0 0

S1 0 0 1 0 0 0

S2 0 -5 1 5 0 0

RHS 6 0.3 6 0

substitute Phase II objective function and restore proper form ( e.g. the Cj column, Zj row and Cj-Zj row entries.

Cj 0.4 0 0.5

Basis X1 S1 X2 Zj Cj-Zj

X1 0.4 1 0 0 0.4 0

X2 0.5 0 0 1 0.5 0

S1 0 0 1 0 0 0

S2 0 -5 1 5 0.5 -0.5

RHS 6 0.3 6 5.4

Carry out further iterations to obtain the optimal solution. Basis X1 S1 X2 Zj Cj-Zj X1 0.4 1 0 0 0.4 0 X2 0.5 0 0 1 0.5 0 S1 0 0 1 0 0 0 S2 0 -5 1 5 0.5 -0.5

Cj 0.4 0 0.5

RHS 6 0.3 6 5.4

ratio 0.3 6/5

Not optimal; NEGATIVE

(a minimization problem) X1 0.4 1 0 0 0.4 0 X2 0.5 0 0 1 0 0 S1 0 5 1 -5 -0.5 0.5 S2 0 0 1 0 0 0

Cj 0.4 0 0.5

Basis X1 S2 X2 Zj Cj-Zj

RHS 7.5 0.3 4.5 5.25

All Cj-Zj values are 0. Hence, solution is optimal. Optimal solution: X1 = 7.5, X2=4.5 Min Z = 5.25 To treat Marys tumor, the minimum absorption by healthy anatomy can be attained by giving her radiation dose at the entry point of 7.5 kilorads for Beam 1, and 4.5 kilorads for Beam2.

Exercises: Solve the following LP problems using the Two-Phase method. 1. Min Z = 4X1 + 4X2 + X3 s.t. X1 + X2 + X 3 2X1 + X2 2X1 + X2 + 3X3 X1, X2,X3 2. 2 3 3 0 Max Z = 3X1 + X2 s.t. X1 + X2 2X1 + X2 X1 + X2 = X1 , X 2

3 4 3 0

3.

Min Z = 3X1 + X2 s.t. 2X1 + X2 6 3X1 + 2X2 = 4 X1, X2 0