## Linear Programming Formulation Of Assignment Problem Operations

## OR-Notes

## J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

#### Linear programming formulation examples

#### Linear programming example 1996 MBA exam

A cargo plane has three compartments for storing cargo: front, centre and rear. These compartments have the following limits on both weight and space:

Compartment Weight capacity (tonnes) Space capacity (cubic metres) Front 10 6800 Centre 16 8700 Rear 8 5300Furthermore, the weight of the cargo in the respective compartments must be the same proportion of that compartment's weight capacity to maintain the balance of the plane.

The following four cargoes are available for shipment on the next flight:

Cargo Weight (tonnes) Volume (cubic metres/tonne) Profit (£/tonne) C1 18 480 310 C2 15 650 380 C3 23 580 350 C4 12 390 285Any proportion of these cargoes can be accepted. The objective is to determine *how much* (if any) of each cargo C1, C2, C3 and C4 should be accepted and *how to distribute* each among the compartments so that the total profit for the flight is maximised.

- Formulate the above problem as a linear program
- What assumptions are made in formulating this problem as a linear program?
- Briefly describe the advantages of using a software package to solve the above linear program, over a judgemental approach to this problem.

#### Solution

#### Variables

We need to decide how much of each of the four cargoes to put in each of the three compartments. Hence let:

x_{ij} be the number of tonnes of cargo i (i=1,2,3,4 for C1, C2, C3 and C4 respectively) that is put into compartment j (j=1 for Front, j=2 for Centre and j=3 for Rear) where x_{ij} >=0 i=1,2,3,4; j=1,2,3

Note here that we are explicitly told we can split the cargoes into any proportions (fractions) that we like.

#### Constraints

- cannot pack more of each of the four cargoes than we have available

x_{11} + x_{12} + x_{13} <= 18

x_{21} + x_{22} + x_{23} <= 15

x_{31} + x_{32} + x_{33} <= 23

x_{41} + x_{42} + x_{43} <= 12

- the weight capacity of each compartment must be respected

x_{11} + x_{21} + x_{31} + x_{41} <= 10

x_{12} + x_{22} + x_{32} + x_{42} <= 16

x_{13} + x_{23} + x_{33} + x_{43} <= 8

- the volume (space) capacity of each compartment must be respected

480x_{11} + 650x_{21} + 580x_{31} + 390x_{41} <= 6800

480x_{12} + 650x_{22} + 580x_{32} + 390x_{42} <= 8700

480x_{13} + 650x_{23} + 580x_{33} + 390x_{43} <= 5300

- the weight of the cargo in the respective compartments must be the same proportion of that compartment's weight capacity to maintain the balance of the plane

[x_{11} + x_{21} + x_{31} + x_{41}]/10 = [x_{12} + x_{22} + x_{32} + x_{42}]/16 = [x_{13} + x_{23} + x_{33} + x_{43}]/8

#### Objective

The objective is to maximise total profit, i.e.

maximise 310[x_{11}+ x_{12}+x_{13}] + 380[x_{21}+ x_{22}+x_{23}] + 350[x_{31}+ x_{32}+x_{33}] + 285[x_{41}+ x_{42}+x_{43}]

The basic assumptions are:

- that each cargo can be split into whatever proportions/fractions we desire
- that each cargo can be split between two or more compartments if we so desire
- that the cargo can be packed into each compartment (for example if the cargo was spherical it would not be possible to pack a compartment to volume capacity, some free space is inevitable in sphere packing)
- all the data/numbers given are accurate

The advantages of using a software package to solve the above linear program, rather than a judgemental approach are:

- actually maximise profit, rather than just believing that our judgemental solution maximises profit (we may have bad judgement, even if we have an MBA!)
- makes the cargo loading the decision one that we can solve in a routine operational manner on a computer, rather than having to exercise judgement each and every time we want to solve it
- problems that can be appropriately formulated as linear programs are almost always better solved by computers than by people
- can perform sensitivity analysis very easily using a computer

