Practica 2

Modelizacion de problemas lineales

En esta practica formularemos algunos modelos con mas de dos variables, aunqueseguiremos teniendo que hacer un esfuerzo y suponer que no hace falta exigir que lasvariables tomen valores enteros. Recordar que estamos en Programacion Lineal. Detodas maneras, puedes anadir esta condicion cuando lo consideres oportuno.

1. Una fabrica puede producir 5 productos diferentes. Cada producto necesita untiempo de proceso, en minutos, en cada maquina de la forma siguiente:

MaquinaProducto 1 2 3

A 12 8 5B 7 9 10C 8 4 7D 10 0 3E 7 11 2

Cada maquina esta disponible 128 horas a la semana. Los productos A, B, C sonmuy competitivos y cualquier cantidad producida se puede vender a un preciopor unidad de $5, $4 y $5 respectivamente. Las primeras 20 unidades producidespor semana de los productos D y E se pueden vender a $4 cada una, pero las quepasen de 20 solo se pueden vender a $3. El coste de la mano de obra es de $4 porhora en las maquinas 1 y 2, y de $3 por hora en la maquina 3. Los costes de losmateriales son de $2 para los productos A y C, y $1 para los productos B, D yE. Formular un modelo para maximizar el beneficio de la fabrica.

2. La American Metal Fabrication Company (AMFC) fabrica diversos productos apartir de barras de acero. Una de las operaciones iniciales es darles forma mediantemaquinas de rodillos. Existen 3 maquinas disponibles para esta operacion, B3,B4 y B5. Las caracterısticas aparecen en la tabla siguiente:

Velocidad Grosor admisible Horas disponibles Coste de la manoMaquina (pies/min) del material por semana de obra por hora

B3 150 3/16 a 3/8 35 $10B4 100 5/16 a 1/2 35 $15B5 75 3/8 a 3/4 35 $17

(Este tipo de combinacion de capacidades no es extrano: maquinas que procesanmaterial mas grande trabajan a menor velocidad).

Esta semana se han de fabricar 3 productos. AMFC ha de producir al menos218000 pies de material de 1/4 de pulgada, 114000 pies de 3/8 pulgadas y 111000pies de 1/2 pulgada. El beneficio por pie de producto, excluido el coste de la manode obra, es de 0.017, 0.019 y 0.02. Estos precios se refieren a toda la produccion, esdecir, se aplican tambien a cualquier exceso sobre la produccion mınima requeri-da. El departamento de transportes a los clientes tiene una capacidad maximade 600000 pies por semana de material de cualquier grosor.

La compania quiere determinar el plan de produccion que maximice el beneficio.

1

3. Una oficina de correos necesita un numero diferente de trabajadores a tiempocompleto cada dıa de la semana, tal como aparece en la tabla.

Dıa TrabajadoresLunes 17Martes 13Miercoles 15Jueves 19Viernes 14Sabado 16Domingo 11

Cada trabajador trabaja 5 dıas consecutivos y descansa los dos dıas siguientes.Por ejemplo, un trabajador que trabaja de lunes a viernes, ha de descansar saba-do y domingo. La oficina quiere cubrir sus necesidades utilizando unicamentetrabajadores a tiempo completo. Formular el modelo que la oficina puede usarpara minimizar el numero total de trabajadores que ha de contratar para cubrirsus necesidades.

4. Un problema de decision multiperiodo

Sailco Corporation ha de decidir que cantidad de veleros ha de producir durantecada uno de los cuatro trimestres siguientes. Se sabe que las demandas que hade cubrir son: 40 veleros el primer trimestre, 60 el segundo, 75 el tercero y 25 elultimo. Al principio del primer trimestre Sailco dispone de un stock de 10 veleros.Al principio de cada trimestre la empresa ha de decidir cuantos veleros ha defabricar durante ese trimestre. Por simplicidad podemos suponer que los velerosproducidos durante un determinado perıodo se pueden utilizar para atender lademanda del mismo perıodo. Siguiendo un plan de produccion normal, Sailcopuede fabricar cada trimestre hasta un maximo de 40 veleros con un coste deproduccion de 400$ por velero. Si los empleados trabajan horas extra es posibleproducir mas veleros, pero el coste serıa, en este caso, de 450$ cada uno.

