Ejercicios de Programación Dinámica

Investigacin de Operaciones - I
Ejercicios de Programacin Dinmica en variable discreta

A continuacin se presentan 5 ejercicios resueltos de Programacin Dinmica en variable discreta.
EJERCICIOS RESUELTOS DE PROGRAMACIN DINAMICA
1.- Un Ingeniero Forestal, requiere saber: i)Cul es el costo mnimo, y ii)Cul es la ruta con ese costo mnimo,
para ir desde su oficina hasta el lugar donde est la cosecha. En su camino debe pasar por 3 sectores o
ciudades antes de llegar a su destino, y lugares posibles en esos sectores o ciudades. Las posibles rutas, y
el costo asociado por Kms. de distancia y otros en $, se ven en el siguiente esquema:
Solucin:
Para ir de 1 a 13 hay 48 rutas posibles. Una posibilidad para encontrar la solucin es calcular el
valor asociado a cada una y ver cual es la que proporciona el menor costo. Y si fuesen miles de rutas?.
Por se descarta esa alternativa y se usa el mtodo de la programacin Dinmica, donde se resuelve desde el
final hacia el inicio, y hay etapas y estados.
Etapas: Son 4. La etapa 1 es decidir ir del estado inicial 1 al estado 2,3,4 o 5 que son los puntos posibles en
el sector siguiente. La etapa 2 es decidir ir a 6, 7 u 8. La etapa 3 es decidir ir a 9, 10, 11 o 12. La etapa
4 es decidir a 13.
Estado: Lugar donde se encuentra. La etapa 1 tiene 1 estado: el 1. La etapa 2 tiene 4 estados: 2, 3, 4, 5. La
etapa 3 tiene 3 estados: 6,7,8. La etapa 4 tiene 4 estados: 9, 10, 11, 12.
Clculos
n=3
n=4
S \ X4
13
9
10
11
12
12
16
15
14
F4*
12
16
15
14
X4*
13
13
13
13
S \ X3
10
11
12
6
7
8
3+12=15
4+12=16
2+12=14
2+16=18
1+16=17
3+16=19
1+15=16
4+15=19
6+15=21
3+14=17
6+14=20
5+14=19
F3*
15
16
14
X3*
9
9
9
n=2
S \ X2
2
3
4
5
n=1
S \ X1
1
9+15=24
5+15=20
9+15=24
9+15=24
4+16=20
7+16=23
10+16=26
10+16=26
6+14=20
4+14=18
8+14=22
11+14=25
F2*
20
18
22
24
X2*
7-8
8
8
6
7+20=27
6+18=24
5+22=27
6+24=30
Respuesta: El ptimo es: 24

La solucin ptima es: X1 = 3 ; X2 = 8 ; X3= 9 ; X4= 13.
La ruta ptima es:
1
3
8
F1*
24
X1*
3
13
Respuesta al problema planteado:

