 # 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
 0 0 0 0 0 0 1 3 2 1 1 0 0 0 2 3 3 0 1 0 0 1 1 -1 0 0 -1 1 -1 -1 1 0 0 1 0

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
 0 0 0 1 1 0 1 1 2/3 1/3 1/3 0 0 0 0 5/3 7/3 -2/3 1 0 0 0 1/3 -4/3 -1/3 0 -1 1 0 -1/3 4/3 1/3 0 1 0

Next iteration

 Basis x1 x5 x2
 Xb 2 5 2
 Cb 0 0 0
 0 0 0 0 0 0 1 1 0 3 1 0 2 -2 0 0 9 1 1 5 -5 0 1 -4 -1 0 -3 3 0 0 0 0 0 0 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 0 0 0 1 0 3 1 0 2 0 0 9 1 1 5 0 1 -4 -1 0 -3 0 0 -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 0 0 0 1 0 0 2/3 -1/3 1/3 0 0 1 1/9 1/9 5/9 0 1 0 1/9 10/9 5/9 0 0 0 1/9 10/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

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