3
$\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$
4
  • $\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, 2018 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, 2018 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$
    – user436658
    Jan 2, 2018 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, 2018 at 14:23

1 Answer 1

Reset to default
7
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .