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.