0

I have no idea how to solve the following problem without using Simplex. Below is the LP

$\min -47x_1 + 13x_2 + 22x_3 $ subject to

$-4x_1 + x_2 - 17x_3 \geq 2$

$-x_1 + x_2 + 39x_3 \geq 1$

$x_1, x_2, x_3 >0$

I have the dual written down as:

$\max 2u_1 + u_2$ such that

$-4u_1 - u_2 \leq -47$

$u_1 + u_2 \leq 13$

$-17u_1 + 39u_2 \leq 22$

$u_1, u_2, u_3 \geq 0$

And I'm not really sure where to go from here. Help would be appreciated!

Nikitau
  • 1,353
  • Minor note: your dual LP should only have two variables $u_1$ and $u_2$, since the primal LP only has two constraints. – Misha Lavrov Mar 31 '17 at 04:04

1 Answers1

0

I'm not sure what other techniques that aren't the simplex method you're fine with using, but in this case, since the dual LP only has two variables, you could solve it by graphing.

Once you have a dual solution, you can use complementary slackness to get a primal solution:

  • Whenever a dual variable is nonzero, the corresponding primal constraint is tight (satisfied with equality), giving you an equation that $x_1, x_2, x_3$ must satisfy.
  • whenever a dual constraint is not tight, the corresponding primal variable must be $0$, letting you get rid of a variable.

Once you have a primal solution and a dual solution, it should be straightforward to confirm you've done everything right by checking that the objective values are the same.

Misha Lavrov
  • 142,276
  • Thanks. I tested this with Phase I even though the question explicitly states not to. What would a graph look like for an infeasible LP? – Nikitau Mar 31 '17 at 05:54
  • At some point as you're drawing the constraints, you'll see that the next constraint tells you that all solutions are on one side of a line, but the feasible region formed by the previous constraints is entirely on the other side of that line. For example, if you have $x \ge 1$ and $y \ge 1$, these form an open cone starting from $(1,1)$. If you add the constraint $x+y\le 1$, that constraint describes a region entirely disjoint from the cone. – Misha Lavrov Mar 31 '17 at 05:58