Part 1: Solutions Manual Contents
Chapter 1.
Introduction
2.
An Introduction to Linear Programming
3.
Linear Programming: Sensitivity Analysis and Interpretation of Solution
4.
Linear Programming Applications in Marketing, Finance and Operations Management
5.
Advanced Linear Programming Applications
6.
Distribution and Network Models
7.
Integer Linear Programming
8.
Nonlinear Optimization Models
9.
Project Scheduling: PERT/CPM
10. Inventory Models 11. Waiting Line Models 12. Simulation 13. Decision Analysis 14. Multicriteria Decision Problems 15. Forecasting 16. Markov Processes 17. Linear Programming: The Simplex Method 18. Simplex-Based Sensitivity Analysis and Duality 19. Solution Procedures for Transportation and Assignment Problems 20. Minimal Spanning Tree 21. Dynamic Programming Appendix A: Building Spreadsheet Models
Chapter 1 Introduction Learning Objectives 1.
Develop a general understanding of the management science/operations research approach to decision making.
2.
Realize that quantitative applications begin with a problem situation.
3.
Obtain a brief introduction to quantitative techniques and their frequency of use in practice.
4.
Understand that managerial problem situations have both quantitative and qualitative considerations that are important in the decision making process.
5.
Learn about models in terms of what they are and why they are useful (the emphasis is on mathematical models).
6.
Identify the step-by-step procedure that is used in most quantitative approaches to decision making.
7.
Learn about basic models of cost, revenue, and profit and be able to compute the breakeven point.
8.
Obtain an introduction to the use of computer software packages such as Microsoft Excel in applying quantitative methods to decision making.
9.
Understand the following terms: model objective function constraint deterministic model stochastic model feasible solution
infeasible solution management science operations research fixed cost variable cost breakeven point
Solutions: 1-1 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 1
1.
Management science and operations research, terms used almost interchangeably, are broad disciplines that employ scientific methodology in managerial decision making or problem solving. Drawing upon a variety of disciplines (behavioral, mathematical, etc.), management science and operations research combine quantitative and qualitative considerations in order to establish policies and decisions that are in the best interest of the organization.
2.
Define the problem Identify the alternatives Determine the criteria Evaluate the alternatives Choose an alternative For further discussion see section 1.3
3.
See section 1.2.
4.
A quantitative approach should be considered because the problem is large, complex, important, new and repetitive.
5.
Models usually have time, cost, and risk advantages over experimenting with actual situations.
6.
Model (a) may be quicker to formulate, easier to solve, and/or more easily understood.
7.
Let
d = distance m = miles per gallon c = cost per gallon,
2d Total Cost = c m We must be willing to treat m and c as known and not subject to variation. 8.
a. Maximize 10x + 5y s.t. 5x + 2y 40 x 0, y 0 b.
Controllable inputs: x and y Uncontrollable inputs: profit (10,5), labor hours (5,2) and labor-hour availability (40)
c. 1-2 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Introduction
Profit:
$10/unit for x $ 5/ unit for y
Labor Hours:
5/unit for x 2/ unit for y 40 labor-hour capacity
Uncontrollable Inputs
Max 10 x + 5 y s.t. 10 x + 5 y 40 x 0 y 0
Production Quantities x and y Controllable Input
Projected Profit and check on production time constraint Output
Mathematical Model d.
x = 0, y = 20 Profit = $100 (Solution by trial-and-error)
e.
Deterministic - all uncontrollable inputs are fixed and known.
9.
If a = 3, x = 13 1/3 and profit = 133 If a = 4, x = 10 and profit = 100 If a = 5, x = 8 and profit = 80 If a = 6, x = 6 2/3 and profit = 67 Since a is unknown, the actual values of x and profit are not known with certainty.
10. a.
Total Units Received = x + y
b.
Total Cost = 0.20x +0.25y
c.
x + y = 5000
d. x 4000 Kansas City Constraint y 3000 Minneapolis Constraint e. Min s.t.
0.20x + 0.25y x+ x
y y
=
5000 4000 3000
x, y 0 11. a. at $20 d = 800 - 10(20) = 600 1-3 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 1
at $70 d = 800 - 10(70) = 100 b.
TR = dp = (800 - 10p)p = 800p - 10p2
c.
at $30 TR = 800(30) - 10(30)2 = 15,000 at $40 TR = 800(40) - 10(40)2 = 16,000 at $50 TR = 800(50) - 10(50)2 = 15,000 Total Revenue is maximized at the $40 price.
d.
d = 800 - 10(40) = 400 units TR = $16,000
12. a.
TC = 1000 + 30x
b.
P = 40x - (1000 + 30x) = 10x - 1000
c.
Breakeven point is the value of x when P = 0 Thus 10x - 1000 = 0 10x = 1000 x = 100
13. a.
Total cost = 4800 + 60x
b.
Total profit = total revenue - total cost = 300x - (4800 + 60x) = 240x - 4800
c.
Total profit = 240(30) - 4800 = 2400
d.
240x - 4800 = 0 x = 4800/240 = 20 The breakeven point is 20 students.
14. a.
Profit = Revenue - Cost = 20x - (80,000 + 3x) = 17x - 80,000 17x - 80,000 = 0 17x = 80,000 x = 4706 Breakeven point = 4706
b.
Profit = 17(4000) - 80,000 = -12,000 Thus, a loss of $12,000 is anticipated.
c.
Profit = px - (80,000 + 3x) = 4000p - (80,000 + 3(4000)) = 0 4000p = 92,000 p = 23
d.
Profit = $25.95 (4000) - (80,000 + 3 (4000)) = $11,800 1-4 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Introduction
Probably go ahead with the project although the $11,800 is only a 12.8% return on the total cost of $92,000. 15. a. b.
Profit
= 100,000x - (1,500,000 + 50,000x) = 0 50,000x = 1,500,000 x = 30 Build the luxury boxes. Profit = 100,000 (50) - (1,500,000 + 50,000 (50)) = $1,000,000
16. a.
Max
50x + 30y 80,000 50x 50,000 30y 45,000 x, y 0
b.
17. a.
6x + 4y
sj = sj - 1 + xj - dj or sj - sj-1 - xj + dj = 0
b.
xj cj
c. sj Ij
1-5 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2 An Introduction to Linear Programming Learning Objectives 1.
Obtain an overview of the kinds of problems linear programming has been used to solve.
2.
Learn how to develop linear programming models for simple problems.
3.
Be able to identify the special features of a model that make it a linear programming model.
4.
Learn how to solve two variable linear programming models by the graphical solution procedure.
5.
Understand the importance of extreme points in obtaining the optimal solution.
6.
Know the use and interpretation of slack and surplus variables.
7.
Be able to interpret the computer solution of a linear programming problem.
8.
Understand how alternative optimal solutions, infeasibility and unboundedness can occur in linear programming problems.
9.
Understand the following terms: problem formulation constraint function objective function solution optimal solution nonnegativity constraints mathematical model linear program linear functions feasible solution
feasible region slack variable standard form redundant constraint extreme point surplus variable alternative optimal solutions infeasibility unbounded
2-1 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
Solutions: 1.
a, b, and e, are acceptable linear programming relationships. c is not acceptable because of −2B 2 d is not acceptable because of 3 A f is not acceptable because of 1AB c, d, and f could not be found in a linear programming model because they have the above nonlinear terms.
2.
a. B 8
4
0
4
8
4
8
A
b.
B 8
4
0
A
c.
B Points on line are only feasible points
8 4
0
4
8
A
2-2 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
3.
a. B (0,9)
A
0
(6,0)
b. B (0,60)
A
0
(40,0)
c. B Points on line are only feasible solutions (0,20) A (40,0)
0
4.
a. B
(20,0)
A
(0,-15)
2-3 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
b. B
(0,12) (-10,0)
A
c. B
(10,25)
Note: Point shown was used to locate position of the constraint line A
0
5. B
a
300
c 200
100 b A 0
100
200
300
2-4 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
6.
7A + 10B = 420 is labeled (a) 6A + 4B = 420 is labeled (b) -4A + 7B = 420 is labeled (c)
B 100 80 60 (b)
(c)
40 20
(a) A
-100
-80
-60
-40
-20
0
20
40
60
80
100
7. B 100
50
A
0 50
100
150
200
2-5 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
250
Chapter 2
8. B 200
133 1/3
(100,200)
A -200
0
-100
100
200
9.
B (150,225) 200
100
0
(150,100)
100
200
300
A
-100
-200
2-6 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
10.
B 5
4
Optimal Solution A = 12/7, B = 15/7
3 Value of Objective Function = 2(12/7) + 3(15/7) = 69/7 2
1
A
0 1
2
(1) × 5 (2) - (3)
4
5
2B 3B 10B 7B B
= 6 = 15 = 30 = -15 = 15/7
3
A 5A 5A
+ + + -
6
(1) (2) (3)
From (1), A = 6 - 2(15/7) = 6 - 30/7 = 12/7
2-7 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
11.
B A = 100
Optimal Solution A = 100, B = 50 Value of Objective Function = 750
100 B = 80
A
0 100
200
12. a.
B 6
5
4
Optimal Solution A = 3, B = 1.5 Value of Objective Function = 13.5
3
(3,1.5)
2
1
A
(0,0) 1
2
3
4 (4,0)
5
6
2-8 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
b.
B 3
Optimal Solution A = 0, B = 3 Value of Objective Function = 18
2
1
A
(0,0) 1 c.
2
3
4
5
6
7
8
9
There are four extreme points: (0,0), (4,0), (3,1,5), and (0,3).
13. a.
B 8
6 Feasible Region consists of this line segment only
4
2
0
A 2
b.
4
6
8
The extreme points are (5, 1) and (2, 4).
2-9 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
10
Chapter 2
c.
B 8
6
Optimal Solution A = 2, B = 4
4
2
0
A 2
14. a.
4
6
8
Let F = number of tons of fuel additive S = number of tons of solvent base Max s.t.
40F
+
30S
2/5F
+
1/ S 200 Material 1 2 1/ S 5 Material 2 5
3/ F 5 F, S 0
+
3/ S 10
21
Material 3
2 - 10 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
b. S
F
c.
Material 2: 4 tons are used, 1 ton is unused.
d.
No redundant constraints.
15. a.
2 - 11 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
b.
Similar to part (a): the same feasible region with a different objective function. The optimal solution occurs at (708, 0) with a profit of z = 20(708) + 9(0) = 14,160.
c.
The sewing constraint is redundant. Such a change would not change the optimal solution to the original problem.
16. a.
b.
A variety of objective functions with a slope greater than -4/10 (slope of I & P line) will make extreme point (0, 540) the optimal solution. For example, one possibility is 3S + 9D. Optimal Solution is S = 0 and D = 540.
c. Department Cutting and Dyeing Sewing Finishing Inspection and Packaging
Hours Used 1(540) = 540 5 /6(540) = 450 2 /3(540) = 360 1 /4(540) = 135
Max. Available 630 600 708 135
Slack 90 150 348 0
17. Max s.t.
5A
+ 2B
+
0S1
1A 2A 6A
- 2B + 3B - 1B
+
1S1
+ 0S2 +
0S3
+ 1S2
= 420 = 610 1S3 = 125
+ A, B, S1, S2, S3 0
18. a. Max s.t.
4A + 1B
+ 0S1
10A + 2B 3A + 2B 2A + 2B
+ 1S1
+ 0S2
+ 0S3
+ 1S2 + 1S3 A, B, S1, S2, S3 0
= 30 = 12 = 10
2 - 12 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
b.
B 14
12
10
8
6 Optimal Solution A = 18/7, B = 15/7, Value = 87/7 4
2
0 c.
A 2
4
6
8
3A +
4B
+ 0S1
+ 0S2
+ 0S3
-1A + 1A + 2A +
2B 2B 1B
+ 1S1
10
S1 = 0, S2 = 0, S3 = 4/7
19. a. Max s.t.
+ 1S2 + 1S3 A, B, S1, S2, S3 0
= 8 = 12 = 16
(1) (2) (3)
2 - 13 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
b.
B 14 (3) 12
10
(1)
8
6 Optimal Solution A = 20/3, B = 8/3 Value = 30 2/3
4
2 (2) 0
A 2
c.
4
6
8
10
12
S1 = 8 + A – 2B = 8 + 20/3 - 16/3 = 28/3 S2 = 12 - A – 2B = 12 - 20/3 - 16/3 = 0 S3 = 16 – 2A - B = 16 - 40/3 - 8/3 = 0
20. a. Max s.t.
3A
+ 2B
A 3A A A
+ B + 4B
- S1 + S2 - S3
-
- S4
B
= = = =
4 24 2 0
A, B, S1, S2, S3, S4 0
2 - 14 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
b.
c.
S1 = (3.43 + 3.43) - 4 = 2.86 S2 = 24 - [3(3.43) + 4(3.43)] = 0 S3 = 3.43 - 2 = 1.43 S4 = 0 - (3.43 - 3.43) = 0
2 - 15 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
21. a. and b. B
90
80
70 Constraint 2
60
50
40
Optimal Solution
Constraint 1
Constraint 3
30
Feasible Region
20
10
2A + 3B = 60
A
0 10 c.
20
30
40
50
60
70
80
90
100
Optimal solution occurs at the intersection of constraints 1 and 2. For constraint 2, B = 10 + A Substituting for B in constraint 1 we obtain 5A + 5(10 + A) 5A + 50 + 5A 10A A
= 400 = 400 = 350 = 35
B = 10 + A = 10 + 35 = 45 Optimal solution is A = 35, B = 45 d.
Because the optimal solution occurs at the intersection of constraints 1 and 2, these are binding constraints.
2 - 16 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
e.
Constraint 3 is the nonbinding constraint. At the optimal solution 1A + 3B = 1(35) + 3(45) = 170. Because 170 exceeds the right-hand side value of 90 by 80 units, there is a surplus of 80 associated with this constraint.
22. a.
C 3500
3000
2500
Inspection and Packaging
2000
Cutting and Dyeing
5 1500
Feasible Region
4 1000
Sewing 3 5A + 4C = 4000
500
0
2 1
500
1000 1500 2000 2500 Number of All-Pro Footballs
A 3000
b. Extreme Point 1 2 3 4 5
Coordinates (0, 0) (1700, 0) (1400, 600) (800, 1200) (0, 1680)
Profit 5(0) + 4(0) = 0 5(1700) + 4(0) = 8500 5(1400) + 4(600) = 9400 5(800) + 4(1200) = 8800 5(0) + 4(1680) = 6720
Extreme point 3 generates the highest profit. c.
Optimal solution is A = 1400, C = 600
d.
The optimal solution occurs at the intersection of the cutting and dyeing constraint and the inspection and packaging constraint. Therefore these two constraints are the binding constraints.
e.
New optimal solution is A = 800, C = 1200 Profit = 4(800) + 5(1200) = 9200
2 - 17 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
23. a.
Let E = number of units of the EZ-Rider produced L = number of units of the Lady-Sport produced Max s.t.
2400E
+
6E
+
2E
+
1800L 3L 2100 L 280 2.5L 1000 E, L 0
Engine time Lady-Sport maximum Assembly and testing
b. L 700
Number of EZ-Rider Produced
600
Engine Manufacturing Time
500
400
Frames for Lady-Sport
300
Optimal Solution E = 250, L = 200 Profit = $960,000
200
100 Assembly and Testing 0
E 100
300
200
400
500
Number of Lady-Sport Produced
c. 24. a.
The binding constraints are the manufacturing time and the assembly and testing time. Let R = number of units of regular model. C = number of units of catcher’s model. Max s.t.
5R
+
8C
1R
+
1/ R 2 1/ R 8
+
3/ C 2 1/ C 3 1/ C 4
+
900
Cutting and sewing
300
Finishing
100
Packing and Shipping
R, C 0
2 - 18 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
.
An Introduction to Linear Programming
b.
C 1000
F
Catcher's Model
800 600
C&
400
S
P&
Optimal Solution (500,150) S
200 R 0
200
400
600
800
1000
Regular Model c.
5(500) + 8(150) = $3,700
d.
C&S
1(500) + 3/2(150) = 725
F
1/ (500) + 1/ (150) = 300 2 3
P&S
1/ (500) + 1/ (150) = 100 8 4
e. Department C&S F P&S 25. a.
Usage 725 300 100
Slack 175 hours 0 hours 0 hours
Let B = percentage of funds invested in the bond fund S = percentage of funds invested in the stock fund Max s.t.
b.
Capacity 900 300 100
0.06 B
+
0.10 S
B 0.06 B B
+ +
0.10 S S
=
0.3 0.075 1
Bond fund minimum Minimum return Percentage requirement
Optimal solution: B = 0.3, S = 0.7 Value of optimal solution is 0.088 or 8.8%
2 - 19 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
26. a.
a.
Let N = amount spent on newspaper advertising R = amount spent on radio advertising Max s.t.
50N
+ 80R
N N
+
N
R = 1000 Budget 250 Newspaper min. R 250 Radio min. -2R 0 News 2 Radio
N, R 0 b. R
1000
Radio Min
Optimal Solution N = 666.67, R = 333.33 Value = 60,000
Budget
N = 2R
500
Newspaper Min Feasible region is this line segment N 0
27.
5 00
1000
Let I = Internet fund investment in thousands B = Blue Chip fund investment in thousands Max s.t.
0.12I
+
0.09B
1I 1I 6I
+
1B
+ 4B I, B 0
50 35 240
Available investment funds Maximum investment in the internet fund Maximum risk for a moderate investor
2 - 20 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
B
Blue Chip Fund (000s)
60
Risk Constraint Optimal Solution I = 20, B = 30 $5,100
50
40
Maximum Internet Funds
30
20
10
Objective Function 0.12I + 0.09B
Available Funds $50,000
0
I 10
30
20
40
50
60
Internet Fund (000s)
Internet fund Blue Chip fund Annual return b.
$20,000 $30,000 $ 5,100
The third constraint for the aggressive investor becomes 6I + 4B 320 This constraint is redundant; the available funds and the maximum Internet fund investment constraints define the feasible region. The optimal solution is: Internet fund Blue Chip fund Annual return
$35,000 $15,000 $ 5,550
The aggressive investor places as much funds as possible in the high return but high risk Internet fund. c.
The third constraint for the conservative investor becomes 6I + 4B 160 This constraint becomes a binding constraint. The optimal solution is Internet fund Blue Chip fund Annual return
$0 $40,000 $ 3,600 2 - 21
© 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
The slack for constraint 1 is $10,000. This indicates that investing all $50,000 in the Blue Chip fund is still too risky for the conservative investor. $40,000 can be invested in the Blue Chip fund. The remaining $10,000 could be invested in low-risk bonds or certificates of deposit. 28. a.
Let W = number of jars of Western Foods Salsa produced M = number of jars of Mexico City Salsa produced Max s.t.
1W
+
1.25M
5W 3W + 2W + W, M 0
7M 1M 2M
4480 2080 1600
Whole tomatoes Tomato sauce Tomato paste
Note: units for constraints are ounces b.
Optimal solution: W = 560, M = 240 Value of optimal solution is 860
29. a.
Let B = proportion of Buffalo's time used to produce component 1 D = proportion of Dayton's time used to produce component 1
Buffalo Dayton
Maximum Daily Production Component 1 Component 2 2000 1000 600 1400
Number of units of component 1 produced: 2000B + 600D Number of units of component 2 produced: 1000(1 - B) + 600(1 - D) For assembly of the ignition systems, the number of units of component 1 produced must equal the number of units of component 2 produced. Therefore, 2000B + 600D = 1000(1 - B) + 1400(1 - D) 2000B + 600D = 1000 - 1000B + 1400 - 1400D 3000B + 2000D = 2400 Note: Because every ignition system uses 1 unit of component 1 and 1 unit of component 2, we can maximize the number of electronic ignition systems produced by maximizing the number of units of subassembly 1 produced. Max 2000B + 600D In addition, B 1 and D 1.
2 - 22 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
The linear programming model is: Max s.t.
2000B
+ 600D
3000B B
+ 2000D
= 2400 1 1 0
D B, D
The graphical solution is shown below. D 1.2
1.0
30
.8
00 B+ 20
.6
00 D =2 40
.4
0
Optimal Solution
2000B + 600D = 300
.2
B 0
.2
.4
.6
.8
1.0
1.2
Optimal Solution: B = .8, D = 0 Optimal Production Plan Buffalo - Component 1 Buffalo - Component 2 Dayton - Component 1 Dayton - Component 2
.8(2000) = 1600 .2(1000) = 200 0(600) = 0 1(1400) = 1400
Total units of electronic ignition system = 1600 per day.
2 - 23 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
30. a.
Let
E = number of shares of Eastern Cable C = number of shares of ComSwitch
Max s.t.
15E
+ 18C
40E 40E
+ 25C
25C 25C E, C 0
50,000 15,000 10,000 25,000
Maximum Investment Eastern Cable Minimum ComSwitch Minimum ComSwitch Maximum
b. C
Number of Shares of ComSw itch
2000
Minimum Eastern Cable
1500
Maximum Comswitch
1000
Maximum Investment 500 Minimum Conswitch
0
500 1000 1500 Number of Shares of Eastern Cable
E
c.
There are four extreme points: (375,400); (1000,400);(625,1000); (375,1000)
d.
Optimal solution is E = 625, C = 1000 Total return = $27,375
2 - 24 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
31.
B 6
Feasible Region
4
2
A 0
2
4
6 3A + 4B = 13
Optimal Solution A = 3, B = 1 Objective Function Value = 13 32. A B A
B A
2 - 25 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
Extreme Points (A = 250, B = 100) (A = 125, B = 225) (A = 125, B = 350)
Objective Function Value 800 925 1300
Surplus Demand 125 — —
Surplus Total Production — — 125
Slack Processing Time — 125 —
33. a.
xB2 6
4
2
0
xA1 2
4
6
Optimal Solution: A = 3, B = 1, value = 5 b. (1) (2) (3) (4)
3 + 4(1) = 7 2(3) + 1 = 7 3(3) + 1.5 = 10.5 -2(3) +6(1) = 0
Slack = 21 - 7 = 14 Surplus = 7 - 7 = 0 Slack = 21 - 10.5 = 10.5 Surplus = 0 - 0 = 0
2 - 26 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
c. B
A
Optimal Solution: A = 6, B = 2, value = 34 34. a. B x2 4
3 Feasible Region
2
(21/4, 9/4)
1
(4,1) x1A 0
1
2
3
4
5
b.
There are two extreme points: (A = 4, B = 1) and (A = 21/4, B = 9/4)
c.
The optimal solution is A = 4, B = 1
6
2 - 27 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
35. a. Min s.t.
6A
+
4B
+
0S1
2A 1A
+ +
1B 1B 1B
-
S1
+
-
0S2
+
0S3
S2 +
S3
= = =
12 10 4
A, B, S1, S2, S3 0 b.
The optimal solution is A = 6, B = 4.
c.
S1 = 4, S2 = 0, S3 = 0.
36. a.
Let
Max s.t.
T = P =
number of training programs on teaming number of training programs on problem solving
10,000T
+
8,000P
+ +
P P 2P
T T 3T
8 10 25 84
Minimum Teaming Minimum Problem Solving Minimum Total Days Available
T, P 0
2 - 28 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
b. P Minimum Teaming
Number o f Probl em-Solv ing Pro grams
40
30 Minimum Total 20
Days Available
Minimum Problem Solving
10
0
10 20 Number of Teaming Programs
c.
There are four extreme points: (15,10); (21.33,10); (8,30); (8,17)
d.
The minimum cost solution is T = 8, P = 17 Total cost = $216,000
30
T
37. Mild Extra Sharp
Regular 80% 20%
Zesty 60% 40%
8100 3000
Let R = number of containers of Regular Z = number of containers of Zesty Each container holds 12/16 or 0.75 pounds of cheese Pounds of mild cheese used
= =
0.80 (0.75) R + 0.60 (0.75) Z 0.60 R + 0.45 Z
Pounds of extra sharp cheese used = =
0.20 (0.75) R + 0.40 (0.75) Z 0.15 R + 0.30 Z
2 - 29 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
Cost of Cheese
= = = =
Cost of mild + Cost of extra sharp 1.20 (0.60 R + 0.45 Z) + 1.40 (0.15 R + 0.30 Z) 0.72 R + 0.54 Z + 0.21 R + 0.42 Z 0.93 R + 0.96 Z
Packaging Cost = 0.20 R + 0.20 Z Total Cost
= (0.93 R + 0.96 Z) + (0.20 R + 0.20 Z) = 1.13 R + 1.16 Z
Revenue
= 1.95 R + 2.20 Z
Profit Contribution = Revenue - Total Cost = (1.95 R + 2.20 Z) - (1.13 R + 1.16 Z) = 0.82 R + 1.04 Z Max s.t.
0.82 R
+
1.04 Z
0.60 R + 0.15 R + R, Z 0
0.45 Z 0.30 Z
8100 3000
Mild Extra Sharp
Optimal Solution: R = 9600, Z = 5200, profit = 0.82(9600) + 1.04(5200) = $13,280 38. a.
Let
S = yards of the standard grade material per frame P = yards of the professional grade material per frame
Min s.t.
7.50S
+ 9.00P
0.10S + 0.30P 0.06S + 0.12P S + P S, P 0
6 3 = 30
carbon fiber (at least 20% of 30 yards) kevlar (no more than 10% of 30 yards) total (30 yards)
2 - 30 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
b. P
Professional Grad e (yards)
50
40
total Extreme Point S = 10 P = 20
30
Feasible region is the line segment
20
kevlar carbon fiber
10
Extreme Point S = 15 P = 15 S 0
10
20
30
40
50
60
Standard Grade (yards)
c. Extreme Point (15, 15) (10, 20)
Cost 7.50(15) + 9.00(15) = 247.50 7.50(10) + 9.00(20) = 255.00
The optimal solution is S = 15, P = 15 d.
Optimal solution does not change: S = 15 and P = 15. However, the value of the optimal solution is reduced to 7.50(15) + 8(15) = $232.50.
e.
At $7.40 per yard, the optimal solution is S = 10, P = 20. The value of the optimal solution is reduced to 7.50(10) + 7.40(20) = $223.00. A lower price for the professional grade will not change the S = 10, P = 20 solution because of the requirement for the maximum percentage of kevlar (10%).
39. a.
Let S = number of units purchased in the stock fund M = number of units purchased in the money market fund Min s.t.
8S
+
50S 5S
+ +
3M
100M 4M M S, M, 0
1,200,000 Funds available 60,000 Annual income 3,000 Minimum units in money market
2 - 31 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
Units of Money Market Fund
x2 M
20000 + 3M = 62,000 8x8S 1 + 3x2 = 62,000
15000 Optimal Solution .
10000
5000
0
5000
10000
15000
20000
x1S
Units of Stock Fund Optimal Solution: S = 4000, M = 10000, value = 62000
40.
b.
Annual income = 5(4000) + 4(10000) = 60,000
c.
Invest everything in the stock fund. Let P1 = gallons of product 1 P2 = gallons of product 2 Min s.t.
1P1
+
1P2
1P1
+
1P1
1P2 2P2 + P1, P2 0
30 20 80
Product 1 minimum Product 2 minimum Raw material
2 - 32 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
P2
Feasible Region
P +1
1
60
1P =
2
55
Number of Gallons of Product 2
80
40
20
Use 80 gal s.
(30,25) 0
40 20 60 80 Number of Gallons of Product 1
P1
Optimal Solution: P1 = 30, P2 = 25 Cost = $55 41. a.
Let R = number of gallons of regular gasoline produced P = number of gallons of premium gasoline produced Max s.t.
0.30R
+
0.50P
0.30R 1R
+ +
0.60P 1P 1P
18,000 50,000 20,000
Grade A crude oil available Production capacity Demand for premium
R, P 0
2 - 33 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
b. P
Gallons o f Premiu m Gasoli ne
60,000
50,000 Production Capacity 40,000
30,000 Maximum Premium
20,000
Optimal Solution R = 40,000, P = 10,000 $17,000
10,000
Grade A Crude Oil 0
R 10,000 20,000 30,000 40,000 50,000 60,000 Gallons of Regular Gasoline
Optimal Solution: 40,000 gallons of regular gasoline 10,000 gallons of premium gasoline Total profit contribution = $17,000 c. Constraint 1 2 3
d.
Value of Slack Variable 0 0 10,000
Interpretation All available grade A crude oil is used Total production capacity is used Premium gasoline production is 10,000 gallons less than the maximum demand
Grade A crude oil and production capacity are the binding constraints.
2 - 34 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
42. B x2
14 Satisfies Constraint # 2
12 10 8
Infeasibility
6 4
Satisfies Constraint # 1
2 0
4
2
6
8
10
12
x1A
43. Bx 2 4 Unbounded
3 2 1
0
1
2
3
x1A
44. a.
xB2 Objective Function Optimal Solution (30/16, 30/16) Value = 60/16
4
2 0 b.
2
4
xA1
New optimal solution is A = 0, B = 3, value = 6.
2 - 35 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
45. a. B
A A
A
46.
B A
b.
Feasible region is unbounded.
c.
Optimal Solution: A = 3, B = 0, z = 3.
d.
An unbounded feasible region does not imply the problem is unbounded. This will only be the case when it is unbounded in the direction of improvement for the objective function. Let
N = number of sq. ft. for national brands G = number of sq. ft. for generic brands
Problem Constraints: N N
+
G G
200 120 20
Space available National brands Generic
2 - 36 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
Extreme Point 1 2 3
N 120 180 120
G 20 20 80
a.
Optimal solution is extreme point 2; 180 sq. ft. for the national brand and 20 sq. ft. for the generic brand.
b.
Alternative optimal solutions. Any point on the line segment joining extreme point 2 and extreme point 3 is optimal.
c.
Optimal solution is extreme point 3; 120 sq. ft. for the national brand and 80 sq. ft. for the generic brand.
2 - 37 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
47. Bx2
e Tim ing cess Pro
600
500 400
300 Alternate optima (125,225)
200
100
(250,100)
0
100
200
300
400
xA 1
Alternative optimal solutions exist at extreme points (A = 125, B = 225) and (A = 250, B = 100). Cost
= 3(125) + 3(225) = 1050
Cost
= 3(250) + 3(100) = 1050
or
The solution (A = 250, B = 100) uses all available processing time. However, the solution (A = 125, B = 225) uses only 2(125) + 1(225) = 475 hours. .
Thus, (A = 125, B = 225) provides 600 - 475 = 125 hours of slack processing time which may be used for other products.
2 - 38 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
48.
Possible Actions: i.
Reduce total production to A = 125, B = 350 on 475 gallons.
ii.
Make solution A = 125, B = 375 which would require 2(125) + 1(375) = 625 hours of processing time. This would involve 25 hours of overtime or extra processing time.
iii. Reduce minimum A production to 100, making A = 100, B = 400 the desired solution. 49. a.
Let
P = number of full-time equivalent pharmacists T = number of full-time equivalent physicians
The model and the optimal solution are shown below: MIN 40P+10T S.T. 1) 2) 3)
P+T >=250 2P-T>=0 P>=90
Optimal Objective Value 5200.00000 Variable P T
Value 90.00000 160.00000
Reduced Cost 0.00000 0.00000
2 - 39 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
Constraint 1 2 3
Slack/Surplus 0.00000 20.00000 0.00000
Dual Value 10.00000 0.00000 30.00000
The optimal solution requires 90 full-time equivalent pharmacists and 160 full-time equivalent technicians. The total cost is $5200 per hour. b. Pharmacists Technicians
Current Levels 85 175
Attrition 10 30
Optimal Values 90 160
New Hires Required 15 15
The payroll cost using the current levels of 85 pharmacists and 175 technicians is 40(85) + 10(175) = $5150 per hour. The payroll cost using the optimal solution in part (a) is $5200 per hour. Thus, the payroll cost will go up by $50 50.
Let
M = number of Mount Everest Parkas R = number of Rocky Mountain Parkas Max s.t.
100M
+
150R
30M 45M 0.8M
+ + -
20R 15R 0.2R
7200 Cutting time 7200 Sewing time 0 % requirement
Note: Students often have difficulty formulating constraints such as the % requirement constraint. We encourage our students to proceed in a systematic step-by-step fashion when formulating these types of constraints. For example: M must be at least 20% of total production M 0.2 (total production) M 0.2 (M + R) M 0.2M + 0.2R 0.8M - 0.2R 0
2 - 40 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
An Introduction to Linear Programming
The optimal solution is M = 65.45 and R = 261.82; the value of this solution is z = 100(65.45) + 150(261.82) = $45,818. If we think of this situation as an on-going continuous production process, the fractional values simply represent partially completed products. If this is not the case, we can approximate the optimal solution by rounding down; this yields the solution M = 65 and R = 261 with a corresponding profit of $45,650. 51.
Let
C = number sent to current customers N = number sent to new customers
Note: Number of current customers that test drive = .25 C Number of new customers that test drive = .20 N Number sold = .12 ( .25 C ) + .20 (.20 N ) = .03 C + .04 N Max s.t.
.03C
+
.04N
.25 C .20 N .25 C - .40 N 4C + 6N C, N, 0
30,000 10,000 0 1,200,000
Current Min New Min Current vs. New Budget
2 - 41 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
Current Min.
N 200,000
Current 2 New
Budget
.03 C
+. 04
N
=6
00 0
100,000
Optimal Solution C = 225,000, N = 50,000 Value = 8,750 New Min.
0
52.
Let
100,000
200,000
S = number of standard size rackets O = number of oversize size rackets Max s.t.
10S
+
15O
0.8S 10S 0.125S
+ + S, O, 0
0.2O 12O 0.4O
0 4800 80
% standard Time Alloy
2 - 42 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
300,000
C
An Introduction to Linear Programming
53. a.
Let
R = time allocated to regular customer service N = time allocated to new customer service Max s.t.
1.2R
+
N
R 25R -0.6R
+ + +
N 8N N
80 800 0
R, N, 0 b. Optimal Objective Value 90.00000 Variable R N
Value 50.00000 30.00000
Reduced Cost 0.00000 0.00000
Constraint 1 2 3
Slack/Surplus 0.00000 690.00000 0.00000
Dual Value 1.12500 0.00000 -0.12500
Optimal solution: R = 50, N = 30, value = 90 HTS should allocate 50 hours to service for regular customers and 30 hours to calling on new customers. 54. a.
Let
M1 = number of hours spent on the M-100 machine M2 = number of hours spent on the M-200 machine
Total Cost 6(40)M1 + 6(50)M2 + 50M1 + 75M2 = 290M1 + 375M2 Total Revenue 25(18)M1 + 40(18)M2 = 450M1 + 720M2 Profit Contribution (450 - 290)M1 + (720 - 375)M2 = 160M1 + 345M2
2 - 43 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Chapter 2
Max s.t.
160 M1
+
345M2
M1 M2 M1 40 M1
+
M2 50 M2
15 10 5 5 1000
M-100 maximum M-200 maximum M-100 minimum M-200 minimum Raw material available
M1, M2 0 b. Optimal Objective Value 5450.00000 Variable M1 M2
Value 12.50000 10.00000
Reduced Cost 0.00000 145.00000
Constraint 1 2 3 4 5
Slack/Surplus 2.50000 0.00000 7.50000 5.00000 0.00000
Dual Value 0.00000 145.00000 0.00000 0.00000 4.00000
The optimal decision is to schedule 12.5 hours on the M-100 and 10 hours on the M-200. 55.
Mr. Krtick’s solution cannot be optimal. Every department has unused hours, so there are no binding constraints. With unused hours in every department, clearly some more product can be made.
56.
No, it is not possible that the problem is now infeasible. Note that the original problem was feasible (it had an optimal solution). Every solution that was feasible is still feasible when we change the constraint to less-than-or-equal-to, since the new constraint is satisfied at equality (as well as inequality). In summary, we have relaxed the constraint so that the previous solutions are feasible (and possibly more satisfying the constraint as strict inequality).
57.
Yes, it is possible that the modified problem is infeasible. To see this, consider a redundant greaterthan-or-equal to constraint as shown below. Constraints 2, 3, and 4 form the feasible region and constraint 1 is redundant. Change constraint 1 to less-than-or-equal-to and the modified problem is infeasible.
2 - 44 © 2010 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.