PROGRAMACIN INTRODUCCIN

LINEAL:

UNA

Programacin Lineal es una tcnica cuantitativa ampliamente aplicada en sistemas que presenten relaciones lineales, para utilizar los recursos escasos de la mejor manera posible.

La Programacin Lineal es un instrumento que se ocupa de los problemas de asignacin de recursos limitados a actividades simultaneas que compiten por ellos entre si. Utiliza un modelo matemtico para describir los diferentes problemas. Lineal significa que se requiere que todas las funciones matemticas que intervienen en el modelo sean lineales. La palabra programacin se deriva del hecho de que se establece una serie de pasos lgicos que permiten procesar diferentes problemas bajo un mismo principio o programa, para obtener un ptimo. Esto es, un algoritmo o programa de proceso que determina los pasos para llegar a un resultado que, en el caso de la programacin lineal intenta ser un ptimo. Tambin se puede definir como un procedimiento de resolucin de problemas desarrollado para ayudar a los administradores a tomar decisiones. Los Modelos Matemticos se dividen bsicamente en Modelos Deterministas (MD) o Modelos Estocsticos (ME). En el primer caso (MD) se considera que los parmetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocsticos, donde la totalidad o un subconjunto de los parmetros tienen una distribucin de probabilidad asociada. Los modelos estudiados en la Programacin Lineal son modelos deterministas. La formulacin correcta de los modelos de Programacin Lineal, parten de los siguientes supuestos: Proporcionalidad: Las cantidades de los insumos y de los productos asociados con cada actividad, son proporcionales al nivel de la actividad Aditividad: Para cada tem o recurso (bi) su uso debe ser igual a la suma de las cantidades que fluyen a las distintas variables de decisin (la cantidad de recurso o tem que se usa como insumo) menos la suma de las cantidades que fluyen fuera (la cantidad del recurso o tem que generan las variables de decisin como su producto). Asume las propiedades aditivas y multiplicativas. Por ejemplo: Si una unidad tipo 1 necesita 2 horas en la Mquina A y una unidad tipo 2 necesita 2 horas, entonces ambas necesitan 4 horas. Si una unidad tipo 3 necesita 1 hora en la mquina B, entonces 10 unidades necesitan 10 horas. Certidumbre: Los parmetros de costos, recursos, componentes tecnolgicos, son conocidos y constantes. Linealidad: El exponente de cada variable es 1 y no hay productos entre ellas. Linealidad asume que no pueden haber trminos as: X 1.X2 X3 2 a14.Log X4
1

Divisibilidad: Los valores que asumen las variables en la solucin final son mayores o iguales que cero.

Modelo Generalizado de Programacin Lineal La Funcin Objetivo del Modelo Lineal es la formulacin matemtica de una meta establecida y por lo tanto su valor final mide la efectividad lograda. Es una funcin lineal a ser maximizada o minimizada y tiene la siguiente forma general: Optimizar C1X1 + C2X2 + C3X3 + C4X4 +...................+ CnXn

Xj ,

simboliza matemticamente a las variables de decisin. Son los valores numricos que se determinan con la solucin del modelo y representan o estn relacionadas con una actividad o accin a tomar. Son los nicos valores desconocidos en el modelo y pueden existir en cualquier cantidad, desde 1 hasta n variables. Es decir, j vara desde 1 hasta n.

Cj,

matemticamente, simboliza el coeficiente de la variable j en la Funcin Objetivo. Son datos relevantes, insumos incontrolables ya conocidos. En la Funcin Objetivo representan la cantidad con la cual contribuye cada unidad de la variable j, al valor total deseado en el objetivo. Las restricciones, desde el punto de vista matemtico, son funciones lineales expresadas como igualdades o desigualdades, que limitan el valor de las variables de decisin a valores permisibles. Representan recursos, condiciones o requerimientos establecidos. Las restricciones del Modelo Lineal general tienen la forma siguiente: a11 X1 + a12 X 2 + a 13 X 3 + a14 X 4 + .................. + a 1n Xn < > = b1 a21 X1 + a22 X 2 + a 23 X 3 + a24 X 4 +.................. + a 2n Xn < > = b2 a31 X1 + a32 X 2 + a 33 X 3 + a34 X 4 +.................. + a 3n Xn < > = b3 ...... ...... am1 X1 + a m2 X 2 + a m3 X 3 + am4 X 4 +...............+ amn Xn < > = bm

