• Author / Uploaded
• carlos

Citation preview

UNIVERSIDAD NACIONAL JOSÉ FAUSTINO SÁNCHEZ CARRIÓN

FACULTAD DE INGENIERÍA INDUSTRIAL, SISTEMAS E INFORMÁTICA E.A.P. INGENIERÍA DE SISTEMAS INGENIERÍA DE OPERACIONES II

“MODELOS DINAMICOS: PROGRAMACIÓN DINÁMICA”

AUTORES: -

BERNABE GAVINO, Olga Lucero

-

CÓRDOVA RODRÍGUEZ, Willian Eduardo

-

INGA COLLANTES, Celia Beatriz

-

MAGUIÑA BELLIDO, Miguel Ángel

-

PEÑA NUÑEZ, Carlos Jesús.

PROFESOR: -

Dr. SOSA PALOMINO, Alcibiades.

CICLO: -

VII HUACHO – PERÚ 2015

INTRODUCCIÓN

La programación dinámica consiste en una técnica que permite determinar de manera eficiente las decisiones que optimizan el comportamiento de un sistema que evoluciona a lo largo de una serie de etapas. Las características esenciales que se puede encontrar en la programación dinámica es la versatilidad con respecto a la amplia gama de problemas que puede atacar y, por otra parte, que se limita a aportar un esquema de solución dejando al ingenio de quien resuelva el problema la construcción del modo matemático para realizar la optimización de cada caso en particular. Para una mejor comprensión de la manera en que trabaja este tipo de programación dinámica, se presentan 3 tipos de casos prácticos en con el fin de presentan soluciones de problemas aplicados a la realidad. El objetivo es presentar la potencia que tiene la Programación Dinámica, que proponerla como la remedio de los métodos de Investigación de Operaciones, pues también se verá que aunque funciona, en ocasiones de la técnica puede resultar impráctica al momento de resolver problemas de cierta envergadura.

pág. 2

ÍNDICE GENERAL CAPITULO I: PLANTEAMIENTO DEL PROBLEMA.........................................................4 1.1.

PLANTEAMIENTO DEL PROBLEMA................................................................4

1.1.1.

PROBLEMA PRINCIPAL..............................................................................4

1.1.2.

PROBLEMA ESPECÍFICO.............................................................................4

1.2.

PLANTEAMIENTO DE LOS OBJETIVOS...........................................................4

1.2.1.

OBJETIVO PRINCIPAL................................................................................ 4

1.2.2.

OBJETIVO ESPECÍFICO............................................................................... 4

1.3.

JUSTIFICACIÓN.............................................................................................. 4

CAPITULO II: MARCO DE TEORÍAS.............................................................................5 2.1.

MARCO TEÓRICO........................................................................................... 5

2.2.

MODELOS DE PROGRAMACION DINÁMICA....................................................6

2.3.

PROCEDIMIENTO GENERAL...........................................................................7

CAPÍTULO III: APLICACION........................................................................................ 8 3.1.

CASO I: PROBLEMA DE VIAJERO................................................................8

3.2.

CASO 2: PROBLEMA DE PRODUCCION.......................................................12

3.3.

CASO 3: PROBLEMA DE MOCHILA.............................................................16

4.1.

CONCLUSIONES...........................................¡Error! Marcador no definido.

4.2.

RECOMENDACIONES....................................¡Error! Marcador no definido.

CAPÍTULO V: REFERENCIAS..................................................................................... 21 5.1.

BIBLIOGRAFICAS......................................................................................... 21

5.2.

ELECTRONICAS........................................................................................... 21

pág. 3

CAPITULO I: PLANTEAMIENTO DEL PROBLEMA 1.1. PLANTEAMIENTO DEL PROBLEMA 1.1.1.  1.1.2.

PROBLEMA PRINCIPAL ¿Qué es un modelo dinámico? PROBLEMA ESPECÍFICO



¿Cuáles son los modelos dinámicos?



¿Cuáles son los pasos a seguir en una programación dinámica?



¿Cómo aplicar la programación dinámica en la realidad?

1.2. PLANTEAMIENTO DE LOS OBJETIVOS 1.2.1.  1.2.2.

OBJETIVO PRINCIPAL Saber que es un modelo dinámico. OBJETIVO ESPECÍFICO



Conocer cuáles son los modelos dinámicos.



Identificar cuáles son los pasos a seguir en una programación dinámica.



Saber cómo aplicar la programación dinámica en la realidad.

