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. | |||||||