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, as we have seen, is to change the sign of objective function to get a minimization problem and, after, put the slack variables x4, x5, x6 to transform the inequalities into 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, so we can identify a 3x3 identity submatrix into constraints 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 , we 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

Fase 1

Basis
x7
x8
x9
Xb
10
15
4
Cb
1
1
1
000000111
321100100
233010010
11-100-1001
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 1st. index in the basis, ie, x7
So following 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 anm subtract the ani element multiplies by anj element divided by the pivot, for example for 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
1
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

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
0
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

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

Phase 2

Lets go to the second phase, we eliminate the artificial variables and replace the original objective function, this is rebuild the table as.

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

So we reach at the end of Phase 2, because the output condition holds. 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

Admin:

2016-11-21 04:38:36
Hi Elindor.

It is logic to obtaing same solution.
Theory says that artificial variables are used to have an square identity mxm submatrix and so intialize simplex algorithm

Extreme points set is the same in both and orignal problem does not change.

Elindor:

2016-11-21 04:38:36
Pranavan is actually correct -- While the solution given is NOT misleading in any way, one may indeed ignore the artificial variables x7 and x8 of the example, since one can start straight away from I={x4, x5, x9} J={x1, x2, x3, x6} (Thus ignoring x7 and x8)

This will lessen the ammount of steps taken and gives out the same result.

A validated example can be found at http://optlab.mcmaster.ca/feng/4O03/Two.Phase.Simplex.pdf , where only two artificial variables were used.

ToStand:

2016-04-19 14:17:14
thanks a lot

Admin:

2016-02-19 22:30:54
Hi Pranavan.
It's you, who mislead.
Please, read the post. On specially, read the wording!!!

Pranavan:

2016-02-15 13:45:04
No need to add artificial variables for <= sign. That is really redundant there. Please correct this post. This will be misleading for others.

sangeetha:

2016-01-22 09:05:13
wow its really nice i have confusion in selecting the artificial variable for starting basic feasible solution, but now it is cleared.

Satishk:

2013-01-30 06:28:13
This is really helpful.. Thank you lot

Carlos:

2012-12-28 17:43:09
Hi 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!

fatima:

2012-12-28 07:39:53
im also having the same problem like priya which is adding slack and artificial variable at a time.

Gandalf:

2012-11-26 09:32:21
Hi 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

priya:

2012-11-25 19:06:38
hi, 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

Charles:

2012-11-07 15:24:35
Hi 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!

Kareca:

2012-11-07 15:24:35
Nice example.

Any other worker example where see how to raise linear programming problem?

Thanks!




Post here