INDICE

I.INTRODUCCION
...2

II. PROBLEMA DE CAMINO MS LARGO (RUTA

CRTICA)3

III.
PROBLEMA
DE
CAMINO
CORTO.....8

MS

IV. PROBLEMA DE
ASIGNACIN.1
2

V.MODELO DE
INVERSION..
..20

VI.
MODELO
VOLUMEN
CARGA...28
VII.PLANIFICACIN DE PRODUCCIN E
INVENTARIO..36

VIII.METODO DE REPOSICIN DE
EQUIPO.48

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

I. INTRODUCCIN
Generalidades:
PROGRAMACIN DINMICA:
Para abordar la resolucin de un problema con Programacin Dinmica,
habra que verificar, en primer lugar, la naturaleza N-etpica del problema
bajo consideracin, para caracterizar la estructura de una solucin optima.
Posteriormente, se tendra que comprobar el cumplimiento del Principio de
Optimalidad de Bellman como condicin absolutamente necesaria para su
aplicacin, y si este se verificara, apoyndose en su propio significado en el
caso concreto que estemos resolviendo, formular una ecuacin de
recurrencias que represente la forma de ir logrando etapa por etapa la
solucin optima correspondiente. A partir de esa ecuacin, a continuacin,
habr que determinar la solucin optima resolviendo problemas encajados
para, por ultimo, construir la solucin. Con esos ingredientes, se podra
iniciar la solucin del problema que, a su vez, podra realizarse desde el
primer estado hasta el ultimo, o bien a la inversa.
De forma mas concisa, el desarrollo de un algoritmo de PD correspondera a
las siguientes etapas:
1.- Caracterizar la estructura de una solucin optima
2.- Definir recursivamente el valor de una solucin optima
3.- Calcular el valor de una solucin optima en forma encajada de menos a
mas, y
4.- Construir una solucin optima a partir de la informacin previamente
calculada.
Las etapas 1-3 constituyen la base de la solucin de PD para un cierto
problema. La etapa 4 puede omitirse si lo nico que buscamos es el valor
de una solucin optimal. Cuando se realiza la etapa 4, a veces
mantenemos informacin adicional durante la etapa 3 para facilitar la
construccin de una solucin optima.
2

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Vemos as que la PD, igual que la tcnica Divide y Vencers, resuelve
problemas combinando las soluciones de subproblemas. Como sabemos,
los algoritmos Divide y Vencers peticionan
el
problema
en
subproblemas independientes, resuelven
estos
recursivamente,
y
combinan sus soluciones para obtener la solucin del problema original.
En contraste, la PD es aplicable cuando los subproblemas no son
independientes, es decir, cuando los subproblemas comparten subsubproblemas. En este contexto, un algoritmo Divide y Vencers hace mas
trabajo del necesario, ya que resuelve repetidamente sub-subproblemas
comunes. Un algoritmo de PD resuelve cada sub-subproblema solo una
vez, salvando su solucin en una tabla de cara a evitar el trabajo de
recalcular la solucin cada vez que se encuentra ese sub-subproblema.

II. PROBLEMA DE CAMINO MS LARGO (RUTA

CRTICA)
PROBLEMA1
Considere la siguiente red de proyecto, donde el nmero sobre el arco es el
tiempo requerido para la actividad correspondiente y la letra el respectivo
nombre de la actividad. Considere el problema de encontrar la trayectoria
ms larga (el mayor tiempo total) a travs de esta red desde el inicio hasta
su trmino, puesto que la trayectoria ms larga es la ruta critica.

Solucin:
Dividimos el problema en 5 etapas, como se muestra en la siguiente figura:
3

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Etapas: n=1, 2, 3, 4, 5

f n( Sn , Xn)=max [t ( Sn , Xn)+ f n1( X n1)]

Funcin recursiva:
Donde:
fn(Sn,Xn):
t(Sn,Xn):
fn-1(Xn-1)

Tiempo total cuando se ha realizado n etapas.

Tiempo de la etapa n.
:
El mejor tiempo total cuando se ha recorrido n-1 etapas.

Etapa 1
S1= A,B
X1= INICIO

S1
A
B

X1
INICIO
3
2

f1
3
2

X1
INICIO
INICIO

Etapa 2
S2 = C, D, E
X2 = A,B
X2

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

S2
C
D
E

A
8
7
-

B
5

f2
8
7
5

X2
A
A
B

F2(A,C) = max [ t( A, C ) + f1 ( X1 ) ]
= 5+ 3 = 8
F2(A,D) = max [ t( A, D) + f1 ( X1 ) ]
= 4+ 3 = 7
F2(B,E) = max [ t( B, E) + f1 ( X1 ) ]
=3+2=5

Etapa 3
S3 = F, G, H, I
X3 = C,D,E

S3
F
G
H
I

C
12
9
-

X3
D
15
9

E
12
8

F3
12
9
15
9

F3(C,F) = max [ t( C, F ) + f2( X2) ]

= 4+8 = 12
F3(C,G) = max [ t( C, G) + f2( X2) ]
= 1+8 = 9
F3(D,H) = max [ t( D, H) + f2( X2) ]
= 8+ 7 =15
F3(D,I) = max [ t( D, I) + f2( X2) ]
= 2+ 7 =9
F3(E,H) = max [ t( E, H) + f2 ( X2 ) ]
= 7+ 5 =12
F3(E,I) = max [ t( E, I) + f2 ( X2 ) ]

X3
C
C
D
D

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

= 3+ 5 =8
Etapa 4
S4 = J, K, L
X4 = F, G, H, I
X4
S4
J
K
L

F
13
-

G
13
-

H
21
-

I
11

f4
13
21
11

X4
F
H
I

F4(F,J) = max [ t( F, J ) + f3( X3) ]

= 1+12 = 13
F4(G,K) = max [ t( G, K )+ f3( X3) ]
= 4+9 = 13
F4(H,K)= max [ t( H, K )+ f3( X3) ]
= 6+15 = 21
F4(I,L)= max [ t( I, L )+ f3( X3) ]
= 2+9 = 11
Etapa 5
S5= INICIO
X5 = J, K ,L

S5
FIN

J
18

X5
K
25

L
18

f5
25

X4
K

F4(J,FIN) = max [ t( J, FIN ) + f4( X4) ]

= 5+13=18
F4(K,FIN) = max [ t( K, FIN ) + f4( X4) ]
= 4+21 = 25
F4(L,FIN) = max [ t( L, FIN ) + f4( X4) ]
= 7+11 = 18
Duracin del proyecto:
Ruta Crtica:
nodos

