Question

Consider the Linear Programming Problem P: \[ \text{Maximize } c_1x_1 + c_2x_2 \] subject to: \[ a_{11}x_1 + a_{12}x_2 \leq b_1, \] \[ a_{21}x_1 + a_{22}x_2 \leq b_2, \] \[ a_{31}x_1 + a_{32}x_2 \leq b_3, \] \[ x_1 \geq 0, \, x_2 \geq 0, \] where  \(a_{ij}, b_i, c_j\)  are real numbers (i = 1, 2, 3; j = 1, 2). Let \[ \begin{bmatrix} p \\ q \end{bmatrix} \] be a feasible solution of P such that \( p c_1 + q c_2 = 6 \), and let all feasible solutions \[ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \] of P satisfy \( -5 \leq c_1x_1 + c_2x_2 \leq 12 \). Then, which one of the following statements is NOT true?

• A. P has an optimal solution
• B. The feasible region of P is a bounded set
• C. If \[ \begin{bmatrix} y_1
  y_2
  y_3 \end{bmatrix} \] is a feasible solution of the dual of P, then \( b_1y_1 + b_2y_2 + b_3y_3 \geq 6 \)
• D. The dual of P has at least one feasible solution

Hint:

In linear programming, always check the feasibility and boundedness of the problem to determine the existence of an optimal solution.

Answer 1

The Correct Option is B

- (A) P has an optimal solution: A linear programming problem has an optimal solution if the feasible region is non-empty and bounded. Since \( c_1x_1 + c_2x_2 \) is bounded and satisfies the given constraints, this statement is true.
- (B) The feasible region of P is a bounded set: Since the constraints do not guarantee that the feasible region is bounded (the constraints are only inequalities), it is possible for the feasible region to be unbounded. Hence, this statement is false.
- (C) If \( \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} \) is a feasible solution of the dual of P, then \( b_1y_1 + b_2y_2 + b_3y_3 \geq 6 \): This is the condition for a feasible solution in the dual problem, so it is true.
- (D) The dual of P has at least one feasible solution: Every linear programming problem has a dual, and the dual problem will always have at least one feasible solution. Therefore, this statement is true. Thus, the correct answer is (B).
Final Answer: (B) The feasible region of P is a bounded set.