There are n people….

The assignment problem introduced in Section 3.4 can be stated as follows.

There are n people who need to be assigned to execute n jobs, one person per job. (That is, each person is assigned to exactly one job and each job is assigned to exactly one person.) The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i,j = 1,...,n. The problem is to assign the people to the jobs to minimize the total cost of the assignment. Express the assignment problem as a 0—1 linear programming problem.

Solution

The above problem can be represented using the following constraints, where Represents the cost of assignment job to person.

Subject to:

The above problem can be represented using a matrix representation with the following matrix values. The problem can be represented by linear equation:

.

.

.

The above forms the matrix shown below.

	Jobs to be assigned
Person	1	2	3	…	N
1	C[1,1]	C[1,2]	C[1,3]	…	C[1,n]
2	C2,1]	C[2,2]	C[2,3]	…	C[2,n]
…
N	C[n,1]	C[n,2]	C[n,3]	…	C[n,n]

The above matrix represents a Linear Programming problem. Using the Hungarian model (algorithms), the above matrix can be solved to give the expected job allocation for each individual.