Multiple optimal solutions for a linear programming problem

Question

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?

Answer 1

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.