Unidad 3 Formulacin de problemas de programacin lineal

La programacin lineal es una herramienta para representar, buscar la solucin y analizar problemas de optimizacin; esto es, maximizar o minimizar algn objetivo; en estos problemas hay que decidir cmo realizar diversas acciones o productos que compiten por recursos limitados o escasos. Para utilizar este modelo es necesario que tanto el objetivo como las restricciones que representan las distintas condiciones del problema se puedan formular con funciones lineales. La gran ventaja del modelo de la programacin lineal (pL) dentro de la investigacin de operaciones es que se trata de una estructura general que puede servir para representar de manera apropiada aplicaciones de campos muy diversos con un mtodo o varios mtodos de solucin sencillos, que, por sus caractersticas, es fcilmente programable. La pL ha sido utilizada con xito en problemas reales de planeacin de produccin, campaas publicitarias, carteras financieras, para establecer turnos de personal, realizar mezclas de productos, o bien para los problemas clsicos de transporte, de ruta ms corta, asignacin, flujo mximo e inventarios. A continuacin se presentar una serie de ejemplos de problemas tpicos que por supuesto no intenta ser exhaustiva, pero s pretende ayudar en este paso que suele ser muy difcil para los estudiantes: la formulacin del modelo matemtico a partir de un problema real, expresado en el lenguaje coloquial. Los problemas abarcan una gran cantidad de temticas: problemas de produccin, administracin y finanzas, de administracin pblica y para la toma de decisiones en las polticas pblicas; problemas ecolgicos, sanitarios y de medio ambiente. En algunos casos el objetivo es fcilmente cuantificable, como obtener la mxima utilidad; en otros, especialmente cuando el objetivo es la salud o el bienestar social, no es tan sencillo medirlo, y deber analizarse cuidadosamente cmo plantear tales objetivos. Pero sin importar el tipo de problema, para su formulacin, en particular en los de pL, el paso fundamental es la definicin de las variables; se trata de aquello que necesitamos decidir: qu y cunto hacer de las diversas acciones o productos que constituyen las incgnitas del problema. El siguiente paso es definir el objetivo del problema. En los modelos de pL siempre se querr optimizar, esto es, minimizar o maximizar la funcin objetivo (fO) que estar
73

program_5.indb 73

22/03/12 13:00

PROGRAMACIN LINEAL

dada por una combinacin lineal de las variables de decisin definidas previamente. Tal vez se pueda pensar que tener que decidir por un solo objetivo limita el tipo de problemas; esto no es as, puede haber otros objetivos expresados como una restriccin de un logro por cumplir. Finalmente habr que escribir las ecuaciones necesarias para representar las distintas restricciones del problema, generalmente debido a recursos limitados, ya sean stos materias primas, mano de obra o condiciones del mercado. Estas restricciones se complementan con las llamadas restricciones de no negatividad, que establecen que las variables de decisin siempre deben ser positivas.

Problemas de planeacin de la produccin

Los problemas de planeacin de la produccin son los problemas ms clsicos de pL. En stos hay que decidir cmo usar los recursos disponibles realizando una combinacin de productos o actividades que compiten por los mismos recursos con el objetivo de maximizar la utilidad. A los recursos limitados suelen agregarse restricciones del mercado y compromisos de la empresa. En estos problemas las variables de decisin son la cantidad de cada producto que se debe producir; el objetivo es maximizar las utilidades de la empresa y est sujeto a una serie de restricciones debido a las limitaciones impuestas por los recursos, como las materias primas, la mano de obra, la energa, el nmero de mquinas disponibles; deber escribirse una desigualdad por cada uno de los recursos necesarios para la fabricacin de los productos. Pueden tambin existir restricciones en la demanda de los distintos productos o actividades que han de realizarse. Ejemplo 3.1 Una empresa maquiladora del norte del pas dedicada a la produccin de televisores y pantallas para video y computadoras necesita planear la produccin del siguiente mes debido a la introduccin de un nuevo producto y a que va a dejar de producir otros por cambios en la demanda. La gerencia piensa que los prximos meses deberan dedicarse a fabricar slo cuatro productos: pantallas de cristal lquido de 20 y de 24 pulgadas y los televisores planos de 24 y 50 pulgadas. Debido a las diferentes tecnologas, los televisores son producidos en la planta de Chihuahua, mientras que las pantallas se producen en la planta de Tijuana. El control de calidad y el empaque final se realiza en esta ltima. En el cuadro 3.1 se presentan las disponibilidades de tiempo en cada una de las plantas; en el caso de Chihuahua hay dos departamentos, el de electrnica y el de ensamble final. En el mismo cuadro se indica la utilidad neta por cada tipo de equipo.
74

program_5.indb 74

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Cuadro 3.1
Horas/unidad Chihuahua Productos Pantalla de 20 Pantalla de 24 Televisor de 24 Televisor de 50 Capacidad (horas/mes) 2.25 2.0 3000 2.5 2.75 3200 5000 Elecrnica Ensamble Tijuana Pantallas LCD 3.5 3.8 Utilidad $ 850 925 800 1200

Finalmente todos los productos deben pasar por los departamentos de control de calidad y de empaque. La disponibilidad de tiempo y el nmero de equipos que se han de procesar por hora se indica en el cuadro 3.2. Cuadro 3.2
Unidades/hora Productos Pantalla de 20 Pantalla de 24 Televisor de 24 Televisor de 50 Capacidad (horas/mes) Control de calidad 3.0 2.5 1.5 2.0 3200 Empaque 6 5 5 3 800

El departamento de mercadotecnia ha decidido que se deben fabricar al menos 100 equipos de cada tipo para mantener su presencia en el mercado nacional. En primer lugar se deben definir las variables de decisin; en este problema hay cuatro incgnitas que son la cantidad de cada equipo que conviene producir mensualmente: x 1: x 2: x 3: x 4: la la la la cantidad cantidad cantidad cantidad de de de de pantallas de 20 pantallas de 24 televisores de 24 televisores de 50

El objetivo de la empresa es maximizar las utilidades, por lo tanto: Mx U = 850x1 + 925x2 + 800x3 + 1200x4
75

program_5.indb 75

22/03/12 13:00

PROGRAMACIN LINEAL

Hay una serie de restricciones para la produccin: el departamento de electrnica de la planta de Chihuahua dispone de 3000 horas mensuales que puede ocupar en producir la parte electrnica de ambos tipos de televisores, requiriendo 2.25 y 2 horas para cada televisor de 24 y 50, respectivamente, por lo tanto: 2.25x3 + 2x4 3000 horas En el departamento donde se ensamblan estos televisores se cuenta con 3250 horas: 2.5x3 + 2.75x4 3250 horas En la planta de Tijuana se cuenta con 5000 horas para la produccin de las pantallas de cristal lquido tanto de 20 como de 24, por lo tanto: 3.5x1 + 3.8x2 5000 horas Todos los equipos deben ser sometidos a pruebas de calidad, y este departamento cuenta con 3200 horas al mes. Aqu se nos indica la cantidad de equipos que pueden ser revisados en una hora; por ejemplo, nos dicen que en una hora se revisan 3 pantallas lcd de 20; esto quiere decir que se requieren 20 minutos o 1/3 de hora para cada pantalla; lo mismo habra que hacer para los dems equipos. Esta restriccin se puede escribir de dos manera: en horas o en minutos, por lo tanto: 1/3x1 + 1/2.5x2 + 1/1.5x3 + 1/2x4 3200 horas O en minutos: 20 x1 + 24 x2 + 40 x3 + 30 x4 192000 minutos Ambas ecuaciones son equivalentes. Por ltimo para el empaque se cuenta con 800 horas, por lo tanto: 1/6x1 + 1/5x2 + 1/5x3 + 1/3x4 800 horas Falta agregar las restricciones impuestas por el departamento de mercadotecnia: x1, x2, x3, x4 100 equipos El modelo del problema queda entonces as:

76

program_5.indb 76

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Mx U = 850x1 + 925x2 + 800x3 + 1200x4 s.a. 2.25x3 + 2x4 3000 horas 2.5x3 + 2.75x4 3250 horas 3.5x1 + 3.8x2 5000 horas 1/3x1 + 1/2.5x2 + 1/1.5x3 + 1/2x4 3200 horas 1/6x1 + 1/5x2 + 1/5x3 + 1/3x4 800 horas x1 100 x2 100 x3 100 x4 100 La solucin de este sistema ser la cantidad de equipos que se deben fabricar para que se maximice la utilidad mensual de la empresa.

Problemas de planeacin de campaas en medios de comunicacin

Se trata de problemas en los que con un presupuesto limitado se quiere incidir en la opinin del mayor nmero de personas utilizando diferentes medios de comunicacin. Como no es posible tratar de llegar al mayor nmero con el menor presupuesto, en estos problemas se plantea cubrir al menos cierta cantidad de poblacin con el menor costo posible. Para presentar este problema se utilizar una variante de un problema visto en la unidad 1. Ejemplo 3.2 Una cadena de supermercados se va a instalar en un municipio que ya cuenta con otras tiendas similares, por lo que ha decidido realizar una campaa publicitaria agresiva el mes anterior a la inauguracin. Tiene tres alternativas: anuncios en la televisin, anuncios en la radio local y folletos para entregar a domicilio. La experiencia obtenida en localidades similares le indica que con cada anuncio en la televisin su mensaje llega a 500 personas, cada anuncio en la radio llega a 320 y de cada 1000 folletos repartidos, 320 sern ledos por las personas. La poblacin es de 260000 habitantes, y la pretensin es llegar a por lo menos 25% minimizando los costos de la campaa y utilizando estos medios. El costo del millar de folletos, es de $400 siempre que el pedido sea por ms de 10 millares de folletos y el costo de los anuncios en televisin es de $2000 cada anuncio si contrata al menos 20 anuncios mensuales; los anuncios en la radio cuestan $1300 y ofrecen un paquete mnimo de un anuncio diario durante una semana. Se ha decidido utilizar los tres medios ya que llegan a pblicos diferentes y slo se cuenta con $75000.
77

program_5.indb 77

22/03/12 13:00

PROGRAMACIN LINEAL

En este problema hay que decidir cuntos anuncios de cada tipo contratar, con la restriccin de que se quiere usar los 3 medios. Por lo tanto, las variables de decisin son stas: TV: nmero de anuncios en la televisin (al menos 20) R: nmero de anuncios en la radio F: cantidad de folletos a repartir (F = 1 equivale a 1000 folletos) La fO es minimizar el costo de la campaa Mn costo = 2000 TV + 1300 R + 400 F Se quiere llegar por lo menos a 25% de la poblacin de 260000 habitantes: 500 TV + 320 R + 320 F 65000 El presupuesto mximo es de $ 75000: 2000 TV + 1300 R + 400 F 75000 adems: TV 20 R 7 F 10 El modelo entonces queda as: Mn costo = 2000 TV + 1300 R + 400 F s.a. 500 TV + 320 R + 320 F 65000 2000 TV + 1300 R + 400 F 75000 TV 20 R 7 F 10 La solucin de este sistema ser la mejor manera de realizar la campaa que cumpla con los requisitos planteados.