Linear programming example 1995 MBA exam

Briefly describe the main steps in using mathematical modelling to support management.

A canning company operates two canning plants. The growers are willing to supply fresh fruits in the following amounts:

- S1: 200 tonnes at £11/tonne
- S2: 310 tonnes at £10/tonne
- S3: 420 tonnes at £9/tonne

Shipping costs in £ per tonne are:

To: Plant A Plant B From: S1 3 3.5 S2 2 2.5 S3 6 4Plant capacities and labour costs are:

Plant A Plant B Capacity 460 tonnes 560 tonnes Labour cost £26/tonne £21/tonneThe canned fruits are sold at £50/tonne to the distributors. The company can sell at this price all they can produce.

The objective is to find the best mixture of the quantities supplied by the three growers to the two plants so that the company maximises its profits.

- Formulate the problem as a linear program and explain it
- Explain the meaning of the dual values associated with the supply and plant capacity constraints
- What assumptions have you made in expressing the problem as a linear program

#### Solution

The main steps in using mathematical modelling to support management are:

- 1. Problem identification
- Diagnosis of the problem from its symptoms if not obvious (i.e. what is the problem?)
- Delineation of the subproblem to be studied. Often we have to ignore parts of the entire problem.
- Establishment of objectives, limitations and requirements.
- 2. Formulation as a mathematical model
- 3. Model validation (or algorithm validation)
- Model validation involves running the algorithm for the model on the computer in order to ensure:
- the input data is free from errors
- the computer program is bug-free (or at least there are no outstanding bugs)
- the computer program correctly represents the model we are attempting to validate
- the results from the algorithm seem reasonable (or if they are surprising we can at least understand why they are surprising).
- 4. Solution of the model
- Standard computer packages, or specially developed algorithms, can be used to solve the model.
- In practice, a "solution" often involves very many solutions under varying assumptions to establish sensitivity.
- 5. Implementation
- This phase may involve the implementation of the results of the study or the implementation of the
*algorithm*for solving the model as an operational tool (usually in a computer package).

To formulate the problem given in the question as a linear program we need to define:

- variables
- constraints
- objective

#### Variables

We need to decide how much to supply from each of the three growers to each of the two canning plants. Hence let x_{ij} be the number of tonnes supplied from grower i (i=1,2,3 for S1, S2 and S3 respectively) to plant j (j=1 for Plant A and j=2 for Plant B) where x_{ij} >=0 i=1,2,3; j=1,2

#### Constraints

- cannot supply more than a grower has available - a supply constraint

x_{11} + x_{12} <= 200

x_{21} + x_{22} <= 310

x_{31} + x_{32} <= 420

- the capacity of each plant must be respected - a capacity constraint

x_{11} + x_{21} + x_{31} <= 460

x_{12} + x_{22} + x_{32} <= 560

#### Objective

The objective is to maximise total profit, i.e.

maximise revenue - grower supply cost - grower shipping cost - plant labour cost

and this is

maximise 50SUM{i=1,2,3}SUM{j=1,2}x_{ij} - 11(x_{11}+x_{12}) - 10(x_{21}+x_{22}) - 9(x_{31}+x_{32}) - 3x_{11} - 2x_{21} - 6x_{31} - 3.5x_{12} - 2.5x_{22} - 4x_{32} - 26SUM{i=1,2,3}x_{i1} - 21SUM{i=1,2,3}x_{i2}

The dual values associated with the supply and plant capacity constraints in the optimal solution of the above linear program tell us by how much the optimal objective function value will change if we change the right-hand side of the corresponding constraints

The basic assumptions are:

- can ship from a grower any quantity we desire
- no loss in weight in processing at the plant
- no loss in weight in shipping
- can sell all we produce
- all the data/numbers given are accurate

Linear programming example 1993 UG exam

