Integer Linear Programming
17 – 13
subject to
Every City is assigned to exactly one carrier:
x[1,1] + x[1,2] + x[1,3] + x[1,4] + x[1,5] + x[1,6] + x[1,7] = 1
x[2,1] + x[2,2] + x[2,3] + x[2,4] + x[2,5] + x[2,6] + x[2,7] = 1
x[3,1] + x[3,2] + x[3,3] + x[3,4] + x[3,5] + x[3,6] + x[3,7] = 1
x[4,1] + x[4,2] + x[4,3] + x[4,4] + x[4,5] + x[4,6] + x[4,7] = 1
x[5,1] + x[5,2] + x[5,3] + x[5,4] + x[5,5] + x[5,6] + x[5,7] = 1
x[12,1] + x[12,2] + x[12,3] + x[12,4] + x[12,5] + x[12,6] + x[12,7] = 1
x[13,1] + x[13,2] + x[13,3] + x[13,4] + x[13,5] + x[13,6] + x[13,7] = 1
x[14,1] + x[14,2] + x[14,3] + x[14,4] + x[14,5] + x[14,6] + x[14,7] = 1
x[15,1] + x[15,2] + x[15,3] + x[15,4] + x[15,5] + x[15,6] + x[15,7] = 1
x[16,1] + x[16,2] + x[16,3] + x[16,4] + x[16,5] + x[16,6] + x[16,7] = 1
If a Carrier is selected, it can be assigned only the number of bids made:
Note:
The idea here is that if carrier j is not chosen, then no cities can be assigned to that carrier. Hence if y[j] =
0, the sum must be less than or equal to zero and hence all the associated x’s must be zero. If y[j] = 1 then
the constraint becomes redundant. It could also be modeled as x[i,j] ≤ y[j] but this would generate more
constraints
x[1,1] + x[2,1] + x[3,1] + x[4,1] + x[5,1] + x[6,1] + x[7,1]+ x[8,1] +
x[9,1] + x[10,1] + x[11,1] + x[12,1] + x[13,1] + x[14,1] + x[15,1] +
x[16,1] + x[17,1] + x[18,1] + x[19,1] + x[20,1] ≤ 10y[1]
x[1,4] + x[2,4] + x[3,4] + x[4,4] + x[5,4] + x[6,4] + x[7,4]+ x[8,4] +
x[9,4] + x[10,4] + x[11,4] + x[12,4] + x[13,4] + x[14,4] + x[15,4] +
x[16,4] + x[17,4] + x[18,4] + x[19,4] + x[20,4] ≤ 7y[4]
x[1,5] + x[2,5] + x[3,5] + x[4,5] + x[5,5] + x[6,5] + x[7,5] + x[8,5] +
x[9,5] + x[10,5] + x[11,5] + x[12,5] + x[13,5] + x[14,5] + x[15,5] +
x[16,5] + x[17,5] + x[18,5] + x[19,5] + x[20,5] ≤ 20y[5]
Chapter 11
17 – 14
x[1,7] + x[2,7] + x[3,7] + x[4,7] + x[5,7] + x[6,7] + x[7,7] + x[8,7] +
x[9,7] + x[10,7] + x[11,7] + x[12,7] + x[13,7] + x[14,7] + x[15,7] +
x[16,7] + x[17,7] + x[18,7] + x[19,7] + x[20,7] ≤ 18y[7]
Non-bids must be set to 0:
x[1,3] + x[2,3] + x[3,3] + x[4,3] + x[5,3] + x[6,3] + x[7,3] + x[8,3]
+ x[9,3] + x[10,3] = 0
x[1,4] + x[2,4] + x[3,4] + x[4,4] + x[5,4] + x[6,4] + x[13,4] + x[14,4]
+ x[15,4] + x[16,4] + x[17,4] + x[19,4] + x[20,4] = 0
No more than 3 carriers
y[1] + y[2] + y[3] + y[4] + y[5] + y[6] + y[7] ≤ 3
Solution: Total Cost = $436,512
Carrier 2: assigned cities 2, 3, 4, 5, 6, and 9
b.
Given the incremental drop in cost, three seems like the correct number of carriers (the curve flattens
considerably after three carriers).
17 – 15
13. a. One just needs to add the following multiple choice constraint to the problem.
y1 + y2 = 1
New Optimal Solution: y1 = 1, y3 = 1, x12 = 10, x31 = 30, x52 = 10, x53 = 20
Value = 940
14. a. Let 1 denote the Michigan plant
2 denote the first New York plant
3 denote the second New York plant
It is not possible to meet needs by modernizing only one plant.
The following table shows the options which involve modernizing two plants.
Plant
Transmission
Engine Block
1
2
3
4
5
Capacity
Capacity
Feasible ?
Cost
700
1300
No
1100
900
Yes
60
900
1400
Yes
65
600
700
No
1200
1200
Yes
70
1000
1700
Yes
75
700
1000
No
1400
1300
Yes
75
1100
600
No
900
1100
Yes
60
b. Modernize plants 1 and 3 or plants 4 and 5.
c. Let
1 if plant is modernized
0 if plant is not modernized
i
i
xi
=
Chapter 11
17 – 16
d. Optimal Solution: x1 = x3 = 1.
15.
a. Let xj = 1 if place a PBB in county j , 0 if not j=1,2,…88
Min x1 + x2 + x3 +….+ x88
s.t.
17 – 17
16. a.
min
105x9
+
105x10
+
105x11
+
32y9
+
32y10
+
32y11
+
32y12
+
32y1
+
32y2
+
32y3
x9
+
y9
6
x9
+
x10
+
y9
+
y10
4
x9
+
x10
+
x11
+
y9
+
y10
+
y11
8
x9
+
x10
+
x11
+
y9
+
y10
+
y11
+
y12
10
x9
x11
+
y11
+
y12
+
y1
+
6
x9
+
x10
+
y12
+
y1
+
+
4
x9
+
x10
+
x11
+
y1
+
+
7
x10
+
+
+
6
x11
+
6
x10
+
x11
+
y10
+
y11
+
y12
+
y1
9
b. Solution to LP Relaxation obtained using LINDO/PC:
y9 = 6 y12 = 6 y3 = 6 All other variables = 0.
y11 = 2 y1 = 1 Cost: $672.
d. Add the following constraints to the formulation in part (a).
x9 1
x11 1
x9 +x10 + x11 5
The new optimal solution, which has a daily cost of $909 is
Chapter 11
17 – 18
17. a. Let xj = 1 if place a PBB in county j , 0 if not for j=1,2,…88
Let yi = 1 if county i is covered (that is, shares a border with a county with a PPB or has a PBB
located in it), 0 if not for j=1,2,…88
Max 36396y1 + 39987y2 + ….+ 17382y88
b. Solution for k=2 is place PPBs in counties 11 and 77 with a population reach of 5,239,214.
c. Based on the graph below, 7 or 8 PPBs seems reasonable, as the incremental reach decreases
significantly at that point.
18. a. Add the part-worths for Antonio’s Pizza for each consumer in the Salem Foods’ consumer panel.
Consumer
Overall Preference for Antonio’s
1
2 + 6 + 17 + 27
= 52
2
7 + 15 + 26 + 1
= 49
3
5 + 8 + 7 + 16
= 36
4
= 83
5
8 + 6 + 20 + 5
= 39
6
= 70
7
= 79
8
9 + 4 + 16 + 30
= 59
17 – 19
b. Let lij = 1 if level i is chosen for attribute j, 0 otherwise
yk = 1 if consumer k chooses the Salem brand, 0 otherwise
Max y1 + y2 + y3 + y4 + y5 + y6 + y7 + y8
s.t.
11l11 +
2l21 +
6l12 +
7l22 +
3l13 +
17l23 +
26l14 +
27l24 +
8l34 –
52y1
1
11l11 +
7l21 +
15l12 +
17l22 +
16l13 +
26l23 +
14l14 +
1l24 +
10l34 –
49y2
1
7l11 +
5l21 +
8l12 +
14l22 +
16l13 +
7l23 +
29l14 +
16l24 +
19l34 –
36y3
1
13l11 +
20l21 +
20l12 +
17l22 +
17l13 +
14l23 +
25l14 +
29l24 +
10l34 –
83y4
1
8l21 +
6l12 +
11l22 +
30l13 +
20l23 +
15l14 +
5l24 +
12l34 –
39y5
1
12l11 +
17l21 +
11l12 +
9l22 +
2l13 +
30l23 +
22l14 +
12l24 +
20l34 –
70y6
1
19l21 +
12l12 +
16l22 +
16l13 +
25l23 +
30l14 +
23l24 +
19l34 –
79y7
1
9l21 +
4l12 +
14l22 +
23l13 +
16l23 +
16l14 +
30l24 +
3l34 –
59y8
1
The optimal solution shows l21 = l22 = l23 = l24 = 1. This calls for a pizza with a thick crust, a cheese
blend, a chunky sauce, and medium sausage. With y1 = y2 = y3 = y5 = y7 = y8 = 1, we see that 6 of the
8 people in the consumer panel will prefer this pizza to Antonio’s.
19. a. Let lij = 1 if level i is chosen for attribute j, 0 otherwise
yk = 1 if child k prefers the new cereal design, 0 otherwise
The share of choices problem to solve is given below:
Max y1 + y2 + y3 + y4 + y5 + y6
s.t.
15l11 +
35l21 +
30l12 +
40l22 +
25l32 +
15l13 +
9l23 –
75y1
1
30l11 +
20l21 +
40l12 +
35l22 +
25l32 +
8l13 +
11l23 –
75y2
1
40l11 +
25l21 +
20l12 +
40l22 +
10l32 +
7l13 +
14l23 –
75y3
1
35l11 +
30l21 +
25l12 +
20l22 +
30l32 +
15l13 +
18l23 –
75y4
1
25l11 +
40l21 +
40l12 +
20l22 +
35l32 +
18l13 +
14l23 –
75y5
1
20l11 +
25l21 +
20l12 +
35l22 +
30l32 +
9l13 +
16l23 –
75y6
1
30l11 +
15l21 +
25l12 +
40l22 +
40l32 +
20l13 +
11l23 –
75y7
1
The optimal solution obtained using LINDO on Excel shows l11 = l32 = l13 = 1. This indicates that a
cereal with a low wheat/corn ratio, artificial sweetener, and no flavor bits will maximize the share of
choices.
The optimal solution also has y4 = y5 = y7 = 1 which indicates that children 4, 5, and 7 will prefer this
cereal.
b. The coefficients for the yi variable must be changed to -70 in constraints 1-4 and to -80 in constraints
5-7.
Chapter 11
17 – 20
20. a. Objective function changes to
Min 25x1 + 40x2 + 40x3 + 40x4 + 25x5
b. x4 = x5 = 1; modernize the Ohio and California plants.
21. a. Let
1 if a camera is located at opening
0 if not
i
i
x
=
min x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 + x13
s.t.
x1 + x4 + x6 1 Room 1
x6 + x8 + x12 1 Room 2
x1 + x2 + x3 1 Room 3
b. x1 = x5 = x8 = x13 = 1. Thus, cameras should be located at 4 openings: 1, 5, 8, and 13.
An alternative optimal solution is x1 = x7 = x11 = x12 = 1.
c. Change the constraint for room 7 to x2 + x5 + x9 + x11 2
d. x3 = x6 = x9 = x11 = x12 = 1. Thus, cameras should be located at openings 3, 6, 9, 11, and 12.
An alternate optimal solution is x2 = x4 = x6 = x10 = x11 = 1. Optimal Value = 5.
17 – 21
23. a. A mixed integer linear program can be set up to solve this problem. Binary variables are used to
indicate whether or not we setup to produce the subassemblies.
Let SB = 1 if bases are produced; 0 if not
STVC = 1 if TV cartridges are produced; 0 if not
SVCRC = 1 if VCR cartridges are produced; 0 if not
•
•
•
VCRPP = No. of VCR keypads purchased
A mixed integer linear programming model for solving this problem follows. There are 11
constraints. Constraints (1) to (5) are to satisfy demand. Constraint (6) reflects the limitation on
manufacturing time. Finally, constraints (7) – (11) are constraints not allowing production unless the
setup variable equals 1. Variables SB, STVC, SVCRC, STVP, and SVCRP must be specified as 0/1.
LINEAR PROGRAMMING PROBLEM
S.T.
1) 1BM+1BP=12000
2) +1TVCM+1TVCP=7000
3) +1VCRCM+1VCRCP=5000
4) +1TVPM+1TVPP=7000
5) +1VCRPM+1VCRPP=5000
OPTIMAL SOLUTION
Objective Function Value = 52800.00
Variable Value
————– —————
BM 12000.000
TVCM 7000.000
VCRCM 0.000
TVPM 0.000
Chapter 11
17 – 22
VCRPP 5000.000
SB 1.000
STVC 1.000
Constraint Slack/Surplus
————– —————
1 0.000
2 0.000
3 0.000
4 0.000
b. This can be solved by changing appropriate coefficients in the formulation for part (a). The SVCRC
coefficient becomes 3000 and the VCRCM coefficient becomes 2.6 in the objective function. Also,
the coefficient of VCRCM becomes 2.5 in constraint (6). The new optimal solution follows.
OPTIMAL SOLUTION
Objective Function Value = 52300.00
Variable Value
————– —————
BM 0.000
TVCM 7000.000
VCRCM 5000.000
VCRCP 0.000
TVPP 7000.000
VCRPP 5000.000
Constraint Slack/Surplus
————– —————
1 0.000
2 0.000
3 0.000
4 0.000
17 – 23
9 0.000
10 0.000
11 0.000
24. Let Xi = the amount (dollars) to invest in alternative i for i=1,2,…10
Let Yi = 1 if Dave invests in alternative i, 0 if not for i = 1,2…10
Max .067X1 + .0765X2 + .0755X3 + .0745X4 + .075X5 + .0645X6 +
.0705X7 + .069X8 + .052X9 + .059X10
Subject to
Y9 + Y10 ≥ 1 At least 1 must be a pure bond fund
X9 + X10 ≥ X1 + X2 + X3 + X4 Amount in pure bonds must be at least that invested
in pure growth funds
Xi ≥ 0 i=1,2,..10
The optimal solution follows:
Fund
Type
Amount Invested
Fund 1
growth
$0
Fund 2
growth
$12,500
Fund 3
growth
$0
Fund 4
growth
$0
Fund 5
growth & income
$25,000
Fund 6
growth & income
$0
Fund 7
growth & income
$25,000
Fund 8
stock & bond
$25,000
Fund 9
bond
$0
Fund 10
bond
$12,500
Total Invested
The optimal return on investment is $7,056.25.
Assumptions: (1) the expected annual returns are valid for the future. (2) All $100,000 will be invested. (3)
These are the only alternatives for this $100,000.
Chapter 11
17 – 24
25. a. Let
1 if a service facility is located in city
0 otherwise
i
i
x
=
Min
x1
+ x2
+ x3
+ x4
+ x5
+ x6
+ x7
+ x8
+ x9
+ x10
+ x11
+ x12
s.t.
1
(Boston)
x1
+ x2
+ x3
1
(New York)
x1
+ x2
+ x3
+ x4
+ x5
+ x6
1
(Philadelphia)
x1
+ x2
+ x3
+ x4
+ x5
+ x6
+ x7
1
(Baltimore)
x2
+ x3
+ x4
+ x5
+ x6
+ x7
1
(Washington)
x2
+ x3
+ x4
+ x5
+ x6
+ x7
1
(Richmond)
x2
+ x3
+ x4
+ x5
+ x6
+ x7
+ x8
1
(Raleigh)
x3
+ x4
+ x5
+ x6
+ x7
+ x8
+ x9
1
(Florence)
x6
+ x7
+ x8
+ x9
+ x10
1
(Savannah)
x7
+ x8
+ x9
+ x10
+ x11
1
(Jacksonville)
x8
+ x9
+ x10
+ x11
1
(Tampa)
x9
+ x10
+ x11
+ x12
1
(Miami)
x11
+ x12
1
b. 3 service facilities: Philadelphia, Savannah and Tampa.
Note: alternate optimal solution is New York, Richmond and Tampa.
c. 4 service facilities: New York, Baltimore, Savannah and Tampa.