Problemas DE Programacion Entera PDF

Preview

Summary

CASOS DE FORMULACIÓN DE PROGRAMACIÓN ENTERAPREGUNTA 1: Problema de expansión de capacidad: Una compañía de servicio eléctrico esta planeando ampliar su capacidad de generación durante los próximos 5 años. Su capacidad actual es de 800 megavatios (MW), pero de acuerdo con sus propios pronósticos de l...

Description

CASOS DE FORMULACIÓN DE PROGRAMACIÓN ENTERA PREGUNTA 1: Problema de expansión de capacidad: Una compañía de servicio eléctrico esta planeando ampliar su capacidad de generación durante los próximos 5 años. Su capacidad actual es de 800 megavatios (MW), pero de acuerdo con sus propios pronósticos de la demanda, va ha requerir la capacidad adicional que muestra la siguiente tabla: AÑO 1 2 3 4 5

CAPACIDAD MINIMA (MW) 880 960 1050 1160 1280

La compañía de servicio eléctrico podrá aumentar su capacidad de generación con la instalación de unidades generadoras adicionales de 10, 50 ó 100 MW. El costo de instalación de un generador depende de su tamaño y del año en el cual entre en servicio. La siguiente tabla muestra el costo de adquisición de cada generador en el año i. Capacidad del Generador (MW) 10 50 100

1 300 670 950

AÑO 2 3 4 5 250 208 173 145 558 465 387 322 791 659 549 458

Una vez que un generador entra en servicio, su capacidad esta disponible para satisfacer la demanda en los años subsiguientes. Formule el modelo de programación lineal que minimice los costos de poner en servicio los generadores necesarios, satisfaciendo al mismo tiempo los requisitos de capacidad mínima. PREGUNTA 2: Formulación usando variables binarias (5 puntos) Un modelo que una compañía de servicio eléctrico requiere para sus operaciones diarias consiste en una guía para decidir que generadores debe poner en marcha en cada ocasión. El servicio en cuestión cuenta con tres generadores con las características que aparecen en la tabla inferior. El día esta dividido en dos periodos y en el primero de ellos se necesitan 2,900 megavatios. En el segundo periodo se requieren 3,900 megavatios. Un generador puesto en marcha en el primer periodo puede usarse en el segundo sin incurrir en un costo adicional de puesta en marcha. Todos los generadores principales A, B y C se apagan al final de cada día, formule el modelo correspondiente para este caso.

Generador A B C

Costo fijo de arranque ($) 3000 2000 1000

Profesor: Luis Ulfe / Gustavo Solis

Costo por periodo por megavatio usado ($) 5 4 7

Capacidad máxima en cada periodo (MW) 2100 1800 3000

PREGUNTA 3: Formulación El departamento central de la policía esta pensando en reubicar varias sub-estaciones de la policía para obtener una mejor vigilancia en áreas de alta criminalidad. Las ubicaciones bajo consideración, junto con las áreas que pueden ser cubiertas a partir de dichas ubicaciones se dan en la tabla anexa. Formule un modelo de programación de enteros que se pudiera utilizar para encontrar el número mínimo de localizaciones necesarias a fin de proporcionar la cobertura para todas las áreas.

Ubicación potencial De las sub-estaciones A B C D E F G

Áreas Cubiertas 1, 5, 7 1, 2, 5, 7 1, 3, 5 2, 4, 5 3, 4, 6 4, 5, 6 1, 5, 6, 7

PREGUNTA 4: Formulación – programación entera binaria La municipalidad de una ciudad, esta pensando en reubicar varias subestaciones de serenazgo para obtener una mejor vigilancia en áreas de alta criminalidad. Las ubicaciones bajo consideración junto con las áreas que pueden ser cubiertas a partir de dichas ubicaciones se dan en la tabla siguiente.

Ubicación potencial de las subestaciones A B C D E F G

Áreas cubiertas 1, 5, 7 1, 2, 5, 7 1, 3, 5 2, 4, 5 3, 4, 6 4, 5, 6 1, 5, 6, 7

Costo implementación de las subestaciones 200 100 150 300 256 270 180

Formule un modelo de programación con variables binarias que se pudiera utilizar para encontrar el costo mínimo de implementación de subestaciones necesarias a fin de proporcionar cobertura para todas las áreas. PREGUNTA 5: Formulación – programación entera binaria La gerencia general esta estudiando el conjunto de inversiones a ejecutar que aparecen en el cuadro inferior, además de los rendimientos y costos asociados a cada inversión, la gerencia desea maximizar el rendimiento total invirtiendo no mas de 30 millones de dólares en total, formule el modelo respectivo. Inversiones 1 2 3 4 5 6 7