The production manager of a chemical plant is attempting to devise a shift pattern for his workforce. Each day of every working week is divided into three eight-hour shift periods (00:01-08:00, 08:01-16:00, 16:01-24:00) denoted by night, day and late respectively. The plant must be manned at all times and the minimum number of workers required for each of these shifts over any working week is as below:

Mon Tues Wed Thur Fri Sat Sun Night 5 3 2 4 3 2 2 Day 7 8 9 5 7 2 5 Late 9 10 10 7 11 2 2The union agreement governing acceptable shifts for workers is as follows:

- Each worker is assigned to work
*either*a night shift*or*a day shift*or*a late shift and once a worker has been assigned to a shift they must remain on the same shift every day that they work. - Each worker works four consecutive days during any seven day period.

In total there are currently 60 workers.

- Formulate the production manager's problem as a linear program.
- Comment upon the advantages/disadvantages you foresee of formulating and solving this problem as a linear program.

#### Solution

#### Variables

The union agreement is such that any worker can only start their four consecutive work days on one of the seven days (Mon to Sun) and in one of the three eight-hour shifts (night, day, late).

Let:

Monday be day 1, Tuesday be day 2, ..., Sunday be day 7

Night be shift 1, Day be shift 2, Late be shift 3

then the variables are:

N_{ij} the number of workers *starting* their four consecutive work days on day i (i=1,...,7) and shift j (j=1,...,3)

Note here that strictly these variables should be integer but, as we are explicitly told to formulate the problem as a linear program in part (a) of the question, we allow them to take fractional values.

#### Constraints

- upper limit on the total number of workers of 60

SUM{i=1 to 7} SUM{j=1 to 3} N_{ij} <= 60

since each worker can start his working week only once during the seven day, three shift, week

- lower limit on the total number of workers required for each day/shift period

let D_{ij} be the (known) number of workers required on day i (i=1,...,7) and shift period j (j=1,...,3) e.g. D_{53}=11 (Friday, Late)

then the constraints are

Monday: N_{1j}+ N

_{7j}+ N

_{6j}+ N

_{5j}>= D

_{1j }j=1,...,3 Tuesday: N

_{2j}+ N

_{1j}+ N

_{7j}+ N

_{6j}>= D

_{2j }j=1,...,3 Wednesday: N

_{3j}+ N

_{2j}+ N

_{1j}+ N

_{7j}>= D

_{3j }j=1,...,3 Thursday: N

_{4j}+ N

_{3j}+ N

_{2j}+ N

_{1j}>= D

_{4j }j=1,...,3 Friday: N

_{5j}+ N

_{4j}+ N

_{3j}+ N

_{2j}>= D

_{5j }j=1,...,3 Saturday: N

_{6j}+ N

_{5j}+ N

_{4j}+ N

_{3j}>= D

_{6j }j=1,...,3 Sunday: N

_{7j}+ N

_{6j}+ N

_{5j}+ N

_{4j}>= D

_{7j }j=1,...,3

The logic here is straightforward, for example for Wednesday (day 3) the workers working shift j on day 3 either started on Wednesday (day 3, N_{3j}) or on Tuesday (day 2, N_{2j}) or on Monday (day 1, N_{1j}) or on Sunday (day 7, N_{7j}) - so the sum of these variables is the total number of workers on duty on day 3 in shift j and this must be at least the minimum number required (D_{3j}).

#### Objective

It appears from the question that the production manager's objective is simply to find a feasible schedule so any objective is possible. Logically however he might be interested in reducing the size of the workforce so the objective function could be:

minimise SUM{i=1 to 7} SUM{j=1 to 3} N_{ij}

where all variables N_{ij}>=0 and continuous (i.e. can take fractional values).

This completes the formulation of the problem as a linear program.

Some of the advantages and disadvantages of solving this problem as a linear program are:

- really need variable values which are integer
- some workers will always end up working weekends
- how do we choose the workers to use, e.g. if N
_{43}=7 which 7 workers do we choose to begin their work week on day 4 working shift 3 - what happens if workers fail to report in (e.g. if they are sick) - we may fall below the minimum number required
- the approach above enables us to deal with the problem in a systematic fashion
- have the potential to reduce the size of the workforce by more effectively matching the resources to the needs