El Ingeniero Forestal tiene un costo mnimo de $24 para ir desde su oficina al lugar de cosecha, y ese
mnimo lo puede lograr yendo desde su oficina al lugar 3 luego al lugar 8 luego al lugar 9 y de ah al
lugar 13, que es donde est la cosecha.
2.-Un Tcnico Forestal, debe revisar 3 faenas: Poda, Raleo y Cosecha, y dispone de 4 das. Segn la
dedicacin en das que le de a cada faena, stas tendrn una probabilidad de fracasar, y con ello
fracasar la faena total, por lo que puede ser despedido. Por ello, dicho Tcnico desea minimizar la
probabilidad de ser despedido minimizando la probabilidad de que las 3 tareas fracasen al mismo
tiempo.
Poda
Raleo
Cosecha
Dedicacin \ Faenas
0 da
0.50
0.60
0.40
1 da
0.42
0.51
0.35
2 das
0.36
0.41
0.21
3 das
0.25
0.36
0.18
Un da no asignado a una faena no tiene valor asociado. A lo ms se puede asignar 3 das a una
misma faena.
Solucin:
Etapas: Son 3. La etapa 1 es el proceso de asignacin de das a Poda. La etapa 2 es el proceso de
asignacin de das a Raleo. La etapa 3 es el proceso de asignacin de das a Cosecha.
Estados: Son los das disponibles para ser asignados, y van de 0 a 4, dependiendo de las etapas. La etapa
1 tiene 1 estado factible y es: tener 4 das disponibles para ser asignados.
Las variables de decisin son 3: X1, X2, X3 y representan: Cuntos das asignar a la faena poda,
Cuntos das asignar a la faena de raleo, Cuntos das asignar a la faena de cosecha; respectivamente.
La Funcin Objetivo y las restricciones forman en el modelo para este problema y es:
P:
Min( p(X1)*p(X2)*p(X3) ) ; s.a: X1+X2+X3 4 ; Xi 0,1,2,3; i=1,2,3
La probabilidad de ser despedido en este momento es: 0.5*0.6*0.4 =0.12, que es de un 12%, y con los 4
das disponibles desea minimizar esa probabilidad.
Los clculos.
n=3
S \ X3
0
1
2
3
4
n=2
S\X2
1
2
3
4
0.4*1=0.40
0.4*1=0.40
0.4*1=0.40
0.4*1=0.40
0.4*1=0.40
0.35*1=0.35
0.35*1=0.35
0.35*1=0.35
0.35*1=0.35
0.21
0.21
0.21
0.18
0.18
F3*
0.40
0.35
0.21
0.18
0.18
0.6*0.35=0.210
0.6*0.21=0.126
0.6*0.18=0.108
0.6*0.18=0.108
0.51*0.40=0.2040
0.51*0.35=0.1785
0.51*0.21=0.1071
0.51*0.18=0.0918
0.41*0.40=0.1640
0.41*0.35=0.1435
0.41*0.21=0.0861
0.36*0.40=0.144
0.36*0.35=0.1260
n=1
S\X1
4
0.5*0.0861
= 0,04305
0.42*0.1071=
0,044982
0.36*0.1260
= 0,04536
0.25*0.2040
= 0,051
Respuesta: ptimo = 0.04305 ( un 4,3% ).

La solucin ptima es: X1 = 0 ; X2 = 2 ; X3= 2
La ruta ptima es:
4
4
X3*
0
1
2
3
3
F2*
0.2040
0.1260
0.1071
0.0861
F1*
0.04305
Respuesta al problema planteado: La probabilidad mnima de ser despedido es 0.04305 , es decir de un

4,3%, y la asignacin ptima de das es: 0 das a la Poda, 2 das al Raleo, 2 Das a la
Cosecha.
3.- Un aserradero debe enviar 4 o 5 cargamentos a cuatro destinos. La mxima asignacin para cada
destino es de cuatro cargamentos. En la tabla siguiente se indica g(x i) como los ingresos en MM$
obtenidos por cada una de las decisiones posibles. Se desea maximizar el ingreso del aserradero por
estos envos.
Adems al destino 2 no se puede asignar 4 sino que mximo 3 cargamentos. Al destino 3 ya se ha
decidido asignar exactamente 1 cargamento. Un cargamento no asignado no tiene valor asignado.
cargamentos \ destinos
0
1
2
3
4
1
0
5
11
15
21
2
0
6
10
16
-
3
0
4
12
17
22
4
0
7
10
14
23
Solucin:
Etapas: son 4 etapas. La etapa 1,2,3,4 es el proceso de decisin de envos de cargamento al destino 1,
destino 2, destino 3 y destino 4 respectivamente.
X2*
1
0
1
2
X1*
0
Estados: La cantidad de cargamentos disponibles para ser enviados en cada etapa.

