Subject to

3x1 + 2x2 + x3 ≤ 10

2x1 + 3x2 + 3 x3 ≤ 15

x1 + x2 - x3 ≥ 4

x1, x2, x3 ≥ 0

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

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

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

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

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

Basis |

x7 |

x8 |

x9 |

Xb |

10 |

15 |

4 |

Cb |

1 |

1 |

1 |

0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |

3 | 2 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |

2 | 3 | 3 | 0 | 1 | 0 | 0 | 1 | 0 |

1 | 1 | -1 | 0 | 0 | -1 | 0 | 0 | 1 |

6 | 6 | 3 | 1 | 1 | -1 | 0 | 0 | 0 |

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 |

0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |

1 | 2/3 | 1/3 | 1/3 | 0 | 0 | 1/3 | 0 | 0 |

0 | 5/3 | 7/3 | -2/3 | 1 | 0 | -2/3 | 1 | 0 |

1 | 1/3 | -4/3 | -1/3 | 0 | -1 | -1/3 | 0 | 1 |

0 | 2 | 1 | -1 | 1 | -1 | -2 | 0 | 0 |

Another iteration

Basis |

x1 |

x8 |

x2 |

Xb |

2 |

5 |

2 |

Cb |

0 |

1 |

0 |

0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |

1 | 0 | 3 | 1 | 0 | 2 | 1 | 0 | -2 |

0 | 0 | 9 | 1 | 1 | 5 | 1 | 1 | -5 |

0 | 1 | -4 | -1 | 0 | -3 | -1 | 0 | 3 |

0 | 0 | 9 | 1 | 1 | 5 | 0 | 0 | 6 |

Entering at basis x3, leaves x8, new iteration

Basis |

x1 |

x3 |

x2 |

Xb |

1/3 |

5/9 |

38/9 |

Cb |

0 |

0 |

0 |

0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |

1 | 0 | 0 | 2/3 | -1/3 | 1/3 | 2/3 | -1/3 | -1/3 |

0 | 0 | 1 | 1/9 | 1/9 | 5/9 | 1/9 | 1/9 | -5/9 |

0 | 1 | 0 | -5/9 | 4/9 | -7/9 | -5/9 | 4/9 | 7/9 |

0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 |

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

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

1 | 0 | 0 | 2/3 | -1/3 | 1/3 |

0 | 0 | 1 | 1/9 | 1/9 | 5/9 |

0 | 1 | 0 | -5/9 | 4/9 | -7/9 |

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

Post here

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.

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.

thanks a lot

Hi Pranavan.

It's you, who mislead.

Please, read the post. On specially, read the wording!!!

No need to add artificial variables for <= sign. That is really redundant there. Please correct this post. This will be misleading for others.

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