List of top Linear Programming Questions asked in GATE MA

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 __________.

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} \]

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?

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?