Home | | **Operations Research An Introduction** | | **Resource Management Techniques** | Knapsack/Fly-Away/Cargo Loading Model- Dynamic Programming(DP) Applications

The knapsack model classically deals with the situation in which a soldier (or a hiker) must decide on the most valuable items to carry in a backpack.

Knapsack/Fly-Away/Cargo-Loading
Model

The
knapsack model classically deals with the situation in which a soldier (or a
hiker) must decide on the most valuable items to carry in a backpack. The
problem paraphrases a general resource allocation model in which a single
limited resource is assigned to a number of alternatives (e.g., limited funds
assigned to projects) with the objective of maximizing the total return.

Before
presenting the DP model, we remark that the *knapsack*
problem is also known in the literature as the *fly-away kit* problem, in which a jet pilot must determine the most
valuable (emergency) items to take aboard a jet; and the *cargo-loading* prob-lem, in which a vessel with limited volume or
weight capacity is loaded with the most valuable cargo items. It appears that the three names
were coined to ensure equal rep-resentation of three branches of the armed
forces: Air Force, Army, and Navy!

The
(backward) recursive equation is developed for the general problem of an n-item
*W-Ib*
knapsack. Let *m _{i}* be the
number of units of item

**Step 2.** Express *x _{i+1}* as a function of

**Example
10.3-1**

A 4-ton
vessel can be loaded with one or more of three items. The following table gives
the unit weight, *w _{i},* in tons and the unit revenue in
thousands of dollars,

Because
the unit weights *w _{i}* and the maximum weight

**Stage 3. **The exact weight to be allocated
to stage 3 (item 3) is not known in advance, but can assume one of the values
0,1, ... , and 4 (because *W* = 4
tons). The states *x _{3}* = and

Given *w _{3}* = 1 ton per unit, the maximum number of units
of item 3 that can be loaded is

4/l = 4, which
means that the possible values of
*m _{3}* are 0,
1,2,3, and 4. An alternative

The
optimum solution is determined in the following manner: Given *W* = 4 tons,
from stage 1, *x _{1}* = 4 gives the optimum alternative
m

In the
table for stage 1, we actually need to obtain the optimum for x_{l} = 4 only because this is the last
stage to be considered. However, the computations for x_{1} = 0, 1, 2, and 3 are induded to
allow carrying out *sensitivity analysis.*
For example, what happens if the vessel capacity is 3 tons in place of 4 tons?
The new optimum solution can be determined as

**Remarks. **The cargo-loading example
represents a typical *resource allocation*
model in which a limited resource is apportioned among a finite number of
(economic) activities. The objective maximizes an associated return function.
In such models, the definition of the state at each stage will be similar to
the definition given for the cargo-loading model. Namely, the state at stage *i* is the total resource amount allocated
to stages *i,* *i* + 1, ... , and *n.*

**Excel
moment**

The
nature of dynamic programming computations makes it impossible to develop a
general computer code that can handle all DP problems. Perhaps this explains
the persistent absence of commercial DP software.

In this
section, we present a Excel-based algorithm for handling a subclass of DP
problems: the single-constraint knapsack problem (file Knapsack.xls). The algorithm
is not data specific and can handle problems in this category with 10 alternatives
or less.

Figure
10.4 shows the starting screen of the knapsack (backward) DP model. The screen
is divided into two sections: The right section (columns Q:V) is used to summarize

the
output solution. In the left section (columns A:P), rows 3,4, and 6 provide the
input data for the current stage, and rows 7 and down are reserved for stage
computations. The input data symbols correspond to the mathematical notation in
the DP model, and are self-explanatory. To fit the spreadsheet conveniently on
one screen, the maximum feasible value for alternative *m _{i}* at stage

Figure
10.5 shows the stage computations generated by the algorithm for Example
10.3-1. The computations are carried out one stage at a time, and the user
provides the basic data that drive each stage. Engaging you in this manner will
enhance your understanding of the computational details in DP

Starting
with stage 3, and using the notation and data in Example 10.3-1, the input
cells are updated as the following list shows:

