List of top Linear Programming Questions on Linear Programming asked in GATE MA

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

Consider the Linear Programming Problem \( P \): \[ \text{Maximize } 2x_1 + 3x_2 \]  subject to \[ 2x_1 + x_2 \leq 6, \] \[ -x_1 + x_2 \leq 1, \] \[ x_1 + x_2 \leq 3, \] \[ x_1 \geq 0 \text{ and } x_2 \geq 0. \] Then the optimal value of the dual of \( P \) is equal to \(\underline{\hspace{1cm}}\).

Consider the Linear Programming Problem \( P \): \[ \text{Minimize } 2x_1 - 5x_2 \]  subject to  \[ 2x_1 + 3x_2 + s_1 = 12, \] \[ -x_1 + x_2 + s_2 = 1, \] \[ -x_1 + 2x_2 + s_3 = 3, \] \[ x_1 \geq 0, x_2 \geq 0, s_1 \geq 0, s_2 \geq 0, \text{ and } s_3 \geq 0. \] If \[ \left[ \begin{array}{c} x_1 \\ s_1 \\ s_2 \\ s_3 \end{array} \right] \]  is a basic feasible solution of \( P \), then \( x_1 + s_1 + s_2 + s_3 = \underline{\hspace{1cm}}. \)

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?

Let \( \tilde{x} = \begin{bmatrix} 11/3 \\ 2/3 \\ 0 \end{bmatrix} \) be an optimal solution of the following Linear Programming Problem P: 
Maximize \( 4x_1 + x_2 - 3x_3 \) 
subject to \[ 2x_1 + 4x_2 + ax_3 \leq 10, \] \[ x_1 - x_2 + bx_3 \leq 3, \] \[ 2x_1 + 3x_2 + 5x_3 \leq 11, \] \[ x_1 \geq 0, x_2 \geq 0, x_3 \geq 0, \text{where} a, b \text{ are real numbers.} \] If \( \tilde{y} = \begin{bmatrix} p \\ q \\ r \end{bmatrix} \) is an optimal solution of the dual of P, then \( p + q + r \)= \(\underline{\hspace{1cm}}\) (round off to 2 decimal places).