1.3. JUSTIFICACIÓN Se realiza el presente informe con los conocimientos previos en Investigación Operativa, como también teniendo una recapitulación previa de la información con respecto al tema, siendo el equipo de trabajo capaz de comprender y poder llegar a conocer los objetivos planteados. Siendo justificada la elaboración del presente trabajo por dichas razones.

pág. 4

CAPITULO II: MARCO DE TEORÍAS 2.1. MARCO TEÓRICO A. PROGRAMACIÓN DINÁMICA La programación dinámica permite resolver problemas complejos caracterizados por decisiones interrelacionadas, es decir, decisiones que se deben tomar en forma secuencial y las cuales influyen en las decisiones de estas secuencias. Finalmente se muestran los diversos tipos de programación dinámica existentes: •

PROGRAMACIÓN DINÁMICA NO HOMOGÉNEA

•

PROGRAMACION DINÁMICA DETERMINISTA.

B. CONCEPTUALIZACIÓN DE LA PROGRAMACIÓN DINÁMICA • En contraste con la programación lineal, no se cuenta con una formulación matemática estándar para “el” problema de Programación dinámica. • Se trata de un enfoque de tipo general para la solución de problemas y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual. • Se necesita un cierto grado de creatividad y un buen conocimiento de la estructura general de los problemas de Programación Dinámica para reconocer cuándo y cómo se puede resolver un problema por medio de estos procedimientos. C. CARACTERISTICAS DE PROGRAMACION DINAMICA 1. Etapas: El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas. 2. Estados asociados: Cada etapa tiene cierto número de estados asociados con su inicio. 3. Política de decisión: El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa. 4. Diseño de solución: El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para la política de decisión óptima en cada etapa para cada uno de los estados posibles. 5. Principio de optimalidad a) Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. b) La decisión inmediata óptima depende sólo del estado actual y no de cómo se llegó ahí. 6. Inicio de solución: El procedimiento de solución se inicia al encontrar una política óptima para la última etapa. pág. 5

7. Relación recursiva: Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n + 1. 8. Retroceso: Cuando se use esta relación recursiva, el procedimiento de solución comienza al final y se mueve hacia atrás etapa por etapa encontrando cada vez la política óptima para esa etapa – hasta que se encuentra la política óptima desde la etapa inicial. 2.2. MODELOS DE PROGRAMACION DINÁMICA Existen tres modelos diferentes:



Problema de la diligencia (Stagecoach Problem) Este problema está referido a encontrar la ruta óptima (ruta mínima o ruta más confiable), para viajar desde un punto llamado nodo inicial o fuente hacia otro llamado nodo final o destino a través de una red de caminos que los conecta dados los retornos (costos beneficios tiempo, etc.), asociados con los arcos o ramas de la red. El problema de la diligencia es una manera de reconocer una situación que se puede formular como un problema de programación dinámica y encontrar la ruta que minimiza el costo total de un nodo específico.



Problema de la mochila (Snapsack Problem) El modelo de la mochila tiene que ver con el hecho de determinar los artículos más valiosos que un combatiente carga en una mochila. El problema representa un modelo de asignación de recursos general en el cual se utilizan recursos limitados por varias actividades económicas. El objetivo es maximizar el rendimiento total. Al problema de la mochila también se le llama problema de conjunto de fuga o equipo de vuelo. El problema de la mochila consiste encontrar un subconjunto de productos que echar en una mochila de modo de maximizar el beneficio, no sobrepasar la capacidad de la mochila y que se cumplan ciertas restricciones.



Programación de producción e inventarios (Production and Inventory Scheduling). Este problema es de dirigir o regular el movimiento metódico de los materiales por todo el ciclo de fabricación, desde la requisición de materias primas, hasta la entrega del

pág. 6

producto terminado, mediante la transmisión sistemática de instrucciones a los subordinados, según el plan que se utiliza en las instalaciones del modo más económico". Para lograr el objetivo, la gerencia debe estar al tanto del desarrollo de los trabajos a realizar, el tiempo y la cantidad producida; así como modificar los planes establecidos, respondiendo a situaciones cambiantes.

2.3. PROCEDIMIENTO GENERAL Identificar las etapas En cada etapa identificar

X n :Situación actual antes de tomar ladecisión d n :Decisión a tomar en cada etapa r n :Contribución en cada etapa ( Utilidad , costo , etc ) r n :f ( x n , , d n ) f n : Integra la solución óptima de una etapa con otra f ∗¿n+ 1 f n ( s )=r n +¿ S: estado N: etapa Se resuelven los sub-modelos empezando por el fin.