aij,

matemticamente simboliza el coeficiente, en la restriccin i, de las variable j. El subndice i indica el recurso, requerimiento o condicin cuya limitacin se est expresando; j indica la variable correspondiente. Cuando la limitacin es de un recurso i, estos coeficientes representan la cantidad del recurso total limitado i, que es utilizada en cada unidad de la variable j. Cuando la limitacin es de un requerimiento o condicin i, representan la cantidad del requerimiento o condicin i limitada, que aporta cada unidad de la variable j, al requerimiento o condicin total
2

establecida. Son, por ello, valores unitarios, al igual que los coeficientes de las variables en la Funcin Objetivo.

b i,

matemticamente constituye el lado derecho de la restriccin i. Representa la cantidad total disponible del recurso limitado i, o la cantidad total de un requerimiento o condicin i establecida. Puede existir cualquier cantidad de restricciones por lo tanto i puede variar desde 1 hasta m.

Xj > 0

es una restriccin de no negatividad de las j variables, la cual se le considera siempre presente como una condicin natural en el Modelo Lineal General.

Pautas y Comentarios para la Formulacin de Modelos En la conversin de modelos verbales a modelos formales, ser muy til describir primero con palabras un modelo que corresponda al problema dado. Es decir, se puede proceder de la siguiente forma: 1. Identificar las variables de decisin: Con frecuencia, una cuidadosa lectura del contenido del problema le revelar que las variables de decisin y el objetivo se le dan en la forma exacta que necesita. Es imperativo e importante que estn definidas en forma correcta sus variables de decisin. En ocasiones encontrar que hay varias elecciones posibles. Una gua til es hacerse a si mismo la pregunta: A qu debo darle respuesta? La respuesta a esta pregunta le ayudar a llegar a identificar correctamente las variables de decisin. 2. Despus expresar el objetivo en palabras. Luego escriba la funcin objetivo, que funcin de utilidad o costo est expresando el problema. Para seleccionar qu funcin objetivo (F.O.) debe elegirse se toma en cuenta lo siguiente: a) Si vamos a encontrar situaciones en las cuales tendremos solo costos ya sea de materia prima, costo de mano de obra, costo de uso de mquina, costos de transporte, costos de depreciacin ,etc. esto indica que indudablemente la F.O. ser de MINIMIZACION. b) Si el enunciado solo da datos econmicos de ganancia, precio de venta o dinero a recibir por unidad producida la F.O. ser de MAXIMIZACION. c) Si el enunciado nos da al mismo tiempo costos y ganancias restaremos de la siguiente manera:

GANANCIAS - COSTOS = UTILIDAD, la que tendr como F.O. MAXIMIZACION.

d) Si no nos dan ningn dato econmico y solo se da tiempos, el tiempo se minimiza, si nos da solo produccin, la produccin se ha de maximizar, si el modelo corresponde a contratar al personal, la funcin objetivo se minimiza. 3. Exprese cada restriccin; al hacer esto, ponga cuidadosa atencin en si la restriccin es un requerimiento de la forma (mayor igual que, al menos, por lo menos, como mnimo), una limitacin de la forma (menor igual que, no mayor que, como mximo), = (igual a, exactamente igual a). Aprendiendo a Formular Modelos
3

A continuacin se presentan algunos ejemplos de formulacin que le servirn para cimentar su habilidad al traducir problemas del mundo real a modelos matemticos. De igual forma se presenta la primera metodologa de solucin: el Mtodo Grfico. Esta transicin, o modo en que se ha de elaborar el modelo, la forma en que se definir las variables y se formularn las restricciones y la funcin objetivo es de primordial importancia. Intente resolver los siguientes problemas por si mismo. Formlelos con la rapidez que le sea posible. No introduzca restricciones adicionales o matices lgicos o datos imaginarios que en su opinin podran hacer ms realista el modelo. Por ejemplo, no se preocupe por lo que ocurra la semana siguiente si el problema nunca se refiere a la semana siguiente. Los problemas que se muestran han sido escogidos para facilitarle el desarrollo del aprendizaje de la formulacin. Para lograr esto y que pueda comprobar su trabajo y calibrar su progreso dentro del contexto descrito, la formulacin correcta, debe carecer por completo de ambigedad. En otras palabras, que haya una respuesta correcta. Ms tarde, cuando tenga experiencia, la amplitud de las dudas en la interpretacin y las sutilezas del mundo real sern mayores.