Note that
the feasible values of *m _{3}*
are 0, 1, ... , and [W/w

As stage
3 data are entered and verified, the spreadsheet will "come alive"
and will generate all the necessary computations of the stage (columns B
through P) automatically. The value -1111111 is used to indicate that the
corresponding entry is not feasible. The optimum solution (*f*_{3}, *m _{3})*
for the stage is given in columns 0 and P Column A provides the values of

Now that
stage 3 calculations are at hand, take the following steps to create a *permanent *record of the optimal solution
of the current stage and to prepare the spread-sheet for next stage
calculations:

**Step 1.** Copy the x_{3}-values,
C9:C13, and paste them in Q5:Q9 in the optimum solution summary section. Next,
copy the (f_{3}, m_{3})-values, 09:P13, and paste them in
R5:S9. Remember that you need to paste values only, which requires selecting *Paste Special* from Edit menu and *Values* from the dialogue box.

**Step 2.** Copy
the *f*_{3}-values in R5:R9 and
paste them in A9:A13 (you do *not* need
*Paste Special *in this step).

**Step 3. **Change cell C4 to 2 and enter the
new values of *w _{2},*

Step 2
places *f _{i+1}(x_{i}* -

Once
stage 2 computations are available, you can prepare the screen for stage 1 in a
similar manner. When stage 1 is complete, the optimum solution summary can be
used to read the solution, as was explained in Example 10.3-1. Note that the
organization of the output solution summary area (right section of the screen,
columns Q:V) is free-formatted and you can organize its contents in any
convenient manner you desire.

**PROBLEM SET 10.3A**^{}

1. In Example 10.3-1, determine the optimum solution, assuming that the
maximum weight capacity of the vessel is 2 tons then 5 tons.

2. Solve the cargo-loading problem of Example 10.3-1 for each of the
following sets of data:

3. In the cargo-loading model of Example 10.3-1, suppose that the
revenue per item includes a constant amount that is realized only if the item
is chosen, as the following table shows:

Find the optimal solution using DP. *(Hint:*
You can use the Excel file excelSetupKnapsack.xls to check your calculations.)

4. A
wilderness hiker must pack three items: food, first-aid kits, and clothes. The
backpack has a capacity of 3 ft^{3}. Each unit of food takes 1 ft3. . A
first-aid kit occupies V4 ft3 and each piece of cloth takes about 1/_{2}ft3. The hiker assigns the priority weights 3,4, and 5 to food, first aid, and
clothes, which means that clothes are the most valuable of the three items.
From experience, the hiker must take at least one unit of each item and no more
than two first-aid kits. How many of each item should the hiker take?

*5. A
student must select 10 electives from four different departments, with at least
one course from each department. The 10 courses are allocated to the four
departments in a manner that maximizes "knowledge." The student
measures knowledge on a l00-point scale and comes up with the following chart:

How
should the student select the courses?

6. I have
a small backyard garden that measures 10 X 20 feet.
This spring I plan to plant three types of vegetables: tomatoes, green beans,
and corn. The garden is organized in 10-foot ro\ys. The corn and tomatoes rows
are 2 feet wide, and the beans rows are 3 feet wide. I like tomatoes the most
and beans the least, and on a scale of 1 to 10, I would assign 10 to tomatoes,
7 to corn, and 3 to beans. Regardless of my preferences, my wife insists that I
plant at least one row of green beans and no more than two rows of toma-toes.
How many rows of each vegetable should I plant?

*7.
Habitat for Humanity is a wonderful charity organization that builds homes for
needy fami-lies using volunteer labor. An eligible family can chose from three
home sizes: 1000, 1100, and 1200 *ft ^{2}.* Each
size house requires a certain number of labor volunteers. The Fayetteville
chapter has received five applications for the upcoming 6 months. The
commit-tee in charge assigns a score to each application based on several
factors. A higher score sig-nifies more need. For the next 6 months, the
Fayetteville chapter can count on a maximum of 23 volunteers. The following
data summarize the scores for the applications and the required number of
volunteers. Which applications should the committee approve?

8. Sheriff
Bassam is up for reelection in Washington county. The funds available for the
campaign are about $10,000. Although the reelection committee would like to
launch the campaign in all five precincts of the county, limited funds dictate
otherwise. The following table lists the voting population and the amount of
funds needed to launch an effective campaign in each precinct. The choice for
each precinct is to receive either all allotted funds or none. How should the
funds be allocated?

9. An
electronic device consists of three components. The three components are in
series so that the failure of one component causes the failure of the device.
The reliability (probability of no failure) of the device can be improved by
installing one or two standby units in each component. The following table
charts the reliability, *r,* and the cost, *c.* The total capital available for the
construction of the device is $10,000. How **10.3**
should the device be constructed? *(Hint:*
The objective is to maximize the reliability, *r _{1}r_{2}r_{3}, *of the
device. This means that the decomposition of the objective function is
multi-plicative rather than additive.)

10. Solve
the following model by DP:

*(Hint: *This problem is similar to
Problem 9, except that the variables,* y _{i},
*are continuous.)

11. Solve
the following problem by DP:

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.