pág. 7

CAPÍTULO III: APLICACION 3.1. CASO I: PROBLEMA DE VIAJERO FORMULACIÓN DEL PROBLEMA:

Un equipo de trabajo de 5 integrantes desea realizar un viaje con la finalidad de realizar un trabajo de investigación enfocado en la panadería Maritza que está ubicado en la ciudad de Barranca. Para realizar la visita a esta panadería se tomara el tipo de movilidad que me genere menos costo (pasaje) para poder llegar hacia el paradero y así poder seguir la ruta. Se quiere saber cuál es el costo mínimo y la ruta óptima con ese costo mínimo. Para esto se proporciona el siguiente cuadro. Costo para 5 estudiantes(s) Huacho –Huaura

Taxi

Custer

Bus

Miniban

Huaura- Supe Supe – Barranca

RUTAS

HUACHO – HUAURA

HUAURA – SUPE

SUPE BARRANC A

PARADERO Av. San Martin Plaza de Armas Av. San Martin Panadería Aromi Plaza de Armas Plaza de Armas Plaza de Armas – Mercado de Supe Plaza de Armas – panadería Aromi Panadería Aromi – Mercado Plaza de Armas Plaza de Armas Plaza de Armas Mercado Plaza de Armas JR Gálvez

RU

COSTO

COSTO PARA 5 PERSONAS

TIPO DE MOVILIDA D

R1-R2

1.20

6.00

taxi

R1-R3

2.00

10.00

Custer

R2-R4

2.00

10.00

Taxi

R2-R6

2.50

12.50

Miniban

R3-R4

2.20

11.00

custer

R3-R5

3.00

15.00

Bus

R4-R7

2.00

10.00

Taxi

R5-R7

3.00

15.00

Custer

R6-R7

3.50

17.50

Miniban

pág. 8

RUTA

NOMBRE

HUACHO

AV San Martin Plaza de Armas Panadería Aromi Plaza de Armas Mercado Supe Mercado JR GALVEZ

HUAURA

SUPE BARRAN CA

RUT A R1 R2 R3 R4 R5 R6 R7 SOLUCION

HUACHO

HUAURA

SUPE

BARR

10.000 R4

R2

6.00

12.500 15.00

R1

11.000

10.000

R3

ETAPA N°3

15.000

ETAPA N°2

17.500

ETAPA N°1

f1 = r1 + f*0

ETAPA 1:

x 1

R7

R5

R6

d 1

10.000

R7

f*1

d1

R4

10.00

10.00

R7

R5

15.00

15.00

R7

R6

17.50

17.50

R7

ETAPA 2:

f2 = r2 + f*1 pág. 9

d 2

X 2

R4

R5

f*2

d2

R2

20.00

-

30.00

20.00

R4

R3

21.00

30.00

-

21.00

R4

ETAPA 3:

X 3

R6

F3 = r3 + f*2

D 3

R1

R2

R3

26.00

31.00

f*3

d3

26.00

R2

R4

10. 00

La ruta óptima Mínima es:

a. R1

6.0 0

R2

10. 00

R7

f*=S/ 26.00

pág. 10

Conclusión 

Se concluye que el equipo de trabajo de investigación que está formado por 5 integrantes gastará un monto de S/ 26.00 en pasaje de acuerdo al tipo de movilidad que genere menos costo, desde una ruta específica hacia otra; para poder llegar



hacia el lugar destino de la cuidad de Barranca. En la programación dinámica, el problema de Viajero nos ayuda poder encontrar la ruta óptima, para viajar desde un punto llamado inicial hacia otro punto final a través de una red de caminos que puede ser costo, tiempo, capacidad entre otros.

Recomendación  Se recomienda que para minimizar más el costo, viajar en un mismo tipo de movilidad que podría ser bus o custer, toda la ruta desde Huacho hacia Barranca y con esto tener un gasto menor en pasaje ya que de no ser así se gastaría más dinero en el pasaje que emprenderás hacia el destino dado de la cuidad de Barranca.

pág. 11