78

program_5.indb 78

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Problemas de planeacin de carteras nancieras

Se trata de cmo invertir una cantidad de dinero en varias opciones financieras con el objeto de obtener el mximo rendimiento esperado, pero ajustndose a restricciones que moderen el riesgo y permitan tener la liquidez requerida por el inversor. Ejemplo 3.3 El seor Montao Garca recibe en diciembre la cantidad de $220000 en concepto de aguinaldo, vacaciones y comisiones. Como no necesita utilizar ese dinero inmediatamente, consulta a un asesor financiero para analizar las distintas posibilidades para un plan de inversin anual. Esta persona sabe que a mitad de ao, en julio necesitar $45000 para saldar una deuda; adems quisiera disponer, para cualquier emergencia, de al menos 15% de este dinero. El asesor le sugiere repartir el dinero en varias alternativas: 1) en este momento parece atractivo comprar dlares ya que estn a $13.5 y se espera que para fin de ao lleguen a $15, pero debido a lo riesgoso sugiere que no se invierta ms que 1/3 del dinero; 2) debido a la competencia que hay entre los bancos, Banorte est ofreciendo 6.8% si se depositan ms de $80000 en pagars a 28 das, pero se deben dejar durante 6 meses; esta inversin permitira retirar el dinero que necesita a mitad de ao; 3) el fondo de inversin Banefo ofrece un rendimiento esperado de 7.8%, aunque depende de la tasa de los Cetes y por lo tanto tambin presenta riesgo, por lo que le sugiere no invertir ms de la mitad de lo que invierta en pagars; 4) para poder tener dinero disponible, debe dejar cierta cantidad en una cuenta corriente cuyo rendimiento es de 1.2 por ciento. Se trata de ayudar al seor Montao a decidir cmo debe invertir su dinero en estas cuatro opciones. Las variables de decisin sern stas: D: cantidad de dinero a invertir en dlares P: cantidad de dinero a invertir en pagars, de donde retirar $45000 a los 6 meses F: cantidad de dinero a invertir en el fondo Banefo C: cantidad de dinero que se dejar en la cuenta corriente El objetivo es maximizar el rendimiento. Si el dlar sube como se espera, la tasa de inters equivalente ser de (1.5)/(13.5) = 11.11%, superior a todas las dems. La fO entonces ser: Mx R = 0.111 D + 0.034 P + 0.034 (P-45000)+ 0.078 F + 0.012 C

79

program_5.indb 79

22/03/12 13:00

PROGRAMACIN LINEAL

Pero por cuestiones de riesgo no se debe invertir ms que la tercera parte en dlares: D (1/3) 220000 Para que Banorte d la tasa de inters de 6.8% es necesario invertir al menos $80000 pero como a mitad de ao se retirarn $45000, para que no baje la tasa debern ser: P 125000 En cuanto a los fondos, debido a que son de inters variable tambin le recomend mesura: F 1/2 P Y para emergencias quiere disponer de 15% de su dinero: C (0.15) 220000 La suma de sus inversiones no puede exceder su capital, por lo que: D + P + F + C 220000 El modelo de pL de esta situacin queda as: Mx R = 0.111 D + 0.034 P + 0.034 (P-45000)+ 0.078 F + 0.012 C s.a. D 73333 P 125000 F (0.5) P 0 C 33000 D + P + F + C 220000 D, P, F, C 0 La solucin de este sistema ser la cantidad de dinero que debe invertirse en cada una de las cuatro opciones para maximizar el rendimiento y conocer el rendimiento esperado.

80

program_5.indb 80

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Problema de dietas
El problema de las dietas se presenta cuando en una institucin como una escuela o un hospital debe disear una dieta que cumpla con ciertos requisitos mnimos de nutrientes, pero tratando de obtener el menor costo. El mismo tipo de problema sirve para realizar dietas para adelgazar, por ejemplo, donde lo que se pretende es minimizar las caloras, o para las granjas donde se debe alimentar animales utilizando aquellos productos que ofrezcan los nutrientes necesarios al menor precio. A continuacin se da un caso especfico. Ejemplo 3.4 Se necesita disear una dieta para estudiantes al menor costo posible pero satisfaciendo sus necesidades bsicas de 2400 kcal diarias y de no menos de 1000 g de comida; las necesidades bsicas tambin incluyen 2 l de agua, aunque el lquido no debe necesariamente provenir de los alimentos, y cantidades especficas de protenas, grasas y carbohidratos. En el cuadro se indican las caractersticas de cada tipo de alimento por porcin de 100 g y los requerimientos diarios mnimos promedio para cada estudiante. La dieta debe tambin incluir al menos 1 huevo, 200 g de vegetales y 100 g de leche o queso. Cuadro 3.3
Protenas (g) 8 11 2 30 3.6 6 20 2 100 Grasas (g) 1.4 11 0.2 4 3.6 1 15 0 50 Carbohidratos (g) 52 1 23 0 4.8 21 0 18 375 Precio ($/kg) 20 25 15 42 10 12 55 13

Alimento Pan Huevos (2) Arroz Pollo Leche Frijoles Queso Vegetales Req. mnimo

kcal 245 150 110 250 66 110 250 35 2400

Agua ml 38 66 72 55 90 67 50 80 2 litros

Variables de decisin. Es necesario saber cuntos gramos o porciones de cada alimento debe incluir la dieta. Debido a que la dieta se debe armar con los ocho alimentos disponibles, el problema tiene ocho variables. Es conveniente expresar la dieta en porciones de 100 g ya que toda la informacin est dada por porcin.
81

program_5.indb 81

22/03/12 13:00

PROGRAMACIN LINEAL

x1: nmero de porciones de pan x2: nmero de porciones de huevo x3: nmero de porciones de arroz x4: nmero de porciones de pollo x5: nmero de porciones de leche x6: nmero de porciones de frijoles x7: nmero de porciones de queso x8: nmero de porciones de vegetales El objetivo es minimizar el costo. Como el precio est dado por kilogramos, y las porciones son de 100 gramos, es necesario que los coeficientes de la fO sean calculados previamente: Mn C = 2x1 + 2.5x2 + 1.5x3 + 4.2x4 + 1x5 + 1.2x6 + 5.5x7 + 1.3x8 Las restricciones de esta dieta son cubrir cierta cantidad de caloras y una mnima de gramos de alimento, y cubrir las necesidades de protenas, grasas y carbohidratos que necesita un estudiante para sus actividades normales. Ntese que no es necesario agregar una restriccin respecto a la necesidad de agua de los individuos ya que este requerimiento no debe ser satisfecho con los alimentos solamente, sino que se complementa con las bebidas. Las ecuaciones de las restricciones son las siguientes: Caloras (kcal): 245x1 +150x2 + 110x3 + 250x4 + 66x5 + 110x6 + 250x7 + 35x8 2400 Cantidad de comida en peso (1000 g = 10 porciones): x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 10 Protenas (g): 8x1 + 11x2 + 2x3 + 30x4 + 3.6x5 + 6x6 + 20x7 + 2x8 100 Grasas (g): 1.4x1 + 11x2 + 0.2x3 + 4x4 + 3.6x5 + 1x6 + 15x7 50 Carbohidratos (g): 52x1 + 1x2 + 23x3 + 4.8x5 + 21x6 + 18x8 375 Huevo (porciones): x2 0.5 Vegetales (porciones): x8 2 Lcteos (porciones): x5 + x7 1

82

program_5.indb 82

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Como no puede haber cantidades negativas de alimentos, hay que agregar las restricciones de no negatividad; el modelo entonces queda as: Mn Costo = 2x1 + 2.5x2 + 1.5x3 + 4.2x4 + x5 + 1.2x6 + 5.5x7 + 1.3x8 s.a. 245x1 + 150x2 + 110x3 + 250x4 + 66x5 + 110x6 + 250x7 + 35x8 2400 x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 10 8x1 + 11x2 + 2x3 + 30x4 + 3.6x5 + 6x6 + 20x7 + 2x8 100 1.4x1 + 11x2 + 0.2x3 + 4x4 + 3.6x5 + 1x6 + 15x7 50 52x1 + 1x2 + 23x3 + 4.8x5 + 21x6 + 18x8 375 x2 0.5 x8 2 x5 + x7 1 x1, x2, x3, x4, x5, x6, x7, x8 0

Problema de mezclas
Los problemas de mezclas se dan cuando para la elaboracin de un producto, o varios, se utiliza una serie de componentes o ingredientes en determinada proporcin para dar las caractersticas especficas a cada producto o mezcla. Por ejemplo, se utilizan distintas variedades de granos de caf para lograr el grado de acidez, aroma y textura deseados; se mezclan semillas como cacahuate, pepitas, nueces, pin, etctera para venderlas en empaques individuales; lo mismo ocurre cuando se produce acero en un horno de fundicin a partir de hierro y otros metales que le darn las caractersticas buscadas segn el tipo de uso para el que va a ser destinado dicho acero. Otro uso frecuente es el diseo de dietas para animales a partir de ingredientes que puedan satisfacer los requerimientos nutricionales; este caso puede verse como el problema de dietas ya tratado. Se pueden encontrar ejemplos en la industria qumica, la petroqumica o en la de cosmticos. En todos estos problemas, el tomador de decisiones quiere minimizar el costo de producir la mezcla que satisfaga los requerimientos impuestos, para lo cual debe indicar la proporcin de los distintos ingredientes que incluir en la mezcla. Ejemplo 3.5 En el estado de Veracruz se ha instalado una cooperativa de pequeos productores de caf para evitar venderlo a precios por debajo de los costos a los grandes acaparadores internacionales. En ella se realizar la compra del caf en cereza a los productores, el lavado, separacin, secado y tostado para posteriormente molerlo, empacarlo y venderlo.
83

program_5.indb 83

22/03/12 13:00

PROGRAMACIN LINEAL

Se ha pensado en vender dos estilos de caf: gourmet y americano ya que son los ms consumidos en el mercado nacional. Aunque los gustos del consumidor nacional estn cambiando, actualmente la demanda de caf estilo americano es mayor que la demanda del estilo gourmet. En el cuadro 3.4 se indican los precios que pagar la cooperativa por la tonelada de caf en cereza: Cuadro 3.4
Variedades Robusta Arbica borbn Arbica caturra No especificado Precio $/t 3750 4450 4100 2800