Condiciones Ninguna Solo si 1 es seleccionada Solo si 2 es seleccionada Se hará si 1 y 2 son seleccionadas No se selecciona si 1 o 2 son seleccionadas No se selecciona si 2 y 3 son seleccionadas Solo si se selecciona 2 y no se selecciona 3

Profesor: Luis Ulfe / Gustavo Solis

Rendimiento 10 8 11 7 11 8 9

Costo 7 4 8 4 7 5 6

PREGUNTA 6: Una competencia de relevos de 100 metros incluye a cuatro diferentes nadadores, quienes nadan sucesivamente 25 metros de dorso, pecho, mariposa y libre. El entrenador tiene seis nadadores muy veloces, cuyos tiempos esperados en segundo para los eventos esperados individuales se dan en la tabla.

Dorso Nadador 1 Nadador 2 Nadador 3 Nadador 4 Nadador 5 Nadador 6

Pecho

Mariposa

Libre

73 70 72 75 69 70

63 65 69 70 75 66

57 58 55 59 57 59

65 67 68 67 69 75

Como deberá el entrenador asignar, los nadadores a los relevos a fin de minimizar la suma de sus tiempos.

PREGUNTA 7: Una empresa dedicada a la fabricación de pinturas para fuselaje de aviones posee 3 maquinas con diferentes capacidades. Poner en operación un día cada máquina, tiene costos fijos y un costo de precio por galón. Las capacidades de cada máquina, son como sigue:

$100 $200

Costo del proceso por Galón. $5 $4

Capacidad Máxima diaria en Galones. 2000 3000

$300

$3

4000

Máquina

Costos Fijos

1 2 3

La empresa espera una demanda diaria de 3500 galones. El problema consiste en determinar que maquinas utilizar y cuantos galones debe producir cada máquina de tal manera que la demanda quede satisfecha y el costo total sea el más pequeño posible.

Profesor: Luis Ulfe / Gustavo Solis

PREGUNTA 8: La Mc Davis Consulting Co. se especializa en la preparación de programas de computadora para el gobierno y la industria. Estos programas se escriben en uno de cuatro lenguajes de programación: FORTRAN, Ensamblador, COBOL y APL. La compañía tiene tres programadores que realizan esta labor y existen cinco trabajos de programación que deben terminarse lo más pronto posible. No todos los programadores trabajan a la misma velocidad en todos los lenguajes y se les paga en forma diferente con base en su experiencia. Cada uno de los trabajos debe elaborarlo un solo programador. Los costos de terminación de cada tarea por programador se muestran a continuación: Programador Joe Sue Susan

Trabajo 1 $100 80 200

Trabajo 2 $150 200 250

Trabajo 3 $200 100 250

Trabajo 4 $100 100 150

Trabajo 5 $50 80 100

A continuación se muestran el tiempo que necesita cada programador para terminar cada trabajo y el tiempo de que dispone después de realizar sus demás tareas. Prog.

Trabajo 1

Trabajo 2

Trabajo 3

Trabajo 4

Trabajo 5

Joe Sue Susan

10 4 20

15 10 25

20 5 25

10 5 15

5 4 10

Tiempo disponible 35 20 40

PREGUNTA 9: Una compañía manufactura cajas de herramientas en tres plantas y la manda después por barco a tres centros de distribución (los cuales son propiedad de la compañía). Los costos de producción y distribución variable por unidad transportada entre las plantas y los centros de distribución, así como la capacidad de producción mensual de las plantas, la demanda mensual de cada centro de distribución, y los costos fijos mensuales por operar las plantas y centros de distribución se muestran en la siguiente tabla:

Planta 1 2 3 Demanda Costo fijo

Centro de distribución A $25 $27 $30 500 $500

Centro de Centro de distribución B distribución C $30 $27 $25 $29 $27 $26 500 500 $400 $600

Capacidad 600 600 600

Costos fijos 1700 2000 1900

La compañía está pasando por momentos económicos difíciles y la administración ha decidido cerrar una planta y un centro de distribución. Desde luego que la demanda del centro de distribución se perderá (no será satisfecho). Cuando un centro de distribución se cierra, nada llegará a él y los costos fijos no se tomarán en cuenta. Cuando se cierra una planta, nada se manufacturará ni saldrá de ella. Formule el modelo de programación entera para decidir qué planta y centro de distribución cerrar.

Profesor: Luis Ulfe / Gustavo Solis

PREGUNTA 10: Un comerciante de equipos industriales se encuentra en una ciudad en la cual puede comprar siete tipos de equipos, los pesos, utilidades, cantidades mínimas y máximas a comprar de los equipos se muestran en la siguiente tabla. Equipo 1 2 3 4 5 6 7

