EJERCICIOS DE INVESTIGACION OPERATIVA

Investigación de Operaciones - I

Ejercicios de Programación Dinámica en variable discreta

A continuación se presentan 5 ejercicios resueltos de Programación Dinámica en variable discreta, y se dejan otros 5 ejercicios planteados para que Ud. los resuelva.

Profesor: Juan Barrios M. ---- Ayudantes: Ramón González – Daniela Romero

(Consultas sobre esta guía hacerlas a:)

EJERCICIOS RESUELTOS DE PROGRAMACIÓN DINAMICA

1.- Un Ingeniero Forestal, requiere saber: i)Cuál es el costo mínimo, y ii)Cuál es la ruta con ese costo mínimo, 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:

Solución:

Para ir de 1 a 13 hay 48 rutas posibles. Una posibilidad para encontrar la solución 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 método de la programación Dinámica, 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.

Cálculos n = 4 S \ X4 13 F4* X4*

9 12 12 13

10 16 16 13

11 15 15 13

12 14 14 13

n = 3 S \ X3 9 10 11 12 F3* X3*

6 3+12=15 2+16=18 1+15=16 3+14=17 15 9

7 4+12=16 1+16=17 4+15=19 6+14=20 16 9

8 2+12=14 3+16=19 6+15=21 5+14=19 14 9

n=2 S \ X2 6 7 8 F2* X2*

2 9+15=24 4+16=20 6+14=20 20 7 - 8

3 5+15=20 7+16=23 4+14=18 18 8

4 9+15=24 10+16=26 8+14=22 22 8

5 9+15=24 10+16=26 11+14=25 24 6

n = 1 S \ X1 2 3 4 5 F1* X1*

1 7+20=27 6+18=24 5+22=27 6+24=30 24 3

Respuesta: El óptimo es: 24

La solución óptima es: X1 = 3 ; X2 = 8 ; X3= 9 ; X4= 13.

La ruta óptima es: 1  3  8  9  13

Respuesta al problema planteado:

El Ingeniero Forestal tiene un costo mínimo de $24 para ir desde su oficina al lugar de cosecha, y ese mínimo 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 Técnico Forestal, debe revisar 3 faenas: Poda, Raleo y Cosecha, y dispone de 4 días. Según la dedicación en días que le de a cada faena, éstas tendrán una probabilidad de fracasar, y con ello fracasar la faena total, por lo que puede ser despedido. Por ello, dicho Técnico desea minimizar la probabilidad de ser despedido minimizando la probabilidad de que las 3 tareas fracasen al mismo tiempo.

Dedicación \ Faenas Poda Raleo Cosecha

0 día 0.50 0.60 0.40

1 día 0.42 0.51 0.35

2 días 0.36 0.41 0.21

3 días 0.25 0.36 0.18

Un día no asignado a una faena no tiene valor asociado. A lo más se puede asignar 3 días a una misma faena.

Solución:

Etapas: Son 3. La etapa 1 es el proceso de asignación de días a Poda. La etapa 2 es el proceso de asignación de días a Raleo. La etapa 3 es el proceso de asignación de días a Cosecha.

Estados: Son los días 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 días disponibles para ser asignados.

Las variables de decisión son 3: X1, X2, X3 y representan: Cuántos días asignar a la faena poda, Cuántos días asignar a la faena de raleo, Cuántos días asignar a la faena de cosecha; respectivamente.

La Función 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 días disponibles desea minimizar esa probabilidad.

Los cálculos.

n = 3 S \ X3 0 1 2 3 F3* X3*

0 0.4*1=0.40 - - - 0.40 0

1 0.4*1=0.40 0.35*1=0.35 - - 0.35 1

2 0.4*1=0.40 0.35*1=0.35 0.21 - 0.21 2

3 0.4*1=0.40 0.35*1=0.35 0.21 0.18 0.18 3

4 0.4*1=0.40 0.35*1=0.35 0.21 0.18 0.18 3

n = 2

S\X2 0 1 2 3 F2* X2*

1 0.6*0.35=0.210 0.51*0.40=0.2040 - - 0.2040 1

2 0.6*0.21=0.126 0.51*0.35=0.1785 0.41*0.40=0.1640 - 0.1260 0

3 0.6*0.18=0.108 0.51*0.21=0.1071 0.41*0.35=0.1435 0.36*0.40=0.144 0.1071 1

4 0.6*0.18=0.108 0.51*0.18=0.0918 0.41*0.21=0.0861 0.36*0.35=0.1260 0.0861 2

n = 1

S\X1 0 1 2 3 F1* 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 0.04305 0

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

La solución óptima es: X1 = 0 ; X2 = 2 ; X3= 2

La ruta óptima es: 4  4  2  2

Respuesta al problema planteado: La probabilidad mínima de ser despedido es 0.04305 , es decir de un 4,3%, y la asignación óptima de días es: 0 días a la Poda, 2 días al Raleo, 2 Días a la Cosecha.

3.- Un aserradero debe enviar 4 o 5 cargamentos a cuatro destinos. La máxima asignación para cada destino es de cuatro cargamentos. En la tabla siguiente se indica g(xi) como los ingresos en MM$ obtenidos por cada una de las decisiones posibles. Se desea maximizar el ingreso del aserradero por estos envíos.

Además al destino 2 no se puede asignar 4 sino que máximo 3 cargamentos. Al destino 3 ya se ha decidido asignar exactamente 1 cargamento. Un cargamento no asignado no tiene valor asignado.

 cargamentos \ destinos 1 2 3 4

0 0 0 0 0

1 5 6 4 7

2 11 10 12 10

3 15 16 17 14

4 21 - 22 23

Solución:

Etapas: son 4 etapas. La etapa 1,2,3,4 es el proceso de decisión de envíos de cargamento al destino 1, destino 2, destino 3 y destino 4 respectivamente.

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

El modelo en este caso es: (Son 2 problemas en uno).

P: Máx (  g(xi); i=1,2,3,4) s.a: X1+X2+X3 +X4  5 ; Xi 0,1,2,3,4;

...