3/19/25, 9:30 PM Two-Phase method Infeasible solution example
We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more Accep
Support us
Try our new - Enter problem or search problem
Home What's new College Algebra Games
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems
Home > Operation Research calculators > Two-Phase method example
3. Two-Phase method example ( Enter your problem )
Other related methods
1. Algorithm & Example-1
2. Example-2 0. Formulate linear programming model
3. Example-3 1. Graphical method
4. Infeasible solution example 2. Simplex method (BigM method)
3. Two-Phase method
4. Primal to dual conversion
5. Dual simplex method
6. Integer simplex method
7. Branch and Bound method
8. 0-1 Integer programming problem
9. Revised Simplex method
3. Example-3 5. Primal to dual co
(Previous example) (Next m
4. Infeasible solution example
Infeasible solution
If there is no any solution that satifies all the constraints, then it is called Infeasible solution
In the final simplex table when all c j - z j imply optimal solution but at least one artificial variable present in the basis with positive
Then the problem has no feasible solution.
Example
Find solution using Two-Phase method
MIN Z = X1 - 2X2 - 3X3
subject to
-2X1 + X2 + 3X3 = 2
2X1 + 3X2 + 4X3 = 1
and X1,X2,X3 >= 0
Solution:
Problem is
Min Z = X 1 - 2 X 2 - 3 X 3
subject to
- 2 X1 + X2 + 3 X3 = 2
2 X1 + 3 X2 + 4 X3 = 1
and X 1, X 2, X 3 ≥ 0;
-->Phase-1<--
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate
1. As the constraint-1 is of type ' = ' we should add artificial variable A 1
2. As the constraint-2 is of type ' = ' we should add artificial variable A 2
After introducing artificial variables
Min Z = A1 + A2
subject to
- 2 X1 + X2 + 3 X3 + A1 =2
X X
2 1 + 3 2 + 4 3 X A
+ 2=1
Modelica-based Simulation - Cloud Simulation Platform
and X 1, X 2, X 3, A 1, A 2 ≥ 0 OPEN
Open standards based physical system simulation. Modelon
[Link] 1/3
3/19/25, 9:30 PM Two-Phase method Infeasible solution example
Iteration-1 Cj 0 0 0 1 1
MinRatio
CB XB X1 X2 X3 A1 A2 XB
B
X3
2
A1 1 2 -2 1 3 1 0 = 0.6667
3
1
A2 1 1 2 3 (4) 0 1 = 0.25 →
4
Z=0 Zj 0 4 7 1 1
Cj - Zj 0 -4 -7 ↑ 0 0
Negative minimum C j - Z j is - 7 and its column index is 3. So, the entering variable is X 3.
Minimum ratio is 0.25 and its row index is 2. So, the leaving basis variable is A 2.
∴ The pivot element is 4.
Entering = X 3, Departing = A 2, Key Element = 4
R 2(new) = R 2(old) ÷ 4
R 1(new) = R 1(old)- 3R 2(new)
Iteration-2 Cj 0 0 0 1
B CB XB X1 X2 X3 A1 MinRatio
5 7 5
A1 1 - - 0 1
4 2 4
1 1 3
X3 0 1 0
4 2 4
7 5
Z=0 Zj - - 0 1
2 4
7 5
Cj - Zj 0 0
2 4
Since all C j - Z j ≥ 0
Hence, optimal solution is arrived with value of variables as :
1
X 1 = 0, X 2 = 0, X 3 =
4
Min Z = 0
But this solution is not feasible
because the final solution violates the 1 st constraint - 2 X 1 + X 2 + 3 X 3 = 2.
5
and the artificial variable A 1 appears in the basis with positive value
4
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here
3. Example-3 5. Primal to dual co
(Previous example) (Next m
[Link] 2/3
3/19/25, 9:30 PM Two-Phase method Infeasible solution example
Share this solution or page with your friends.
Home What's new College Algebra Games
Copyright © 2025. All rights reserved. Terms, Privacy
.
.
[Link] 3/3