25
Inicio A D H K FIN, segn los
Segn las actividades:
A-D-H-N-Q

SOLUCIN CON SOFTWARE WinQSB

1) Ingresamos los datos

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

2) Informe de resultados e interpretacin

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

III. PROBLEMA DE CAMINO MS CORTO

Un vuelo de Speedy Airlines est a punto de despegar de Seattle sin escalas
a Londres. Existe cierta flexibilidad para elegir la ruta ms precisa, segn las
condiciones del clima. La siguiente red describe las rutas posibles
consideradas, donde SE y LN son Seattle y Londres, respectivamente, y los
otros nodos representan varios lugares intermedios.
El viento a lo largo de cada arco afecta de manera considerable el tiempo de
vuelo, y por ende, el consumo de combustible. Con base en el informe
meteorolgico actual junto a los arcos se muestran los tiempos de vuelo (en
horas).
Debido al alto costo del combustible, la administracin ha adquirido la
poltica de elegir la ruta que minimiza el tiempo total de vuelo. Resuelva el
problema utilizando PD.

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Solucin:
Dividimos el problema en 3 etapas, como se muestra en la siguiente figura:

Etapas: n=1, 2, 3

f n( Sn , Xn)=min[t (Sn , Xn)+f n1(X n1)]

Funcin recursiva:
Donde:
fn(Sn,Xn) :
t(Sn,Xn) :
fn-1(Xn-1)

Tiempo total cuando se ha realizado n etapas.

Tiempo de la etapa n.
:
El mejor tiempo total cuando se ha recorrido n-1 etapas.

Etapa 1
S1= A,B,C
X1= SE

S1
A
B
C
Etapa 2

X1
SE
4.6
4.7
4.2

f1
4.6
4.7
4.2
10

X1
SE
SE
SE

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

S2 = D, E,F
X2 = A,B,C

S5
D
E
F

A
8.1
8
-

X5
B
8.3
7.9
8

C
7.7
7.6

F2
8.1
7.7
7.6

X2
B
C
C

F
11.4

f3
11.3

X3
E

F2(A,D) = min[ t( A, D ) + f1 ( X1 ) ]
= 3.5 + 4.6 = 8.1
F2(A,E) = min[ t( A, E) + f1 ( X1 ) ]
= 3.4+ 4.6 = 8
F2(B,D) = min[ t( B, D) + f1 ( X1 ) ]
= 3.6 + 4.7 = 8.3
F2(B,E) = min [ t( B, E) + f1 ( X1 ) ]
= 3.2 + 4.7 = 7.9
F2(B,F) = min[ t( B, F) + f1 ( X1 ) ]
= 3.3 + 4.7 = 8

F2(C,E) = min [ t( C, E) + f1 ( X1 ) ]
= 3.5+4.2 = 7.7
F2(C,F) = min[ t( C, F) + f1 ( X1 ) ]
= 3.4+4.2= 7.6
Etapa 3
S3 = LN
X3 = D, E, F

S3
LN

D
11.5

X3
E
11.3

F3(D,LN) = min [ t( D, LN) + f2( X2) ]

= 3.4+ 8.1 = 11.5
F3(E,LN) = min [ t( D, LN) + f2( X2) ]
= 3.6 + 7.7 = 11.3
F3(F,LN) = min [ t( F, LN) + f2( X2) ]
= 3.8 + 7.6 = 11.4

Tiempo mnimo de vuelo:

Camino ms corto:

11.3 horas
SE C E LN
11

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

SOLUCIN EN SOFTWARE WinQSB:

Solucion:
Tiempo mnimo de vuelo: 11.3 horas
Camino ms corto:
ST C E LN

IV. PROBLEMA DE ASIGNACIN:

Problema 1:

12

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

El propietario de 3 tiendas ha comprado 5 cestas de cerezas, para

satisfacer la demanda en las diferentes tiendas. El propietario desea
determinar la forma de distribuir los canastos, de manera de
maximizar el beneficio total. Los retornos (utilidades) enfuncin del
nmero de canastos distribuidos (se asume vendidos) en las 3 tiendas
estn dados en la siguiente tabla:

Tienda\canas
tos
1
2
3

0
0
0

3
5
4

7
10
6

9
11
11

12
11
12

13
11
12

Solucion:
Funcin de recurrencia:

f i ( Si , X i )=max {r i ( X i) + f i1 (Si1 , X i1) }

ETAPA I: TIENDA 3
Si\Xi
0
1
2
3
4
5

0
0
0
0
0
0
0

4
4
4
4
4

6
6
6
6

11
11
11

12
12

12

F(Xi)
0
4
6
11
12
12

Xi
0
1
2
3
4
4,5

ETAPA II:TIENDA2
S2\X2
0
1
2
3

0
0
4
6
11

12

12

5+11=1
6
5+12=1
7

ETAPAIII:TIENDA1

5
5+4=9
5+6=11

10
10+4=1
4
10+6=16
10+11=
21

13

11
11+4=1
5
11+6=1
7

11
11+4=1
5

11

F(Xi)
0
5
10
14

Xi
0
1
2
2

16

1,2

21

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

S2\X2
5

0
21+0

1
3+16=1
9

2
7+14=2
1

Alternativa 1
T1
0
T2
2
T3
3
Beneficio
21
total

3
9+10=1
9

4
12+5=1
7

5
13

F(Xi)
21

Alternativa 2
T1
2
T2
2
T3
1
Beneficio total 21

Solucion utilzando DIN:

14

Xi
2,0

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

15

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

La solucin ptima nos indica que se tienen dos

alternativas:

Alternativa 1
T1
0
T2
2
T3
3
Beneficio
21
total

Alternativa 2
T1
2
T2
2
T3
1
Beneficio total 21

16

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

PROBEMA 2:
El propietario de una cadena de tres supermercados compr cinco cargas de
fresas frescas. La distribucin de probabilidad estimada de las ventas
potenciales de las fresas antes de que se echen a perder difiere entre los
tres supermercados. El propietario quiere saber cmo debe asignar las cinco
cargas a las tiendas para maximizar la ganancia esperada.
Por razones administrativas, no quiere dividir las cargas entre las tiendas.
Sin embargo, est de acuerdo en asignar cero cargas a cualquiera de ellas.
En la siguiente tabla se proporciona la ganancia estimada de cada tienda al
asignar distintas cantidades de carga:

