Turning a linear program into an auxiliary problem

Question

I have maximise $$10x-2y+5z$$ s.t $$2x+y-z \le 3$$ $$-8x-2y+5z \le 2 $$ $$-x+2y-3z \ge 7$$

This becomes maximise $$10x-2y+5z$$ s.t $$2x+y-z +s_1= 3$$ $$-8x-2y+5z +s_2=3 2 $$ $$-x+2y-3z -s_1= 7$$

Now only the third constraint gives me an infeasible solution

So auxiliary problem is

Minimize $$-x_0$$ s.t $$2x+y-z = 3$$ $$-8x-2y+5z =3 2 $$ $$-x+2y-3z -x_0= 7$$

if I were to add an $x_0$ in the second and third constraint the most that it would do is make the algebra tedious, but theoretically it should not change the answer as I am trying to achieve $x_0$ =0 anyway, is that correct?

HINT: By simple inspection the solution is one of the "simplex" points.... — Brethlosze, Jun 19 '17 at 01:58
is my last statement correct, that placing $x_0$ in a constraint will at most do nothing? — stackdsewew, Jun 19 '17 at 02:19
Will find a feasible solution, if "auxiliary" is the qualification for the reduced problem focused on that stage... — Brethlosze, Jun 19 '17 at 02:20

score 1 · Answer 1 · answered Jun 19 '17 at 06:16

I don't know why you are making this look hard.

If you have an LP in ineqality form

$Ax \leq b$, where A is m*n matrix

you add new variable for each inequality so that you have m new variables.

In your example, first mulitply third row by -1 so all inequalities are of the same type ( $\leq$ usually).

Then add m=3 new variables $s_1,s_2,s_3$:

$$2x+y-z +s_1= 3$$ $$-8x-2y+5z +s_2=3 2 $$ $$x-2y+3z +s_3= -7$$

And you can start simplex method right away, no neex for auxilliary LP.

Turning a linear program into an auxiliary problem

1 Answers1