Debido a las diferentes caractersticas de cada especie de caf, se necesita mezclarlas en diferentes proporciones para obtener las mezclas apropiadas para los estilos gourmet y americano. La variedad arbica tiene un sabor delicado, aroma intenso y mayor cantidad de cafena; la planta requiere de cuidados y de la sombra de grandes rboles, mientras que la variedad robusta, como su nombre lo indica, es ms resistente, es una planta de mayor tamao y rendimiento, de sabor ms fuerte. Entre los productores hay un grupo de la sierra de Zongolica que es de origen nhuatl y que estn comenzando con la explotacin de caf, pero este ao tendrn una produccin de no muy buena calidad. Aun as la cooperativa se ha comprometido a que al menos 10% del volumen que se procese provenga de esta regin. En el cuadro 3.5 se especifican los requerimientos que debe cumplir cada uno de los estilos de caf. Cuadro 3.5
Americano Robusta Arbica borbn Arbica caturra Revuelto menos de 30% ms de 15% menos de 55% ms de 25% menos de 80% menos de 25% ms de 25% menos de 65% menos de 12% Gourmet menos de 8% ms de 25%

84

program_5.indb 84

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Es necesario establecer la cantidad o el porcentaje de cada tipo de grano con que se realizar la mezcla para cada uno de los estilos de caf. El porcentaje de cada ingrediente de la mezcla para obtener el costo mnimo es independiente de la cantidad, ya sea que se trate de producir un kilogramo o una tonelada o cualquier otra cantidad. As, para definir las variables se puede establecer lo siguiente: xij: cantidad del ingrediente i a utilizar en 1 kg de la mezcla j, expresada en kg con i = 1,...4 y j = 1, 2, donde: i = 1 robusta, j = 1 americano, i = 2 borbn, j = 2 gourmet i = 3 caturra, i = 4 revuelto, En este caso empezaremos por plantear las restricciones. Consideremos la restriccin que dice que el caf estilo americano no debe contener ms que 30% de grano del tipo robusta. La cantidad de robusta en 1 kg de caf americano es x11 y sabemos que debe ser menor o igual a 30% del total de la mezcla. x11 0.30 total de la mezcla Tambin sabemos que el total de la mezcla de caf americano debe estar formado por la suma de cada uno de los cuatro ingredientes: x11 0.3 (x11 + x21 + x31 + x41) Esta ecuacin se puede rescribir como 0.7 x11 0.3 x21 0.3 x31 0.3 x41 0 De la misma manera se pueden escribir el resto de las restricciones. Para el caf estilo americano x21 0.15 (x11 + x21 + x31 + x41) (mnimo de borbn) x21 0.55 (x11 + x21 + x31 + x41) (mximo de borbn) x31 0.25 (x11 + x21 + x31 + x41) (mnimo de caturra) x31 0.80 (x11 + x21 + x31 + x41) (mximo de caturra) x41 0.25 (x11 + x21 + x31 + x41) (mximo revuelto)

85

program_5.indb 85

22/03/12 13:00

PROGRAMACIN LINEAL

Para el caf estilo gourmet: x12 0.08 (x12 + x22 + x32 + x42) (mximo de robusta) x22 0.25 (x12 + x22 + x32 + x42) (mnimo de borbn) x32 0.25 (x12 + x22 + x32 + x42) (mnimo de caturra) x32 0.65 (x12 + x22 + x32 + x42) (mximo de caturra) x42 0.12 (x12 + x22 + x32 + x42) (mximo revuelto) Por ltimo se quiere que al menos 10% sea del caf de la sierra de Zongolica: x41 + x42 0.1 (x11 + x21 + x31 + x41 + x12 + x22 + x32 + x42) Adems es necesario que la suma de los ingredientes sea 1 kg: x11 + x21 + x31 + x41 = 1 kg x12 + x22 + x32 + x42 = 1 kg Como las variables fueron definidas como la parte de cada ingrediente que debe llevar 1 kg de mezcla, las ltimas ecuaciones son igualdades estrictas. Por ltimo, el objetivo es obtener las mezclas ms econmicas, por lo que la fO queda as: Mn costo = 3.75x11 + 4.45x21 + 4.10x31 + 2.80x41 + 3.75x12 +4.45x22 + 4.10x32 + 2.80x42 El modelo de pL obtenido para este problema de mezclas es el siguiente: Mn costo = 3.75x11 + 4.45x21 + 4.1x31 + 2.8x41 + 3.75x12 + 4.45x22 + 4.1x32 + 2.8x42 s.a. 0.70x11 0.30x21 0.30x31 0.30x41 0 -0.15x11 + 0.85x21 0.15x31 0.15x41 0 -0.55x11 + 0.45x21 0.55x31 0.55x41 0 -0.25x11 0.25x21 + 0.75x31 0.25x41 0 -0.80x11 0.80x21 + 0.20x31 0.80x41 0 -0.25x11 0.25x21 0.25x31 + 0.75x41 0 0.92x12 0.08x22 0.08x32 0.08x42 0 -0.25x12 + 0.75x22 0.25x32 0.25x42 0 -0.25x12 0.25x22 + 0.75x32 0.25x42 0 -0.65x12 0.65x22 + 0.35x32 0.65x42 0 -0.12x12 0.12x22 0.12x32 + 0.88x42 0

86

program_5.indb 86

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

x11 + x21 + x31 + x41 = 1 x12 + x22 + x32 + x42 = 1 -0.1x11 -0.1x21 -0.1x31 + 0.9x41 -0.1x12 -0.1x22 -0.1x32 + 0.9x42 0 x11, x21, x31, x41, x12, x22, x32, x42 0 Los problemas de mezclas suelen tener variantes; por ejemplo, puede ser que se tenga una oferta determinada de cada uno de los ingredientes, incluso puede estar especificada cierta demanda para cada uno de los productos resultantes. En esos casos, convendr definir las variables como la cantidad del ingrediente (i) que se utilizar para la mezcla (j). Adems habr que escribir las ecuaciones de oferta y demanda para cada una de las restricciones que especifique el problema. Por ejemplo, si se nos explicitara que la demanda es de cinco toneladas de mezcla para caf americano y dos toneladas para caf gourmet, con slo variar las restricciones que indican el total se obtendra la mezcla ms adecuada para la nueva condicin: x11 + x21 + x31 + x41 = 5 x12 + x22 + x32 + x42 = 2 Si hubiera restricciones en la disponibilidad de alguno de los ingredientes, por ejemplo, se dispone slo de diez toneladas de granos de caf Borbn, habra que definir las variables en toneladas y agregar x21 + x22 10 El resultado indicara cuanto de cada grano mezclar pero expresado en toneladas.

Problemas de asignacin de turnos de personal

Estos problemas se presentan en los casos en que hay que cubrir diferentes requerimientos de personal a lo largo del da o de la semana, como seran los cajeros de un supermercado o de un banco, los meseros, los turnos de vigilancia en edificios, etctera. Una condicin implcita en estos problemas es que todos los empleados ganan lo mismo, y lo que se intenta es minimizar el nmero de personas necesarias para satisfacer las necesidades. El siguiente ejemplo presenta este tipo de problema.

87

program_5.indb 87

22/03/12 13:00

PROGRAMACIN LINEAL

Ejemplo 3.6 Se quieren reorganizar los turnos de las enfermeras de un hospital general que da atencin a una ciudad de medio milln de habitantes. Las enfermeras trabajan turnos de 8 horas continuas, con excepcin del turno nocturno de 12 horas (de 8 pm a 8 am). Hay 4 turnos diurnos que comienzan a las 6 am, 10 am, 2 pm y 6 pm. El nmero de enfermeras necesarias vara segn las distintas tareas que deben realizarse como baar a los pacientes, darles de comer, asistir a los mdicos en las consultas, realizar curaciones, etctera. La administracin del hospital indica que el nmero de enfermeras mnimo necesario es el siguiente: Cuadro 3.6
Intervalo 6a8 8 a 10 10 a 14 14 a 16 16 a 20 20 a 22 22 a 6 Nmero mnimo de enfermeras 30 22 26 17 20 15 12

Para resolver este problema es importante entender cul es la decisin que han de tomar las autoridades del hospital. Como existen cuatro turnos diurnos y uno nocturno, es necesario decidir cuntas personas trabajarn en cada uno de los turnos, por lo que se tienen cinco variables de decisin: x 1: x 2: x 3: x 4: x 5: cantidad cantidad cantidad cantidad cantidad de de de de de enfermeras enfermeras enfermeras enfermeras enfermeras en en en en en el turno de 6 a 14 el turno de 10 a 18 el turno de 14 a 22 el turno de 18 a 2 el turno de 20 a 8

y por supuesto el objetivo es tener la menor cantidad de enfermeras pero que cubran los requerimientos de personal para cada uno de los intervalos en que se conoce la demanda. Mn x1 + x2 + x3 + x4 + x5 Para plantear las restricciones hay que garantizar que se cumpla con el nmero mnimo necesario de enfermeras en cada intervalo. Por ejemplo, se sabe que entre las 6 y
88

program_5.indb 88

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

las 8 am se requieren de al menos 30 enfermeras; durante esas horas estarn las enfermeras del turno de la noche ya que su hora de salida es a las 8 am; adems estarn las que entran a las 6 am de la maana. Esto se puede representar as: x1 + x5 30 En el intervalo de las 8 am a las 10 am se requieren 22 enfermeras. Dado que las nicas que trabajan en ese horario son las del primer turno de la maana, las que entran a las 6 am, pues las del turno nocturno acaban de salir, entonces: x1 22 Habr que seguir analizando cada uno de los intervalos, observando cules turnos cubren dicho intervalo, y escribir las ecuaciones correspondientes. Para visualizar mejor este tipo de problemas se puede utilizar una representacin de tipo matricial, en las que, por un lado, se ponen los turnos y, por el otro, los intervalos en los cuales deben cumplirse ciertas restricciones. El cuadro 3.7 es la representacin de la matriz de este problema. El primer rengln que corresponde al intervalo de 6 a 8 am muestra cuales son los turnos que cubren ese intervalo. Como el primer turno tiene x1 enfermeras y el turno nocturno x5, la suma de ambas deber ser al menos igual a las 30 enfermeras que se requieren. Para el turno de 8 a 10 am solamente trabajan las del primer turno, mientras que entre las 10 am y las 2 pm se dispondr del personal que entr a las 6 am, as como del que lo hizo a las 10 am. Cuadro 3.7
Nmero mnimo de enfermeras 30 22 26 17 16-18 18-20 20 a 22 22 a 06 22-02 02-06
89

Intervalos Subintervalos 06 a 08 08 a 10 10 a 14 14 a 16 16 a 20

X1 6 a 14

X2 10 a 18

X3 14 a 22

X4 18 a 2

X5 20 a 8

20 20 15 12 12

program_5.indb 89

22/03/12 13:00

PROGRAMACIN LINEAL