Numero de
cargas
0
1
2
3
4
5

Tienda
2
0
6
11
15
19
22

1
0
5
9
14
17
21

3
0
4
9
13
18
20

Utilice programacin dinmica para determinar cuntas cargas debe

asignarse a cada tienda para maximizar la ganancia total esperada.
Solucin:
Funcin de recurrencia:

f i ( Si , X i )=max {r i ( X i) + f i1 (Si1 , X i1) }

ETAPA I: TIENDA 1
S1
X1
0
1
2
3
4
5

0
0
0
0
0
0

5
5
5
5
5

9
9
9
9

14
14
14

17
17

21

f 1 ( Si , 0 )=max { 0+0 }=0

f 1 ( Si ,1 )=max {5+ 0 }=5

17

f 1 ( X 1)
0
5
9
14
17
21

X1*
0
1
2
3
4
5

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f 1 ( Si , 2 )=max {9+ 0 }=9

f 1 ( Si , 3 )=max {14 +0 }=14

f 1 ( Si , 4 )=max {17+ 0 }=17

f 1 ( Si ,5 )=max {21+ 0 }=21

ETAPA II: TIENDA 2

S2
X2
0
1
2
3
4
5

0
5
9
14
17
21

6
11
15
20
23

11
16
20
25

15
20
24

19
24

22

f 2 ( 0,0 ) =max { 0+0 }=0

f 2 ( 1,0 )=max { 0+5 }=5
f 2 ( 2,0 )=max { 0+9 }=9
f 2 ( 3,0 )=max { 0+14 }=14
f 2 ( 4,0 )=max { 0+17 }=17
f 2 ( 5,0 )=max { 0+21 }=21

f 2 ( 1,1 )=max {6 +0 }=6

f 2 ( 2,1 )=max {6 +5 }=11

f 2 ( 3,1 )=max {6 +9 }=15
f 2 ( 4,1 ) =max { 6+14 }=20
f 2 ( 5,1 )=max {6 +17 }=23

f 2 ( 2,2 )=max {11 +0 }=11

f 2 ( 3,2 )=max {11+ 5 }=16
f 2 ( 4,2 ) =max { 11+9 }=20
f 2 ( 5,2 )=max {11+ 14 }=25
18

f 2( X 2)
0
6
11
16
20
25

X2*
0
1
1, 2
2
1, 2, 3
2

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f 2 ( 3,3 )=max { 15+ 0 }=15

f 2 ( 4,3 )=max { 15+5 }=20
f 2 ( 5,3 )=max {15+ 9 }=24

f 2 ( 4,4 )=max {19+ 0 }=19

f 2 ( 5,4 )=max { 19+5 }=24

f 2 ( 5,5 )=max { 22+ 0 }=22

ETAPA III: TIENDA 3

S3
X3
5

25

24

25

24

24

20

f 3 ( 5,0 )=max { 0+25 } =25

f 3 ( 5,1 )=max { 4+20 }=24

f 3 ( 5,2 )=max { 9+16 }=25

f 3 ( 5,3 )=max { 13+11 }=24

f 3 ( 5,4 )=max { 18+6 }=24

f 3 ( 5,5 )=max { 20+0 }=20

f 3 ( X 3) X3*
25

0, 2

La distribucin de cargas de fresas frescas debe darse de la siguiente

forma:
Tienda

1
2
3
Total

Solucin
Alternativa
Alternativa
1
2
3
1
2
2
0
2
5
5

SOLUCIN CON SOTFWARE DIN1:

1) Planteamiento del problema:

19

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

2) Clculo de estados:

3) Informe de resultados e interpretacin:

20

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

De los resultados podemos observar que existen dos soluciones al igual que
la solucin anterior.

Tienda

Solucin
Alternativa
Alternativa
1
2
3
1
2
2
0
2
5
5

1
2
3
Total

V.MODELO DE INVERSION
Al gerente general de una empresa muy importante se le presenta la
oportunidad de invertir en 4 proyectos y tiene a su disposicin 1000 . Las
ganancias estimadas para diferentes cantidades invertidas en cada proyecto
se presentan en el siguiente cuadro:

Capital

200
400
600
800
1000

Proyectos
1
20
20
30
50
50

2
30
20
40
30
50

3
20
30
50
40
60

4
20
30
40
40
60

Solucin:
Funcin de recurrencia:

f i ( Si , X i )=max {gi ( X i ) + f i1 (Si1 , X i1) }

gi ( X i ) :ganancia en el proyecto ial invertir x

ETAPA I: PROYECTO 4

S1
X1
0
200

200

400

0
0

20

600
21-

800

1000

f 1 ( X 1)
0
20

X1*
0
200

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

400
600
800

0
0
0

20
20
20

30
30
30

40
40

40

30
40
40

1000

20

30

40

40

60

60

400
600
600,
800
1000

f 1 ( Si , 0 )=max { 0+0 }=0

f 1 ( Si , 200 )=max {20+ 0 }=20

f 1 ( Si , 400 ) =max { 30+0 }=30

f 1 ( Si , 600 )=max { 40+0 }=40

ETAPA II: PROYECTO 3

S2
X2
0
200
400
600

200

400

600

800

1000

f 2( X 2)

X2*

0
20
30
40

20
40
50

30
50

50

0
20
40
50

800
1000

40
60

60
60

60
70

70
80

40
60

60

70
80

0
0, 200
200
200, 400,
600
600
600

f 2 ( 0,0 ) =max { 0+0 }=0

f 2 ( 200,0 )=max { 0+20 }=20
f 2 ( 400,0 )=max { 0+30 }=30

f 2 ( 200,200 )=max { 20+0 }=20

f 2 ( 400,200 )=max { 20+20 }=40
f 2 ( 600,200 )=max { 20+30 }=50

f 2 ( 400,400 )=max { 30+0 }=30

22

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f 2 ( 600,400 )=max { 30+20 }=50

f 2 ( 800,400 )=max { 30+30 }=60

f 2 ( 600,600 )=max { 50+0 }=50

f 2 ( 800,600 )=max { 50+20 }=70
f 2 ( 1000,600 )=max {50+ 30 }=80

f 2 ( 800,800 )=max { 40+0 }=40

f 2 ( 1000,800 )=max { 40+20 } =60

f 2 ( 1000,1000 )=max {60+ 0 }=60

ETAPA III: PROYECTO 2

S3
X3
0
200
400
600
800
1000

200

400

600

800

1000

f 3 ( X 3)

X3*

0
20
40
50
70
80

