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} \]
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} \]
Show Hint
Correct Answer: 27
Solution and Explanation
We are tasked with finding the optimal assignment that minimizes the total cost. This is a typical assignment problem that can be solved using the Hungarian Method or by directly inspecting the minimum cost for each job assignment.
We will follow the steps below to determine the minimum cost:
- Step 1: Consider the costs associated with each job:
- For \( J_1 \), the minimum cost is \( 9 \) from \( C_2 \).
- For \( J_2 \), the minimum cost is \( 10 \) from \( C_3 \).
- For \( J_3 \), the minimum cost is \( 8 \) from \( C_1 \).
Step 2: Add up the minimum costs for the optimal assignment:
\[ 9 + 10 + 8 = 27 \]
Final Answer:
The cost of the optimal assignment is \( \boxed{27} \).
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?
- 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 __________.
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}}\).
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?
- 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 __________.
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}}\).
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?