The Assignment Problem is a special application of the transhipment theory in operational research, and it can be translated into a corresponding network problem:

The assignment problem

Maximize: S(ij) sij xij

Subject to: S(i) xij = 1 for all j=1, 2,..., 10

S(j) xij = 1 for all i=1, 2,..., 10

xij = 0 or 1 for all i and j.

Here, sij can be utility, profit, score, or other attributes that one would want to maximize in a problem relating to assigning i to j. On the other hand, xij is an indicator variable, which takes on the value of 1 if object i is assigned to sink j, and the value is 0 if object i is not assigned to sink j.

The related problem can be formulated as:

Minimize: SS (ij) (-sij) xij

Subject to: S(i) xij = 1 for all j=1, 2,..., 10

S(j) xij = 1 for all i=1, 2,..., 10

xij = 0 or 1 for all i and j.

which can be solved by the network simplex method. As shown on the diagram, the network has a source ui with a unit supply for each teacher i, and a sink vj for each school j. The score on each arc ui vj is -sij which is shown on the arc connecting ui and vj.

The problem reflects a situation where the overall satisfaction of the assignment is measured by the worst score resulted from a particular match. Consider the following algorithm of solving the network problem:

1. Let M consist of the arcs u1v1, u2v2,....u10v10.
2. Let t be the smallest of the 10 scores sij such that uivj e M.
3. If Gt contains no matching M* of size 10, then stop: M represents an optimal solution. Otherwise replace M by M* and return to step 1

In fact, this algorithm to the development of a bottleneck assignment problem that can be shown to be equivalent of finding the largest matching in a bipartite graph.

To obtain the optimal assignment of each of the ten teachers to the ten schools, we formulated the problem in terms of a mathematical model very similar to the assignment problem as discussed above. The problem is then solved using a software GAMS. The code of the program to the core problem and each of the extensions, along with the excerpts of the output, are reproduced in the Appendices.

Similarities in the structure of mathematical model can be found among the different models. However, each assignment problem has optimal solution that is largely dependent on the specific data relating to the problem and any additional constraints imposed in the various situation. As a result, the unique solution for the core problem and each of the extensions are not reproduced here. Readers can review the solution summary subsection in each of the problem and extension.