View source for Assignment problem

<!--
a1107701.png
$#A+1 = 21 n = 0
$#C+1 = 21 : ~/encyclopedia/old_files/data/A110/A.1100770 Assignment problem
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

The problem of optimally assigning  $  m $
individuals to  $  m $
jobs. It can be formulated as a [[Linear programming|linear programming]] problem that is a special case of the [[Transport problem|transport problem]]:

maximize  $  \sum _ {i,j }  c _ {ij }  x _ {ij }  $

subject to

$$ 
\sum _ { j } x _ {ij }  = a _ {i} ,  i = 1 \dots m
$$

(origins or supply),

$$ 
\sum _ { i } x _ {ij }  = b _ {j} ,  j = 1 \dots n
$$

(destinations or demand), where  $  x _ {ij }  \geq  0 $
and  $  \sum a _ {i} = \sum b _ {j} $, 
which is called the balance condition. The assignment problem arises when  $  m = n $
and all  $  a _ {i} $
and  $  b _ {j} $
are  $  1 $.

If all  $  a _ {i} $
and  $  b _ {j} $
in the transposed problem are integers, then there is an optimal solution for which all  $  x _ {ij }  $
are integers (Dantzig's theorem on integral solutions of the transport problem).

In the assignment problem, for such a solution  $  x _ {ij }  $
is either zero or one;  $  x _ {ij }  = 1 $
means that person  $  i $
is assigned to job  $  j $; 
the weight  $  c _ {ij }  $
is the utility of person  $  i $
assigned to job  $  j $.

The special structure of the transport problem and the assignment problem makes it possible to use algorithms that are more efficient than the [[Simplex method|simplex method]]. Some of these use the Hungarian method (see, e.g., [[#References|[a5]]], [[#References|[a1]]], Chapt. 7), which is based on the König–Egervary theorem (see [[König theorem|König theorem]]), the method of potentials (see [[#References|[a1]]], [[#References|[a2]]]), the out-of-kilter algorithm (see, e.g., [[#References|[a3]]]) or the transportation simplex method.

In turn, the transportation problem is a special case of the network optimization problem.

A totally different assignment problem is the [[Pole assignment problem|pole assignment problem]] in control theory.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D.B. Yudin,   E.G. Gol'shtein,   "Linear programming" , Israel Program Sci. Transl.  (1965)  (In Russian)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Frisch,   "La résolution des problèmes de programme linéaire par la méthode du potentiel logarithmique"  ''Cahier Sém. Econom.'' , '''4'''  (1956)  pp. 20–23</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  K. Murtz,   "Linear and combinatorial programming" , Wiley  (1976)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Grötschel,   L. Lovász,   A. Schrijver,   "Geometric algorithms and combinatorial optimization" , Springer  (1987)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  C.H. Papadimitriou,   K. Steiglitz,   "Combinatorial optimization" , Prentice-Hall  (1982)</TD></TR></table>