8. (a) (The Knapsack Problem) A backpacker's knapsack has a volume of V in. and can...

Transcribed Image Text:

8. (a) (The Knapsack Problem) A backpacker's knapsack has a volume of V in. and can hold up to W lb of gear. The backpacker has a choice of n items to carry in it, with the ith item requiring a; in.3 of space, weighing w; lb, and providing c; units of value for the trip. What items should be taken in the knapsack? (b) Refine part (a) to include the following considerations: Item 1, a can of tuna fish, Item 2, a can of corn, and Item 3, a can of stew, have no value unless Item 4, the can opener, is taken; and only one snack, either Item 5, potato chips (light but bulky), or Item 6, unpopped popcorn (small but heavy), is to go. Of course Items 2, 3, and 6 all use Item 7, the cooking pot. 9. A road construction firm seeks to assign its force optimally over the next 28- week period. They can be assigned to any combination of the following: For any number of 10-week periods, working for the state, and earning a profit of $3200/week. For any number of 6-week periods, working for the county, and earning a profit of $2900/week. For any number of 3-week periods, working for a private land developer, and earning $2750/week. For any number of weeks, working on parking lot construction, and earning $2550/week. However, if the firm does any work at all for either the state or county (or both), it is expected to contribute $7500 to the campaign fund of a certain anonymous political figure. 15. Maximize 3x1 +5x2+7x3 subject to 5x1+4x2+2x3300,x1, x2, x3 0, and (x1+x3100 x1x20 % } or { 2x1-4x2+5x3250 X2-2x350 } Solve the following using the Cutting Plane Algorithm. (a) Minimize x - x2 subject to 3x1 + 4x2 6 - x1 x2 1 x1,x20 and integral (c) Maximize 2x1 -4x2+x3 subject to x1 - x2 <12 2x2 + 3x3 28 X1, X2, X30 and integral 8. (a) (The Knapsack Problem) A backpacker's knapsack has a volume of V in. and can hold up to W lb of gear. The backpacker has a choice of n items to carry in it, with the ith item requiring a; in.3 of space, weighing w; lb, and providing c; units of value for the trip. What items should be taken in the knapsack? (b) Refine part (a) to include the following considerations: Item 1, a can of tuna fish, Item 2, a can of corn, and Item 3, a can of stew, have no value unless Item 4, the can opener, is taken; and only one snack, either Item 5, potato chips (light but bulky), or Item 6, unpopped popcorn (small but heavy), is to go. Of course Items 2, 3, and 6 all use Item 7, the cooking pot. 9. A road construction firm seeks to assign its force optimally over the next 28- week period. They can be assigned to any combination of the following: For any number of 10-week periods, working for the state, and earning a profit of $3200/week. For any number of 6-week periods, working for the county, and earning a profit of $2900/week. For any number of 3-week periods, working for a private land developer, and earning $2750/week. For any number of weeks, working on parking lot construction, and earning $2550/week. However, if the firm does any work at all for either the state or county (or both), it is expected to contribute $7500 to the campaign fund of a certain anonymous political figure. 15. Maximize 3x1 +5x2+7x3 subject to 5x1+4x2+2x3300,x1, x2, x3 0, and (x1+x3100 x1x20 % } or { 2x1-4x2+5x3250 X2-2x350 } Solve the following using the Cutting Plane Algorithm. (a) Minimize x - x2 subject to 3x1 + 4x2 6 - x1 x2 1 x1,x20 and integral (c) Maximize 2x1 -4x2+x3 subject to x1 - x2 <12 2x2 + 3x3 28 X1, X2, X30 and integral