### Assignment Problem

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