Simplex algorithm - phase one - why do I need to use it here?

[wanderlust.xx]

Hello everyone, I hope I've posted in the right section!

I have the following linear program. All I've done is added my slack variables (w) and made each constraint the subject, as you do.

\mathrm{maximize} \ z=x_1+3x_2 \<br /> <br /> w_1 = -3 + x_1 + x_2 \\<br /> <br /> w_2 = -1 + x_1 - x_2 \\<br /> <br /> w_3 = 4 - x_1 -2x_2

This seems a rather silly question, but I was lead to believe that I need to run the phase one method if the linear program is infeasible - ie, if either if the objective z value is completely negative (so we can't improve on it) or if I can't find an initial basis to start the simplex algorithm.

However, in this case, can't I let x_2 enter, then as a result, w_3 is my pivot row so w_3 leaves so we can now start with the simplex?

I have no idea why the latex isn't working... I've added new lines but it certainly isn't cooperating.

http://imageshack.us/m/51/7668/phasei.png

This is what I meant.

(I've also not really followed the template since... well, it's not really an actual homework, more of a passing query, and I can't really attempt a query :P )

 

[Ray Vickson]

Hello everyone, I hope I've posted in the right section!

I have the following linear program. All I've done is added my slack variables (w) and made each constraint the subject, as you do.

\mathrm{maximize} \ z=x_1+3x_2 \<br /> <br /> w_1 = -3 + x_1 + x_2 \\<br /> <br /> w_2 = -1 + x_1 - x_2 \\<br /> <br /> w_3 = 4 - x_1 -2x_2

This seems a rather silly question, but I was lead to believe that I need to run the phase one method if the linear program is infeasible - ie, if either if the objective z value is completely negative (so we can't improve on it) or if I can't find an initial basis to start the simplex algorithm.

However, in this case, can't I let x_2 enter, then as a result, w_3 is my pivot row so w_3 leaves so we can now start with the simplex?

I have no idea why the latex isn't working... I've added new lines but it certainly isn't cooperating.

http://imageshack.us/m/51/7668/phasei.png

This is what I meant.

(I've also not really followed the template since... well, it's not really an actual homework, more of a passing query, and I can't really attempt a query :P )

Are all your variables supposed to be >= 0? That is normally (but not always) the case in linear programming. Anyway, I will assume that.

The first order of business is to get a feasible starting point (or to demonstrate that no feasible solution exists). With equation system written by putting all w_i on the left, as you have done, you get the initial *infeasible* basic solution w_1 = -3, w_2 = -1, w_3 = 4. Here the variables w_i are all basic and x_1, x_2 are nonbasic = 0. This solution is infeasible because some w_i are < 0. Increasing x_1 increases both w_1 and w_2. Normally, one would need a few iterations, but in this case the problem is so simple that we can spot a basic feasible solution immediately: as x_1 increases to 3 (holding x_2 = 0), w_1 hits zero, w_2 becomes positive and w_3 remains positive. So, let w_1 become nonbasic and x_1 basic. The new solution will be feasible, with positive (basic) variables x_1, w_2, w_3 and zeo (nonbasic) variables w_1, x_2.

Your question about whether or not Phase I is needed is relevant to *some* (but not all) implementations of the simplex method. Some of the better ones just try to eliminate infeasibilities one-by-one in roughly the method done above (except that I did two steps for the price of 1) and avoid artificial variables and explicit Phase I objectives altogether. Artificial variables and Phase I are always used in introductory courses, but not always in industrial-scale computer codes.

RGV

 

[wanderlust.xx]

Ah I see! So essentially, the slack variables w_i are negative when we proceed with the simplex which means that we can't actually run the simplex algorithm because we do not have an initial basic feasible solution. Is this correct?

 

[Ray Vickson]

Ah I see! So essentially, the slack variables w_i are negative when we proceed with the simplex which means that we can't actually run the simplex algorithm because we do not have an initial basic feasible solution. Is this correct?

I don't know what you mean by saying "we proceed with simplex which means that we can't actually run the simplex algorithm", which seems contradictory. I would say instead: we cannot start *maximizing* (or minimizing) until we have achieved a feasible solution. In other words, until we have obtained a feasible solution we effectively neglect the actual objective. Actually, this is not quite true. In some sophisticated implementations, we try to guide the path to feasibility by also looking at the effects on the objective, so that if there are two nonbasic variables that would each lessen the amount of infeasibility, we could choose the one that hurts the objective the least, or helps it the most. Essentially, the so-called "Big-M" method attempts something like this, but in a clumsy way IMHO.

RGV