OPERATION RESEACH I

CHAPTER 5
SIMPLEX METHOD (TWO PHASE)
Erni Puspanantasari Putri, ST., M.Eng., Ph.D.

Department of Industrial Engineering, Faculty of Engineering

University of 17 Agustus 1945 (Untag) Surabaya

Discussion Material:

1. Various uses of the simplex method modification for non-standard LP problems with the two-
phase technique.
2. How to solve and get optimal LP solution with two-phase technique.

EXPLANATION

1. Basic Concepts of the Two Phase Method

The two-phase method is a method of solving the LP problem into 2 parts as described in Table A.

Table A. Basic Concepts of the Two-Phase Method

Phase Penjelasan
Phase I Strive for all artificial variable values to be zero.
Phase II Maximizing the real objective function Z starts from a basic solution that is feasible, either loading
artificial vectors with variable values at the zero level or not loading artificial vectors at all.

2. Criteria for Optimal Solution Completion Methods

 The "simplex method" is used to solve the optimal solution if all constraint / limiting functions in
the general form LP have the inequality "≤".
 "Two-phase simplex method" is used when the constraint / limiting function in the general form
LP has a combination of inequalities ("≤" and or "≥") and / or equation (=).

1
4. Case Study - Solving LP Problems with the Two-Phase Simplex Method

4.1. Explanation of the LP Case Study and the Mathematical Standard Form of LP
(Minimum Objective Function)

Objective Function
Minimum Z = 4 X1 + X2

Constraint Functions: (1) 3 X1 + X2 = 3

(2) 4 X1 + 3X2 ≥ 6
(3) X1 + 2X2 ≤ 4

X1 , X2 ≥ 0

4.2.1 Transformation of LP Standard Form to LP Standard Form

 The basis for the transformation of "General Form" to "Standard Form" is as described in "Table A".

Table A. Transformation of Constraint Function from "General Form" to "Standard Form"

Function Criteria General Form Inequality Sign Standard Form (=)

Constraint Function ≤ + Si
= + Ri
≥ ─ Si + Ri
+Si =Slack Variable, -Si=Surplus Variable, Ri=Artificial Variable

A. Transformation of Standard Form " Constraint Function"

→ Used for “Constraint Function” in “Initial Simplex Table - Phase I”

Standard Form R1 and R2 values of "Standard Form"

Constrain (1) 3 X1 + X2 + R1 = 3 → R1 = 3 - 3 X1 - X2
Function: (2) 4 X1 + 3X2 - S1 + R2 = 6 → R2 = 6 - 4 X1 - 3X2 + S1
(3) X1 + 2X2 + S2 = 4

X1 , X2 , S1 , S2 , R1 , R2 ≥ 0

2
 B. Transformation of Standard Form "Objective Function"

 The Formula of the Objective Function: r = ∑ Ri ..... (i = 1, 2, 3, ...... n)

 The value of Ri is obtained from the standard form "Constraint Function" (See discussion
above).

Objective r = ∑ Ri ..... (i = 1, 2, 3, ...... n)

Function :

Minimum r = R1 + R2 → →→→ R1 = 3 - 3 - X2
X1
R2 = 6 - 4 - 3X2 + S1 +
X1

R1+R2 → r = 9 - 7X1 - 4X2 + S1

r=0 → r + 7X1 + 4X2 - S1 = 9

WORKING PROCESS FROM PHASE I

4.2.2. Formation of "Table 1. Initial Simplex - Iteration 0 (Phase I)"

 Based on the "Standard Form" of "Constraint Function" and "Objective Function" above, it
can be formed "Table 1. Initial Simplex - 0 Iteration (Phase I)".

Table 1. Initial Simplex - Iteration 0 (Phase I)

Iteration VB X1 (EV) X2 S1 S2 R1 R2 Solusi Rasio

0 r 7 4 -1 0 0 0 9
R1 (LV) 3 1 0 0 1 0 3 1 * The smallest
R2 4 3 -1 0 0 1 6 1.5
S2 1 2 0 1 0 0 4 4

3
4.2.4. Formation of "Table 2. Simplex - Iteration 1 (Phase I)

Table 2. Iteration Simplex 1 (Phase I) - Optimum

Iteration VB X1 X2 S1 S2 R1 R2 Solution

2 r 0 0 0 0 1 -1 0
X1 1 0 .1/5 0 .8/15 .-1/5 .3/5
X2 0 1 .-3/5 0 .-4/5 .3/5 .6/5
S2 0 0 1 1 1 -1 1

 Table 2. Simplex Iteration 1 (Phase I) is the optimum Simplex Table because

minimum value " r = 0".
 Therefore, the working process can be continued in Phase II calculations.

WORKING PROCESS FROM PHASE II

4.3. Phase II - Two Phase Method

4.3.1. Determining Constraint Function - Phase II

 The constraint function is taken from "Table 2. Simplex Iteration 1 (Phase I) - Optimum" without
