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

Let's analyze each statement to determine if it is true or false.

1. Statement S1: If \( \alpha = 2 \) and \( \beta = 1 \), then \( (x_1, x_2)^T \) forms an optimal basis.  
   \(Z = 2x_1 + 4x_2 + 4x_3 - 3x_4\)
   Subject to: \(2x_1 + x_2 + x_3 = 4\), and \(x_1 + x_2 + x_4 = 8\) 
   Here, the corresponding matrix for basic feasible solutions using the given choices would be:

\( 2 \)	\( 1 \)	\( 1 \)	\( 0 \)
\( 1 \)	\( 1 \)	\( 0 \)	\( 1 \)

1. Solving the equations gives no feasible solution with optimum values being obtained for \( (x_1, x_2)^T \) as a basis. Thus, Statement S1 is False.
2. Statement S2: If \( \alpha = 1 \) and \( \beta = 4 \), then \( (x_3, x_2)^T \) forms an optimal basis. 
   Given the equations are: \(x_1 + x_2 + x_3 = 4\), and \(x_1 + 4x_2 + x_4 = 8\) 
   Here, the matrix associated with the basis \( (x_3, x_2)^T \) after rearranging is:

\( 1 \)	\( 1 \)	\( 1 \)	\( 0 \)
\( 1 \)	\( 4 \)	\( 0 \)	\( 1 \)

1. Solving these equations gives feasible solutions indicating \((x_3, x_2)^T\) does form a feasible basis, optimizing the given function. Thus, Statement S2 is True.

After analysis, we conclude that the correct answer is: S2 is TRUE and S1 is FALSE.