able to investigate changes (e.g. in shift patterns, workers needed per day, etc) very easily.

#### Linear programming example 1991 UG exam

A company manufactures four products (1,2,3,4) on two machines (X and Y). The time (in minutes) to process one unit of each product on each machine is shown below:

Machine X Y Product 1 10 27 2 12 19 3 13 33 4 8 23The profit per unit for each product (1,2,3,4) is £10, £12, £17 and £8 respectively. Product 1 must be produced on *both* machines X and Y but products 2, 3 and 4 can be produced on either machine.

The factory is very small and this means that floor space is very limited. Only one week's production is stored in 50 square metres of floor space where the floor space taken up by each product is 0.1, 0.15, 0.5 and 0.05 (square metres) for products 1, 2, 3 and 4 respectively.

Customer requirements mean that the amount of product 3 produced should be related to the amount of product 2 produced. Over a week approximately twice as many units of product 2 should be produced as product 3.

Machine X is out of action (for maintenance/because of breakdown) 5% of the time and machine Y 7% of the time.

Assuming a working week 35 hours long formulate the problem of how to manufacture these products as a linear program.

#### Solution

#### Variables

Essentially we are interested in the amount produced on each machine. Hence let:

x_{i} = amount of product i (i=1,2,3,4) produced on machine X per week

y_{i} = amount of product i (i=2,3,4) produced on machine Y per week

where x_{i} >= 0 i=1,2,3,4 and y_{i} >= 0 i=2,3,4

Note here that as product 1 must be processed on both machines X and Y we do not define y_{1}.

#### Constraints

0.1x_{1} + 0.15(x_{2} + y_{2}) + 0.5(x_{3} + y_{3}) + 0.05(x_{4} + y_{4}) <= 50

x_{2} + y_{2} = 2(x_{3} + y_{3})

Note here that as this is only an approximate (±5% say) constraint we might do better to express this constraint as

0.95[2(x_{3} + y_{3})] <= x_{2} + y_{2} <= 1.05[2(x_{3} + y_{3})]

10x_{1} + 12x_{2} + 13x_{3} + 8x_{4} <= 0.95(35)(60) (machine X)

27x_{1} + 19y_{2} + 33y_{3} + 23y_{4} <= 0.93(35)(60) (machine Y)

#### Objective

maximise profit, i.e.

maximise 10x_{1} + 12(x_{2} + y_{2}) + 17(x_{3} + y_{3}) + 8(x_{4} + y_{4})

#### Linear programming example 1987 UG exam

A company is planning its production schedule over the next six months (it is currently the end of month 2). The demand (in units) for its product over that timescale is as shown below:

Month 3 4 5 6 7 8 Demand 5000 6000 6500 7000 8000 9500The company currently has in stock: 1000 units which were produced in month 2; 2000 units which were produced in month 1; 500 units which were produced in month 0.

The company can only produce up to 6000 units per month and the managing director has stated that stocks must be built up to help meet demand in months 5, 6, 7 and 8. Each unit produced costs £15 and the cost of holding stock is estimated to be £0.75 per unit per month (based upon the stock held at the beginning of each month).

The company has a major problem with deterioration of stock in that the stock inspection which takes place at the end of each month regularly identifies ruined stock (costing the company £25 per unit). It is estimated that, on average, the stock inspection at the end of month t will show that 11% of the units in stock which were produced in month t are ruined; 47% of the units in stock which were produced in month t-1 are ruined; 100% of the units in stock which were produced in month t-2 are ruined. The stock inspection for month 2 is just about to take place.

The company wants a production plan for the next six months that avoids stockouts. Formulate their problem as a linear program.

Because of the stock deterioration problem the managing director is thinking of directing that customers should always be supplied with the oldest stock available. How would this affect your formulation of the problem?