El cuadro 3.7 permite ver quines estn trabajando simultneamente en cada intervalo, lo que facilita la construccin de las ecuaciones. Es importante notar que los intervalos en que se tienen determinados requisitos no tienen por qu coincidir con los turnos de los trabajadores; esto se puede observar con la restriccin en que se especifica que entre las 16 y las 20 horas se necesitan 20 enfermeras. Al observar los horarios de inicio y fin de cada turno, se identifica un turno que comienza dentro de dicho intervalo, por lo que durante esas cuatro horas del intervalo no se contar con las mismas enfermeras, razn por la cual fue necesario dividir el intervalo en dos subintervalos, pero asegurndonos de que en ambos existiera el mnimo de personal requerido para efectuar las labores. Se sugiere al alumno analizar qu ocurre durante el intervalo de 10 pm a 6 am. El problema queda modelado por el siguiente conjunto de ecuaciones: Mn x1 + x2 + x3 + x4 + x5 s. a. x1 + x5 30 x1 22 x1 + x2 26 x2 + x3 17 x2 + x3 20 x3 + x4 20 x3 + x4 + x5 15 x4 + x5 12 x5 12 x1, x2, x3, x4, x5 0 El modelo encontrado tiene 9 restricciones estructurales y las condiciones de no negatividad. Sin embargo, si se revisan podemos notar que la cuarta y quinta restricciones tienen la misma expresin del lado izquierdo; asimismo, mientras que en la cuarta se pide que haya por lo menos 17 enfermeras, en la quinta se exige que al menos sean 20, por lo que la primera de estas ecuaciones resulta una condicin redundante y por lo tanto puede quitarse del modelo sin afectar la solucin. Como ejercicio, vamos a buscar una solucin posible que cumpla con los requerimientos mnimos, aunque no necesariamente sea la ptima. Empezaremos por aquellos turnos para los que hay lmites mnimos establecidos. En el turno de la noche debe haber al menos 12 personas, por lo tanto proponemos x5 = 12; adems como de 8 a 10 am solamente est el personal que inicia su turno a las 6 am, se requiere que al menos x1 = 22. Con eso queda satisfecha la necesidad de contar con 30 personas de 6 a 8 am, ya que habr 34. Desde las 10 am a las 2 pm se necesitan 26 enfermeras y ya se cuenta con 22, por lo que x2 = 4, pero como luego se necesita que x2 + x3 20, entonces x3 = 16.
90

program_5.indb 90

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

En el intervalo siguiente, de las 6 pm a las 8 pm se necesitan 20, por lo que x4 = 4. La solucin propuesta requiere de 22 + 4 + 16 + 4 + 12 = 58 enfermeras para cubrir las necesidades diarias del hospital. Esta es una solucin posible aunque no necesariamente ptima. En la siguiente unidad se aprender cmo resolver estos problemas para encontrar la solucin ptima.

Problemas de transporte
En los problemas de transporte hay un nico producto, homogneo, que se debe distribuir desde varios orgenes a varios destinos. Se acepta la hiptesis de que el producto cuesta lo mismo cualquiera sea su origen, lo que vara es el costo del transporte. El costo del transporte puede estar dado en cualquier tipo de unidades como $/t, $/camin, $/caja, etctera, lo que interesa es minimizar el costo de surtir la demanda solicitada por los distintos destinos. Ejemplo 3.7 La Zona Metropolitana del Valle de Mxico (zmvm) tiene problemas de abasto de agua en varias de sus colonias, especialmente al este de la ciudad. En este momento las autoridades del Sistema de Aguas de la Ciudad de Mxico, junto con la Comisin de Agua del Estado de Mxico deben decidir cmo abastecer tres zonas que estn padeciendo un desabasto sistemtico: Nezahualcyotl, Iztapalapa y Los Reyes, con necesidades de 3.4, 5 y 2.2 m3/s. Las fuentes de abastecimiento que se estn considerando son 3 sistemas de pozos profundos (uno de ellos del Estado de Mxico), que an tienen excedentes, y agua proveniente del sistema Cutzamala. El primer sistema puede abastecer 2 m3/s, el segundo, 2.5 m3/s, y el tercer sistema de pozos, 2.5 m3/s; de la presa de Valle de Bravo, que forma parte del sistema Cutzamala, despus de realizar obras de mantenimiento, se podr extraer de 1 a 10 m3/s, segn sea necesario. Los costos de abastecimiento, operacin y conduccin por m3/s son stos: Cuadro 3.8
P1 Iztapalapa Los Reyes Nezahualcyotl 6.0 3.5 3.0 P2 4.5 3.0 3.5 P3 3.0 4.5 4.5 Cutzamala 12.5 12.0 11.5

91

program_5.indb 91

22/03/12 13:00

PROGRAMACIN LINEAL

Se debe encontrar la manera ms econmica de satisfacer la demanda de agua a los lugares que la necesitan. Es necesario decidir cunta agua se enviar desde cada uno de los orgenes a cada uno de los destinos. Este problema, adems de pertenecer a los de pL, se puede analizar como un problema de redes. Aqu utilizaremos la grfica de redes correspondiente. En el siguiente diagrama se representa cada punto origen con un crculo y cada destino tambin con un crculo, llamados nodos. Estos nodos estn unidos por unas lneas o flechas llamadas ramas, que indican los posibles flujos del agua. Cada nodo representa un punto de origen u oferta o un punto de destino o demanda, por lo tanto cada nodo tiene asignada una cantidad que es la oferta o demanda correspondiente. Las ramas representan un flujo o una accin, y a cada una de ellas se asocia una variable que corresponde a la cantidad del flujo que se enviar del origen (i) al destino (j). Cada rama tiene asociada tambin un parmetro que indica el costo de enviar una unidad del origen (i) al destino (j). Diagrama 3.1
2m3/s P1 x11 x12 x21 2.5m3/s P2 x31 2.5m3/s P3 N c43= 11.5 3.4m3/s LR 2.2m3/s c11= 6

Iz

5m3/s

x41

10m3/s

En este problema hay 12 variables de decisin que llamaremos xij donde xij es la cantidad de agua medida en m3/seg, que va desde el origen i al destino j. 1: Iztapalapa con i = 1: P1 j = 2: P2 2: Los Reyes 3: P3 3: Nezahualcyotl 4: Cutzamala
92

program_5.indb 92

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

El objetivo es satisfacer la demanda de agua en las tres delegaciones al menor costo posible. Por lo tanto la fO se formular como: Mn = 6x11 + 3.5x12 + 3x13 + 4.5x21 +3x22 + 3.5x23 + 3x31 + 4.5x32 + 4.5x33 + 12.5x41 + 12x42 +11.5x43 Restricciones de la oferta. Cada uno de los pozos puede enviar cierto flujo de agua a cada una de las tres delegaciones demandantes, pero la suma de los flujos enviados no puede exceder la disponibilidad de ellos. Las restricciones son: x11 + x12 + x13 2 x21 + x22 + x23 2.5 x31 + x32 + x33 2.5 x41 + x42 + x43 10 m3/s m3/s m3/s m3/s

Restricciones de la demanda. Visto desde la demanda, cada destino puede recibir el lquido de cualquiera de las cuatro fuentes. Aqu es necesario analizar la situacin para establecer el signo de las restricciones: puede ser que el demandante quiera exactamente la cantidad demandada o al menos dicha cantidad. Pero como se trata de un caso de minimizar costos, seguramente la solucin ptima har que se cumpla la igualdad y por lo tanto no enviar excedentes. Las restricciones son: x11 + x21 + x31 + x41 5 x12 + x22 + x32 + x42 2.2 x31 + x32 + x33 + x34 3.4 Como ningn flujo puede ser negativo en ese caso significara que el agua ira en sentido inverso, se plantean la condicin de no negatividad: x11, x21, x31, x41, x12, x22, x32, x42, x13, x23, x33, x34 0 El sistema de ecuaciones resultante tiene caractersticas que lo hacen muy fcil de resolver dado que todos los coeficientes son cero o uno y con una distribucin muy particular. Esta simplificacin en el modelo permite utilizar una simplificacin del mtodo general de resolucin de problemas de pL, llamado mtodo de transporte. Este mtodo se explica en la unidad 6, aunque estos problemas tambin se pueden resolver con el mtodo general, el mtodo Simplex y se puede resolver con los paquetes tradicionales para pL.

93

program_5.indb 93

22/03/12 13:00

PROGRAMACIN LINEAL

A continuacin se presentan dos problemas que comparten varias caractersticas de los problemas de transporte; se trata de los problemas de transporte con transbordo y de los problemas llamados de asignacin de recursos.

Problemas de transporte con transbordo

Los problemas de transporte con transbordo son muy similares a los de transporte: existen puntos de oferta con determinadas cantidades disponibles de cierto producto, y otros puntos destino que demandan dicho producto, pero adems pueden existir puntos intermedios donde llega mercanca de varios orgenes y que desde all se distribuye a los puntos de demanda. A continuacin se muestra el diagrama de redes de un problema de este tipo. Igual que en el problema de transporte, cada rama deber ser representada por una variable, y habr que escribir una restriccin por cada nodo de la grfica. En un nodo de transbordo la suma de lo que llega debe ser igual a lo que sale. En un nodo que funcione como punto intermedio y como destino, la suma de lo que llega deber ser igual a lo que se queda ms lo que sale. Diagrama 3.2
O1 1 x1T T O2 2 x2T x22 2 O3 3 x32 D2 xT1 xT2

1 xD21

D1

En el diagrama 3.2 se pueden contar siete ramas, por lo que el problema tiene siete variables de decisin, y existen seis nodos, para los cuales hay que plantear las ecuaciones de equilibrio: x1T oferta1 x2T + x22 oferta2 x32 oferta2
94

program_5.indb 94

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

xT1 + xD21 D1 x22 + x32 + xT2 D2 + xD21 x1T + x2T = xT1 + xT2 El objetivo es minimizar el costo del transporte, entonces la fO ser: Mn C = cij xij donde cij son los costos unitarios de cada trayecto.

Problemas de asignacin
Los problemas de asignacin son aquellos en que es necesario asignar personas a tareas especficas; mquinas a distintos operarios o vendedores a diferentes rutas, maestros a grupos de alumnos, etctera. El costo o el rendimiento de asignar a determinado individuo cada una de las tareas vara de acuerdo a sus capacidades particulares. El objetivo generalmente es minimizar el costo de la asignacin o el tiempo en que se produzca el trabajo. En algunos casos puede ser ms conveniente plantear maximizar la utilidad obtenida por esas tareas. Ejemplo 3.8 Una empresa de publicidad en expansin acaba de seleccionar a cinco nuevos empleados con capacidades profesionales: dos son licenciados en comunicacin y los otros tres son diseadores grficos con entrenamiento y experiencias diversas que pueden ser tiles a la empresa. Debido a que las vacantes son de diferente responsabilidad y considerando las habilidades personales, el departamento de recursos humanos realiz la siguiente matriz en la que se indica el salario que debera pagarse a cada uno de los individuos para las distintas funciones que podra desempear. Cuadro 3.9
Puesto 1 C1 C2 DG1 DG2 DG3 7000 6500 5800 6000 5500 Puesto 2 7250 7500 6500 7000 Puesto 3 7250 7000 7000 5700 Puesto 4 6000 7000 6500 7000 Puesto 5 10000 8500 9500

