Assignment problem: Difference between revisions

Revision as of 05:58, 12 November 2003

Revision as of 19:05, 14 November 2003

Line 1:

AnThe '''assignmentAssignment problem''' is anone importantof problemfundamental ''conbinatorial optimization'' problems in the branch of [[optimization]] or [[operations research]] in [[mathematics]]. The problem is as follows:

In its most general form, the problem is as follows:

:There are a number of ''agents'' and an equal number of ''tasks'', we want to search a way to assign each agent exactly one task such that the total ''cost'' of the assignment is minimized.

The:There costare ofa annumber assignmentof is determined''agents'' fromand a number of ''cost functiontasks'',. whichAny givesagent thecan costbe ofassigned assigningto aperform particularany agenttask, toincurring asome particular''cost'' task.that Themay overallvary costdepending ofon the assignment. isIt thenis equalrequired to theperform sumall oftasks theby costsassigning forexactly eachone agent (orto theeach sumtask ofin thesuch costsa forway eachthat task,the which''total iscost'' of the sameassignment is thing)minimized.

If the numers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called ''Linear assignment problem''. Commonly, when spoken of ''Assignment problem'' without any additional qualification, then the ''Linear assignment problem'' is meant.

The assignment problem is a special case of another optimization problem known as the [[transportation problem]], which is a special case the [[maximal flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], each problem has more efficient algorithms designed to take advantage of its special structure. It is known that an algorithm exists to solve the assignment problem within time bounded by a polynomial expression of the number of agents.

Another kinds are the ''Quadratic assignment problem'', ''Minmax assignment problem''.

The requirement about equal number of agents and tasks could be relaxed, as shown in the example below.

The assignment problem is a special case of another optimization problem known as the [[transportation problem]], which is a special case the [[maximal flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], each problem has more efficient algorithms designed to take advantage of its special structure. ItAlgorithm isare known that an algorithm exists to solve the linear assignment problem within time bounded by a polynomial expression of the number of agents.

==An example==

ForThe examplerestrictions on agents, supposetasks and cost in the (linear) assignemnt problem could be relaxed, as shown in the example below.

==Example==

Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.

However, the assignment problem can be made rather more flexible than it first appears. In the above example, suppose that there are four taxis available, but still only three customers. Then a fourth task can be invented, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. The assignment problem can then be solved in the usual way and still give the best solution to the problem.

Line 19 ⟶ 23:

==Formal mathematical definition==

The formal definition of anthe '''assignmentAssignment problem''' (or '''linearLinear assignment problem''') is

:Given two sets, ''A'' and ''T'', of equal size, together with a cost function ''C'':''A''×''T''→'''[[real number|R]]'''. Find the [[bijection]] ''f'':''A''→''T'' such that: