Subject to

3x1 + 2x2 + x3 ≤ 10

2x1 + 3x2 + 3 x3 ≤ 15

x1 + x2 - x3 ≥ 4

x1, x2, x3 ≥ 0

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

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

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

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

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

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

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.

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!

Post here

thanks a lot

wow its really nice i have confusion in selecting the artificial variable for starting basic feasible solution, but now it is cleared.

This is really helpful.. Thank you lot

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!

im also having the same problem like priya which is adding slack and artificial variable at a time.

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

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

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!

Nice example.

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

Thanks!

Post here