El modelo en este caso es: (Son 2 problemas en uno).
P: Mx ( g(xi); i=1,2,3,4) s.a: X1+X2+X3 +X4 5 ; Xi 0,1,2,3,4; i=1,2,3,4.
P: Mx ( g(xi); i=1,2,3,4) s.a: X1+X2+X3 +X4 4 ; Xi 0,1,2,3,4; i=1,2,3,4.
Los Clculos.
n=4
S \X3
0
1
2
3
4
0
0
0
0
0
7+0=7
7+0=7
7+0=7
7+0=7
10
10
10
14
14
23
n =3
S \ X3
1
2
3
4
5
n=2
S\X2
1
2
3
4
5
n=1
S \ X1
4
5
F4*
0
7
10
14
23
F3*
4
11
14
18
27
4+ 0 = 4
4+ 7 =11
4+10=14
4+14=18
4+23=27
0+4=4
0+11=11
0+14=14
0+18=18
0+27=27
6+4=10
6+11=17
6+14=20
6+18=24
10+4=14
10+11=21
10+14=24
16+ 4=20
16+11=27
X4*
0
1
2
3
4
X3*
1
1
1
1
1
F2*
4
11
14
21
27
0+21=21
0+27=27
5+14=19
5+21=26
11+11=22
11+17=28
15+4=19
15+11=26
--21+4=25
X2*
0
0
1
2
0-3
F1*
22
28
X1 *
2
2
Respuesta:
A) Si enva 4 cargamentos, el ptimo es: MM$ 22, y la solucin ptima es: X 1 = 3 ; X2 = 0 ; X3= 1;
X4= 0;
X1 = 2
X2 = 0
X3= 1
X4= 1
2
2
1
0
11
0
4
7
Es decir: Al destino-1 debe enviar 2 cargamentos, al destino-2 debe enviar 0 cargamento, al destino3 enviar 1 cargamento, y al destino-4 enviar 1 cargamento. Con esto obtiene el mx que es de
MM$22.
La ruta ptima es:
B) Si enva 5 cargamentos, el ptimo es: MM$ 28, y la solucin ptima es: X 1 = 2 ; X2

