GATE 2014 ME Set 4 · Question 28
The total number of decision variables in the objective function of an assignment problem of size ( jobs and machines) is
- A
- B
- C
- D
GATE 2014 · Mechanical Engineering · Set 4 · IIT Kharagpur · printed as Q.18 in the ME section
Answer
From the official answer key published by IIT Kharagpur.
Worked solution
In an assignment problem with jobs and machines, let the decision variable be defined as:
for each job and each machine .
The objective function to minimize total assignment cost is:
Since each of the jobs can potentially be assigned to any of the machines, there are possible pairings. Hence, the objective function contains exactly decision variables.
Note that while the number of functional constraints is (each job assigned to one machine, each machine assigned one job), the number of decision variables is .
Answer: (A)
Practise Transportation, Assignment and Network Flow
8 GATE questions from this chapter, in short untimed sets, with the formula sheet beside them. Free.
More from Transportation, Assignment and Network Flow
- GATE 2024 ME · Q65In a supplier-retailer supply chain, the demand of each retailer, the capacity of each supplier, and the…
- GATE 2022 ME Set 1 · Q58An assignment problem is solved to minimize the total processing time of four jobs (1, 2, 3 and 4) on four…
- GATE 2019 ME Set 1 · Q64Five jobs (J1, J2, J3, J4 and J5) need to be processed in a factory. Each job can be assigned to any of the…
- GATE 2018 ME Set 2 · Q61The arc lengths of a directed graph of a project are as shown in the figure. The shortest path length from…
- GATE 2017 ME Set 2 · Q48A product made in two factories, P and Q, is transported to two destinations, R and S. The per unit costs of…
- GATE 2014 ME Set 2 · Q28If there are m sources and n destinations in a transportation matrix, the total number of basic variables in…
Question from the official GATE 2014 ME paper (Set 4), IIT Kharagpur. Solutions by PARIXO AI. All 65 questions of this paper.