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 Answer 1

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$
3
  • $\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$ Commented Mar 26, 2017 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$ Commented Mar 27, 2017 at 0:17
  • $\begingroup$ Ohhh.. I see what you mean. Thanks so much, this answer fills an entire void in my notes. $\endgroup$ Commented Mar 27, 2017 at 0:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .