A typical assignment problem, presented in the classic manner, is shown in Fig. 12. Here there are five machines to be assigned to five jobs. The numbers in the matrix indicate the cost of doing each job with each machine. Jobs with costs of M are disallowed assignments. The problem is to find the minimum cost matching of machines to jobs.

Figure 12. Matrix model of the assignment problem.

The network model is in Fig. 13. It is very similar to the transportation model except the external flows are all +1 or -1. The only relevant parameter for the assignment model is arc cost (not shown in the figure for clarity) ; all other parameters should be set to default values. The assignment network also has the bipartite structure.

Figure 13. Network model of the assignment problem.

The solution to the assignment problem as shown in Fig. 14 has a total flow of 1 in every column and row, and is the assignment that minimizes total cost.

Figure 14. Solution to the assignment Problem