Example 3 (Simplex Method)
Solve the following LPP by Simplex Method
Minimize Z=-3+3
Subject to
3-+2≤ 7
2+4≥ -12
-4+3+8≤10
and , , ≥ 0
Standard Form of LPP
Minimize Z=-3+3+0+0+0
Subject to
3-+2+ 7
-24+ 12
-4+3+8+10 and
, , , ,,≥ 0
ITERATIO
N1
Basic RHS RATIO
Variable
3 -1 2 1 0 0 7 -
-2 -4 0 0 1 0 12 -
-4 (3) 8 0 0 1 10
Z -1 3 -3 0 0 0 0
This current BFS is not Optimal.
is the Entering Variable,
is the leaving Variable
Pivot Element is 3
ITERATION 2
Basic RHS RATIO
Variable
() 0 1 0
0 0 1 -
1 0 0 -
Z 3 0 -11 0 0 -1 -10
This current BFS is not Optimal.
is the Entering Variable,
is the leaving Variable
Pivot Element is
ITERATION 3
Basic RHS
Variable
1 0 0
0 0 1
0 1 0
Z 0 0 0
This current BFS is Optimal.
Optimal BFS : = and
Minimum Z value =
Introduction of Two-phase
method
When a Initial basic feasible solution is not readily available,
the two-phase simplex method may be used to solve the
mixed constraints LPP
It is one of the method to solve a given LPP involving some
artificial variables
This Method solves the LPP in Two Phases: Phase I attempts to
find a starting BFS and if one is found, Phase II is invoked to
solve the given problem
Phase I : In this phase, construct an auxiliary LPP leading to a optimal simplex
table containing a Basic feasible solution to the given LPP.
Steps
1. Write the standard form of given LPP and then add artificial variables to the
(≥)type and (=) type constraints.
2. Form the auxiliary LPP, the objective function is to minimize the sum of all
artificial variables subject to constraints of given LPP.
3. Find a basic feasible solution to the given LPP by solving the auxiliary LPP.
4. i) If the objective function value of auxiliary LPP is zero and no artificial
variable appears as basic variable in the Optimal Table, Go to Phase II.
ii) If auxiliary LPP objective function value is not equal to zero, the given
LPP does not possess any feasible solution. STOP.
Two Phase Simplex Method
Remarks:
The removal of artificial variables and their column at the end of Phase I can take place
only when they are all nonbasic. If one or more artificial variables are basic ( at zero
level) at the end of Phase I, then the following additional steps must be under taken to
remove them prior to start Phase II
Step 1. Select a zero artificial variable to leave the basic solution and designate its row
as pivot row. The entering variable can be any nonbasic (non artificial) variable with
nonzero (positive or negative) coefficient in the pivot row. Perform the associated
simplex iteration.
Step 2. Remove the column of the (Just-leaving) artificial from the tableau. If all the
zero artificial variables have been removed , go to Phase II.
Otherwise, go back to Step I.
Phase II
Steps
1. Take the Optimal simplex table of Phase I as a Initial Simplex table .
2. Replace the artificial objective function row (i.e.,r-row )by the given
LPP objective function.
3. Apply simplex method to the modified simplex table to find the
Optimal Basic Feasible Solution(if it exists)
Two Phase Simplex Method
Example 1
Minimize z 4 x1 x2
Subject to:
3 x1 x2 3
4 x1 3 x2 6
x1 2 x2 4
x1 , x2 0
Solution:
Phase I: AUXIALIARY LPP
Minimize: r R1 R2
Subject to:
3x1 x2 R1 3
4 x1 3x2 x3 R2 6
x1 2 x2 x4 4
x1 , x2 , x3 , x4 , R1 , R2 0
Here and are the artificial variables and is the slack
variable, is the surplus variable
Iteration 1
RHS x4 R2 R1 x3 x2 x1 Basic
variable
3 0 0 1 0 1 3 R1
6 0 1 0 1- 3 4 R2
4 1 0 0 0 2 1 x4
9 0 1- 1- 0 0 0 r
New r-row = Old r-row + 1* R1-row + 1*R2 -row
RHS x4 R2 R1 x3 x2 x1 Basic
variable
3 0 0 1 0 1 3 R1
6 0 1 0 1- 3 4 R2
4 1 0 0 0 2 1 x4
9 0 0 0 1- 4 7 r
By using new r-row, we solve Phase I of the problem which yields
the following optimum tableau
RHS x4 R2 R1 x3 x2 x1 Basic
variable
3/5 0 1/5- 3/5 1/5 0 1 x1
6/5 0 3/5 4/5- 3/5- 1 0 x2
1 1 1- 1 1 0 0 x4
0 0 1- 1- 0 0 0 r
Because minimum r=0, Phase I produces the basic
feasible solution:
6
x1 , x2 , and x4 1
3
5
5
Phase II
After eliminating artificial variables column, the original
problem can be written as:
Minimize: z 4 x1 x2
Subject to:
and
RHS x4 x3 x2 x1 Basic
variable
3/5 0 1/5 0 1 x1
6/5 0 3/5- 1 0 x2
1 1 1 0 0 x4
0 0 0 1- 4- z
Again, because basic variables x1 and x2 have nonzero
coefficient in the z row, they must be substituted out,
using the following computation:
New z-row = Old z-row + 4* x1-row + 1*x2 -row
Phase II
The initial tableau of Phase II is as the following:
RHS x4 x3 x2 x1 Basic
variable
3/5 0 1/5 0 1 x1
6/5 0 3/5- 1 0 x2
1 1 1 0 0 x4
18/5 0 1/5 0 0 z
The current BFS is not Optimal
is the entering variable
is the leaving variable
1 is the pivot element
Phase II
Iteration 2:
RHS x4 x3 x2 x1 Basic
variable
2/5 0 0 1 x1
9/5 0 1 0 x2
1 1 1 0 0
17/5 0 0 0 z
The current BFS is Optimal. The optimal BFS is
=
=
Minimum Z value =
Example 2 (Two Phase Simplex
Method)
Solve the following LPP:
Maximize Z=3+2+3
Subject to
2++≤ 2
3+4+2≥ 8 and ≥ 0
Phase I
Auxiliary LPP
Minimise r=R
Subject to
2+++= 2
3+4+2-+R = 8 and R ≥ 0
Phase I
Iteration 1
Basic RHS
Variable
2 (1) 1 0 1 0 2
R 3 4 2 -1 0 1 8
r 3 4 2 -1 0 0 8
Phase I
Iteration 2
Basic RHS
Variable
2 1 1 0 1 0 2
R -5 0 -2 -1 -4 1 0
r -5 0 -2 -1 -4 0 0
Since r=0 and artificial variable R appears in the Phase I Optimal table at
zero level, Go to Phase II
Phase II
Iteration 1(Replace the last row in the Optimal table of Phase I by given
LPP Objective function)
Basic RHS
Variable
2 1 1 0 1 2
R -5 0 -2 -1 -4 0
Z 1 0 -1 0 2 4
This table is not optimal
is the entering variable
R is the leaving variable
-2 is the pivot element
Phase II
Iteration 2
Basic RHS
Variable
2 1 1 0 1 2
2.5 0 1 0.5 2 0
Z 3.5 0 0 0.5 4 4
This table is optimal
Optimal BFS : = 0; =2; =0 with Maximum Z value=4
NOTES FOR SIMPLEX TABLE
1. If there is a zero under one or more nonbasic variables in the last tableau (optimal
solution tableau), then there is a multiple optimal solution.
2. When determining the leaving variable of any tableau, if there is no positive ratio (all the
entries in the pivot column are negative and zeroes), then the solution is unbounded.
3. If there is a tie in determining the leaving variable, choose any one to be the leaving
variable. In this case a zero will appear in RHS column; therefore, a “cycle” will occur, this
means that the value of the objective function will be the same for several iterations.
4. A Solution that has a basic variable with zero value is called a “degenerate solution”.
5. If there is no Artificial variables in the problem, there is no room for “infeasible solution”
24
Example (Degenerate Optimal Solution)
Maximize Z = 3+9
Subject to
+4≤ 8
+2≤ 4 and , ≥ 0
Example (Infinite Number of Solutions)
Maximize Z=2+4
Subject to
+2≤ 5
+ and ,≥ 0
Example (Unbounded Solution)
Maximize Z= 2+
Subject to
-≤ 10
2≤ 40 and , ≥ 0
Example (Infeasible Solution)
Maximize Z= 3+2
Subject to
2+≤ 2
3+4≥ 12 and , ≥ 0
29
