Partial Loading (Knapsack Problem) |
|
|
|
|
| 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. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