3.2. CASO 2: PROBLEMA DE PRODUCCION 1. FORMULACIÓN DEL PROBLEMA La Sra. Margarita Camones Zavala, es dueña de un negocio dedicada a la elaboración de carteras, ubicado en el mercado central de Barranca, ella ha estimado de forma aproximada y en base a su experiencia, la demanda de carteras para los meses de Enero, Febrero y Marzo; su objetivo es saber la cantidad de carteras que debe elaborar para satisfacer la demanda de sus clientes a un costo mínimo. 2. TABLA DE PRODUCCIÓN La siguiente tabla muestra los datos brindados por la Sra. Margarita Camones Zavala: La demanda para los meses de Enero, Febrero y Marzo son de 15, 10 y 10 carteras respectivamente. Las capacidades de producción son de 11, 9 y 15 carteras; las capacidades de almacenaje son 9, 8, 7 carteras respectivamente. Los costos de producción varían de un mes a otro, estos son: S/.120.00, S/100.00 y S/90.00, todo ello debido a que los insumos utilizados pueden ser distintos (otra calidad, diferente color, entre otros) o pueden variar en cuanto a sus precios. Inventario Inicial=5 unidad

Mes ENERO FEBRERO MARZO

Di

Pi

Wi

Cp./u

Cw./u

15 10 10

11 9 15

9 8 7

120.00 100.00 90.00

10.00 20.00 10.00

SOLUCIÓN

Mes ENERO FEBRERO MARZO

Di

Pi

Wi

Cp./u

Cw./u

15 10 10

11 9 15

9 8 7

120.00 100.00 90.00

10.00 20.00 10.00

I0=5=X3

pág. 12

A. GRÁFICO POR ETAPAS

B. FUNCIÓN OBJETIVA: FUNCION ES Min r3=130d3+10x3-150

Min r2=120d2+20x2-200

Min r1=100d1+10x1-100

CRITERI ROS E Almacén S T R I C Producción C I O Demanda N

X3+d3-15≤9

X2+d2-10≤8

X1+d1-10≤7

X3+d3≤24

X2+d2≤18

X1+d1≤17

d3≤11

d2≤9

d1≤15

X3+d3≥15

X2+d2≥10

X1+d1≥10

C.N.N: Xj, dj ≥ 0

pág. 13

ETAPA01 (Marzo):

f1=r1+f0

r1=100d1+10x1-100

ETAPA02 (Febrero):

f2=r2+f1*

r2=120d2+20x2-200

pág. 14

ETAPA03 (Enero):

f3=r3+f2*

r3=130d3+10x3-150

C. RESUMEN:

MES

PRODUCCION(di )

Cp/u

I0

If

Costo Inv.

Costo Total

Enero

10

(10*120)=120 0

5

0

0

1200

Febrero

9

(9*100)=900

0

0

0

900

Marzo

10

(10*90)=900

0

5

50

950

3050

 El costo mínimo es S/.3050.00. Conclusiones 

Después de haber realizado el análisis, se concluye que la Sra. Margarita Camones Zavala, deberá producir para el mes de Enero 10 carteras, Febrero 9 carteras y Marzo 10 carteras el cual resulta un costo mínimo de S/.3050.00.



En la programación Dinámica, el problema de producción nos ayuda a determinar un programa de producción para un periodo de tiempo con el fin de minimizar los costos.

Recomendaciones 

Se le recomienda a la Sra. Margarita Camones Zavala, aumentar su producción en el mes de Enero para obtener una mejor rentabilidad en el negocio.



Se recomienda a la Sra. Margarita Camones Zavala adquirir maquinarias que le ayuden a optimizar el trabajo en la elaboración de carteras. pág. 15

3.3. CASO 3: PROBLEMA DE MOCHILA 3. FORMULACIÓN DEL PROBLEMA Los profesores del C.E: “José Olaya Balandra” ya estando próximo el final de año escolar, han decidido entregar un pequeño presente al alumno que ha mostrado mayor desempeño desde primero hasta quinto de secundaria para ello han decidido que el obsequio este conformado por: Cuadernos, Libros, Tableros de ajedrez; dado que el colegio recibió estos elementos como donaciones. -Se sabe que:  El obsequio no debe pesar más de 8 kg  Los pesos unitarios de los cuadernos, libros y tableros de ajedrez son 1kg, 2kg y 2kg respectivamente  Se estima que en una escala de 0 a 10 el beneficio unitarios que tienen los cuadernos, libros y tableros de ajedrez son de 4, 4 y 6 -Se pide un informe que contenga:  Formular el modelo de programación lineal para dar solución a este problema.  Elaborar el grafico por etapas.  Determinar la selección optima de la cantidad de elementos que debemos ingresar como obsequio para el mejor alumno. -Además:  Resolver el modelo de programación lineal y compare los resultados. SOLUCIÓN:

