Geometra de programacin Lineal

Universidad Nacional de Ingeniera

Investigacin de Operaciones IProgramacin Lineal y Solucin GrficaIng. Luis Medina AquinoX2X1R1R2R3

Introduccin a la Programacin LinealExisten problemas de decisin administrativos que pueden ser resueltos a travs de un modelo matemtico llamado programacin lineal. Por ejemplo:1) PRODUCCION2) MARKETING3) FINANZAS Juan se dedica a la compra y venta de naranja y papaya. Todos los das temprano en la maana visita a su proveedor de frutas en el mercado mayorista y hace las compras del da. El da anterior recibe los pedidos de sus clientes y esta suma 600 kilos de papaya y 1200 kilos de naranja. ProblemaProblema Juan lleva su camioneta para el transporte cuya capacidad de carga es de 1600 kilos. Cuntos kilos de cada fruta debe comprar Juan para maximizar los beneficios?

Se tienen los siguientes precios y costos por kilo de fruta :Precio de compra al por mayor x KgPrecio de venta al minorista x KgUtilidad por KgPapayaS/. 1.30S/. 1.60S/. 0.30NaranjaS/. 1.00S/. 1.20S/. 0.20

Cuntos kilos de papaya y naranja debe comprar Juan para obtener la Mxima Utilidad?X1 = ??X2 = ??X1 < 600 kgX2 < 1200 kgX1 + X2 < 1600 kgPrimero se debe cargar a la camioneta con aquel que tiene mas utilidad por kilo.Capacidad

Utilidad por kilo: S/. 0.30X1 < 600 kgX2 < 1200 kgX1 + X2 < 1600 kgSe debe comprar 600 kg. de papaya y 1000 kg. de naranja, su utilidad ser S/. 380. Utilidad por kilo: S/. 0.20Modelo de Programacin LinealUn modelo de programacin lineal busca el objetivo de maximizar o minimizar una funcin lineal, sujeta a un conjunto de restricciones lineales.Modelo de Programacin LinealUn modelo de programacin lineal esta compuesto de lo siguiente:* Un conjunto de variables de decisin* Una funcin objetivo* Un conjunto de restricciones

1) Formulacin del ProblemaDefinicin de las Variables de Decisin x1 = Cantidad, en kilos, de papaya que se debe comprar. x2 = Cantidad, en kilos, de naranja que se debe comprar.1) Formulacin del ProblemaFuncin Objetivo Maximizar la utilidad total de los dos productos:Maximizar Z = 0.30 x1 + 0.20 x2

