PARIXO GATE · ME Open the app

GATE 2014 ME Set 4 · Question 28

1 markMultiple choiceIndustrial EngineeringTransportation, Assignment and Network Flow

The total number of decision variables in the objective function of an assignment problem of size ( jobs and machines) is

  1. A

  2. B

  3. C

  4. D

GATE 2014 · Mechanical Engineering · Set 4 · IIT Kharagpur · printed as Q.18 in the ME section

Answer
(A)

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

Question from the official GATE 2014 ME paper (Set 4), IIT Kharagpur. Solutions by PARIXO AI. All 65 questions of this paper.