95

program_5.indb 95

22/03/12 13:00

PROGRAMACIN LINEAL

La empresa quiere colocar a cada uno de los nuevos empleados en los distintos puestos de manera que la nmina a pagar sea la menor posible, dado que el proyecto en que est trabajando la empresa lo empezar a cobrar seis meses despus, por lo que tendr que obtener un prstamo bancario para mantenerse hasta ese momento. Diagrama 3.3
C1 x15 x11 x12 C2 x29 DG1 DG2 DG3

7 000 P1

7 250 P2 P3

6 000 P4

10 000 P5

En este caso se puede hacer un diagrama de red como en los problemas de transporte, en el que existir una rama entre cada uno de los empleados y los puestos que puede ocupar. A cada rama le corresponder un costo que indica la matriz de salarios. Y como en los problemas de transporte, a cada rama se le asigna una variable. Aqu es donde aparece la diferencia fundamental entre los problemas de transporte y los de asignacin: cada una de las variables xij slo puede tomar dos valores, 1 y 0: xij = 1 si el empleado i se asigna al puesto j = 0 si el empleado i no se asigna al puesto j La fO es: Mn C = c1j x1j + c2j x2j + c3j x3j + c4j x4j + c5j x5j Las restricciones corresponden a cada nodo; por ejemplo, el primer empleado puede ser colocado en cualquiera de los puestos, excepto el puesto 4, pero si ocupa un
96

program_5.indb 96

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

puesto, ya no puede estar en ninguno de los otros; por lo que la restriccin correspondiente ser: x11 + x12 + x13 + x15 = 1 E igual para los otros empleados: x21 + x22 + x23 + x24 = x31 + x33 + x34 + x35 = x41 + x42 + x43 + x44 = x51 + x52 + x54 + x55 = 1 1 1 1

Lo mismo pasa con los puestos ya que slo una persona podr ocupar cada puesto: x11 + x21 + x31 + x41 + x51 = 1 x12 + x22 + x42 + x52 = 1 x13 + x23 + x33 + x43 = 1 x24 + x34 + x44 + x54 = 1 x15 + x35 + x55 = 1 Adems: xij {0, 1} La resolucin de estos problemas requiere que se agregue esta condicin y existen programas de cmputo para resolverlos.

Problemas de inventarios
Todos los problemas presentados hasta ahora no tomaban en cuenta el tiempo, esto es, se planea la mejor manera de realizar una serie de actividades y stas se ejecutan una sola vez, o se repiten de la misma manera en los periodos siguientes. A este tipo de modelos podemos llamarlos estticos. Los problemas de inventarios, por el contrario, corresponden a modelos dinmicos en los que el valor que toma una variable en un periodo depende del valor que tena en el periodo anterior: xt+1 = f (xt). En estos problemas es necesario analizar lo que ocurre a lo largo de un ciclo, sea ste un ao, un mes, una semana; no interesa optimizar cada periodo por separado, sino el rendimiento en el ciclo completo. El problema que analizaremos es un tpico problema administrativo en el que, por ejemplo, se conoce la demanda mensual de cierto producto durante todo el ao. En
97

program_5.indb 97

22/03/12 13:00

PROGRAMACIN LINEAL

general casi todos los productos tienen demandas cclicas; por ejemplo, los uniformes escolares se venden al comienzo del ao escolar; los electrodomsticos, a fin de ao porque la gente utiliza el aguinaldo para comprar bienes duraderos o tambin para celebrar el da de la madre (aunque sera mejor regalar flores que una plancha); hay comidas tpicas de determinadas fiestas; ropa para fro o para calor, etctera. Por otro lado, para las empresas no es fcil cambiar sus productos o volmenes de produccin de un momento a otro; si producen a ritmo constante para satisfacer los meses de menor demanda, se perdern la posibilidad de vender cuando la demanda crezca y si producen por encima de la demanda de ciertos meses tendrn que pagar el costo financiero de la inversin que no puedan vender inmediatamente y pagar los costos de almacenamiento, seguros y los costos administrativos del manejo de estos inventarios. Ejemplo 3.9 En octubre una empresa automotriz debe planear su produccin del siguiente ao para satisfacer la demanda de su modelo ms econmico en funcin de los pedidos anticipados. En el cuadro 3.10 se muestra la demanda en miles de carros para cada bimestre. Se ha estimado que el costo de tener que mantener un carro de un bimestre al otro ms los costos del seguro y del personal de vigilancia es de $420 bimestrales. Los costos de produccin de los vehculos tambin varan a lo largo del ao pues en el mes de marzo se espera un aumento en los salarios de 5% y los costos de los insumos tambin se incrementan. Tambin se han estimado estos costos y se muestran en el cuadro 3.10. El precio de venta es el mismo durante todo el ao. Al comenzar el siguiente ao se dispondr de 2000 vehculos, este es el inventario inicial y se quiere que para el ao siguiente queden al menos 2200 vehculos. Por polticas de la empresa, ningn pedido debe quedar sin satisfacerse totalmente. Cuadro 3.10
Bimestre Demanda Costo total 1 6 38000 2 3.5 39600 3 3 39750 4 3 40100 5 4 40400 6 6.5 41000

Planear la produccin implica determinar el nmero de carros que se han de producir cada bimestre, o sea, habr seis variables de decisin: xi: miles de carros a producir en el bimestre i: i ={1,2...6}

98

program_5.indb 98

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Pero tambin hay otras variables que conviene definir: di: demanda durante el intervalo i en miles de carros (dato en este problema) Ii: inventario o sobrante del intervalo i en miles de carros El nmero de carros que se han de producir en el primer bimestre deber ser: x1 = d1 + I1 I0 esto es la demanda del bimestre ms los que se queden para el siguiente menos los carros que se tenan del periodo anterior. En este caso conocemos la demanda y el inventario inicial: d1 = 6 I0 = 2 Pero la cantidad de carros que nos conviene producir y almacenar para el siguiente perodo tambin es una incgnita. La ecuacin entonces queda as: x1 = 6 + I1 2 = 4 + I1 O el inventario del periodo ser: I1 = x1 + I0 d1 = x1 4 El inventario al final del periodo es igual a lo que se produce en el periodo ms lo que haba en existencia menos lo que se vende. Para el segundo bimestre el inventario ser igual a lo que se produzca en ese bimestre ms lo que haba quedado menos lo que se venda: I2 = x2 + I1 d2 = x2 + I1 3.5 Y de igual manera para los siguientes bimestres: I3 = x3 + I2 d3 = x3 + I2 3 I4 = x4 + I3 d4 = x4 + I3 3 I5 = x5 + I4 d5 = x5 + I4 4 I6 = x6 + I5 d6

99

program_5.indb 99

22/03/12 13:00

PROGRAMACIN LINEAL

Pero como se quiere que el sexto bimestre queden 2200 carros para el ao siguiente, entonces: I6 = 2.2 = x6 + I5 6.5 Entonces el problema tiene 11 variables de decisin, ya que en este caso I6 fue dato: xi: miles de carros a producir en el bimestre i: i ={1,2..6} Ii: miles de carros que quedan del periodo i al i + 1 con i ={1, 2, 3, 4, 5} El objetivo de la empresa es minimizar los costos de produccin y de inventarios a lo largo del ao: Mn C = cj xj + kj Ij Donde cj es el costo de produccin unitario y kj es el costo de almacenaje de los carros. Como las variables de decisin indican los miles de carros a producir, la fO queda as: Mn C =[38000 x1 + 39600 x2 +39750 x3 + 40100 x4 + 40400 x5+ 41000 x6 + 420 ( I1 + I2 + I3 + I4 + I5 + I6 )] 1000 s.a. x1 I1 = 4 x2 + I1 I2 = 3.5 x3 + I2 I3 = 3 x4 + I3 I4 = 3 x5 + I4 I5 = 4 x6 + I5 = 8.7 Adems: xi, Ii 0 Nota: este ejemplo no cubre todos los aspectos que se ven en el estudio de los problemas de inventarios, pero sirve como introduccin a modelos dinmicos y muestra cmo la pL puede utilizarse cuando se trata de optimizar en problemas en los que el tiempo es un componente fundamental.1 Este esquema de planteamiento es utilizado para la planeacin de la comercializacin de cualquier producto. Para mostrar este tipo de aplicacin se presenta el siguiente caso.
1Otros problemas que no se presentan en el presente texto, pero que tienen caractersticas similares, son los problemas financieros en los que se quiere invertir, pero que debe considerarse el flujo de dinero en el tiempo.

100

program_5.indb 100

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Ejemplo 3.10 La comercializadora de granos MaizMex se dedica a la compra y venta de maz al contado; posee una bodega con capacidad para 520 toneladas. El 1 de enero tiene un inventario de 100 t y $2000000 en caja. La empresa debe planear sus compras y ventas para el trimestre ya que se tienen los precios a futuro. En el cuadro 3.11 se muestran los precios por tonelada de enero a marzo. Por las condiciones de transporte y entrega lo que se compra en un mes no puede ser vendido hasta el siguiente mes. Al final del trimestre se quiere contar con un inventario de 200 toneladas.2 Cuadro 3.11
Mes Enero Febrero Marzo Precio compra $2850 $3050 $2900 Precio venta $3100 $3250 $2950

Para realizar el programa de compras y ventas se deben definir las variables del problema; en este caso se propone xe, xf y xm : toneladas a comprar los meses de enero, febrero y marzo ye, yf y ym: toneladas a vender los meses de enero, febrero y marzo I1 e I2: inventarios en toneladas al finalizar enero y febrero C1 y C2: capital disponible a fines de enero y febrero El objetivo es maximizar la utilidad: fO: Mx U = 3100ye + 3250yf + 2950ym 2850xe 3050xf 2900xm Las restricciones son para cada mes; las de enero son stas: 1) Espacio: Io + xe ye 520 t xe ye 420 2) Capacidad de compra: 2850xe Co = $2000000 2850xe 2000000 3) Venta mxima: ye Io ye 100 Para simplificar el problema se agrega la definicin de dos variables:

2Este

problema fue adaptado de Moskowitz, H. Y Wrigth, G., Investigacin de operaciones, PHH. 101

program_5.indb 101

22/03/12 13:00

PROGRAMACIN LINEAL