#### Solution

#### Variables

Let

P_{t} be the production (units) in month t (t=3,...,8)

I_{it} be the number of units in stock at the *end* of month t which were produced in month i (i=t,t-1,t-2)

S_{it} be the number of units in stock at the *beginning* of month t which were produced in month i (i=t-1,t-2)

d_{it} be the demand in month t met from units produced in month i (i=t,t-1,t-2)

#### Constraints

P_{t} <= 6000

I_{22} = 1000

I_{12} = 2000

I_{02} = 500

- relate opening stock in month t to closing stock in previous months

S_{t-1,t} = 0.89I_{t-1,t-1}

S_{t-2,t} = 0.53I_{t-2,t-1}

- inventory continuity equation where we
*assume*we can meet demand in month t from production in month t. Let D_{t}represent the (known) demand for the product in month t (t=3,4,...,8) then

closing stock = opening stock + production - demand

and we have

I_{t,t} = 0 + P_{t} - d_{t,t}

I_{t-1,t} = S_{t-1,t} + 0 - d_{t-1,t}

I_{t-2,t} = S_{t-2,t} + 0 - d_{t-2,t}

where

d_{t,t} + d_{t-1,t} + d_{t-2,t} = D_{t}

all inventory (I,S) and d variables >= 0

#### Objective

Presumably to minimise cost and this is given by

SUM{t=3 to 8}15P_{t} + SUM{t=3 to 9}0.75(S_{t-1,t}+S_{t-2,t}) + SUM{t=3 to 8}25(0.11I_{t,t}+0.47I_{t-1,t}+1.0I_{t-2,t})

Note because we are told to formulate this problem as a linear program we assume all variables are fractional - in reality they are likely to be quite large and so this is a reasonable approximation to make (also a problem occurs with finding integer values which satisfy (for example) S_{t-1,t}=0.89I_{t-1,t-1} unless this is assumed).

If we want to ensure that demand is met from the oldest stock first then we can conclude that this is *already* assumed in the numerical solution to our formulation of the problem since (plainly) it worsens the objective to age stock unnecessarily and so in minimising costs we will automatically supply (via the d_{it} variables) the oldest stock first to satisfy demand (although the managing director needs to *tell* the employees to issue the oldest stock first).

#### Linear programming example 1986 UG exam

A company assembles four products (1, 2, 3, 4) from delivered components. The profit per unit for each product (1, 2, 3, 4) is £10, £15, £22 and £17 respectively. The maximum demand in the next week for each product (1, 2, 3, 4) is 50, 60, 85 and 70 units respectively.

There are three stages (A, B, C) in the manual assembly of each product and the man-hours needed for each stage per unit of product are shown below:

Product 1 2 3 4 Stage A 2 2 1 1 B 2 4 1 2 C 3 6 1 5The nominal time available in the next week for assembly at each stage (A, B, C) is 160, 200 and 80 man-hours respectively.

It is possible to vary the man-hours spent on assembly at each stage such that workers previously employed on stage B assembly could spend up to 20% of their time on stage A assembly and workers previously employed on stage C assembly could spend up to 30% of their time on stage A assembly.

Production constraints also require that the ratio (product 1 units assembled)/(product 4 units assembled) must lie between 0.9 and 1.15.

Formulate the problem of deciding how much to produce next week as a linear program.

#### Solution

#### Variables

Let

x_{i} = amount of product i produced (i=1,2,3,4)

t_{BA} be the amount of time transferred from B to A

t_{CA} be the amount of time transferred from C to A

#### Constraints

x_{1} <= 50

x_{2} <= 60

x_{3} <= 85

x_{4} <= 70

0.9 <= (x_{1}/x_{4}) <= 1.15

i.e. 0.9x_{4} <= x_{1} and x_{1} <= 1.15x_{4}

2x_{1} + 2x_{2} + x_{3} + x_{4} <= 160 + t_{BA} + t_{CA}

