Formulating an Allocation Problem as a Linear Programming Problem

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:

Whereimplies Andrew,implies Boris andimplies 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, oneand 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

You have no rights to post comments