Question

Consider the linear programming problem (LPP):

\[ \text{Maximize } Z = 3x_1 + 5x_2 \]

Subject to:
\[ x_1 + x_3 = 4, \]
\[ 2x_2 + x_4 = 12, \]
\[ 3x_1 + 2x_2 + x_5 = 18, \]
\[ x_1, x_2, x_3, x_4, x_5 \geq 0. \]

Given that \( x_B = (x_3, x_2, x_1)^T \) forms the optimal basis of the LPP with basis matrix \( B \) and respective \( B^{-1} \):

\[ B^{-1} = \begin{bmatrix} \alpha & \beta & -\beta \\ 0 & \gamma & 0 \\ 0 & -\beta & \beta \end{bmatrix} \]

If \( (p, q, r) \) is the optimal solution of the dual of the LPP, then which one of the following is/are TRUE?

• A. \( \alpha + 3\beta + 2\gamma = 3 \)
• B. \( \alpha - 3\beta + 4\gamma = 1 \)
• C. \( p + q + r = \frac{5}{2} \)
• D. \( p^2 + q^2 + r^2 = \frac{17}{4} \)

Hint:

For duality in linear programming, the optimal solutions of the primal and dual problems are related. Use the structure of the basis matrix and its inverse to derive the relationships between the primal and dual variables.

Answer 1

The Correct Option is A, C

Step 1: Understanding the Linear Programming Problem
The given LPP has the objective function \( Z = 3x_1 + 5x_2 \), and we are given the constraints:
\[ x_1 + x_3 = 4, \]
\[ 2x_2 + x_4 = 12, \]
\[ 3x_1 + 2x_2 + x_5 = 18. \]
We are also given the basis matrix \( B \) and its inverse \( B^{-1} \).

Step 2: Relating the Dual of the LPP
The dual of the given linear program has the variables corresponding to the constraints, and the solution of the dual gives the values of the dual variables \( p \), \( q \), and \( r \). These values are related to the primal problem's optimal solution.

Step 3: Using the KKT Conditions
The complementary slackness conditions and the structure of the dual variables imply relationships between the coefficients \( \alpha \), \( \beta \), \( \gamma \), \( p \), \( q \), and \( r \). The specific conditions derived from the structure of \( B \) and \( B^{-1} \) give the equation \( \alpha + 3\beta + 2\gamma = 3 \), which is the correct relationship. Also, based on the structure of the dual, we have \( p + q + r = \frac{5}{2} \).

Step 4: Conclusion
Therefore, the correct answers are \( \boxed{A} \) and \( \boxed{C} \).

Final Answer
\[ \boxed{A} \quad \alpha + 3\beta + 2\gamma = 3 \]
\[ \boxed{C} \quad p + q + r = \frac{5}{2} \]