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
000000111
321100100
233010010
11-1001001
66311-1000

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
000000111
12/31/31/3001/300
05/37/3-2/310-2/310
11/3-4/3-1/30-1-1/301
021-11-1-200

We make another iteration

Basis
x1
x8
x2
Xb
2
5
2
Cb
0
1
0
000 000 111
1031021 0-2
0091151 1-5
01-4-10-3 -103
009 115 006

Entering at basis x3, leaves x8, new iteration

Basis
x1
x3
x2
Xb
1/3
5/9
38/9
Cb
0
1
0
000 000 111
1002/3-1/31/32/3 -1/3-1/3
0011/91/95/91/9 1/9-5/9
010-5/94/9-7/9 -5/94/97/9
000 000 -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 000
1002/3-1/31/3
0011/91/95/9
010-5/94/9-7/9
000 -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