1. Universidad Nacional Experimental Francisco de Miranda rea de Tecnologa Unidad Curricular: Investigacin de Operaciones Tema No. 1 Modelacin Matemtica. Formulacin de Modelos de Programacin Lineal Facilitador: Dr. Juan J. Lugo Marn. 2. Antecedentes de la Investigacin de Operaciones La Investigacin de Operaciones surgi formalmente durante la Segunda Guerra Mundial, cuando haba una gran necesidad de administrar los escasos recursos. La Fuerza Area Britnica form el primer grupo que desarrollara mtodos cuantitativos para resolver estos problemas operacionales y bautiz sus esfuerzos como investigacin operacional. Poco despus, las fuerzas armadas estadounidenses formaron un grupo similar, compuesto por cientficos fsicos e ingenieros, cinco de los cuales posteriormente fueron laureados con el premio Nobel. Los esfuerzos de estos grupos, especialmente en el rea de la deteccin por radar, se consideran vitales en el triunfo de la guerra area de Gran Bretaa. 3. Antecedentes de la Investigacin de Operaciones Despus de la Segunda Guerra Mundial, los administradores de la industria reconocieron el valor de aplicar tcnicas similares a sus complejos problemas de decisin. Los primeros esfuerzos se dedicaron a desarrollar modelos apropiados y procedimientos correspondientes para solucionar problemas que surgan en reas tales como la programacin de refineras de petrleo, la distribucin de productos, la planeacin de produccin, el estudio de mercado y la planeacin de inversiones. Estos procedimientos de soluciones se hicieron posibles con el advenimiento de computadoras de alta velocidad, porque la resolucin del tpico problema de investigacin de operaciones requiere demasiados clculos para ser realizados prcticamente a mano. El uso de tcnicas de administracin ha aumentado con los avances en los clculos hasta el punto en que actualmente estas tcnicas son empleadas rutinariamente en una computadora de escritorio para solucionar muchos problemas de decisin. 4. Investigacin de Operaciones - Definiciones Administracin/ investigacin de operaciones: el uso de las matemticas y las computadoras para ayudar a tomar decisiones racionales frente a problemas de administracin complejos. La definicin de Churchman, Ackoff y Arroff: La investigacin de operaciones es la aplicacin, por grupos interdisciplinarios, del mtodo cientfico a problemas relacionados con el control de las organizaciones o sistemas (hombre-mquina), a fin de que se produzcan soluciones que mejor sirvan a los objetivos de la organizacin. 5. Investigacin de Operaciones - Definiciones La definicin de la Sociedad de Investigacin de Operaciones de la Gran Bretaa es la siguiente: La investigacin de operaciones es el abordaje de la ciencia moderna a los complejos problemas que surgen en la direccin y en la administracin de grandes sistemas de hombres, mquinas, materiales y dinero, en la industria, en los negocios, en el gobierno y en la defensa. Su actitud diferencial consiste en desarrollar un modelo cientfico del sistema tal, que incorpore valoraciones de factores como el azar y el riesgo y mediante el cual se predigan y comparen los resultados de decisiones, estrategias o controles alternativos. Su propsito es el de ayudar a la gerencia a determinar cientficamente sus polticas y acciones. La investigacin de operaciones tambin se puede definir como la aplicacin por grupos interdisciplinarios del mtodo cientfico a problemas relacionados con el control de las organizaciones o sistemas a fin de que se produzcan soluciones que mejor sirvan a los objetivos de toda la organizacin 6. Investigacin de Operaciones - Metodologa Paso 1: Planteamiento y conceptualizacin del Problema. Paso 2: Formulacin del Modelo. Paso 3: Resolucin del Modelo. 7. Investigacin de Operaciones - Metodologa Paso 4: Validacin del Modelo. Paso 5: Implantacin del Modelo 8. Investigacin de Operaciones reas de Aplicacin Como su nombre lo dice, la Investigacin de Operaciones significa hacer investigacin sobre las operaciones. Entonces, la investigacin de operaciones se aplica a problemas que se refieren a la conduccin y coordinacin de operaciones (o actividades) dentro de una organizacin. La naturaleza de la organizacin es en su ms amplio significado y, de hecho, la investigacin de operaciones se ha aplicado de manera extensa e reas tan diversas como la manufactura, el transporte, las telecomunicaciones, la planeacin financiera, el cuidado de la salud, los servicios pblicos, etc. 9. Que es un Modelo Un Modelo es producto de una abstraccin de Un Modelo es un un sistema real, eliminado las complejidades y Patrn de Referencia. haciendo suposiciones pertinentes, se aplican tcnicas matemticas y se obtiene una Un Modelo es una representacin simblica del mismo. abstraccin selectiva de la realidad . Sistema Real El modelo se define Autor: Natasha Snchez como una funcin objetiva y restricciones que se Sistema Supuesto expresan en trminos de Modelo las variables (alternativas) de decisin del problema. 10. Que es un Modelo Un modelo matemtico son representaciones Un modelo de decisin matemticas de situaciones reales que se debe considerarse como un podran usar para tomar mejores decisiones, o vehculo para resumir un bien, simplemente para entender mejor la problema de decisin en situacional real. forma tal que haga posible la identificacin y Un modelo matemtico es una ecuacin, evaluacin sistemtica de desigualdad o sistema de ecuaciones o todas las alternativas de desigualdades, que representan determinados decisin del problema. aspectos del sistema fsico representado en el Despus se llega a una modelo. Los modelos de este tipo se utilizan en decisin seleccionando la gran medida en las ciencias fsicas, en el campo alternativa que se juzgue de la ingeniera los negocios y la economa. sea la mejor entre todas las opciones disponible. 11. Tipos de Modelo Modelo de Simulacin: Por lo general, toma la forma de Modelos Determinsticos: un conjunto de suposiciones Cuando se conoce con certeza el comportamiento de acerca de la operacin del sistema, los parmetros involucrados en el Modelo, por lo expresado como relaciones tanto tienen un bajo nivel de incertidumbre. matemticas o lgicas entre los objetos de inters en el sistema. A diferencia de las soluciones matemticas exactas disponibles con la mayor parte de los modelos Autor: Natasha Snchez analticos, el proceso de simulacin tiene que ver con Modelo Probabilstico o Estocstico: ejecutar el modelo a travs del En los que parte de la informacin necesaria no se tiempo, por lo comn en una conoce con certeza sino ms bien se comporta de una computadora, para generar manera probabilstica , poseen por lo tanto un alto muestras representativas de las nivel de incertidumbre. medidas de desempeo. 12. Modelos de Programacin Lineal Un modelo de Programacin Lineal (PL) considera que las variables de decisin tienen un comportamiento lineal, tanto en la funcin objetivo como restricciones del problema. En este sentido, la Programacin Lineal es una de las herramientas ms utilizadas en la Investigacin de Operaciones debido a que por su naturaleza se facilitan los clculos y en general permite una buena aproximacin de la realidad. 13. Modelos de Programacin Lineal Decisiones de Planeacin de Fabricacin o Produccin Compra Agregada Problemas de Problemas de Dietas Aplicaciones Mezclas Administracin Decisiones de de Cartera de Mezcla de Valores Productos 14. Elementos de un Modelo de Programacin Lineal Funcin Objetivo: Variable de Decisin /variable/variable El objetivo Global de un problema controlable: de decisin expresado en una forma Valores que se buscan determinar con matemtica en trminos de los la solucin del modelo datos y de las variables de decisin. Restricciones (limitaciones): Requerimientos o Limitaciones Condiciones de No Negatividad: sobre los valores de variables en Condiciones del modelo que estipulan que las variables de un modelo matemtico decisin deben tener slo valores tpicamente impuesto por no negativos (positivos). condiciones externas. 15. Elementos de un Modelo de Programacin Lineal Vector Disponibilidad (valor del lado derecho): An el cambio ms pequeo en el valor del lado derecho de una restriccin puede ocasionar que la solucin ptima cambie. Sin embrago, mientras el valor cambia dentro de algn intervalo alrededor de su valor original, el valor ptimo de la funcin objetivo cambia en forma lineal en proporcin con el cambio en el valor del lado derecho, de acuerdo al precio sombra. Incluso fuera de este intervalo, para cada valor del lado derecho respecto del cual el programa lineal es factible, existe un precio sombra, que puede usarse para obtener el nuevo valor ptimo de la funcin objetivo. Coeficientes Objetivos: Coeficientes tecnolgicos: Coeficientes que acompaan a Coeficientes que acompaan a las variables en la Ecuacin las variables en las restricciones. Objetivo. 16. Pasos para formular un Modelo de Programacin Lineal Paso 1: Identificacin de las variables de Decisin: El primer paso en la formulacin del problema es identificar las variables de decisin, a menudo simplemente llamadas variables. Los valores de estas variables, una vez determinados, proporcionan la solucin al problema. Cuando los valores de los elementos no se conocen todava, a cada variable de decisin se le da un nombre simblico. Se puede elegir el nombre simblico que recuerde la cantidad que la variable de decisin representa. 17. Pasos para formular un Modelo de Programacin Lineal Paso 2: Identificacin de los datos del problema: La finalidad de resolver un problema es proporcionar los valores para las variables de decisin que ha identificado. Se requiere conocer cierta informacin para ayuda a determinar esos valores. A diferencia de las variables de decisin, cuyos valores usted puede controlar, usted no puede controlar directamente los valores de los datos. Paso 3: Identificacin de la funcin objetivo: En este paso en la formulacin del problema es expresar el objetivo organizacional global en forma matemtica usando las variables de decisin y los datos conocidos del problema. La funcin objetivo, generalmente se crea en tres etapas: Establecer el objetivo en forma verbal Donde sea adecuado descomponer el objetivo en una suma, diferencia o producto de cantidades individuales. Expresar las cantidades individuales matemticamente usando las variables de decisin y otros datos conocidos en el problema. 18. Pasos para formular un Modelo de Programacin Lineal Paso 4. Identificacin de las restricciones : El paso final en la formulacin del problema es identificar estas restricciones y escribirlas en forma matemtica. Las restricciones son condiciones que las variables de decisin deben satisfacer para construir una solucin aceptable. Estas restricciones por lo general surgen de: Limitaciones fsicas Restricciones impuestas por la administracin Restricciones externas Relaciones implicadas entre variables Restricciones lgicas sobre las variables individuales 19. Modelos de Programacin Lineal Decisiones de Mezcla de Productos Ejemplo: EL PROBLEMA DE MEZCLA DE PRODUCTOS DE BLUBBERMAID, INC. BlubberMaid, Inc, fabrica tres TABLA. INGREDIENTES USADOS EN LA PRODUCCIN DE AIRTEX, EXTENDEX Y productos de caucho: Airtex (material RESISTEX INGREDIENTE (oz/lb de producto) esponjoso), Extendex (material elstico) PRODUCTO POLMERO A POLMERO B POLMERO C BASE y Resistex (material rgido). Los tres Airtex 4 2 4 6 productos requieren los mismos tres Extendex 3 2 2 9 polmeros qumicos y una base. La Resistex 6 3 5 2 cantidad de cada ingrediente usada por libra del producto final se muestra en la tabla 20. Modelos de Programacin Lineal BlubberMaid, Inc, tiene el compromiso de producir al menos 1000 libras de Airtex, 500 libras de Extendex y 400 libras de Resistex para la prxima semana, pero la gerencia de la compaa sabe que puede vender ms de cada uno de los tres productos. Los inventarios actuales de los ingredientes son 500 libras del polmero A, 425 libras del polmero B, 650 libras del polmero C y 1100 libras de base. Cada libra de Airtex produce a la compaa una ganancia de $7, cada libra de Extendex una ganancia de $7 y cada libra de Resistex una ganancia de $6. Como gerente del departamento de produccin, usted necesita determinar un plan de produccin ptimo para esta semana. Solucin: Identificacin de las variables de decisin. Siguiendo los pasos de la formulacin de problemas, primero identifique las variables de decisin. Pregntese lo que puede controlar y la informacin que constituye un plan de produccin, esto lo debe llevar a identificar las siguientes variables: A: el nmero de libras de Airtex por producir esta semana E: el nmero de libras de Extendex por producir esta semana R: el nmero de libras de Resistex por producir esta semana 21. Modelos de Programacin Lineal Identificacin de la funcin objetivo. Para BlubberMaid, el objetivo lgico es determinar cunto fabricar de cada producto para maximizar la ganancia total. Al aplicar la tcnica de descomposicin se llega a: Ganancia Total=ganancia de Airtex+ ganancia de Extendex+ ganancia de Resistex Como cada libra de Airtex produce una ganancia de $7, A libras de Airtex produce $7 A. De manera similar, Extendex y Resistex contribuyen con $7E y $6R, respectivamente, a la ganancia total. En trminos de las variables de decisin y de los datos de ganancia, la funcin objetivo es: Maximizar 7A+7E+6R 22. Modelos de Programacin Lineal Identificacin de las restricciones Aplicar la tcnica de agrupamiento lo debe conducir a identificar los siguientes tres grupos de restricciones: 1. Restricciones de recursos para asegurar que no se usen ms de los tres polmeros y la base que estn disponibles. 2. Restricciones de demanda para asegurar que se cumplan los compromisos de la compaa. 3. Restricciones lgicas para especificar que todas las cantidades de produccin son no negativas. RESTRICCIONES DE RECURSOS Este grupo consiste en cuatro restricciones: una para cada uno de los tres polmeros y una para la base. Para la disponibilidad limitada de 500 libras del polmero A: Cantidad empleada del polmero A 500 libras 23. Modelos de Programacin Lineal El uso de la descomposicin lleva a: Cantidad empleada del polmero A= (cantidad empleada para producir A libras de Airtex) + (cantidad empleada para producir E libras de Extendex) + (cantidad empleada para producir R libras de Resistex) Para determinar la cantidad del polmero A usada en la fabricacin de cada producto, trabaje con un ejemplo especfico. Por ejemplo, fije A=100, E=300 y R=200. De acuerdo con los datos de la tabla 1: Cantidad del polmero A empleada en Airtex = 4(100) = 400 Cantidad del polmero A empleada en Extendex = 3(300) = 900 Cantidad del polmero A empleada en Resistex = 6(200) = 1200 Entonces, en trminos de las variables de decisin, podra pensar que la restriccin apropiada para el polmero A es: 4 A + 3 E + 6 R 500 24. Modelos de Programacin Lineal Sin embargo, esta restriccin no es correcta. La razn es que las unidades en la expresin de la izquierda estn en onzas, pero las unidades de la derecha estn en libras. Esta discrepancia puede corregirse convirtiendo las unidades de cualquier lada a las del otro lado. Por ejemplo, al convertir las 500 libras disponibles del polmero A a 800 onzas (1 libra es igual a 16 onzas) se obtiene la siguiente restriccin: 4 A + 3 E + 6 R 8000 (polmero A) Siguiendo una lgica similar para los tres resultados de recursos restantes en estas restricciones: 2 A + 2 E + 3 R 6800 (polmero B) 4 A + 2 E + 5 R 10400 (polmero C) 6 A + 9 E + 2 R 17600 (base) 25. Modelos de Programacin Lineal RESTRICCIONES DE DEMANDA Este grupo consiste en tres restricciones: una para el requerimiento mnimo sobre la cantidad de cada uno de los tres productos. Estas restricciones son A 1000 (Airtex) E 500 (Extendex) R 400 (Resistex) RESTRICCIONES LGICAS Como todas las cantidades de produccin deben ser no negativas, se necesitan las siguientes restricciones lgicas: A, E, R 0 26. Modelos de Programacin Lineal Formulacin completa y solucin del problema de mezcla de productos de BlubberMaid, Inc. Como gerente del departamento de produccin, usted junta todas las piezas, lo que resulta en el siguiente modelo matemtico del problema de programacin lineal de BlubberMaid, Inc. Maximizar 7A+7E+6R Dependiendo de RESTRICCIONES DE RECURSOS A 1000 (Airtex) E 500 (Extendex) R 400 (Resistex) RESTRICCIONES LGICAS A E R 0 27. Modelos de Programacin Lineal La solucin ptima a este problema, calculada usando cualquier paquete de software de programacin lineal, es A= 1000.00 E= 533.33 R= 400.00 Con una valor de funcin objetivo de 13 333.33. En otras palabras, el plan semanal ptimo es producir 1000 libras de Airtex, 533.33 libras de Extendex y 400 libras de Resistex, dando como resultado una ganancia neta de $13 333.33. 28. Modelos de Programacin Lineal Decisiones de Fabricacin o Compra Ejemplo: EL PROBLEMA DE HACER O COMPRAR DE MTV STEEL COMPANY MTV Steel Company produce tres tamaos de tubos: A, B y C, que son vendidos, respectivamente en $10, $12 y $9 por pie. Para fabricar cada pie del tubo A se requieren 0.5 minutos de tiempo de procesamiento sobre un tipo particular de mquina de modelado. Cada pie del tubo B requiere 0.45 minutos y cada pie del tubo C requiere 0.6 minutos. Despus de la produccin, cada pie de tubo, sin importar el tipo, requiere 1 onza de material de soldar. El costo total se estima en $3, $4 y $4 por pie de los tubos A, B y C, respectivamente. Para la siguiente semana, MTV Steel ha recibido pedidos excepcionalmente grandes que totalizan 2000 pies del tubo A, 4000 pies del tubo B y 5000 pies del tubo C. Como slo se disponen de 40 horas de tiempo de mquina esta semana y slo se tienen en inventario 5500 onzas de material de soldar, el departamento de produccin no podr satisfacer esta demanda, que requiere un total de 97 horas de tiempo de mquina y 11000 onzas de material de soldar. 29. Modelos de Programacin Lineal No se espera que contine este alto nivel de demanda. En vez de expandir la capacidad de las instalaciones de produccin, la gerencia de MTV Steel est considerando la compra de algunos de estos tubos a pro-veedores de Japn a un costo de entrega de $6 por pie del tubo A, $6 por pie del tubo B y $7 por pie del tubo C. Estos diversos datos se resumen en la tabla 2. Como gerente del departamento de produccin, se le ha pedido hacer recomendaciones respecto a la cantidad de produccin de cada tipo de tubo y la cantidad de compra a Japn para satisfacer la demanda y maximizar las ganancias de la compaa. TABLA2. DATOS PARA EL PROBLEMA DE HACER O COMPRAR DE MTV STEEL TIEMPO DE MATERIAL COSTO DE COSTO PRECIO DE DEMANDA TIPO MQUINA PARA SOLDAR PRODUCCIN COMPRA VENTA ($/ft) (ft) (min/ft) (oz/ft) ($/ft) ($/ft) A 10 2000 0.50 1 3 6 B 12 4000 0.45 1 4 6 C 9 5000 0.60 1 4 7 Cantidad Disponible 40 hr 5500 oz 30. Modelos de Programacin Lineal Solucin: Identificacin de las variables de decisin En este problema, tiene libertad para elegir cuntos pies de cada tipo de tubo producir y cuntos pies comprar a Japn. Esto da como resultado las siguientes seis variables de decisin: AP= el nmero de pies de tubo de tipo A por producir BP= el nmero de pies de tubo de tipo B por producir CP= el nmero de pies de tubo de tipo C por producir AJ= el nmero de pies de tubo de tipo A que comprar a Japn BJ= el nmero de pies de tubo de tipo B que comprar a Japn CJ= el nmero de pies de tubo de tipo C que comprar a Japn 31. Modelos de Programacin Lineal Identificacin de la funcin objetivo. Como se estableci en la descripcin del problema, el objetivo global es maximizar las ganancias totales. Si aplicamos la descomposicin se obtiene: Ganancias Totales= (ganancias de la produccin)+ (ganancias de los productos comprados a Japn) Si aplicamos la descomposicin a las ganancias de la produccin tenemos: Ganancias de la produccin= (ganancias de producir el tubo de tipo A)+ (ganancias de producir el tubo de tipo B)+ (ganancias de producir el tubo de tipo C) 32. Modelos de Programacin Lineal Cada una de estas ganancias, a su vez, se calcula como el ingreso menos el costo por pie. Por ejemplo, como los tubos del tipo A se venden a $10 por pie pero su produccin cuesta $3, la ganancia neta es $7 por pie. Por tanto, la ganancia por producir AP pies de tubo del tipo A es 7 AP. Un clculo similar para los tubos de los tipos B y C tiene como resultado: Ganancias de la produccin= 7 AP+ 8 BP + 5 CP Aplicando una descomposicin y lgica similares a los productos comprados a Japn se tiene: Ganancias de los productos comprados a Japn= 4 AJ+ 6 BJ+ 2 CJ Como esperara, cada pie de tubo producido tiene como resultado una ganancia ms alta que cada pie de tubo comprado del proveedor externo. La combinacin de estos dos componentes de ganancia resulta en la siguiente funcin objetivo global: Maximizar 7 AP+ 8 BP+ 5 CP+ 4 AJ+ 6 BJ+ 2 CJ 33. Modelos de Programacin Lineal La aplicacin de la descomposicin lleva a: Tiempo de mquina= (tiempo de mquina usado para producir tubo de tipo A)+ total usado (tiempo de mquina usado para producir tubo de tipo B)+ (tiempo de mquina usado para producir tubo de tipo C) Recuerde de la tabla 2 que cada pie del tubo A requiere 0.5 minutos de tiempo de mquina. Por tanto, para producir AP pies se requiere 0.5AP minutos. De manera anloga, cada pie de tubo B requiere 0.45 minutos y cada pie de tubo C requiere 0.6 minutos. La restriccin es: 0.5AP+ 0.45BP+ 0.6CP 40 Sin embargo, observe que la cantidad del lado izquierdo se expresa en minutos, mientras que la de la derecha se expresa en horas. Una forma de corregir esta inconsistencia es convertir 40 horas en 40 * 60= 2400 minutos: 0.5AP+ 0.45BP+ 0.6CP 2400 (tiempo de mquina) 34. Modelos de Programacin Lineal Regresando a la disponibilidad de material para soldar, la restriccin asociada es: El material para soldar total no debe exceder las 5500 onzas Aplicando la descomposicin y recordando que cada pie de tubo, sin importar el tipo, requiere 1 onza de material para soldar, esta restriccin de recursos es: AP+ BP+ CP 5500 (material para soldar) RESTRICCIONES DE DEMANDA Este grupo est constituido por tres restricciones, una para la demanda asociada con cada tipo de tubo. Para el tubo A: Nmero total de pies del tubo de tipo A= 2000 pies 35. Modelos de Programacin Lineal Modelos de Programacin Lineal Aplicando la descomposicin: Nmero total de pies =(nmero de pies de tipo A producidos)+ del tubo de tipo A (nmero de pies de tipo A comprados a Japn) = AP+ AJ En consecuencia, la restriccin de demanda del tubo de tipo A es: AP+ AJ = 2000 (demanda del tipo A) Una lgica similar da como resultado las siguientes restricciones de demanda para los tubos de tipo B y C: BP+ BJ = 4000 (demanda del tipo B) CP+ CJ = 5500 (demanda del tipo C) 36. Modelos de Programacin Lineal RESTRICCIONES LGICAS La nica restriccin lgica en este problema es que todas las variables deben ser no negativas. Formulacin completa y solucin del problema de fabricacin o compra de MTV Steel Company Una vez que se unen todas las piezas, da por resultado el modelo de programacin lineal siguiente para el problema de MTV Steel Company: Maximizar 7AP+ 8BP+ 5CP+ 4AJ+ 6BJ+ 2CJ Dependiendo de RESTRICCIONES DE DEMANDA AP + AJ = 2000 (demanda del tipo A) BP + BJ = 4000 (demanda del tipo B) CP +CJ = 5500 (demanda del tipo C) 37. Modelos de Programacin Lineal RESTRICCIONES DE RECURSOS 0.5AP+ 0.45BP+ 0.6CP 2400 (tiempo de mquina) AP+ BP+ CP 5500 (tiempo para soldar) RESTRICCIONES LGICAS AP , BP , CP , AJ , BJ , CJ 0 La solucin ptima a este problema, obtenida con un paquete de software de programacin lineal, es: AP = 2000.000 BP = 0.000 CP = 2333.333 AJ = 0.000 BJ = 4000.000 CJ = 2666.667 Con una ganancia neta de $55000. En otras palabras, MTV Steel debera producir 2000 pies de tubo de tipo A y 2333.333 pies de tubo C e importar 4000 pies de tubo de tipo B y 2666.667 pies de tubo de tipo C de Japn. 38. Modelos de Programacin Lineal Problemas de dietas Ejemplo: EL PROBLEMA DE DIETAS DEL HOSPITAL GENERAL MOUNTAIN VIEW El Departamento de Nutricin del Hospital General Mountain View prepara 30 mens de cena, uno para cada da del mes. Una comida consiste en espagueti, pavo, papas en escalope, espinacas y pastel de manzana. Como director del Departamento de Nutricin, usted ha determinado que esta comida debe proporcionar 63000 miligramos (mg) de protenas, 10 mg de hierro, 15 mg de niacina, 1 mg de tiamina y 50 mg de vitamina C. Cada 100 gramos de esta comida proporciona la cantidad de cada nutriente y grasas indicadas en la tabla 3. TABLA 3. NUTRIENTES PROPORCIONADOS POR LAS DISTINTAS COMIDAS NUTRIENTE (mg/100g) PROTENAS HIERRO TIACINA TIAMINA VITAMINA C GRASA Espagueti 5000 1.1 1.4 0.18 0.0 5000 Pavo 29300 1.8 5.4 0.06 0.0 5000 Papas 5300 0.5 0.9 0.06 10.0 7900 Espinacas 3000 2.2 0.5 0.07 28.0 300 Pastel de Manzana 4000 1.2 0.6 0.15 3.0 14300 39. Modelos de Programacin Lineal Para evitar la demasiada cantidad de un tipo de comida, no debe incluirse en ella ms de 300 gramos de espagueti, 300 gramos de pavo, 200 gramos de papas, 100 gramos de espinacas y 100 gramos de pastel de manzana. Como director del departamento de nutricin, usted desea determinar la composicin de una comida que satisface los requerimientos nutricionales y proporciona la mnima cantidad de grasas. Solucin: Identificacin de las variables de decisin. En este problema, usted puede controlar la cantidad de cada uno de los cinco alimentos que incluir en la comida, lo que lo lleva a definir las siguientes cinco variables: SPAG= el nmero de 100 gramos de espagueti que incluir PAVO= el nmero de 100 gramos de pavo que incluir PAPA= el nmero de 100 gramos de papas que incluir SPIN= el nmero de 100 gramos de espinacas que incluir MANZ= el nmero de 100 gramos de espinacas que incluir Por conveniencia, se ha escogido que las unidades de las variables se den en cientos de gramos porque sas son las unidades usadas en la tabla 3. 40. Modelos de Programacin Lineal Identificacin de la funcin objetivo. Como se estableci en la descripcin del problema, el objetivo global es minimizar el contenido de grasas totales de la dieta. Aplicando los resultados de descomposicin en lo siguiente: Contenido de grasas totales= (grasa aportada por el espagueti)+ (grasa aportada por el pavo)+ (grasa aportada por las papas)+ (grasa aportada por las espinacas)+ (grasa aportada por el pastel de manzana) Si usa los datos de la ltima columna de la tabla 3 y trabaja con un ejemplo especfico debe llegar a identificar el siguiente objetivo global: Minimizar 5000SPAG+ 5000PAVO+ 7900PAPA+ 300SPIN+ 14300MANZ 41. Modelos de Programacin Lineal Identificacin de las restricciones La aplicacin de la tcnica de agrupamiento lo conduce a los siguientes tres grupos de restricciones: 1. Restricciones de nutrientes para asegurar que la comida proporciona la cantidad mnima de cada nutriente. 2. Restricciones de lmite para asegurar que no se incluya demasiada cantidad de un tipo de comida (por ejemplo, solicitar a un paciente que coma 1000 gramos de espinacas). 3. Restricciones lgicas para asegurar que todas las variables sean no negativas. REQUERIMIENTOS DE NUTRIENTES Este grupo consiste en cinco restricciones, una para asegurar la cantidad mnima de cada uno de los cinco nutrientes. Considere el requerimiento de protenas: Cantidad total de protenas en la comida 63000 mg 42. Modelos de Programacin Lineal Aplicando la descomposicin: Cantidad total de = (cantidad de protenas del espagueti)+ Protenas en la comida (cantidad de protenas del pavo)+ (cantidad de protenas de las papas)+ (cantidad de protenas de las espinacas)+ (cantidad de protenas del pastel de manzana) Refirase a la primera columna de la tabla 3. Cada 100 gramos de espagueti contienen 5000 mg de protenas. Por tanto, SPAG cien gramos de esta comida proporciona 5000SPAG mg de protenas a la comida. De manera similar, usando los datos restantes de la primera columna de la tabla 3 da como resultado la siguiente restriccin para protenas: 5000SPAG+ 29300PAVO+ 5300PAPA+ 3000SPIN+ 4000MANZ 63000 (protenas) 43. Modelos de Programacin Lineal Aunque las unidades de las variables se expresan en cientos de gramos, las unidades de ambos lados de la restriccin anterior estn en miligramos. Usando las siguientes cuatro columnas de datos de la tabla 3 obtenemos las siguientes restricciones similares para cada uno de los siguientes cuatro nutrientes: 1.1SPAG + 1.8PAVO + 0.5PAPA + 2.2SPIN + 1.2MANZ 10 (hierro) 1.4SPAG + 5.4PAVO + 0.9PAPA + 0.5SPIN + 0.6MANZ 15 (niacina) 0.18SPAG+ 0.06PAVO+ 0.06PAPA+ 0.07SPIN+ 0.15MANZ 1 (tiamina) 10PAPA+ 28SPIN+ 3MANZ 50 (vitamina C) 44. Modelos de Programacin Lineal RESTRICCIONES DE LMITE Estas restricciones limitan la cantidad mxima de cada tipo de alimento en la comida. Teniendo en mente que las unidades de las variables estn en cientos de gramos, surgen las siguientes restricciones de lmite: SPAG 3 PAVO 3 PAPA 2 SPIN 1 MANZ 1 RESTRICCIONES LGICAS La nica restriccin lgica en este problema es que todas las variables son no negativas. 45. Modelos de Programacin Lineal Formulacin completa y solucin del problema de dietas del Hospital General Mountain View Toda esta informacin da como resultado el siguiente modelo de programacin lineal para el problema del Hospital General Mountian View: Minimizar 5000SPAG+ 5000PAVO+ 7900PAPA+ 300SPIN+ 14300MANZ Dependiendo de REQUERIMIENTOS DE NUTRIENTES 5000SPAG+ 29300PAVO+ 5300PAPA+ 3000SPIN+ 4000MANZ 63000 (protenas) 1.1SPAG+ 1.8PAVO+ 0.5PAPA+ 2.2SPIN+ 1.2MANZ 10 (hierro) 1.4SPAG+ 5.4PAVO+ 0.9PAPA+ 0.5SPIN+ 0.6MANZ 15 (niacina) 0.18SPAG+ 0.06PAVO+ 0.06PAPA+ 0.07SPIN+ 0.15MANZ 1 (tiamina) 10PAPA+ 28SPIN+ 3MANZ 50 (vitamina C) 46. Modelos de Programacin Lineal RESTRICCIONES DEL LMITE SPAG 3 PAVO 3 PAPA 2 SPIN 1 MANZ 1 RESTRICCIONES LGICAS SPAG, PAVO, PAPA, SPIN, MANZ 0 Con un contenido de grasa de 54800 miligramos. En otras palabras, la comida debera consistir en 300 gramos de espagueti, 283.3 gramos de pavo, 200 gramos de papas, 100 gramos de espinacas y 66.7 gramos de pastel de manzana. 47. Modelos de Programacin Lineal Administracin de cartera de valores Ejemplo: EL PROBLEMA DE INVERSIN DE PENSION PLANNERS, INC. Al gerente de cartera de PensionvPlanners, Inc. se le ha pedido invertir $1 000 000 de un gran fondo de pensiones. El departamento de investigacin de Inversiones ha identificado seis fondos mutuos con estrategias de inversin variables, resultando en diferencia rendimientos potenciales y riesgos asociados, como se resume en la tabla 4. TABLA 4. RIESGOS Y TASA ESPERADA DE RENDIMIENTOS DE SEIS FONDOS DE INVERSIN FONDO 1 2 3 4 5 6 Precio ($/accin 45 76 110 17 23 22 Devolucin esperada (%) 30 20 15 12 10 7 Categora de riesgo Alto Alto Alto Mediano Mediano Bajo 48. Modelos de Programacin Lineal Una forma de controlar el riesgo es limitar la cantidad de dinero invertido en los diversos fondos. Para ese fin, la administracin de Pension Planners, Inc. ha especificado las siguientes pautas: 1. La cantidad total invertida en fondos de alto riesgo debe estar entre 50 y 75% de la cartera. 2. La cantidad total invertida en fondos de mediano riesgo debe estar entre 20 y 30% de la cartera. 3. La cantidad total invertida en fondos de bajo riesgo debe ser al menos de 5% de la cartera. Una segunda forma de controlar el riesgo es diversificar, esto es, esparcir el riesgo invirtiendo en muchas alternativas diferentes. La gerencia de Pension Planners, Inc, ha especificado que la cantidad invertida en los fondos de alto riesgo 1, 2 y 3 deben estar en la tasa 1:2:3, respectivamente. La cantidad invertida en los fondos de mediano riesgo 4 y 5 debe ser 1:2. Con estas pautas, qu cartera debera usted, gerente de cartera, recomendar para maximizar la tasa esperada de retorno? 49. Modelos de Programacin Lineal Solucin: Identificacin de las variables de decisin. En este problema, usted puede controlar cunto invertir en cada uno de los seis fondos mutuos, dando as origen a seis variables de decisin. Como siempre, debe especificar las unidades asociadas con cada variable. Por ejemplo, para el fondo 1, podra definir cualquiera de las siguientes variables: F1 = el nmero de acciones del fondo 1 por comprar F1 = el nmero de dlares por invertir en el fondo 1 F1 = la fraccin de la agenda por invertir en el fondo 1 Cada opcin conduce a un modelo matemtico diferente pero equivalente. Aqu se utiliza la ltima opcin. As que, para cada uno de los fondos restantes, defina: F2 = la fraccin de la cartera por invertir en el fondo 2 F3 = la fraccin de la cartera por invertir en el fondo 3 F4 = la fraccin de la cartera por invertir en el fondo 4 50. Modelos de Programacin Lineal F5 = la fraccin de la cartera por invertir en el fondo 5 F6 = la fraccin de la cartera por invertir en el fondo 6 Identificacin de la funcin objetivo. Como se estableci en la descripcin del problema, el objetivo global es maximizar la tasa esperada de rendimiento, esto es: Si aplicamos la descomposicin al numerador obtenemos: Rendimiento total esperado: (rendimiento esperado del fondo 1)+ (rendimiento esperado del fondo 2)+ (rendimiento esperado del fondo 3)+ (rendimiento esperado del fondo 4)+ (rendimiento esperado del fondo 5)+ (rendimiento esperado del fondo 6) 51. Modelos de Programacin Lineal Para determinar el rendimiento esperado del fondo 1, trabaje con un ejemplo especfico en el que 10% de la cartera se invierte en el fondo 1, es decir, F1=0.10. En este caso, 0.10*1 000 000=$100 000 de la cartera se invierte en el fondo 1. De acuerdo con los datos de la tabla 4, se espera que este dinero devuelva 30% o 0.30*100000= $30 000. Por tanto, en trminos de F1, Rendimiento esperado del fondo 1= (cantidad invertida en el fondo 1)* (tasa de rendimiento del fondo 1) = (F1* 1 000 000)* 0.30 = 300 000F1 Usando una lgica similar para los cinco fondos restantes, llegamos a Rendimiento total esperado= 300 000F1 + 200 000F2 + 150 000F3 + 120 000F4 + 100 000F5 + 70 000F6 52. Modelos de Programacin Lineal Dividiendo esto entre la inversin total de $1 000 000 obtenemos la tasa de rendimiento y por tanto la siguiente funcin objetivo: Maximizar 0.30F1 + 0.20F2 + 0.15F3 + 0.12F4 + 0.10F5 + 0.07F6 Identificacin de las restricciones Aplicando la tcnica de agrupamiento debe llegar a identificar los siguientes tres grupos de restricciones: 1. Limitaciones de inversin para controlar la cantidad invertida en cada una de las tres categoras de riesgo. 2. Restricciones de diversificacin para extender la inversin dentro de cada categora de riesgo. 3. Restricciones lgicas. 53. Modelos de Programacin Lineal RESTRICCIONES DE LIMITACIN DE INVERSIN Este grupo consiste en tres subgrupos de restricciones, uno para cada categora de riesgo, a saber: 1. La cantidad total invertida en fondos de alto riesgo debe estar entre 50 y 75% de la cartera. Como F1, F2 y F3 representan la fraccin de la cartera por invertir en fondos de alto riesgo, la fraccin de la cartera total invertida en fondos de alto riesgo es F1 + F2 + F3. Estas restricciones son F1 + F2 + F3 0.50 (mnimo en alto riesgo) F1 + F2 + F3 0.75 (mximo en alto riesgo) 2. La cantidad total invertida en fondos de mediano riesgo debe estar entre 20 y 30% de la cartera. Como F4 y F5 representan la fraccin de cartera por invertir en fondos de mediano riesgo, la fraccin de la cartera total invertida en fondos de mediano riesgo es F4 + F5. Estas restricciones son: F4 + F5 0.20 (mnimo en mediano riesgo) F4 + F5 0.30 (mximo en alto riesgo) 54. Modelos de Programacin Lineal 3. La cantidad total invertida en fondos de bajo riesgo debe ser al menos 5% de la cartera. Como F6 es la fraccin de la cartera invertida en fondos de bajo riesgo, esta restriccin es: F6 0.05 (mnimo en bajo riesgo) RESTRICCIONES DE DIVERSIFICACIN Este grupo de restricciones se utiliza para controlar el riesgo asegurando que la cantidad invertida en los fondos pertenecientes a una categora de riesgo dada est dentro de la tasa especificada, de la manera siguiente: 1. La cantidad invertida en los fondos de alto riesgo 1, 2 y 3 debe estar en la tasa 1:2:3. Esta restriccin especfica que la cantidad invertida en el fondo 2 sea el doble de la cantidad invertida en el fondo 1: F2 = 2F1 55. Modelos de Programacin Lineal Si cambiamos el orden para que todas las variables estn a la derecha, se obtiene: - 2F1 + F2 = 0 (proporcin de F1 a F2) De manera similar, la cantidad invertida en el fondo 3 debe ser tres veces la invertida en el fondo 1: F2 = 3F1 -3F1 + F3 = 0 (proporcin de F1 a F3) 2. La cantidad invertida en los fondos 4 y 5 de mediano riesgo debe estar en la proporcin de 1:2, esto es, la cantidad invertida en el fondo 5 debe ser el doble de la del fondo 4: F5 = 2F4 Si cambiamos el orden para que todas las variables estn a la derecha, se obtiene: -2F4 + F5 = 0 (proporcin de F4 a F5) 56. Modelos de Programacin Lineal RESTRICCIONES LGICAS Claro est que un conjunto de restricciones lgicas es que cada variable sea no negativa. Asimismo, como es posible comprar acciones fraccionales de un fondo mutuo, a estas variables se les permite tener cualquier valor fraccional, lo que resulta en un problema de programacin lineal. Ms an, se requiere otra restriccin lgica para asegurar que se invierta la cartera total de precisamente $1 000 000. Como las variables de decisin representan la fraccin de esta cartera por invertir en los diversos fondos, esta restriccin es: La fraccin total de $1 000 000 invertida debe ser igual a 1 , o F1+ F2+ F3+ F4+ F5+ F6 = 1.0 (agenda total) 57. Modelos de Programacin Lineal Formulacin completa y solucin del problema de inversin de Pension Planners, Inc. A continuacin se muestra el modelo de programacin lineal completo para los socios generales de Pension Planners, Inc: Maximizar 0.30F1+ 0.20F2+ 0.15F3+ 0.12F4+ 0.10F5+ 0.07F6 Dependiendo de RESTRICCIONES DE LIMITACIN DE INVERSIN F1+ F2+ F3 0.50 (mnimo en alto riesgo) F1+ F2+ F3 0.75 (mximo en alto riesgo) F4+ F5 0.20 (mnimo en mediano riesgo) F4+ F5 0.30 (mximo en mediano riesgo) F6 0.05 (mnimo en bajo riesgo) 58. Modelos de Programacin Lineal RESTRICCIONES DE DIVERSIFICACIN -2F1 + F2 = 0 (proporcin de F1 a F2) -3F 1 + F3 = 0 (proporcin de F1 a F3) -2F4 + F5 = 0 (proporcin de F4 a F5) RESTRICCIONES LGICAS F1 + F2 + F3 + F4 + F5 + F6 = 1.0 (cartera total) F1 + F2 + F3 + F4 + F5 + F6 0 La solucin ptima para este problema que cualquier paquete de software de programacin lineal produce es: F1 = 0.1250 F2 = 0.2500 F3 = 0.3750 F4 = 0.0667 F5 = 0.1333 F6 = 0.0500 59. Modelos de Programacin Lineal Cada una tasa de rendimiento de 0.168583. En otras palabras, la cantidad de dinero invertido en cada uno de los seis fondos es: Cantidad en el fondo 1 = 0.1250 * 1 000 000 = $ 125 000 Cantidad en el fondo 2 = 0.2500 * 1 000 000 = $ 250 000 Cantidad en el fondo 3 = 0.3750 * 1 000 000 = $ 375 000 Cantidad en el fondo 4 = 0.0667 * 1 000 000 = $ 66 700 Cantidad en el fondo 5 = 0.1333 * 1 000 000 = $ 133 300 Cantidad en el fondo 6 = 0.0500 * 1 000 000 = $ 50 000 Inversin Total = $ 1 000 000 con una tasa de rendimiento esperado de 16. 86% (o $ 168 600). Recuerde que las variables de decisin se definen como la fraccin de la cartera a invertir, en vez de la cantidad de dlares. Este enfoque tiene una ventaja clara. Si la cantidad de dlares de la cartera cambia, un evento probable, el modelo actual permanece inalterado. Simplemente necesita multiplicar las fracciones obtenidas en la solucin anterior por el nuevo tamao de la cartera para determinar las nuevas cantidades a invertir en cada uno de los seis fondos. 60. Modelos de Programacin Lineal Problemas de Mezclas Ejemplo: EL PROBLEMA DE MEZCLADO DE GASOLINA DE HEXXON OIL COMPANY Hexxon Oil Company obtiene tres tipos de petrleo crudo de sus pozos de Mississippi, Nuevo Mxico y Texas. La gasolina obtenida de estos petrleos crudos se mezcla junto con dos aditivos para obtener el producto final. Estos petrleos crudos y aditivos contienen azufre, plomo y fsforo, como se muestra en la tabla 5. El costo de cada componente tambin se presenta. Debido a los residuos e impurezas, cada galn de petrleo crudo de Mississipi resulta slo en 0.35 de galn del producto final, que contiene 0.07% de azufre. De manera similar, cada galn de crudo de Nuevo Mxico produce 0.40 de galn del producto final que contiene 0.08% de sulfuro y cada galn de crudo de Texas resulta en 0.30 de galn del producto final que contiene 0.10% de azufre. La gerencia ha establecido las siguientes especificaciones para controlar las cantidades de azufre, plomo y fsforo: 61. Modelos de Programacin Lineal 1. Cada galn debe tener a lo ms 0.07% de azufre 2. Cada galn debe tener entre 1.25 y 2.5 gramos de plomo 3. Cada galn debe tener entre 0.0025 y 0.0045 gramos de fsforo 4. La cantidad total de los aditivos no puede exceder de 19% de la mezcla TABLA 5. COMPOSICIN Y COSTO DE LOS COMPONENTES DE MEZCLA PETROLEOS CRUDOS ADITIVOS Mississipi Nuevos Mxico Texas 1 2 Azufre /%) 0.07 0.08 0.10 - - Plomo (g/gal) - - - 7 6 Fsforo (g/gal) - - - 0.025 0.02 Costo ($/gal) 0.55 0.47 0.33 0.08 0.12 Como gerente de produccin, determine un plan de mezclado que produzca una gasolina aceptable al mnimo costo. 62. Modelos de Programacin Lineal Solucin: Identificacin de las variables de decisin Usted puede controlar la cantidad de cada tipo de crudo y cada aditivo por mezclar al producir un galn de gasolina. Esto lleva a las siguientes cinco variables de decisin: XM = el nmero de galones de petrleo crudo de Mississippi usados para hacer un galn de gasolina. XN = el nmero de galones de petrleo crudo de Nuevo Mxico usados para hacer un galn de gasolina. XT = el nmero de galones crudo de Texas usados para hacer un galn de gasolina. A1 = el nmero de galones del aditivo 1 usados para hacer un galn de gasolina. A2 = el nmero de galones del aditivo 2 usados para hacer un galn de gasolina. 63. Modelos de Programacin Lineal Identificacin de la funcin objetivo Como se estableci en la descripcin del problema, el objetivo global es minimizar el costo de los componentes usados en la fabricacin de cada galn de gasolina. La aplicacin de la descomposicin nos lleva a: Costo Total = (costo del petrleo crudo de Mississippi) + (costo del petrleo crudo de Nuevo Mxico) + (costo del petrleo crudo de Texas) + (costo del aditivo 1) + (costo del aditivo 2) Usando las variables y los costos asociados de la tabla 5 obtenemos la siguiente funcin objetiva: Minimizar 0.55XM + 0.47XN + 0.33X T + 0.08 A1 + 0.12 A2 64. Modelos de Programacin Lineal Identificacin de las restricciones Aplicando la tcnica de agrupamiento debe llegar a la identificacin de los siguientes tres grupos de restricciones: 1. Una restriccin de produccin para asegurar la produccin de 1 galn de gasolina, porque el plan de mezcla es para cada galn. 2. Restricciones de composicin de mezclado para asegurar que la gasolina resultante cumpla con los requerimientos de azufre, plomo, fsforo y aditivos. 3. Restricciones lgicas. RESTRICCIONES DE PRODUCCIN Esta restriccin asegura que se produzca precisamente 1 galn de gasolina: Cantidad de gasolina producida = 1 galn 65. Modelos de Programacin Lineal Si aplicamos la descomposicin llegamos a Cantidad de gasolina = (cantidad producida del petrleo crudo de Mississippi)+ (cantidad producida del petrleo crudo de Nuevo Mxico)+ (cantidad producida del petrleo crudo de Texas)+ (cantidad del aditivo 1)+ (cantidad del aditivo 2) Recuerde que cada galn de crudo de Mississippi produce slo 0.35 de galn de gasolina. Por tanto, XM galones de este crudo producen 0.35XM galones de gasolina. De manera similar, como cada galn de petrleo crudo de Nuevo Mxico produce 0.40 de galn de gasolina y cada galn de petrleo crudo de Texas resulta en 0.30 de galn de gasolina, esta restriccin es 0.35XM + 0.40XN + 0.30XT + A1 + A2 = 1.0 (produccin) 66. Modelos de Programacin Lineal RESTRICCIONES DE COMPOSICION DE MEZCLADO Este grupo consiste en tres conjuntos de restricciones, uno por cada una de las limitaciones de azufre, plomo y fsforo en la mezcla final. Por ejemplo, para el azufre: Proporcin de azufre en la mezcla 0.0007 (esto es, 0.07%) Aplicando la descomposicin, Sin embargo, de la restriccin de produccin anterior, la cantidad total de la mezcla es precisamente 1 galn, as que lo nico que se necesita calcular es la cantidad de azufre en la mezcla. Aplicando la descomposicin, Cantidad de azufre = (cantidad de azufre del petrleo crudo de Mississippi)+ en la mezcla (cantidad de azufre del petrleo crudo de Nuevo Mxico)+ (cantidad de azufre del petrleo crudo de Texas)+ (cantidad de azufre del aditivo 1)+ (cantidad de azufre del aditivo 2) 67. Modelos de Programacin Lineal De acuerdo con la tabla 5, cada galn de petrleo crudo de Mississippi produce 0.35 de galn de gasolina que contiene 0.07% de azufre. Por tanto, XM galones de este petrleo crudo produce 0.35 XM galones que contienen 0.07% de azufre. As Cantidad de azufre del petrleo crudo de Mississippi = 0.0007 * 0.35Xm = 0.000245XM Observando que los aditivos no aportan azufre, y aplicando una lgica similar a los otros dos resultados de petrleos crudos en la siguiente restriccin de azufre: 0.35 * 0.0007XM + 0.40 * 0.0008XN + 0.30 * 0.001XT 0.0007 o 0.000245XM + 0.00032XN + 0.0003XT 0.0007 (azufre) 68. Modelos de Programacin Lineal Existen lmites inferiores y superiores sobre las cantidades de plomo y azufre en la mezcla final. Aplicando el mismo razonamiento usado en el desarrollo de la restriccin de azufre, se obtienen las siguientes cuatro restricciones para plomo y fsforo: 7 A1 + 6 A2 2.50 (lmite superior en plomo) 7 A1 + 6 A2 1.25 (lmite inferior en plomo) 0.025 A1 + 0.02 A2 0.0045 (lmite superior en fsforo) 0.025 A1 + 0.02 A2 0.0025 (lmite inferior en fsforo) Finalmente, existe la limitacin de que la mezcla contenga a lo ms 19% de aditivos. Por tanto, el total de A1 y A2 debe ser de a lo ms 0.19 de galn, resultando la siguiente restricciones: A1 + A2 0.19 (lmite superior en aditivos) 69. Modelos de Programacin Lineal RESTRICCIONES LGICAS La nica restriccin lgica es que todas las variables sean no negativas. Formulacin completa y solucin del problema de mezclas de la Hexxon Oil Company Como gerente de produccin de Hexxon Oil Company, rene toda esta informacin en el siguiente modelo de programacin lineal: Minimizar 0.55XM + 0.47XN + 0.33XT + 0.08 A1 + 0.12 A2 Dependiendo de RESTRICCIONES DE PRODUCIN 0.35XM + 0.40XN + 0.30XT + A1 + A2 = 1.0 (produccin) 70. Modelos de Programacin Lineal RESTRICCIONES DE COMPOSICION DE MEZCLADO 0.000245XM + 0.00032XN + 0.0003XT 0.0007 (azufre) 7 A1 + 6 A2 2.50 (lmite superior en plomo) 7 A1 + 6 A2 1.25 (lmite inferior en plomo) 0.025 A1 + 0.02 A2 0.0045 (lmite superior en fsforo) 0.025 A1 + 0.02 A2 0.0025 (lmite inferior en fsforo) A1 + A2 0.19 (lmite superior en aditivos) RESTRICCIN LGICA XM , XN , XT , A1 , A2 0 71. Modelos de Programacin Lineal La solucin ptima a este problema, que resulta de usar cualquier paquete de software de programacin lineal, es XM = 0.0000 XN = 1.3750 XT = 0.8667 A1 = 0.1400 A2 = 0.0500 con una valor de funcin objetivo de 0.94945. En otras palabras, cada galn de producto final se fabrica mezclando y procesando 1.3750 galones de petrleo crudo de Nuevo Mxico y 0.8667 de galn de petrleo crudo de Texas con 0.14 de galn de aditivo 1 y 0.05 de galn de aditivo 2, a un costo total de 94.945 centavos. 72. Modelos de Programacin Lineal Planeacin de Produccin Agregada Ejemplo: EL PROBLEMA DE PLANEACIN DE PRODUCCIN DE NATIONAL STEEL CORPORATION National Steel Corporation (NSC) produce un acero especial usado en las industrias de aviacin y aeroespaciales. El departamento de ventas de NSC ha recibido pedidos de 2400, 2200, 2700 y 2500 toneladas de acero para cada uno de los siguientes 4 meses. NSC puede satisfacer estas demandas produciendo el acero, extrayndolo de su inventario, o usando cualquier combinacin de las dos alternativas. Se proyecta que los costos de produccin por tonelada de acero durante cada uno de los siguientes cuatro meses sean de $7400, $7500, $7600 y $7650. Como los costos suben cada mes, debido a las presiones inflacionarias, tal vez sea mejor que NSC produzca ms acero del que necesita en un mes determinado y que almacene el exceso. La capacidad de produccin, sin embargo, no puede exceder las 4000 toneladas en ningn mes. La produccin mensual se termina al final del mes, cuando la demanda se satisface. Cualquier acero remanente se almacena en inventario a un costo de $120 por tonelada por cada mes que permanece all. Estos datos se resumen en la tabla 6 73. Modelos de Programacin Lineal TABLA 6. DATOS PARA EL PROBLEMA DE PRODUCCIN-PLANEACIN DE NSC MES 1 2 3 4 Demanda (tons) 2400 2200 2700 2500 Costo de Produccin ($/ton) 7400 7500 7600 7650 Costo de inventario ($/ton/mes) 120 120 120 120 Si el nivel de produccin se incrementa de un mes al siguiente, entonces la compaa incurre en un costo de $50 por tonelada de produccin incrementada para cubrir la mano de obra adicional y/o el tiempo extra. Cada tonelada de produccin disminuida incurre en un costo de $30 para cubrir los beneficios de empleados no utilizados. El nivel de produccin durante el mes anterior fue de 1800 toneladas, y el inventario que comienza es de 1000 toneladas. El inventario al final del cuarto mes debe ser de al menos 1500 toneladas para cubrir la demanda anticipada. Formule un plan de produccin para NSC que minimice los costos totales en los siguientes 4 meses. 74. Modelos de Programacin Lineal Solucin: Identificacin de las variables de decisin En este problema, usted tiene la libertad para elegir cuntas toneladas de acero producir cada mes para satisfacer la demanda. Surgen cuatro variables: X1 = el nmero de toneladas de acero por producir durante el mes 1 X2 = el nmero de toneladas de acero por producir durante el mes 2 X3 = el nmero de toneladas de acero por producir durante el mes 3 X4 = el nmero de toneladas de acero por producir durante el mes 4 A primera vista, usted podra pensar que stas son todas las variables que se requieren. Con estas variables, siempre puede determinar la cantidad en inventario. Por ejemplo, del diagrama esquemtico de la figura 1, el inventario al final del primer mes es 75. Modelos de Programacin Lineal Inventario al final del mes 1 = inventario inicial + cantidad de produccin demanda = 1000 + X1 2400 cantidad de produccin (X1) Inventario de inicio Inventario de terminacin Mes 1 (l1=1000) (I2) Demanda (D1=2400) Figura 1. Relacin entre niveles de inventario, produccin y demanda 76. Modelos de Programacin Lineal Sin embargo, escribir el inventario al final del segundo, tercero y subsecuentes meses es ms complicado. Por ejemplo, para el mes 2: Inventario al = inventario inicial+ cantidad de produccin- demanda final del mes 2 = (1000 + X1 2400) + X2 2200 Para simplificar, es conveniente crear otras cinco variables para representar los niveles de inventario al principio de cada mes: I1 = inventario en toneladas al principio del mes 1 I2 = inventario en toneladas al principio del mes 2 I3 = inventario en toneladas al principio del mes 3 I4 = inventario en toneladas al principio del mes 4 I5 = inventario en toneladas al principio del mes 5 77. Modelos de Programacin Lineal Identificacin de la funcin objetivo Como se estableci en la descripcin del problema, el objetivo global es minimizar los costos totales sobre el horizonte de planeacin de 4 meses. Si aplicamos la descomposicin para identificar tres componentes de costo diferentes llegamos a Costos totales = costos de produccin+ costos de inventario+ costos del cambio en la produccin COSTOS DE PRODUCCIN Aplicando nuevamente la descomposicin se identifican los costos de produccin como la suma de los costos de produccin en cada uno de los 4 meses. Usando las variables de produccin X1, X2, X3, X4, junto con los costos de produccin por toneladas de la tabla 6, llegamos a Costos de produccin = 7400X1 + 7500X2 + 7600X3 + 7650X4 78. Modelos de Programacin Lineal COSTOS DE INVENTARIO Una descomposicin similar produce un costo de inventario total como la suma de los costos de inventario durante cada uno de los cuatro meses. Como los niveles de inventario cambian solamente al final del mes, todos los inventarios al principio del mes incurren en un costo de $120 por tonelada para ese mes. Usando las variables I1, I2, I3, I4 llegamos a Costos de inventario = 120I1 + 120I2 + 120I3 + 120I4 Observe que I5 no se incluye en esta porcin porque el objetivo es minimizar los costos totales solamente en los siguientes 4 meses, e I5 incurre en costos durante el quinto mes. COSTOS DEL CAMBIO EN LA PRODUCCION Para determinar los costos del cambio en la produccin de un mes al siguiente, trabaje con un ejemplo especfico en el que, digamos X1 = 100 y X2 = 300. En este caso, existe un incremento de 300 100 = 200 toneladas de acero del mes 1 al mes 2. Por tanto, a un costo de $50 por tonelada de incremento, 79. Modelos de Programacin Lineal Costo del cambio en la produccin = (300 100) * 50 = $10 000 Usando este ejemplo, podra escribir la siguiente expresin general: Costo del cambio en la produccin = (X2 X1) * 50 Sin embargo, qu sucede si X1=300 y X2=100? Esto es, qu pasa si el nivel de produccin disminuye? En este caso, la expresin anterior resulta en un costo de (100 300) * 50= -$10 000, es decir, una ganancia de $10 000, que no tiene sentido. En vez de esto, a un costo de $30 por tonelada de decremento, la expresin correcta es Costo del cambio en la produccin = (300 100) * 30 = $6000 En general, cuando el nivel de produccin disminuye del mes 1 al mes 2, la expresin correcta es Costo del cambio en la produccin = (X1 X2) * 30 80. Modelos de Programacin Lineal combinando con las expresiones para resultados de incremento y decremento se obtienen los siguientes costos del cambio en la produccin del mes 1 al mes 2: Costo del cambio en la produccin = 50(X2 X1), si X2 X1 (incremento) 30(X1 X2), si X1 >X2 (decremento) Como los valores de X1 y X2 son por ahora desconocidos, la cuestin es cmo combinar estos dos casos en una sola expresin. Una forma de abordar esto es creando variables de decisin adicionales cuyos valores son precisamente las cantidades de produccin incrementada y decrementada de un mes al siguiente. Esto es, S1 = el nmero de toneladas de produccin incrementada en el mes 1 D1 = el nmero de toneladas de produccin decrementada en el mes 1 S2 = el nmero de toneladas de produccin incrementada en el mes 2 D2 = el nmero de toneladas de produccin decrementada en el mes 2 81. Modelos de Programacin Lineal S3 = el nmero de toneladas de produccin incrementada en el mes 3 D3 = el nmero de toneladas de produccin decrementada en el mes 3 S4 = el nmero de toneladas de produccin incrementada en el mes 4 D4 = el nmero de toneladas de produccin decrementada en el mes 4 Los valores de estas variables dependen de los niveles de produccin. Por ejemplo, cuando X2=300 y X1=100, usted desea que S2 sea 200 y D2, 0. Si X2=100 y X1=300, desea que S2 sea 0 y D2, 200. Las restricciones que aseguran las relaciones adecuadas entre estas variables se identifican en la siguiente seccin. Con estas nuevas variables, cuando S1 es positiva, D1 debe ser 0. De manera similar, cuando D1 es positiva, S1 debe ser 0. Por tanto, los costos del cambio en la produccin para el primer mes son 50S1+ 30D1. Por consiguiente, los costos totales del cambio en la produccin son: 82. Modelos de Programacin Lineal Costos del cambio = (costo del cambio en la produccin en el mes 1)+ en la produccin (costo del cambio en la produccin en el mes 2)+ (costo del cambio en la produccin en el mes 3)+ (costo del cambio en la produccin en el mes 4)+ = (50S1+ 30D1) + (50S2+ 30D2)+ (50S3+ 30D3) + (50S4+ 30D4) FUNCIN OBJETIVO COMPLETA La combinacin de los tres componentes de costo da como resultado la siguiente funcin objetivo global: Minimizar costos totales = 7400X1 + 7500X2 + 7600X3 + 7650X4 + 120I1 + 120I2 + 120I3 + 120I4 + 50S1 + 30D1 + 50S2 + 30D2 + 50S3 + 30D3 + 50S4 + 30D4 83. Modelos de Programacin Lineal Identificacin de las restricciones Aplicando la tcnica de agrupamiento debe llegar a identificar los siguientes seis grupos de restricciones: 1. Restricciones de inventario inicial y final para asegurar los adecuados niveles de inventario de inicio y fin 2. Restricciones de limitacin de produccin para asegurar que la produccin de cualquier mes dado no exceda de 4000 toneladas 3. Restricciones de equilibrio de inventario para asegurar la adecuada relacin entre las variables de produccin y las de inventario 4. Las restricciones de cambio en la produccin para asegurar la adecuada relacin entre las variables de produccin y las de cambio en la produccin 5. Restricciones de demanda para asegurar que se satisfagan las demandas cada mes 6. Restricciones lgicas para asegurar que todas las variables son no negativas 84. Modelos de Programacin Lineal RESTRICCIONES DE INVENTARIO INICIAL Y FINAL En palabras, las dos restricciones en este grupo son: 1. El nivel de inventario inicial es de 1000 toneladas 2. El nivel de inventario final debe ser al menos de 1500 toneladas Como I1 e I5 representan los inventarios inicial y final al principio y final del perodo de planeacin de 4 meses, respectivamente, estas restricciones son: I1 = 1000 (inventario de inicio) I5 1500 (inventario final) RESTRICCIONES DE LIMITACIN DE PRODUCCIN La produccin en cualquier mes no puede exceder las 4000 toneladas, as que las cuatro restricciones en este grupo son X1 4000 (lmite en el mes 1) X2 4000 (lmite en el mes 2) X3 4000 (lmite en el mes 3) X4 4000 (lmite en el mes 4)2m3bcpp