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. PROBLEMA PRINCIPAL

¿Qué es un modelo dinámico?

1.1.2. 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. OBJETIVO PRINCIPAL

Saber que es un modelo dinámico.

1.2.2. 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í.

pág. 5

6. Inicio de solución: El procedimiento de solución se inicia al encontrar una política

óptima para la última etapa.

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).

pág. 6

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

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ónactual antes de tomar ladecisión

dn :Decisióna tomar encada etapa

rn :Contribuciónencadaetapa (Utilidad , costo , etc )

rn : f (xn , , dn)

f n: Integra la soluciónóptimade unaetapaconotra

f n ( s )=rn+ f∗¿n+1 ¿

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 5estudiantes(s) Taxi Custer Bus Miniban

Huacho –Huaura

Huaura- Supe

Supe – Barranca

RUTAS PARADERO RU COSTOCOSTO PARA 5

PERSONAS

TIPO DE MOVILIDAD

HUACHO – HUAURA

Av. San Martin - Plaza de Armas R1-R2 1.20 6.00 taxi

Av. San Martin - Panadería Aromi R1-R3 2.00 10.00 Custer

HUAURA – SUPE

Plaza de Armas - Plaza de Armas R2-R4 2.00 10.00 Taxi

Plaza de Armas – Mercado de Supe R2-R6 2.50 12.50 Miniban

Plaza de Armas – panadería Aromi R3-R4 2.20 11.00 custer

Panadería Aromi – Mercado R3-R5 3.00 15.00 Bus

SUPE - BARRANCA

Plaza de Armas - Plaza de Armas R4-R7 2.00 10.00 Taxi

Plaza de Armas - Mercado R5-R7 3.00 15.00 Custer

Plaza de Armas -JR Gálvez R6-R7 3.50 17.50 Miniban

pág. 8

R1

R2

R3

R4

R6

R5 R7

6.00

10.000

10.000

15.000

12.500

10.000

17.500

ETAPA N°3 ETAPA N°2 ETAPA N°1

15.0011.000

HUACHO HUAURA SUPE BARRANCA

SOLUCION

ETAPA 1:

ETAPA 2:

pág. 9

f1 = r1 + f*0

f2 = r2 + f*1

RUTA NOMBRE RUTA

HUACHO AV San Martin R1

HUAURAPlaza de Armas R2Panadería Aromi R3

SUPEPlaza de Armas R4Mercado Supe R5

BARRANCAMercado R6JR GALVEZ R7

f*1 d1

10.00 10.00

15.00 15.00

17.50 17.50

d1x1

R4

R6

R5

R7

R7

R7

R7

ETAPA 3:

La ruta óptima Mínima es:

a.

pág. 10

10.0010.006.00

F3 = r3 + f*2

f*=S/ 26.00

R1 R2 R7R4

f*2 d2

20.00 - 30.00 20.00

21.00 30.00 - 21.00

d2X2

R4 R6R5

R2

R3

R4

R4

f*3 d3

26.00 31.00 26.00

D3X3

R1

R2 R3

R2

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 Di Pi Wi Cp./u Cw./uENERO 15 11 9 120.00 10.00FEBRERO 10 9 8 100.00 20.00MARZO 10 15 7 90.00 10.00

SOLUCIÓN

Mes Di Pi Wi Cp./u Cw./uENERO 15 11 9 120.00 10.00FEBRERO 10 9 8 100.00 20.00MARZO 10 15 7 90.00 10.00

I0=5=X3

pág. 12

A. GRÁFICO POR ETAPAS

B. FUNCIÓN OBJETIVA:

Min r3=130d3+10x3-150 Min r2=120d2+20x2-200 Min r1=100d1+10x1-100

RESTRICCION

Almacén X3+d3-15≤9

X3+d3≤24

X2+d2-10≤8

X2+d2≤18

X1+d1-10≤7

X1+d1≤17

Producción d3≤11 d2≤9 d1≤15

Demanda X3+d3≥15 X2+d2≥10 X1+d1≥10

C.N.N: Xj, dj ≥ 0

pág. 13

FUNCIONES

CRITERIOS

ETAPA01 (Marzo):

ETAPA02 (Febrero):

pág. 14

f1=r1+f0 r1=100d1+10x1-100

f2=r2+f1*r2=120d2+20x2-200

ETAPA03 (Enero):

MES PRODUCCION(di) Cp/u I0 If Costo Inv. Costo Total

Enero 10 (10*120)=1200 5 0 0 1200

Febrero 9 (9*100)=900 0 0 0 900

Marzo 10 (10*90)=900 0 5 50 950

3050

C. RESUMEN:

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

f3=r3+f2* r3=130d3+10x3-150

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

*GRAFICO POR ETAPAS:

*Ingresamos el Producto “C”

*Ingresamos el Producto “B”

pág. 17

X0 = x1 – 2d1X1 = x2 – 2d2X2 = x3 – 2d3X3 = 8

d3 = ? d2 = ? d1 = ?

r3 = 4r3 r2 = 4r2r1 = 6r1

f1 = r1 + f0*

Como: f0* = 0 ; r1 = 6d1

Entonces: f1 = 6d1

PRODUCTO PESO (kg) BENEFICIOCuadernos (A) 1 4

Libros (B) 2 4Tableros de Ajedrez (C) 2 6

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

d2

X20 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

*Ingresamos el Producto “A”

*RESUMEN

PRODUCTO di Vi r

A 8 4 32

B 0 4 0

pág. 18

f2 = r2 + f1*Como: r2 = 4d2

Entonces: f2 = 4d2 + f1*

f3 = r3 + f2*Como: r3 = 4d3

Entonces: f3 = 4d3 + f2*

d3

X3

0 1 2 3 4 d3 f3 X2= X3 – d3

8 48 46 44 42 40 0 48 8,7,6,5,4

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

pág. 19

Región Factible

d3

d2

d1

(0; 0; 4)

(8; 0; 0)(0; 4; 0)

A

B

C

*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.

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