1. Modelo de Programación Lineal: Declaramos la variable: di : Cantidad de producto “ i “ a ingresar FUNCIÓN OBJETIVO: Max Z = 4d1 + 4d2 + 6d3 RESTRICCIONES: d1 + 2d2 + 2d3 ≤ 8 ∀ di ≥ 0, i = 1, 2, 3 2. Elaboración del Grafico por Etapas: *MATRIZ PESO-BENEFICIO: pág. 16

Inventario Inicial: Capacidad 8 Kg PRODUCTO Cuadernos (A) Libros (B) Tableros de Ajedrez (C)

PESO (kg) 1 2 2

BENEFICIO 4 4 6

*GRAFICO POR ETAPAS:

d3 = ?

d2 = ?

X3 = 8

X2 = x 3 – 2d3

d1 = ? X0 = x1 – 2d1

X1 = x 2 – 2d2

r3 = 4r3

r1 = 6r1

r2 = 4r2

*Ingresamos el Producto “C” X1

d1

f1

0

0

0

1

1

6

2

2

12

3

3

18

4

4

24

5

5

30

6

6

36

7

7

42

8

8

48

f1 = r1 + f0* Como:

f 0* = 0

;

r1 =

6d1

*Ingresamos el Producto “B” f2 = r2 + f1* Como:

r2 = 4d2

pág. 17

d2

0

1

2

3

4

5

6

7

8

d2

f2

X1= X2 – 2d2

0

0

-

-

-

-

-

-

-

-

0

0

0

1

6

-

-

-

-

-

-

-

-

0

6

1

2

12

4

-

-

-

-

-

-

-

0

12

2,0

3

18

10

-

-

-

-

-

-

-

0

18

3,1

4

24

16

8

-

-

-

-

-

-

0

24

4,2,0

5

30

22

14

-

-

-

-

-

-

0

30

5,3,1

6

36

28

20

12

-

-

-

-

-

0

36

6,4,2,0

7

42

34

26

18

-

-

-

-

-

0

42

7,5,3,1

8

48

40

32

24

16

-

-

-

-

0

48

8,6,4,2,0

X2

*Ingresamos el Producto “A”

f3 = r3 + f2* r3 = 4d3

Como:

d3 X3 8

0

1

2

3

4

d3

f3

X2= X3 – d3

48

46

44

42

40

0

48

8,7,6,5,4

*RESUMEN

PRODUCTO

di

Vi

r

A

8

4

32

B

0

4

0 pág. 18

C

0

6

0

TOTAL BENEFICIO

32

*RESULTADO O DECISION: Los profesores deberán incluir en el obsequio solamente 8 libros, para así obtener un beneficio máximo total de 32. 3.- Resolución del Modelo de Programación Lineal: GRAFICAMOS: d1 + 2d2 + 2d3 ≤ 8 d3

B

(0; 0; 4)

Región Factible

C A d1

d2

(8; 0; 0)

(0; 4; 0)

pág. 19

*Evaluación:

PUNTO

Z = 4d1 + 4d2 + 6d3

A = (8;0;0)

Z = 32

B = (0;0;4)

Z = 24

C = (0;4;0)

Z = 16

CONCLUSION Los profesores deberán incluir en la mochila solamente 8 libros, para así obtener un beneficio máximo total de 32.

pág. 20

CAPÍTULO V: REFERENCIAS 4.1. BIBLIOGRAFICAS Joan B. – José M. (2002):”Métodos Cuantitativos de organización Industrial ll”. Ed. UPC E. Arbones, E. Arbones M (1989): “Optimización Industrial II: Programación de recursos”. Ed. Marcombo M. Rodriguez, B. Perez, S. Alonso (1997) “Optimización dinámica: Teoría del control óptimo” Ed. Universidad Oviedo J. Prawda (2000) “Métodos y modelos de investigación de operaciones” Ed. Limusa. Taha, H. A. (2005) “Investigación de Operaciones”. Hiller, F. S. (2008) “Introducción a la Investigación de Operaciones”.

4.2. ELECTRONICAS Programación Dinámica. Consultado en: http://es.slideshare.net/ajmae28/programacin-dinmica[6, noviembre, 2015]

Aplicación de la Programación Dinámica. Consultado en: http://io2ramosmarm.blogspot.com/2011/08/programacion-dinamica.html

[7, noviembre, 2015]

pág. 21