3-2
3.3-5 The activities for the two examples are choosing the mix of advertising media and
personnel scheduling.
3.4-1 Mixed problems may contain all three types of functional constraints: resource constraints,
benefit constraints, and fixed-requirement constraints.
3.4-3 Two benefit constraints and a fixed-requirement constraint are included in the new linear
programming model.
3.5-1 Transportation problems deal with transporting goods through a distribution network at
minimum cost.
3.5-3 In contrast to the ≤ form for resource constraints and the ≥ form for benefit constraints,
fixed-requirement constraints have an = form.
3.6-1 Assignment problems involve making assignments.
3.6-2 Pure assignment problems have all fixed-requirement constraints.
3.7-1 A linear programming model must accurately reflect the managerial view of the problem.
3.7-2 Model validation is a testing process used on an initial version of a model to identify the
errors and omissions that inevitably occur when constructing large models.
3.7-4 What-if analysis is an important part of a linear programming study because an optimal
solution can only be solved for with respect to one specific version of the model at a time.
3-3
Problems
3.1 a)
1
2
3
4
5
6
7
8
9
10
11
12
13
A B C D E F G H
TV Spots Magazine Ads Radio Ads SS Ads
Exposures per Ad 1300 600 900 500
(thousands)
Budget Budget
Cost per Ad ($thousands) Spent Available
Ad Budget 300 150 200 100 4000 <= 4000
Planning Budget 90 30 50 40 1000 <= 1000
Total Exposures
TV Spots Magazine Ads Radio Ads SS Ads (thousands)
Number of Ads 0 10 10 5 17,500
<= <=
Max TV Spots 5 10 Max Radio Spots
Data cells: B2:E2, B6:E7, H6:H7, B13, and D13
Changing cells: B11:E11
Target cell: H11
4
5
6
7
F
9
10
11
H
Total Exposures
(thousands)
=SUMPRODUCT(B2:E2,B11:E11)
b) This is a linear programming model because the decisions are represented by changing
cells that can have any value that satisfy the constraints. Each constraint has an output
c) Let T = number of commercials on TV
M = number of advertisements in magazines
Maximize Exposures (thousands) = 140T + 60M + 90R + 50S
3-5
3.3 a)
1
2
3
4
5
6
7
8
9
10
11
A B C D E F G
Activity 1 Activity 2 Activity 3
Contribution per unit $50 $40 $70
Resource Usage Resource Resource
per Unit of Activity Used Available
Resource A 30 20 0 500 <= 500
Resource B 0 10 40 600 <= 600
Resource C 20 20 30 783.333 <= 1,000
Activity 1 Activity 2 Activity 3 Total Contribution
Level of Activity 16.667 0 15 $1,883.33
b) Let x1 = level of activity 1
x2 = level of activity 2
3.4 a & c)
1
2
3
4
5
6
7
8
9
10
11
12
A B C D E F G H
Activity 1 Activity 2 Activity 3 Activity 4
Contribution per unit $11 $9 $8 $9
Resource Resource
Used Available
Resource P 3 5 -2 4 400 <= 400
Resource Q 4 -1 3 2 300 <= 300
Resource R 6 3 2 -1 400 <= 400
Resource S -2 2 5 3 300 <= 300
Activity 1 Activity 2 Activity 3 Activity 4 Total Contribution
Level of Activity 39.421 41.953 37.071 36.528 $1,436.53
Resource Usage
per Unit of Activity
b) Below are five possible guesses (many answers are possible).
(x1, x2, x3, x4)
Feasible?
P
(30,30,30,30)
Yes
$1110
(40,40,40,40)
No
(35,39,30,40)
Yes
$1336
(35,39,34,40)
Yes
$1368
(37,39,35,40)
Yes
$1398
Best
3.5 a) The activities are the production rates of products 1, 2, and 3. The limited resources are
hours available per week on the milling machine, lathe, and grinder.
3-6
c) milling machine: 9(# units of 1) + 3(# units of 2) + 5(# units of 3) ≤ 500
lathe: 5(# units of 1) + 4(# units of 2) ≤ 350
d)
1
2
3
4
5
6
7
8
9
10
11
12
A B C D E F G
Product 1 Product 2 Product 3
Unit Profit $50 $20 $25
Hours Hours
Machine Hours Used per Unit of Product Used Available
Milling machine 9 3 5 500 <= 500
Lathe 5 4 0 350 <= 350
Grinder 3 0 2 118.571429 <= 150
Product 1 Product 2 Product 3 Total Profit
Production Rate 26.190 54.762 20 $2,904.76
(per week) <=
Sales Potential 20
Data cells: B2:D2, B5:D7, G5:G7, and D12
Changing cells: B10:D10
3
4
5
6
7
E
Hours
Used
=SUMP RODUCT(B5: D5,$B$10:$D$10)
=SUMP RODUCT(B6: D6,$B$10:$D$10)
=SUMP RODUCT(B7: D7,$B$10:$D$10)
9
10
G
Total Profit
= SUMPRO DUCT(B2:D2,B10:D10)
e) Let x1 = units of product 1 produced per week
x2 = units of product 2 produced per week
x3 = units of product 3 produced per week
3.6 a) The activities are the production quantities of parts A, B, and C. The limited resources
are the hours available on machine 1 and machine 2.
3.8 United Airlines used linear programming approach for scheduling. The purpose of this
study was “to determine the needs for increased manpower, to identify excess manpower
for reallocation, to reduce the time required for preparing schedules, to make manpower
allocation more day- and time-sensitive, and to quantify the costs associated with
3.9 a & c)
1
2
3
4
5
6
7
8
9
10
11
A B C D E F
Activity 1 Activity 2
Unit Cost $60 $50
Minimum
Level Acceptable
Achieved Level
Benefit 1 5 3 60 >= 60
Benefit 2 2 2 31 >= 30
Benefit 3 7 9 126 >= 126
Activity 1 Activity 2 Total Cost
Level of Activity 6.75 8.75 $842.50
Benefit Contribution per
Unit of Each Activity
3-9
b)
(x1, x2)
Feasible?
C
(7,7)
No
(7,8)
No
(8,7)
No
(8,8)
Yes
$880
Best
(8,9)
Yes
$930
(9,8)
Yes
$940
d) Let x1 = level of activity 1
x2 = level of activity 2
Minimize Cost = $60x1 + $50x2
e) Optimal Solution: (x1, x2) = (6.75, 8.75) and Total Cost = $842.50.
3.10 a & c)
1
2
3
4
5
6
7
8
9
10
11
A B C D E F G H
Activity 1 Activity 2 Activity 3 Activity 4
Unit Cost $400 $600 $500 $300
Minimum
Level Acceptable
Achieved Level
Benefit P 2 -1 4 3 80 >= 80
Benefit Q 1 4 -1 260 >= 60
Benefit R 3 5 4 -1 110 >= 110
Activity 1 Activity 2 Activity 3 Activity 4 Total Cost
Level of Activity 32.5 3.75 0 6.25 $17,125
Benefit Contribution per
Unit of Each Activity
3-10
b) Below are five possible guesses (many answers are possible).
(x1, x2, x3, x4)
Feasible?
C
(32,4,0,6)
No
(33,4,0,6)
Yes
$17,400
Best
(33,5,0,6)
No
(33,4,1,6)
Yes
$17,900
(33,4,1,7)
Yes
$18,200
3.11 a & d)
1
2
3
4
5
6
7
8
9
10
11
A B C D E F G
Corn Tankage Alfalfa
Unit Cost $0.84 $0.72 $0.60
(per kg) Minimum
Level Daily
Nutritional Contents (per kg) Achieved Requirement
Carbohydrates 90 20 40 200 >= 200
Protein 30 80 60 180 >= 180
Vitamins 10 20 60 157.142857 >= 150
Corn Tankage Alfalfa Total Cost
Diet (kg) 1.143 0 2.429 $2.42
b) (x1, x2, x3) = (1,2,2) is a feasible solution with a daily cost of $3.48. This diet will
provide 210 kg of carbohydrates, 310 kg of protein, and 170 kg of vitamins daily.
c) Answers will vary.
e) Let C = kg of corn to feed each pig
T = kg of tankage to feed each pig
3.12 a & d)
1
2
3
4
5
6
7
8
9
A B C D E F G
Income per Unit of Asset ($million) Cash Flow Minimum
Asset 1 Asset 2 Asset 3 Achieved Required
Year 5 2 1 0.5 400 >= 400
Year 10 0.5 0.5 1 150 >= 100
Year 20 0 1.5 2 300 >= 300
Total Cost
Asset 1 Asset 2 Asset 3 ($million)
Units Purchased 100 200 0 300
c) (x1, x2, x3) = (100,100,200) is a feasible solution. This would generate $400 million in
5 years, $300 million in 10 years, and $550 million in 20 years. The total invested will
be $400 million.
3-11
d) Answers will vary.
f) Let x1 = units of Asset 1 purchased
x2 = units of Asset 2 purchased
3.13 a) The activities are leasing space in each month for a number of months. The benefit is
meeting the space requirements for each month.
b) The decisions to be made are how much space to lease and for how many months. The
c) Month 1: (M1 1mo lease) + (M1 2mo lease) + (M1 3mo lease) + (M1 4mo lease) +
(M1 5 mo lease) ≥ 30,000 square feet.
Month 4: (M1 4mo lease) + (M1 5mo lease) + (M2 3mo lease) + (M2 4mo lease) +
Nonnegativity: (M1 1mo lease) ≥ 0, (M1 2mo lease) ≥ 0, (M1 3 mo lease) ≥ 0, (M1 4
Cost = ($650)[(M1 1mo lease) + (M2 1mo lease) + (M3 1mo lease) + (M4 1mo lease)
+ (M5 1mo lease)] + ($1,000)[(M1 2mo lease) + (M2 2mo lease) + (M3 2mo lease) +
3-12
d)
1
2
3
4
5
6
7
8
9
10
11
12
13
A B C D E F G H I J K L M N O P Q R S
Month Covered by Lease? Total Space
Month of Lease: 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5 Leased Required
Length of Lease: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1 (sq. ft.) (sq. ft.)
Month 1 1 1 1 1 1 30,000 >= 30,000
Month 2 1 1 1 1 1 1 1 1 30,000 >= 20,000
Month 3 1 1 1 1 1 1 1 1 1 40,000 >= 40,000
Month 4 1 1 1 1 1 1 1 1 30,000 >= 10,000
Month 5 1 1 1 1 1 50,000 >= 50,000
Cost of Lease $65 $100 $135 $160 $190 $65 $100 $135 $160 $65 $100 $135 $65 $100 $65
(per sq. ft.)
Total Cost
Lease (sq. ft.) 0 0 0 0 30,000 0 0 0 0 10,000 0 0 0 0 20,000 $7,650,000
Data cells: B4:P8, B10:P10, and S4:S8
1
2
3
4
5
6
7
8
Q
To tal
Leased
(sq. ft.)
=SUMPROD UCT(B4:P4,$B$ 13:$P$13)
=SUMPROD UCT(B5:P5,$B$ 13:$P$13)
=SUMPROD UCT(B6:P6,$B$ 13:$P$13)
=SUMPROD UCT(B7:P7,$B$ 13:$P$13)
=SUMPROD UCT(B8:P8,$B$ 13:$P$13)
12
13
S
Total Cost
= SUMPRO DUCT(B10:P10,B13:P13)
e) Let xij = square feet of space leased in month i for a period of j months.
for i = 1, … , 5 and j = 1, … , 6-i.
Minimize C = $650(x11 + x21 + x31 + x41 + x51) + $1,000(x12 + x22 + x32 + x42)
x14 + x15 + x23 + x24 + x32 + x33 + x41 + x42 ≥ 10,000 square feet
x15 + x24 + x33 + x42 + x51 ≥ 50,000 square feet
and xij ≥ 0, for i = 1, … , 5 and j = 1 , … , 6-i.
3.14
1
2
3
4
5
6
7
8
9
10
11
A B C D E F G H
Activity 1 Activity 2 Activity 3 Activity 4
Unit Cost 2 1 -1 3
Minimum
Level Acceptable
Achieved Level
Benefit 1 3 2 -2 580 >= 80
Benefit 2 1 -1 0 1 10 >= 10
Benefit 3 1 1 -1 2 32.857 >= 30
Activity 1 Activity 2 Activity 3 Activity 4 Total Cost
Level of Activity 0 4.286 0 14.286 47.14
Benefit Contribution per
Unit of Each Activity
3.15 a) This is a cost-benefit-tradeoff problem because it asks you to meet minimum required
benefit levels (number of consultants working each time period) at minimum cost.
3-13
b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A B C D E F G H I J K
Full Time Full Time Full Time Part Time Part Time Part Time Part Time
8am-4pm noon–8pm 4pm-midnight 8am-noon noon–4pm 4pm-8pm 8pm-midnight
Cost per Shift $112 $112 $112 $48 $48 $48 $48
Total Total
Shift Covers Time of Day? (1=yes, 0= no) Working Needed
8am-noon 1 1 6 >= 6
noon-4pm 1 1 1 8 >= 8
4pm-8pm 1 1 1 12 >= 12
8pm-midnight 1 1 6 >= 6
Workers per Shift 4 2 6 2 2 4 0
2
Total Times Total Total
Time of Day F ull Time Part Time Cost
8am-noon 4 >= 4 $1,728
noon-4pm 6 >= 4
4pm-8pm 8 >= 8
8pm-midnight 6 >= 0
c) Let f1 = number of full-time consultants working the morning shift (8 a.m.-4 p.m.),
f2 = number of full-time consultants working the afternoon shift (12 p.m.-8 p.m.),
3.16 a) This is a distribution-network problem because it deals with the distribution of goods
through a distribution network at minimum cost.
b)
1
2
3
4
5
6
7
8
9
10
11
12
A B C D E F G
Ship ping CostCustomer 1 Customer 2 Customer 3
Factory 1 $600 $800 $700
Factory 2 $400 $900 $600
Total
Shipped
Units Sh ippedCustomer 1 Customer 2 Customer 3 Out Output
Factory 1 0 200 200 400 = 400
Factory 2 300 0 200 500 = 500
Total To Customer 300 200 400
= = = Total Cost
Order Size 300 200 400 $540,000
3-14
c) Let xij = number of units to ship from Factory i to Customer j (i = 1,2; j = 1, 2, 3)
Minimize Cost = $600x11 + $800x12 + $700x13 + $400x21 + $900x22 + $600x23
subject to x11 + x12 + x13 = 400
x21 + x22 + x23 = 500
3.17 a) Requirement 1: The total amount shipped from Mine 1 must be 40 tons.
Requirement 2: The total amount shipped from Mine 2 must be 60 tons.
b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
A B C D E F
Shipping
Cost S1 S2
M1 $2,000 $1,700
M2 $1,600 $1,100
P $400 $800
Capacity S1 S2
M1 30 30
M2 50 50
P70 70
Units Total Shipped
Shipped S1 S2 Out of M1,M2 Output
M1 30 10 40 =40
M2 10 50 60 =60
Total Into S1,S2 40 60
= = Total Shipped
Total Out of S1,S2 40 60 Into P Needed
P40 60 100 = 100
Total Cost
3-16
3.19 a) Let xi = percentage of alloy i in the new alloy (i = 1, 2, 3, 4, 5).
(60%)x1 + (25%)x2 + (45%)x3 + (20%)x4 + (50%)x5 = 40%
b)
1
2
3
4
5
6
7
8
9
10
11
12
13
A B C D E F G H I
Alloy 1 Alloy 2 Alloy 3 Alloy 4 Alloy 5
Cost ($/lb.) $22 $20 $25 $24 $27
New Alloy Desired
Alloy Composition Composition Composition
Tin 60% 25% 45% 20% 50% 40% = 40%
Zinc 10% 15% 45% 50% 40% 35% = 35%
Lead 30% 60% 10% 30% 10% 25% = 25%
Alloy 1 Alloy 2 Alloy 3 Alloy 4 Alloy 5 Total Blend
New Alloy Blend 4.3% 28.3% 67.4% 0.0% 0.0% 100% = 100%
Total Cost
$23.46
c) Let xi = percentage of alloy i in the new alloy (i = 1, 2, 3, 4, 5).
Minimize Cost = $22x1 + $20x2 + $25x3 + $24x4 + $27x5
3.20 a)
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
Large Medium Small
Unit Profit $420 $360 $300
Space Required 20 15 12
(sq.ft. per unit)
Total Space Space
Prod uction Large Medium Small Produced Capacity Required Available
Plant 1 516.67 177.78 0 694.4 <= 750 13,000 <= 13,000
Plant 2 0 666.67 166.67 833.3 <= 900 12,000 <= 12,000
Plant 3 0 0 416.67 416.7 <= 450 5,000 <= 5,000
Total Produced 516.67 844.44 583.33
<= <= <= Total Profit
Sales F orecast 900 1200 750 $696,000
Percentage of Plant 1 Capacity 93% = 93% Percentage of Plant 2 Capacity
Percentage of Plant 1 Capacity 93% = 93% Percentage of Plant 3 Capacity
3-17
b) Let xij = number of units produced at plant i of product j (i = 1, 2, 3; j = L, M, S).
Maximize Profit = $420(x1L + x2L + x3L) + $360(x1M + x2M + x3M) + $300(x1S + x2S +
x3S)
subject to x1L + x1M + x1S ≤ 750
x2L + x2M + x2S ≤ 900
x3L + x3M + x3S ≤ 450
3.21 a)
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 K L
Cargo 1 Cargo 2 Cargo 3 Cargo 4
Volume (cf/ton) 500 700 600 400
Profit (per ton) $320 $400 $360 $290
Cargo Total Weight T otal Volume
Placement (ton s) Cargo 1 Cargo 2 Cargo 3 Cargo 4 Weight Capacity Volume Capacity
Front 0 7.333 0 4.667 12 <= 12 7,000 <= 7,000
Center 13 1.667 0 3.333 18 <= 18 9,000 <= 9,000
Back 0 0 5 5 10 <= 10 5,000 <= 5,000
Total 13 9 5 13
<= <= <= <= Total Profit
Available (tons) 20 16 25 13 $13,330
Percentage of Front Capacity 100% = 100% Percentage of Middle Capacity
Percentage of Front Capacity 100% = 100% Percentage of Back Capacity
b) Let xij = tons of cargo i stowed in compartment j (i = 1,2,3,4; j = F, C, B)
x3F + x3C + x3B ≤ 25 tons
x4F + x4C + x4B ≤ 13 tons
500x1F + 700x2F + 600x3F + 400x4F ≤ 7,000 cubic feet
500x1C + 700x2C + 600x3C + 400x4C ≤ 9,000 cubic feet
3-19
3.24 a) Resource Constraints:
Calories must be no more than 420.
No more than 20% of total calories from fat.
Fixed-Requirement Constraints:
There must be 15 mg of thickeners.
b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
A B C D E F G H I J K
St rawberry Cream Vitamin Sweetener T hickener
Unit Cost $0.10 $0.08 $0.25 $0.15 $0.06
(per tbsp)
Level
Nutritional Cont ents (per tbsp) Achieved Minimum Maximum
Total Calories 50 100 0 120 80 380 >= 380 <= 420
Vitamin Content (mg) 20 050 0 2 64.167 >= 50
Thickeners (mg) 3 8 1 2 25 15 =15
Calories from Fat 1 75 0 0 30 23.521 <= 76
20%
St rawberry Cream Vitamin Sweetener Thickener Total Cost of Total Calories
Cont ents (tbsp) 3.208 0.271 0 1.604 0 $0.58
>=
3.208 2 times Sweetener
c) Let S = Tablespoons of strawberry flavoring,
CR = Tablespoons of cream,
Minimize C = $0.10S + $0.08CR + $0.25V + $0.15A + $0.06T
subject to 50S + 100CR + 120A + 80T ≥ 380 calories