Assignment problem: Difference between revisions

Revision as of 21:30, 14 March 2022

Revision as of 21:32, 14 March 2022

Line 13:

Now, suppose that there are ''four'' taxis available, but still only three customers. This is an ''unbalanced assignment'' problem. One way to solve it is to invent a fourth dummy task, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. This reduces the problem to a balanced assignment problem, which can then be solved in the usual way and still give the best solution to the problem.

An alternate example: Suppose the military wants to assign its soldiers (the agents) to particular countries (tasks). Each soldier has a ranked list of countries they want to go to (weightswhich oncorresponds to the edgescost for each country). The problem is to assign soldiers to countries such that as many soldiers as possible get close to their top pick.

Similar adjustments can be done in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.