Complementary slackness and optimal solution for primal

607 Views Asked by At

We have primal, minimize $z = 3u_1 + 0.5u_2$

subject to $$ u_1 - 2u_2 \leq 4 \\ u_1 + u_2 \leq 2 \\ u_1, u_2 \geq 0 $$ I found the dual $$ \text{max: } z' = 4v_1 + v_2 \\ \text{subject to: } \\ v_1 + v_2 \leq 3 \\ -2v_1 + v_2 \leq 0.5 \\ v_1, v_2 \geq 0 $$ And that the solution is $(3, 0)$ for the dual. How do I use complementary slackness to find solutions to the primal.

1

There are 1 best solutions below

0
On

In my opinion your dual is not right. See the table. I have the following dual

$$ \text{max: } z' = 4v_1 + v_2 \\ \text{subject to: } \\ v_1 + v_2 \leq 3 \\ -2v_1 + v_2 \leq 0.5 \\ v_1, v_2 \leq 0 $$ $\texttt{Edit}$: I´ve changed the sign of the inequalities. The optimal solution is $(v_1^*,v_2^*)=(0,0)$. Thus the slack variables for the dual are positive and therefore not zero. That means that the corresponding variables of the primal problem are zero.

Read the table from right to left, since your primal problem is a minimizing problem.

enter image description here

For the complementary slackness theorem see, for instance, this link.