Prove that Dual linear program does not have finite optimal solution

linear programmingmaxima-minimaoperations researchoptimizationproof-verification

Consider the following

$\displaystyle \max z=x+2y\\s.t.-x+y\le-2\\4x+y\le4\\ x,y\ge0$

Find the dual program and prove graphically that D has no finite optimal solution.

Solution

The dual is given by

$\displaystyle \max -2x+4y\\s.t.-x+4y\ge1\\x+y\ge2\\ x,y\ge0$

In the plot we see that there is no bounded feasible region. And as we have to maximize the objective function $-2x+4y$ then there won't be a fesible solution, because $z$ goes to $\infty$.

enter image description here

Is my solution correct? If it is, is it well justified?

Best Answer

The graph looks ok, but the real trouble is the dual maximizing. Your teacher is right,

it must be the change from min to max and vice versa in dual problems.

It is though the same reasoning for the minimum in the dual problem as it is possible to move the level set for $z=-2x+4y$ to $-\infty$ within the feasible region.

Related Question