Debido a que el tema de la formulacin es tan importante y como la prctica es el nico camino para dominarlo, se recomienda hacer un nmero de problemas grande. Como ltimo consejo: No lea simplemente el problema y despus vaya de inmediato a la solucin. Esa sera la mejor forma de engaarse a si mismo sobre lo que ha comprendido. No lea la solucin hasta que est seguro de haber solucionado en forma correcta el problema por si mismo o est totalmente convencido que se encuentra en un callejn sin salida. Problema No. 1 - Problema de Produccin La compaa Sigma produce bibliotecas y escritorios para los cuales se ha establecido un precio de venta por unidad de $9000 y $10000 respectivamente. Para la produccin de dichos artculos la compaa cuenta con una disponibilidad mensual de 700 metros de madera, 800 metros de tubo y 900 metros de pliegos de papel de lija. Qu cantidad de bibliotecas y escritorios se debe fabricar mensualmente si se sabe que una biblioteca consume 7 metros de madera, 10 metros de tubo y 6 pliegos de papel de lija; mientras que para producir un escritorio se requieren 10 metros de madera, 8 metros de tubo y 15 pliegos de papel de lija? Realizamos un resumen de la informacin presentada:

Solucin. Variables de Decisin: Nos respondemos a la pregunta A qu debemos darle solucin? X1 = Cantidad de bibliotecas a fabricar por mes. X2 = Cantidad de escritorios a fabricar por mes. Funcin Objetivo: Max Z = 9000 X1 + 10000 X2 Restricciones: 7 X1 + 10 X2 < 700 Disponibilidad de metros de madera. 10 X1 + 8 X2 < 800 Disponibilidad de metros de tubo. 6 X1 + 15 X2 < 900 Disponibilidad de pliegos de papel de lija. X1, X2 > 0 En total tenemos 3 restricciones. La restriccin de no negatividad, no se cuenta dentro del conjunto de restricciones, pero se tiene en cuenta debido a su importancia en la limitacin de soluciones positivas.

Problema No. 2 - Problema de Produccin Una industria vincola produce vino y vinagre. El doble de la produccin de vino es siempre menor o igual que la produccin de vinagre ms cuatro unidades. Por otra parte, el triple de la produccin de vinagre sumado con cuatro veces la produccin de vino se mantiene siempre menor o igual a 18 unidades. Halla el nmero de unidades de cada producto que se deben producir para alcanzar un beneficio mximo, sabiendo que cada unidad de vino deja un beneficio de S/8 y cada unidad de vinagre de S/2. Solucin. Vino $8 / unidad Vinagre $2 / unidad

Benefici o

Variable de decisin: Xi= Nmero de unidades producidas de i (i=Vino, Vinagre=1,2) a elaborar. Funcin Objetivo: Maximizar Z = 8 X1 + 2 X2
5

Restricciones: El doble de la produccin de vino es siempre menor o igual que la produccin de vinagre ms cuatro unidades: 2 X1 < X2 + 4 El triple de la produccin de vinagre sumado con cuatro veces la produccin de vino se mantiene siempre menor o igual a 18 unidades. 3 X2 + 4 X1 < 18 Modelo Lineal Maximizar Z = 8 X1 + 2 X2 Sujeto a: 2 X1 < X2 + 4 3 X2 + 4 X1 < 18 No negatividad: Xi > 0

Problema No. 3 - Problema de Inversin Una persona tiene $ 500.000 para invertir en dos tipos de acciones A y B. El tipo A tiene bastante riesgo con un inters anual del 10% y el tipo B es bastante seguro con un inters anual del 7%. Decide invertir como mximo $ 300.000 en A y como mnimo $ 100.000 en B, e invertir en A por lo menos tanto como en B. Cmo deber invertir sus $ 500.000 para maximizar sus intereses anuales? Solucin.
Acciones A Inters Inversin Dinero 0,10 Mximo $ 300.000 Acciones B 0,07 Mnimo $100.000 Disponibilid ad

$ 500.000

Variable de decisin: Xi= Nmero de acciones de tipo i (i = A, B =1, 2) a comprar. Funcin objetivo: Maximizar intereses Maximizar Z = 0,10 X1+ 0,07 X2
6