2x_{1} + 4x_{2} + x_{3} + 2x_{4} <= 200 - t_{BA}

3x_{1} + 6x_{2} + x_{3} + 5x_{4} <= 80 - t_{CA}

- limit on transferred time

t_{BA} <= 0.2(200)

t_{CA} <= 0.3(80)

#### Objective

maximise 10x_{1} + 15x_{2} + 22x_{3} + 17x_{4}

Note we neglect the fact that the x_{i} variables should be integer because we are told to formulate the problem as an LP.

#### Linear programming example

A company makes three products and has available 4 workstations. The production time (in minutes) per unit produced varies from workstation to workstation (due to different manning levels) as shown below:

Workstation 1 2 3 4 Product 1 5 7 4 10 2 6 12 8 15 3 13 14 9 17Similarly the profit (£) contribution (contribution to fixed costs) per unit varies from workstation to workstation as below

Workstation 1 2 3 4 Product 1 10 8 6 9 2 18 20 15 17 3 15 16 13 17If, one week, there are 35 working hours available at each workstation how much of each product should be produced given that we need at least 100 units of product 1, 150 units of product 2 and 100 units of product 3. Formulate this problem as an LP.

#### Solution

#### Variables

At first sight we are trying to decide how much of each product to make. However on closer inspection it is clear that we need to decide how much of each product to make at each workstation. Hence let

x_{ij} = amount of product i (i=1,2,3) made at workstation j (j=1,2,3,4) per week.

Although (strictly) all the x_{ij} variables should be integer they are likely to be quite large and so we let them take fractional values and ignore any fractional parts in the numerical solution. Note too that the question explicitly asks us to formulate the problem as an LP rather than as an IP.

#### Constraints

We first formulate each constraint in words and then in a mathematical way.

- limit on the number of minutes available each week for each workstation

5x_{11} + 6x_{21} + 13x_{31} <= 35(60)

7x_{12} + 12x_{22} + 14x_{32} <= 35(60)

4x_{13} + 8x_{23} + 9x_{33} <= 35(60)

10x_{14} + 15x_{24} + 17x_{34} <= 35(60)

- lower limit on the total amount of each product produced

x_{11} + x_{12} + x_{13} + x_{14} >= 100

x_{21} + x_{22} + x_{23} + x_{24} >= 150

x_{31} + x_{32} + x_{33} + x_{34} >= 100

#### Objective

Presumably to maximise profit - hence we have

maximise

10x_{11} + 8x_{12} + 6x_{13} + 9x_{14} + 18x_{21} + 20x_{22} + 15x_{23} + 17x_{24} + 15x_{31} + 16x_{32} + 13x_{33} + 17x_{34}

#### Production planning problem

Consider the production of tin cans which are stamped from metal sheets. A can consists of a main body and two ends,. We have 4 possible stamping patterns (involving 2 different types (sizes) of metal sheet). as shown below

We have the following information:

Pattern 1 2 3 4 Type of sheet used 1 2 1 1 Number of main bodies 1 4 2 0 Number of ends 7 4 3 9 Amount of scrap s_{1}s

_{2}s

_{3 }s

_{4 }Time to stamp (hours) t

_{1}t

_{2}t

_{3 }t

_{4}

Note here that the s_{i} (i=1,2,3,4) and the t_{i} (i=1,2,3,4) are *not* variables but constants (which have a known value). Often in formulating LP's it is easier to use a symbol for a number rather than write out the number in full every time it occurs in a constraint or in the objective function.

Let P be the profit obtained from selling one can, C be the cost per unit of scrap, T be the total number of hours available per week, L_{1} be the number of metal sheets of type 1 which are available for stamping per week and L_{2} be the number of metal sheets of type 2 which are available for stamping per week.

At the start of the week there is nothing in stock. Each (unused) main body in stock at the end of the week incurs a stock-holding cost of c_{1}. Similarly each (unused) end in stock at the end of the week incurs a stock-holding cost of c_{2}. Assume that all cans produced one week are sold that week.