30
50
70
80
100

20
40
60
70

40
60
80

30
50

50

0
30
50
70
80
100

0
200
200
200
200
200

f 3 ( 0,0 ) =max { 0+0 }=0

f 3 ( 200,0 )=max { 0+20 } =20
f 3 ( 400,0 )=max { 0+ 40 }=40

23

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f 3 ( 200,200 )=max { 30+0 }=30

f 3 ( 400,200 )=max { 30+20 }=50
f 3 ( 600,200 )=max { 30+40 }=70

f 3 ( 400,400 )=max { 20+0 }=20

f 3 ( 600,400 )=max { 20+20 }=40
f 3 ( 800,400 ) =max { 20+40 }=60

f 3 ( 600,600 )=max { 40+0 }=40

f 3 ( 800,600 ) =max { 40+20 }=60
f 3 ( 1000,600 )=max { 40+ 40 }=80

f 3 ( 800,800 ) =max { 30+0 } =30

f 3 ( 1000,800 )=max { 30+ 20 }=50

f 3 ( 1000,1000 )=max {50+ 0 }=50

ETAPA IV: PROYECTO 1

S4
\X4
1000

200

400

600

800

1000

100

100

90

80

80

50

f 4 (1000,0 )=max { 0+100 }=100

f 4 (1000,200 )=max { 20+80 }=100

f 4 (1000,400 )=max { 20+70 }=90

f 4 (1000,600 )=max { 30+50 }=80

24

f 4 (X 4) X4*
100

0, 200

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f 4 (1000,800 )=max { 50+30 }=80

f 4 (1000,1000 )=max { 50+0 }=50

La inversin debe darse de la siguiente forma:

PROYECTO

1
2
3
4

Alternativa
1
0
200
600
200

Solucin
Alternativa
Alternativa
2
3
200
200
200
200
200
400
400
200

Alternativa
4
200
200
600
0

Problema 2:
Un multimillonario desea donar 1millon de dlares para
implementar hospitales en diferentesciudades del pas,con
lo cual beneficiara a la poblacin de ese lugar, cada pueblo
requiere de diferentes fondos.
El multimillonario desea ayudar a la mayor cantidad de
personas posibles, por tal motivo desea saber cmo asignar
su donacin.
N

ciudades

1
2
3
4
5
6
7

Ilave
Requena
Querecotillo
Satipo
Chanchamayo
Paramonga
Paijan

Poblacin
(real)
22153
22155
21916
21894
21885
21397
20980

Solucin: Para resolver el problema dividimos las

cantidades entre 10000.

25

Fondos requeridos
($)
300000
150000
200000
100000
100000
200000
200000

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Solucin:
N

ciudades

Donacin

1
2
3
4
5
6
7

Ilave
Requena
Querecotillo
Satipo
Chanchamayo
Paramonga
Paijan

S
S
S
S
S
S
No

Poblacin
(real)
22153
22155
21916
21894
21885
21397
20980

La mayor cantidad de personas beneficiadas sera 130227

habitantes.

Solucin utilizando el programa DIN:

26

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

El programa nos da como resultado que la mejor opcin es:

ciudades
Ilave
Requena
Querecotillo

Poblacin
(real)
22153
22155
21916
27

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Satipo
Chanchamayo
Paramonga

21894
21885
21397

Siendo 130227 habitantes el total de poblacin que puede ayudar.

Utilizando 950000
del milln que pensaba donar.

28

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

VI. MODELO VOLUMEN CARGA

PROBLEMA 1:
Tengo un pequeo jardn en mi traspatio que mide 10x20 pies. Esta
primavera deseo sembrar verduras: tomates, ejotes y maz. El huerto se
organiza en surcos de 10 pies. Los surcos con tomate y maz tienen 2 pies
de ancho, y los de ejotes son de 3 pies de ancho. Lo que ms me gusta son
los tomates, y los ejotes casi no me gustan, en una escala del 1 al 10
calificara con 10 a los tomates, 7 al maz y 3 a los ejotes.
Independientemente de mis gustos, mi esposa insiste en sembrar al menos
un surco de ejotes y no ms de dos surcos de tomates. Cuntos surcos de
cada planta debo sembrar?
Solucin:

Se dispone de 20 pies, ya que se organiza los surcos de 10 pies de largo.

Restricciones:
Al menos un surco de ejotes y no ms de dos surcos de tomate.
Verdura
1
(Ejotes)
2
(Tomate)
3 (Maz)

Ancho
3

Gustos
3

10

Sea:
(x,y)
Donde:
x= numero de verdura.
y = Cantidad de terreno disponible.

29

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Solucin:
SURCOS
Tomates
Maiz
Ejotes
TOTAL

2
6
1

30

SATISFACC
IN
20
42
3
65

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Problema2
Un par de ladrones quieren robar en una mansin en la que se puede
encontrar muchos objetos de valor. El plan es que solo uno de ellos
entre en la mansin mientras que el otro espera fuera con un furgn
en marcha para acelerar la huida. Los ladrones saben que solo
disponen de un tiempo 10minutos para cargar objetos en el furgn
antes de que la polica llegue a la mansin, as que han de elegir muy
bien los objetos a cargar. Teniendo en cuenta que los ladrones
conocen el valor de los diferentes objetos y el tiempo que emplean
en cargar cada uno de ellos en el camin.

N
1
2
3
4
5
6
7

OBJETOS
Joyas
Cuadros
Vasijas
Juego de cubiertos de
plata
Televisores
Equipo de sonido
laptops

TIEMPO(MIN)
2
6
5
2

VALOR($)
6000
39000
5000
5000

6
7
3

3000
2000
6000

Solucin:
Funcin de recurrencia:
Fi(Xi) = max [ ri mi + fi+1(Xi wimi) ],
[ W / Wi]
Ri, mi = 0, 1, 2, 3

Etapa 7
F7(X7) = max [ r7 m7 ] , [ W / W7 ] = [ 10/3] = 3.33
R7=6000 , mi = 0, 1, 2, 3
F7(X7) = 6000 m7
X7
0
1
2

m7=0
0
0
0

m7=1

m7=2

31

m7=3

F7(X7)
0
0
0

m7
0
0
0

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

3
4
5
6
7
8
9
10

0
0
0
0
0
0
0
0

6000
6000
6000
6000
6000
6000
6000
6000

12000
12000
12000
12000
12000

18000
18000

