An allocation problem can be formulated as a linear programming problem with the introduction of decision variables. Suppose for example we have the following cost matrix for workers doing specific tasks:
|
|
Task 1 |
Task 2 |
Task 3 |
|
Andrew |
9 |
25 |
17 |
|
Boris |
11 |
10 |
49 |
|
Charles |
27 |
24 |
13 |
We can define decision variables x-{ij} with the following properties:
Where
implies Andrew,
implies Boris and
implies Charles, and
implies task 1, 2 or 3 respectively.
The objective is to minimise the total cost. We can write the objective function therefore as
The constraints are found by using the requirement that each worker be allocated to one task so that for each task, one
and the others equal 0 for that task. The requirement that just one worker be allocated to task 1 implies that
The requirement that just one worker be allocated to task 2 implies that
The requirement that just one worker be allocated to task 1 implies that
