 # Linear programming examples

### Complete example of the two-phase method

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 x4, x5, x6 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 x7, x8, x9 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

### Phase 1

 Basis x7 x8 x9
 Xb 10 15 4
 Cb 1 1 1
 0 0 0 0 0 0 1 1 1 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 6 6 3 1 1 -1 0 0 0

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

 Basis x1 x8 x9
 Xb 10/3 25/3 2/3
 Cb 0 1 0
 0 0 0 0 0 0 1 1 1 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 0 2 1 -1 1 -1 -2 0 0

We make another iteration

 Basis x1 x8 x2
 Xb 2 5 2
 Cb 0 1 0
 0 0 0 0 0 0 1 1 1 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 0 0 9 1 1 5 0 0 6

Entering at basis x3, leaves x8, new iteration

 Basis x1 x3 x2
 Xb 1/3 5/9 38/9
 Cb 0 1 0
 0 0 0 0 0 0 1 1 1 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 0 0 0 0 0 0 -1 -1 -1

Thus we arrive at the end of first phase with the solution x7, x8, x9=0 and maximizing trivial zero.

### Phase 2

We go to the second phase, we eliminate the artificial variables and replace the original objective function, thus rebuild the table.

 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 -5/9 4/9 -7/9 0 0 0 -1/9 -11/9 -5/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!

## Was useful? want add anything?

Post here

### Post from other users

Post here 