9.3 a) Optimal solution: (x1, x2) = (2, 3). Profit = 13.
b) The optimal solution to the LP-relaxation is (x1, x2) = (2.6, 1.6). Profit = 14.6.
Rounded to the nearest integer, (x1, x2) = (3, 2). This is not feasible since it violates the third constraint.
Rounded Solution Feasible? (3,2) No (3,1) No (2,2) Yes (2,1) Yes
None of these is optimal for the integer programming model. Two are not feasible and
the other two have lower values of Profit.
Constraint Violated 3rd 2nd & 3rd - - P - - 12 11 9-5
9.4 a) Optimal solution: (x1, x2) = (2, 3). Profit = 680.
b) The optimal solution to the LP-relaxation is (x1, x2) = (2.67, 1.33). Profit = 693.33.
Rounded to the nearest integer, (x1, x2) = (3, 1). This is not feasible since it violates the second and third constraint.
Rounded Solution (3,1) (3,2) (2,2) (2,1)
None of these is optimal for the integer programming model. Two are not feasible and the other two have lower values of Profit.
Feasible? No No Yes Yes Constraint Violated 2nd & 3rd 2nd - - P - - 600 520
9-6
9.5 a)
A123456789101112BCDEFGLong-RangeJetsAnnual Profit ($million)4.2BudgetMaintenance CapacityPilot CrewsMedium-RangeJets3Short-RangeJets2.3ResourceUsed1498<=39.333<=30<=ResourceAvailable15004030Total AnnualProfit ($million)95.6 Resource Used Per Unit Produced6750351.6671.3331111Long-RangeJets14Medium-RangeJets0Short-RangeJets16Purchase
b) Let L = the number of long-range jets to purchase
M = the number of medium-range jets to purchase S = the number of short-range jets to purchase Maximize Annual Profit ($millions) = 4.2L + 3M + 2.3S subject to 67L + 50M + 35S ≤ 1,500 ($million) (5/3)L + (4/3)M + S ≤ 40 (maintenance capacity) L + M + S ≤ 30 (pilot crews) and L ≥ 0, M ≥ 0, S ≥ 0 L, M, S are integers.
a) Let xij = tons of gravel hauled from pit i to site j (for i = N, S; j = 1, 2, 3) yij = the number of trucks hauling from pit i to site j (for i = N, S; j = 1, 2, 3) Minimize Cost = $130xN1 + $160xN2 + $150xN3 + $180xS1 + $150xS2 + $160xS3 + $50yN1 + $50yN2 + $50yN3 + $50yS1 + $50yS2 + $50yS3 subject to xN1 + xN2 + xN3 ≤ 18 tons (supply at North Pit) xS1 + xS2 + xS3 ≤ 14 tons (supply at South Pit) xN1 + xS1 = 10 tons (demand at Site 1) xN2 + xS2 = 5 tons (demand at Site 2) xN3 + xS3 = 10 tons (demand at Site 3) xij ≤ 5yij (for i = N, S; j = 1, 2, 3) (max 5 tons per truck) and xij ≥ 0, yij ≥ 0, yij are integers (for i = N, S; j = 1, 2, 3)
9.6
9-7
b)
A123456789101112131415161718192021222324252627BCDEFGHHauling CostPitNorthSouth1$30$60110010=10Site2$60$30Site2055=53$50$4035510=10Priceper Ton$100$120Total1510Supply1814Total CostGravel HauledNorthSouthTotal ReceivedDemandPit<=<=Fixed Cost per Truck$50.00Capacity per Truck (tons)5Trucks UsedPitCapacityPitNorthSouth1100NorthSouth120Site201Site205311355Hauling CostPurchase CostFixed Truck CostTotal Cost$900$2,700$250$3,850(Gravel Hauled <= Capacity) 9.7
a) Let FLA = 1 if build a factory in Los Angeles; 0 otherwise FSF = 1 if build a factory in San Francisco; 0 otherwise FSD = 1 if build a factory in San Diego; 0 otherwise WLA = 1 if build a warehouse in Los Angeles; 0 otherwise WSF = 1 if build a warehouse in San Francisco; 0 otherwise WSD = 1 if build a warehouse in San Diego; 0 otherwise
Maximize NPV ($million) = 9FLA + 5FSF + 7FSD + 6WLA + 4WSF + 5WSD subject to 6FLA + 3FSF + 4FSD + 5WLA + 2WSF + 3WSD ≤ $10 million (Capital) WLA + WSF + WSD ≤ 1 warehouse WLA ≤ FLA (warehouse only if factory) WSF ≤ FSF WSD ≤ FSD
and FLA, FSF, FSD, WLA, WSF, WSD are binary variables.
9-8