How many cans should be produced per week?

#### Production planning solution

#### Variables

Let

x_{i} be the number of patterns of type i (i=1,2,3,4) stamped per week

y be the number of cans produced per week

Note x_{i} >= 0 i=1,2,3,4 and y >= 0 and again we assume that the x_{i} and y are large enough for fractional values not to be significant.

#### Constraints

t_{1}x_{1} + t_{2}x_{2} + t_{3}x_{3} + t_{4}x_{4} <= T

x_{1} + x_{3} + x_{4} <= L_{1} (sheet 1)

x_{2} <= L_{2} (sheet 2)

y = min[ (7x_{1}+4x_{2}+3x_{3}+9x_{4})/2, (x_{1}+4x_{2}+2x_{3}) ]

where the first term in this expression is the limit imposed upon y by the number of can ends produced and the second term in this expression is the limit imposed upon y by the number of can bodies produced. This constraint (because of the min[,] part) is not a linear constraint.

#### Objective

Presumably to maximise profit - hence

maximise

revenue - cost of scrap - unused main bodies stock - holding cost - unused ends stock - holding cost

i.e. maximise

Py - C(s_{1}x_{1} + s_{2}x_{2} + s_{3}x_{3} + s_{4}x_{4}) - c_{1}(x_{1} + 4x_{2} + 2x_{3} - y) - c_{2}((7x_{1} + 4x_{2} + 3x_{3} + 9x_{4}) - 2y)

As noted above this formulation of the problem is not an LP - however it is relatively easy (for this *particular* problem) to turn it into an LP by replacing the y = min[,] non-linear equation by *two* linear equations.

Suppose we replace the constraint

y = min[ (7x_{1}+4x

_{2}+3x

_{3}+9x

_{4})/2, (x

_{1}+4x

_{2}+2x

_{3}) ] (A)

by the two constraints

y <= (7x_{1}+4x

_{2}+3x

_{3}+9x

_{4})/2 (B) y <= (x

_{1}+4x

_{2}+2x

_{3}) (C)

(which are both linear constraints) then we do have an LP and in the *optimal* solution of this LP either:

- constraint (B) or constraint (C) is satisfied with equality, in which case constraint (A) is also satisfied with equality; or

- neither constraint (B) nor constraint (C) is satisfied with equality i.e. y < (7x
_{1}+4x_{2}+3x_{3}+9x_{4})/2*and*y < (x_{1}+4x_{2}+2x_{3}) - but in this case we can increase y (without changing any x_{i}values), increasing the objective function (assuming P + c_{1}+ 2c_{2}>0) and contradicting the statement (above) that we already had the optimal solution.

Hence case (b) cannot occur and so case (a) is valid - replacing constraint (A) by constraints (B) and (C) generates a valid LP formulation of the problem.

Note that this problem illustrates that even if our initial formulation of the problem is non-linear we may be able to transform it into an LP.

Note too that it is relatively easy to extend the LP formulation of the problem to cope with the situation where can bodies/ends unused at the end of one week are available for production the following week.

Production planning problem

A company is producing a product which requires, at the final assembly stage, three parts. These three parts can be produced by two different departments as detailed below.

Production rate (units/hr) Part 1 Part 2 Part 3 Cost (£/hr) Department 1 7 6 9 25.0 Department 2 6 11 5 12.5One week, 1050 finished (assembled) products are needed (but up to 1200 can be produced if necessary). If department 1 has 100 working hours available, but department 2 has 110 working hours available, formulate the problem of minimising the cost of producing the finished (assembled) products needed this week as an LP, subject to the constraint that limited storage space means that a total of only 200 unassembled parts (of all types) can be stored at the end of the week.

Note: because of the way production is organised in the two departments it is not possible to produce, for example, only one or two parts in each department, e.g. one hour of working in department 1 produces 7 part 1 units, 6 part 2 units and 9 part 3 units and this cannot be altered.

#### Production planning solution

