9.5. Optimal Assignement Problem.
The problem: Let us consider the Personnel Assignment Problem and, in addition, we take into account the the effectiveness of the workers in their various jobs. In this case, one is interested in an assignment that maximises the total effectiveness of the workers.
The problem of finding such an assignment is known as the Optimal Assignment Problem.
The mathematical model:
We construct a weighted complete bipartite graph G with
bipartition , where
,
and edge has weight
, the effectiveness of of worker
in job
.
The optimal assignment problem is equivalent to that of finding a maximum-weight perfect matching in this weighted graph. The optimal solution is an optimal matching.
Solution 1.: We enumerate all n! perfect matchings and find an opti-mal one among them.
For large n, such a procedure is inefficient and time consuming.
A feasible
vertex labelling is a real-valued function l on the vertex-set such that, for all
.
We call as the label of the vertex v. It is
easy to see that such a labeling always exists. For example
Let denote the set of those edges for which
equality holds:
Let us consider the spanning subgraph which we call as the equality subgraph
corresponding to the feasible vertex labeling l.
Theorem 9.9.: Let l be a feasible vertex
labeling of G. If contains a perfect
matching
, then
is an optimal matching of G.
Proof.
Suppose that contains a perfect matching
.
Since
is a span-ning subgraph of G,
is also a perfect matching of G. Then
since each belongs to the equality subgraph
and the ends of edges
cover each vertex exactly once.
On the other hand, if M is any perfect matching of G, then
Form these it
follows that . Thus
is an optimal
matching.
The Kuhn-Munkers Algorithm (1957):
1. Let
and we start with an arbitrary feasible labelling l, determine
, and choose an arbitrary matching
in
.
2. If
saturates every vertex in X, then
is a perfect matching (since
), and hence, by Theorem 9.9, an optimal matching. So, the algorithm stops.
Otherwise, let u be an
-unsaturated vertex in X. Set
.
3. If
, go to Step 4. Otherwise,
. Compute
and the feasible vertex labelling
given by
Note that
and that
.
Replace l by
and
by
.
4. Choose a vertex y in
. As in the tree-growing procedure of the PA P, consider whether or not y is
- saturated.
If y is
- saturated, with
, replace S by
and T by
, and go to Step 3.
Otherwise, let P be an
- augmenting
-path in
, replace
by
and
, go to Step 2.