9.16

A1234567891011121314151617BCDEFGHIJKProfit ($million)1 PlaneCustomer 1-1Customer 21Customer 31Capacity UsedCustomer 1Customer 2Customer 3Produce?Customer 1Customer 2Customer 31 Plane0002 Planes0003 Planes0004 Planes0005 PlanesTotal000011<=<=<=111Total Profit7($million) 1 Plane20@ %2 Planes40?@%3 Planes60%?60%4 Planes??80%5 Planes??100%TotalCapacityCapacityUsedAvailable100%<=100%2 Planes2533 Planes4?54 Planes??65 Planes??7 An alternative optimal solution is to produce 3 planes for customer 1 and 2 planes for customer 2. 9.17

A123456789101112131415BCDEFGUnit ProfitMilling machineLatheGrinderProduct 1$50Product 2$20Product 3$25HoursUsed500<=350<=135.714<=HoursAvailable500350150Total Profit$2,881Total220Machine Hours Used per Unit Produced935540302Product 230.952<=99910Product 30<=00<=Product 1Production Rate45.238<=Only if Produce999Produce?1Produce 3 Production Rate<=2Sales Potential 9.18

a) Let yij = 1 if xi = j; 0 otherwise (for i = 1, 2; and j = 1, 2, 3)

Maximize Profit = 3y11 + 8y12 + 9y13 + 9y21 + 24y22 + 9y23 subject to y11 + y12 + y13 ≤ 1 (xi can only take on one value) y21 + y22 + y13 ≤ 1 (y11 + 2y12 + 3y13) + (y21 + 2y22 + 3y23) ≤ 3 and yij are binary variables (for i = 1, 2; and j = 1, 2, 3)

9-13

b)

A1234567891011121314BCDEFGHIProfitX1X2ConstraintX1X2AssignmentX1X2110111139Value2824222201399333300Total3<=3Total1<=11<=1Total Profit27 9.19

c) Optimal Solution (x1,x2) = (1, 2). Profit = 27.

A12345678910111213BCDEFGHICostOA3OA1OB6OB0only ifAC6AC0<=1OA===AD5AD1<=1OA111BC4BC0<=0OBBD3BD0<=0OBCT3DT2Travel Path?CTDT01<=<=01AC or BCAD or BDTotal Cost10 OA or OBAC, AD, BC, or BDCt or DT111 The constraints in C11:E13 are mutually exclusive alternative (at each stage, exactly one arc is used). The constraints in D6:I8 are contingent decisions (a route can leave a node only if a route enters the node).

9-14

9.20

A1234567891011121314151617181920BCDEFGHIJKLMNTime (hours)LocationABCDEFGHI161243745Route5646758397111106Total onRoute111111111Total3>=>=>=>=>=>=>=>=>=111111111111111020Delivery Location on Route?1111111111111111113041Route56107081111Do Route?90100<=3Total Time (hours)12 9-15

9.21

A123456789101112131415161718192021222324252627282930BCDEFGHStationLocationTract 1Tract 15Tract 220Tract 315Tract 425Tract 510Avg. Fires/Day2StationLocationTract 1Tract 2Tract 3Tract 4Tract 5Response Time (minutes)Tract 2Tract 3Tract 4123020415102061515254251512131Tract 51525121053Tract 11040305020Average Total Response Time per DayTract 2Tract 3Tract 4Tract 512902045445107520181536157543025451215(Station? >=all five tracts)Tract 1>=0>=0>=0>=0>=11=18.5Tract Assigned to Station?Tract 2Tract 3Tract 4000000110000001111===111Tract 5000011=1StationLocationStation?Tract 10Tract 20Tract 31Tract 40Tract 51Total2=2Average Response Time (minutes) = The six equality constraints (total stations = 2; one station assigned to each tract) correspond to mutually exclusive alternatives. In addition, there are the following

contingent decision constraints: each tract can only be assigned to a station location if there is a station at that location (D21:D25 ≤ B21:B25; E21:E25 ≤ B21:B25; F21:F25 ≤ B21:B25; G21:G25 ≤ B21:B25; H21:H25 ≤ B21:B25).

9.22

a) Let xi = 1 if a station is located in tract i; 0 otherwise (for i = 1, 2, 3, 4, 5) Minimize Cost ($thousand) = 200x1 + 250x2 + 400x3 + 300x4 + 500x5 subject to x1 + x3 + x5 ≥ 1 (stations within 15 minutes of tract 1) x1 + x2 + x4 ≥ 1 (stations within 15 minutes of tract 2) x2 + x3 + x5 ≥ 1 (stations within 15 minutes of tract 3) x2 + x3 + x4 + x5 ≥ 1 (stations within 15 minutes of tract 4) x1 + x3 + x4 + x5 ≥ 1 (stations within 15 minutes of tract 5) and xi are binary variables (for i = 1, 2, 3, 4, 5).

9-16