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?
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?
Show Hint
- P has an optimal solution
- The feasible region of P is a bounded set
- 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 \) - The dual of P has at least one feasible solution
The Correct Option is B
Solution and Explanation
- (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.
Top GATE MA Linear Programming Questions
- Let \( y = (\alpha, -1)^T \), where \( \alpha \in \mathbb{R} \), be a feasible solution for the dual problem of the linear programming problem
Maximize: \( 5x_1 + 12x_2 \)
subject to: \[ x_1 + 2x_2 + x_3 \leq 10 \] \[ 2x_1 - x_2 + 3x_3 = 8 \] \[ x_1, x_2, x_3 \geq 0 \] Which of the following statements is TRUE?
- Let \( A \in \mathbb{R}^{m \times n}, c \in \mathbb{R}^n \) and \( b \in \mathbb{R}^m \). Consider the linear programming primal problem
\[ \text{Minimize: } c^T x \] \[ \text{subject to: } A x = b, \quad x \geq 0. \] Let \( x^0 \) and \( y^0 \) be feasible solutions of the primal and its dual, respectively. Which of the following statements are TRUE?
Three companies \( C_1, C_2 \) and \( C_3 \) submit bids for three jobs \( J_1, J_2 \) and \( J_3 \). The costs involved per unit are given in the table below: \[ \begin{array}{c|ccc} & J_1 & J_2 & J_3 \\ \hline C_1 & 10 & 12 & 8 \\ C_2 & 9 & 15 & 10 \\ C_3 & 15 & 10 & 9 \\ \end{array} \]
- The optimal value for the linear programming problem Maximize: \( 6x_1 + 5x_2 \) subject to: \[ 3x_1 + 2x_2 \leq 12 \] \[ -x_1 + x_2 \leq 1 \] \[ x_1, x_2 \geq 0 \] is __________.
A certain product is manufactured by plants \( P_1, P_2 \) and \( P_3 \) whose capacities are 15, 25, and 10 units, respectively. The product is shipped to markets \( M_1, M_2, M_3 \), and \( M_4 \), whose requirements are 10, 10, 10, and 20, respectively. The transportation costs per unit are given in the table below. \[ \begin{array}{|c|c|c|c|c|} \hline \text{Plant} & M_1 & M_2 & M_3 & M_4 \\ \hline P_1 & 1 & 3 & 1 & 15 \\ P_2 & 2 & 4 & 1 & 25 \\ P_3 & 2 & 1 & 2 & 10 \\ \hline \end{array} \] Then the cost corresponding to the starting basic solution by the Northwest-corner method is __________.
Top GATE MA Linear Programming Questions
- Let \( y = (\alpha, -1)^T \), where \( \alpha \in \mathbb{R} \), be a feasible solution for the dual problem of the linear programming problem
Maximize: \( 5x_1 + 12x_2 \)
subject to: \[ x_1 + 2x_2 + x_3 \leq 10 \] \[ 2x_1 - x_2 + 3x_3 = 8 \] \[ x_1, x_2, x_3 \geq 0 \] Which of the following statements is TRUE?
- Let \( A \in \mathbb{R}^{m \times n}, c \in \mathbb{R}^n \) and \( b \in \mathbb{R}^m \). Consider the linear programming primal problem
\[ \text{Minimize: } c^T x \] \[ \text{subject to: } A x = b, \quad x \geq 0. \] Let \( x^0 \) and \( y^0 \) be feasible solutions of the primal and its dual, respectively. Which of the following statements are TRUE?
Three companies \( C_1, C_2 \) and \( C_3 \) submit bids for three jobs \( J_1, J_2 \) and \( J_3 \). The costs involved per unit are given in the table below: \[ \begin{array}{c|ccc} & J_1 & J_2 & J_3 \\ \hline C_1 & 10 & 12 & 8 \\ C_2 & 9 & 15 & 10 \\ C_3 & 15 & 10 & 9 \\ \end{array} \]
- The optimal value for the linear programming problem Maximize: \( 6x_1 + 5x_2 \) subject to: \[ 3x_1 + 2x_2 \leq 12 \] \[ -x_1 + x_2 \leq 1 \] \[ x_1, x_2 \geq 0 \] is __________.
A certain product is manufactured by plants \( P_1, P_2 \) and \( P_3 \) whose capacities are 15, 25, and 10 units, respectively. The product is shipped to markets \( M_1, M_2, M_3 \), and \( M_4 \), whose requirements are 10, 10, 10, and 20, respectively. The transportation costs per unit are given in the table below. \[ \begin{array}{|c|c|c|c|c|} \hline \text{Plant} & M_1 & M_2 & M_3 & M_4 \\ \hline P_1 & 1 & 3 & 1 & 15 \\ P_2 & 2 & 4 & 1 & 25 \\ P_3 & 2 & 1 & 2 & 10 \\ \hline \end{array} \] Then the cost corresponding to the starting basic solution by the Northwest-corner method is __________.
Top GATE MA Questions
- No. of group homomorphism from Z4 to S4
- Number of finite non-isomorphic groups with exactly 3 conjugacy classes_____.
- f(x,y)=\(\left\{\begin{matrix} 1-cos(\frac{x^2}{y^2}) \\ \sqrt{x^2+y^2} \end{matrix}\right.\) ;if y≠0 & n∈R, then
- If ‘=’ denotes increasing order of intensity, then the meaning of the words [drizzle — rain — downpour] is analogous to [ — quarrel — feud]. Which one of the given options is appropriate to fill the blank?
- Statements: 1. All heroes are winners.
2. All winners are lucky people. Inferences: I. All lucky people are heroes.
II. Some lucky people are heroes.
III. Some winners are heroes. Which of the above inferences can be logically deduced from statements 1 and 2?