4) Inventario a fin de mes: I1 = Io + xe ye I1 xe + ye = 100 5) Capital a fin de mes: C1 = Co + 3100ye 2850xe C1 3100ye + 2850xe = 2000000 Para el mes de febrero: 1) I1 + xf yf 520 2) 3050xf C1 3) yf I1 4) I2 = I1 + xf yf 5) C2 = C1 + 3250yf 3050xf Para el mes de marzo: 1) I2 + xm ym 520 2) 2900xm C2 3) ym I2 4) I3 = 200 = I2 + xm ym El modelo entonces queda como sigue: fO: Mx U = 3100ye + 3250yf + 2950ym 2850xe 3050xf 2900xm s. a. xe ye 420 2850xe 2000000 ye 100 I1 xe + ye = 100 C1 3100ye + 2850xe = 2000000 I1 + xf yf 520 3050xf C1 0 yf I1 0 I2 I1 xf + yf = 0 C2 C1 3250yf + 3050xf = 0 I2 + xm ym 520 2900xm C2 0 ym I2 0 I2 + xm ym = 200 Con todas las variables mayores o iguales a cero.
102

I1 + xf yf 520 3050xf C1 0 yf I1 0 I2 I1 xf + yf = 0 C2 C1 3250yf + 3050xf = 0

I2 + xm ym 520 2900xm C2 0 ym I2 0 I2 + xm ym = 200

program_5.indb 102

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Al resolver este problema utilizando la herramienta Solver de Excel, se obtiene que el plan ptimo de compras y ventas es ste: Comprar: Vender: 520 t en enero 200 t en marzo 100 t en enero 520 t en febrero

Al finalizar marzo se dispondr de 200 toneladas de maz en la bodega y de $1938000 en caja.

Lecturas complementarias
Eppen y otros (2000), sobre todo el captulo 3, secciones 3.1 a 3.4 y 3.10 a 3.17; Arreola y Arreola (2003), captulo 2; Stokey y Zeckhauser (1978).

Problemas de la unidad 3
Para cada uno de los problemas de esta seccin, identifique las variables con las unidades que corresponda, defina la fO, identifique las restricciones y plantee las ecuaciones del modelo de pL.

Problemas de produccin
Problema 3.1 Una fbrica de productos metal-mecnicos tiene alguna capacidad excedente que quiere utilizar para la produccin de algunos de los tres nuevos artculos que est considerando. El tiempo disponible medido en horas-mquina a la semana es el siguiente: para la fresadora 500 horas, torno, 350 horas, y rectificadora, 150 horas. La productividad de cada mquina, esto es, el nmero de productos que hace cada mquina en una hora, para cada uno de los tres productos es la siguiente:

103

program_5.indb 103

22/03/12 13:00

PROGRAMACIN LINEAL

Cuadro 3.12
Mquina Fresadora Torno Rectificadora Prod. 1 9 5 3 Prod. 2 3 4 0 Prod. 3 5 0 2

El departamento de mercadotecnia estima que se podr vender todo lo que se produzca de los producto 1 y 2, mientras que del producto 3 la demanda semanal no supera las 20 unidades. Si la ganancia unitaria es de $50, $20 y $25, respectivamente, cul debe ser la combinacin de productos que maximice la ganancia semanal? Problema 3.2 En una planta se producen cuatro productos diferentes (a, b, c, d); para cada producto se requiere realizar trabajo con cuatro mquinas (cortar, armar, pegar y pintar), el cual se expresa en min/kg en el cuadro 3.13. Se cuenta con 60 horas semanales de cada mquina (el armado se realiza con una mquina robotizada totalmente). Cuadro 3.13
Mquina min/kg Cortadora a b c d 5 3 4 4 Robot 10 6 5 2 Pegadora 6 4 3 1 Compresora 3 8 3 2 Demanda mxima 400 100 150 500

Los precios de venta de los productos por kilogramo son $9, $7, $6 y $5, respectivamente; la mano de obra tiene un costo de $2 por hora. El costo de materia prima para el producto 1 es de 3.5 $/kg, mientras que para los otros es de 1.2 $/kg. Cul es la produccin semanal que ms le conviene para maximizar su utilidad? Problema 3.3 Una planta productora de fibras tiene una lnea donde produce polister, elastano y dacrn. El departamento de hilandera requiere de 20, 40 y 30 horas respectivamente para producir una tonelada de cada una de las fibras; este departamento cuenta
104

program_5.indb 104

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

con 2000 horas. El departamento de teido cuenta con 4800 horas y requiere 70, 80 y 90 horas respectivamente para teir una tonelada de fibra. Por ltimo los productos deben ser colocados en bobinas de 1 kg para su venta. El tiempo requerido es de 25 horas por cada tonelada de polister o de dacrn y de 35 horas para bobinar una tonelada de elastano pues debe realizarse mucho ms lentamente para no perder sus propiedades. Se cuenta con 1500 horas de bobinadora. Las ventas limitan la produccin de dacrn a 25 000 kg por mes. Si los costos de materia prima para las 3 fibras son similares y si el precio de venta es de 1000, 1500 y 2000 pesos por tonelada, plantelo como un problema de pL. Problema 3.4 Una cooperativa opera cuatro granjas con rendimientos similares. Cada una de las granjas tiene cierta cantidad de hectreas y horas hombre disponibles como se muestra en el cuadro 3.14: Cuadro 3.14
Granja 1 2 3 4 ha tiles 500 900 300 700 Horas disponibles al mes 1700 3000 900 2200

Se est pensando en sembrar tres cultivos: maz, frijol y calabaza, cada uno de los cuales produce distintas ganancias y requieren distinta cantidad de mano de obra (vase cuadro 3.15). Tambin por cuestiones de dinero, solamente se compraron las semillas y fertilizantes para determinado nmero de ha mximo de cada cultivo. Cuadro 3.15
Semillas y fertilizantes ha mximas 700 800 300 Ganancias esperadas por ha ($) 500 200 300

Cultivo Maz Frijol Calabaza

Horas mes/ha 2 4 3

Determine el plan de cultivo ms apropiado con los recursos disponibles.

105

program_5.indb 105

22/03/12 13:00

PROGRAMACIN LINEAL

Problema 3.5 Una cooperativa agrcola posee 3 ranchos de 25, 30 y 40 ha respectivamente. Se est planeando la produccin del prximo ciclo agrcola. Las opciones son sembrar maz, frijol y sorgo; adems tienen instalaciones para la cra de hasta 2500 pollos en el rancho ms grande (adems de las hectreas para cultivo). Cuentan con un capital de $200000 para gastos de fertilizantes, semillas y el alimento de las aves. Debido a la cantidad de agua disponible en la presa, se les han asignado 200000 m3 para el riego. Para la cra de pollos se requieren de $20 por pollo, y un hombre puede atender a 250 animales (durante 125 das, que es el periodo antes de venderlos). Las necesidades de agua son inferiores a 1 m3 diario (puede despreciarse), y la utilidad, el precio de venta menos los costos, es de $20 por ave. En el siguiente cuadro se presentan los datos especficos de cada rancho as como los requerimientos de mano de obra por hectrea y la lmina de agua de cada cultivo para todo el ciclo productivo. Cuadro 3.16
Mano de obra (h/ha) Maz Frijol Sorgo 800 1200 300 Costo de los insumos ($/ha) 3000 5000 1200 Lmina de agua (cm) 55 60 20 Mano de obra disponible (h) 12000 20000 27000

Utilidad ($/ha) 7000 10200 4500

Rancho 1 2 3

La cooperativa debe planear cuntas hectreas de cada cultivo sembrar y dnde, as como la conveniencia o no de criar pollos. Para alimentar a los pollos requiere sembrar al menos 3 ha de sorgo. a) Cuntas variables de decisin tiene este problema?, descrbalas. b) Cuntas restricciones tiene el problema y cules son? c) Plantee el problema como un modelo de pL (sistema de ecuaciones). Problema 3.63 Una ciudad de dos millones de habitantes, que produce 3 000 toneladas de residuos por da, utiliza 3 incineradores, bastante obsoletos por cierto, como el mtodo para procesar la mayor parte de sus residuos. El resto los enva a un relleno sanitario a 20 km de la ciudad, con un costo mucho ms elevado.
3

Problema de polticas pblicas tomado de Stokey y Zeckhauser (1978). 106

program_5.indb 106

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

La capacidad en toneladas de cada incinerador as como las unidades de los contaminantes bixido de sulfuro y de partculas enviadas a la atmsfera por tonelada incinerada son: Cuadro 3.17
Incinerador 1 2 3 Capacidad (t/da) 1200 800 1000 Emisiones SO2 (Und/t) 250 150 220 Partculas (kg/t) 20 30 24

La nueva reglamentacin para el control de emisiones indica que las plantas de incineracin tendrn como topes en la emisin de contaminantes hasta 50 000 kg de partculas suspendidas y no ms de 400000 unidades de bixido de sulfuro. La ciudad debe planear la manera ms econmica de procesar sus desperdicios sin exceder los topes estipulados por la nueva reglamentacin ambiental.4 Plantee el problema como un modelo de pL. Problema 3.75 Una empresa pblica generadora de energa tiene una demanda de 2000 megavatios por hora (MWh) para una ciudad industrial. La legislacin ambiental la obliga a que la emisin de contaminantes generada est por debajo de 180 kg/h. La empresa debe decidir qu combustibles y mtodo utilizar para minimizar los costos de generacin, pero cumpliendo con las reglamentaciones ambientales. Cuadro 3.18
Contaminantes Combustible y mtodo actual Diesel pesado Con filtros de pila Importar energa 0.12 kg/ MWh 0.04 kg/ MWh 0.021 kg/ MWh 0 Costo MWh $3.5 $5.0 $5.8 $4.5

Pero si solamente puede importar 200 MWh, qu deber hacer?

4La incineracin de los desperdicios se realiza solamente en sociedades altamente industrializadas, que adems realizan la separacin de los materiales reutilizables, y los residuos remanentes tienen un elevado potencial calorfico. 5 Problema elaborado por la maestra Myriam Cardozo.

107

program_5.indb 107

22/03/12 13:00

PROGRAMACIN LINEAL

Problema 3.8 Una refinera compra dos tipos de petrleo: ligero tipo Brent y petrleo crudo pesado tipo Maya. Los costos actuales estn en 77 y 64 dlares por barril, respectivamente. De cada tipo de petrleo se obtiene por el proceso de destilacin las siguientes cantidades de gasolina, diesel y aceites lubricantes, expresado en barriles: Cuadro 3.19
Gasolina Crudo ligero Brent Crudo pesado Maya 0.40 0.33 Diesel 0.25 0.38 Aceites 0.30 0.25

La refinera debe entregar mensualmente 600000 barriles de gasolina, 500000 barriles de diesel y 200000 barriles de aceites lubricantes. Encuentre la cantidad de barriles de crudo de cada tipo que le conviene comprar para satisfacer la demanda con el mnimo costo en los insumos.

Problemas de planeacin nanciera

