INVOP2 Deterministic Dynamic Programming

PROBLEM 1 (Model: Load Volume)

A 4-ton boat is loaded with one or more of three items. The table below shows the
unit weightnin tons and the income per unitnin thousands of $, for the article. How do you
Should the ship be loaded to maximize total revenue?

Articlen in
1 2 31
2 3 47
3 1 14

Keep in mind that the ship can load these items in any order, also, as the
The unit weight and the permissible weight are integers; the variables must only have integer values.

Solution:
Stage: Each type of item refers to a stage.
Status: Availability regarding the ship's capacity
Decision: How many units of each type of item to take
Recursive function: Represents the total income that is to be maximized.

Stage 3
f3(s3,x3=14x3 Optimal solution
s3 x3=0 x3=1 x3=2 x3=3 x3=4 f3*(s3) x3*
0 14(0)=0 - - - - 0 0
1 14(0)=014(1)=14 - - - 14 1
2 14(0)=014(1)=1414(2)=28 - - 28 2
3 14(0)=014(1)=1414(2)=2814(3)=42 - 42 3
4 14(0)=014(1)=1414(2)=2814(3)=4214(4)=56 56 4
s3=0; means that the boat is full, zero availability.
s3=4; it means that the ship is empty, availability 4 tons.

Stage 2
f2(s2,x2=47x2+f3(s* 2-3x2) Optimal solution
s2 x2=0 x2=1 f2*(s2) x2*
0 47(0)+0=0 - 0 0
1 47(0)+14=14 - 14 0
2 47(0)+28=28 - 28 0
3 47(0)+42=4247(1)+0=47 47 1
4 47(0)+56=5647(1)+14=61 61 1

Stage 1
f1(s1,x1=31x1+f2(s*1-2x1) Optimal solution
s1 x1=0 x1=1 x1=2 f1*(s1) x1*
0 31(0)+0=0 - - 0 0
1 31(0)+14=14 - - 14 0
2 31(0)+28=2831(1)+0=31 - 31 1
3 31(0)+47=4731(1)+14=45 - 47 0
4 31(0)+61=6131(1)+28=5931(2)+0=62 62 2
 To obtain the optimal solution, it is noted that the maximum income generated in stage 1, that is
$62 thousand is produced when it is decided to carry 2 units of item 1.

PROBLEM 2 (Model: Workforce)

A construction contractor estimates that the workforce required over the next 5 weeks
will be 5, 7, 8, 4, and 6 workers, respectively. The excess labor that is kept will be
it will cost $300 per worker weekly, and the new hiring in any week will have a
fixed cost of $400 plus $200 per worker per week. Suggest a hiring plan for
minimize the costs incurred.

Solution:
Seaxnthe labor assigned to each week.
Searnthe labor required for each week, then:1=5,r2=7,r3=8,r4=4yr5=6

Excess labor cost: 300(xn–r n) when:xn>rn

Hiring cost: 400 + 200(xn–sn) when:xn >sn

Stage 5 (r5 = 6)
f5(s5,x5=300(x5- 6)+[400+200(x5-s5Optimal solution
s5 x5=6 f5*(s5) x5*
4 300(0)+[400+200(2)]=800 800 6
5 300(0)+[400+200(1)]=600 600 6
6 300(0)+[0]=0 0 6

Stage 4 (r4= 4)
f4(s4,x4=300(x4- 4)+[400+200(x4-s4)]+f5(x4*) Optimal solution
s4 x4=4 x4=5 x4=6 f4*(s4) x4*
8 300(0)+[0]+800=800300(1)+[0]+600=900300(2)+[0]+0=600 600 6

Stage 3 (r3= 8)
f3(s3,x3=300(x3- 8)+[400+200(x3-s3)]+f4(x3*Optimal solution
s3 x3=8 f3*(s3) x3*
7 300(0)+[400+200(1)]+600=1200 1200 8
8 300(0)+[0]+600=600 600 8

Stage 2 (r2= 7)
f2(s2,x2)=300(x2- 7)+[400+200(x2-s2)]+f3(x*2) Optimal solution
s2 x2=7 x2=8 f2*(s2) x2*
5 300(0)+[400+200(2)]+1200=2000300(1)+[400+200(3)]+600=1900 1900 8
6 300(0)+[400+200(1)]+1200=1800300(1)+[400+200(2)]+600=1700 1700 8
7 300(0)+[0]+1200=1200 300(1)+[400+200(1)]+600=1500 1200 7
8 300(0)+[0]+1200=1200 300(1)+[0]+600=900 900 8

Step 1 (r1= 5)
f1(s1,x1=300(x1 - 5)+[400+200(x1-s1)]+f2(x*1) Solution
optimal
s1 x15 x1 6 x1=7 x1=8 f1*(s1) x1 *
300(0)+[400+200(5)]300(1)+[400+200(6)]300(2)+[400+200(7)]300(3)+[400+200(8)]
0 3300 5
["+1900=3300","+1700=3600","+1200=3600","+900=3800"]

PROBLEMA 3 (Modelo: Reposición de equipo)

In the course of the following four years, during a certain production process, it is desired to know
when to replace a machine or continue keeping it in order to find the most
beneficial for the company. Initially, there is a machine that is three years old
trabajando en la producción. Los datos respecto a la maquina los obtenemos en la siguiente tabla:

t I(t) C(t) R(t)

Time Income Cost of Value of
(years) (miles de $) operación ( $ ) Recuperación ( $ )
0 20000 200 -
1 19000 600 80000
2 18500 1200 60000
3 17200 1500 50000
4 15500 1700 30000
5 14000 1800 10000
6 12200 2200 5000

Consider that:
The cost of a new machine is $100,000.
Any machine that is 6 years old must be replaced.
At the end of the planning horizon, the machine must be sold.

Since this is the final stage, the machine must be sold, and there are no further contributions.
The state of stage n is the age t of the machine at the beginning of year n, then:

Stage 4
t Conserve Replace Optimal solution
s4 I(t)-C(t)+R(t +1) I(0) + R(t) + R(1) - 100000 - C(0) f4*(s4) x4*
1 19000-600+60000=78400 20000+80000+80000-100000-200=79800 79800 R
2 18500-1200+50000=67300 20000+60000+80000-100000-200=59800 67300 C
3 17200+1500+30000=45700 20000+50000+80000-100000-200=49800 49800 R
6 It must be replaced 20000+5000+80000-100000-200=4800 4800 R

Stage 3
t Conserve Replace Optimal solution
*
s3 I(t) - C(t) + f4(t + 1) I(0) + R(t) - 100000 - C(0) + f4(1) f3*(s3) x3*
 1 19000-600+67300=85700 20000+80000-100000-200+79800=79600 85700 C
2 18500-1200+49800=67100 20000+60000-100000-200+79800=59600 67100 C
5 14000-1800+4800=17000 20000+10000-100000-200+79800=9600 17000 C

Stage 2
t Conserve Replace Optimal solution
*
s2 I(t)-C(t)+f3(t +1) I(0) + R(t) - 100000 - C(0) + f3(1) f2*(s2) x2*
1 19000-600+67100=85500 20000 + 80000 - 100000 - 200 + 85700 = 8550085500 C o R
4 15500-1700+17000=30800 20000+30000-100000-200+85700=3550035500 R

Stage 1
t Conserve Replace Optimal solution
*
s1 I(t)-C(t)+f2(t +1) I(0) + R(t) - 100000 - C(0) + f2(1) f1*(s1) x1*
3 17200-1500+35500=51200 20000+50000-100000-200+85500=55300 55300 R

PROBLEM 4
A company requires 28, 30, 25, 29, and 20 workers for the next 5 years respectively.
Currently, there are 30 employees in the company. Each worker earns 16,000 soles a year. To
At the beginning of each year, workers can be hired or fired. It costs 1000 soles to hire one.
worker and 15000 soles to dismiss him, due to the insurance and benefits that must be paid. For
how exhausting work is, every year 3 workers resign (who do not earn 15000)
dismissal soles). By using dynamic programming, find the optimal policy defining
the stages, states, and decision variables; also explain the recursive function. Keep in mind
that, if it were economical, it would be ideal to have the exact number of workers needed in each
week; furthermore, the company tries as much as possible to avoid the costs of hiring or firing.

Solution:
rnRequirement for year n
xnWorkers assigned in year n
Stage: year
Status: workers remaining at the beginning of the current period.
fn(sn,xn)= min{16000(xn) + 1000(xn-sn) + 15000(sn-xn) +fn+1(sn+1) } or also
fn(sn,xn)= min{16000(xn) + 1000(xn-sn) + 15000(sn-xn) + fn+1(xn-3) }
considering that: 1000(xn-sn); xn>sny15000(sn-xn); sn>xn

For practicality, the costs in the tables are in thousands of soles.

Stage 5 (r5= 20)

f5(s5,x5)=16000(x5) +15000(s5-x5Optimal solution
s5
x5=20 f5*(s5) x5*
29-3=26 16(20)+15(6)=410 410 20

Stage 4 (r4= 29)

f4(s4,x4)=16000(x4+1000(x4-s4) + f5(x4-3) Optimal solution
s4
x4 =29 f4*(s4) x4*
25-3=22 16(22)+1(7)+410 =769 769 29
27-3=24 16(24)+1(5)+410=799 799 29

Stage 3 (r3= 25)

f3(s3,x3=16000(x3) +15000(s3-x3)+f4(x3-3) Optimal solution
s3
x2=25 x2=27 f3*(s3) x3*
 30-3=27 16(25)+15(2)+769=1199 16(27)+ 799=1231 1199 25

Stage 2 (r2= 30)

f2(s2,x2)=16000(x2+1000(x2-s2) + f3(x2-3) Optimal solution
s2
x2=30 f2*(s2) x2*
28-3=25 16(30)+1(5)+1199 =1754 1754 30
30-3=27 16(30)+1(3)+1199 =1724 1724 30

Stage 11= 28)

f1(s1,x1=16000(x1+15000(s1-x1) + f2(x1-3) Optimal solution
s1
x1=28 x1=30 f1*(s1) x1*
30 16(28)+15(2)+1754=2232 16(30)+1724=2204 2204 30

PROBLEM 5
A company needs to have a machine that will operate for the next 5 years. Currently
They have a new machine. The company could keep the machine or sell it at the beginning of each
year and buy a new one. A new machine costs 5000 dollars. The income obtained with the
machine, the maintenance cost and the salvage value that can be obtained by selling it to
the end of the year, depends on the age of the machine (see table). A machine can be used up to
a maximum of three years old.

Use dynamic programming to maximize the net utility earned over the six years.
next.

YEAR 0-1 YEAR 1-2 YEAR 2-3

Ingresos ($) 4500 3000 1500
Operating costs ($) 500 700 1100
Salvage value at the end of the year 3000 1800 500

STAGES: Years
STATES: Age of the machine
ALTERNATIVAS: Conservar, Reemplazar

Since this is the last stage, the machine must be sold, and there are no contributions.
posteriors.
The state of stage n is the age t of the machine at the beginning of year n, then:

Stage 6
t Conserve Replace Optimal solution
s6 I(t)-C(t)+R(t +1) I(0)+R(t)+R(1)- 5000 -C(0) f6*(s6) x6*
1 3000-700+1800=4100 4500+3000+3000-5000-500=5000 5000 R
 2 1500-1100+500=900 4500+1800+3000-5000-500=3800 3800 R
3 It should be replaced 4500+500+3000-5000-500=2500 2500 R

Stage 5
t Conserve Replace Optimal solution
s5 *
I(t)-C(t)+f6(t +1) I(0) + R(t) - 5000 - C(0) + f6(1) *
f5*(s5) x5*
1 3000-700+3800=4100 4500+3000-5000-500+5000=7000 7000 R
2 1500-1100+2500=2900 4500+1800-5000-500+5000=5800 5800 R
3 It must be replaced 4500+500-5000-500+5000=4500 4500 R

Stage 4
t Conserve Replace Optimal solution
s4 *
I(t)-C(t)+f5(t +1) I(0) + R(t) - 5000 - C(0) + f5(1) *
f4*(s4) x4*
1 3000-700+5800=8100 4500+3000-5000-500+7000=9000 9000 R
2 1500-1100+4500=4900 4500+1800-5000-500+7000=7800 7800 R
3 It must be replaced 4500+500-5000-500+7000=6500 6500 R

Stage 3
t Conserve Replace Optimal solution
s3 *
I(t)-C(t)+f4(t +1) I(0) + R(t) - 5000 - C(0) + f4(1) *
f3*(s3) x3*
1 3000-700+7800=10100 4500+3000-5000-500+9000=11000 11000 R
2 1500-1100+6500=6900 4500+1800-5000-500+9000=9800 9800 R

Stage 2
t Conserve Replace Optimal solution
s2 *
I(t)-C(t)+f3(t +1) I(0)+R(t)- 5000 -C(0)+f3(1) * f2*(s2) x2*
1 3000-700+9800=12100 4500+3000-5000-500+11000=13000 13000 R

Stage 1
t To conserve Replace Optimal solution
s1 *
I(t)-C(t)+f2(t +1) I(0) + R(t) - 5000 - C(0) + f2(1) *
f1*(s1) x1*
0 3000-700+13000=15300 - 15300 C

PROBLEM 6
A company has the following demand data for its product:
My Demand
1 1
2 3
3 2
4 4
How many units should be produced in the month? Knowing that:
During the month that some units are produced, a fixed cost of $30 is incurred.
The variable cost is $10 per unit manufactured.
At the end of each month, a storage cost of $5 is generated for each unit.
The capacity limitations allow a maximum production of 5 units.
The size of the warehouse restricts a maximum ending inventory of 4 units each month.
There are 0 units available at the beginning of the first month.

Features:
The demand for each month is known at the beginning of month 1.
It is necessary to determine how many units should be produced considering that the capacity of
Manufacturing is limited.
The demand for each period must be met on time with the current inventory or production.
During each period where production takes place, a fixed cost is generated, as well as a cost
variable per unit.
There is limited storage capacity. A storage cost per unit is incurred.
to the final inventory of each period.
The objective is to minimize the total cost by meeting the demand of each period.

Periodic review model: The inventory is known at the end of each period, and the decision is made.
about production.

Solution:
Sean: xn the level of production in the month n
ynthe initial inventory in the month n
dnthe demand in the month n

CP(xnthe production cost of xnunits, CP(xn=30+10xn

What I have in store for next month will be:
what I had in inventory + what I produced - the demand for that month
that is to say: yi+1= yi+ xi- di
so: CI(yi+1)=5(yi+ xi- di)

Recursive function: Minimum cost of meeting demands fn(sn,xn) = min

{CI(yi+1) + CP(xn) + fn+1(sn+1)}
Stage: Every month
Status: Initial inventory

Stage 4 (demand=4)
f4(s4,x4)=30+10x4 Optimal solution
s4
x4= 0 x4= 1 x4= 2 x4= 3 x44 f4*(s4) x4*
0 - - - - 30+40 70 4
1 - - - 30+30 - 60 3
2 - - 30+20 - - 50 2
3 - 30+10 - - - 40 1
4 0+0 - - - - 0 0

Stage 3 (demand=2)
Solution
f3(s3,x3)=5(y3+x3-d3)+30+10x3+f4(y*3+x3-d3)
s3 optimal
x 3= 0 x3= 1 x 3= 2 x3= 3 x3= 4 x3= 5 f3*(s3) x3 *
0 - - 0+50+70=120 5 + 60 + 60 = 125 10+70+50=13015+80+40=135 120 2
1 - 0+40+70=110 5+50+60=115 10+60+50=12015+70+40=125 20+80+0=100 100 5
2 0+0+70=70 5 + 40 + 60 = 105 10+50+50=11015+60+40=115 20 + 70 + 0 = 90 - 70 0
3 5+0+60=65 10 + 40 + 50 = 100 15 + 50 + 40 = 105 20+60+0=80 - - 65 0
4 10+0+50=60 15+40+40=95 20+50+0=70 - - - 60 0

Stage 2 (demand=3)
Solution
f2(s2,x2=5(y2+x2-d2)+30+10x2+f3(y*2+x2-d2)
s2 optimal
x 2= 0 x 2= 1 x2= 2 x2= 3 x2= 4 x2= 5 f2*(s2) x2 *
0 - - - ["0 + 60 + 120 = 180","5 + 70 + 100 = 175","10 + 80 + 70 160
= 160"] 5
1 - - 0+50+120=170 5+60+100=165 10+70+70=150 15+80+65=160 150 4
2 - 0+40+120=1605+50+100=15510+60+70=14015+70+65=15020+80+60=160 140 3
 3 0+0+120=1205+40+100=14510+50+70=13015+60+65=14020+70+60=150 - 120 0
4 5+0+100=10510+40+70=12015+50+65=13020+60+60=140 - - 105 0

Stage 1 (demand=1)
Solution
f1(s1,x1)=5(y1+x1-d1+30+10x1+f2(y*1+x1-d1)
s1 optimal
x 1= 0 x1= 1 x1= 2 x1= 3 x14 x15 f1*(s1) x1 *
0 - 0+40+160=200 5 + 50 + 150 = 205 10+60+140=210 15+70+120=205 20 + 80 + 105 = 205 200 1

PROBLEM 7
A company builds commercial airplanes for various airlines around the world. The latest
This phase of the process involves the manufacturing of turbine engines and their installation in the structure.
of the plane. The company has to deliver, soon, a large number of planes and,
for this reason, he wishes to schedule the production of the turbine engines for the next four
months.

The following table shows, for each of the next four months, the amount of
engines that must be ready for installation, the maximum production capacity of such
Yes, the unit cost of manufacturing each engine (which can vary from month to month due to the
staff needs, changes in material prices, energy consumption, etc.
and the cost of storing an engine for a month (in this case, the cost is always fixed at $15000
by engine).

Production Facilities Unit Cost Unit cost

Me
programmed maximum production* 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
*cost given in millions of $.

Given the variations in production costs, it might be worth it to manufacture some motors.
before its installation date. Use dynamic programming methods to determine the
optimal production for each month, considering that the amounts produced must be
multiples of 5.

Solution:
Sean:
xnthe level of production in the month n
yn the initial inventory in month n
dnthe demand in the month n

Recursive function: Minimum cost to meet the demands fn(sn,xn) = min {CP(xn) + CI(yi+1) + fn+1(sn+1)}
Stage: Every month
Status: Initial Inventory

STAGE 4 (Demand = 20)

f4(s4,x4=1.13x4 Optimal solution
s4
x4=0 x45 x410 f4*(s4) x4
10 - - 11.3 11.3 10
15 - 5.65 - 5.65 5
20 0 - - 0 0
 ETAPA 3 (Demanda =25)
*
f3(s3,x3)=1.10x3+0.015(y3+x3-d3) + f4(y3+x 3-d3) Optimal solution
s3
x3=0 x35 x310 x315 x320 x3=25 x3=30 f3*(s3) x3
5 - - - - - - 44.45 44.45 30
10 - - - - - 38.95 38.875 38.875 30
15 - - - - 33.45 33.375 33.3 33.3 30
20 - - - 27.95 27.875 27.8 - 27.8 25
25 - - 22.45 22.375 22.3 - - 22.3 20
30 - 16.95 16.875 16.8 - - - 16.8 15
3511.45 11.375 11.3 - - - - 11.375 10

STAGE 2 (Demand = 15)

*
f2(s2,x2)= 1.11x2+0.015(y2+x2-d2)+f3(y2+x 2-d2) Optimal solution
s2
x2=0 x2=5 x2=10 x2=15 x2=20 x2=25 x2=30 x2=35 f2*(s2) x2
0 - - - - 66.725 66.775 66.825 66.95 66.725 20
5 - - - ["61.175","61.225","61.275"] 61.4 61.525 61.175 15
10 - - 55.625 55.675 55.725 55.85 55.975 56.1 55.625 10
15 - 50.075 50.125 50.175 50.3 50.425 50.55 50.675 50.075 5

ETAPA 1 (Demanda =10)

f1(s1,x1=1.08x1+0.015(y1+x1-
Optimal solution
s1 d1) + f2*(y1+x1-d1)
x1=10 x115 x120 x1=25 f1*(s1) x1
0 77.525 77.375 77.225 77.075 77.075 25