Verify that the optimal basis consists of the particular slack variable without using simplex method.

Question

In a linear programming problem, how to verify that the optimal basis consists of the slack variable of a particular constraint without using the simplex method? Consider the following problem: $$ {\rm Maximize} 10x_1+15x_2+5x_3$$ subject to $$2x_1+x_2≤6000$$ $$3x_1+ 3x_2+x_3≤9000$$ $$x_1+ 2x_2+ 2x_3≤4000$$ $$x_1, x_2, x_3≥0$$

Without using the simplex method, verify that the optimal basis consists of the slack variable of the first constraint x1 and x2.

Answer 1

Since you only need to verify a solution rather than come up with one, the simplex method isn't necessary. We can prove the basic solution is optimal directly. First, since $x_3$ and the slacks in last two constraints are non-basic and have value $0$, the values of the decision variables satisfy.

$$ 3x_1+ 3x_2 = 9000 \\ x_1 + 2x_2 = 4000 \\ x_3 = 0$$

and are $(x_1, x_2, x_3) = (2000, 1000, 0)$. This gives us a left hand side of the first constraint of $5000$ so the solution is feasible. The objective value is given by $10 \cdot 2000 + 15 \cdot 1000 + 5 \cdot 0 = 35000$. Now we are left to show that there are no other non-negative values of $x_1, x_2, x_3$ that satisfy the constraints and have an objective value of greater than $35000$. The last two constraints imply an inequality with a right hand side of $35000$ and a left-hand side that will always be at least as large as $10𝑥_1+ 15𝑥_2+5𝑥_3$. Adding $\frac{5}{3}$ of the second inequality and $5$ of the third, we get the inequality

$$ \frac{5}{3} (3x_1+ 3x_2+x_3) + 5 (x_1+ 2x_2+ 2x_3) \le \frac{5}{3} 9000 + 5 \cdot 4000 \\ 10 x_1 + 15 x_2 + 11 \frac{2}{3} x_3 \le 35000$$

Since $x_3$ must be non-negative we know $$10 x_1 + 15 x_2 + 10 x_3 \le 10 x_1 + 15 x_2 + 11 \frac{2}{3} x_3 \le 35000. $$ The basic solution is feasible and produces an objective that is at least as good as any other feasible solution, so it is an optimal basis.

Now, about the weights. The weights we used to get the upper-bound on the objective are the dual prices.

Adding the slack variables, the constraints become $$2x_1+x_2 + s_1 = 6000 \\ 3x_1+ 3x_2+x_3 + s_2 = 9000 \\ x_1+ 2x_2+ 2x_3 + s_3 =4000$$

If $x_1, x_2$ and $s_1$ are the basic variables, the basis matrix and its inverse are $$B = \left[\begin{matrix}2 & 1 & 1\\3 & 3 & 0\\1 & 2 & 0\end{matrix}\right]$$

and $$B^{-1} = \left[\begin{matrix}0 & \frac{2}{3} & -1\\0 & - \frac{1}{3} & 1\\1 & -1 & 1\end{matrix}\right].$$

The primal solution is given by $$ \begin{bmatrix} x_1 \\ x_2 \\ s_1 \end{bmatrix} = B^{-1} \begin{bmatrix} 6000 \\ 9000 \\ 4000 \end{bmatrix}$$ and the dual is given by $$ [\begin{matrix} 10 & 15 & 0 \end{matrix}] \cdot B^{-1} = \left[\begin{matrix}0 & \frac{5}{3} & 5\end{matrix}\right].$$

Which are the weights on the constraints used to produce the upper bound.