2

My textbook introduces the following method to compute initial feasible basis in the simplex algorithm:

enter image description here

What is the implication for the original LP if the auxiliary LP's objective function can't attain the value $0$, or if it is infeasible?

ensbana
  • 2,277
  • What you've written down is known as "phase I" of the two-phase simplex algorithm and the x4, x5 are usually called artificial variables (not the same as surplus variables). – creanion Sep 06 '22 at 22:48

1 Answers1

1

If the auxiliary problem can’t attain the value zero, then the original problem is infeasible.

The auxiliary problem can’t be infeasible. For a general LP with constraints $Ax=b$ with $x\geq0$, the auxiliary problem has constraints $Ax+s=b$, $x\geq0$, $s$ free**. There is always the feasible solution $x=0$ and $s=b$.

**If you require $s\geq0$, then you can write the slack variables $s$ as $s^+-s^-$ for $s^+,s^-\geq0$.

David M.
  • 2,623
  • If the auxiliary problem can't attain the value zero, is it possible that the original problem is not infeasible, but unbounded? – ensbana Feb 02 '19 at 22:44
  • I'm working with this auxiliary program: maximize $z = -x_6 - x_7$, subject to: $-2x_1 + 2x_2 + 2x_3 - x_4 + x_6 = 2$, $2x_1 - 2x_2 + x_3 + x_5 + x_7 =2$,
    $x_1,x_2,x_3,x_4,x_5,x_6,x_7 \geq 0$. Let $x_6, x_7$ be the basic variables, we obtain $z = -4 + 3x_3 - x_4 + x_5$, so there's no possibility of further improving $z$. I also used an online solver to solve the original LP, and it says the program is unbounded.     – ensbana Feb 02 '19 at 22:47
  • No, if the original problem is unbounded, the auxiliary problem will be feasible. I’m not really sure what your second comment is describing. Add it to the question with some details (e.g. what’s the original LP, etc.) – David M. Feb 03 '19 at 01:36