Utilizing theorems of duality to solve primal linear programming problem

Question

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.

Answer 1

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.)