9 – 1
Chapter 9
Linear Programming Applications in Marketing, Finance, and
Operations Management
Case Problem 1: Planning an Advertising Campaign
The decision variables are as follows:
T1 = number of television advertisements with rating of 90 and 4000 new customers
T2 = number of television advertisements with rating of 40 and 1500 new customers
R1 = number of radio advertisements with rating of 25 and 2000 new customers
The Linear Programming Model and solution are as follows:
MAX 90T1+55T2+25R1+20R2+10N1+5N2
S.T.
1) 1T1<=10
2) 1R1<=15
3) 1N1<=20
4) 10000T1+10000T2+3000R1+3000R2+1000N1+1000N2<=279000
5) 4000T1+1500T2+2000R1+1200R2+1000N1+800N2>=100000
OPTIMAL SOLUTION
Optimal Objective Value
2160.00000
Variable
Value
Reduced Cost
T1
10.00000
0.00000
T2
5.00000
0.00000
Constraint
Slack/Surplus
Shadow Price
1
0.00000
35.00000
Linear Programming Applications in Marketing, Finance, and Operations Management
9 – 14
2
0.00000
5.00000
3
0.00000
5.00000
4
0.00000
0.00550
5
27100.00000
0.00000
6
3.00000
0.00000
7
5.00000
0.00000
8
10000.00000
0.00000
9
0.00000
0.00117
0.00000
-0.00050
Objective
Allowable
Allowable
Coefficient
Increase
Decrease
90.00000
Infinite
35.00000
55.00000
11.66667
5.00000
25.00000
5.00000
20.00000
5.00000
3.50000
10.00000
5.00000
0.50000
RHS
Allowable
Allowable
Value
Increase
Decrease
10.00000
5.00000
10.00000
15.00000
18.00000
15.00000
20.00000
10.00000
20.00000
279000.00000
15000.00000
10000.00000
100000.00000
27100.00000
3.00000
20.00000
5.00000
140000.00000
10000.00000
10000.00000
10000.00000
10000.00000
1. Summary of the Optimal Solution
T1 + T2 = 10 + 5 = 15 Television advertisements
R1 + R2 = 15 + 18 = 33 Radio advertisements
N1 + N2 = 20 + 10 = 30 Online advertisements
Advertising Schedule:
Media
Number of Ads
Television
15
Radio
33
Chapter 9
9 – 15
Online
30
Totals
78
2. The shadow price shows that total exposure increases 0.0055 points for each one dollar increase in
the advertising budget. Right Hand Side Ranges show this shadow price applies for a budget
increase of up to $15,000. Thus the shadow price applies for the $10,000 increase.
Total Exposure Rating would increase by 10,000(0.0055) = 55 points
3. The ranges for the exposure rating of 90 for the first 10 television ads show that the solution remains
optimal as long as the exposure rating is 55 or higher. This indicates that the solution is not very
sensitive to the exposure rating HJ has provided. Indeed, we would draw the same conclusion after
4. Remove constraint #5 for the linear programming model and use it to develop the objective function:
MAX 4000T1+1500T2+2000R1+1200R2+1000N1+800N2
Solving provides the following Optimal Solution
T1 + T2 = 10 + 4 = 14 Television advertisements
R1 + R2 = 15 + 13 = 28 Radio advertisements
N1 + N2 = 20 + 35 = 55 Online advertisements
Advertising Schedule:
Media
Number of Ads
Television
14
Radio
28
83,000
Online
55
55,000
Totals
97
$279,000
5. The solution with the objective to maximize the number of potential new customers reached looks
attractive. The total number of ads is increased from 78 to 97 (24%) and the number of potential
new customers reached is increased by 139,600 – 127,100 = 12,500 (9.8%).
Maximizing total exposure may seem to be the preferred objective because it is a more general
measure of advertising effectiveness. Exposure includes issues of image, message recall and appeal
9 – 14
At this point, we would expect some discussion concerning which solution is preferred: the one
obtained by maximizing total exposure or the one obtained by maximizing potential new customers
reached. Expect students to have differing opinions on the final recommendation. Basically, there
are two good media allocation solutions for this problem.
Case Problem 2: Phoenix Computer
1. The monthly cost of a new employee is $2,250 = $27,000/12. The training program is 3 months for
to be a laptop specialist is $8,250 = 3($2,250) + $1,500.
2. The training program is only 2 months for current employees and costs $1,000. So a replacement
3. It is clear that 100 new employees will need to be hired either to become laptop specialists
themselves or to replace current employees who will become laptop specialists. So the company’s
monthly payroll cost will increase by $225,000 = 100($2,250) in September over January.
A linear program can be formulated and solved to minimize the cost of hiring and training over the
period from February to August. The following variable definitions are used:
•
•
•
Jul 2 = No. of current employees entering the 2-month program in July
IdleMay = No. of trained laptop specialists in excess of those needed in May
•
•
•
IdleSep = No. of trained laptop specialists in excess of those needed in September
LINEAR PROGRAMMING PROBLEM
MIN
8250Feb3+5500Mar2+2250IdleMay+8250Mar3+5500Apr2+2250IdleJun+8250Apr3+55
Chapter 9
9 – 15
S.T.
1) 1Feb3+1Mar2–1IdleMay=20
2) 1Feb3+1Mar2+1Mar3+1Apr2–1IdleJun=30
1Feb3+1Mar2+1Mar3+1Apr2+1Apr3+1May2+1May3+1Jun2+1Jun3+1Jul2–IdleSep
=100
6) 1Mar2<=15
7) 1Mar2+1Apr2<=35
8) 1Mar2+1Apr2+1May2<=35
9) 1Mar2+1Apr2+1May2+1Jun2<=40
10) 1Mar2+1Apr2+1May2+1Jun2+1Jul2<=50
11) 1Feb3<=25
OPTIMAL SOLUTION
Optimal Objective Value
698750.00000
Variable
Value
Reduced Cost
Feb3
10.00000
0.00000
Mar2
10.00000
0.00000
IdleMay
0.00000
0.00000
0.00000
0.00000
0.00000
5.00000
0.00000
Apr3
25.00000
0.00000
May2
25.00000
0.00000
IdleJul
0.00000
9000.00000
May3
0.00000
9000.00000
Jun2
0.00000
0.00000
IdleAug
0.00000
2250.00000
Jun3
0.00000
2250.00000
15.00000
0.00000
0.00000
8250.00000
Constraint
Slack/Surplus
Shadow Price
1
0.00000
-2250.00000
2
0.00000
-2250.00000
3
0.00000
6750.00000
4
0.00000
0.00000
5
0.00000
6000.00000
6
5.00000
0.00000
7
8
0.00000
9
5.00000
0.00000
10
0.00000
-500.00000
11
15.00000
0.00000
12
0.00000
-2250.00000
13
0.00000
-4500.00000
14
0.00000
-6750.00000
15
25.00000
0.00000
16
10.00000
0.00000
Case Problem 3: Textile Mill Scheduling
Let X3R = Yards of fabric 3 on regular looms
X4R = Yards of fabric 4 on regular looms
X5R = Yards of fabric 5 on regular looms
X1D = Yards of fabric 1 on dobbie looms
X2D = Yards of fabric 2 on dobbie looms
X3D = Yards of fabric 3 on dobbie looms
Profit Contribution per Yard
Manufactured
Purchased
1
0.33
0.19
2
0.31
0.16
4
0.73
0.54
5
0.20
0.00
Production Times in Hours per Yard
Regular
Dobbie
1
—
0.21598
2
—
0.21598
Chapter 9
9 – 15
4
0.1912
0.1912
5
0.2398
0.2398
Model may use a Max Profit or Min Cost objective function.
Max 0.61X3R + 0.73X4R + 0.20X5R
+ 0.33X1D + 0.31X2D + 0.61X3D + 0.73X4D + 0.20X5D
Regular Hours Available
30 Looms x 30 days x 24 hours/day = 21600
Dobbie Hours Available
8 Looms x 30 days x 24 hours/day = 5760
Constraints:
Demand Constraints
X1D + Y1
= 16500
X2D + Y2
= 22000
X3R + X3D + Y3
= 62000
X4R + X4D + Y4
= 7500
X5R + X5D + Y5
= 62000
OPTIMAL SOLUTION
Optimal Objective Value
62531.49090
Variable
Value
Reduced Cost
X3R
27707.80815
0.00000
X4R
7500.00000
0.00000
X5R
62000.00000
0.00000
4668.80000
0.00000
X4D
0.00000
-0.01394
X5D
0.00000
-0.01748
Y1
11831.20000
0.00000
Y2
0.00000
Y3
34292.19185
0.00000
Y4
0.00000
0.00000
-0.06204
Constraint
Slack/Surplus
Shadow Price
1
0.00000
0.57530
2
0.00000
0.64820
3
0.00000
0.19000
4
0.00000
0.17000
5
0.00000
0.50000
6
0.00000
0.62000
7
0.00000
0.06204
Objective
Allowable
Allowable
Coefficient
Increase
Decrease
0.61000
0.01394
0.11000
0.73000
0.01394
0.20000
0.01748
0.33000
0.01000
0.01575
0.31000
Infinite
0.01000
0.61000
0.01394
Infinite
0.73000
0.01394
Infinite
0.20000
0.01748
Infinite
0.19000
0.01575
0.01000
0.16000
0.01000
Infinite
0.50000
0.11000
0.01394
0.54000
0.08000
Infinite
0.00000
0.06204
Infinite
RHS
Allowable
Allowable
Value
Increase
Decrease
21600.00000
6556.82444
5297.86007
5760.00000
2555.33477
1008.38013
4668.80000
Chapter 9
9 – 15
62000.00000
Infinite
34292.19185
Production/Purchase Schedule (Yards)
Regular
Looms
Dobbie
Looms
Purchased
1
4669
11831
2
22000
3
27711
4
7500
5
62000
Projected Profit: $62,531.49
Value of 9th Dobbie Loom
Shadow Price (Constraint 2) = 0.6482 per hour dobbie
Discussion of Objective Coefficient Ranges
For example, fabric one on the dobbie loom shares ranges of 0.31426 to 0.34 for the profit
maximization model or 0.64426 to 0.67 for the cost minimization model.
Note here that since demand for the fabrics is fixed, both the profit maximization and cost
minimization models will provide the same optimal solution. However, the interpretation of the
ranges for the objective function coefficients differ for the two models. In the profit maximization
case, the coefficients are profit contributions. Thus, the range information indicates how price per
Case Problem 4: Workforce Scheduling
9 – 14
1. Let tij = number of temporary employees hired under option i (i = 1, 2, 3) in month j (j = 1 for
January, j = 2 for February and so on)
The following table depicts the decision variables used in this case problem.
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
Option 2
Option 3
Costs: Contract cost plus training cost
Option
Contract Cost
Training Cost
Total Cost
1
$2000
$875
$2875
2
$4800
$875
$5675
3
$7500
$875
$8375
One constraint is required for each of the six months.
Constraint 1: Need 10 additional employees in January
t11 = number of temporary employees hired under Option 1 (one-month contract) in January
t21 = number of temporary employees hired under Option 2 (two-month contract) in January
t31 = number of temporary employees hired under Option 3 (three-month contract) in January
t11 + t21 + t31 = 10
Constraint 2: Need 23 additional employees in February
Note: The following table shows the decision variables used in this constraint
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
Option 2
Option 3
Constraint 3: Need 19 additional employees in March
Chapter 9
9 – 15
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
t13
Option 2
t22
t23
Option 3
t31
t32
t31 + t22 + t32 + t13 + t23 + t33 = 19
Constraint 4: Need 26 additional employees in May
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
t14
Option 2
t23
t24
Option 3
t32
Constraint 5: Need 20 additional employees in May
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
t15
Option 2
t24
t25
Option 3
t33
t34
Constraint 6: Need 14 additional employees in June
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
t16
Option 2
t25
Option 3
t34 + t25 + t16 = 14
Optimal Solution: Total Cost = $313,525
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
0
1
0
0
6
0
Option 2
3
0
0
0
0
Option 3
7
2.
Option
Number Hired
Contract Cost
Training Cost
Total Cost
1
7
$14,000
$6,125
$20,125
2
3
$14,400
$2,625
$17,025
3
33
$247,500
$28,875
$276,375
Total:
$275,900
$37,625
$313,525
9 – 14
Jan.
Feb.
Mar.
Apr.
May
June
Option 1
0
4
0
0
3
0
Option 2
0
0
0
3
0
Option 3
0
9
0
4
Option
Number Hired
Contract Cost
Training Cost
Total Cost
1
2
3
Total:
Full-time employees cost:
Training cost: 10($875) = $8,750
Salary: 10(6)(168)($16.50) = $166,320
Total Cost = $146,025 + $8750 + $166,320 = $321,095
4. With the lower training costs, the costs per employee for each option are as follows:
Option
Cost
Training Cost
Total Cost
1
$2000
$700
$2700
2
$4800
$700
$5500
3
$7500
$700
$8200
Resolving the original linear programming model with the above costs indicates that Davis should
Case Problem 5: Duke Energy Coal Allocation
A linear programming model can be used to determine how much coal to buy from each of the
mining companies and where to ship it. Let
ij
x
= tons of coal purchased from supplier i and used by generating unit j
The objective function minimizes the total cost to buy and burn coal. The objective function
Chapter 9
9 – 15
There are two types of constraints: supply constraints and demand constraints. The supply
constraints limit the amount of coal that can be bought under the various contracts. For the fixed-
tonnage contracts, the constraints are equalities. For the variable-tonnage contracts, any amount of
j
The demand constraints specify the number of mWh of electricity that must be generated by each
generating unit. Let
ij
a
= mWh hours of electricity generated by a ton of coal purchased from
supplier i and used by generating unit j, and Dj = mWh of electricity demand at generating unit j.
The demand constraints can then be written as follows:
1. The number of tons of coal that should be purchased from each of the mining companies and where
it should be shipped is shown below:
Miami Fort #
5
Miami Fort # 7
Beckjord
East Bend
Zimmer
RAG
0
0
61,538
288,462
0
Peabody
217,105
11,278
71,617
0
0
American
0
0
0
0
275,000
Consol
0
0
33,878
0
166,122
Cyprus
0
0
0
0
0
Addington
0
0
0
0
Waterloo
0
0
98,673
0
0
2. The cost of the coal in cents per million BTUs for each generating unit is as follows:
Miami Fort #5
Miami Fort #7
Beckjord
East Bend
Zimmer
111.84
136.97
127.24
103.85
114.51
3. The average number of BTUs per pound of coal received at each generating unit is shown
below:
9 – 14
Miami Fort #5
Miami Fort #7
Beckjord
East Bend
Zimmer
13,300
12,069
12,354
13,000
12,468
4. The sensitivity report shows that the shadow price per ton of coal purchased from American Coal
Sales is -$13 per ton and the allowable increase is 88,492 tons. This means that every additional ton
5. If the energy content of the Cyprus coal turns out to be 13,000 BTUs per ton the procurement plan
changes as shown below:
Miami Fort # 5
Miami Fort # 7
Beckjord
East Bend
Zimmer
RAG
0
0
61,538
288,462
0
Peabody
36,654
191,729
71,617
0
0
American
0
0
0
0
275,000
Consol
0
0
33,878
0
166,122
Cyprus
0
0
85,769
0
0
Addington
200,000
0
0
0
0
Waterloo
0
0
0
0
0
6. The shadow prices for the demand constraints are as follows:
Miami Fort #5
Miami Fort #7
Beckjord
East Bend
Zimmer
21
20
20
18
19
The East Bend unit is the least cost producer at the margin ($18 per mWh), and the allowable
increase is 160,000 mWh. Thus, Duke Energy should sell the 50,000 mWh over the grid. The
Chapter 9
9 – 15