Etapa 6 :
F6(X6) = max [ r6 m6 + f7(X6 7m6) ] ,
m6 = [ 0/7 ] = 1.42
m6 = 0, 1
f6(X6) = 2000 m6+ f7(X6 7m6)
X6
0
1
2
3
4
5
6
7
8
9
10

M6=0
0
0
0
6000
6000
6000
6000
12000
12000
18000
18000

M6=1
2000
2000
2000
8000

F6(X6)
0
0
0
6000
6000
6000
6000
12000
12000
18000
18000

M6
0
0
0
0
0
0
0
0
0
0
0

Etapa 5 :
F5(X5) = max [ r5 m5+ f6(X5 6m5) ] ,
M5 = [ 10/6 ] = 1.667
M5 = 0, 1
F5(X5) = 3000 m5 + f6(X5 6m5)

X5

M5=0

M5=1

F5(X5)
32

M5

6000
6000
6000
6000
12000
12000
18000
18000

0
0
0
0
0
0
0
0

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

0
1
2
3
4
5
6
7
8
9
10

0
0
0
6000
6000
6000
6000
12000
12000
18000
18000

3000
3000
3000
9000
9000

0
0
0
6000
6000
6000
6000
12000
12000
18000
18000

0
0
0
0
0
0
0
0
0
0
0

Etapa 4:
F4(X4) = max [ r4 m4+ f5(X4 2m4) ] ,
M4 = [ 10/2 ] = 5
M4 = 0, 1,2,3,4,5
F4(X4) = 5000 m4 + f5(X4 2m4)
X4
0
1
2
3
4
5
6
7
8
9
10

M4=0
0
0
0
6000
6000
6000
6000
12000
12000
18000
18000

M4=1

M4=2

M4=3

M4=4

M4=5

5000
5000
5000
11000
11000
11000
11000
17000
17000

0
10000
10000
10000
16000
16000
22000
22000

0
0
15000
15000
15000
21000
21000

0
0
0
20000
20000
20000

0
0
0
0
25000

Etapa 3:
F3(X3) = max [ r3 m3+ f4(X3 5m3) ] ,
M3 = [ 10/5] = 2
M3= 0, 1,2
F3(X3) = 5000 m3 + f4(X3 5m3)

33

F4(X4)
0
0
5000
6000
10000
11000
11000
16000
20000
22000
25000

M4
0
0
1
0
2
1
1
2
4
2
5

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

X3
0
1
2
3
4
5
6
7
8
9
10

M3=0
0
0
5000
6000
10000
11000
11000
16000
20000
22000
25000

M3=1

M3=2

5000
5000
10000
11000
15000
21000

10000

F3(X3)
0
0
5000
6000
10000
11000
11000
16000
20000
22000
25000

Etapa 2 :
F2(X2) = max [ r2 m2+ f3(X2 6m2) ] ,
M2 = [ 10/6 ] = 1.667
M2 = 0, 1

F2(X2) = 39000 m5 + f3(X2 6m2)

X2
0
1
2
3
4
5
6
7
8
9
10

M2=0
0
0
5000
6000
10000
11000
11000
16000
20000
22000
25000

M2=1
39000
39000
44000
45000
49000

F2(X2)
0
0
0
6000
10000
11000
39000
39000
44000
45000
49000

Etapa 1:
F1(X1) = max [ r1 m+ f2(X1 2m1) ] ,
34

M2
0
0
0
0
0
0
1
1
1
1
1

M3
0
0
0
0
0
0
0
0
0
0
0

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

M4 = [ 10/2 ] = 5
M4 = 0, 1,2,3,4,5

F1(X1) = 6000 m1 + f2(X1 2m1)

X1
0
1
2
3
4
5
6
7
8
9
10

M1=0
0
0
0
6000
10000
11000
39000
39000
44000
45000
49000

M1=1

M1=2

6000
6000
12000
16000
27000
45000
45000
50000

12000
12000
12000
18000
22000
23000
51000=
39000+120
00

M1=3

M1=4

M1=5

18000
18000
18000
24000
28000

24000
24000
24000

30000

Solucin:

Utilizara 4 minutos para las joyas y 6 minutos para los cuadros

Solucin utilizando DIN:

35

F1(X1)
0
0
0
6000
12000
16000
39000
39000
45000
22000
51000

M1
0
0
1
0
2
0
0
0
1
1,2
2

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

VII.PLANIFICACIN DE PRODUCCIN E INVENTARIO

36

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

PROBLEMA 1
Una empresa debe decidir su poltica de produccin e inventario para
los prximos 3
meses. La empresa ha adquirido algunos compromisos de entrega
para estos meses: 3,
2 y 4 unidades, respectivamente.
En el proceso productivo se incurre en algunos costos que estn
asociados con la
produccin propiamente tal y el almacenamiento de los productos.
Estos costos son:
Costos de almacenamiento (hi por unidad con i = 2; 3; 4) y costos de
produccin (ci
por unidad con i = 1; 2; 3). Los valores de los costos se indican a
continuacin:

Etapas: meses de planificacin i = 1; 2; 3

Variable de Estado:
yk = nivel de inventario al comienzo del periodo k.
Variable de Decisin:
xk = Cantidad a producir en el periodo k.
Ecuaciones de Recurrencia:
Funcin de transformacin: La clsicaconservacin
de flujo:
37

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

yi+1 = yi + xi di
Funcin de recursin:
fi(yi) = min [CP(xi) + CI(yi + xi - di) + fi+1(yi+1)]

xi>=0, enteros

Con CP(xi) = ci*xi (costo de produccin)

CI(yi+1) = hi+1yi+1 (costo de inventario)

Condiciones de Borde:
Condicin inicial: Al comienzo no hay productos almacenados y1 = 0
Condicin final: Dado que se debe cumplir con los compromisos,
quedar con productos
no entregados en bodega no tiene beneficio, por lo que y4 = 0, y
asumo que
no tengo costos de produccin en el cuarto periodo, as f4(y4) = 0

Observacin: Se considerar a que el nmeromximo de estados

corresponde a la
Demanda que falta por satisfacer en las etapas siguientes. As para el
periodo3 , la
Resolucin debe considerar que la variable de estado y3 puede tomar
valores entre 0
y 4, puesto que la demanda para ese periodo es de 4 y se requiere
inventario cero al
final de este ultimo periodo.

Etapa 3:
El problema a resolver es:
f3(y3) = min[20*x3 + 2(y3 + x3 - 4)]
x3 = 4 - y3
x3>= 0, entero

38

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Apliquemos nuestra estrategia de solucin en una tabla