Peso (kg/unidad) 320 400 450 400 300 360 380

Utilidad ($/unidad) 2500 3700 2600 2800 1900 3000 2700

Mínimo a comprar 1 0 2 1 0 0 1

Máximo a comprar 3 3 4 3 2 4 4

Suponga que el comerciante dispone de un camión con capacidad de 3600 Kg. Además, para los productos 2 y 5, existe un costo fijo de embarque (este costo es independiente de la cantidad embarcada, solo en caso de no embarcar dicho producto el costo fijo será cero); el costo fijo para el producto 2 es de $ 280 y para el producto 5 es de $ 350. Para el producto 6 el costo fijo es de $320, pero solo se aplica este costo si se embarcan 3 o más unidades de este producto. Formule un modelo adecuado para esta situación. PREGUNTA 11: Hemos recibido las ofertas de tres compañías de teléfonos para suscribirnos a su servicio de larga distancia hacia Estados Unidos, Telefónica cobrará una tarifa fija de 16 dólares al mes más 0.25 centavos por minuto, Telmex cobrará 25 dólares al mes, pero reducirá el costo por minuto a 0.21 centavos, en tanto que Nextel ofrece cobrar una tarifa fija mensual de 18 dólares y el costo por minuto es de 0.22 centavos. Generalmente hacemos un promedio de 200 minutos de llamadas de larga distancia al mes. Suponiendo que, no se pague la tarifa fija a menos que haga las llamadas y de que pueda dividir mis llamadas entre las tres compañías según nos parezca o nos convenga, formular un modelo que nos ayude a determinar cómo se debe utilizar los servicios de las tres compañías para minimizar nuestra cuenta mensual de teléfono. PREGUNTA 12: Una línea aérea piensa comprar Jet de pasajeros grandes, medianos y chicos. El precio de compra será de $67 millones cada avión grande, $50 millones por cada uno mediano, $35 millones por cada avión chico. El consejo directivo ha autorizado un compromiso máximo de $1500 millones para estas compras. Sin importar que aviones se compren, se espera que las distancias de viajes aéreos sean lo suficientemente grandes como para que los aviones se utilicen, en esencia, a su capacidad máxima. Se estima que la ganancia neta anual (después de restar los costos de recuperación de capital) será $4.2 millones para un avión grande, $3 millones si se trata de un avión mediano y $2.3 millones por cada avión chico. Se piensa que la compañía podrá disponer de suficientes pilotos entrenados para operar 30 aviones nuevos. Si solo se comprar aviones chicos, las instalaciones de mantenimiento podrían manejar 40 aviones, pero cada avión mediano equivale a 1 1/3 aviones chicos y cada avión grande equivale a 1 2/3 aviones chicos, en términos de la utilización de las instalaciones de mantenimiento. Esta información se obtuvo en un análisis preliminar del problema. Más adelante se llevará a cabo un estudio mas detallado. Si se toman estos datos como una primera aproximación la gerencia desea saber cuantos aviones de cada tipo debe comprar a fin de maximizar la ganancia.

Profesor: Luis Ulfe / Gustavo Solis

PREGUNTA 13: Una compañía opera una planta en Lima con una capacidad anual de 30,000 unidades. El producto se embarca a centros regionales de distribución localizados en Arequipa, Trujillo, Iquitos. Debido a un incremento anticipado en la demanda, la compañía planea aumentar la capacidad construyendo una nueva planta en una ò más de las ciudades siguientes: Piura, Chiclayo, Tacna, Tarapoto. El costo fijo anual estimado y la capacidad anual de las cuatro plantas propuestas son como sigue: Planta propuesta Piura Chiclayo Tacna Tarapoto

Costo fijo anual US$ 175,000 US$ 300,000 US$ 375,000 US$ 500,000

Capacidad anual 10,000 20,000 30,000 40,000

El grupo de planeación a largo plazo de la empresa a desarrollado pronostico de la demanda prevista anual en los centros de distribución como sigue: Centro de distribución Arequipa Trujillo Iquitos

Demanda anual 30,000 20,000 20,000

El costo de embarque por unidad de cada una de las plantas a cada uno de los centros de distribución aparece en la siguiente tabla: Localización de la planta Piura Chiclayo Tacna Tarapoto Lima

Arequipa 5 4 9 10 8

Trujillo 2 3 7 4 4

Iquitos 3 4 5 2 3

Formule un modelo de programación lineal entera que determine las nuevas plantas que deberán construir.

Profesor: Luis Ulfe / Gustavo Solis...