1) Formulacin del ProblemaRestricciones Cantidad mxima de Papaya < 600 kilos.x1 < 600 Cantidad mxima de Naranja < 1200 kilos.x2 < 1200 Carga mxima de la camioneta < 1600 kilos.x1 + x2 < 16001) Formulacin del ProblemaMaximizar Z = 0.30 x1 + 0.20 x2 x1 < 600 x2 < 1200 x1 + x2 < 1600 x1, x2 > 0Procedimiento de Solucin Grfica en Problemas de PL con dos variables1)Establecer la formulacin del problema Procedimiento de Solucin Grfica en Problemas de PL con dos variables1)Establecer la formulacin del problema 2)Graficar en el plano cartesiano (X,Y) las restricciones del tipo >, < =, como si fueran rectas.2) Graficar RestriccionesMax Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)X1X2(0,0)Cada punto en este cuadrante no negativo esta asociado con una especifica alternativa de solucin.16Page N2) Graficar RestriccionesMax Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)X1X2(0,0)17Page N2) Graficar RestriccionesMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)R118Page N2) Graficar RestriccionesMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)R119Page N2) Graficar RestriccionesMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)(0,1200)R1R220Page N2) Graficar RestriccionesMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)(0,1200)R1R221Page N2) Graficar RestriccionesMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)(0,1200)R2R122Page N2) Graficar RestriccionesMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)(0,1200)R3R2R1(1600,0)(0,1600)23Page N2) Graficar RestriccionesMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)(0,1200)R3R2R1(1600,0)(0,1600)(400,1200)(600,1000)24Page NProcedimiento de Solucin Grfica en Problemas de PL con dos variables1)Establecer la formulacin del problema 2)Graficar en el plano cartesiano (X,Y) las restricciones del tipo >, < =, como si fueran rectas.3)Ubicar el espacio de la solucin factible (regin factible), el cual est dado por el rea comn a todas las restricciones. 3) Ubicar Regin FactibleMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta 1) 2 P2 < 12 (Planta 2) 3 P1 + 2 P2 < 18 (Planta 3) P1, P2 > 0 (no negatividad)X1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)(0,1200)R3R2R1(400,1200)(600,1000)Regin factible es el conjunto de puntos que satisface todas las restricciones simultneamente. Existen infinitos puntos factibles (soluciones).26Page N3) Ubicar Regin FactibleX1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)(0,1200)(400,1200)(600,1000)ABCDESe llaman puntos extremos a los vrtices de la regin de factibilidad.Los valores que optimizan la funcin objetivo siempre se encuentran en uno de los puntos extremos.27Page NProcedimiento de Solucin Grfica en Problemas de PL con dos variables1)Establecer la formulacin del problema 2)Graficar en el plano cartesiano (X,Y) las restricciones del tipo >, < =, como si fueran rectas.3)Ubicar el espacio de la solucin factible (regin factible), el cual est dado por el rea comn a todas las restricciones.4)Obtener la solucin ptima.4) Obtener Solucin OptimaX1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2En la regin factible(0,1200)(400,1200)(600,1000)ABCDE0.300.20Pendiente de la funcin objetivoSe debe dibujar el contorno de la funcin objetivo (lnea iso-beneficio) mediante rectas paralelas, en cada vrtice, segn la relacin: X2 = 1.5 X1 + K29Page N4) Obtener Solucin OptimaX1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2En la regin factible(0,1200)(400,1200)(600,1000)ABCDE Z1 = 0.30 (0) + 0.20 (0) = 0Pendiente de la funcin objetivo Z1 0.300.2030Page N4) Obtener Solucin OptimaX1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2En la regin factible(0,1200)(400,1200)(600,1000)ABCDE Z1 = 0.30 (0) + 0.20 (0) = 0 Z2 = 0.30 (600) + 0.20 (0) = 180Pendiente de la funcin objetivo Z1 0.300.20 Z2 31Page N4) Obtener Solucin OptimaX1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2En la regin factible(0,1200)(400,1200)(600,1000)ABCDE Z1 = 0.30 (0) + 0.20 (0) = 0 Z2 = 0.30 (600) + 0.20 (0) = 180 Z3 = 0.30 (0) + 0.20 (1200) = 240Pendiente de la funcin objetivo Z1 0.300.20 Z2 Z3 32Page N4) Obtener Solucin OptimaX1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2En la regin factible(0,1200)(400,1200)(600,1000)ABCDE Z1 = 0.30 (0) + 0.20 (0) = 0 Z2 = 0.30 (600) + 0.20 (0) = 180 Z3 = 0.30 (0) + 0.20 (1200) = 240 Z4 = 0.30 (400) + 0.20 (1200) = 360Pendiente de la funcin objetivo Z1 0.300.20 Z2 Z3 Z4 33Page N4) Obtener Solucin OptimaX1X2(0,0) (600,0)Max Z = 0.30 X1 + 0.20 X2En la regin factible(0,1200)(400,1200)(600,1000)ABCDE Z1 = 0.30 (0) + 0.20 (0) = 0 Z2 = 0.30 (600) + 0.20 (0) = 180 Z3 = 0.30 (0) + 0.20 (1200) = 240 Z4 = 0.30 (400) + 0.20 (1200) = 360 Z5 = 0.30 (600) + 0.20 (1000) = 380 Z1 Z2 Z3 Z4 Z5 34Page N4) Obtener Solucin OptimaX1X2 Max Z = 0.30 X1 + 0.20 X2En la regin factible(600,1000)ABCDE Z1 = 0.30 (0) + 0.20 (0) = 0 Z2 = 0.30 (600) + 0.20 (0) = 180 Z3 = 0.30 (0) + 0.20 (1200) = 240 Z4 = 0.30 (400) + 0.20 (1200) = 360 Z5 = 0.30 (600) + 0.20 (1000) = 380Solucin ptima: Se encuentra en el punto C de las restricciones activas (R1 y R3)R1R3R235Page NPrograma Lineal sin Solucin OptimaLa funcin objetivo es no acotado: Ocurre cuando el objetivo puede crecer infinitamente (maximizacin)No factible: Ocurre cuando en el modelo no hay ningn punto de factible36Page NModelo General de Programacin LinealMaximizar (o Minimizar) Z = C1 X1 + C2 X2 +....+ Cn XnSujeto a:a11 X1 + a12 X2 + a13 X3 +....+ a1n Xn < b1:ak1 X1 + ak2 X2 + ak3 X3 +....+ akn Xn > bk:am1 X1 + am2 X2 + am3 X3 +....+ amn Xn = bm

X1, X2, X3,...., Xn > 0Se define las variables de decisin: X1, X2, X3,...., Xn PROBLEMA Un herrero con 80 kgs. de acero y 120 kgs. de aluminio quiere hacer bicicletas de paseo y de montaa, cuya utilidad son, respectivamente a S/.60 y S/.40 cada una. Para la de paseo emplear 1 kg. de acero y 3 kg. de aluminio, y para la de montaa 2 kg. de ambos metales. Como mximo se puede vender 30 bicicletas de paseo. Cuntas bicicletas de paseo y de montaa vender?

PROBLEMADefinicin de las Variables de Decisin x1 = Cantidad, en unidades, de bicicletas de paseo que debe producir. x2 = Cantidad, en unidades, de bicicletas de montaa que debe producir.PROBLEMAFuncin Objetivo Maximizar la utilidad total de los dos productos:Maximizar Z = 60 x1 + 40 x2

Restricciones Cantidad mxima de acero < 80 kilos.1 x1 + 2 x2 < 80 Cantidad mxima de aluminio < 120 kilos. 3 x1 + 2 x2 < 120Demanda mxima bicicletas de paseo < 30 bici-x1 < 30PROBLEMA

SOLUCIN GRFICADecisin Producir vs. Subcontratar:Caso NOKIA CorporationNOKIA es un productor lider de celulares.La empresa ha recibido un pedido de $750,000. Modelo 1 Modelo 2Modelo 3Cantidad ordenada3,0002,000900Horas de equipamiento/unid21.53Horas de ensamblado/unid121Costo unitario de producir$50$83$130Costo unitario subcontrata$61$97$145