Etapa
2:
El
problema a resolver es:
f2(y2) = min [15*x2 + 3(y2 + x2 - 2) + f3(y2 + x2 - 2)]
6 - y2 <=x2 <= 2 - y2
x2>=0, entero

Aplicando la estrategia de solucin tenemos:

Ntese que hay valores que no es necesario evaluar. Por ejemplo, si

se tienen 6
Unidades al inicio del periodo 2, no es necesario producir, ya que esto
trae consigo un
Almacenamiento innecesario de producto.

Etapa 1:
El problema a resolver es:

39

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f1(y1) = min [10*x1 + 1*(y1 + x1 -3) + f2(y1 + x1 - 3)]

3<= x1<= 9
x1>= 0, entero

Aplicando la estrategia de solucin tenemos:

As vemos que la estrategia ptima es:

Con un costo de 108 dlares

Solucin con winqsb:

40

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Con el software se pude comprobar la respuesta de un costo mnimo

total de 108 dlares con produccin de 9 unidades en el mes 1 y en
los dems meses produccin de cero unidades.

Problema 2
Una empresa antigua y reconocida de motocicletas MartyDavidson
por su aniversario 50, quiere crear un diseo de motocicleta especial
por un tiempo limitado por un tiempo de medio ao, esta
motocicletas de edicin especial sern producidas cada mes en un
nmero que vara y como estas motocicletas son muy valiosas para
los coleccionistas solo saldrn a la venta segn la demanda de cada
mes ya que estas seran compradas muy rpidamente sin dar opcin
de compra a personas que vienen de lejos. Las demandas para estos
meses, costos fijos si se elabora una motocicleta en el respectivo
mes, costo de produccin, costo de almacenamiento y sus respectivas
capacidades se dan a continuacin.

Mes

demand
a

Costos
fijos($
)

Costos
Costos de
variable almacenamie
s ($)
41 nto

Capacida
d de
producci

Capacidad de
almacenamie
nto

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

1
2
3
4
5
6

8
8
7
6
4
3

5000
5000
4500
3500
3000
2800

300
300
310
320
360
500

($)

50
50
50
50
50
50

10
10
10
10
10
10

2
2
2
2
2
2

Solucin en Winqsb:

Funcin de recurrencia:

P(n): el nmero de unidades producidas en el periodo n

D(n): la demanda en el periodo n
H(n): el inventario disponible al final del periodo n
B(n): el backorder al final del periodo n I(n): la posicin del
inventario al final del periodo n, es decir, I(n) = H(n) oI(n) =B(n)I(n) =
I(n-1) + P(n) - D(n)
S(n): el costo de preparacin en el periodo n
V (P(n), I(n)): el costo variable = funcin de P(n), H(n), y/o B(n)

C(n,P(n),I(n)): = S(n) + V(P(n),I(n)) si P(n)>0, = V(P(n),I(n))

si P(n)=0

f(n,i): costo total acumulativo dado el nivel del inventario inicial i

para elperiodonLa relacin recursiva dinmica se expresa como:
f(n,i) = mximo {C(n,P(n),i+P(n)-D(n)) + f(n-1,i+P(n)-D(n))} para todo
posibleP(n).

42

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

La solucin con un costo mnimo es 11650 dlares con una

produccin igual a la demanda de cada mes excepto en los dos
ltimos meses ya que en el mes 5 se fabrico 6 motos( 2 mas que su
demanda) y por eso el mes 6 comenz con un inventario inicial de 2
motos.
g ( t )=max {uti tx + g( x )}

g(t) = utilidad neta mxima generada a partir del tiempo t hasta el

tiempo 4 incluido el ingreso anual el ingreso anual, el costo de
compra de maquina nueva y el valor de reventa dado que se compr
una nueva mquina en el tiempo t.

utitx = utilidad neta de la compra de una maquina en el tiempo t y

de operarla hasta el tiempo x.

43

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

t={0,1,2,3,4} , x<=5

Como el problema termina en el tiempo 5, no se genera costo alguno

a partir de este tiempo en adelante , de modo que se podra escribir
g(5)=0

Ingreso anual= 10 clientes*3 podadas/ao*$50/clientes = $1500/ao

C01=1500-2000-1200+1500=-200
C02=1500-2000+1500-1200-1440+1350=-290
C03=1500-2000+1500+1500-1200-1440-1680+1200=-620
C04=1500-2000+1500+1500+1500-1200-1440-1680-1920+1050=1190
C05=1500-2000+1500+1500+1500+1500-1200-1440-1680-19202160+900=-2000

C12=1500-2200-1200+1500=-400
C13=1500-2200+1500-1200-1440+1350=-490
C14=1500-2200+1500+1500-1200-1440-1680+1200=

PROBLEMA3:
Una fbrica de papeles, PAPER S.A., tiene una demanda a satisfacer durante
la campaa escolar. Se debe cumplir la demanda de cada uno de los meses
implicados, de lo contrario se perdern clientes; y se puede dar el caso de
que no se produzca en algunos de los meses. Adems es poltica de la
fabrica tener como inventario final 10 lotes de papel al culminar toda la
campaa escolar.
PAPER S.A. produce lotes mltiplos de 10, la cantidad mxima de su
produccin es de 50 lotes y empieza con 0 lotes en el almacn.
44

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

En la siguiente tabla se muestra la demanda y los costos de produccin y de
almacn de cada uno de los 5 meses de campaa.
-determinar el plan optimo de produccin.

Mes

Demanda

1
2
3
4
5

40
40
30
10
10

Costo unitario
variable
12
11
11
9
9

Costo fijo
250
230
200
200
200

Costo de
almacn
2.5
2
2
2
1

Solucin:

Funcin de recurrencia:

II
( i+ X iDi )+ f i (X i1)
f i ( X i) =CV i x X i +CF i + ( 2.5, 2,2, 2, 1 ) x

ETAPA I: MES 5

II
( i+ X iDi )

0 + 20 10 = 10
10 + 10 10 = 10
20 + 0 10 = 10

II1 \ X1

10

20

f 1 ( X 1)

X1*

0
10
20

210

300
-

390
-

390
300
210

20
10
0

f 1 ( 20 )=9 x 20+200+1 ( 10 ) +0=390

45

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f 1 ( 10 )=9 x 10+200+1 ( 10 ) +0=300

f 1 ( 0 ) =9 x 0+200+1 ( 10 ) +0=210

ETAPA II: MES 4

II
( i+ X iDi )

