1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A B C D E F G H I J K
California Manufacturing Co. Facility Location Problem
NPV ($millions) Los Angeles San Francisco San Diego Range Name Cells
Warehouse 6 4 5 Build? C16:D18
BuildFactory? C18:D18
Factory 8 5 7 BuildWarehouse? C16:D16
CapitalAvailable G12
Capital Required
CapitalRequired C10:D12
($millions) Los Angeles San Francisco San Diego CapitalSpent E12
Warehouse 5 2 3 Capital Capital MaxWarehouses G16
Spent Available NPV C4:D6
Factory 6 3 4 10 <= 10 TotalNPV D20
TotalWarehouses E16
Total Maximum
Build? Los Angeles San Francisco San Diego
Warehouses
Warehouses
Warehouse 0 0 1 1 <= 1
<= <= <=
Factory 0 1 1
Total NPV ($millions) 17
1
2
3
4
5
6
7
8
9
10
11
12
A B C D E F G H I
Time Needed (hours)
Marketing Cooking
Dishwashing
Laundry
Eve 4.5 7.8 3.6 2.9
Steven 4.9 7.2 4.3 3.1
Does Task? Tasks
Marketing Cooking
Dishwashing
Laundry
Performed
Eve 1 0 1 0 2 = 2
Steven 0 1 0 1 2 = 2
Total 1 1 1 1
= = = = Total Time (hours)
1 1 1 1 18.4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
A B C D E F G H I
Project 1 Project 2 Project 3 Project 4 Project 5
Estimated Profit
11.8 1.6 0.8 1.4
($million) Capital Capital
Spent Available
Capital Required for Project ($million) ($million) ($million)
Capital 6 12 10 4 8 20 <= 20
Total Profit
Project 1 Project 2 Project 3 Project 4 Project 5 ($million)
Undertake? 1 0 1 1 0 3.4
Capital Total
Available Undertake? Profit
($million) Project 1 Project 2 Project 3 Project 4 Project 5 ($million)
101103.4
16 010102.6
18 100113.2
20 101103.4
22 001113.8
24 1 0 1 0 1 4
26 110014.2
28 101114.8
30 1 1 0 1 1 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
A B C D E F G H I J K
Investment Opportunity
1234567
Estimated Profit
17 10 15 19 713 9
($million) Capital Capital
Capital Required for Investment Opportunity ($million)
Spent Available
Capital 43 28 34 48 17 32 23 100 <= 100
Investment Opportunity Total Profit
1 2 3 4 5 6 7 ($million)
Undertake? 1 0 1 0 0 0 1 41
<= <=
only if (1 or 2) 1 1
(1 or 2) 1 <= 1
(3 or 4) 1 <= 1
1
2
3
4
5
6
7
8
9
10
11
A B C D E F G
Customer 1 Customer 2 Customer 3
Startup Cost ($million) 3 2 0 Capacity Capacity
Marginal net Revenue ($million)
2 3 0.8 Used Available
Capacity Used per Plane 20% 40% 20% 100% <= 100%
Maximum Order 3 2 5
Start Up? 0 1 1 Total Startup Cost 2
Total Revenue 6.8
Planes to Produce 0 2 1 Total Profit 4.8
<= <= <= ($million)
Maximum Order (if start up) 0 2 5
1
2
3
4
5
6
7
8
9
10
11
12
13
A B C D E F G H I J
OA OB AC AD BC BD CT DT
Cost 3 6 6 5 4 3 3 2
OA OB AC AD BC BD CT DT
Travel Path?
10010001
<= <= <= <= <= <=
only if 1 1 0 0 0 1
OA OA OB OB AC or BC AD or BD
OA or OB 1 = 1
AC, AD, BC, or BD 1 = 1 Total Cost
Ct or DT 1 = 1 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A B C D E F G H I J K L M N
12345678910
Time (hours)
6475465376
Total on
Location Route
A 1 1 1 1 >= 1
B 1 1 1 1 1 1 >= 1
C 1 1 1 1 1 >= 1
D 1 1 1 1 >= 1
E 1 1 1 1 >= 1
F 1 1 1 >= 1
G 1 1 1 1 1 >= 1
H 1 1 1 1 >= 1
I 1 1 1 1 >= 1
12345678910 Total
Do Route? 0 0 0 1 1 0 0 1 0 0 3 <= 3
Total Time (hours) 12
Route
Route
Delivery Location on Route?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
A B C D E F G H I
Response Station Location Avg. Emergencies
Time (min) Tract 1 Tract 2 Tract 3 Tract 4 Tract 5 per Day
Tract 1 5 20 15 25 10 2
Tract 2 12 420 15 25 1
Tract 3 30 15 625 15 3
Tract 4 20 10 15 412 1
Tract 5 15 25 12 10 5 3
Average Total Station Location
Response Time Tract 1 Tract 2 Tract 3 Tract 4 Tract 5
Tract 1 10 40 30 50 20
Tract 2 12 420 15 25
Tract 3 90 45 18 75 45
Tract 4 20 10 15 412
Tract 5 45 75 36 30 15
Tract Assigned to Station? Total Number of
Tract 1 Tract 2 Tract 3 Tract 4 Tract 5 Stations Assigned to Tract
Tract 1 0 0 0 0 1 1 = 1
Tract 2 0 0 1 0 0 1 = 1
Tract 3 0 0 1 0 0 1 = 1
Tract 4 0 0 0 0 1 1 = 1
Tract 5 0 0 0 0 1 1 = 1
all <= all <= all <= all <= all <= Total Stations
Station in Tract? 0 0 1 0 1 2 = 2
Average Response Time (minutes) = 8.5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A B C D E F G H I
Response Station Location
Time (min.) Tract 1 Tract 2 Tract 3 Tract 4 Tract 5
Tract 1 5 20 15 25 10
Tract 2 12 420 15 25
Tract 3 30 15 625 15
Tract 4 20 10 15 412
Tract 5 15 25 12 10 5
Station Cost ($thousand) 200 250 400 300 500
Station within 15 minutes?
Stations within
Tract 1 Tract 2 Tract 3 Tract 4 Tract 5 15 minutes
Tract 1 1 0 1 0 1 1 >= 1
Tract 2 1 1 0 1 0 2 >= 1
Tract 3 0 1 1 0 1 1 >= 1
Tract 4 0 1 1 1 1 1 >= 1
Tract 5 1 0 1 1 1 1 >= 1
Station? 1 1 0 0 0
Total Cost ($thousand) 450
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A B C D E F G H I J K L M N O P Q
Southwest Airways Crew Scheduling Problem
Flight Sequence
12345678910 11 12
Cost ($thousands) 2 3 4 6 7 5 7 8 9 9 8 9 At
Least
Includes Segment? Total One
SFO-LAX 1 0 0 1 0 0 1 0 0 1 0 0 1 >= 1
SFO-DEN 0 1 0 0 1 0 0 1 0 0 1 0 1 >= 1
SFO-SEA 0 0 1 0 0 1 0 0 1 0 0 1 1 >= 1
LAX-SFO 1 0 0 0 0 1 0 0 0 1 1 0 1 >= 1
DEN-SFO 0 1 0 1 1 0 0 0 1 0 0 0 1 >= 1
SEA-SFO 0 0 1 0 0 0 1 1 0 0 0 1 1 >= 1
SEA-LAX 0 0 0 0 0 1 0 0 1 1 1 1 1 >= 1
Total Number
12345678910 11 12 Sequences of Crews
Fly Sequence? 1 1 0 0 0 0 0 0 0 0 0 1 3 <= 3
Total Cost ($thousands) 14
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A B C D E F G H I J
Project 1 Project 2 Project 3 Project 4 Project 5
NPV ($million) 12 15 20 923
Cumulative Cumulative
Cumulative Cash Outflow Required ($million) Outflow Available
Year 1 8 10 12 414 36 <= 40
Year 2 14 18 18 720 59 <= 65
Year 3 17 25 24 925 76 <= 81
Year 4 0 30 30 032 62 <= 93
Total NPV
Project 1 Project 2 Project 3 Project 4 Project 5 ($million)
Undertake? 1 1 0 1 1 59
Project 1 1 <= 1 Project 2 (Project 1 only if Project 2)
Project 3&4 1 <= 1 (At most one of Project 3 & 4)
1
2
3
4
5
6
7
8
9
10
A B C D E F G H I
A B C D E Cost
Fixed Startup Cost $3,000 $2,000 $2,500 $1,500 $1,000 Startup $8,500
Cost per Megawatt-hour $5 $4 $6 $6 $7 Variable $33,400
Maximum Capacity (MW-hr)
2100 1800 2500 1500 3000 Total $41,900
Startup Generator? 1 1 1 0 1
Total Needed
MW-hr Generated 2100 1800 2500 0100 6500 >= 6500
<= <= <= <= <=
Capacity if Startup 2100 1800 2500 03000
7.16b&c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
A B C D E F G H
Bellevue School District Computer Purchase
Educomp Macwin McElectronics
Capacity 700 700 1000 Fixed Cost $85,000
Fixed Cost $45,000 $35,000 $50,000 Variable Cost $971,250
Variable Cost $750 $775 $700 Total Cost $1,056,250
Total Computers
Educomp Macwin McElectronics Purchased Needed
Number to Purchase 0 350 1000 1350 >= 1350
<= <= <=
Maximum 0 700 1000
Use Vendor? 0 1 1
Macwin
Variable Number to Purchase
Cost Educomp Macwin McElectronics Total Cost
0350 1000 $1,056,250
$680 0700 650 $1,016,000
$690 0700 650 $1,023,000
$700 0700 650 $1,030,000
$710 0350 1000 $1,033,500
$720 0350 1000 $1,037,000
$730 0350 1000 $1,040,500
$740 0350 1000 $1,044,000
$750 0350 1000 $1,047,500
$760 0350 1000 $1,051,000
$770 0350 1000 $1,054,500
$780 350 01000 $1,057,500
$790 350 01000 $1,057,500
$800 350 01000 $1,057,500
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
A B C D E F G H I J K
Warehouse Site Selection Problem
Weekly
Fixed Weekly
Shipping Cost Northwest Southwest Midwest Southeast Northeast Cost Capacity
Spokane $2.40 $3.50 $4.80 $6.80 $5.75 $40,000 20,000
Reno $3.25 $2.30 $3.40 $5.25 $6.00 $30,000 20,000
Omaha $4.05 $3.25 $2.85 $4.30 $4.75 $25,000 15,000
Harrisburg $5.25 $6.05 $4.30 $3.20 $2.75 $40,000 25,000
Jacksonville $6.95 $5.85 $4.80 $2.10 $3.50 $30,000 15,000
Total Operate
Shipments Northwest Southwest Midwest Southeast Northeast Shipped Capacity Warehouse?
Spokane 0 0 0 0 0 0 <= 0 0
Reno 8,000 12,000 0 0 0 20000 <= 20,000 1
Omaha 0 0 0 0 0 0 <= 0 0
Harrisburg 0 0 8,000 0 17,000 25000 <= 25,000 1
Jacksonville 0 0 1,000 14,000 0 15000 <= 15,000 1
Total Shipped 8000 12000 9000 14000 17000
>= >= >= >= >=
Weekly Demand 8,000 12,000 9,000 14,000 17,000
Shipping Cost $168,950
Fixed Cost $100,000
Total Cost $268,950
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
A B C D E F G H I J K L
Distribution Problem (part a)
Nashville San Jose Houston Production
Shipping Cost Warehouse Warehouse Warehouse Cost Capacity Costs
Atlanta Plant $30 $40 $50 $208 200 Shipping(P–>WH) $20,000
KC Plant $25 $45 $40 $214 300 Shipping(WH–>C) $12,875
Aberdeen Plant $45 $30 $55 $215 300 Production (P) $143,050
Austin Plant $30 $50 $30 $210 400 Variable (WH) $3,125
Total $179,050
Nashville San Jose Houston Total
Shipments Warehouse Warehouse Warehouse Produced Capacity
Atlanta Plant 200 0 0 200 <= 200
KC Plant 50 0 0 50 <= 300
Aberdeen Plant 0 300 0300 <= 300
Austin Plant 0 0 125 125 <= 400
Total 250 300 125
Shipped
Variable
Shipping Cost Sears Best Buy Fry‘s Comp USA Office Max Cost Capacity
Nashville WH $40 $45 $30 $25 $20 $4 300
San Jose WH $15 $50 $25 $15 $40 $5 500
Houston WH $50 $35 $15 $40 $50 $5 500
Total Total
Shipments Sears Best Buy Fry‘s Comp USA Office Max Shipped Out Shipped In Capacity
Nashville WH 0 0 0 100 150 250 <= 250 <= 300
San Jose WH 100 0 0 200 0300 <= 300 <= 500
Houston WH 0 50 75 0 0 125 <= 125 <= 500
Total 100 50 75 300 150
>= >= >= >= >=
Demand 100 50 75 300 150
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
A B C D E F G H I J K L M N
Distribution Problem (part b)
Nashville San Jose Houston Production Fixed Costs
Shipping Cost
Warehouse
Warehouse
Warehouse
Cost Capacity Cost Shipping(P–>WH) $21,750
Atlanta Plant $30 $40 $50 $208 200 $8,000 Shipping(WH–>C) $13,750
KC Plant $25 $45 $40 $214 300 $9,000 Production (P) $143,250
Aberdeen Plant $45 $30 $55 $215 300 $9,000 Variable (WH) $3,075
Austin Plant $30 $50 $30 $210 400 $10,000 Fixed (P) $19,000
Fixed (WH) $9,000
Nashville San Jose Houston Total Total $209,825
Shipments
Warehouse
Warehouse
Warehouse
Produced Capacity Open?
Atlanta Plant 0 0 0 0 <= 0 0
KC Plant 0 0 0 0 <= 0 0
Aberdeen Plant 0 300 0300 <= 300 1
Austin Plant 300 75 0375 <= 400 1
Total 300 375 0
Shipped
Variable Fixed
Shipping Cost Sears Best Buy Fry‘s
Comp USA
Office Max Cost Capacity Cost
Nashville WH $40 $45 $30 $25 $20 $4 300 $4,000
San Jose WH $15 $50 $25 $15 $40 $5 500 $5,000
Houston WH $50 $35 $15 $40 $50 $5 500 $5,000
Total Total
Shipments Sears Best Buy Fry’s
Comp USA
Office Max
Shipped Out Shipped In Capacity Open?
Nashville WH 0 50 75 25 150 300 <= 300 <= 300 1
San Jose WH 100 0 0 275 0375 <= 375 <= 500 1
Houston WH 0 0 0 0 0 0 <= 0<= 0 0
Total 100 50 75 300 150
>= >= >= >= >=
Demand 100 50 75 300 150