A fuel truck with 4 compartments needs to supply 3 different types of gas to a customer. When demand is not filled, the company loses \$0.25 per gallon that is not delivered. How should the truck be loaded to minimize loss? Truck Specifications Comp. 1 Comp. 2 Comp. 3 Comp. 4 Size (gallons) 1200 800 1300 700 Loading of Compartments (1=yes, 0=no) Comp. 1 Comp. 2 Comp. 3 Comp. 4 Gas 1 0 0 0 0 Gas 2 0 0 0 0 Gas 3 0 0 0 0 Total 0 0 0 0 Amount (gallons) Comp. 1 Comp. 2 Comp. 3 Comp. 4 Total Demand Loss Gas 1 0 0 0 0 0 1800 \$450.00 Gas 2 0 0 0 0 0 1500 \$375.00 Gas 3 0 0 0 0 0 1000 \$250.00 Total Loss \$1,075.00 Maximum Amount (gallons) Comp. 1 Comp. 2 Comp. 3 Comp. 4 Gas 1 0 0 0 0 Gas 2 0 0 0 0 Gas 3 0 0 0 0 Problem A fuel truck needs to supply 3 different kinds of gas to a customer. When demand is not filled the company loses \$0.25 per gallon that is not delivered. The truck has 4 separate compartments of different size. How should the truck be loaded to minimize loss? Solution 1) The variables are the decisions to fill the compartments for each type of gas, and the amounts to be put in if the compartment is filled. In worksheet Knapsack, these are given the name Gallons_loaded and Loading_decisions. 2) The logical constraints are Gallons_loaded >= 0 via the Assume Non-Negative option Loading_decisions = binary Since there can only be one kind of gas in any compartment we have Total_decisions <= 1 The size limitations of the truck give Gallons_loaded <= Maximum_gallons We don't want to load more than needed. This gives Total_gallons <= Demand 3) The objective is to minimize the loss. This is given the name Total_loss. Remarks It is often possible to have different objectives in these types of problems. We might, for instance, want to minimize the wasted space in the truck in this example. Knapsack problems are characterized by a series of 0-1 integer variables with a single capacity constraint. If someone goes camping and his backpack can hold only a certain amount of weight, what items should the camper bring? He should try to optimize the value of the items while not exceeding the weight allowed by the backpack. There is a wide set of problems that fall into this category.