• Author / Uploaded
• Paolo

• Categories
• Inventario
• Camión
• Business

Citation preview

INVESTIGACION OPERATIVA II CUARTO LABORATORIO: PROGRAMACION DINAMICA 1. Haciendo uso de la programación dinámica, encontrar la ruta más corta de la ciudad de Munbai a Kolkata. Crear la función recursiva para este tipo de problema

2. Use la programación dinámica para encontrar: La ruta más corta, La ruta más larga desde S hasta T en cada uno de las siguientes redes

3. Un camionero que trabaja por su cuenta tiene 8 m3 de espacio disponible en un camión que saldrá para la ciudad de Lima. Un distribuidor que tiene grandes cantidades de tres artículos diferentes, todos destinados para esa ciudad, ha ofrecido al camionero los siguientes pagos por transportar tantos artículos como quepan en el camión: Artículo

Pago, $/articulo

Volumen m3/articulo

I

11

1

II III

32 58

3 5

¿Cuántas unidades de cada artículo deberá aceptar el camionero a fin de maximizar los pagos de embarque, sin exceder la capacidad disponible del camión? 4. Una compañía tiene 3 tipos de artículos para ser transportados de una ciudad a otra, el precio a pagar a un transportista depende el peso de cada artículo, como se detalla a continuación. Articulo A B C

Peso (toneladas) 1 2 3

Valor ($/ton) 120 250 500 1

La condición que pone la compañía es que se trasporte al menos 1 artículo de cada uno. La capacidad del camión del transportista es de 10 toneladas. ¿Qué cantidades de cada artículo debe llevar el transportista para maximizar su utilidad. Utilice programación dinámica para dar su respuesta. 5. Cuatro compañías han solicitado que un lanchón de carga capaz de transportar hasta 10 toneladas de material, lleve sus mercancías de San Luis a Nueva Orleans. Cada compañía puede suministrar tanta mercancía como el capitán del lanchón desee aceptar. La mercancía deberá ser embarcada en cantidades limitadas. La tabla siguiente da los costos de embarque. Compañía I II III IV

Peso de la mercancía, ton/art. 1 2 3 4

Costo de embarque, $/art. 10 25 45 60

¿Cuántos artículos de la mercancía de cada compañía deberá aceptar el capitán del lanchón, a fin de maximizar las cuotas totales de embarque, sin exceder la capacidad del lanchón? 6. Un excursionista planea salir de campamento. Hay cinco artículos que desea llevar consigo, pero entre todos sobrepasan las 60 libras que considera que puede cargar. Para auxiliarse en la selección, ha asignado un valor a cada artículo en orden ascendente de importancia: Articulo Peso, libras Valor

1 52 100

2 23 60

3 35 70

4 15 15

5 7 15

¿Qué artículos deberá llevar para maximizar el valor total, sin sobrepasar la restricción de peso? 7. El siguiente cuadro especifica los pesos y valores de cinco productos en los depósitos. La cantidad de cada artículo es ilimitado.

Un avión con una capacidad de 13 unidades de peso es utilizado para el transporte de los productos. ¿Cómo se debe cargar el avión para maximizar el valor de los bienes enviados? (Formule el problema como un programa entero y resolver mediante programación dinámica.) 8. Una fábrica de láminas de fierro galvanizado ha recibido pedidos de cuatro diferentes fabricantes de cajas de fierro galvanizado, de la siguiente manera: Beneficio por rollo Pedido 1: 2 rollos de 20 Cm. de ancho b1 = $4.5/rollo Pedido 2: 2 rollos de 25 Cm. de ancho b2 = $5/rollo Pedido 3: 4 rollos de 40 Cm. de ancho b3 = $9.5/rollo Pedido 4: 6 rollos de 55 Cm. de ancho b4 = $13.5/rollo La fábrica tiene 2 rollos de 210 Cm. de ancho de láminas de fierro galvanizado para atender estos pedidos. Ordenes parciales pueden ser satisfechas. ¿Cuáles órdenes y cuanto de cada una se deben satisfacer para maximizar el beneficio total?. Que pedidos quedan pendientes por atender y que cantidad? 9. Una persona tiene $ 4000 que desea invertir y se le presentan 3 opciones. Cada opción requiere depósitos en cantidades de $ 1000; el inversionista puede colocar todo el dinero entre las tres. Las ganancias esperadas se presentan en las tablas siguientes: 2

Dólares invertidos 1000 2000 3000 2000 5000 6000 1000 3000 6000 1000 4000 5000

0 0 0 0

Ganancia en la oportunidad 1 Ganancia en la oportunidad 2 Ganancia en la oportunidad 3

4000 7000 7000 8000

¿Cuánto dinero deberá invertirse en cada opción para obtener la mayor ganancia total? 10. Una consultoría en organización está auditando una empresa. Para lograr que esta sociedad obtenga mejores resultados, propone un plan de inversiones industriales para el año siguiente. La financiación estará asegurada por aportaciones exteriores y por el margen neto de autofinanciación. Se estima que el valor de la financiación total se eleva a 30 millones de soles y servirá para acometer las principales acciones a tomar a corto plazo. Estas acciones se desarrollarán por dos vías: por una parte el aumento de la productividad y por la otra, la disminución de los costes logísticos. Primera vía: Aumento de la productividad. Es la solución A. Consiste en la adquisición hasta un máximo de 10 máquinas-herramientas con control numérico, con un coste unitario de dos millones de soles. Segunda vía: Disminución de los costos logísticos. Prevee tres posibles soluciones no incompatibles entre sí. — La solución B supone la adquisición de un paquete informático de gestión de producción asistida por ordenador, cuyo coste es de cuatro millones de soles por módulo, con un máximo de cinco módulos. — La solución C consiste en la construcción de depósitos de almacenamiento por un valor unitario de 10 millones. — La solución D consiste en la adquisición de sendos paquetes informáticos de gestión de rutas de entrega y de implantación por valores respectivos de 4 y 2 millones de soles, pudiéndose completar el lote con un tercer paquete para el seguimiento de pedidos cuyo valor asciende a 6 millones. Los estudios de rentabilidad han permitido obtener la tabla siguiente en la que se describen los beneficios que se pueden obtener para cada una de las soluciones en función de la inversión realizada. Beneficios (en millones de soles) Inversión (en millones soles) 2

0.5

0

0

0

4 6 8 10 12 14 16 18 20

1.0 1.5 2.0 2.4 2.7 2.9 3.0 3.1 3.2

1.2 1.2 2.2 2.2 3.0 3.0 3.4 3.4 3.6

0 0 0 2.6 2.6 2.6 2.6 2.6 4.0

0 1.2 1.2 1.2 2.8 2.8 2.8 2.8 2.8

A

B

C

30 3.2 3.6 5.0 Tabla: Beneficios según el tipo de solución y el volumen de inversión.

D

2.8

Se trata de establecer un modelo que nos proporcione el reparto óptimo de la inversión de los 30 millones de soles 11. David Vázquez, contador público, ha recibido ofertas de tres diferentes clientes que desean sus servicios. A cada cliente le gustaría que el señor Vázquez trabajara para él de tiempo completo; sin 3

embargo, cada cliente está deseoso de emplear al señor Vázquez por tantos días semanales como él pueda hacerlo, por los honorarios que se muestran en la tabla siguiente. ¿Cuántos días deberá dedicar el señor Vázquez a cada cliente para maximizar su ingreso semanal? Número de días 0 1 2 3 4 5

Cliente 1, $ Cliente 2, $ Cliente 3, $ 0 100 250 400 525 600

0 125 250 375 500 625

0 150 300 400 550 650

12. Resuélvase nuevamente el problema 11 con la restricción adicional de que el señor Vázquez trabaje al menos 1 día a la semana para cada cliente. (Consejo: Penalícese la posibilidad de trabajar 0 días para cualquier cliente. También puede utilizar los métodos estudiados en clase ) 13. Una pequeña compañía puede fabricar hasta cuatro computadoras especiales por semana y se ha comprometido a entregar en cada una de las siguientes 4 semanas tres, dos, cuatro y dos computadoras, respectivamente. Los costos de producción están en función del número de computadoras fabricadas y se dan (en miles de dólares) como sigue: Unidades producidas, x Costo 𝑓(𝑥)

0 4

1 13

Semanas 2 19

3 27

4 32

Las computadoras pueden entregarse a los consumidores al final de la misma semana en que se fabrican o pueden almacenarse para su entrega futura, con un costo de $400 por semana. Debido a la capacidad limitada de almacenamiento, la compañía no puede almacenar más de tres computadoras a un tiempo. El inventario actual es cero y la compañía no desea ningún inventario al final de la semana 4. ¿Cuántas computadoras deberán fabricarse en cada una de las siguientes cuatro semanas, para cumplir todas las demandas a un costo mínimo total? 14. Un fabricante tiene una orden de 12 locomotoras diesel, las cuales serán entregadas tres cada año durante los próximos 4 años. Los datos de producción se presentan en la tabla siguiente. Las locomotoras pueden entregarse al final del mismo año en que se producen, o el fabricante puede almacenarlas a un costo anual de $ 30 000 por locomotora, para ser embarcadas en un año posterior. Por lo general, el fabricante tiene una locomotora almacenada y desearía incrementar este inventario a tres al final de cuatro años. Determínese un programa de producción que cubra todos los requisitos a un costo total mínimo. Años 1

2

3

4

Capacidad de producción (turno normal)

1

2

3

4

Capacidad de producción (tiempo extra)

2

2

3

2

$350 000

$370 000

$395 000

$420 000

$375 000

$400 000

$430 000

$465 000

Costo por máquina (turno normal) Costo por máquina (tiempo extra)

15. Obténgase la fórmula de recursión para el siguiente problema. Un candidato a la presidencia necesita 100 votos electorales para asegurar su nominación por parte del partido mayoritario. Quedan por realizarse cinco elecciones primarias en las que el ganador se lleva todo, y el candidato tiene 10 unidades de dinero disponibles para gastar en ellas. La probabilidad de ganar una elección primaria está en función de la cantidad de dinero gastada en ella, como se muestra en la tabla siguiente: Unidades de dinero gastado

Primaria 1 Primaria 2 Primaria 3 Primaria 4 Primaria 5

0 0.10 0.15 0.05 0.20 0.17

1 0.15 0.21 0.12 0.25 0.22

2 0.25 0.27 0.17 0.31 0.29

3 0.38 0.40 0.22 0.38 0.30

4 0.44 0.45 0.27 0.45 0.38

5 0.48 0.51 0.31 0.52 0.44

6 0.54 0.56 0.35 0.59 0.51

7 0.60 0.61 0.38 0.67 0.55 4

La probabilidad de ganar cualquier elección primaria no aumenta si se asignan más de 7 unidades de dinero. En la elección primaria 1 están en juego 89 votos, en la elección primaria 2 se trata de 69 votos, en la elección primaria 3 se trata de 52 votos, en la elección primaria 4 se trata de 38 votos y en la elección primaria 5 se trata de 100 votos. Determínese una política para maximizar las posibilidades del candidato de obtener al menos 100 votos. 16. Una empresa de fabricación, que recibe un pedido de un producto especial, ha elaborado un plan de producción para los próximos 5 meses. Todos los componentes se fabrican internamente a excepción de una parte electrónica, que debe comprarse, el gerente a cargo de la compra de la parte electrónica debe cumplir con el calendario de los requisitos establecidos por el departamento de producción. Después de negociar con varios proveedores, el gerente de compras ha determinado el mejor precio posible para la parte electrónica para cada uno de los cinco meses en el horizonte de planificación. En la tabla siguiente se resume los requerimientos y los costos respectivos. Mes

Requerimiento Precio de compra (miles unidades) ($/miles piezas) 1 5 10 2 10 11 3 6 13 4 9 10 5 4 12 Tabla de requerimiento mensual y precios de compra

