Question

For the linear programming problem: \[ {Maximize} \quad Z = 2x_1 + 4x_2 + 4x_3 - 3x_4 \] subject to \[ \alpha x_1 + x_2 + x_3 = 4, \quad x_1 + \beta x_2 + x_4 = 8, \quad x_1, x_2, x_3, x_4 \geq 0, \] consider the following two statements: 
S1: If \( \alpha = 2 \) and \( \beta = 1 \), then \( (x_1, x_2)^T \) forms an optimal basis. 
S2: If \( \alpha = 1 \) and \( \beta = 4 \), then \( (x_3, x_2)^T \) forms an optimal basis. Then, which one of the following is correct?

• A. S1 is TRUE and S2 is FALSE
• B. S2 is TRUE and S1 is FALSE
• C. both S1 and S2 are TRUE
• D. neither S1 nor S2 is TRUE

Hint:

When verifying optimal bases in linear programming, check the system of equations using Gaussian elimination or matrix methods to determine if the solution satisfies the conditions of the problem.

Answer 1

The Correct Option is B

We need to check the two statements \( S1 \) and \( S2 \) and verify if the given solutions are optimal bases.

Step 1: Analyzing S1:

For \( \alpha = 2 \) and \( \beta = 1 \), the system of equations becomes:
\[ 2x_1 + x_2 + x_3 = 4 \quad \text{and} \quad x_1 + x_2 + x_4 = 8. \]

We can set up the corresponding augmented matrix for the system:
\[ \begin{pmatrix} 2 & 1 & 1 & 0 & | & 4 \\ 1 & 1 & 0 & 1 & | & 8 \end{pmatrix} \]
Performing Gaussian elimination, we find that \( (x_1, x_2)^T \) does not form an optimal basis. Therefore, S1 is FALSE.

Step 2: Analyzing S2:

For \( \alpha = 1 \) and \( \beta = 4 \), the system of equations becomes:
\[ x_1 + x_2 + x_3 = 4 \quad \text{and} \quad x_1 + 4x_2 + x_4 = 8. \]

Setting up the augmented matrix for this system:
\[ \begin{pmatrix} 1 & 1 & 1 & 0 & | & 4 \\ 1 & 4 & 0 & 1 & | & 8 \end{pmatrix} \]
Performing Gaussian elimination here shows that \( (x_3, x_2)^T \) indeed forms an optimal basis. Therefore, S2 is TRUE.

Thus, the correct answer is:

\[ \boxed{\text{S2 is TRUE and S1 is FALSE.}} \]