Problems with solving the dual problem graphically

linear programmingoptimization

I have the following problem

minimize $21x_1-15x_2-16x_3$

subject to $2x_1-5x_2+7x_3\ge2$

$3x_1+3x_2-2x_3\ge-5$

$x_1,x_2,x_3\ge0$

So, I transformed the second constraint to make sure that the right hand part is positive.

So that made the problem look like this.

minimize $21x_1-15x_2-16x_3$

subject to $2x_1-5x_2+7x_3\ge2$

$-3x_1-3x_2+2x_3\le5$

$x_1,x_2,x_3\ge0$

Now the dual problem before the conversion of the second constraint looks like this

maximize $2y_1=5y_2$

subject to $2y_1+3y_2\le21$

$-5y_1+3y_2\le-15$

$7y_1-2y_2\le-16$

$y_1,y_2\ge0$

But graphically this makes no sense because they don't intercept when both $y_1,y_2$ are greater than or equal to zero.

And when I do convert the second constraint I'm not sure how to construct the dual problem.

Please help out.

Best Answer

It's not that it "doesn't make sense" graphically, it's just that there are no points that satisfy all of the constraints. In other words, the dual problem is infeasible -- it has no feasible solutions. The reason the dual is infeasible is that the primal problem is unbounded. You can check both of those claims by plugging the LPs into an LP solver.

As for how to formulate the dual when the primal is not in "standard form," the rules are here, or I like this method.