= 1 ; X3= 1; X4= 1;
X1 = 2
La ruta ptima es:
X2 =1
3
X3= 1
2
X4= 1
1
11
Es decir: Al destino-1 debe enviar 2 cargamentos, al destino-2 debe enviar 1 cargamento, al destino3 enviar 1 cargamento, y al destino-4 enviar 1 cargamento. Con esto obtiene el mx que es de
MM$22.
4.- Un dueo de tres supermercados tiene 5 cargas de fresas frescas. Su problema es destinar las fresas a cada
supermercado, ya que en cada uno las fresas tienen distinto valor. El ingreso en los supermercados,
segn la asignacin de cargas se indica a continuacin en MM$.
Cargamentos \ destino
0
1
2
3
4
5
Supermercado 1
0
5
9
14
17
21
Supermercado 2
0
6
11
15
19
22
Supermercado 3
0
4
9
13
18
20
El no asignar las cargas de fresas a un supermercado tiene valor asociado de cero pesos al horizonte,
porque se perdern.
Cul es el mximo ingreso posible, y cul es la asignacin que para ello?.
Solucin:
n=3
n=2
S \ X2
0
1
2
3
4
5
n=1
S\ X1
5
S \ X3
0
1
2
3
4
5
0
0
0
0
0
0
4+0
4+0
4+0
4+0
4+0
9+0
9+0
9+0
9+0
13+0
13+0
13+0
18+0
18+0
20+0
0+0=0
0+4=4
0+9=9
0+13=13
0+18=18
0+20=20
6+0=6
6+4=10
6+9=15
6+13=19
6+18=24
11
11+4=15
11+9=20
11+13=24
15
15+4=19
15+9=24
19
19+4=23
22
0+24=24
5+20=25
9+15=24
14+11=25
17+6=23
21+0=21
F3*
0
4
9
13
18
20
F2*
0
6
11
15
20
24
F1*
25
X3*
0
1
2
3
4
5
X2 *
0
1
2
1-2-3
2
1-2-3
X1 *
1-3
Respuesta: El mximo ingreso posible es MM$ 25, y se puede alcanzar con la asignacin : X 1 = 1 ; X2
= 2 ; X3= 2 ( Con ingresos: 5+11+9= 25). O bien con la asignacin: X 1 = 3 ; X2 = 2 ;
X3= 0 ( Con ingresos: 14+11+0 = 25 ).
5.- Se dispone de 6 brigadas para asignar a tres sectores. El aumento de la productividad en los sectores
depende de la asignacin, y es la que se indica en el cuadro siguiente:
Nm.brigadas asign. \ sector
0
1
2
3
4
Sector-1
0
12
25
30
40
Sector-2
0
14
19
37
49
Sector-3
0
13
21
32
48
Cuntas brigadas asignar a cada sector para hacer mxima la suma de aumento de la
productividad?.
Una brigada no asignada no tiene valor asociado en la productividad. Esto equivale a decir que el
valor al horizonte de una brigada no asignada es de cero, ya que ese valor no influye sobre el valor
de la funcin objetivo.
Solucin:
Las etapas: Son tres etapas
Los Estados: Son el nmero de brigadas disponibles al inicio de la etapa.
Estado inicial: Es uno slo, y es tener 6 brigadas disponibles.
Variables de decisin: Son 3, indicadas por: X1 , X2 , X3 y el valor de ellas es un elemento del
conjunto: 0,1,2,3, 4
El modelo: P: Mx ( f (Xi ); i=1,2,3) s.a: X1+X2+X3 6 ; Xi 0,1,2,3,4; i=1,2,3.
Los clculos:
n=3
S \ X3
F3*
48
48
48
32
21
13
0
6
5
4
3
2
1
0
n=2
n=1
X3*
4
4
4
3
2
1
0
S \ X2
6
5
4
3
2
49+21=70
49+13=62
49+ 0=49
-
37+32=69
37+21=58
37+13=50
37+0=37
-
19+48=67
19+32=51
19+21=40
19+13=32
19+ 0=19
14+48=62
14+48=62
14+32=46
14+21=35
14+13=27
0+48
0+48
0+48
0+32
0+21
S \ X1
40+27=67
30+37=67
25+50=75
12+62=74
0+70=70
F2*
70
62
50
37
27
X2*
4
1-4
3
3
1
F1*
75
X1*
2
Respuesta: Optimo =75; Solucin ptima: X1*=2; X2*=3; X3*=1

Respuesta: La mayor productividad posible es de 75 y se logra asignando 2 brigadas al sector 1, 3
brigadas al sector 2 y 1 brigada al sector 3.
Ruta ptima:
X1 = 2
X2 = 3
X3= 1
La ruta ptima es:
6
4
1
0
25
37
13
52
E. Orlando Rodrguez Gmez / Tarea de: Investigacin de operaciones II

Ejercicios de Programación Dinámica

Cargado por

Copyright:

Formatos disponibles

Ejercicios de Programación Dinámica

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Ejercicios de Programación Dinámica

Cargado por

Copyright:

Formatos disponibles

Investigacin de Operaciones - I

Ejercicios de Programacin Dinmica en variable discreta

Respuesta: El ptimo es: 24

Respuesta al problema planteado:

Respuesta: ptimo = 0.04305 ( un 4,3% ).

Respuesta al problema planteado: La probabilidad mnima de ser despedido es 0.04305 , es decir de un

Estados: La cantidad de cargamentos disponibles para ser enviados en cada etapa.

La ruta ptima es:

B) Si enva 5 cargamentos, el ptimo es: MM$ 28, y la solucin ptima es: X 1 = 2 ; X2

Respuesta: Optimo =75; Solucin ptima: X1=2; X2=3; X3*=1

E. Orlando Rodrguez Gmez / Tarea de: Investigacin de operaciones II

También podría gustarte