INSTITUTO TECNOLOGICO DE PIEDRAS NEGRAS

TRABAJO:

EJERCICIOS DE UNIDAD 1

ALUMNO:

JOSE ARTURO MARTINEZ BRISEÑO

MAESTRO:

LUIS MANUEL GARCIA PIZARRO

MATERIA:

INVESTIGACION DE OPERACIONES II

CARRERA:

ING. INDUSTRIAL

PIEDRAS NEGRAS COAHUILA, 16 DE JULIO DEL 2013

1.2 EJEMPLOS DE MODELOS 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 cuál 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.

1.4 Programación Dinámica Probabilística.

En la programación dinámica probabilística, el estado en la etapa siguiente no queda completamente determinado por el estado y la decisión de la subpolítica en el estado actual, sino que existe una distribución de probabilidad para lo que sería el estado siguiente.

Gráficamente tenemos:

Ejemplo 1

Una compañía ha recibido un pedido para surtir un solo artículo muy especial y de una calidad tan rigurosa que es posible que el fabricante tenga que producir más de un artículo para obtener uno aceptable. La probabilidad estimada para que sea aceptable es 1/3 y de que sea defectuoso sin posibilidad de reparación 2/3. Por lo tanto la probabilidad de producir cero artículos aceptables en un lote de tamaño L es (2/3)L.

Los costos marginales de producción son de $ 100 por artículo, incluso si es defectuoso (los artículos en exceso no tienen valor). El costo de preparación es $ 200, cada vez que se monte el proceso de producción de este artículo, el cual puede hacerlo como máximo 3 veces. Si no se ha obtenido un artículo aceptable al final de la tercera serie de producción, el costo por ventas perdidas y de penalización será de $ 1500. El objetivo es determinar la política referente al tamaño del lote para las series de producción de manera de minimizar el costo total esperado.

Solución:

Etapas: Series de producción (1, 2, 3).

Variables de decisión: Xn: Son el tamaño del lote producción en la etapa n.

Estados: Sn : puede suceder que, Sn =0 si el articulo aceptable se logro en la etapa anterior. o Sn =1 que significa que en la etapa anterior no se logró el articulo aceptable.

f*n (Sn) = Mín fn(Sn,Xn)

Xn = 0, 1, ..., L (tamaño del lote, costo marginal)

Donde:

f*n (0) = 0 y S = 0 , cuando se ha obtenido en la etapa anterior un artículo

aceptable, por lo tanto f*n (0) = 0, en esta etapa no es necesario que se

incurra en gastos adicionales.

(Prob. de 0 art. acept. ( prob de 1 art. Acept.)

f*n (Sn,Xn) = K + Xn + (2/3)Xn fn + 1 (1) + ( 1- (2/3)Xn) fn + 1

(0)

donde:

( 1- (2/3)Xn) fn + 1 (0) = 0 costo marginal

luego

f*n (1,Xn) = K + Xn + (2/3)Xn f*

n + 1 (1).

Considerando $ 100 como unidad monetaria y definiendo

0 Si Xn = 0 K = 2 Si Xn 0 (costo de preparación)

(ETAPA ANTERIOR NO SE LOGRO ART. ACEPTABLE)

f*4 (1) = 15 , que es el costo de no obtener un artículo aceptable y perder la

venta.

f*4 (0) SI SE LOGRO ART.ACEPT.

Luego, para n = 3 tendríamos:

f3(1, X3) = K + X3 + (2/3)X3 15

S3 /X3 0 1 2 3 4 5 f*3(1) X*

3

0 0

1 15 13 10 2/3 9 4/9 8 26/27 8 79/81 8 26/27 4

Para n = 2:

F2(1, X2) = K + X2 + (2/3)X2 8 26/27S2 /X2 0 1 2 3 4 f*

2(1) X*2

0 01 8 26/27 8 79/81 7 239/243 7 478/729 7 1685/2187 7 478/729 3

Para n = 1

f1(1, X1) = K + X1 + (2/3)X1 7 478/729 S1 /X1 0 1 2 3 4 f*

1(1) X*1

1 7.655 8.1 7.4 7.27 7.51 7.27 3

Luego la solución del problema es la siguiente:

En la primera serie de producción deben fabricarse 3 artículos, si se obtiene un articulo aceptable, X2 = X3 = 0. Si son defectuosos en la segunda se debe fabricar 3 artículos, si se obtiene un articulo aceptable X3 = 0. Si son defectuosos en la tercera serie de producción deben fabricarse 4 artículos, todo con un costo esperado de $ 727.-

1.3 Programacion Dinamica Deterministica

Problema 1Cierto estudiante desea destinar los siete dias de la semana proxima a estudiar cuatro cursos. Necesita al menos un dia para cada curso y el

puntaje que puede lograr se da en la siguiente tabla:¿Cuantos dias debe estudiar cada curso para lograr un puntaje?

BIBLIOGRAFIA

http://webcache.googleusercontent.com/search?q=cache:qUatiE1xc4MJ:prontus.uv.cl/pubacademica/pubprofesores/c/pubcalvosergio/site/artic/20070410/asocfile/

apunte_prog_dinamica.doc+ejemplos+de+programacion+dinamica+deterministica&cd=40&hl=es&ct=clnk&gl=mx

http://webcache.googleusercontent.com/search?q=cache:vqOcwB1xj9IJ:https://www.u-cursos.cl/forestal/2009/1/EF046/1/material_docente/objeto/481171+ejemplos+de+programacion+dinamica+resueltos&cd=2&hl=es&ct=clnk&gl=mx

http://marcosinvopeiiucv.blogspot.mx/2011/05/programacion-dinamica-deterministica.html

INDICE

1.1 CARACTERISTICAS DE LOS PROBLEMAS DE PROGRAMACION DINAMICA

1.2 EJEMPLOS DE MODELOS DE PROGRAMACION DINAMICA

1.3 PROGRAMACION DINAMICA DETERMINISTICA

1.4 PROGRAMACION DINAMICA PROBABILISTICA

1.1 CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA

La programación dinámica (PD) es un procedimiento matemático diseñado principalmente para mejorar la eficiencia de cálculo de problemas de programación matemática seleccionados, descomponiéndolos en subproblemas de menor tamaño y por consiguiente, más fáciles de calcular.

Características de la programación dinámica

1. El problema puede dividirse en etapas, con una decisión de la política requerida en cada etapa.El problema de la diligencia se dividió literalmente es sus cuatro “etapas”, correspondientes a las cuatro jornadas del viaje. La decisión de una política en cada etapa fue el destino para esa jornada particular (es decir, cual política de seguro de vida a elegir).

2. Cada etapa tiene un cierto número de estados asociados a ella. Los estados asociados con cada diligencia fueron los estados (o territorios) en los que el vendedor podía estar localizado al embarcarse en esa jornada particular del viaje.

3. En efecto de la decisión de una política en cada etapa es transformar el estado actual en un estado asociado a la etapa siguiente (posiblemente de acuerdo con una distribución de probabilidad).

4. Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en las etapas previas.

5. El procedimiento de resolución empieza por hallar la política optima para cada estado de la última etapa.

6. Se dispone de una relación recursiva que identifica la política óptima para cada estado en la etapa n, dada la política optima para cada estado en la etapa (n+1).