Let \( \alpha, \beta \in \mathbb{R} \). If \( (4, 0, 2, \beta) \) is an optimal solution of the Linear Programming Problem:
\[ \text{minimize} \quad x_1 + 3x_2 + 2x_3 - \alpha x_4 \]
subject to
\[ 4x_1 + x_2 + x_3 = 18 \]
\[ -3x_1 + 2x_3 + x_4 = 2 \]
\[ x_1, x_2, x_3, x_4 \geq 0, \]
then the maximum value of \( 22(\alpha + \beta) \) is equal to ______.
Show Hint
Find beta from the second constraint directly, then apply complementary slackness (reduced cost equal to zero on the positive variables) to pin down alpha.
Step 1: Reduce to two free variables. The two equality constraints let us solve for $x_2$ and $x_4$ in terms of $x_1$ and $x_3$:
\[ x_2 = 18 - 4x_1 - x_3, \qquad x_4 = 2 + 3x_1 - 2x_3 \]
Substituting these into the objective removes $x_2$ and $x_4$ completely, leaving a linear function of only $x_1$ and $x_3$:
\[ x_1 + 3(18-4x_1-x_3) + 2x_3 - \alpha(2+3x_1-2x_3) = (-11-3\alpha)x_1 + (2\alpha-1)x_3 + (54-2\alpha) \]
Step 2: Locate the given point in this reduced picture. At $x_1=4, x_3=2$ we get $x_2 = 18-16-2=0$ and $x_4=2+12-4=10=\beta$, matching the point we were given. Only the constraint $x_2 \geq 0$ is tight here (it equals 0), while $x_1, x_3, x_4$ are all strictly positive. In the $(x_1,x_3)$ plane this means the point sits on the edge $4x_1+x_3=18$ of the feasible region, not at a corner.
Step 3: An edge point can only be a minimizer if the objective is flat along that edge. Parametrize the edge $4x_1+x_3=18$ by moving along the direction $(1,-4)$ (increasing $x_1$ by 1 decreases $x_3$ by 4, keeping $4x_1+x_3$ fixed). For $(4,2)$ to minimize the objective everywhere on this edge, the directional derivative of the objective along $(1,-4)$ must be zero:
\[ (-11-3\alpha)(1) + (2\alpha-1)(-4) = 0 \]
\[ -11 - 3\alpha - 8\alpha + 4 = 0 \implies -7 - 11\alpha = 0 \implies \alpha = -\frac{7}{11} \]
This matches the value found from the reduced cost condition, now confirmed by a purely geometric argument.
Step 4: Combine with $\beta$. We already found $\beta = 10$ directly from the second constraint. So
\[ \alpha + \beta = -\frac{7}{11} + 10 = \frac{103}{11} \]