Problema 3.9 Un asesor financiero debe colocar 10 millones de pesos en cuatro alternativas financieras, cuidando obtener el mayor rendimiento anual, pero manteniendo al menos 10% de liquidez. Las opciones son Cetes a 90 das, Cetes a 180 das, acciones de Cemex y mesas de dinero. El rendimiento esperado es de 7.25% y 7.45% para los Cetes; Cemex se espera que de 8.5% a condicin de retenerlas durante un ao; y en mesas de dinero se espera 6.25%. Para minimizar riesgos no se quiere tener ms del 50% ni en acciones de Cemex ni en Cetes. Las acciones de Cemex cuestan $17, y los Cetes se venden en unidades de $1000. Plantee el problema como un modelo de pL. Problema 3.10 Banco Azteca estima que el prximo ao tendr 100 millnes de pesos para prstamos. Tiene distintos tipos de prstamos a diferente tasa de inters. Debido a las polticas de la empresa se deben respetar los siguientes lmites: a) los prstamos personales no pueden exceder 15%. b) Los prstamos para mejora de casas
108

program_5.indb 108

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

junto con los dedicados a actividades recreativas no pueden exceder 20% del total de los crditos. c) Los prestamos a las Pymes deben ser menos de 30% del total. d) Al menos 10% de los prstamos deben destinarse a los prstamos personales tipo a, otro tanto debe destinarse a las hipotecas y a las Pymes. El banco quiere maximizar sus utilidades. Cuntas variables tiene el problema?; cuntas restricciones? Plantee el problema de pL. Cuadro 3.20
Tipo de prstamo Personal tipo a Personal tipo b Automvil Hipoteca Inters anual (%) 8 12 10 8 Tipo de prstamo Mejoras a la casa habitacin Implementos para actividades recreativas Pymes Inters anual (%) 10 12 9

Problema 3.116 Conacyt ha decidido repartir 1000 millones de pesos para estimular la investigacin en innovacin tecnolgica en el rea de energa. Se recibieron 200 solicitudes para otros tantos proyectos entre los cuales se seleccionaron 6 finalistas. Un grupo de cientficos y economistas evaluaron los proyectos y estimaron los beneficios potenciales que cada uno de ellos podra significar para un periodo de 10 aos por cada peso invertido ahora en investigacin. Los proyectos seleccionados aparecen en el cuadro 3.21. Cuadro 3.21
Beneficio neto por peso invertido 4.4 3.8 4.1 3.5 5.1 3.2 Fondos solicitados (millones de pesos) 220 180 250 150 400 120

Proyecto 1 2 3 4 5 6

Tipo de energa Solar Solar Biocombustible Carbn Nuclear Geocntrica

Esto quiere decir que el primer proyecto al cabo de 10 aos potencialmente producir $4.4 por cada peso que se haya invertido en l despus de recuperar la inversin, y
6

Problema adaptado de un ejercicio de Reyes Garca y Romero (2004). 109

program_5.indb 109

22/03/12 13:00

PROGRAMACIN LINEAL

que requiere como mximo 220 millones de pesos, pero el Conacyt puede decidir entregarle slo parte de esos fondos. El Conacyt necesita decidir cunto dinero asignar a cada proyecto tratando de maximizar los beneficios futuros, pero tambin deben tomarse en cuenta otros criterios por lo que se ha decidido que al menos deben otorgarse $300 millones para la investigacin de energa solar, no menos de 100 millones de pesos para biocombustibles y restringir la cantidad invertida en investigaciones relacionadas con carbn y nuclear a menos de 250 millones de pesos en total.

Planeacin de publicidad
Problema 3.12 Se est planeando una campaa publicitaria para anunciar la apertura de un nuevo supermercado en Tapachula. Se cuenta con un presupuesto de $250000 y se est considerando la posibilidad de contratar anuncios en la radio a $10000, y en la televisin local, a $20000. Cada anuncio en la radio llega a 12000 personas y cada anuncio en la televisin llega a 20000 personas. Se quiere llegar a la mayor cantidad de pblico posible, pero garantizando una audiencia de al menos 20000 mujeres y de 18000 hombres adultos. Los medios de difusin dicen que su audiencia por anuncio es: Cuadro 3.22
Mujeres Radio Televisin 2000 2500 Hombres 1500 5000

Problemas de dietas
Problema 3.13 Un criadero de cerdos debe determinar los distintos tipos de alimento que deben dar a los cerdos para cubrir los requerimientos nutricionales a costo mnimo. En el siguiente cuadro se dan las unidades nutricionales por kilogramo de alimento, los requerimientos mnimos y los costos. Se debe encontrar la dieta de costo mnimo.

110

program_5.indb 110

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Cuadro 3.23
Requisito mnimo 200 180 150

Maz (kg) Carbohidratos Protenas Vitaminas Costo($/kg) 90 30 10 8

Grasa (kg) 20 80 20 9

Alfalfa (kg) 40 60 60 6

Unidad g g mg

Problema 3.14 Un hospital se propone elaborar una dieta balanceada para el desayuno de sus pacientes con las siguientes caractersticas: a) El desayuno debe aportar no menos de 480 caloras b) El consumo mnimo de protenas en el desayuno debe ser de 25 g. c) Los alimentos que se han de utilizar son jamn, huevo, leche, pan y queso fresco; Las caractersticas de cada uno de estos alimentos se dan a continuacin: Cuadro 3.24
Alimentos Jamn Huevo Leche Pan Queso Porcin 1 rebanada 1 pieza 1 vaso 1 pieza 1 racin Precio $2.5 $1.0 $2.2 $0.5 $4.0 Caloras 76 74 116 124 127 Protenas (g) 3.9 5.6 6.8 2.0 11.3

Plantelo como un modelo de pL considerando que el desayuno no debe llevar ms de dos huevos y que slo se incluir una pieza de pan si se incluye una porcin de jamn.

111

program_5.indb 111

22/03/12 13:00

PROGRAMACIN LINEAL

Problemas de mezclas
Problema 3.15 Una fbrica de plsticos planea sacar un nuevo producto utilizando plstico reciclado proveniente de cuatro plantas recicladoras. Dadas las caractersticas del producto que se quiere obtener en cuanto a flexibilidad, transparencia y resistencia trmica, se tiene que encontrar la mezcla ms conveniente de los cuatro insumos de tal manera que la resina resultante contenga al menos 20% de pet, al menos 30% de polietileno de baja densidad y al menos 20% de polipropileno. Debido a que se necesita que el producto final sea muy flexible, no debe contener ms de 30% de pet ni ms de 35% de polietileno. En el siguiente cuadro se indica el porcentaje del contenido de cada una de las resinas en los insumos provenientes de las cuatro plantas: Cuadro 3.25
Insumos de resina pet Polietileno Polipropileno

Planta 1 35 45 12

Planta 2 25 15 60

Planta 3 25 30 40

Planta 4 30 25 25

El precio del kilogramo de cada uno de los insumos es de $20, $25, $15 y $10. Indique cul es la mezcla de insumos ms conveniente para minimizar el costo del producto. Problema 3.16 Una pequea fbrica de productos cosmticos naturales produce jabn, champ para prevenir la cada del cabello, crema y aceite para la piel. Sus ingredientes bsicos son la jojoba, el romero y la sbila que ellos mismos producen. Esta temporada han cosechado y procesado 1000 litros de sbila, 560 litros de aceite de romero y 2200 litros de aceite de jojoba. Debido a que se trata de una cooperativa quieren utilizar especialmente todo lo producido por ellos mismos. En el siguiente cuadro se indican las cantidades mnimas y mximas que debe contener un litro de estos productos, as como los precios tentativos de venta por litro. El jabn lleva una pasta base que no debe exceder 70%; el champ puede tener hasta 20% de agua, la crema slo 12% y el aceite apenas 5%. Se debe decidir cul es el mejor plan de produccin.
112

program_5.indb 112

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Cuadro 3.26
Jojoba (ml) Jabn Champ Crema Aceite mx. 180 mn. 125 mx. 250 mn. 140 mx. 450 mn. 300 mx. 800 mn. 700 mn. 50 mx. 100 mn. 30 70 Sbila (ml) mx. 300 mn. 175 mx. 350 mn. 220 mn. 220 mx. 350 mn. 320 mx. 30 55 43 Romero (ml) Precio de venta ($/l) 25

Turnos de trabajo
Problema 3.17 Un municipio conurbado altamente poblado ha estimado el nmero mnimo de patrullas necesarias para la vigilancia de su territorio para periodos de cuatro horas. Los oficiales de las patrullas trabajan turnos continuos de ocho horas y no hay policas con turnos parciales. Se quiere organizar los turnos para reducir el nmero de empleados necesarios. Los oficiales pueden empezar su turno al comienzo de cualquiera de los intervalos que se muestran a continuacin; en cada patrulla deben ir dos oficiales. Cuadro 3.27
Intervalo 12 a 16 16 a 20 20 a 00 00 a 4 4a8 8 a 12 Nmero mnimo requerido 100 250 400 500 200 150

Indique cul es la cantidad de patrullas con que debe contar el municipio (se considera que debe tener un 10% de carros extra para darles mantenimiento) y cuntos oficiales requiere para satisfacer la demanda de vigilancia.

113

program_5.indb 113

22/03/12 13:00

PROGRAMACIN LINEAL

Problemas de transporte
Problema 3.18 Una compaa que produce concreto debe abastecer a cuatro obras en construccin. La compaa tiene tres plantas desde las que suministrar el concreto. En el cuadro se indican los costos por camin enviado desde las plantas a las obras, que depende de la distancia que se debe recorrer, as como la capacidad diaria en cargas de camin de cada planta y la demanda de cada obra. Cuadro 3.28
Capacidad de las plantas 120 100 80

Planta 1 2 3 Demanda

Obra 1 $80 $40 $100 50

Obra 2 $100 $80 $120 40

Obra 3 $60 $75 $90 75

Obra 4 $70 $60 $110 60

Plantee las ecuaciones como un problema de pL. Problema 3.19 Una compaa tiene dos bodegas que surten mercanca a cinco tiendas de abarrotes. Los envos se hacen slo por una carga completa de camin. El nmero de cargas requerido por cada tienda es de 80, 50, 75, 45, 80, respectivamente. Los costos de envo estn en el siguiente cuadro junto con las cargas disponibles en cada bodega. Cuadro 3.29
Tiendas 1 Bodega 1 Bodega 2 $40 $50 2 $50 $35 3 $45 $40 4 $50 $20 5 $25 $40 Mx. de cargas disponibles 100 250

a) Haga una representacin del problema. b) Plantee las ecuaciones del problema. c) D una solucin posible.

114

program_5.indb 114

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Problema 3.20 Una empresa duea de una cadena de supermercados acaba de comprar las tiendas de otra cadena, con lo que logra una cobertura a nivel nacional. Ahora tiene que disear la estrategia para surtir a sus nuevas tiendas desde las bodegas que tena establecidas, incluso para determinar cules de ellas necesitarn aumentar su capacidad. El criterio para decidir desde dnde surtir a las nuevas tiendas lo establece tratando de minimizar las distancias, ya que esto se traduce en disminucin de combustible y de costos. Tiene que proveer de mercancas a cuatro tiendas, una en Cuernavaca, otra en Puebla y dos en el Distrito Federal, una al norte y otra en el oriente. Las bodegas se encuentran en la ciudad de Veracruz, en Puebla y Toluca. En el siguiente cuadro se dan las distancias en kilmetros entre las bodegas, las tiendas y las necesidades semanales medidas en camiones de 12 t. Cuadro 3.30
Tiendas/Bodegas Cuernavaca D. F. norte D. F. oriente Puebla Toluca 96 40 48 117 Puebla 109 80 75 8 Veracruz 291 260 255 182 Necesidades semanales 35 70 73 47

