Linear programming examples

Complex example of two phase method

Lets consider following L.P. problem:
Maximize (2x1 + 3x2 + 4 x3)
Subject to
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≥ 4
x1, x2, x3 ≥ 0
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
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
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
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

Phase 1

Basis
x4
x5
x7
Xb
10
15
4
Cb
0
0
-1
0000001
3211000
2330100
11-100-11
-1-110010

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
0001101
12/31/31/3000
05/37/3-2/3100
01/3-4/3-1/30-11
0-1/34/31/3010

Next iteration

Basis
x1
x5
x2
Xb
2
5
2
Cb
0
0
0
0000001
103102-2
009115-5
01-4-10-33
000 000 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 000
103 10 2
009 1 15
01-4 -10-3
00-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 000
1002/3 -1/3 1/3
0011/9 1/95/9
010 1/910/95/9
0001/910/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:35
Nice example.

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

Thanks!

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!

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

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

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.

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!

Satishk:

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

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.

ToStand:

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

LIVIS LIQUORO:

2018-12-09 05:45:27
yeah,it is so helpful. each confusion have resolved.




Post here
Update cookies preferences