La compaa tiene 10,000 horas de capacidad en equipamiento y 5,000 horas de capacidad en ensamblado disponibles.Definiendo las Variables de Decision P1 = Cantidad del celular modelo 1 que se produce en la empresa P2 = Cantidad del celular modelo 2 que se produce en la empresa P3 = Cantidad del celular modelo 3 que se produce en la empresa S1 = Cantidad del celular modelo 1 que se subcontrata S2 = Cantidad del celular modelo 2 que se subcontrata S3 = Cantidad del celular modelo 3 que se subcontrataDefiniendo la Funcin ObjetivoMinimizar el costo total de cumplir la orden.Minimizar:50 P1 + 83 P2 + 130 P3 + 61 S1 + 97 S2 + 145 S3Definiendo las RestriccionesRestricciones de DemandaP1 + S1 = 3,000} modelo 1P2 + S2 = 2,000} modelo 2P3 + S3 = 900} modelo 3Restricciones de Recursos2P1 + 1.5P2 + 3P3 < 10,000 } Equipamiento1P1 + 2.0P2 + 1P3 < 5,000 } EnsambladoCondicin de no negatividadP1, P2, P3, S1, S2, S3 > 0Un Problema de Inversin:Retirement Planning Services, Inc.Un cliente desea invertir $750,000 en los siguientes bonosAos deCompaaRetorno Vencto. RatingAcme Chemical8.65%111-ExcelenteDynaStar9.50%103-BuenoEagle Vision10.00%64-RegularMicro Modeling8.75%101-ExcelenteOptiPro9.25%73-BuenoSabre Systems9.00%132-Muy BuenoRestricciones de InversinNo ms del 25% puede ser invertido en cualquier compaa.Al menos 50% debera ser invertido en bonos a largo plazo (vencimiento mayor o igual de 10 aos).No ms del 35% puede ser invertido en DynaStar, Eagle Vision, y OptiPro.Definiendo las Variables de DecisinX1 = Monto de dinero a invertir en Acme ChemicalX2 = Monto de dinero a invertir en DynaStarX3 = Monto de dinero a invertir en Eagle VisionX4 = Monto de dinero a invertir en MicroModelingX5 = Monto de dinero a invertir en OptiProX6 = Monto de dinero a invertir en Sabre SystemsDefiniendo la Funcin ObjetivoMaximizar el retorno anual total invertidoMAXIMIZAR: 0.0865 X1 + 0.095 X2 + 0.10 X3 + 0.0875 X4 + 0.0925 X5 + 0.09 X6Definiendo las RestriccionesMonto total a invertirX1 + X2 + X3 + X4 + X5 + X6 = 750,000 No ms del 25% en alguna compaaXi < 187,500, para todo i Restriccin 50% en inversin a largo plazoX1 + X2 + X4 + X6 > 375,000Restriccin del 35% en DynaStar, Eagle Vision, and OptiPro.X2 + X3 + X5 < 262,500Condicin de no negatividadXi > 0 para todo i Problema de Transporte:Caso Cosmic ComputerEn la tabla se muestra el costo del embarque de una microcomputadora desde la planta de ensamblaje hasta cada una de las distintas tiendas minoristas.S.DIEGOBARSTOWTUCSONDALLASSan Francisco5326Los Angeles47810Phoenix6538PLANTASTIENDASDiagrama de redesSe puede esquematizar el problema a fin de identificar las variables y plantear el modelo.San Francisco1700D1S2S3D2D3D4S1Los Angeles2000Phoenix1700San Diego1700Barstow1000Tucson1500Dallas12005463783810623Definiendo las Variables de DecisinXij = # de microcomputadoras por embarcar desde la planta i (i=1,2,3) hasta el destino j (j=1,2,3,4). Por ejemplo:X13 = # de microcomputadoras por embarcar de la planta de ensamblaje 1 (San Francisco) a la tienda 3 (Tucson)Definiendo la Funcin ObjetivoMinimizar los costos de embarque desde todas las plantas a todas las tiendas.Min( 5 X11 + 3 X12 + 2 X13 + 6 X14) + ( 4 X21 + 7 X22 + 8 X23 + 10 X24) +( 6 X31 + 5 X32 + 3 X33 + 8 X34)Definiendo las RestriccionesEl embarque total de cada planta no debe exceder su capacidad.X11 + X12 + X13 + X14 < 1700 (SF)X21 + X22 + X23 + X24 < 2000 (LA)X31 + X32 + X33 + X34 < 1700 (PH)El embarque total recibida por cada tienda debe satisfacer su demanda. X11 + X21 + X31 = 1700 X12 + X22 + X32 = 2000 X13 + X23 + X33 = 1500 X14 + X24 + X34 = 1200El embarque debe ser un nmero entero no negativo.Solucin Usando Hoja de Clculo Excel Los libros americanos en programacin lineal utilizan el software Solver, que es una herramienta de la hoja de clculo Excel de Microsoft, para hallar la solucin de un programa lineal.Solucin Usando Hoja de Clculo Excel En el men Herramientas, aparece el comando Solver. Si no aparece, se deber instalar el complemento o macro automtica Solver. Maximizar Z = 0.30 x1 + 0.20 x2 (Beneficio Total) s.a. 1 x1 + 0 x2 < 600 (Cantidad mxima de Papaya) 0 x1 + 1 x2 < 1200 (Cantidad mxima de Naranja) 1 x1 + 1 x2 < 1600 (Carga mxima de la camioneta) x1, x2 > 0 (Condicin de no negatividad)Solucin del modelo con Hoja de Clculo Excel

Aqu se colocan los coeficientes de la funcin objetivoAqu se colocan los coeficientes de las restriccionesSe coloca el tipo de restriccin como referenciaAqu se colocan los coeficientes del lado derecho de las restricciones

Los valores iniciales de X1 y X2 son cero y se colocan en las celdas B4 y C4

En la celda E4 se coloca la frmula de la funcin objetivo Z = 0.3 X1 + 0.2 X2 B3*B4+C3*C4Se ingresa en la celda D7 la frmula:=SUMAPRODUCTO(B$4:C$4,B7:C7)y es equivalente a =B4*B7+C4*C7Se copia la frmula de la celda D7

Seleccione del men Herramientas / Solver... Aparecer el cuadro de dilogo Parmetros de Solver, en la que ingresaremos los datos.

MUCHAS GRACIASIng. Luis Medina AquinoX2X1R1R2R3