0 + 10 10 = 0

10 + 0 10 = 0

0 + 20 10 = 10

10 + 10 10 = 10

0 + 30 10 = 20

10 + 20 10 = 20

20 + 0 10 = 10
20 + 10 10 = 20

10

20

30

X2*

X2
0

f 2( X 2)

680

700

720

680

10

10

590

610

630

590

20

520

540

520

II2

f 2 ( 10 )=9 x 10+200+2 ( 0 ) +390=680

f 2 ( 20 )=9 x 20+200+2 ( 10 ) +300=700
f 2 ( 30 )=9 x 30+200+2 ( 20 ) +210=720

f 2 ( 0 ) =9 x 0+200+ 2 ( 0 )+390=590
f 2 ( 10 )=9 x 10+200+2 ( 10 ) +300=610
f 2 ( 20 )=9 x 20+200+2 ( 20 ) +210=630

f 2 ( 0 ) =9 x 0+200+ 2 ( 10 ) +300=520
f 2 ( 10 )=9 x 10+200+2 ( 20 ) +210=540
46

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

ETAPA III: MES 3

II
( i+ X iDi )

II3 \

0 + 30 30 = 0

10 + 20 30 = 0

0 + 40 30 = 10

10 + 30 30 = 10

0 + 50 30 = 20

10 + 40 30 = 20

X3

0
10

20

30

40

50

f 3 ( X 3)

X3*

1100

1210
1140

1250
1200

1310
-

1210
1100

30
20

f 3 ( 30 )=11 x 30+200+2 ( 0 ) +680=1210

f 3 ( 40 )=11 x 40+200+2 ( 10 ) +590=1250
f 3 ( 50 )=11 x 50+200+2 ( 20 ) +520=1310

f 3 ( 20 ) =11 x 20+200+2 ( 0 ) +680=1100

f 3 ( 30 )=11 x 30+200+2 ( 10 ) +590=1140
f 3 ( 40 )=11 x 40+200+2 ( 20 ) +520=1200

ETAPA IV: MES 2

II
( i+ X iDi )

0 + 40 40 = 0

10 + 30 40 = 0

0 + 50 40 = 10

II4

\X4
0
10

10 + 40 40 = 10

30

40

50

f 4 ( X 4)

X4*

1770

1880
1790

1900
-

1880
1770

40
30

47

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

f 4 ( 40 )=11 x 40+230+ 2 ( 0 )+1210=1880

f 4 (50 )=11 x 50+230+ 2 ( 10 ) +1100=1900

f 4 (30 )=11 x 30+ 230+ 2 ( 0 )+ 1210=1770

f 4 ( 40 )=11 x 40+230+ 2 ( 10 ) +1100=1790

ETAPA V: MES 1

II
( i+ X iDi )

0 + 40 40 = 0
0 + 50 40 = 10

II5

\X5
0

40

50

f 5 ( X 5)

X5*

2610

2645

2610

40

f 5 ( 40 )=12 x 40+ 250+2.5 ( 0 ) +1880=2610

f 5 ( 50 )=12 x 50+ 250+2.5 (10 )+ 1770=2645

La produccin de PAPER S.A., debe ser de la siguiente manera:

MES

Solucin

1
2
3
4
5
Costo ptimo

40
40
30
10
20
2610

48

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

SOLUCIN EN SOFTWARE DIN1:
1) Planteamiento del problema:

2) Clculo de estados:

3) Informe de resultados e interpretacin:

49

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

VIII.METODO DE REPOSICIN DE EQUIPO

PROBLEMA 1
CircleFarms posee un tractor de 2 aos de antigedad, y desea
establecer una poltica de reemplazo para sus tractores durante los 5
aos. Se debe tener en servicio durante mnimo de 3 aos, pero
despus de un mximo de 5 aos se debe desechar. El precio actual
de un tractor es de $40,000, y aumenta 10% por ao. El valor de
recuperacin de un tractor con 1 ao de uso es de $30,000 y
disminuye 10% por ao. El costo de operacin del tractor es de
$1,300, y se espera que aumente 10% por ao.

SOLUCION

Funcin de recurrencia