#### Variables

We need to decide the amount of time given over to the production of parts in each department (since we, obviously, may not make use of all the available working time) and also to decide the total number of finished (assembled) products made. Hence let:

x_{i} = number of hours used in department i (i=1,2)

y = number of finished (assembled) products made

where x_{i} >= 0 i=1,2 and y >= 0 and (as is usual) we assume that any fractional parts in the variables in the numerical solution of the LP are not significant.

#### Constraints

x_{1} <= 100

x_{2} <= 110

- number of assembled products produced

1050 <= y <= 1200

- production constraints relating the hours worked to the number of assembled products

We produce (7x_{1} + 6x_{2}) part 1 units, (6x_{1} + 11x_{2}) part 2 units and (9x_{1} + 5x_{2}) part 3 units. Now to ensure that the number of assembled products produced is exactly y we need at least y part 1 units, at least y part 2 units and at least y part 3 units. Hence we have the three constraints

7x_{1} + 6x_{2} >= y

6x_{1} + 11x_{2} >= y

9x_{1} + 5x_{2} >= y

- the total number of parts (of all types) produced is (7x
_{1}+ 6x_{2}) + (6x_{1}+ 11x_{2}) + (9x_{1}+ 5x_{2}) = 22x_{1}+ 22x_{2}. Since we produce exactly y assembled products the number of parts left over at the end of the week is (22x_{1}+ 22x_{2}) - 3y and hence the constraint relating to the limited storage space is given by

22x_{1} + 22x_{2} - 3y <= 200

#### Objective

minimise 25.0x_{1} + 12.5x_{2}

Obvious extensions to this problem involve increasing (from the current value of 3) the number of parts needed for the finished product and changing the ratio of parts used in a finished product from its current value of 1:1:1.

The **assignment problem** is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching (or minimum weight perfect matching) in a weightedbipartite graph.

In its most general form, the problem is as follows:

- The problem instance has a number of
*agents*and a number of*tasks*. Any agent can be assigned to perform any task, incurring some*cost*that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the*total cost*of the assignment is minimized.

If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the *linear assignment problem*. Commonly, when speaking of the *assignment problem* without any additional qualification, then the *linear assignment problem* is meant.

## Algorithms and generalizations[edit]

The Hungarian algorithm is one of many algorithms that have been devised that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents. Other algorithms include adaptations of the primal simplex algorithm, and the auction algorithm.

The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure.

When a number of agents and tasks is very large, a parallel algorithm with randomization can be applied. The problem of finding minimum weight maximum matching can be converted to finding a minimum weight perfect matching. A bipartite graph can be extended to a complete bipartite graph by adding artificial edges with large weights. These weights should exceed the weights of all existing matchings to prevent appearance of artificial edges in the possible solution. As shown by Mulmuley, Vazirani & Vazirani (1987), the problem of minimum weight perfect matching is converted to finding minors in the adjacency matrix of a graph. Using the isolation lemma, a minimum weight perfect matching in a graph can be found with probability at least ½. For a graph with n vertices, it requires time.

## Example[edit]

Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.

However, the assignment problem can be made rather more flexible than it first appears. In the above example, suppose that there are four taxis available, but still only three customers. Then a fourth dummy task can be invented, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. The assignment problem can then be solved in the usual way and still give the best solution to the problem.

Similar adjustments can be done in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.

## Formal mathematical definition[edit]

The formal definition of the **assignment problem** (or **linear assignment problem**) is

- Given two sets,
*A*and*T*, of equal size, together with a weight function*C*:*A*×*T*→**R**. Find a bijection*f*:*A*→*T*such that the cost function:

is minimized.

Usually the weight function is viewed as a square real-valued matrix*C*, so that the cost function is written down as:

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

The problem can be expressed as a standard linear program with the objective function

subject to the constraints

The variable represents the assignment of agent to task , taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent.

## One thought on “Linear Programming Formulation Of Assignment Problem Operations”