0
$\begingroup$

Given the Linear Programming Problem:

Minimize $2x_1+3x_2+5x_3+6x_4$ subject to

$x_1 + 2x_2 + 3x_3 + x_4 \geq 2$

$2x_1-x_2+x_3-3x_4 \geq 3$

I can get the dual from this which is :

Maximize $2y_1+3y_2$ subject to

$y_1+2y_2 \leq 2$

$2y_1-y_2 \leq 3$

$3y_1+y_2 \leq 5$

$y_1-3y_2 \leq 6 $

I can solve this graphically and obtain the optimal solution for the dual which is $y_1 = \frac{8}{5}$ and $y_2=\frac{1}{5}$

From this I am told to "Utilize information about the dual linear program and the theorems of duality to solve the primal problem"

I know since the dual solutions are positive the corresponding constraints in the primal are tight.

This means I am left with system of equations of which there are more variables than equations. So this must not work.

Any ideas how to approach this? Or possibly a text which gives example problems and answers would suffice. Just trying to learn.

$\endgroup$
1
$\begingroup$

We can deduce valid equations for $x_1, x_2, x_3, x_4$ in two different ways:

  1. As you've said, whenever a dual variable is positive, the corresponding primal constraint is tight, giving us: \begin{align} x_1 + 2x_2 + 3x_3 + x_4 &= 2 & \text{since } y_1 > 0 \\ 2x_1 − x_2 + x_3 − 3x_4 &= 3 & \text{since } y_2 > 0 \end{align}
  2. Conversely, whenever a dual constraint is not tight, the corresponding primal variable is not positive, giving us: \begin{align} x_4 &= 0 & \text{since }y_1 - 3y_2 &< 6 \end{align}

This is still fewer equations than variables, which is a sign of degeneracy in the dual solution: with two dual variables, three constraints are tight, meaning three lines meet at a single point. This usually doesn't happen.

If it does happen, that means we need to do extra work. In this case, we could solve the three equations with $x_1$ as a free variable and get \begin{align} x_1 &= x_1 \\ x_2 &= x_1 - \tfrac75 \\ x_3 &= -x_1 + \tfrac85 \\ x_4 &= 0 \end{align} All solutions of this form are optimal, but not all are feasible. In this case, we can just look at this solution and see that any choice of $x_1$ with $\frac75 \le x_1 \le \frac85$ will give a feasible (and optimal) solution. In general (for bigger systems), we'd probably need to do one or more steps of the simplex method to get a feasible solution from something like this.

(You could also try setting some more primal variables to $0$ at random. As you can see from this example, setting $x_1=0$ would not work, but $x_2=0$ or $x_3=0$ would. This is pure guesswork, but we do know that if there's degeneracy, then some primal variable can be set to $0$ even though its corresponding dual constraint is tight.)

$\endgroup$
  • $\begingroup$ Wow. Thanks a lot for that detailed answer. I'm just a bit confused on part 2 (possibly the definition of tight). How does $y_1-3y_2<6$ imply $x_4=0$? Would you not get $x_2=0$ from the same logic? $\endgroup$ – Gregory Peck Mar 26 '17 at 23:55
  • $\begingroup$ Complementary slackness tells us that for each variable-constraint pair, either the constraint is tight or the variable is $0$. We don't get $x_2=0$, because the second dual constraint is tight: $2y_1 - y_2 = \frac{16}{5}-\frac{1}{5} = 3$. Tight just means "satisfied with equality". $\endgroup$ – Misha Lavrov Mar 27 '17 at 0:17
  • $\begingroup$ Ohhh.. I see what you mean. Thanks so much, this answer fills an entire void in my notes. $\endgroup$ – Gregory Peck Mar 27 '17 at 0:23

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.