Operations Research

Dynamic Programming Exercise Guide

School of Commercial Engineering - Pontifical Catholic University of Valparaíso.
Professor: Pablo Diez B.

The breakdown of the exercises in this guide is as follows:

01 – 02: Critical path.

03 - 08: Load volume.
09 – 10: Number of employees.
11 – 12: Equipment replacement.
13 - 15 Inventory.
16 - 17 Investment.

1.- A traveler is currently in city A and needs to reach city J.

There are several intermediate cities (B, C, D, E, F, G, H, and I) between A and J.
they connect through certain paths, as shown in the following figure:

B 7 E 1 H
4 3
2 4
6
3 6
A 4 C 2 F J
4 3
3
4
4 1 3
D 5 G 3 I

The distances of the different paths (in hundreds of kilometers) are indicated on the
arcs of the figure. The traveler wishes to find the route that minimizes the distance to
travel between the cities A and J.

Solve using dynamic programming.

2.- I am an avid hiking enthusiast. Last summer, my friend DonFra and I
we took a 5-day trip to hike and camp in the mountain range of the
Coast Mountain Range that is in La Campana National Park. We decided
limit our walks to an area that includes three well-known mountains:
Cerro La Campana, Cerro Los Penitentes and Puntilla de Imán. Cerro La Campana
It has a trail of 6 kilometers from the base to the top. The trails
corresponding from the base to Los Penitentes and Puntilla de Imán are 4 and 5
kilometers, respectively.

The paths that connect the bases of the three mountains are of:

3 kilometers between the La Campana hills and Cerro Los Penitentes

2 kilometers between the Cerros Puntilla de Imán and Cerro Los Penitentes
5 kilometers between the La Campana Hills and Cerro Puntilla de Imán

We started the first day at the base of Cerro La Campana and returned to it.
place in 5 days, our goal was to walk as many kilometers as
we could. We also decided to climb exactly one mountain each day and
camping at the base of the mountain where we would make the ascent the next day.
In addition, we decided that we could not visit the same mountain two days in a row.
consecutive.

How do we schedule our walks?

3.- A hiker in the woods must pack three items: food, equipment for
first aid and clothing. The backpack has a capacity of 3 m.3Each unit of
food occupies 1 m3A first aid kit takes up a quarter of 1 m.3
and each piece of clothing takes up about half a meter3.

The hiker assigns priority weights 3, 4, and 5 to the food items, the backpack.
first aid and clothing, which means that clothing is the most valuable of the 3
articles. From experience, the hiker knows that they should carry at least one
unit of each item and no more than two first aid kits.

How much should the hiker carry for each item?

4.- A student must select 10 elective courses from four different ones.
departments and at least one course from each department. The ten courses are
they have assigned the four departments in a way that maximizes the
“conocimiento”. El estudiante mide el conocimiento en una escala de 100 puntos y
prepare the following table:

Dept / No Resources 1 2 3 4 5 6 >7

I 25 50 60 80 100 100 100
II 20 70 90 100 100 100 100
III 40 60 80 100 100 100 100
IV 10 20 30 40 50 60 70

How should the student select courses?

5. "A roof for Chile" is a wonderful charity organization that

build homes for families in need, using labor from
volunteers. A selected family can choose from three house sizes:
1000, 1100 and 1200 feet2Each house requires a certain number of volunteers for the
labor, depending on the size. The local organization of Rautén has received five
requests for the next six months.

The committee in charge assigns a rating to each application, based on various factors.
factors. A higher rating means more need. For the next six
In the months, the Rautén organization can count on a maximum of 23 volunteers.
The following data summarizes the ratings of the applications and the number
volunteers needed