including the values of " R1 dan R2".
 Refer again to "Table 2. Iteration Simplex 1 (Phase I) - Optimum".

Table 2. Iteration Simplex 1 (Phase I) - Optimum

Iteration VB X1 X2 S1 S2 R1 R2 Solution

2
X1 1 0 .1/5 0 .8/15 .-1/5 .3/5
X2 0 1 .-3/5 0 .-4/5 .3/5 .6/5
S2 0 0 1 1 1 -1 1

4
  Thus, “Table 4. Initial Simplex - 0 Iteration - Phase II” for “Constraint Function” is as follows:

Table 4. Initial Simplex - 0 Iteration - Phase II” for “Constraint Function”

Iteration VB X1 X2 S1 S2 Solution

0
(Awal) X1 1 0 1/5 0 3/5
X2 0 1 -3/5 0 6/5
S2 0 0 1 1 1

 Based on Table 4, the "Constraint Functions" equations can be made as follows:

Constrain Function (1) X1 + 1/5S1 = 3/5

(2) + X2 - -3/5S1 = 6/5
(3) S1 + S2 = 1

4.3.2. Determine the "Objective Function" in Phase II

 Determination of “Objective Function” - Phase II is based on LP's “General Form Objective

Functions”.

Objective Function
Minimum Z = 4 X1 + X2

 The value of "X1" and "X2" in the "Objective Function" is based on the equation "Constraint
Function" above. Accordingly, the values for "X1" and "X2" are as follows:

Constraint Function:
(1) X1 + 1/5S1 = 3/5 → X1 = 3/5 - 1/5S1
(2) X2 - 3/5S1 = 6/5 → X2 = 6/5 + 3/5S1

5
 Substitute the values of X1 and X2 in the general form "Objective Function".

Objective Function
Minimum Z = 4 X1 + X2
= 4 (3/5 - 1/5S1) + (6/5 +3/5S1)
= 12/5 –4/5S1 + 6/5 + 3/5S1
= - 4/5S1+ 3/5S1 + 12/5 + 6/5
↓↓↓↓
Zmin = - 1/5S1+ 18/5
↓↓↓↓
Z = 0 → Z + 1/5S1 = 18/5
↓↓↓↓

 The value "Z + 1 / 5S1 = 18/5" is used for the "Purpose Function" in "Table 5. Initial Simplex -
Iteration 0 (Phase II)".

Table 5. Initial Simplex - Iteration 0 (Phase II) for "Objective Function"

Iteration VB X1 X2 S1 S2 Solution

0 Zmin 0 0 1/5 0 18/5

(Initial)

6
4.3.3. Formation of "Table 6. Initial Simplex - Iteration 0 (Phase II)"

 The formation of "Table 6. Initial Simplex - Iteration 0 (Phase II)" is a combination of "Table 5.
Initial Simplex - Iteration 0 (Phase II) for the Objective Function" and "Table 4. Initial Simplex -
Iteration 0 (Phase II) for Constraint Function”.

Table 6. Initial Simplex - 0 Iteration (Phase II)

See:
“Table 5. Initial Simplex - Iteration 0
(Phase II) for the Objective Function”

Iteration VB X1 X2 S1 S2 Solution

0 Zmin 0 0 1/5 0 18/5

(Awal) X1 1 0 1/5 0 3/5

X2 0 1 -3/5 0 6/5
S2 0 0 1 1 1

See:
“Table 4. Initial Simplex - Iteration 0
(Phase II) for Constraint Function”

7
4.3.4. Formation of "Table 7. Simplex - Iteration 1 (Phase II) and so on until the" Simplex
Table - Optimal Iteration (Phase II) "is obtained.

 The calculation process is the same as the calculation in Phase I.

Table 7. Simplex - Iteration 1 (Phase II) - Optimum

Iteration VB X1 X2 S1 S2 Solution

1 Zmin 0 0 0 -1/5 17/5

X1 1 0 0 -1/5 2/5
X2 0 1 0 3/5 9/5
S2 0 0 1 1 1

 "Table 7. Simplex - Iteration 1 (Phase II)" is the Optimal Simplex Table.

 Thus, the optimum solution for the problem of minimization objective function using the Two-
Phase Method is Zmin = 17/5, X1 2/5, X3 = 9/5, and S2 = 1.

8
 INDIVIDUAL ASSIGNMENT 1
Two-Phase Simplex Method (Minimum Objective Function)

 Solve the following case study problem using the Two-Phase Simplex Method (Minimum Purpose
Function):

Objective Function
Minimum Z = 20 X1 + 5X2

Constraint Function (1) 15 X1 + 5 X2 = 15

(2) 20 X1 + 15 X2 ≥ 30
(3) 5 X1 + 10 X2 ≤ 20

X1 , X2 ≥ 0