Question

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 ______.

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.

Answer 1

Correct Answer: 206

Step 1: Understanding the Question.
We are told the point \( (x_1,x_2,x_3,x_4) = (4,0,2,\beta) \) is optimal for this linear program. We first pin down \( \beta \) using the constraints, then use the optimality condition to pin down \( \alpha \), and finally compute \( 22(\alpha+\beta) \).

Step 2: Find \( \beta \) from the constraints.
Substitute \( x_1=4, x_2=0, x_3=2 \) into the first constraint as a check:
\[ 4(4) + 0 + 2 = 18 \]
This holds true, confirming the point is feasible in the first constraint (it does not fix \( \beta \)). Use the second constraint to solve for \( \beta = x_4 \):
\[ -3(4) + 2(2) + \beta = 2 \implies -12 + 4 + \beta = 2 \implies \beta = 10 \]

Step 3: Key Formula or Approach.
For a linear program of the form minimize \( c^Tx \) subject to \( Ax=b, x\geq0 \), a feasible point \( x^* \) is optimal exactly when there exist multipliers \( y_1,y_2 \) (one per equality constraint) such that every variable's reduced cost is non negative,
\[ c_j - (\text{column}_j \cdot y) \geq 0 \]
and this reduced cost is exactly zero for every variable that is strictly positive in \( x^* \) (complementary slackness). Here \( x_1=4, x_3=2, x_4=\beta=10 \) are all strictly positive, so their reduced costs must vanish.

Step 4: Set up and solve the reduced cost equations.
The columns of the constraint matrix are \( x_1:(4,-3),\ x_2:(1,0),\ x_3:(1,2),\ x_4:(0,1) \), with costs \( c_1=1,\ c_2=3,\ c_3=2,\ c_4=-\alpha \). Setting the reduced costs of \( x_1 \) and \( x_3 \) to zero:
\[ 1 - (4y_1 - 3y_2) = 0 \implies 4y_1 - 3y_2 = 1 \]
\[ 2 - (y_1 + 2y_2) = 0 \implies y_1 + 2y_2 = 2 \]
From the second equation, \( y_1 = 2 - 2y_2 \). Substitute into the first:
\[ 4(2-2y_2) - 3y_2 = 1 \implies 8 - 8y_2 - 3y_2 = 1 \implies 11y_2 = 7 \implies y_2 = \frac{7}{11} \]
Then \( y_1 = 2 - 2\left(\frac{7}{11}\right) = 2 - \frac{14}{11} = \frac{8}{11} \).

Step 5: Use the \( x_4 \) reduced cost to find \( \alpha \).
\[ -\alpha - y_2 = 0 \implies \alpha = -y_2 = -\frac{7}{11} \]
As a check, the reduced cost of \( x_2 \) (which is zero in \( x^* \), so it only needs to be non negative) is \( 3 - y_1 = 3 - \frac{8}{11} = \frac{25}{11} \geq 0 \), so all the optimality conditions hold together.

Final Answer:
\[ \alpha + \beta = -\frac{7}{11} + 10 = \frac{103}{11} \]
\[ 22(\alpha+\beta) = 22 \times \frac{103}{11} = 2 \times 103 = 206 \]
\[ \boxed{206} \]