LGT5102 Models for decision making

Linear Programming: Formulation

●
Example: Personnel Scheduling Problem
●
Example: Transportation Problem
●
Example: Assignment Problem
 Union Airways Personnel Scheduling

• Union Airways is adding more flights to and from its hub airport
and so needs to hire additional customer service agents.
• The five authorized eight-hour shifts are
– Shift 1: 6:00 AM to 2:00 PM
– Shift 2: 8:00 AM to 4:00 PM
– Shift 3: Noon to 8:00 PM
– Shift 4: 4:00 PM to midnight
– Shift 5: 10:00 PM to 6:00 AM

Question: How many agents should be assigned to each shift?

2
 Schedule Data
Time Periods Covered by Shift

Time Period 1 2 3 4 5 Minimum

Number of
Agents Needed
6 AM to 8 AM √ 48

8 AM to 10 AM √ √ 79

10 AM to noon √ √ 65

Noon to 2 PM √ √ √ 87

2 PM to 4 PM √ √ 64

4 PM to 6 PM √ √ 73

6 PM to 8 PM √ √ 82

8 PM to 10 PM √ 43

10 PM to midnight √ √ 52

Midnight to 6 AM √ 15

Daily cost per agent $170 $160 $175 $180 $195

3
 Algebraic Formulation

Let Si = Number working shift i (for i = 1 to 5),

Minimize Cost = $170 S1 + $160 S2 + $175 S3 + $180 S4 + $195 S5

subject to
Total agents 6AM–8AM: S1 ≥ 48
Total agents 8AM–10AM: S1 + S2 ≥ 79
Total agents 10AM–12PM: S1 + S2 ≥ 65
Total agents 12PM–2PM: S1 + S2 + S3 ≥ 87
Total agents 2PM–4PM: S2 + S3 ≥ 64
Total agents 4PM–6PM: S3 + S4 ≥ 73
Total agents 6PM–8PM: S3 + S4 ≥ 82
Total agents 8PM–10PM: S4 ≥ 43
Total agents 10PM–12AM: S4 + S5 ≥ 52
Total agents 12AM–6AM: S5 ≥ 15
and Si ≥ 0 (for i = 1 to 5) 4
Spreadsheet Formulation

5
 The Big M Transportation Problem

• The Big M Company produces a variety of heavy duty

machinery at two factories. One of its products is a large
turret lathe.
• Orders have been received from three customers for the
turret lathe.
Question: How many lathes should be shipped from each
factory to each customer?

6
 Some Data

Shipping Cost for Each Lathe

To Customer 1 Customer 2 Customer 3
From Output
Factory 1 $700 $900 $800 12 lathes
Factory 2 800 900 700 15 lathes
Order Size 10 lathes 8 lathes 9 lathes

7
 The Distribution Network

C1 10 lathes
needed
$700/lathe

12 lathe F1
produced
$900/lathe

$800/lathe
C2 8 lathes
needed
$800/lathe $900/lathe

15 lathes F2
produced

$700/lathe
C3 9 lathes
needed 8
 Algebraic Formulation

Let Sij = Number of lathes to ship from i to j (i = F1, F2; j = C1, C2, C3).

Minimize Cost = $700SF1-C1 + $900SF1-C2 + $800SF1-C3

+ $800SF2-C1 + $900SF2-C2 + $700SF2-C3
subject to
Factory 1: SF1-C1 + SF1-C2 + SF1-C3 = 12
Factory 2: SF2-C1 + SF2-C2 + SF2-C3 = 15
Customer 1: SF1-C1 + SF2-C1 = 10
Customer 2: SF1-C2 + SF2-C2 = 8
Customer 3: SF1-C3 + SF2-C3 = 9
and Sij ≥ 0 (i = F1, F2; j = C1, C2, C3).
 Spreadsheet Formulation

A B C D E F G H
1 Big M Company Distribution Problem
2
3 Shipping Cost
4 (per Lathe) Customer 1 Customer 2 Customer 3
5 Factory 1 $700 $900 $800
6 Factory 2 $800 $900 $700
7
8 Total
9 Shipped
10 Units Shipped Customer 1 Customer 2 Customer 3 Out Output
11 Factory 1 10 2 0 12 = 12
12 Factory 2 0 6 9 15 = 15
13 Total To Customer 10 8 9
14 = = = Total Cost
15 Order Size 10 8 9 $20,500
10
 Types of Functional Constraints

Type Form* Typical Interpretation Main Usage

Resource constraint LHS ≤ RHS For some resource, Resource-allocation

Amount used ≤ problems and mixed
Amount available problems
Benefit constraint LHS ≥ RHS For some benefit, Cost-benefit-trade-off
Level achieved ≥ problems and mixed
Minimum Acceptable problems

Fixed-requirement LHS = RHS For some quantity, Transportation

constraint Amount provided = problems and mixed
Required amount problems

* LHS = Left-hand side (a SUMPRODUCT function).

RHS = Right-hand side (a constant).

11
 Sellmore Company Assignment Problem
• The marketing manager of Sellmore Company will be holding the
company’s annual sales conference soon.
• He is hiring four temporary employees:
– Ann
– Ian
– Joan
– Sean
• Each will handle one of the following four tasks:
– Word processing of written presentations
– Computer graphics for both oral and written presentations
– Preparation of conference packets, including copying and organizing
materials
– Handling of advance and on-site registration for the conference
Question: Which person should be assigned to which task? 12
 Data for the Sellmore Problem

Required Time per Task (Hours)

Temporary Word Graphics Packets Registrations Hourly
Employee Processing Wage
Ann 35 41 27 40 $14

Ian 47 45 32 51 12
Joan 39 56 36 43 13
Sean 32 51 25 46 15

13
 Spreadsheet Formulation
A B C D E F G H I J
1 Sellmore Co. Assignment Problem
2
3 Task
4 Required Time Word Hourly
5 (Hours) Processing Graphics Packets Registrations Wage
6 Ann 35 41 27 40 $14
7 Assignee Ian 47 45 32 51 $12
8 Joan 39 56 36 43 $13
9 Sean 32 51 25 46 $15
10
11
12 Task
13 Word
14 Cost Processing Graphics Packets Registrations
15 Ann $490 $574 $378 $560
16 Assignee Ian $564 $540 $384 $612
17 Joan $507 $728 $468 $559
18 Sean $480 $765 $375 $690
19
20
21 Task
22 Word Total
23 Assignment Processing Graphics Packets Registrations Assignments Supply
24 Ann 0 0 1 0 1 = 1
25 Assignee Ian 0 1 0 0 1 = 1
26 Joan 0 0 0 1 1 = 1
27 Sean 1 0 0 0 1 = 1 14
28 Total Assigned 1 1 1 1
29 = = = = Total Cost
30 Demand 1 1 1 1 $1,957
 Assignment

●
Review
 Slides, lecture notes (incl. review questions).

●
Assignment
 Problem: 1 (Web Mercantile); 2 (Fagersta); 3 (Four cargo ships)

 Submission via Blackboard: due date (check Blackboard)

 Requirement: please upload a single Word file for question answers
(incl. explaining your models) and a single Excel file containing
spreadsheets. Name them (word/spreadsheet files) properly.
●
Preview for next class
 Lecture notes “modeling with spreadsheets”

15