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

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 \ w_1 = -3 + x_1 + x_2 \\ w_2 = -1 + x_1 - x_2 \\ 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 )

Related Precalculus Mathematics Homework Help News on Phys.org
Ray Vickson
Homework Helper
Dearly Missed
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 \ w_1 = -3 + x_1 + x_2 \\ w_2 = -1 + x_1 - x_2 \\ 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

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