Al final de cada trimestre, una vez cerrado el plan de produccion y satisfecha lademanda, se incurre en un coste extra de 20$ por cada velero que queda alma-cenado para el siguiente trimestre. Formular un modelo de Programacion Linealque permita decidir la planificacion de la produccion adecuada para minimizar elcoste de produccion mas el de almacenamiento.

2

5. La Winston-Salem Development Management (WSDM) esta intentando com-pletar sus planes de inversion para los proximos 3 anos. Actualmente WSDMdispone de 2 millones de dolares para inversiones. A intervalos de 6 meses durantelos proximos 3 anos WSDM espera los siguientes ingresos, provenientes de otrasinversiones: $500000 (dentro de 6 meses), $400000, $380000, $360000, $340000i $300000 (dentro de 3 anos). Hay tres proyectos en los que WSDM esta con-siderando participar. El Foster City Development tendrıa, si WSDM participara,el siguiente flujo de capital cada 6 meses en los proximos 3 anos (cantidadesnegativas representan inversiones y cantidades positivas beneficios): -$3000000,-$1000000, -$1800000, $400000, $1800000, $1800000, $5500000. La ultima canti-dad es el valor estimado de la inversion al final de los 3 anos. Un segundo proyectose refiere a hacerse cargo de la gestion de unos bloques de viviendas antiguas, conla condicion de que se haran algunas reparaciones iniciales y serıan derribadasal final de los 3 anos. El flujo de capital serıa: -$2000000, -$500000, $1500000,$1500000, $1500000, $200000 i -$1000000.

El tercer proyecto, Hotel Universe, tendrıa el siguiente flujo de capital: -$2000000,-$2000000, $1800000, $1000000, $1000000, $1000000 i $6000000. WSDM puedepedir prestamos por intervalos de 6 meses a un interes del 3.5% cada medioano. Puede tener creditos pendientes por un maximo de 2 millones de dolares.Ademas, si no invierte todo el capital en los proyectos, puede colocar los fondossobrantes a un interes de 3 % cada seis meses.

Inicialmente no se tienen en cuenta los impuestos. Si WSDM no participa enun proyecto al 100 %, puede hacerlo en otro porcentaje y los flujos de capital sereducirıan en el mismo porcentaje. Calcular el plan de inversiones que maximiceel valor neto de WSDM al final de los tres anos.

6. CSL es una cadena de tiendas de computadoras. El numero de horas de mano deobra cualificada que CSL necesitara los proximos 5 meses es:

Enero 6000 horasFebrero 7000 horasMarzo 8000 horasAbril 9500 horasMayo 11000 horas

Al principio de enero, 50 tecnicos cualificados trabajan para CSL. Cada tecnicocualificado puede trabajar hasta 160 horas por mes. Para atender demandas fu-turas, es necesario entrenar nuevos tecnicos. Entrenar un tecnico cuesta un mes.En ese mes el aprendiz ha de estar supervisado por un tecnico cualificado 50horas. Cada tecnico cualificado cobra $2000 al mes (incluso si no trabaja el maxi-mo de 160 horas). Durante el mes de aprendizaje, un aprendiz cobra $1000. Alfinal de cada mes, un 5 % de los tecnicos cualificados deja la empresa para irsea trabajar a una empresa de la competencia. Formular un problema lineal paraminimizar el coste total de la mano de obra necesaria para cubrir la demandaestimada.

3

7. La Pittsburgh Steel (PS) Co. ha sido contratada para producir un nuevo tipo deacero, con las siguientes especificaciones:

Como mınimo Como maximoContenido de Carbono 3.0 % 3.5 %Contenido de Cromo 0.3 % 0.45 %Contenido de Manganeso 1.35 % 1.65 %Contenido de Silicio 2.7 % 3.0 %

PS tiene los siguientes materiales disponibles para fabricar el nuevo producto:

Coste Carbono Cromo Manganeso Silicio CantidadMaterial por libra ( %) ( %) ( %) ( %) disponibleHierro fundido 1 0.03 4.0 0 0.9 2.25 IlimitadaHierro fundido 2 0.0645 0 10.0 4.5 15.0 IlimitadaHierro-silicio 1 0.065 0 0 0 45.0 IlimitadaHierro-silicio 2 0.061 0 0 0 42.0 IlimitadaAleacion 1 0.10 0 0 60.0 18.0 IlimitadaAleacion 2 0.13 0 20.0 9.0 30.0 IlimitadaAleacion 3 0.119 0 8.0 33.0 25.0 IlimitadaCarbide (Silicio) 0.08 15.0 0 0 30.0 20 librasAcero 1 0.021 0.4 0 0.9 0 200 librasAcero 2 0.02 0.1 0 0.3 0 200 librasAcero 3 0.0195 0.1 0 0.3 0 200 libras

Se ha de producir una tonelada (2000 libras) del nuevo acero, cumpliendo losrequerimientos mencionados. El problema es decidir que cantidad de cada unode los once materiales ha de utilizarse para minimizar el coste de produccion. Unexperto en aceros opina que el compuesto de mınimo coste no utilizara mas denueve de los once materiales. ¿Cual es la mejor mezcla?. La mayor parte de losonce precios y de las cuatro especificaciones del nuevo producto son negociables.¿Que precios y especificaciones valdrıa la pena discutir?

Supongamos ahora que se puede bombear oxıgeno al horno de fundicion. Eloxıgeno quema completamente el carbono produciendo CO2 que se escapa. Eloxıgene quema el carbono a razon de 12 libras de carbono quemado por cada32 libras de oxıgeno bombeado. El oxıgeno cuesta 0.02$ por libra. Reformular elproblema con esta opcion adicional. ¿Cambiara la decision inicial?

8. Islandia tiene cuatro importantes sectores exportadores: Acero, Automocion,Electronica y Plasticos. El ministro de Economıa de Islandia quisiera maximizarla relacion exportacion/importacion. La unidad monetaria de Islandia es la coro-na. Los precios en coronas en el mercado mundial por unidad de Acero, Au-tomocion, Electronica y Plastico son, respectivamente, 500, 1500, 300 y 1200.La produccion de una unidad de Acero requiere 0.02 unidades de Automocion,0.01 unidades de Plastico, 250 coronas de materiales adquiridos en el mercadomundial y medio ano/hombre de mano de obra. La produccion de una unidad deAutomocion requiere 0.8 unidades de Acero, 0.15 unidades de Electronica, 0.11unidades de Plastico, un ano/hombre de mano de obra y 300 coronas de material

4

importado. La produccion de Automocion esta limitada a 650000 unidades. Laproduccion de una unidad de Electronica requiere 0.01 unidades de Acero, 0.01unidades de Automocion, 0.05 unidades de Plastico, medio ano/hombre de traba-jo y 50 coronas de material importado. La produccion de una unidad de Plasticorequiere 0.03 unidades de Automocion, 0.2 unidades de Acero, 0.05 unidades deElectronica, 2 anos/hombre de trabajo y 300 coronas de material importado. Ellımite superior de produccion de Plasticos es de 60000 unidades. La mano deobra total disponible es de 830000 personas al ano. No puede importarse Acero,Electronica, Plastico o Automocion.

¿Cual ha de ser la produccion y exportacion de cada sector?

9. New Forest es una zona de bosque de aproximadamente 145 millas cuadradassituada en Hampshire, Inglaterra. Por tanto, contaremos el dinero en libras y lamadera en pies de Hoppus (un pie de Hoppus, abreviadamente h.ft., es el volumende una tabla de un pie cuadrado de area y una pulgada de grosor). La gerencia deNew Forest ha de decidir el programa de corte de arboles para un area de 30000acres, con el objetivo de maximizar los ingresos netos a lo largo de la proximadecada. El problema considerado aquı se refiere unicamente a un area de 8500acres, con 6 tipos de arboles, tal como aparece en la tabla.

