Given a feasible solution to an LP, how to determine if it is basic?

Question

How can I tell if the given solution is basic?

Answer 1

(a) The given solution is not basic. Rewrite the LPP into the standard form. Let $$A = \begin{bmatrix} 4 & 8 & 2 & 15 \\ 4 & 15 & 0 & 6 \\ 2 & 3 & 3 & 6 \\ 15 & 8 & 10 & 20 \end{bmatrix},$$ $ c = \begin{bmatrix}200 & 320 & 165 & 392\end{bmatrix}^T$ and $b = \begin{bmatrix}10 & 12 & 5 & 15\end{bmatrix}^T $, $y_s = Ay - b$.

From the given FS $y'$, we have $y_s' = Ay' - b = \begin{bmatrix}67/48 & 0 & 0 & 191/516\end{bmatrix}^T$.

Then we have $\min c^Ty$ subject to $Ay - Iy_s = b$ and $y,y_s \ge 0$. We see that $\begin{bmatrix}y' \\ y_s'\end{bmatrix}$ is a FS to this LPP is standard form. The rank of $\begin{bmatrix}A & -I\end{bmatrix} \le 4$, but $\begin{bmatrix}y' \\ y_s'\end{bmatrix}$ has 5 non-zero entries, so it's a non-basic FS.

(b) First, we write down the dual of the problem: $\max b^T x$ subject to $A^T x \le c$ and $x \ge 0$. Let $x_s = c - A^T x$. The dual in standard form: $\max b^T x$ subject to $A^T x + I x_s = c$ and $x,x_s \ge 0$. To use CSC, we assume that $y'$ is an optimal FS, and apply $x^T y_s + y^T x_s = 0$ to find solution in the dual.

• If everything is consistent, then the optimality of $y'$ is proved numerically.
• Otherwise, if we get a contradiction, then our assumption is wrong.

$y_2,y_3,y_4,y_{s_1},y_{s_4} \ne 0 \implies x_{s_2},x_{s_3},x_{s_4},x_1,x_4 = 0$

\begin{equation} \left\{ \begin{aligned} 15 x_2 + 3 x_3 &= 320 \\ \phantom{15 x_2 +} 3 x_3 &= 165 \\ 6 x_2 + 6 x_3 &= 392 \end{aligned} \right. \end{equation}

• From the second equation, $x_3 = 55$.
• Substitute this to the third equation: $6 x_2 + 6(55) = 392$, so $x_2 = 31/3$.
• Substitute this to the first equation: $15(31/3) + 3(55) = 320$.
• $x_{s_1} = c_1 - 4x_1 - 4x_2 - 2x_3 - 15x_4 = 200 - 0 - 4(31/3) - 2(55) - 0 = 146/3$

Therefore, $(x_1,x_2,x_3,x_4,x_{s_1},x_{s_2},x_{s_3},x_{s_4}) = (0, 31/3, 55, 0,146/3,0,0,0)$ is a FS to the dual that satisfies CSC, we conclude that $y'$ is optimal.