0
$\begingroup$

The primal problem is as followed: Minimize $z=4x-5y$ Subject to

$y\le10-x$,

$y\le2+3x$,

$x,y\ge0$

Write out its dual and solve it geometrically.

...I have found its dual and graphed out the inequalities but I'm not sure if it is right, mainly because the primal problem is bounded and my graphed dual problem is not.

$\endgroup$
  • $\begingroup$ What did you find as the dual? $\endgroup$ – Peter Woolfitt Apr 22 '15 at 3:50
  • $\begingroup$ maximize -10u1-2u2 $\endgroup$ – BlueJello27 Apr 23 '15 at 2:17
  • $\begingroup$ subject to -u1+3u2<=4, -u1-u2<=-5,u>=0 $\endgroup$ – BlueJello27 Apr 23 '15 at 2:18
0
$\begingroup$

I agree with the dual problem you give. Now let's verify that the dual problem has a solution equal to the solution of primal problem.

For the primal problem, we get the following feasible region:

primal

We can see that the vertices are at $(0,0)$, $(0,2)$, $(2,8)$, and $(10,0)$ (note that we could make this calculation by finding the intersection of the lines if we wanted to). We know the minimum must occur at one of these vertices, so we simply calculate the value of $z$ at each point. Recalling $x=4x-5y$, we get

Point $(0,0)$: $z=0$

Point $(0,2)$: $z=-10$

Point $(2,8)$: $z=-32$

Point $(10,0)$: $z=40$

Hence the minimum is $z=-32$ achieved at the point $(2,8)$.

Now onto the dual problem.

For the dual problem, we get the following feasible region:

dual

Now I the worry is that the feasible region is unbounded. This is not a problem! The goal is to maximize $-10u_1-2u_2$ which is the same as minimizing $10u_1+2u_2$. Since the second expression is easier, I will work with that. Note that if we have two points $(x_1,y_1)$ and $(x_2,y_2)$ n the feasible region, we have $10x_1+2y_1<10x_2+2y_2$ if either $x_1<x_2$ or $y_1<y_2$. Hence given any point, we can make our function $10u_1+10u_2$ smaller by moving to the left or moving down. Hence we know that the point which minimizes $10u_1+10u_2$ must lie on the following line segment:

victory line

Since it lies on the line segment, we know the extreme value of the objective function must occur at one of the endpoints of the line segment - that is at either $(5,0)$ or $\left(\frac{11}{4},\frac{9}{4}\right)$. Finally, we check for the maximum using $z=-10u_1-2u_2$

Point $(5,0)$: $z=-50$

Point $\left(\frac{11}{4},\frac{9}{4}\right)$: $z=-\frac{110}{4}-\frac{18}{4}=-32$

Great! We've now confirmed that our dual program gets the answer it should.

$\endgroup$

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.