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