MATH 3170 6.00 A SU 2012
Solutions to selected problems from Sections 9.2, 9.3 and 9.4.
9.2.12
Let y1 = 1 if NY is used, y2 = 1 if LA is used, y3 = 1 if Chicago is used, y4 = 1 if Atlanta is used. Also yi = 0 if city i is not used. Define xij = units shipped from warehouse in city i to region j
min z = 400y1 + 500y2 + 300y3 + 150y4 + 20x11 + 40x12 + 50x13 + 48x21 + 15x22 + 26x23 + 26x31 + 35x32 + 18x33 + 24x41 + 50x42 +35x43
st x11 + x21 + x31 + x41³80, x12 + x22 + x32 + x42³70
x13 + x23 + x33 + x43³40, x11 + x12 + x13£100y1
x21 + x22 + x23£100y2, x31 + x32 + x33£100y3,
x41 + x42 + x43£100y4, y1£y2, y2 + y4³1,
y1 + y2 + y3 + y4£2 , All xij³0, all yi = 0 or 1.
9.2.20
The question does not specifically disallow assigning two reps to the same state, and so it is possible to have that happen. However, in an optimal solution, that will never happen (why?). Therefore, the following formulation assumes that no two reps can be assigned to the same state. Let AB = 1 if a rep is assigned to states A and B, etc.
MAX 72 AB + 85 AC + 50 BD + 85 BE + 63 CD + 77 DE + 92 DG + 74 EF
+ 89 FG + 71 BC + 39 DF
SUBJECT TO
2) AB + AC + BD + BE + CD + DE + DG + EF + FG + BC + DF = 2
3) AB + AC £ 1
4) AB + BD + BE + BC £ 1
5) AC + CD + BC £ 1
6) BD + CD + DE + DG + DF £ 1
7) BE + DE + EF £ 1
8) DG + FG £ 1
9) EF + FG + DF £ 1
END
INTE 11
Here is an alternate solution. This formulation allows assigning two reps to one state and let the optimization take care of it. Let xij=1 if rep #i is assigned to state j, and 0 otherwise (i=1,2; j=A,B,…,G). Let yj=1 if state j has a rep, and 0 otherwise (j=A,B,…,G).
MAX 43yA + 29yB + 42yC + 21yD + 56yE + 18yF + 71yG
ST
xiA + xiB + xiC + xiD + xiE + xiF + xiG = 2
xiA + xiD £ 1
xiA + xiE £ 1
xiA + xiF £ 1
xiA + xiG £ 1
xiB + xiF £ 1
xiB + xiG £ 1
xiC + xiE £ 1
xiC + xiF £ 1
xiC + xiG £ 1
xiE + xiG £ 1
(for each i=1,2)
0.5(x1j+x2j) £ yj £ x1j+x2j
(for each j=A,B,…,G)
Each xij and yj is 0 or 1
9.2.21
Let xij = number of air conditioners (in thousands) produced in city i for region j (i = 1 is NY, j = 1 is East, etc.). Also let yj = 1 if factory is operated in city j, yj = 0 otherwise. Then the appropriate IP is (z is in thousands of dollars):
min z = 6000y1 + 5500y2 + 5800y3 +6200y4 + 206x11 + 225x12 + 230x13 +290x14 + 225x21 + 206x22 + 221x23 + 270x24 + 230x31 + 221x32 + 208x33 + 262x34 + 290x41 + 270x42 + 262x43 + 215x44
st x11 + x21 + x31 + x41³100 (East)
x12 + x22 + x32 + x42³150 (South)
x13 + x23 + x33 + x43³110 (Midwest)
x14 + x24 + x34 + x44³90 (West)
x11 + x12 + x13 + x14£150y1 (NY)
x21 + x22 + x23 + x24£150y2 (Atl)
x31 + x32 + x33 + x34£150y3 (Chic)
x41 + x42 + x43 + x44£150y4 (LA)
(Either x13³50 or x23³50)
50 - x13£50z
50 - x23£50(1 - z)
All xij integer; z, all yi = 0 or 1
9.2.23
Let Xij = 1 if machine i is used to do job j and Xij = 0 otherwise. Also let Yi = 1 if machine i is used at all and Yi = 0 otherwise.
MIN 42 X11 + 70 X12 + 93 X13 + 85 X22 + 45 X23 + 58 X31 + 37 X34 + 58 X41 + 55 X43 + 38 X45 + 60 X52 + 54 X54 + 30 Y1 + 40 Y2 + 50 Y3 + 60 Y4 + 20 Y5
SUBJECT TO
X11 + X31 + X41 = 1
X12 + X22 + X52 = 1
X13 + X23 + X43 = 1
X34 + X54 = 1
X45 = 1
X11 + X12 + X13 - 3 Y1 <= 0
X22 + X23 - 2 Y2 <= 0
X31 + X34 - 2 Y3 <= 0
X41 + X43 + X45 - 3 Y4 <= 0
X52 + X54 - 2 Y5 <= 0
Each Xij and Yi is 0 or 1
9.2.25
Let Region 1 = SE, Region 2 = NE, Region 3 = FW, Region 4 = MW, and let FF = Bank 1, R = Bank 2, PF = Bank 3, and B = Bank 4. Define xij = daily amount of checks for region i sent from bank j, and let yj = 1 if bank j is used and yj = 0 if bank j is not used. Then the appropriate IP is
max z = 1.05x11 + .30x12 + .90x13 + .75x14 + 1.2x21 + .60x22 + .75x23 + .45x24 + .60x31 + 1.2x32 + .30x33 + 1.65x34 + .75x41 +.60x42 + 1.05x43 + .75x44
50,000y1 40,000y2 30,000y3 20,000y4
st. x11 + x12 + x13 + x14 = 40,000
x21 + x22 + x23 + x24 = 60,000
x31 + x32 + x33 + x34 = 30,000
x41 + x42 + x43 + x44 = 50,000
x11 + x21 + x31 + x41£90,000y1
x12 + x22 + x32 + x42£90,000y2
x13 + x23 + x33 + x43£90,000y3
x14 + x24 + x34 + x44£90,000y4
xij³0, yj = 0 or 1
To understand the objective function observe that if x11 = 1, then each day $7 remains in the bank and earns interest for the Clearinghouse. Thus on an annual basis x11 =1 "earns"
Clearinghouse 7(.15) = $1.05. This explains the term 1.05x11 in
the objective function.
9.3.2
We wish to solve min z = 50x1 + 100x2
st 7x1 + 2x2³28
2x1 + 12x2³24
x1, x2³0
SP 1
Note: In solving subproblems we have used the result discussed in Problem 8 to conclude that in each subproblem's optimal solution the "newest" constraint must be binding. Thus we know that some optimal solution to SP2 will have x1 = 4.
The two optimal solutions x1 = 6, x2 = 1 and x1 = 4 , x2 = 2 have been found.
9.3.7
9.3.9
9a. Letting It = inventory at end of period t yields given LINDO printout (20 branches).
MIN 250 Y1 + 250 Y2 + 250 Y3 + 250 Y4 + 250 Y5 + 2 X1 + 2 X2 + 2 X3
+ 2 X4 + 2 X5 + I1 + I2 + I3 + I4 + I5
SUBJECT TO
2) - 1270 Y1 + X1 <= 0
3) - 1270 Y2 + X2 <= 0
4) - 1270 Y3 + X3 <= 0
5) - 1270 Y4 + X4 <= 0
6) - 1270 Y5 + X5 <= 0
7) - X1 + I1 = - 220
8) - X2 - I1 + I2 = - 280
9) - X3 - I2 + I3 = - 360
10) - X4 - I3 + I4 = - 140
11) - X5 - I4 + I5 = - 270
END
INTE 5
OBJECTIVE FUNCTION VALUE
1) 3680.000
VARIABLE VALUE REDUCED COST
Y1 1.000000 250.000000
Y2 1.000000 250.000000
Y3 1.000000 250.000000
Y4 0.000000 -1020.000000
Y5 1.000000 250.000000
X1 220.000000 0.000000
X2 280.000000 0.000000
X3 500.000000 0.000000
X4 0.000000 0.000000
X5 270.000000 0.000000
I1 0.000000 1.000000
I2 0.000000 1.000000
I3 140.000000 0.000000
I4 0.000000 2.000000
I5 0.000000 3.000000
9b. See attached LINDO printout . (LP solution yields optimal solution!!
MIN 250 Y1 + 250 Y2 + 250 Y3 + 250 Y4 + 250 Y5 + 2 X11 + 3 X12
+ 4 X13 + 5 X14 + 6 X15 + 2 X22 + 3 X23 + 4 X24 + 5 X25 + 2 X33 + 3 X34
+ 4 X35 + 2 X44 + 3 X45 + 2 X55
SUBJECT TO
2) X11 = 220
3) X12 + X22 = 280
4) X13 + X23 + X33 = 360
5) X14 + X24 + X34 + X44 = 140
6) X15 + X25 + X35 + X45 + X55 = 270
7) - 220 Y1 + X11 <= 0
8) - 280 Y1 + X12 <= 0
9) - 360 Y1 + X13 <= 0
10) - 140 Y1 + X14 <= 0
11) - 270 Y1 + X15 <= 0
12) - 280 Y2 + X22 <= 0
13) - 360 Y2 + X23 <= 0
14) - 140 Y2 + X24 <= 0
15) - 270 Y2 + X25 <= 0
16) - 360 Y3 + X33 <= 0
17) - 140 Y3 + X34 <= 0
18) - 270 Y3 + X35 <= 0
19) - 140 Y4 + X44 <= 0
20) - 270 Y4 + X45 <= 0
21) - 270 Y5 + X55 <= 0
END
INTE 5
OBJECTIVE FUNCTION VALUE
1) 3680.000
VARIABLE VALUE REDUCED COST
Y1 1.000000 250.000000
Y2 1.000000 -30.000000
Y3 1.000000 250.000000
Y4 0.000000 110.000000
Y5 1.000000 250.000000
X11 220.000000 0.000000
X12 0.000000 0.000000
X13 0.000000 2.000000
X14 0.000000 2.000000
X15 0.000000 4.000000
X22 280.000000 0.000000
X23 0.000000 1.000000
X24 0.000000 1.000000
X25 0.000000 3.000000
X33 360.000000 0.000000
X34 140.000000 0.000000
X35 0.000000 2.000000
X44 0.000000 0.000000
X45 0.000000 1.000000
X55 270.000000 0.000000
9c. Part (b) is faster.
9d. There are many fractional solutions for the Yi's that are feasible in LP relaxation for (9a) but not for (9b). For example, 1/1270<Y1<1/220 could yield a feasible solution with X11>0 for part (9a) but not for part (9b).Thus (9a) has a "bigger" feasible region to search and will take longer than (9b). Actually it has been shown that when solved as an LP the solution to (9b) will always yield integer values for the variables.
9.4.1
9.4.3