fi(t)=min{ c(t) + fi+1(t+1)

Mantener

c(0)+pc(i)-s(t) + fi+1(1) Reemplazar

fi(t) = costo mnimo neto para los aos i,i+1,, y n dado que el
tractor tiene t aos de antigedad
al comenzar el
ao i
c(t)=costo de mantenimiento

Ao
0
1
2
3
4
5

Precio de tractor
40000
44000
48000
52000
56000
60000

50

Valor de
recuperacin
30000
33000
36000
39000
42000

Costo de
operacin
1300
1430
1560
1690
1820
1950

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Etapa 5
t
1
2
3

M
1430+0=1430
1560-36000=-34440
1690-39000=-37310

R
1300+56000-36000=21300

F(t)
1430
-34440
-37310

Decisin
M
M
M

F(t)
-33010
-35750
12730

Decisin
M
M
R

F(t)

Decisi
n
M
R

Etapa 4
t
1
2
5

M
1430-34440=-33010
1560-37310=-35750

R
1300+5200042000+1430=12730

Etapa 3
t

1
4

1430-35750=-34320
1820+12730=14550

1300+48000-39000-33010=22710

-34320
-22710

Etapa 2
t
3

M
1690-22710=-21020

R
1300+44000-36000-34320=25020

F(t)
-25020

Decisin
R

F(t)
-23460

Decisin
M

Etapa 1
t
2

M
1560-25020=-23460

Ao
1
2
3
4
5

Decisin

Mantener
Reemplazar
Mantener
Mantener
Mantener

Formulando el problema como uno de ruta ms corta:

51

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Cij=Costos netos desde el comienzo del ao 1 hasta operar la

maquina hasta el comienzo del ao 2.

C12=1560-36000=-34440
C25=44000+1300+1430+1560-36000=12290
C56=56000+1300=57300
C26=4400+1300+1430+1560+1690-39000=10980
C13=1560+1960-39000=-35750
C36=48000+1300+1430+1560-36000=16290
C14=1560+1690+1820-42000=-36930
C46=52000+1300+1430=54730

Solucion con Winqsb:

52

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

53

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

La solucin optima ir del nodo 1 al nodo 2 y del nodo 2 al nodo 6, es

decir se paga el mantenimiento del tercer ao en el ao uno del
estudio y se compra al inicio del ao 2 para mantenerlo y revenderlo
al final del ao 5. El costo mnimo total es de 23460 dlares.

54

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

PROBLEMA 2
El hijo de Mara tiene 12 aos de edad, l tiene un negocio que
consiste en podar el csped a 10 clientes. Para cada ao, poda el
csped tres veces al ao, por lo que le da a ganar 50 dlares por cada
podada. Acaba de pagar 2000 dlares por una nueva podadora. El
costo de mantenimiento y operacin de la podadora es de 1200
dlares por el primer ao en servicio, el cual se incrementa un 20% al
ao y as sucesivamente. Una podadora de un ao tiene valor de
reventa de 1500 dlares, que disminuye un 10% anualmente. Mi hijo
que planea conservar su negocio hasta que cumpla los 16 aos,
piensa que es ms econmica comprar un podadora nueva cada dos
aos. Basa su decisin en el hecho de que el precio de una podadora
nueva solo aumentara un 10% al ao Esta justifica su decisin?.
Defina sus variables, funcin de recurrencia.
Utilice la programacin dinmica para hallar la solucin ptima.

SOLUCION:

Ao
0
1
2
3
4
5

costo de maquina
nueva
2000
2200
2400
2600
2800
3000

cmo

Valor de reventa

1200
1440
1680
1920
2160
2400

1500
1350
1200
1050
900

Funcin de recurrencia

fi(t)=max{ r- c(t) + fi+1(t+1)

Mantener

r + s(t) pc(i) - c(0) + fi+1(1)

Reemplazar

fi(t) = costo mnimo neto para los aos i,i+1,, y n dado que el
tractor tiene t aos de antigedad
al comenzar el
ao i
55

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

c(t)=costo de mantenimiento
r=ingreso anual
pc(i)=precio de podadora nueva en el ao i
s(t)=valor de salvamento con podadora de t aos de antigedad

Ingreso anual= 10 clientes*3 podadas/ao*$50/clientes = $1500/ao

Etapa 4 (ao 4)
t

f4(t)

1500-1440+1350=1410

1500-1680+1200=1020

1500-1920+1050=630

1500+1500-26001200+1500=700
1500+1350-26001200+1500=550
1500+1200-26001200+1500=400

141
0
102
0
630

decisi
n
M
M
M

Etapa 3 (ao 3)
t

f3 (t)

1500-1440+1020=1080

1500-1680+630=450

1500+1500-24001200+1410=810
1500+1350-24001200+1410=660

108
0
660

decisi
n
M
R

Etapa 2 (ao 2)
t

f3 (t)

1500-1440+660=720

1500+1500-22001200+1080=680

114
0

decisi
n
M

Etapa 1 (ao 1)
t

f3 (t)

1500-1200+720=1020

No se puede cambiar al inicio de

ao 1

102
0

56

decisi
n
M

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Ao
1
2
3
4

Decisin

Mantener
Mantener
Reemplazar
Mantener

La decisin del hijo de Mara est justificado ya que cada 2 aos

recambiara la podadora para que la ganancia del ao 1(12 aos)
hasta el ao 4(cumple 16 aos) es ptima de 1020 soles.

PROBLEMA 3:
Una empresa debe determinar la poltica optima, durante los prximos
cuatro aos, de reemplazo de una maquina, que en la actualidad tiene 3
aos. La siguiente tabla muestra los datos del problema. La empresa
establece que toda mquina que tenga 6 aos de edad debe reemplazarse.
El costo de una maquina nueva es 110
Tiempo
t(aos)
0
1
2
3
4
5
6

Utilidades
r(t)
30
18
14
11
10
9
8

Costo de
operacin c(t)
0.1
0.5
1
1.1
1.3
1.5
2

Valor de Venta
s(t)
80
60
50
30
10
5

* Datos en miles de dlares.

Sea:
1: mantener la maquina
( M ).
0: vender la mquina para adquirir una nueva.

( V ).

A continuacin se muestra la red, en la cual cada nodo indica el tiempo de

vida de la mquina y respectivos arcos indican la decisin de mantener con
el mismo equipo o reemplazarlo por uno nuevo.
Como se trata de 4 aos, plantearemos el problema tal que cada ao sea
una etapa.
n= 1, 2, 3, 4
El estado en la etapa n es la antigedad de la maquina al comienzo del ao
n.
Funcin recursiva:
Fn(t) = max

r(t) c(t) + fn+1(t+1)

MANTENIENE
r(0) + s(t) I c(0) 57
+fn+1 (1)

si se
si

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Donde:
Fn(t):

Ingreso neto mximo para los aos i,i+1, y n

Grfica:

58

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

59

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

Etapa 4:

t
1
2
3
6

M
r(t) +s(t+1) - c(t)
18+ 60-0.5 =
77.5
14+50-1 = 63
11 +30-1.1=
39.9
Solo se vende

V
r(0) +s(t) +s(1) - c(0) -I
30+80+80-0.1-110= 79.1

Solucin ptima
f4(t)
X4
79.1
V

30+80+60-0.1-110= 59.1
30+80+50-0.1-110= 49.1

63
49.1

M
V

30+80+5-0.1-110= 4.9

4.9

Etapa 3:

t
1
2
5

M
r(t) - c(t)
+f4(t+1)
18-0.5+63 =
80.5
14-1+49.1 =
62.1
9-2+4.9=11.9

V
r(0) +s(t) - c(0) -I+f4(1)

Solucin ptima
F3(t)
X3

30+80-0.1-110 + 79.1= 79

80.5

30+60-0.1-110+79.1= 59

62.1

30+10-0.1-110+79.1= 9.9

11.9

Etapa 2:

t
1
4

M
r(t) - c(t)
+f3(t+1)
18-0.5+62.1 =
79.6
10-1.3 + 11.9=
20.6

V
r(0) +s(t) - c(0) -I+f3(1)

Solucin ptima
F2(t)
X2

30+80-0.1-110 + 80.5= 80.4

80.4

30+10-0.1-110+80.5= 30.4

30.4

Etapa 1:
t
3

M
r(t) - c(t)
+f2(t+1)
11-1.1 + 30.4=
40.3

V
r(0) +s(t) - c(0) -I+f2(1)
30+50-0.1-110+80.4= 50.3

El costo ptimo total ser: 50.3 (miles de dlares)

Las polticas para cada ao sern:
Ao
1
2

Poltica
V
V
60

Solucin ptima
f1(t)
X1
50.3

INVESTIGACION OPERATIVA: LABORATORIO PROGRAMACION DINAMICA

3
4

M
M

61