Housing size request (feet2Qualification Number of volunteers required

1 1200 78 7
2 1000 64 4
3 1100 68 6
4 1000 62 5
5 1200 85 8

How many applications must the committee approve?

6.- 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
the reliability (probability of not failing) of the device can be improved
installing one or two backup units in each component. The following table
proporciona la confiabilidad (r), y el costo (c).

Component 1 Component 2 Component 3

Number of units in parallel r1 C1($) r2 C2($) r3 C3($)
1 0.6 1000 0.7 3000 0.5 2000
2 0.8 2000 0.8 5000 0.7 4000
3 0.9 3000 0.9 6000 0.9 5000

The total capital available for the construction of the device is $10,000.
How should the device be built?

Suggestion: the goal is to maximize reliability, r1, r2y r3of the device. This
it means that the decomposition of the objective function is of multiplication, plus
what a sum.

7.- LISTER ROSSEL is dedicated to improving healthcare in countries.

underdeveloped countries of the world. It has 5 medical brigades to assign to 3 of
these countries in order to improve healthcare, health education and
the training programs.
Then, the LISTER ROSSEL directory needs to determine how many brigades
must assign (if it does) to each of these countries to maximize the measure of
efficiency of the 5 brigades. The teams must remain as they are formed
therefore the number assigned to each country must be an integer.

The measure of efficiency will be taken in terms of additional years of life for
For a specific country, this measure is equal to the increase in the average
expected life in years, multiplied by its population). In the following table, it
and gives the estimates of these additional years of life per person (in multiples of
1000) for each country and for each possible number of assigned medical brigades.
Thousands of additional person-years of life
Number of medical brigades Country 1 Country 2 Country 3
0 0 0 0
1 45 20 50
2 70 45 70
3 90 75 80
4 105 110 100
5 120 150 130
It is desired to establish the allocation that maximizes the measure of efficiency.

A) Set up the recursive function for dynamic programming.

B) Obtain the optimal solution for LISTER ROSSEL.
8. A political campaign is in its final stage and the preliminary polls
They indicate that the election is close. One of the candidates has sufficient funds.
to purchase TV time for a total of five commercials during peak hours
audience in stations located in four different areas.

Based on the information from the preliminary surveys, an estimation was made.
of the additional votes that can be gained in the different areas of
dissemination according to the number of commercials that are purchased. These estimates are given
in the following table, in thousands of votes.

Number of salespeople Area 1 Area 2 Área 3 Área 4

0 0 0 0 0
1 4 6 5 3
2 7 8 9 7
3 9 10 11 12
4 12 11 10 14
5 15 12 9 16

Use dynamic programming to determine how the 5 salespeople should be distributed.

among the four areas in order to maximize the estimated number of votes gained.

9.- A road repair contractor estimates that the number of workers needed
During the next 5 weeks, there will be: 8, 4, 7, 8 and 2 workers, respectively. The
The excess of workers that remains in the workforce will cost $3000 for each
worker and for each week. Meanwhile, the new hires in any
per week incur a fixed cost of $4000 plus $2000 per worker and per week.
In addition, a severance payment of $100 is incurred for each dismissed worker.

Recommend to the contractor the effective number of workers for each of the 5
weeks, solving using dynamic programming.

10.-Alex Staffa organizes week-long tours in northern Chile. The agency

he has a contract to provide groups of tourists with 7, 4, 7, and 8 cars
rented, respectively, for the next 4 weeks.
Alex Staffa subcontracts to a local car distributor, which meets its
rental car needs. The dealer charges a rental fee
weekly of $220 per car, plus a fixed fee of $500 for any
car rental transaction (independent of the number of cars
that they are rented out.

Alex Staffa can choose not to return the rented cars at the end of the week,
in which case the agency will only be responsible for the weekly rent (US$ 220)
What is the best way for Alex Staffa to resolve car rental?
11.- A company needs to determine the replacement policy for a machine,
during the next 4 years (n = 4), that is until the beginning of year 5. the following
table provides the data of the problem. The company requires that a machine of
six years is replaced. The cost of a new machine is UF$ 1000.
The determination of: the utility of the machine, the operating cost of the machine
and the salvage value of the machine depends on the t years of age that it has
machine. The relevant information is shown in the following table:

Edad, t(años) Utilidad, r(t) Costo de operación, r(t) Valor de rescate, s(t)
0 US$ 200 UF$ 2
1 UF$ 190 UF$ 6 US$ 800
2 UF$ 185 UF$ 12 UF$ 600
3 UF$ 172 UF$ 15 UF$ 500
4 UF$ 155 UF$ 17 UF$ 300
5 UF$ 140 UF$ 18 UF$ 100
6 UF$ 122 UF$ 22 USD 50

Develop the network of feasible values for the age of the machine in each year and
find the optimal solution for the equipment replacement model, if:

A) The machine is 2 years old at the beginning of year 1.

