Scribd
Upload
215 views3 pages

Two-Phase Method in Linear Programming

This document describes the two phase simplex method to solve a linear programming problem with three decision variables (x1, x2, x3) and three constraints. In phase 1, slack and artificial variables are introduced to convert inequalities to equalities. An iterative process removes the artificial variables to find a basic feasible solution. In phase 2, the original objective function is optimized using the simplex method to find the optimal solution values of x1=6, x2=7, x3=0, with maximum z=177.

Uploaded by

Jagat Singh Dhami
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
215 views3 pages

Two-Phase Method in Linear Programming

This document describes the two phase simplex method to solve a linear programming problem with three decision variables (x1, x2, x3) and three constraints. In phase 1, slack and artificial variables are introduced to convert inequalities to equalities. An iterative process removes the artificial variables to find a basic feasible solution. In phase 2, the original objective function is optimized using the simplex method to find the optimal solution values of x1=6, x2=7, x3=0, with maximum z=177.

Uploaded by

Jagat Singh Dhami
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
  • Two Phase Method Introduction
  • Two Phase Method - Phase 1
  • Two Phase Method - Phase 2

Two Phase Method

Two phase Method

Maximize z = 12x1 + 15x2 + 9x3


Subject to
8x1 + 16x2 + 12x3 <= 250
4x1 + 8x2 + 10x3 >=80
7x1 + 9x2 + 8x3 = 105
x1, x2, x3 >= 0

Solution

Converting the inequalities into equalities.


Introducing slack, surplus & artificial variables
8x1 + 16x2 + 12x3 + s1 = 250
4x1 + 8x2 + 10x3 – s2 + A1 = 80
7x1 + 9x2 + 8x3 + A2 = 105
Where:
s1 is a slack variable.
s2 is a surplus variable.
A1& A2 are artificial variables.

Phase 1

Maximize 0x1 + 0x2 + 0x3 + 0s1 + 0s2 + (–A1) + (–A2)


Subject to
8x1 + 16x2 + 12x3 + s1 = 250
4x1 + 8x2 + 10x3 – s2 + A1 = 80
7x1 + 9x2 + 8x3 + A2 = 105
x1, x2, x3, s1, s2, A1, A2 ³ 0
Equating x1, x2, x3, s2 to zero.

Initial basic feasible solution

s1 = 250, A1= 80, A2 = 105

Table 1

  cj 0 0 0 0 0 -1 -1 Ratio
cB X B x1 x2 x3 s1 s2 A1 A2 B/x3
0 s1 250 8 16 12 1 0 0 0 250/12
-1 A1 80 4 8 10 0 -1 1 0 8
-1 A2 105 7 9 8 0 0 0 1 105/8
zj–cj   -11 -17 -18 0 1 0 0  

Since zj–cj values are not positive. Iteration will go further.


-18 is the smallest value among zj–cj values, thus x3 is the key column.
8 is the smallest positive value among the ratio, thus A1 is the key row.
Pivot Element = 10
A1 departs and x3 enters.

Table 2
Use the following formula to calculate the value for new table.
New Row (R2) = Old Row (R2) / Pivot Element (10)
New Row (R1) = Old Row (R1) – key column value of old Row R1 (12) * New Row (R2)
New Row (R3) = Old Row (R3) – key column value of old Row R3 (8) * New Row (R2)

  cj 0 0 0 0 0 -1 Ratio
cB Basic variables x1 x2 x3 s1 s2 A2 B/x1
X B
0 s1 154 16/5 32/5 0 1 6/5 0 48
0 x3 8 2/5 4/5 1 0 -1/10 0 20
-1 A2 41 19/5 13/5 0 0 4/5 1 10
zj-cj   -19/5 -13/5 0 0 -4/5 0  

A2 departs and x1 enters.


Here, Phase 1 terminates because both the artificial variables have been removed from the basis.

Phase 2

The basic feasible solution at the end of Phase 1 computation is used as the initial basic feasible solution of the
problem. The original objective function is introduced in Phase 2 computation and the usual simplex procedure is
used to solve the problem.

Table 3
Use the following formula to calculate the value for new table.
New Row (R3) = Old Row (R3) / Pivot Element (19/5)
New Row (R1) = Old Row (R1) – key column value of old Row R1 (16/5) * New Row (R3)
New Row (R2) = Old Row (R2) – key column value of old Row R2 (2/5) * New Row (R3)

   cj 12 15 9 0 0 Ratio
cB Basic variables B x1 x2 x3 x4 x5 B/x2
X
0 x4 2270/19 0 80/19 0 1 10/19 28
9 x3 70/19 0 10/19 1 0 -7/38 7
12 x1 205/19 1 13/19 0 0 4/19 15
zj-cj    0 -39/19 0 0 33/38  

x3 departs and x2 enters.

Table 4
Use the following formula to calculate the value for new table.
New Row (R2) = Old Row (R2) / Pivot Element (10/19)
New Row (R1) = Old Row (R1) – key column value of old Row R1 (80/19) * New Row (R2)
New Row (R3) = Old Row (R3) – key column value of old Row R3 (13/19) * New Row (R2)

   cj 12 15 9 0 0  
cB Basic variables x1 x2 x3 x4 x5 Solution values
B b (= XB)
0 x4 0 0 -8 1 2 90
15 x2 0 1 19/10 0 -7/20 7
12 x1 1 0 -13/10 0 9/20 6
zj-cj    0 0 39/10 0 3/20  

The optimal solution is:


x1 = 6, x2 = 7, x3 = 0
z = 12 X 6 + 15 X 7 + 9 X 0 = 177.

Two Phase Method Two phase Method Maximize z = 12x1 + 15x2 + 9x3 Subject to 8x1 + 16x2 + 12x3 <= 250 4x1 + 8x2 + 10x3 >=80 7x
A1 departs and x3 enters. Table 2 Use the following formula to calculate the value for new table. New Row (R2) = Old Row (R2)
cB Basic variables B x1 x2 x3 x4 x5 Solution values b (= XB) 0 x4 0 0 -8 1 2 90 15 x2 0 1 19/10 0 -7/20 7 12 x1 1 0 -13

You might also like