Dual of a linear program is infeasible

4.1k Views Asked by At

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!

1

There are 1 best solutions below

0
On BEST ANSWER

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.