2
$\begingroup$

I have been given the problem of solving the dual of the linear program

$$\max_{x\in\mathbb{R}^3}\{2x_1+6x_2+x_3\}$$

subject to

$$x_1-2x_2-x_3 \le -3 \\ 2x_1+3x_2-x_3 \ge -3\\x_1 \ge 0, x_2\ge 0, x_3\ge 0$$

I went ahead and reformulated the problem to the dual one and ended up with

$$\max\{3y_1-3y_2\}$$

where

$$-y_1+2y_2 \le -2\\ 2y_1+3y_2 \le -6\\ y_1 - y_2 \le -1\\ y_1\ge 0, y_2 \ge 0$$

The constraints of the dual problem however, leave me with an empty set. This confuses me, since the problem was formulated in a way that you expect the dual to have a solution. That's why I wanted to ask, whether or not I did make any mistakes in formulating the dual problem. Any help would be greatly appreciated!

$\endgroup$
  • $\begingroup$ Something is hinky with your initial problem: If $x_1=x_2=x_3$, then the constraints collapse to $-2x_1\leq -3,\, 4x_1\geq -3,\,x_1\geq 0\implies x_1\geq 3/2,x_1\geq -3/4,x_1\geq 0$. But this is satisfied so long as $x_1\geq 3/2$, so we can increase $2x_1+6x_2+x_3$ without bound by moving along the line $x_1=x_2=x_3$. Is one of your inequalities perhaps stated backwards? (My argument fails if the first is reversed, so I'd suspect that it's the problem.) $\endgroup$ – Semiclassical Jan 2 '18 at 14:14
  • 2
    $\begingroup$ The principle here is that if the original problem is unbounded, then the dual problem is infeasible. $\endgroup$ – hardmath Jan 2 '18 at 14:20
  • $\begingroup$ If the dual problem doesn't have a feasible solution, the primal problem has no finite maximum, the objective function is unbounded. $\endgroup$ – Professor Vector Jan 2 '18 at 14:22
  • $\begingroup$ @semiclassical I suppose either there is a mistake on the authors end or it is supposed to have no solution. But thank you for reassuring that there is something off here! $\endgroup$ – Jack4t3 Jan 2 '18 at 14:23
4
$\begingroup$

You can't expect your dual problem to have solution, since the primal(original) problem has an unbounded feasible region: you can take $x_1=x_3 = 0$ and $x_2>2$, so your maximum is $+ \infty$. This means your dual problem must be unfeasible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.