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 | -10/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 Again, Pete.

Thanks to you!.

Exactly, you are right, all coefficients not negative implies output condition.

Also it is as you said, any positive coefficient implies any other(s) iteration(s) just at same mode as phase 1.

If you want, you can access to

http://www.mathstools.com/section/main/simplex_online_calculator

And make variations of this problem for get more iterations at phase two

Finally, only to say that if problem were a maximization problem (instead minimization) it would be the opposite: the: the output condition would happen when all coefficients were positive. This is how the dual method works.

Hi Admin!

Many thanks, I understand now. And we see that this is the end of Phase 2, because all results in bottom row now are non-positive, right?

What would happen if there were a positive result? We have to do then the same iterattion again, that we have done in phase 1? (I mean identifying a pivot element, divide each element by the pivot elements row and for other rows we use the same formula (for the item to anm subtract the ani element multiplies by anj element divided by the pivot)?

I just wondered what would we have to do if we didnt reach the output conditions this fast :)

Thanks again!

Hi, Pete.

The original C vector is called the costs vector, or function to maximize.

Original function to maximize is 2x1+3x2+4x3. Thus

C = (-2,-3,-4,0,0,0)

The change of sign is because we transformed the problem from maximize to minimize (more details at theory sections).

Last row is only formed by those elements called zj -cj. Again, theory says that such elements are formed by

zj -cj = Cbi. Aij-Cj

In our case, because variables at basis are x1, x2, x3, implies Cb=(-2,-4,-3).

original C is as said (-2,-3,-4,0,0,0). Now, to get last row is only to do the calculations

For example, to obtain the -1/9 we have that i=4 (thus A4j= 2/3, 1/9, -5/9) therefore:

-1/9 = -2 * (2/3) - 4 * (1/9) -3 * (-5/9) = -12/9 -4/9 +15/9 = 1/9.

Got it?

Hi!

Sorry I still dont get the final bottom row. What is original C vector? Can you explane please with the numbers, how did you get for example the -1/9 and -10/9 values in the last table, bottom row?

Thanks!

Hi Gabor, Thanks to you!

Such numbers results from calculate zj-Cj

Note that

zj -Cj = CbjAij - Cj

(being i, the pivot element file index).

now note that Cb=(-2,-4,-3), A(i)=(-1/3,1/9,4/9) and C is original C vector.

from here it is only make calculations.

Hi Admin!

I didn't notice the mistake, because i don't know how to get those numbers in the bottom row :) Can you explain that step by step?

Thanks in advance!

Hi Gabor!

You're right, there were a mistake, it is correct now!

Thanks!

Hi!

How did you get the last row of the last table? I can't figure out that 0;0;0;-1/9;-11/9;-5/9 row.

Thanks!

Hi manav.

Yes it is a misprint error.

It is correct now, thank you!

pls make a correction sr in table 3 last colmn last row should b -6 instead of 6 pls make me correct, if i m wrong pls inform me .thanks

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