[Math] When is a linear program feasible but not optimal

convex optimizationlinear programmingoptimization

Let be the following program
$$\begin{array}{rrcr@{\qquad}l}
\text{max:} &4x_1 &+& 5x_2 &\\
\text{subject to:} &2x_1 &+& x_2 &\le 8\\
&x_1 &+& 2x_2 &\le 7\\
& & &x_2&\le 3\\
\forall i,x_i\ge 0
\end{array}
$$

with $x_1\prime=1$ and $x_2\prime = 3$ is it feasible? Optimal?

I first tried to see if it satisfied complementary slackness theorem
$$
\begin{array}
& 2*1 &+& 3 &= 5 &\le 8&(\Rightarrow y_1 = 0)\\
1 &+& 2*3 &= 7\\
& & 3 &= 3
\end{array}
$$
Therefore I think it is feasible.

Yet when providing its dual. I find out that $y_2 = 4$ and $y_3 = -3$… As far as the last one is $<0$ does it mean it is feasible and not optimal?

Best Answer

Is $x=(1,3)$ feasible: yes, the constraints are satisfied.

Is $x=(1,3)$ optimal? Consider complementary slackness:

$\begin{align} y_1(2 x_1 + x_2 - 8) = 0 \\ y_2(x_1 + 2 x_2 - 7) = 0 \\ y_3(x_2 - 3) = 0 \\ x_1(2y_1 + y_2-4) = 0 \\ x_2(y_1 + 2y_2 + y_3-5) = 0 \end{align}$

The first two equalities yield $y_1=y_2=0$, but this violates the fourth equality. Since no $y \geq 0$ can be found that satisfies complementary slackness, $x$ is not optimal.