Les consider a problem as follows
Maximize (2x1 + 3x2 + 4 x3)
Subject to
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≤ 4
x1, x2, x3 ≥ 0
The first thing to do is, as always, sign change the objective function for a minimization problem and put the slack variables x
4, x
5, x
6 to transform the inequalities to equalities
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
Now we introduce artificial variables x
7, x
8, x
9 have a 3x3 identity submatrix constraint matrix
Minimize (-2x1 - 3x2 - 4 x3)
Subject to
3x1 + 2x2 + x3 + x4 + x7 = 10
2x1 + 3x2 + 3 x3 + x5 + x8 = 15
x1 + x2 - x3 - x6 + x9 = 4
xi ≥ 0, , ∀ i=1,2, ..,9
We already have a 3x3 identity submatrix can start first phase the two-phase method, for it changed the objective function, ie we consider
Minimize (x7 + x8 + x9)
Subject to
3x1 + 2x2 + x3 + x4 + x7 = 10
2x1 + 3x2 + 3 x3 + x5 + x8 = 15
x1 + x2 - x3 - x6 + x9 = 4
xi ≥ 0, , ∀ i=1,2, ..,9
3 | 2 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
2 | 3 | 3 | 0 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | -1 | 0 | 0 | 1 | 0 | 0 | 1 |
The pivot element is 3 because 6 is the maximum of the positive zj - cj, its index is 1 and so, the entering variable is x 1 also
3 / 10 = min (10/3, 15/2, 4/1), so the leaving basis variable is those occupying 1 index in the basis the base, ie, x7
So as the names that we used in the theory k=1 and the index i=1
and the pivot element is on the index aik = a11
So do one iteration of the simplex algorithm as follows:
1) On the pivot row simply divide each element by the pivot element (including himself)
2) For the other rows are operating as we have seen in the theory: for the item to nm subtract the ani element multiplies by anj element divided by the pivot, for example, the complete second 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)
-2/3 = 0 - (2*1/3)
1 = 1 - (1*0/3)
0 = 1 - (2*0/3)
the table transforms to
1 | 2/3 | 1/3 | 1/3 | 0 | 0 | 1/3 | 0 | 0 |
0 | 5/3 | 7/3 | -2/3 | 1 | 0 | -2/3 | 1 | 0 |
1 | 1/3 | -4/3 | -1/3 | 0 | -1 | -1/3 | 0 | 1 |
We make another iteration
1 | 0 | 3 | 1 | 0 | 2 | 1 |
0 | -2 |
0 | 0 | 9 | 1 | 1 | 5 | 1 |
1 | -5 |
0 | 1 | -4 | -1 | 0 | -3 |
-1 | 0 | 3 |
Entering at basis x3, leaves x8, new iteration
1 | 0 | 0 | 2/3 | -1/3 | 1/3 | 2/3 |
-1/3 | -1/3 |
0 | 0 | 1 | 1/9 | 1/9 | 5/9 | 1/9 |
1/9 | -5/9 |
0 | 1 | 0 | -5/9 | 4/9 | -7/9 |
-5/9 | 4/9 | 7/9 |
Thus we arrive at the end of first phase with the solution x7, x8, x9=0 and maximizing trivial zero.
We go to the second phase, we eliminate the artificial variables and replace the original objective function, thus rebuild the table.
1 | 0 | 0 | 2/3 | -1/3 | 1/3 |
0 | 0 | 1 | 1/9 | 1/9 | 5/9 |
0 | 1 | 0 | -5/9 | 4/9 | -7/9 |
This then at the end of Phase 2, as it gives the output condition. We have a finite optimal solution
x1 = 1/3 |
x2 = 38/9 |
x3 = 5/9 |
with an optimal value (remember to re-change the sign the objetive function)
2 * 1/3 |
+ 3 * 38/9 |
+ 4 * 5/9 |
= 140/9 |
Execute it here!