# Multiple optimal solutions for a linear programming problem

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?

• 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$. – Math1000 Apr 2 '18 at 14:41

## 1 Answer

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.

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