Tipo Descripcion Acres Volumen (h.ft/acre)

1 Arboles de madera noble (volumen alto) 2754 2000

2 Arboles de madera noble (volumen medio) 850 1200

3 Arboles de madera noble (volumen bajo) 855 7004 Bosque de conıferas 1598 40005 Bosque mixto 405 25006 Tierra sin arboles 1761

Las areas de arboles de madera noble se clasifican en tres categorıas: con so-tobosque completo, con sotobosque parcial y sin sotobosque. Las extensionescorrespondientes son:

Sotobosque Sotobosque Sincompleto parcial sotobosque

Madera noble (volumen alto) 357 500 1897Madera noble (volumen medio) 197 130 523Madera noble (volumen bajo) 39 170 646

Cualquier numero de acres de cualquier tipo de bosque puede recibir uno delos dos trataments basicos: cortar y plantar conıferas (tratamiento 1A) o cortar

y plantar arboles de madera noble (tratamiento 1B). Cuando se aplican a latierra sin arboles, los tratamientos son plantar conıferas o plantar arboles de

madera noble. Ademas, para las zonas de arboles de madera noble con sotobosquecompleto existe la opcion de cortar y mantener el sotobosque (tratamiento 2).Analogamente, para las zonas de arboles de madera noble con sotobosque parcialse tiene la opcion de cortar i enriquecer el sotobosque (tratamiento 3). Una opcionfinal en todos los casos y para todas las areas es posponer el tratamiento.

5

Los ingresos netos para los proximos diez anos dependen del tratamiento y deltipo de bosque. Las cifras, en libras por acre, aparecen en la tabla:

Tratamiento NoTipo de bosque 1A 1B 2 3 tratamiento

1 287 215 228 292 2042 207 135 148 212 1483 157 85 98 162 1124 487 415 3715 337 265 2646 87 15 61

Cuestiones de impacto ambiental y disponibilidad de mano de obra imponen lassiguientes limitaciones:

El area tratada no ha de exceder de 5000 acres.

El area de conıferas resultante, es decir, el area de conıferas plantadas masel area de conıferas antiguas no tratada, no ha de exceder de 3845 acres.

El volumen de madera noble cortada no ha de ser mayor de 2.44 millonesde h.ft.

El volumen de conıferas y bosque mixto cortado no ha de ser mayor de 4.16millones de h.ft.

Si quisieramos 500 acres de madera noble, ¿como cambiarıa la solucion?.

10. La companıa aerea Sayre-Priors tiene el siguiente conjunto de vuelos diarios:

Numero de vuelo Origen Destino Perıodo101 Chicago Los Angeles Tarde410 New York Chicago Tarde220 New York Miami Noche17 Miami Chicago Manana7 Los Angeles Chicago Tarde13 Chicago New York Noche11 Miami New York Manana19 Chicago Miami Noche23 Los Angeles Miami Noche3 Miami Los Angeles Tarde

La companıa quiere establecer una polıtica de asignacion de tripulaciones a vueloscon el mınimo coste. El problema basico es determinar si una tripulacion, despuesde hacer un vuelo, ha de hacer o no un nuevo vuelo y, en caso afirmativo, que vuelotendrıa que hacer. Un concepto basico en este planteamiento es el de circuito. Lascaracterısticas de un circuito son:

Un circuito consiste en un conjunto de 1, 2 o 3 vuelos conectados (el destinode un vuelo es el origen del vuelo siguiente)

Un circuito tiene un coste de $2000 si acaba en la ciudad de origen.

Un circuit que acaba en una ciudad diferente de la de origen tiene un costede $3000

Determinar el conjunto de circuitos que cubre todos los vuelos de la companıacon el mınimo coste.

6