2
$\begingroup$

I'm attempting the following problem:

$\max\ \ 6x_1 + 5x_2 + 4x_3 + 5x_4 + 6x_5\ \ $,$\ \ $subject to

$x_1 + x_2 + x_3 + x_4 + x_5 \leq 3,$

$5x_1 + 4x_2 + 3x_3 + 2x_4 + x_5 \leq 14,$

$x_i \geq 0\ \ $ for all $i$.

I'm supposed to formulate the dual problem, solve that graphically and then use the dual optimal solution to get the primal one. Here's my attempt: the dual problem is:

$\min\ \ 3y_1 + 14y_2\ \ $,$\ \ $subject to

$y_1 + 5y_2 \geq 6,$

$y_1 + 4y_2 \geq 5,$

$y_1 + 3y_2 \geq 4,$

$y_1 + 2y_2 \geq 5,$

$y_1 + y_2 \geq 6,$

$y_1, y_2 \geq 0$.

By inspection of the graph, the solution is $(6,0)$. Substituting this in all dual constraints, only the 1st and 5th dual constraints are tight, so only $x_1, x_5 \geq 0$ and the rest of the primal variables are $0$. Also, since $y_1^* > 0$, the first primal constraint is tight, so we're left with:

$\max\ \ 6x_1 + 6x_5\ \ $,$\ \ $subject to

$x_1 + x_5 = 3,$

$5x_1 + x_5 \leq 14,$

$x_1, x_2 \geq 0$.

I'm confused because the problem states : "determine the optimal solution to the primal problem" as if there's a unique optimal solution. Can't there be several solutions though? It's not necessary that the 2nd primal constraint is also tight. I also tried out this online LP calculator and it gives the same solution as if both primal constraints are tight. Am I missing something?

$\endgroup$
  • $\begingroup$ Yes, there certainly can be more than one optimal solution to a LP. Consider $$\max\left\{ x_1+x_2 : 0\leqslant x_1\leqslant 1,\ 0\leqslant x_2\leqslant 1,\ x_1+x_2\leqslant 1 \right\}. $$ Then $\lambda x_1+(1-\lambda)x_2$ is an optimal solution for any $0\leqslant\lambda\leqslant 1$. $\endgroup$ – Math1000 Apr 2 '18 at 14:41
0
$\begingroup$

Based on strong duality you know that the primal optimal solution has value 18 (since the dual optimal objective is $6\cdot 3 + 0\cdot 14 = 18$). Any solution to $x_1 + x_5=3$, $5x_1 + x_5 \leq 14$, $x_1 \geq$, $x_2 \geq 0$ is optimal since it also gives an optimal value of 18.

The online solvers gives a corner point solution since it is based on the simplex method. An interior point solver without crossover would give a different optimal solution.

$\endgroup$
  • $\begingroup$ Ah yes you're right! I'll edit that part. $\endgroup$ – Shirish Kulhari Apr 2 '18 at 16:37

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.