Complex example of two phase method
Math and science in a lapse of, euler s method matlab program code with c, phase 1 simplex method university of waterloo, revised simplex method part 2, the two phase simplex method 1 authorstream, introduction to linear optimization and extensions with, some simplex method examples mathematics, solving linear programs using the simplex method. This is a description of a Matlab function called nmasimplex.m that implements the matrix based simplex algorithm for solving standard form linear programming problem. It supports phase one and phase two.
Lets consider following L.P. problem:
Subject to
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≥ 4
x1, x2, x3 ≥ 0
Subject to
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5= 15
x1 + x2 - x3 - x6 = 4
xi ≥ 0, ∀ i=1,2, ..,6
L.P. transforms as follows
Subject to
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5 = 15
x1 + x2 - x3 - x6 + x7 = 4
xi ≥ 0, , ∀ i=1,2, ..,7
Subject to
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5 = 15
x1 + x2 - x3 - x6 + x7 = 4
xi ≥ 0, , ∀ i=1,2, ..,7
Phase 1
| Basis |
| x4 |
| x5 |
| x7 |
| Xb |
| 10 |
| 15 |
| 4 |
| Cb |
| 0 |
| 0 |
| -1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 3 | 2 | 1 | 1 | 0 | 0 | 0 |
| 2 | 3 | 3 | 0 | 1 | 0 | 0 |
| 1 | 1 | -1 | 0 | 0 | -1 | 1 |
| -1 | -1 | 1 | 0 | 0 | 1 | 0 |
10/3 = min (10/3, 15/2, 4/1), so, leaving variable is those at index 1 of C, thus x4.
So, naming that we have use in theory, we have k=1 and index i=1 Pivot element is on aik = a11
We do an iteration of the simplex algorithm in the following way;
Matlab Code For Phase 2 Simplex Methods
1) If the row is that of the pivot element, we simply divide each element by the pivot element (including the same).
2) For the other rows we operate as we have seen in the theory: for the element anm rest ani multiply for anj and we divide by the pivot element, for example, p the second full row:
| 25/3 = 15-(2*10/3) |
| 0 = 2-(2*3/3) |
| 5/3 = 3-(2*2/3) |
| 7/3 = 3-(2*1/3) |
| -2/3 = 0 - (2*1/3) |
| 1 = 1 - (2*0/3) |
| 0 = 0 - (2*0/3) |
| 0 = 0 - (1*0/3) |
As you can see, the calculations are easier to understand and do than to explain.
Tableau transforms to
| Basis |
| x1 |
| x5 |
| x7 |
| Xb |
| 10/3 |
| 25/3 |
| 2/3 |
| Cb |
| 0 |
| 0 |
| -1 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 2/3 | 1/3 | 1/3 | 0 | 0 | 0 |
| 0 | 5/3 | 7/3 | -2/3 | 1 | 0 | 0 |
| 0 | 1/3 | -4/3 | -1/3 | 0 | -1 | 1 |
| 0 | -1/3 | 4/3 | 1/3 | 0 | 1 | 0 |
Next iteration
| Basis |
| x1 |
| x5 |
| x2 |
| Xb |
| 2 |
| 5 |
| 2 |
| Cb |
| 0 |
| 0 |
| 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 3 | 1 | 0 | 2 | -2 |
| 0 | 0 | 9 | 1 | 1 | 5 | -5 |
| 0 | 1 | -4 | -1 | 0 | -3 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
So, we have reached the end of the first phase with the solution x7=0 and the best value obtained is the trivial one. Thus, we can forward to second phase.
Phase 2
We go on the second phase, we eliminate the artificial variables and we reestablish the original function, that is, we reconstruct the table as follows.
| Basis |
| x1 |
| x3 |
| x2 |
| Xb |
| 1/3 |
| 5/9 |
| 38/9 |
| Cb |
| -2 |
| -4 |
| -3 |
| -2 | -3 | -4 | 0 | 0 | 0 |
| 1 | 0 | 3 | 1 | 0 | 2 |
| 0 | 0 | 9 | 1 | 1 | 5 |
| 0 | 1 | -4 | -1 | 0 | -3 |
| 0 | 0 | -10 | -1 | 0 | -5 |
Next iteration 2.
| Basis |
| x1 |
| x3 |
| x2 |
| Xb |
| 1/3 |
| 5/9 |
| 38/9 |
| Cb |
| -2 |
| -4 |
| -3 |
| -2 | -3 | -4 | 0 | 0 | 0 |
| 1 | 0 | 0 | 2/3 | -1/3 | 1/3 |
| 0 | 0 | 1 | 1/9 | 1/9 | 5/9 |
| 0 | 1 | 0 | 1/9 | 10/9 | 5/9 |
| 0 | 0 | 0 | 1/9 | 10/9 | 5/9 |
Thus, we have reached the end of phase 2 because the optimality criterion holds. We have finite optimum solution at the extreme point of coordinates
| x1 = 1/3 |
| x2 = 38/9 |
| x3 = 5/9 |
with the optimal value (remember to change the original objective function again)
| 2 * 1/3 | + 3 * 38/9 | + 4 * 5/9 | = 140/9 |
Execute here!
Was useful? want add anything?
Post here
Post from other users
Kareca:
2012-11-07 15:24:35Nice example.
Any other worker example where see how to raise linear programming problem?
Thanks!
Charles:
2012-11-07 15:24:35Hi Kareka.You have other complete example at this same site on this URLhttp://www.mathstools.com/section/main/simplex_method_exampleI hope to be useful!Good Luck!
priya:
2012-11-25 19:06:38hi, i want the solved problem in two phase method which contain subject of constraints as in both slack and artificial variable in the same problem
Gandalf:
2012-11-26 09:32:21Hi priya.
Would you can to write here your problem?
you have a on line solver at
http://www.mathstools.com/section/main/simplex_online_calculator
fatima:
2012-12-28 07:39:53im also having the same problem like priya which is adding slack and artificial variable at a time.
Phase 2 Reopening New York
Carlos:
2012-12-28 17:43:09Hi Fatima.
Have you seen the example at
http://www.mathstools.com/section/main/Two-phase_Method_Example
It is solved by adding both, artificial and slack variables at two first steps.
Also you have the calculator on line at
http://www.mathstools.com/section/main/simplex_online_calculator
To use it, there is not need to input artificial nor slack variables, it does it authomatically.
Any problem, please write here your LPP problem.
Good Luck!
Satishk:
2013-01-30 06:28:13This is really helpful.. Thank you lot
Matlab Code For Phase 2 Simplex Method Pdf
sangeetha:
2016-01-22 09:05:13wow its really nice i have confusion in selecting the artificial variable for starting basic feasible solution, but now it is cleared.
LIVIS LIQUORO:
2018-12-09 05:45:27yeah,it is so helpful. each confusion have resolved.
Phase 2 Massachusetts
Post here