B) The machine is 1 year old at the beginning of year 1.
C) The machine is purchased new at the beginning of year 1.

My 13-year-old son has a business that consists of mowing lawns.

10 clients. For each client, mow the lawn 3 times a year, which earns you
$50 for each mowing. Just paid $200 for a new mower. The cost of
maintenance and operation of the mower is $120 for the first year of service, the
which increases by 20% per year and so on.

A one-year-old mower has a resale value of $150 that decreases by 10%.

annually. My son, who plans to keep his business until he turns 16 years old,
thinks it is more economical to buy a new mower every two years. It bases its
decision based on the fact that the price of a new mower will only increase a
10% per year.

Is their decision justified?

13.-Given the following inventory model for 4 periods:

Demand Costo de preparación Costo de Almacenamiento

Period i Di (units) Ki ($) hi ($)
1 5 5 1
2 2 7 1
3 3 9 1
4 3 7 1

The production cost per unit is $1 for the first 6 units and $2 for
the additional units.

Find the optimal solution using dynamic programming.

14.-Consider the inventory situation of 3 periods presented in the table. The

demand occurs in discrete demands and the initial inventory is X11 unit.

Demand Costo de Preparación Costo de Almacenamiento

Period i Di (units) Ki ($) hi ($)
1 3 3 1
2 2 7 3
3 4 6 2

The production cost per unit is $10 for the first 3 units and $20
for each additional unit.

A) Find the optimal solution using dynamic programming.

For each of the two following cases (cases C and D), determine the ranges.
feasible for Z1, Z2, X1, X2y X3:

B) X1= 0, D1= 5, D2= 4, D3= 5.

15.-LOCOVICH builds commercial airplanes for various airlines around the
world. The final stage of the production process consists of manufacturing the engines.
of the turbine and install them (extremely quick operation) in the structure of the airplane
finished. The company has several work contracts to deliver a large
number of planes in the near future, and at this moment it must be scheduled the
turbine engine production over the next 4 months.

In the second column of the following table, the number of engines is indicated.
they must be ready for installation in order to meet the delivery dates
contracted. Thus, the cumulative number of engines that must be produced by the end
For months 1, 2, 3, and 4, it must be at least 10, 25, 50, and 70, respectively.

My Facilities Production Unit cost Unit cost

scheduled maximum of production for storage
1 10 25 1.08 0,015
2 15 35 1.11 0.015
3 25 30 1,10 0.015
4 20 10 1.13

The facilities available for producing the engines vary according to others.
production, maintenance, and renewal programs during this period. The
monthly differences that result in the maximum number that can be
produce and the unit cost of production (in millions of $) are given in the third and
fourth column of the preceding table.

Given the variations in production costs, it might be worth producing

some engines one month or two before their installation date and it is being studied
this possibility. The drawback is that these engines will have to be stored until
that they be installed (the structure of the planes will not be ready beforehand). The cost of
Storage for each engine is $15,000 each month (includes the interest on the)
invested capital), as shown in the last column of the previous table.

Assuming that the produced quantities must be multiples of 5, solve

through dynamic programming.

16.-You wish to invest the following amounts in the next 4 years P 1= 5000, P2
= 4000, P3= 3000 and P4= 2000. You can invest in two banks. The first bank pays
an annual compound interest rate of 8.5% and the percentages of the bonuses
over the next four years are 1.8; 1.7; 2.1 and 2.5; respectively. The rate
the compound annual interest offered by the second bank is 8%, but its
The bonus is 0.5% higher than that of the first bank.

The goal is to maximize the accumulated capital at the end of 4 years.

Solve using dynamic programming

17.-You wish to invest the following amounts over the next 4 years: P 1= 4000, P2
= 3000, P3= 2500 and P4= 1500. You can invest in two banks. The first bank pays
an annual compounded interest rate of 6% and the percentages of the bonuses
during the next four years are 1.6; 1.8; 2.0 and 2.2; respectively. The rate
the compounded annual interest offered by the second bank is 5.5%, but its
the bonus is 0.5% higher than that of the first bank.

Solve this investment problem using dynamic programming.