1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh, okay. I think I get it now. Thanks. $\endgroup$ – Nick202 May 9 at 22:21

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.