La capacidad de almacenamiento de este artículo se limita a 12000 unidades; no hay stock inicial, y después de los cinco meses periodo ya no será necesario el elemento. Suponga que los pedidos de la parte electrónica se colocan una vez cada mes (al principio de cada mes) y que el plazo de entrega es muy corto (la entrega se hace prácticamente instantáneamente). No se permite ninguna copia de ordenar. Derivar el horario de compra mensual si el costo total de compra debe ser minimizado. Supongamos que un cargo de almacenamiento de 250 dólares se incurre por cada 1000 unidades que se encuentran en inventario al final de un mes. ¿Qué plan de compra minimizaría los costes de compra y de almacenamiento? 17. La fundición “EL SUPER ACERO” tiene 11 órdenes por moldes que deben ser entregados en las próximas cuatro semanas. Sus hornos e instalaciones de moldeo son normalmente usados para la producción regular de moldes estándar, pero también pueden ser programados para usarse si se presentan cuatro órdenes especiales por semana. Los costos de operación varían un poco dependiendo del número de trabajos especiales que la empresa trata de producir en ese lapso. Esto se debe a que la preparación del molde, calentamiento requerido de los hornos, requerimientos de inventarios y tiempo extra tienden a variar. Si no se hacen trabajos especiales, sin embargo, las instalaciones tienen un costo asignado de tiempo ocioso. Considerando los diferentes costos, así como el ingreso de unidades especiales, se ha derivado la siguiente tabla de utilidades: Número de unidades N (producidas en el periodo) 0 1 2 3 4

Utilidad ($) de producir N unidades en el periodo (semanas) A B C D -4 -4 -4 -4 4 9 8 3 12 10 15 11 20 22 20 20 18 16 24 18

Úsese un enfoque de programación dinámica para programar la producción de las 11 unidades sobre los cuatro períodos, en tal forma que se maximicen las utilidades de la fundición. 18. Establézcase una fórmula de recursión para resolver el siguiente problema mediante programación dinámica. Una compañía de máquinas vendedoras opera normalmente una máquina con dos años 5

de uso en cierto lugar. La tabla siguiente da las estimaciones de mantenimiento, costo de reemplazo e ingresos (todo en dólares) para cualquier máquina en este sitio, en función de la edad de la máquina. Edad, 𝑢 0 Ingreso, I(u) Mantenimiento M(u)

1

2

10 000

9500

9200

100

400 3500

…..

Reemplazo, R(u)

3

4

5

8500

7300

6100

800

2000

2800

3300

4200

4900

5800

5900

De acuerdo a una política establecida, ninguna máquina se conserva después de que cumple seis años y solamente se reemplazan por máquinas nuevas. Determínese una política de reemplazo que maximice el beneficio total para este sitio durante los próximos 4 años. Resuélvase el problema respectivo. 19. Establézcase una fórmula de recursión para el siguiente problema y luego resuélvase. Una pequeña compañía constructora tiene actualmente un camión de volteo de 1 año de antigüedad. En la tabla siguiente se dan estimaciones del mantenimiento, costos de reemplazo y de los beneficios que se pueden esperar en dinero, junto con datos similares para camiones nuevos que podrían comprarse en el futuro; todas las cantidades están en unidades de $1 000. Los camiones nunca se conservan durante más de 3 años y los reemplazos se hacen sólo por modelos nuevos. Determínese una política de reemplazo de beneficio máximo para esta máquina durante los próximos 5 años. Edad Modelo actual Modelo nuevo

Modelo para el próximo año

1 2 3 0 1 2 3 0 1 2

Modelo para dentro de tres años

Modelo para dentro de cuatro años

Manteamiento

20 17

8 11

….

….

21 20 17 ….

21 17 15 3

Modelo para dentro de dos años

Ganancia

….

1 11 ….

1 7 …. ….

Reemplazo 18 25 35 6 19 26 36 6 18 26 36 7 19

0 1

22 19

2 8

2 3 0 1

17

12

….

….

24 18

3 4

24 37 6 12

2

15

11

27

3 0 1

….

….

25 19

3 5

37 6 13

2

14

10

27

3

….

….

38

6