Investigació operativa. Problemes

Títol : Investigació Operativa Autor : Jaime Barceló Diposit Legal Impres per Elena Fernandez : B.16075 -1996 : REPRO BARNA, S.L. l4co2ro?-ri C/. Entenya 16-18. 08015 Barcelona I! \ - Modelización l. Un problema común a diferentes industrias es el de las pérdidas asociadas al corte de rollos de papel, tela, planchas metálicas etc., para poder satisfacer los pedidos de los clientes. Este problema de1iva del hecho que, por limitaciones de producción, las fábricas producen rollos de anchura estándar (p.ej. 100 pulgadas) y longitud fija (p.ej. 500 pies). Los clientes piden a menudo rollos de menor anchura. Los rollos se cortan en una máquina cuyas cuchillas pueden fijarse a cualquier combinación de anchuras, siempre que la anchura de la combinación no exceda la del rollo. Así, el problema se convierte en el de asignar los pedidos de manera que: a) El número total de rollos estándar usados para satisfacer los pedidos sea mínimo, o bien b) Se minimice la pérdida total, siendo la pérdida la parte de un rollo no usada al ser su anchura menor que cualquier medida pedida, así como el número de rollos cortados que sobran respecto al número de rollos (de cierta anchura) pedidos. Suponiendo que una fábrica de papel de periódico que fabrica rollos estándar de 100", debe satisfacer un pedido de 75 rollos de 24", 50 rollos de 40" y 110 rollos de 32", formular el problema como uno de programación entera, para las dos funciones objetivo anteriores. Sugerencia: enumerar las formas de cortar un rollo de anchura 100" en rollos de anchuras 24", 40" y 32". Definir como variable de decisión x¡ a la i-ésima forrna de efectuar el corte. 2. En el congreso de los diputados hay n comités. El j-ésimo comité tiene Vj vacantes j=l.. .. ,n. Hay m diputados para cub1ir las vacantes (m:s;:Evj). Pij es la preferencia del diputado i por una vacante del comité j (i=l, ... ,m; j=l, ... ,n). Cada vacante debe cubrirse por un diputado, y hay que cumplir las condiciones siguientes: a) Cada diputado puede cubrir, como máximo, vacantes en dos comités. b) Hay tres tipos de comités: exclusivos, semiexclusivos y no exclusivos. Si un diputado cubre una vacante en un comité exclusivo, no puede cubrir ninguna otra, y si cubre una vacante en uno semiexclusivo y otra en otro comité, el otro debe ser no exclusivo. Formular este problema como uno de programación entera sometido a las condiciones dadas que maximice las preferencias. ¿Cúal seda la fmmulación en el ejemplo numérico siguiente? DipuL1clo Ag,icultura Danca Eduaición Autonomías J uclicial Ciencia Interior Correos 1 o 1 o 1/2 o o o 1/2 2 1/3 o o 1 o o o 1 3 o o o o o o o o 4 o o o 1 1/2 o o o 5 o o o 1 o o 1/2 o 6 o o o 1/2 1 1/3 o o 7 o o o 1 1/2 o o 1/3 8 o o o o o o o o 9 o o o 1 o o o o 10 o 1 o o o o o o 11 o o o 1 o o o o 12 1/2 o o o o o o o 13 1/3 1/2 o o o o #vacantes 5 3 1 2 1 Tipo Semiex Semiex Semiex Ex Semiex Semiex Noex Noex 3. Plantear el siguiente problema de programación matemática: Una compañía minera desea planificar sus operaciones de laboreo de manera que le permita controlar el grado de plomo que va a los molinos en cada tumo. Las minas tienen 15 túneles que han de ser tratados entre los tres tumos de cada día. El porcentaje de plomo y las toneladas de mineral que pueden explotarse por tumo en cada tune) son: Tu11el 1 2 %Plomo 2 5 Tm min 540 520 3 4 5 8 20 25 480 600 580 6 7 4 8 575 555 8 9 10 10 12 18 540 530 535 11 12 12 4 585 530 13 14 15 2 1 3 510 500 620 En cada turno se han de trabajar 5 túneles y la combinación de mineral que ha de producir el tumo debe contener, como mínimo un 8% de plomo. ¿Qué túneles se trabajan en cada tumo? 4. Plantear el siguiente problema: Al realizar el plan de inversiones los responsables de una empresa deben decidir entre 5 proyectos, para los que han estimado las siguientes cifras de inversión e ingresos actualizados en millones de pts: Proyecto A D C D E Inversión 10 20 10 50 30 Ingresos 13 27 14 60 40 Hallar el plan que maximiza el beneficio total, considerando que sólo se pueden invertir 60 millones y que: 1) Los proyectos A y C son incompatibles 2) Si se invierte en A y D no puede invertirse en E 3) Si se invierte en D ó E, no puede invertirse ni en A ni en D 4) Si se invierte en C debe invertirse en E 5. Duranle la construcción de una presa han de transportarse grandes cantidades de grava apta para la producción de hormigón desde los depósitos hasta la planta de fabricación de hormigón aneja a la presa. La tabla proporciona las cantidades estimadas y los costes de producción y transporte de la grava desde las ubicaciones de los depósitos hasta la planta de fabricación. Ubicación del depósito Cantidad (m3) coste/m3 A 8000 380 pts. D 16000 540 pts. C 8000 340 pts. D 6000 480. pts. En la construcción de la presa se utilizan tres tipos de hormigón en las cantidades que se indican, que se obtienen mezclando los distintos tipos de grava con cemento y otras componentes según los límites especificados y los costes que da la tabla: Tipo de hormigón Límites coste/m3 Requerimiento (m3) 1 (A+D):,50%, C�10%, D sin límite 580 6000 2 (A+D):,60%, C�10%, (C+D):,(A+D) 500 15000 3 A�20%, (C+D)�l/2(A+D) 650 8000 Fo1mular el problema como un problema lineal, cuyo objetivo es la minimización de los costes de Lransportc y producción de las cantidades requeridas de los diferentes tipos de ho1migón. 6. El presidente de la Tim Burr Company desea emplear de la mejor forma posible los recursos madereros en una de sus áreas forestales. En esta zona hay un aserradero y un molino de contrachapado; por tanto, la madera de los árboles puede convertirse en tablas de madera o madera contrachapada. Una tabla de madera vendible de 1000 pies cuadrados requiere 1000 pies cuadrados de pícea y 4000 pies cuadrados de abeto; 1000 pies cuadrados de madera contrachapada requieren 2000 pies cuadrados de pícea y 4000 pies cuadrados de abeto. En la zona hay 32000 pies cuadrados de pícea y 72000 pies cuadrados de abeto. El departamento de ventas exige que, en este periodo, se produzcan 5000 pies cuadrados de tablas de madera y 12000 pies cuadrados de contrachapada. Las contribuciones al beneficio son de 45$ por 1000 pies cuadrados de tablas de madera y 60$ por 1000 pies cuadrados de madera contrachapada. Sean T y C las cantidades (en miles de pies cuadrados) de tablas de madera y madera contrachapada producidas respectivamente. Formular el problema como un modelo lineal. 7. El gerente de una planta de la Compañía de Acero Jericho debe decidir cuantas libras de acero puro x 1 y cuantas libras de chatarra x2 deben utilizarse en una aleación que se funde para uno de sus clientes. El coste por libra del acero puro es de 3 y el de la chatarra es de 6 (que es superior porque primero deben eliminarse todas las impurezas). El pedido del cliente es de 5 libras, a pesar de que estaría dispuesto a aceptar una producción mayor si la Compañía Jericho se lo exige. Se dispone de 4 libras de acero puro y de 7 de chatarra. La proporción de chatarra con respecto al acero puro no debe superar los 7/8. En la planta sólo disponen de 18 horas para realizar este pedido; en el proceso total, cada libra de acero puro requiere 3 horas mientras que cada libra de chatarra requiere sólo 2 horas. Fo1mular el problema como un modelo lineal. 8. El ayuntamiento de la ciudad en la que está ubicada la Compañía Química Fowlayer, le ha exigido que instale y utilice mecanismos para evitar la polución. La compañía comercializa dos productos; para cada uno de ellos el proceso de manufactura produce una cantidad excesiva de gases irritantes y partículas (sólidos que flotan en el aire). La tabla siguiente muestra la emisión diaiia, en libras, de cada polucionante por cada 1000 galones de producto producido: Tipo de polucionanle GasGM Gas SD Partículas Libras de Polucionanle emitido Por 1000 galones de producto 1 Por 1000 galones de producto 2 24 36 8 12 100 50 La compañía no puede emitir más de G¡, 02 y P¡ libras de gas GM, gas SD y partículas, respectivamente. El beneficio por cada 1000 galones de los productos 1 y 2 obtenidos por día son p¡ y P2 respectivamente. El encargado de producción, ha aprobado la instalación de dos mecanismos antipolutivos. El primero de ellos elimina 75% del gas GM, 50% del gas SD y 90% de las partículas, independientemente del producto que se esté fabricando. El segundo, elimina 33% del gas GM, nada del gas SD y 80% de las partículas en el producto 1, y 25% de CM, nada de SD y 60% de las partículas en el producto 2. El primer mecanismo reduce el beneficio por cada mil galones producidos diariamente en c¡, independientemente del producto; análogamente, el segundo mecanismo reduce el beneficio en c2 por cada 1000 galones producidos diariamente, independientemente del producto. Las necesidades comerciales requieren que se produzcan por lo menos R¡ miles de galones diariamente del producto 1 y R2 miles de galones diarios del producto 2. Si las variables de decisión son: x 1: miles de galones del producto I obtenidos diariamente sin utilizar ningún mecanismo antipolutivo x 11: miles de galones del producto 1 obtenidos diariamente utilizando el primer mecanismo antipolutivo x12: miles de galones del producto 1 obtenidos diariamente utilizanto el segundo mecanismo antipolutivo. Análogamente, para el producto 2 se defineen xz, x21 y x22. Formular un modelo de optimización apropiado. 9. Una economista de la compañía publicitaria, Flag-Poole Advertising Company, opina que puede conocer la forma óptima de distribuir los dólares invertidos en publicidad de un cliente mediante un programa lineal. Basta con identificar las audiencias a las que quiere dirigirse el clientetales como adolescentes, parejas recién casadas, tercera edad, etc. Sea i el índice que representa la i-ésima audiencia. El cliente debe especificar el nivel de exposición que desea para cada audiencia i, E¡. Entonces se evalua en función de su efectividad cada uno de los medios publicitarios (tales como un anuncio en televisión, un anuncio en color en un suplemento dominical, etc.). Sea j el índice que representa el j-ésimo medio publicitario, y% la efectividad evaluada de invertir un dolar para la i-ésima audiencia en el j-ésimo medio. Cada variable de decisión se designa por Xj, que representa la cantidad total de dólares que se invierten en el medio publicitario j durante una campaña de promoción. El objetivo del cliente es minimizar el gasto total publicitario, manteniendo sus niveles deseados de exposición. Suponiendo que hay 4 audiencias y 5 medios publicitatios, esciibir el modelo lineal que se describe anterimmente. 10. La Best Tasties Corporation hace cuatro tipos de cereales para el desayuno; Noisies, Soggies, Bursties y Reposies. Cada uno de ellos es un compuesto de ingredientes (granos, vitaminas, azucar y conservantes). Sea i el índice que representa al i-ésimo ingrediente i=l, ... ,I. Sea ªNi la cantidad del ingrediente i en una libra de Noisies, y similarmente as¡, ªBi y aRi las cantidades para los otros tres cereales. Supongamos que M¡ es la máxima cantidad disponible el próximo mes del ingrediente i para la producción de los cereales. La contribución al beneficio de una libra de Noisies se representa por PN, y similarmente las contribuciones al beneficio de los otros cereales se representan por PS, p13 y PR· Sean XN, xs, xn y XR las libras de cada cereal que se van a producir el próximo mes. Por lo menos deben producirse 15000 libras de Noisies, así como 130000 libras de Soggies, 45000 libras de Bursties y 600000 libras de Reposies. Escribir un programa lineal para obtener un esquema de planificación de la producción óptimo. 11. La compañía Turned-On Transistor Radio Company, fabrica tres modelos de radio, A, By C, cuyas contribuciones al beneficio son de 16, 30 y 50 respectivamente. La demanda mínima semanal del modelo A es de 20 unidades, la del Bes de 120 unidades y la del C, de 60. Cada tipo de radio requiere una cierta cantidad de tiempo para la fabricación de componentes, montaje y embalaje. Específicamente, doce unidades del modelo A requieren 3 horas de fabricación, 4 horas de montaje y 1 hora de embalaje. Los tiempos correspondientes para una docena de unidades del modelo B son 3.5, 5 y 1.5, y para una docena de unidades del modelo C son 5, 8 y 3. La semana próxima la compañía dispondrá de 120 horas de fabricación, 160 horas de montaje y 48 horas de tiempo de embalaje. Formular un programa lineal para obtener un esquema de planificación de la producción óptimo. 12.Antes de que termine la cosecha la compañía Fickle-Pickle debe efectuar los pedidos de compra de pepinos a cada uno de los N productores. El producto se envía poste1io1mente a M plantas de producción en las que se transfonna en encurtidos. Actualmente se conoce la variación esperada en el tamaño de los pepinos comprados a cada uno de los granjeros. Hay D clases de pepinos (medidos en términos de los tamaños de sus diametros). La i-ésima planta de producción requiere Rile bushels* de pepinos de diámetro dk, donde i=l, ... ,M y k=l, ... ,D. Sea xj el número de bushels que se compran al cultivador j, y Uj el máximo número de bushels disponibles del cultivador j. Sea pjk la fracción de un bushel comprado al granjero j que tiene pepinos de diametro k. (P.ej. si p34=0,5, entonces la mitad de cada bushel comprado al cultivador 3 pertenece a la clase de diametro d4). Por tanto, pjk�0 y Spjk=l, tomando la suma en k. El coste por bushel de pepinos comprado al cultivador j es cj y el coste de transpo11e por bushel comprado al cultivador j hasta la planta i es cji. Hay que notar que, en general, cualquier esquema de pedidos hará que la compañía adquiera más pepinos de determinados tamaños que los que en realidad requiere. Supongamos que después de su encargo, los pepinos se ordenan por su tamaño en el lugar de cultivo y los bushels de pepinos de cualquier tamaño con una proporción supe1ior a la requerida se destrnyen "in situ" sin ningún coste adicional. F01mular un modelo de optimización apropiado que indique cúantos bushels deben comprarse a cada cultivador y qué tamaños deben tener los pepinos que deben transportarse a cada planta. *Bushel: Medida de áridos correspondiente a 36,36 litros. 13. La gerente de la Bailen Oíl Company desea encontrar las proporciones óptimas de dos posibles procesos de mezclado. En el proceso 1, un input de un barril de aceite crudo A y 3 barriles de aceite crudo B produce un output de 50 galones de gasolina X y 20 galones de gasolina Y. En el proceso 2, un input de 4 baniles de aceite crudo A y 2 baiTiles de aceite crudo B produce un output de 30 galones de gasolina X y 80 galones de gasolina Y. Sean x¡ y x2 los números de barriles que se decide utilizar en el proceso 1 y 2 respectivamente. La cantidad máxima disponible de Acite Crudo A es de 120 barriles y 180 barriles de Aceite Crudo B. El departamento de ventas exige que se produzcan por lo menos 2800 galones de Gasolina X y 2200 galones de Gasolina Y. Los beneficios unitarios de los Procesos 1 y 2 son p 1 y p2 respectivamente. Formular este problema de mezclas como un problema de programación lineal. 14. La encargada de High Tail Airflight Company, compañía que opera desde un terminal central dispone de 8 aviones de tipo 1, 15 aviones de tipo 2 y 11 aviones de tipo 3 disponibles para los vuelos de hoy. Las capacidades de tonelaje (en miles de toneladas) son de 45 para el tipo 1, 7 para el tipo 2 y 5 para el tipo 3. La encargada decide enviar aviones a las ciudades A y B. Los tonelajes necesarios (en miles de toneladas) son de 20 para la ciudad A y 28 en la ciudad B; si se proporcionan aviones con un exceso de tonelaje sobre el requerido ello no supone ningún coste extra. Un avión puede volar una única vez por día. El coste de enviar un avión desde el terminal hasta cada ciudad es el siguiente: Ciudad A Ciudad 13 Tipo l 23 58 Tipo 2 15 20 Tipo 3 1,4 3,8 Sean x¡, x2 y x3 las variables que denotan el número de aviones de cada tipo que se envían a la ciudad A, y, similam,ente, y¡, Y2, y3 los aviones enviados a la ciudad B. Fom1ular un modelo lineal para resolver este problema de itineratios. 15. La Glassey-Staire Television Network desea establecer precios competitivos para sus tiempos publicitaiios. Lo que sigue es una versión simplificada del problema. Supongamos que hay tres tipos de periodos publicitarios: tarde-noche, entre-semana y Sábado/Domingo-tarde (antes de las 6 p.m.). Sean p¡, p2 y p3 los precios por minuto en cada uno de los periodos, respectivamente. La compañía vende bloques de tiempo a K grandes compañías publicitarias que tienen un efecto importante en los precios que se fijan. Se sabe que la compañía k desea adquirir un lote que constiste en a¡k, a2k y a3k minutos en los 3 periodos publicitarios y está dispuesta a pagar Ak dólares por todo el lote. La compañía también vende tiempo a publicitarios menores y piensa que, si los precios son adecuados para los K grandes publicitarios, en total puede vender M¡, M2 y M3 minutos de tarde-noche, entre-semana y Sábado/Domingo-tarde, res pee ti vamente. Formular este problema como un modelo de programación lineal. 16. La ciudad de Shlepping, Massachusetts, tiene tres distritos educativos; en cada uno de ellos, la proporción de estudiantes residentes blancos y negros es diferente. El Consejo Educativo (CE) local quiere definir un plan de asignación de estudiantes a los distintos distritos que, en la medida de lo posible, establezca las mismas proporciones raciales en sus colegios. Entre los planes alternativos posibles, el CE elegirá uno que minimice el coste total de transporte. El CE ha contratado a un consultor para diseñar un plan y ha establecido que la proporción (o fracción) de estudiantes blancos en los colegios de los distritos no debería diferenciarse en más de 0, l de la proporción de estudiantes blancos en toda la ciudad. (Por ejemplo, si la proporción de estudiantes blancos en toda la ciudad es de 0.73, entonces, la proporción de estudiantes blancos en cada distrito debe estar entre 0.63 y 0.83). A partir de estadísticas publicadas, se sabe que la cantidad de residentes en edad escolar negros y blancos en los Distritos 1, 2 y 3 son n¡,b¡; n2, b2; y n3, b3; respectivamente. El máximo número de estudiantes que pueden ubicarse en los Distritos 1, 2 y 3 son N¡, N2 y N3, respectivamente. El coste de transpo1te desde el disttito i hasta el distrito j por estudiante es Cij- Supongamos que las 29. Una compañía forestal dispone de cuatro terrenos en los que cultiva árboles. Actualmente, están considerando cuatro especies de árboles: pinos, piceas, avellanos y otros árboles de hojas caducas. Los datos del problema se presentan en la siguiente tabla: 1 2 3 4 Rendimiento anual esperado Ingresos anuales esperados de las Area d ispon iblc l-"-d"'-'-'la..,s-"--"'-".!JC!fl.0..><2.l""'"""'-...wJwu.1W.--f---"'-'LWJ.w.i.....,.="'"'-=Llll'-'-""L.><>'-"-i.=......,"'--l Ha 1500 1700 900 600 Pino 17 15 13 10 16 14 17 12 Rendimiento ele co�<:clm · , anunl 22.5 14 16 12 11 9 10 12 14 8 4.8 ¿Qué área debería dedicar la compañía a las distintas especies en los distintos terrenos? 30. Un granjero debe adquirir las siguientes cantidades de fertilizante en cuatro tiendas distintas, sujeto a las siguientes limitaciones de capacidades y precios. 1 Tipo ele fertilizante 1 2 3 4 5 Míním11 r�m11:ci1!11 Cf",cn 'i so 'iO 00 185 Tienc11 Número 2 3 4 Máximo proporcionable (T.rn.) 350 225 195 275 Precio en unic1ides de dinero por tonelada ele ferlilizrulle 1iumln 1 2 3 4 5 1 45.0 13.9 29.9 31.9 9.9 2 42.5 17 .8 31.0 35.0 12.3 3 47.5 19.9 24.0 32.5 12.4 4 , 'i , ¿Cómo puede conseguirlo minimizando los costes? 31. Un producto puede realizarse en tres tallas, grande, media y pequeña, que proporcionan un beneficio neto de 12$, 10$ y 9$ respectivamente. La compañía tiene 3 centros en los que manufactura el producto, cuyas capacidades de producción son de 550, 750 y 275 unidades diarias, respectivamente, independientemente del tamaño o combinación ele tamaños que se obtenga. La manufactura del producto tiene una etapa de refrigeración por agua; cada unidad producida de la talla grande, media y pequeña requiere 21, 17 y 9 galones de agua, respectivamente. Los centros 1, 2 y 3 disponen diariamente de 10000, 7000 y 4200 galones ele agua para refrigeración, respectivamente. Los estudios de mercado, indican que hay una demanda de 700, 900 y 450 unidades de tallas grande, media y pequeña, respectivamente. La política comercial de la empresa requiere que la fracción (producción planificada)/(capacidad del centro) sea igual en todos los centros. ¿Cúantas unidades de cada una de las tallas deben producirse en los distintos centros para maximizar el beneficio? 32. Una compañía produce una mezcla de dos productos químicos, 1 y 2, siguiendo una proporción de peso de 5:2. Los productos químicos pueden obtenerse, a su vez mediante tres procesos diferentes que utilizan dos materiales distintos y un fuel. Los datos referentes a la producción son los siguientes: Re erimiento� 1 9 2 6 3 4 n iclacl el is on ibl or unidad de tiem o Material2 Fue! ·1 50 75 100 50 Químico! Quí mico2 9 6 7 10 10 6 ades ¿Cúanto tiempo hay que ejecutar cada proceso para maximizar la mezcla total obtenida? 33. Cada círculo de la siguiente figura representa una ciudad. Un producto puede transportarse desde la ciudad i hasta la ciudad j sólo si hay un arco dirigido desde la ciudad i hasta la ciudad j tal como: G)-1 .. k .. c .. .. ➔.G) lJ, lJ, lj Los tres números en el arco representan la menor cantidad que puede enviarse por el arco, el máximo tonelaje que puede mandarse por el arco y el coste en dólares/tonelada enviada a lo largo del arco, respectivamente. Hay 27 toneladas de producto en la ciudad 1 y todo él debería enviarse hasta la ciudad 6 con un coste total mínimo. Todo el producto debe salir inicialmente de la ciudad I y llegar finalmente a la ciudad 6. En cualquier ciudad intermedia la cantidad de producto que llega debe ser igual a la cantidad de producto que sale. 34. Una empresa posee 3 plantas con hornos de coque. El carbón viene de: USA, Rin, Lorena y Saar. Las plantas producen dos tipos de coque -metalúrgico y residuo de coque, así como gas de horno de coque; operan calentándose con gas de altos hornos o con gas de horno coque. La producción de coque y gas de horno de coque depende del carbón usado. La proporción de residuo en el coque depende del carbón y la planta utilizados. Coque metalúrgico es lo que queda en el coque después de separar el residuo. El calor requerido para procesar una Tm de carbón es 0.611 kth* de gas de hornos de coque. Una unidad de gas de altos hornos equivale a 0.927 kth de gas de horno de coque. Las capacidades de procesamiento anuales de las plantas son 9xl05, 7xl05 y 3xl05 Tm de carbón respectivamente. El diagrama del proceso es: USA ► Rin ► Carbón de a:ir ► Lorena ► Planta de horno de coque Gas de altos hornos Coque metalúrgico Rc:sluuo de coque Gas de horno de coque El carbón del Saar no puede usarse en las plantas I y 2. Los carbones de USA y Lorena no pueden usarse en la planta 3. El carbón de Lorena no puede superar el 30% en la planta I ni el 35% en la planta 2. En la planta 3, el carbón del Saar no puede superar el 40%. El gas de horno de coque se compra o vende a 1100 pts/kth. El residuo de coque se vende a 9800 ptsffm. El gas de altos hornos se compra a 800 pts/unidad. Los precios del carbón se dan en la tabla. Todo el residuo de coque producido se vende. Todo el gas de hornos de coque producido se utiliza en las plantas o se vende. Se desean producir 106 Tm. de carbón metalúrgico a un coste mínimo. USA Rin Saar T or Rin Sruuklh de gas de horno de coque r l I i osrronelacla de rnrbón 1.8 1.10 1.25 '\ Toneladas de coque/ Tonel ad ón 0.88 0.80 0.74 O 2 8039 Pro¡:xl[t"ión <fe rcsilluu tic l'J ,qut: en d qx¡uc omclut;iúo Utilizando carbón de 8090 en plantas 1 y 2 8393 en planta 3 8014 6R70 PJaora 1 2 3 0.10 0.08 0.07 0.09 0.10 0.15 0.08 0.08 O. 11 ºº 00 O O *La cantidad de gas de hornos de coque se mide por su contenido calorífico; un klh es un kilo rerrnio, donde termia es la canlidml de calor necesaria para elevar la lemperatura de una lonelada de agua un grado cenlígrado (25200 calorías) 35. Una empresa fabrica un producto cuya demanda varía mensualmente. La disponibilidad de materia prima y de personal varía según las distintas épocas. En los meses I O, 11, 12, 1, 2, 3 la compañía puede contratar como mucho el personal suficiente como para producir 1200 y 600 toneladas mensuales en horas regulares y horas extraordinarias respectivamente. En los meses 4, 5, 6, 7, 8, 9 estas capacidades de producción del personal son de 800 y 500 toneladas mensuales, respectivamente. El producto fabricado durante un mes, puede venderse en cualquier momento del mes siguiente o posteriormente. Los costes de almacenamiento mensual son de 100 pls/Tm de producto. La materia prima no puede almacenarse: debe utilizarse el mes en el que se adquiere. Las operaciones empiezan el mes 1 con un stock de 50 Tm de producto. Al final del mes 12, la compañía debe tener un stock de, por lo menos, 50 Tm de producto. Determina el esquema de producción óptimo. 1 2 1 4 5 6 7 8 l) 10 11 ') 400 600 dunmte estos meses 600 900 durante estos meses 400 600 durante estos meses Disponibilidad de 600 450 4 " 1200 1300 1600 1600 1500 B O 500 500 500 400 1800 700 1800 o 00 900 2500 900 2500 900 2500 800 2500 500 2500 00 2'i00 1200 3000 1100 3000 400 ':\000 36. Una agencia controla el funcionamiento de un sistema que consiste en dos depósitos de agua, al lado de cada uno de los cuales se ha situado una planta generadora de potencia hidroeléctrica. El horizonte de planificación para el sistema es de un año, dividido en seis periodos. El depósito 1 tiene una capacidad de 3500 kiloacre-pies* (ka-ft) de agua y el depósito 2 tiene una capacidad de 5500 ka-ft. En cualquier instante los depósitos deben de soltar una cantidad mínima de agua para satisfacer las necesidades de recreo, riego y navegación. Sin embargo, no hay un límite superior de la cantidad de agua que debe de fluir de los depósitos. Todo el agua que no fluye de los depósitos se almacena (hasta la capacidad de los depósitos) y puede utilizarse para soltarla en periodos posteriores. Todo el agua que fluye de los depósitos (aunque sea para recreo y otras actividades) produce electricidad. Puede suponerse que, durante cada periodo, las llegadas de agua y las salidas de agua suceden con un ritmo constante. También, en media un acre-pie (a-ft) de agua que fluye del depósito 1 produce 310 kw de electricidad y un a-ft soltado del depósito 2 produce 420 kw. A ptincipio de año el depósito 1 contiene 1800 ka-ft de agua y el depósito 2 2500 ka-ft de agua. A final de año los depósitos deben contener las mismas cantidades de agua. La electricidad producida puede venderse ya sea a una empresa local (llamada cliente de tipo 1) o a clientes de tipo 2. Los clientes de tipo 1 compran electricidad una vez al año; exigen que distintos porcentajes del pedido se distribuyan en los diferentes periodos. Pagan 1000 pts. por 1000 kw. Los clientes de tipo 2 compran electricidad por periodos. Encargarán cualquier cantidad de electricidad en un periodo determinado a 500 pts. por 1000 kw. Los restantes datos del problema se dan a continuación. 1 2 3 4 5 6 Llegadas al depósito en Ka-ft 547 2616 1471 2335 982 1231 146 731 32 411 'i9 4Q Cantidad mínima que debe fluir del depósito 200 304 200 578 200 995 200 1495 200 558 o192 Porcentaje de la energía anual vendido al cliente 1 que debe 10 12 15 32 21 Obten un esquema de funcionamiento del sistema que maximice los ingresos anuales totales derivados de la venta de electricidad. *acre-pie: cantidad de agua necesaria para cubrir un acre con un pie de altura. Vale 1233.49 m3 37. Una compañía tiene permiso para operar durante cinco temporadas. Unicamente puede producir durante las cuatro primeras temporadas y durante la quinta sólo puede vender los productos remanentes. Puede fabricar dos tipos de productos. Una unidad de producto 1 requiere 5 hombres-hora en la tarea preparatoria y 3 hombres-hora en la tarea de terminación. Cada unidad del producto 2 requiere 6 hombres-hora en la tarea preparatoria y un hombre-hora en la tarea de terminación. Durante cada temporada la compañía tiene como mucho 12000 hombres-hora para tareas preparatorias y 15000 hombres-hora para tareas de tenninación (sólo durante las cuatro primeras temporadas). El producto obtenido en una temporada puede venderse en cualquier momento a partir de la siguiente temporada. Sin embargo, las ventas requieren cierto esfuerzo de marketing y se estima que para vender 10 unidades de los productos 1 y 2 son necesarios 0.1 y 0.2 hombres-hora para marketing, respectivamente. La contratación de hombres-hora para marketing puede realizarse según las siguientes tarifas: 2 3 4 'i Tarifa normal/ 1 om 1r -1,or 200 400 100 #máximo ,nombres-hora Tarifa horas extra/ n 1rií , 400 300 600 Precio uni 1.ario m 1 'l<l 1 11Kl11c102 2000 4500 2500 4000 3000 4000 'íll 101 No hay límite del número de hombres-hora a contratar para marketing en horas extraordinarias. Si en una temporada no se vende todo el producto del que se dispone en dicha temporada, el fabricante debe pagar una tarifa de 200 pts por unidad de producto para que sea posible ponerlo a la venta la siguiente temporada. Los precios de venta en las distintas temporadas se encuentran en la tabla anterior. ¿Cómo debe operar la compañía para maximizar su beneficio total? 38. La siguiente tabla da la composición de los productos utilizados para obtener una mezcla de cereales para desayuno. Los otros componentes son fibra, agua, etc. La compañía mezcla estos productos y obtiene dos tipos distintos de cereales. En el proceso de mezcla, se pierden el 3% de proteínas, 5% de almidón y 10% de minerales y vitaminas. Por cada 100 kg de productos utilizados, se añaden a la mezcla otros 5 kg de otros ingredientes (básicamente agua y harina). La mezcla 1 se vende a 150 pts/kg; debe contener al menos 22% de proteínas, 2% de minerales y vitaminas y como mucho 30% de almidón. La mezcla 2 se vende a 100 pts/kg; deber contener al menos 30% de almidón. ¿Cúales son las mezclas óptimas para la compañía? 1 45 2 7 3 12 4 27 Porcentajes de contenido . . . 12 4 38 1 25 2 4 '.l 39 68 54 27 61 31 ,o 4S 39. Un granjero tiene 3 granjas en las que puede cultivar tres tipos de grano. Los datos para la próxima estación son los siguientes: Agua disponible en m3 Coste por m3 de agua por encima de -�� ......... -�������-��,��� ...... =3 ____ __..Ja;,.,s..,.c .. anwU.,.·cta ... c..,le..,s.,,d.,.e...,la¡¡..;c ..,_ ·c,,_,)hwm ..,_ i1 .,. 1¡,._. , a ... owte.._ n=·o r 1 2 1 A 400 600 .¡ � #máximo de acres que 500 700 350 1200 500 2200 600 01 O l Consumo de agua Cosecha Precio de venta .lfo�:Cl.ll 111Jillmlc·s/n�:r� (1ml1111ida!ll 6 50 2500 hasta 10000 unidades 2000 a partir de 10000 unidades 5 100 1500 hasl.a 40000 unidades 800 a partir de 40000 unidades 4 75 4500 hasta 20000 unidades 4 ) Para mantener una carga de trabajo similar en las tres granjas, el granjero adopta una política en la que las 3 granjas deben tener el mismo porcentaje de tereno cultivable plantado. Sin embargo, cualquier combinación de los tipos de grano puede cultivarse en cualquiera de las tres granjas. Los únicos gastos con los que cuenta el granjero son de utilización de agua. ¿Qué parte de cada granja debe destinarse a los distintos granos para maximizar el beneficio neto del granjero? 40. Un granjero puede alquilar hasta un máximo de 1000 áreas de terreno. Debe pagar 500 pts/area por año si alquila hata 600 áreas. Por encima de 600 áreas puede alquilar a 800 pts/área y año. En el terreno cultiva maíz y puede cultivarlo a un nivel normal o a nivel intensivo (más fertilizante, riego frcuente,etc.) El nivel normal produce un rendimiento de 70 fanegas por acre; el nivel intensivo proporciona 100 fanegas por acre. Los requisitos se dan en la siguiente tabla. Necesidades por acre y ano Trabajo(hombres-hora Material (semillas,fertilizante, agua, etc.) Nivel normal 6 2000 pts Nivel intensivo 9 3500 pts Para la recolección son necesarios 0.5 hombres-hora por fanega recogida. El granjero puede vender maíz al por mayor a un precio de 250 pts por fanega. El granjero también puede criar aves; para criar un ave se necesitan 25 fanegas de maiz, 20 hombres hora de trabajo y 25 pies cuadrados de cobertizo. El maíz necesaiio en la cría de aves puede ser el que él mismo ha plantado o puede comprarlo al por menor a un precio de 350 pts por fanega. Puede vender al por mayor las aves criadas a un precio de 17500 por ave hasta un máximo de 200 unidades. Cualquier cantidad por encima de las 200 unidades se vende a 16000 pts. Para la cría de aves dispone de un único cobertizo del5000 pies cuadrados. El granjero y su familia pueden contribuir con 4000 hombres-hora de trabajo anual a coste nulo. Si necesita más hombres-hora, puede contratarlos, hasta 3000, a 300 pts hombre-hora; por encima de dicha cantidad, debe pagar 600 pts por hombre-hora. Maximiza el beneficio neto. Programación Lineal l. Sea una matriz A= [a¡j] de dimensión mxn (m::;;n) y un vector de m componentes b=[b¡]. Supongamos que aij>0 y b¡>0 i=l, ... ,m, j=l, ... ,n. ¿Es siempre posible encontrar un vector x tal que Ax;?:b? ¿Es siempre posible encontrar un vector x tal que Ax=b?¿Es siempre posible encontrar un vector x;?:0 tal que Ax=b? ¿Por qué? 2.Dada la matriz A= 11 1 2 3 2 4 6 Demostrar que no existe x tal que Ax=b. 3 3 6 b= 1 I 1 3.¿ El conjunto de soluciones de Ax;?:0 fo1ma un cono? ¿Un cono convexo? 4. Demostrar la siguiente forma alternativa del lema de Minkowski-Farkas: Ax$b tiene una solución no negativa {::> V 1t;?:0, 1tA;?:0 ⇒ 1tb;?:0. 5.Considera la envolvente convexa de un número finito de puntos dados del plano. ¿Son los puntos dados los extremos de la envolvente convexa? ¿Si los puntos son (5,0), (2,1), (0,6) y (O.O) cúal es la envolvente convexa? 6. Determina si las siguientes funciones reales son convexas. i)f(x) = lxl ii)f(x) = x2 iii)f(x) = J c l-c x;?:0 x<0 ¿Cúal de las funciones antetiores es est,ictamente convexa? Constrnye una función continua que no sea ni cóncava ni convexa. 7. Construye a) un cono que no sea un conjunto convexo b)un conjunto convexo que no sea un cono 8.Define una función convexa en el conjunto convexo -3$ x ::;;4 tal que f(-3) =3 y f(4) =2. ¿Cúal es el valor máximo de esta función convexa? ¿Por qué? 9.Dado el problema lineal min z = 6 x 1 + 3 x2 + x3 + 7 x4 + 8 x5 x¡ + 2 x2 + 7 x3 6 x2 + 3 x3 + x4 -x5 Xj�D. j=l, ... .5 =9 =9 Busca cuatro vectores diferentes que sean respectivamente a) solución factible, b) solución básica no factible, c) solución posible básica y d) solución básica óptima. Utiliza el método del simplex para resolver el programa anterior. 10. ¿Qué formas de los costes reducidos de las va1iables no básicas garantizan que la solución óptima es única? ¿Qué formas garantizan que la solución óptima no es única? 11. Considera el programa min z = 10 X[ • X3 +X4 + X3 + 1/2 X4 •3 x5 +3 x5 +2 x5 =3 =2 Toma inicialmente x ¡, x2 como variables básicas y selecciona siempre la columna lexicográficamente menor para entrar en la base. Comprneba los cálculos en cada paso mediante z=1tb (La constante 10 no debería incluirse en la comprobación z=1tb) 12. Construye un programa lineal en el que las variables de holgura sean no nulas en la solución óptima. 13. Formula en términos matemáticos las siguientes afirmaciones. a) Si una actividad es estrictamente no aprovechable en términos de los precios sombra, el nivel de dicha actividad debe ser O. b) Si un recurso no se utiliza totalmente, entonces el precio sombra correspondiente a ese recurso debe ser cero. 14. Considera el programa min z= 11 X[ + x3•x4 + 2 x5 -x3 + 2 x4 +x5 =2 = l Sean x¡ y x2 las variables básicas iniciales. Elige para entrar en la base el vector para el que la función objetivo tenga el mayor decremento entre todos los candidatos a entrar en la base. Describe una regla para seleccionar dichos vectores en términos de Cj, a¡j, b¡. 15. Considera el problema lineal min z = X] X[ X[ x3 +x3 Escribe su problema dual y sus variables duales a) todas sin restricciones de signo y b) todas restringidas a ser no negativas. 16. Da un ejemplo en el que tanto el problema primal como el dual sean no factibles. 17. Demuestra que si el problema primal tiene una solución óptima degenerada, entonces la solución óptima del problema dual no es única. 18. Si una desigualdad de un problema lineal se satisface como estricta igualdad en la solución óptima, entonces el precio sombra correspondiente a esa desigualdad es cero. Si una desigualdad de un programa lineal se satisface como igualdad en la solución óptima, entonces el precio sombra correspondiente a esa desigualdad es positivo. Interpreta estos resultados en té1minos económicos. 19. Considera el problema min {ex/ Ax=b, x�O} (A es mxn) y su dual. Supón que B es una matriz de base óptima. Demuestra que 1t=cBB-l es una solución óptima para el problema d_ual, donde el vector CB está formado por las componentes de e que corresponden a las variable básicas óptimas. (Puedes utilizar el hecho de que ex� 1tb se cumple para cualquier x y 7t que sean soluciones factibles para los problemas primal y dual respectivamente). 20. Resuelve los siguientes problemas mediante el Simplex Revisado min z = maxw= X[ X¡ + 6 X2 · 7 x3 + x4 + 5 x5 x ¡ · 3/4 x2 + 2 x3 • 1/4 x4 -1/4 x2 + 3 x3 -3/4 x4 Xj�O. j=l, ... ,5 78 x2 + 21 x3 -124 x5 x3 + x4 · 8 x5 6 x2 · x3 + x5 + 4 xz + x3 · 5 x5 Xj�O. j=l, ... ,9 + x5 + X6 =5 =5 + 6 X7 + 17 Xg + 2 X7 • xg · 2 x7 + 4 xg + xg + 10 x9 ·3 x9 = 33 =27 + x9 =86 21. Considera el problema de programación lineal max {ex/ Ax=b, x�} (_A es mxn). Sea XB la solución óptima asociada a la matriz de base B. a) Supón que b se substituye por b+Ad, donde A es un escalar y d un vector no nulo m dimensional. Da una condición para que la base B siga siendo óptima V A �O. b) Supón que c se substituye por c+Ag, donde A es un escalar y g un vector no nulo n dimensional cuyas componentes asociadas a las actividades básicas son todas nulas. Da una condición para que la base B siga siendo óptima V A �O. Sin embargo, los técnicos prevén dos meses anómalos. El primero los beneficios netos serán de 63 pts. por paquete de Frisky Pup y de 49 pts. por paquete de Husky Hound, pero solo se podrán contratar 200000 Kg. de cereales y 150000 Kg. de carne. El segundo será un més normal en todo excepto en que la contribución neta del Frisky Pup será de 63 pis. por paquete y sólo se podrán empaquetar 50000 paquetes. ¿Qué ocurrirá? 40. Considerar el siguiente programa lineal: min z(x) = -2x} -4x2 -x3 X} + 3x2 2x1 +x2 x2 +4x3 Xj�0. Vj En el que x5, X6, x7 son las variables de holgura correspondientes a las restricciones de disponibilidad de recursos. La base -115 3/5 -1/10 1/20 2/5 -1/5 correspondiente al vector básico (x1, x3, x2) es la óptima. o 1/4 o a) Si sólo podemos aumentar la capacidad de un recurso ¿cúal debemos elegir? ¿por qué? b) Dentro de qué intervalo de valores de b¡ (cantidad de recurso 1 disponible) continua siendo óptima la base B? ¿Cúal es la solución óptima del problema si b¡=20? c) Si podemos tener 7 unidades más del recurso 1 (además de las 8 que tenemos actualmente) ¿Cúal sería el precio máximo que estaríamos dispuestos a pagar por ellas? ¿Por qué? d) La compañía tiene opción a producir un nuevo producto. Sea xg el número de unidades de dicho producto que se han fabricado. El vector de coeficientes tecnológicos de xg sería (20, 24-3A, -25+Al4)', donde A es un parámetro que puede tomar valores entre O y 6. ¿Cúal es el mínimo valor de 'A. a partir del cual resulta provechoso producir el producto, siendo cg=lO? ¿Cúal es la solución óptima cuando 'A.=4? 41. Una empresa de productos químicos fabrica disolventes a base de mezclar diferentes disolventes básicos. Los datos del proceso son: Producto 1 contenido (unidades/kg.) Producto 2 Disolventes básicos 1 2 3 4 180 120 90 60 Unidades de cada produclO por kg. de mezcla contenido (unidades/kg.) 3 2 6 5 �4 coste (Pts/kg.) 16 12 10 11 Si Xj es la proporción de disolvente básico de tipo j, j=l,2,3,4 en la mezcla. la mezcla de coste mínimo viene dada por la base óptima 3/2 a-1= -112 o o -1/4 1/4 135 -1 -15/2 asociada con (x2,x3,x5), (x5 es la holgura de la primera restricción de desigualdad). a) Formular el problema dual y las condiciones de holgura complementaria. ¿Cúal es la solución óptima dual? b) ¿Cúanto cambia la función objetivo si el requisito del producto 1 baja a 88 unidades? c) Sea Pi el mínimo requerimiento del producto 1 (inicialmente P1 =90). ¿Para qué intervalo de valores de P1 sigue siendo B la base óptima? ¿Cúal es la base óptima si P1=114? d) ¿Cúanto hay que cambiar el coste por kg. del disolvente básico 3 para que B deje de ser óptima? ¿Cúal es la solución óptima cuando el coste por kg. de 3 es 11 pts? 42. Una empresa siderúrgica tiene que producir 1000 libras de un acero que contenga al menos un 0,35% de manganeso y no más del 3,2% de silicio. Dispone para ello de tres tipos de acero bruto, en cantidades ilimitadas, con las características siguientes: Tipo de Acero Bruto Silicio Manganeso Coste/! 000/Libras A 4% 0,35% 28$ B 1% 0,4% 30$ e 5% 0,3% 20$ Suponiendo que el acero deseado se puede obtener mezclando los aceros brutos fundidos, en las proporciones adecuadas: a) Formular el problema como un programa de programación lineal que minimice los costes b) Resolverlo mediante el algoritmo del simplex primal. La tabla óptima es x1 X(j -253 -10 x4 1/5 x2 0.5 0.5 4 x5 x7 10 10 -4 -17 -1 -3 x3 0.5 0.5 -14 x1, x2, x3 son las variables originales X4 holgura de la restricción de :,; (% de silicio) x 5 exceso de la restricción de � (% de manganeso) X6 y x7 artificiales c) Qué coste debe tener el acero bruto A (x1) para estar en la solución? ¿A quién sustituye? d) ¿Qué precio estaríamos dispuestos a pagar para añadir manganeso a la mezcla? e) ¿En cúanto se puede modificar el requerimiento de manganeso sin modificar la base? ¿Cúales son los valores de las otras variables básicas cuando esto sucede? f) ¿Cómo puede ser óptima esta tabla, si el coste reducido de la vaiiable X6 es -10? g) En caso de disponer de un acero bruto alternativo con un 6% de silicio y un 4% de manganeso ¿Qué coste habría de tener para interesar? ¿A quién sustituiría? h) ¿Qué pasaría si por limitaciones de mercado x2 no pudiera ser mayor de 400 libras? 43. Los carbones procedentes de tres minas distintas tienen como impurezas fósforo y cenizas. Cierto proceso industrial requiere 100 Tm. de combustible consistente en briquetas obtenidas por compresión de una mezcla de dichos carbones. Las caracte1isticas del proceso exigen que el combustible no contenga más del 3% de cenizas, ni más del 0,03% de fósforo. Teniendo en cuenta los datos siguientes: Carbón % Fósforo 1 0.02 2 3 0.04 0.03 %Cenizas 3 2 5 a) ¿Cúal es la composición óptima de la mezcla? Coste (Miles de pts. por Trn) 8 5 6 b) ¿Qué ocurriría si hubiese un carbón alternativo con un O.Ol % de fósforo, un 4% de cenizas y un coste de 9000 pts. por Tm? c) ¿Y si se restringiese el fósforo al 0.02% y las cenizas al 2.5%? d) ¿ Y si además se decidiese controlar el contenido de azufre, presente en las cantidades: Carbón 1 2 3 % Azufre 3% 6% 5% respectivamente, no permitiendo que en la mezcla aparezca más de un 4%? e) ¿Qué solución se obtendría en el caso de que por razones de producción no pudiese disponer más de 30 Tm. del carbón 1? f) Plantear el problema dual. Obtener su solución. Escribir las ecuaciones del teorema de holgura complementaria correspondientes a este problema. Interpretarlas. 44. Considerar el siguiente problema de dietas: Contenido del nutriente Nutriente en la comida disponible Verrluras Patatas Maiz Vitamina A 10 1 9 c 10 10 10 D 10 11 11 Coste (pts/kg) 50 100 51 Requerimientos mínimos diarios del nutriente 5 50 10 Sean x1, x2 y x3 las cantidades de verduras, patatas y maíz que se incluyen en la dieta. Sean X4, x5, X6 las variables de holgura que representan, respectivamente, los excesos de vitaminas A, C y D. La base B asociada al vector básico (X4, x1, X6) es la óptima para este problema: -1 1 O wl= O 1/10 O O -1 a) Encontrar las soluciones óptimas primal y dual asociadas con la base B. b) Hay otro alimento, leche, que tiene, O, 10 y 20 unidades de vitaminas A, C y D respectivamente y cuesta 40 pts./lt. ¿Es recomendable incluirla en la dieta? ¿Por qué? ¿Cúal es el mayor precio de la leche para el que aun resulta atractivo incluirla en la dieta? c) Considerar de nuevo el problema original. Un especialista en nutrición considera que los requerimientos mínimos diarios deben ser realmente, 5, 5+A. y 10+ 15A., donde A. es un parámetro no negativo. Suponiendo que esté en lo correcto, encontrar A. , valor máximo de A. para el que B todavía es óptima. ¿Cúal es la solución óptima para A.= X"+ 1? 45) La dirección de una central térmica que produce energía eléctlica utilizando carbón como combustible, está estudiando un plan de operación que satisfaga los estándares de emisión establecidos por las leyes de control de la polución. Para la central en cuestión las máximas tasas de emisión admitidas son: . máxima emisión de óxido de azufre: 3000 partes por millón (PPM) . máxima emisión de partículas (humos): 12 Kilogramos/hora (Kg/hora) El carbón es traído hasta la central en femocarril, donde se almacena para ser llevado en una cinta transportadora hasta la unidad de pulverización, donde una vez pulverizado, pasa a alimentar directamente la cámara de combustión según la tasa deseada. El calor producido en la cámara de combustión se utiliza para producir el vapor que mueve las turbinas. Se utilizan dos tipos de carbón: el carbón de tipo A, que es un carbón duro de combustión limpia, con un bajo contenido de azufre, aunque bastante caro; y el carbón de tipo B, que es más barato, relativamente blando y con humos de alto contenido en azufre, tal como indica la tabla: Emisión de polucionantes Carbón Oxidos de Azufre en los gases de la chimenea A 1800 PPM B 3800 PPM Partículas (Emisión/fonelada) 0.5 Kg. 1.0 Kg. La capacidad térmica (expresada en función del valor producido) es de 24000 libras por tonelada para el carbón A, y 20000 libras por tonelada para el carbón B. Dado que el carbón A es más duro, la unidad de pulverización sólo puede tratar hasta 16 toneladas por hora, mientras que puede pulverizar hasta 24 toneladas de carbón B por hora. La cinta transportadora tiene una capacidad de 20 toneladas por hora, independientemente del tipo de carbón que transporte. Dados los tipos de carbón disponibles y sus características, y los límites de emisión de polucionantes; suponiendo que la cantidad de electricidad producida es una función de la cantidad de vapor producida ¿Cúal sería la máxima cantidad que se pod1ia producir? a) Formular el problema b) Hallar una primera solución real posible c) Discutir si hay o no otra posibilidad de iniciar las iteraciones del simplex. En caso de haberla, efectuar la primera iteración. 46. La compañía "Talla Clásica de Piedras" produce cuatro tipos de esculturas de piedra: figuras, figurines, formas libres y estatuas. Cada producto requiere las siguientes horas de trabajo de talla, cincelado y pulido: Operación Figuras Figurines Fonnas Libres Es1a1uas Corte 30 5 45 60 Cincelado 20 8 60 30 Pulido o20 o 120 Benelicio/wtidad 33600 4800 60000 61200 La última fila de la tabla específica la contribución unitaria de cada producto al beneficio neto. La compañía dispone de las capacidades de producción siguientes: 300 horas de corte, 180 horas de cincelado y 300 horas de pulido por semana. a) Hallar el programa de producción que maximiza el beneficio neto. b) ¿En qué intervalo de la capacidad de corte sigue siendo óptima la solución hallada? c) La compañía estudia una ampliación de mercado a base de fabricar un nuevo producto: bustos, con las siguientes características: Corte 15 horas Cincelado 10 horas ¿Es interesante? Pulido 20 horas Beneficio unitario 28800 pts d) La compañía puede contratar 5 hora adicionales de corte y 5 de cincelado a un contratista externo por un coste total de 9000 pts. ¿Debe contratarlas? e) ¿En qué condiciones sería interesante incrementar la producción de formas libres? f) ¿Cúal sería el programa de producción semanal para satisfacer un pedido de no más de 5 estatuas y no menos de 2 figurines? 47. Dado el problema de programación lineal siguiente: Una unidad de producción debe producir por lo menos 100 unidades de un producto; para ello dispone de cuatro procedimientos distintos de fabricación caracterizados por: 1) Cantidad de producto producida a nivel unitario 2) Cantidades consumidas por unidad del recurso materia prima (disponemos en total de 60) 3) Cantidades consumidas por unidad del recurso tiempo de proceso (disponemos de 40) 4) Costes unitarios de producción cuyos valores numéricos son: Procedimiento 1 Procedimiento 2 Procedimiento3 Procedimiento 4 !) 4 2 10 3 2) 1o 3 2 3)81 1 4) 2 5 10 7 Encontrar el programa de producción que minimiza los costes. Se pide: a) Definir una versión del algoritmo del simplex dual que resuelva directamente los problemas de programación lineal formulados como problemas de minimización b) Aplicarlo al problema propuesto y obtener una solución óptima 48. Formulado el problema 47 como: min z= 2x¡ + 5 x2 + 10 x3 + 7 x4 4 x¡ + 2 x2 + 10 x3 + 3 x4 � 100 x¡ +3 x3 +2 x4 560 8 x¡ + x2+ x3 + 3 x4 5 40 x¡, x2, x3, x4 � O La tabla óptima del simplex dual para minimización es x¡ x5 -1750/19 39/38 75/19 1/76 x2 61/19 2/19 x7 x4 5/19 179/38 5/38 27/76 X6 585/19 23/76 -11/19 1/38 89/76 x3 160/19 -2/19 3/19 -1/19 3/19 a) Interesaría un procedimiento de fabricación cuyos coeficientes tecnológicos fuesen (3, 2, 6) respectivamente, con un coste unitario 2? b) Analizar lo que ocurre si forzamos que X4 intervenga (entre en la base) c) Estudiar la parametrización de e¡ en la forma c¡ = 2 + 2 f Flujos en redes y transporte 1. El administrador de un hospital necesita establecer una planificación de los turnos de las enfermeras que cumplan los requisitos diarios que se exponen en la siguiente tabla. Tumo 2 3 4 5 6 Horario 6 a.m 10 a.m. 2 p.m. 6 p.m. 10 p.m. 2 a.m. a a a a a a 10 a.m. 2 p.m. 6 p.m. 10 p.m. 2 a.m. 6 a.m. Nº mfnimo 70 80 50 60 40 30 de enfenneras Las enfermeras que empiezan a trabajar en cualquiera de los 5 primeros tumos trabajan durante 8 horas consecutivas, mientras que las que entran en el último tumo (2 a.m. a 6 a.m.) trabajan durante 4 horas. El administrador desea determinar el mínimo número de enfermeras que deben emplearse para asegurar un número suficiente de enfermeras durante cada turno. Formula este problema como un problema de flujos en redes. 2. Como parte de su servicio, una empresa de catering necesita dj servilletas cada uno de los días de la semana próxima. La empresa puede comprar las servilletas a un precio de a pts. cada una o llevar a la lavandería las que ya posee. La lavande1ia proporciona dos tipos diferentes de servicio: regular y urgente. El servicio regular tarda dos días laborables y cuesta p pts. por servilleta, mientras que el servicio urgente tarda un único día laborable y cuesta y pts. por servilleta (y >P). El problema consiste en determinar una política de compra y envío a la lavandería de servilletas que satisfaga la demanda al menor coste posible. Formula este problema como uno de flujo de coste mínimo. (Ayuda: define una red con 15 nodos, de los cuales 7 nodos correspondan a servilletas usadas, 7 nodos corresponden a servilletas nuevas y un nodo para la provisión de servilletas nuevas.) 3. En un nuevo programa académico subvencionado por la industria, cada alumno de licenciatura debe realizar un proyecto de 6 meses de duración en una empresa. Dada la importancia de los proyectos en el curriculum de los estudiantes y dado que éstos varían considerablemente de una empresa a otra, los estudiantes desean poder elegir un proyecto de su agrado. Para asegurar que la asignación de proyectos es "justa" los profesores y estudiantes han decidido realizar lo siguiente: Cada estudiante establece una ordenación por preferencia creciente de los proyectos ofertados. El objetivo es asignar proyectos a estudiantes de forma que se consiga la mayor suma total de preferencias de proyectos asignados. Existen, sin embargo, varias restricciones; cada estudiante debe trabajar en, exactamente, un proyecto y cada proyecto tiene una cota superior del número de estudiantes que puede aceptar. Cada proyecto debe tener un supervisor perteneciente a un grupo conocido de profesores elegibles. Finalmente, cada uno 60 de estos profesores tiene cotas (superior e inferior) del número de proyectos que puede supervisar. Formula este problema como uno de flujo de coste mínimo. 4. Una compañía aérea ofrece 6 vuelos diarios de Barcelona a Madrid. Desde las 10 a.m. hasta las 8 p.m. los vuelos salen cada 2 horas. Los tres primeros vuelos tienen una capacidad de 100 pasajeros, mientras que los tres últimos vuelos pueden acomodar a 150 pasajeros cada uno. Cuando por overbooking un pasajero con reserva no tiene plaza en el vuelo planeado, la compañía asigna a dicho pasajero a un vuelo posterior. Cualquier pasajero que sufra un retraso de más de 2 horas sobre la hora de salida planificada resulta indemnizado por la compañía con 20000 pls. más 2000 pts. adicionales por cada hora de retraso. Esta compañía siempre puede acomodar a todos pasajeros que hayan sido retrasados del vuelo de las 8 p.m. en el vuelo de las 11 p.m. de otra compañía aérea que siempre tiene muchísimas plazas libres. Supongamos que al principio de un día cualquiera, los seis vuelos de la compañía tienen 110, 160, 103, 149, 175 y 140 reservas confirmadas respectivamente. Formula el problema de determinar la estrategia más económica para la compañía como un problema de flujo de coste mínimo. 5.Varias familias salen a cenar juntas. Para aumentar su relación social, intentan sentarse en mesas de forma que no haya más de un miembro de cada familia en cada mesa. Formula este problema como uno de flujo máximo; para ello supón que hay p familias y que la i-ésima familia tiene a(i) miembros. Supón también que hay q mesas disponibles y que la j-ésima mesa tiene una capacidad para bU) personas. 6. La figura (b) representa una solución factible para el problema de flujo de coste mínimo de la figura (a). Convierte esta solución en una solución asociada a un árbol generador (solución posible básica) con un coste igual o inferior. LO (4. LO) -5 7. Busca una solución óptima utilizando el Simplex para problemas de flujos en redes para el siguiente problema. Toma como solución posible básica inicial la asociada al árbol generador T=( (1,2), (3,2), (2,5), (4,5), (4,6)), L={(3,5)} y U={(l,3), (2,4), (5,6)). o o @ (5, 15)► © (3, 10) (I, l5>/ t (2, 10) � " 20 /"j\ (S, IO) f6\ -20 \..!./ (7.20) �� (4, 15) �® ►S (2,15) O (6, 10) O 8. Utiliza el algoritmo primal-dual para resolver el siguiente problema de caminos mínimos: 9. Resuelve los siguientes problemas de caminos mínimos: (a) 10. Calcula las distancias mínimas entre Chicago y las otras nueve ciudades del medio oeste. 2 1 4 s 6 1 8 2 lQ 1 Chicago 96 105 50 41 86 46 29 56 70 2 Dallas 78 49 94 21 64 63 41 37 3 Denver 60 84 61 54 86 76 SI 4 Kansas City 45 35 20 26 17 18 s Minneapolis 80 36 SS 59 64 6 Oklahoma City 46 50 28 8 7 Omaha 45 37 30 8 St. Louis 21 45 9 Springfield 25 10 Wichila 11. Utiliza el algoritmo primal-dual para resolver los siguientes problemas: a) min 3 XI + 2 x2+ x3 + 2 x4 +2 x5 x¡ -x2 + 2 x3 - X4 +xs + 2 X6 =1 -x¡ + 2 x2 +x3 -2 x4 -xs + X6 =3 2 x¡ + x2 -x3 +x4 -2 xs + X6 =2 xi�o. j=l, ... ,6 b) min -x2 + 10 x3 + 14 x4 + 3 x5 x¡ +x3 +X4 +xs '° 5 x2 + 2 x3 +x4 -xs =6 x¡ +x2 + 3 x3 + 2 x4 =4 Xj�O. j=l, ... ,5 12. Utiliza el algoritmo primal-dual para resolver el siguiente problema de transporte: b 3 1 4 5 3 2 5 4 1 2 3 4 3 3 2 1 5 2 5 2 2 2 1 2 a 3 2 1 4 13. Utiliza el algoritmo primal-dual para resolver el siguiente problema de transporte: b 3 3 6 2 5 3 7 3 8 5 5 6 12 5 7 11 2 8 3 4 8 2 11 6 10 5 10 9 14. Considera el flujo factible para la red de la siguiente figura (x .. u .. ) f:'\ �' IJ G) \!;,./�I a 4 5 3 5 i) Especifica cuatro conjuntos de corte entre los nodos 1 y 7, que contenga, cada uno de ellos cuatro arcos progresivos. ii) Dibuja la red residual y busca cuatro caminos aumentativos de flujo desde 1 a 7. 15) Resuelve el siguiente problema de flujo máximo y especifica el corte mínimo obtenido. 01/�� �df�V.