Maximize (2x1 + 3x2 + 4 x3)
Subject to
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≥ 4
x1, x2, x3 ≥ 0
Subject to
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≥ 4
x1, x2, x3 ≥ 0
Linear programming examples
Complex example of two phase method
Lets consider following L.P. problem:
First of all, as we have seen, is to change the sign to objective function to have a minimization problem instead maximiazion. Alse we put all slack variables to
change inequalities at x4, x5, x6 into equalitites
Minimize (-2x1 - 3x2 - 4 x3)
Subject to
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5= 15
x1 + x2 - x3 - x6 = 4
xi ≥ 0, ∀ i=1,2, ..,6
Subject to
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5= 15
x1 + x2 - x3 - x6 = 4
xi ≥ 0, ∀ i=1,2, ..,6
Now, we want to have an identity 3x3 submatrix into constraints matrix. With this idea we introduce artificial variables.
It is enough to use one unique variable for third constraint, we call la llamamos x7.
L.P. transforms as follows
L.P. transforms as follows
Minimize (-2x1 - 3x2 - 4 x3)
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
Well, we can identify one identity 3x3 submatriz into A. With this we can to start iterations of two phase method.
Identity submatriz is those formed for columns corresponding to variables x4, x5, x7. Applying two phase method, we consider
Minimize (-x7)
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 |
Pivot element is 3 because -1 is most negative of zj - cj,
so 1, is the index of entering variable then x 1. Also
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;
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 URL http://www.mathstools.com/section/main/simplex_method_example I 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.
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
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.
ToStand:
2016-04-19 14:17:14thanks a lot
LIVIS LIQUORO:
2018-12-09 05:45:27yeah,it is so helpful. each confusion have resolved.
Post here