Restricciones: Dinero mximo a invertir en acciones tipo A X1 < $300.000 Dinero mnimo a invertir en acciones tipo B X2 > $100.000 Invertir en A por lo menos tanto como en B X1 > X2 Dinero disponible X1 + X2 < $500.000 No negatividad: Xi > 0

Problema No. 4 - Problema de Mezcla Juan Carlos Rodrguez, un antiguo entrenador de grupos de ftbol, se ha convertido en avicultor. Desea alimentar a sus animales en forma tal que se cubran sus necesidades de nutricin a un costo mnimo. Juan est estudiando el uso de maz, soya, avena y alfalfa. En la figura se muestra la informacin diettica importante por libra de grano (por ejemplo, 1 libra de maz proporciona 15 miligramos de protena). Elabore un modelo de Programacin Lineal para determinar la mezcla diettica que satisfar los requisitos diarios a un costo mnimo. Nutrientes por libra de grano:
Nutrien te (mg.) Protena Calcio Grasas Alfalf a 7 45 25 4000 $ 90 Necesidades (mg.) Mnimo 50 Mnimo 150 Mximo 120 y Mnimo 25 Mnimo 5000

Maz Soya Avena 15 40 20 850 $ 70 30 10 50 1500 $ 45 15 40 8 1200 $ 40

Ejercicios

Caloras Costo por libra

Solucin. Variables de Decisin: Xi= Nmero de libras a comprar de i (i= Maz, soya, avena, alfalfa =1, 2, 3,4). Funcin Objetivo: Minimizar costos Minimizar Z =70 X1 + 45 X2 + 40 X3 + 90 X4 Restricciones: Protenas: 15 X1 + 30 X2 + 15 X3 + 7 X4 > 50 Calcio: 40 X1 + 10 X2 + 40 X3 + 45 X4 > 150 Grasas: 20 X1 + 50 X2 + 8 X3 + 25 X4 > 25 20 X1 + 50 X2 + 8 X3 + 25 X4 < 120 Caloras: 850 X1 + 1500 X2 + 1200 X3 + 4000 X4 > 5000 No negatividad: Xi > 0

Problema No. 5 - Problema de Encuestas Para realizar una encuesta por telfono, un grupo de investigacin de mercado necesita comunicar por lo menos a 150 esposas, 120 maridos, 100 hombres adultos solteros y 110 mujeres adultas solteras. Cuesta $2 realizar una llamada telefnica durante el da, y $5 realizar una llamada telefnica durante la noche (debido a mayores costos laborales). Estos resultados se muestran en la tabla. Se pueden realizar a lo ms la mitad de estas llamadas en la noche, por disponer de un nmero limitado de empleados. Formule un modelo de Programacin Lineal que minimice los costos para completar la encuesta.
Persona que Contesto Esposa Marido Soltera Soltero Nadie Porcentaje de Llamadas Diurnas 30 10 10 10 40 Porcentaje de Llamadas Nocturnas 30 30 15 20 5

Solucin. Variables de decisin:

8

Xij= Nmero de llamadas realizadas en el horario i (i=diurno/nocturno=1,2)

Funcin Objetivo: Minimizar costos Minimizar Z = 2 X1 + 5 X2 Restricciones: Esposas encuestadas: 0.30 X1 + 0.30 X2 > 150 Maridos encuestados: 0.10 X1 + 0.30 X2 > 120 Solteros encuestados: 0.10 X1 + 0.15 X2 > 100 Solteras encuestados: 0.10 X1 + 0.20 X2 > 110 Realizar a lo ms la mitad de estas llamadas en la noche X2 < (1/2) (X1 + X2) No negatividad: Xi > 0

Bibliografa Los problemas y la informacin presentados en este documento fueron tomados de: HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introduccin a la investigacin de operaciones. Sexta edicin. Editorial McGraw-Hill Interamericana, Mxico. 1.997. NAMAKFOROOSH, Mamad Naghi. Investigacin de operaciones . Editorial Limusa. TAHA, Handy A. Investigacin de operaciones: Una introduccin. Editorial Prentice Hall, Mxico. Sexta edicin 1.998 CHEDIAK, Francisco. Investigacin de Operaciones. JAVEZ, Francisco. Formulacin de Problemas Lineales. Apuntes de Clase.