La bodega de Toluca tiene capacidad para surtir 48 toneladas, la de Puebla, un mximo de 72, y la de Veracruz puede suplir hasta 150, y lo que no sea necesario se embarcar para Tampico. Encuentre la mejor manera de realizar el transporte de mercancas. Problema 3.217 Se debe realizar un plan de emergencia para asignar heridos a los hospitales generales de la zona en caso de que ocurra un temblor importante en la ciudad. Debido a la densidad de la poblacin y al tipo de construcciones, se estima que un temblor de grado 6 en la escala de Richter producira 300 heridos en la zona a y 250 heridos en la zona b. Hay tres hospitales en la ciudad para atender este tipo de emergencias. El tiempo de traslado desde el lugar a es de 25, 15 y 10 minutos a cada uno de los hospitales, y desde el punto b es de 20, 5 y 15 minutos. Las capacidades de los hospitales para estos casos son 250, 150 y 150 pacientes respectivamente. Cmo convendra asignar las
7

Problema de polticas pblicas elaborado a partir de Stokey y Zeckhauser (1978). 115

program_5.indb 115

22/03/12 13:00

PROGRAMACIN LINEAL

vctimas a los hospitales? Cul es el tiempo promedio de traslado? Si disponen de 10 ambulancias, cunto tiempo tardarn en recoger todos los heridos? Problema 3.22 Una cadena de restaurantes tiene tres locales en Tlalpan, Villa Coapa y Tlhuac, a los que debe surtir los vasos desechables. Hay tres proveedores con diferentes precios y capacidades de produccin que le ofrecen el producto. stos le enviaron sus cotizaciones y capacidades de produccin. Adems se anexa el precio del transporte por 1000 unidades. Se solicita plantearlo como un problema de transporte. Cuadro 3.31
Proveedor a b c Precio (por 1000 unidades) $9 $10 $11 Capacidad anual 40000 75000 135000

Costo del transporte por 1000 vasos en pesos. Cuadro 3.32

De proveedor a b c Tlalpan 8 5 2 Villa Coapa 1 2 4 Tlhuac 3 5 2

Se necesitan 90000 vasos en Tlalpan; 70000 en Villa Coapa, y 90000 en Tlhuac.

Problemas de inventarios
Problema 3.238 Una compaa quiere planear la produccin de cierto artculo para las prximas 4 semanas. El costo de produccin es de $1 000 las 2 primeras semanas y $1 500 las siguientes. Las demandas semanales son 7, 8, 10 y 10 unidades, pero la planta no puede
8Este

problema fue adaptado de Moskowitz, H. Y. Wrigth, G., Investigacin de operaciones, PHH. 116

program_5.indb 116

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

producir ms de 9 unidades semanales, aunque puede pagar horas extra las dos ltimas semanas, lo que le permite aumentar la produccin en 2 unidades semanales, con un costo extra de $580 por unidad. El exceso de produccin se puede almacenar a un costo de $35 por semana y por unidad. El objetivo es minimizar los costos totales.

Respuesta a los problemas de la unidad 3

Problema 3.1. El problema tiene 3 variables y 4 restricciones. La solucin ptima es producir a la semana 450 unidades del artculo 1; 1040, del artculo 2, y no producir el tercer artculo. La ganancia semanal ser de $43300 y quedarn sin utilizar 103.3 horas de fresadora. Problema 3.2. La solucin ptima es producir de a, 220 kg; b, 100 kg; c, 150 kg, y d, 525 kg. Con esta produccin sobraran (1505 min), 25 h de pegadora y 15.7 h de compresora. La utilidad sera de $3556.50. Problema 3.3. Se deben producir 25 t de elastano y 25 t de dacrn, con lo que se obtiene una utilidad de $87500, quedarn disponibles 250 h en el departamento de teido. Problema 3.4. La cooperativa deber sembrar: granja 1: 200 ha de frijol y 300 ha de calabaza, granja 2: 300 ha de maz y 600 ha de frijol, granja 3: 300 ha de maz, granja 4: 100 ha de maz. La ganancia esperada con este plan de produccin es de $600000. Problema 3.5. a) Hay 10 variables de decisin: el nmero de ha que se deben sembrar de cada cultivo en cada rancho y el nmero de pollos que deben criarse. b) El problema tiene 10 restricciones. c) La solucin ptima ser criar los 2500 pollos para los que hay capacidad, y producir especialmente sorgo: 25 ha en el rancho 1, 27.5 ha en el rancho 2, y 40 ha en el rancho 3; adems se debern sembrar 2.5 ha en el rancho 2 de frijol. La utilidad ser de $491750. Seguramente hay otras soluciones alternas con igual utilidad. Problema 3.6. Solamente se podrn incinerar 1987.5 t: en el incinerador 1, 625 t; en el incinerador 2, 800 t, y en el incinerador 3, 562.5 t. Las otras 1012.5 t debern ser enviadas al relleno sanitario para no sobrepasar los lmites de contaminacin establecidos por la norma ambiental. Problema 3.7. La empresa pblica deber producir 1350 MWh con el combustible y mtodos tradicionales, 450 Mwh a partir de diesel pesado e importar los 200 Mwh que le permiten. El costo ser de $7875 pesos por los 2000 Mwh necesarios. Problema 3.8. La refinera debe comprar 906475 barriles de petrleo ligero y 719424 barriles de crudo pesado con un costo de $115841727 millones de dlares. Con
117

program_5.indb 117

22/03/12 13:00

PROGRAMACIN LINEAL

esto producir exactamente las cantidades necesarias de gasolina y diesel, pero tendr un excedente de 215798 barriles de aceites lubricantes. Problema 3.9. El asesor debe invertir $1000000 en mesas de dinero; $4000000 en 4000 Cetes a 180 das, y $5000000 en 249117 acciones de Cemex. El rendimiento ser de $785500. Problema 3.10. El banco, para maximizar sus utilidades, debe prestar: 10% a prstamos personales tipo a 5% a prstamos personales tipo b 20% a prstamos para actividades recreativas 10% a prstamos hipotecarios 45% a prstamos para automviles (o a mejora de vivienda) 10% en prstamos a Pymes Problema 3.11. El Conacyt ha decidido entregar las siguientes cantidades a cada uno de los proyectos, expresado en millones de pesos: Solar 1: 220 mp Solar 2: 180 mp Biocombustibles: 250 mp Nuclear: 250 mp Geotrmica: 100 mp Problema 3.12. Es conviente contratar 25 anuncios de radio solamente, con lo que se tendra una audiencia de 300000 personas con al menos 50000 mujeres y 37500 hombres. Problema 3.13. La dieta de costo mnimo es de $24 diarios por cerdo e incluye 1.20 kg de maz, 0.103 kg de grasa y 2.27 kg de alfalfa; si se quiere que los animales engorden ms rpido se les puede dar comida suplementaria. Problema 3.14. La dieta de costo mnimo debe incluir una rebanada de jamn, dos huevos, 1.2 vasos de leche (o sea, un vaso grande) y una pieza de pan. El costo del desayuno es de $7.55 aproximadamente. Problema 3.15. La mezcla ms conveniente tiene un costo de 13 $/kg y est compuesta con 20% de la planta 1; 20% de la planta 3, 60% de la planta 4. Problema 3.16. La fbrica debe producir solamente champ, crema y aceite. Las mezclas que se deben realizar se muestran en el cuadro con una utilidad de 258 434 pesos.

118

program_5.indb 118

22/03/12 13:00

FORMuLACIN DE pRObLEMAS DE pROGRAMACIN LINEAL

Cuadro 3.33
Litros Jojoba Sbila Romero Agua Total Champ 107.8 238.6 269.4 154.0 769.8 Crema 193.4 354.5 19.3 77.3 644.5 Aceite 1899.0 407.0 271.3 135.6 2715.9

Problema 3.17. Se debe contar con no menos de 500 patrullas (sera conveniente tener algunas para imprevistos y mantenimiento); se deben organizar 900 parejas de oficiales, o sea, 1800 oficiales. Aunque hay muchas soluciones, una posible sera que entren a trabajar 150 oficiales a las 12 am, 350 a las 4 pm, 550 a las 8 pm, 450 a las 12 am y 300 a las 8 am. Problema 3.18. La compaa debe enviar la carga en los camiones como se indica en el cuadro, y el costo ser de $13950. Cuadro 3.34
Obra 1 Planta 1 Planta 2 Planta 3 50 40 5 Obra 2 Obra 3 70 Obra 4 50 10

Problema 3.19. En este caso la oferta es inferior a la demanda, por lo que se sugiere para minimizar los costos, enviar la siguiente cantidad de cargas: Cuadro 3.35
Bodega 1 2 Tienda 1 20 60 50 75 45 Tienda 2 Tienda 3 Tienda 4 Tienda 5 80

Problema 3.20. Para surtir la demanda recorriendo la menor distancia posible se deben realizar los siguientes envos de camiones. Se recorrern 31964 km.

119

program_5.indb 119

22/03/12 13:00

PROGRAMACIN LINEAL

Cuadro 3.36
Distrito Federal (zona norte) Toluca Puebla Veracruz 22 48 37 36 35 47 Distrito Federal (zona oeste) Cuernavaca Puebla

Problema 3.21. Lo ms conveniente es enviar de la zona a 150 heridos al hospital 1 y 150 al hospital 3. De la zona b se deben enviar 100 heridos al hospital 1 y 150 al hospital 2. El tiempo promedio de los traslados ser de 14.55 minutos. Como las ambulancias deben ir y regresar, demorarn ms de 26 horas (26.66) en terminar de trasladar a todos los heridos. Problema 3.22. Lo ms conveniente para la cadena es surtir al restaurante de Tlhuac con 40000 unidades del proveedor a, 5000 de b y 45000 de c. Para el restaurante de Villa Coapa se deben comprar las 70000 piezas al proveedor b; y para Tlalpan, las 90000 unidades del proveedor c. El costo ser de $3150. Problema 3.23. La mejor solucin para la compaa es producir lo siguiente: Primer semana: 9 unidades, 7 para la demanda y 2 para la tercera semana Segunda semana: 9 unidades, 8 para la demanda y una para la cuarta semana Tercera semana: 8 unidades Cuarta semana: 9 unidades Con un costo de 18 (1000) + 2 (2) 35 + 1 (35) + 17 (1500)

120

program_5.indb 120

22/03/12 13:00