programacion lineal.docx

22
PROGRAMACIÓN LINEAL La programación lineal (PL) es una herramienta para resolver problemas de optimiza !eorge "antzig creó un m#todo e$icaz el algoritmo simple% para resolver problemas de programación lineal. & partir del surgimiento del algoritmo simple% se ha usado e lineal para resolver problemas de optimización en industrias tan diversas educación el petróleo ' el transporte. En una encuesta realizada por la revista empresas el + , de las -ue contestaron di eron -ue hab/an utilizado la programac Ejemplo de un problema de programación lineal 0oodcarving nc. de !iapetto $abrica dos tipos de uguetes de madera2 3oldados ' un soldado a 57 dólares ' se usan 1* dólares de materia prima. 6ada soldado -ue se los costos variables de mano de obra ' los costos generales en 14 dólares. 3e vend dólares ' se usan 9 dólares de materia prima. 6ada tren producido aumenta los cost mano de obra ' los costos generales en 1* dólares. La producción de soldados ' tre necesita dos tipos de traba o especializado2 carpinter/a ' acabado. n soldado re acabado ' 1 hora de carpinter/a. n tren re-uiere 1 hora de acabado ' 1 hora de ca semana !iapetto puede conseguir toda la materia prima -ue necesita pero solament horas de acabado ' +* de carpinter/a. La demanda de los trenes no tiene l/mite pe m8s 4* soldados semanalmente. !iapetto -uiere ma%imizar su ganancia semanal (ingre ormule ' resuelva un modelo matem8tico para la situación de !iapetto -ue se pueda utilizar para ma%imizar su ganancia semanal. Podemos resumir la in$ormación en la siguiente tabla2 Tipo de Juguete Precio de venta (dólares) Costo materia prima Costos variables de mano de obra y generales Horas de Acabado Horas de carpintería Ganancia 3oldado 57 1* 14 5 1 : ren 51 9 1* 1 1 5 "isponibilidad 1** +* 3ean x 1 2 La cantidad de soldados a producir x 52 La cantidad de trenes a producir El modelo es2 * * 4* +* 1** 5 a. s. 5 : ;a%. 5 1 1 5 1 5 1 5 1 + + + = x x x x x x x x x z Características comunes a todos los problemas de PL . Variables de decisión . Empezamos de$iniendo las variables de decisión pertinentes. En cu problema de PL las variables de decisión tienen -ue representar completamente l se deben tomar. 1

Upload: sebastian-tambo

Post on 08-Oct-2015

122 views

Category:

Documents


3 download

TRANSCRIPT

PROGRAMACION LINEAL

PROGRAMACIN LINEAL

La programacin lineal (PL) es una herramienta para resolver problemas de optimizacin. En 1947, George Dantzig cre un mtodo eficaz, el algoritmo simplex, para resolver problemas de programacin lineal. A partir del surgimiento del algoritmo simplex, se ha usado en la programacin lineal para resolver problemas de optimizacin en industrias tan diversas como la banca, la educacin, el petrleo y el transporte. En una encuesta realizada por la revista Fortune, de 500 empresas, el 85% de las que contestaron dijeron que haban utilizado la programacin lineal.

Ejemplo de un problema de programacin linealWoodcarving, Inc. de Giapetto, fabrica dos tipos de juguetes de madera: Soldados y Trenes. Se vende un soldado a 27 dlares y se usan 10 dlares de materia prima. Cada soldado que se produce aumenta los costos variables de mano de obra y los costos generales en 14 dlares. Se vende un tren a 21 dlares y se usan 9 dlares de materia prima. Cada tren producido aumenta los costos variables de mano de obra y los costos generales en 10 dlares. La produccin de soldados y trenes de madera necesita dos tipos de trabajo especializado: carpintera y acabado. Un soldado requiere 2 horas de acabado y 1 hora de carpintera. Un tren requiere 1 hora de acabado y 1 hora de carpintera. Cada semana, Giapetto puede conseguir toda la materia prima que necesita, pero solamente dispone de 100 horas de acabado y 80 de carpintera. La demanda de los trenes no tiene lmite, pero se venden a lo ms 40 soldados semanalmente. Giapetto quiere maximizar su ganancia semanal (ingresos - costos). Formule y resuelva un modelo matemtico para la situacin de Giapetto que se pueda utilizar para maximizar su ganancia semanal.

Podemos resumir la informacin en la siguiente tabla:

Tipo de JuguetePrecio de venta (dlares)Costo materia primaCostos variables de mano de obra y generalesHoras de AcabadoHoras de carpinteraGanancia

Soldado271014213

Tren21910112

Disponibilidad10080

Sean x1: La cantidad de soldados a producirx2: La cantidad de trenes a producir

El modelo es:

Caractersticas comunes a todos los problemas de PL.

Variables de decisin. Empezamos definiendo las variables de decisin pertinentes. En cualquier problema de PL, las variables de decisin tienen que representar completamente las decisiones que se deben tomar.

Funcin objetivo. En cualquier problema de PL, la persona que toma la decisin quiere maximizar (generalmente el ingreso o las ganancias) o minimizar (por lo general los costos) alguna funcin de las variables de decisin. La funcin que hay que maximizar o minimizar se llama funcin objetivo.El coeficiente de una variable en la funcin objetivo se llama coeficiente de la funcin objetivo de la variable, el coeficiente de la funcin objetivo de cada variable es simplemente la contribucin de la variable a la ganancia de la compaa.

Restricciones. Para que una restriccin sea razonable, todos los trminos en la restriccin tienen que tener las mismas unidades. De otra manera se sumaran manzanas con naranjas, y la restriccin no tendra ningn sentido. Los coeficientes de las variables de decisin en las restricciones se llaman coeficientes tecnolgicos. Esto se debe a que los coeficientes tecnolgicos reflejan a menudo la tecnologa utilizada para producir diferentes productos. El nmero a cada lado derecho de la restriccin se llama lado derecho de la restriccin. Muchas veces el lado derecho de una restriccin representa la cantidad disponible de un recurso.

Restricciones de signo (o de no negatividad). Para completar la formulacin de un problema de PL, hay que contestar la siguiente pregunta para cada variable de decisin: puede tomar la variable de decisin valores no negativos solamente, o se le pueden permitir valores tanto positivos como negativos?Si una variable de decisin xi solamente toma valores no negativos, aadimos la restriccin de signo xi 0. Si una variable de decisin xi puede tomar valores positivos y negativos (o inclusive ser cero), decimos que xi no tiene restriccin de signo, se abreviar SRS sin restriccin de signo.

DEFINICINUn problema de programacin lineal (PL) es un problema de optimizacin, para el cual hacemos lo siguiente:1. Tratamos de maximizar (o minimizar) una funcin lineal de variables de decisin. La funcin que se pretende maximizar o minimizar se llama la funcin objetivo.2. Los valores de las variables de decisin tienen que satisfacer un conjunto de restricciones. Cada restriccin tiene que ser una ecuacin lineal o una desigualdad lineal.3. Hay una restriccin de signo para cada variable. Para cualquier variable xi, la restriccin de signo especifica que xi tiene que ser no negativo o que xi puede ser una variable sin restriccin de signo (SRS).

SUPOSICIONES DE UN PL

De proporcionalidad y aditividadEl hecho de que la funcin objetivo de un PL tiene que ser una funcin lineal de las variables de decisin, tiene dos implicaciones:

1. La contribucin de cada variable de decisin a la funcin objetivo es proporcional al valor de la variable de decisin.2. La contribucin a la funcin objetivo por parte de cualquier variable es independiente de los valores de las otras variables de decisin.

De manera anloga, el hecho de que cada restriccin de PL tiene que ser una desigualdad o igualdad lineal, tiene dos implicaciones:

1. El aporte de cada variable al lado izquierdo de cada restriccin es proporcional al valor de la variable.2. La contribucin de una variable al lado izquierdo de cada restriccin es independiente de los valores de las otras variables.El primer punto dado cada listado, se llama suposicin de proporcionalidad de la programacin lineal. El punto 2 de la primera lista afirma que el valor de la funcin objetivo es la suma de las contribuciones de las variables individuales, y el punto 2 de la segunda lista indica que el lado izquierdo de cada restriccin es la suma de las contribuciones de cada variable. Por tal razn, el segundo punto de cada listado se llama Suposicin de aditividad de la programacin lineal.

De divisibilidadLa suposicin de divisibilidad requiere que cada variable de decisin pueda tomar valores fraccionarios. Un problema de PL en el cual algunas, o todas las variables tienen que ser nmeros enteros no negativos, se llama un problema de programacin entera. Luego estudiaremos soluciones de problemas de programacin entera.

CertidumbreLa suposicin de certidumbre significa que tiene que conocerse con certeza cada parmetro del modelo (coeficiente de la funcin objetivo, lado derecho y el coeficiente tecnolgico).

La Regin Factible y La Solucin ptimaDos de los conceptos ms fundamentales asociados a los problemas PL, son la regin factible y la solucin ptima. Para definir estos conceptos, usamos el trmino punto para indicar un valor especfico de cada variable de decisin.

DefinicinLa regin factible para un PL es el conjunto de todos los puntos que satisfacen todas las restricciones.

Cuando el PL tiene ms de dos variables de decisin, a la regin factible se le conoce como hiperplano. Cualquier punto que no se encuentra en la regin factible se llama punto no factible.

DefinicinPara un problema de maximizacin, una solucin ptima para un PL, es un punto de la regin factible con el mayor valor de la funcin objetivo. Similarmente, para un problema de minimizacin, una solucin ptima corresponde a un punto de la regin factible, con el menor valor de la funcin objetivo.

La mayora de los PL tiene solamente una solucin ptima. Sin embargo, algunos PL no tienen solucin ptima, y algunos PL tienen un nmero infinito de soluciones.

Solucin grfica de problemas bidimensionales de Programacin LinealPara resolver grficamente cualquier PL con solamente dos variables. Siempre denominamos las variables x1 y x2 y los ejes coordenados los ejes x1 y x2. Luego haremos lo siguiente:1. Graficamos cada una de las restricciones incluyendo las de no negatividad.

La regin factible para el problema de Giapetto se muestra en la grfica siguiente:

Despus de identificar la regin factible buscamos

2. la solucin ptima, que corresponder al punto de la regin factible con el mayor (o menor) valor de z. Para encontrar la solucin ptima, tenemos que graficar una lnea recta que corresponde a todos los puntos con un mismo valor de z. Estas lneas se conocen como lneas de indiferencia o de isocostos (o isoutilidades para maximizacin)

3. Para dibujar una lnea de indiferencia escogemos cualquier punto de la regin factible y calculamos el valor de z, o simplemente le podemos dar un valor particular a z. Luego de graficar al menos dos lneas de indiferencia notaremos que dichas lneas son paralelas pues todas tienen la misma pendiente. Esto quiere decir que podemos encontrar todas las lneas de indiferencia, una vez trazada una lnea de indiferencia, trazndolas paralelamente a la primera.4. La ltima lnea de indiferencia que toca la regin factible define el mximo (o mnimo) valor de z de cualquier punto en la regin factible e indica la solucin ptima del PL.

5. El punto que corresponde a la solucin ptima es la interseccin de al menos dos rectas que corresponden a las restricciones. Para hallar dicho valor solamente debemos resolver el sistema de ecuaciones lineales asociado a todas las rectas de dicha interseccin.6. El valor ptimo de z se obtiene sustituyendo los valores de x1 y x2 en la funcin objetivo.

Se puede demostrar que cualquier PL que tiene una solucin ptima, tiene un punto de las esquinas de la regin factible que es ptimo.

Un Problema de Minimizacin

Dorian Auto fabrica automviles de lujo y camiones. La compaa opina que sus clientes ms probables son mujeres y hombres de ingresos altos. Para llegar a estos grupos, Dorian Auto lanz una campaa ambiciosa de publicidad por televisin y decidi comprar comerciales de un minuto en dos tipos de programa: series cmicas y partidos de ftbol. 7 millones de mujeres de ingresos altos y 2 millones de hombres de ingresos altos ven cada comercial en series cmicas. 2 millones de mujeres de ingresos altos y 12 millones de hombres de ingresos altos ven cada comercial en partidos de ftbol. Un comercial de un minuto en una serie cmica, cuesta 50000 dlares, y un comercial de un minuto en un juego de ftbol, cuesta 100000 dlares. Dorian quisiera que por lo menos 28 millones de mujeres de ingresos altos y 24 millones de hombres de ingresos altos vieran los comerciales. Utilice la programacin lineal para determinar cmo Dorian Auto puede alcanzar sus requerimientos publicitarios a un costo mnimo.

Sean x1: La cantidad de comerciales de 1 minuto en series cmicasx2: La cantidad de trenes de 1 minuto en juegos de ftbol

El modelo es:

CASOS ESPECIALES

Los problemas de Giapetto y de Dorian tienen una solucin ptima nica, pero no siempre este es el caso. La solucin de un PL que no tiene una solucin ptima nica puede estar dentro de alguna de las tres categoras siguientes:1. Algunos PL tienen un nmero infinito de soluciones ptimas (soluciones ptimas alternativas o mltiples)2. Algunos PL no tiene soluciones factibles (PL no factibles)3. Alguno PL son no acotados: hay puntos de la regin factible con valores de z arbitrariamente grandes (o pequeos)

Soluciones ptimas Alternativas Mltiples

Una compaa automotriz produce automviles y camiones. Cada vehculo tiene que pasar por un taller de pintura y por un taller de montaje de la carrocera. Si en el taller de pintura se pintaran solamente camiones, se podran pintar 40 camiones al da. Si en el taller de pintura se pintaran solamente automviles, se podran pintar 60 automviles diariamente. Si el taller de carrocera produjera solamente automviles, podra fabricar 50 automviles al da. Si el taller de carrocera produjera solamente camiones, podra fabricar 50 camiones al da. Cada camin aporta 300 dlares a la utilidad, y cada automvil 200. Utilice la programacin lineal para determinar la produccin diaria que maximizar la ganancia de la compaa.

Si en la regin factible, dos puntos son ptimos, entonces cualquier punto del segmento rectilneo que une estos dos puntos, tambin ser ptimo.Si se presenta un ptimo alternativo, quin tome la decisin puede utilizar un segundo criterio para escoger entre las soluciones ptimas. Se usa frecuentemente la programacin de metas para escoger entre soluciones ptimas alternativas.

Sean x1: La cantidad de automviles a producirx2: La cantidad de camiones a producir

El modelo es:

Al trazar la lnea de indiferencia para z = 6000, observamos que es paralela a la recta 2x1 + 3x2 = 120. Por lo que el problema tiene 2 soluciones ptimas.Producir 30 automviles y 20 camiones o producir nicamente 40 camiones.

Problema de Programacin Lineal No Factible

Una compaa automotriz produce automviles y camiones. Cada vehculo tiene que pasar por un taller de pintura y por un taller de montaje de la carrocera. Si en el taller de pintura se pintaran solamente camiones, se podran pintar 40 camiones al da. Si en el taller de pintura se pintaran solamente automviles, se podran pintar 60 automviles diariamente. Si el taller de carrocera produjera solamente automviles, podra fabricar 50 automviles al da. Si el taller de carrocera produjera solamente camiones, podra fabricar 50 camiones al da. Cada camin aporta 300 dlares a la utilidad, y cada automvil 200. Los distribuidores de automviles requieren que la compaa automotriz produzca por lo menos 30 camiones y 20 automviles. Utilice la programacin lineal para determinar la produccin diaria que maximizar la ganancia de la compaa.

Sean x1: La cantidad de automviles a producirx2: La cantidad de camiones a producir

El modelo es:

Como no existe regin factible (no qued regin sombreada) entonces el problema es infactible.

Problema de Programacin Lineal No Acotado

El siguiente PL especial es un PL no acotado. Para un problema de maximizacin un PL no acotado se presenta cuando es posible encontrar puntos en la regin factible de z con valores arbitrariamente grandes, lo que corresponde a una ganancia arbitrariamente grande para quien toma las decisiones. Esto indicara que una solucin ptima no acotada no debera presentarse en un PL corectamente formulado. Por lo tanto, si el lector llega a resolver un PL con ayuda de un computador, y encuentra que el PL es no acotado, entonces probablemente se ha cometido un error en la formulacin del PL o en la determinacin del PL en el computador.

Para un problema de minimizacin, un PL es no acotado, si existen puntos en la regin factible con valores z arbitrariamente pequeos. Al resolver grficamente un PL, podemos descubrir un PL no acotado de la manera siguiente. Un problema de maximizacin es no acotado si, al moverse paralelamente a la lnea de indiferencia original, en la direccin que aumenta z, nunca salimos completamente de la regin factible. Un problema de minimizacin es no acotado, si nunca salimos de la regin factible, al movernos en la direccin que decrece z.

EjemploResuelva grficamente el siguiente PL

Como no podemos abandonar la regin factible al ir con paralelas, entonces el problema es no acotado.

El Algoritmo Simplex

El mtodo simplex es un procedimiento general para resolver problemas de programacin lineal. Desarrollado por George Dantzig en 1947, est comprobada su extraordinaria eficiencia, y se usa en forma rutinaria para resolver problemas con las computadoras actuales. Excepto en el caso de problemas muy pequeos, se ejecuta siempre en una computadora y existe una amplia variedad de paquetes complejos de software para ello.

Hemos visto como resolver PL vibariables. Infortunadamente, la mayora de los PL en la vida real tienen muchas variables y, por lo tanto, se necesita un mtodo para resolver un PL con ms de dos variables. Este mtodo es el algoritmo simplex que se usa para resolver PL muy grandes.

CMO TRANSFORMAR UN PL EN LA FORMA ESTNDAR

Vimos que un PL puede tener restricciones en forma de igualdad o de desigualdad. Tambin puede tener variables que tienen que ser no negativas, o variables que pueden no tener restriccin de signo. Antes de poder usar el algoritmo simplex para resolver un PL hay que trasformar el PL en un problema equivalente, en el cual todas las restricciones son ecuaciones y todas las variables son no negativas. Un PL que se encuentra en esta forma, est en su forma estndar.

Para transformar un PL en la forma estndar, hay que sustituir cada restriccin en forma de desigualdad, por una restriccin en forma de igualdad. Ilustramos este procedimiento mediante el siguiente ejemplo.

Leather Limited produce dos tipos de cinturones: el modelo de lujo y el modelo regular. Cada tipo requiere 1 yarda2 de cuero. El cinturn regular requiere una hora de trabajo especializado, y el cinturn de lujo necesita dos horas. Se dispone, semanalmente, de 40 yardas2 de cuero y 60 horas de mano de obra especializada. Cada cinturn regular contribuye con tres dlares a la ganancia, y cada cinturn de lujo contribuye con cuatro dlares a la ganancia. Cuntos cinturones de cada tipo se deben producir con objeto de maximizar la ganancia?

SolucinPodemos resumir la informacin en la siguiente tabla:

Tipo de CinturnRequerimiento de cueroyarda2Horas de trabajo especializadoGanancia(dlares)

De lujo124

Regular113

Disponibilidad4060

Sean x1: La cantidad de cinturones regulares a producirx2: La cantidad de cinturones de lujo a producir

El respectivo modelo es:

La solucin grafica es la siguiente:

En consecuencia, para maximizar la ganancia se deben producir 20 cinturones regulares y 20 cinturones de lujo. La mxima ganancia ser de 140 dlares.

Algoritmo Simplex

Paso 1: Transforme el problema de programacin lineal en la forma estndarPara llevar al modelo a la forma estndar debemos introducir una variable de holgura por cada restriccin de menor o igual. Las variables de holgura representan la cantidad de recursos no utilizada en la i-sima restriccin, no afectan la funcin objetivo y por eso tienen coeficiente cero en dicha funcin.

Paso 2: Obtenga una solucin bsica factible a partir de la forma estndar. Una solucin bsica factible es aquella que cumple con todas las restricciones.Para obtener una solucin bsica factible llevamos el modelo a una tabla simplex como la que se da a continuacin.

Bsica3400Lado derecho

x1x2S1S2

S10111040

S20120160

Cj zj34000

La solucin siempre se leer igualando la respectiva variable bsica con el lado derecho. Si una variable no es bsica, entonces tomar el valor cero.

En el ejemplo, como x1 y x2 no son bsicas entonces x1 = 0 y x2 = 0 (primera solucin bsica factibles (sbf))

Paso 3: Determine si la solucin bsica factible es ptimaEn una tabla simplex, la solucin es ptima si todos los coeficientes en la fila Cj zj son menores o iguales a cero.

Bsica3400Lado derecho

x1x2S1S2

S10111040

S20120160

Cj zj34000

Como existen valores positivos en la fila Cj zj, entonces la sbf no es ptima.

Paso 4: Si la solucin bsica factible no es ptima, determine qu variable no bsica se tiene que convertir en una variable bsica y qu variable bsica se tiene que convertir en una variable no bsica para encontrar as una nueva solucin bsica factible con un mejor valor de la funcin objetivo.

Se elige como la variable bsica entrante la que tiene el coeficiente positivo mayor en la fila Cj zj, ya que es la que hace que z se incremente a la tasa ms rpida.

Bsica3400Lado derecho

x1x2S1S2

S10111040

S20120160

Cj zj34000

Para determinar la variable bsica que sale hacemos lo siguiente:a) Tomamos cada coeficiente estrictamente positivo de la columna pivoteb) Dividimos el lado derecho de cada ecuacin entre estos coeficientesc) Identificamos la ecuacin con el menor cociente. El menor cociente es el mximo valor de la variable que entra que mantendr todas las variables bsicas actuales no negativas.d) Seleccionamos la variable bsica entrante para esta ecuacin

Bsica3400Lado derechoRazn

x1x2S1S2

S1011104040

S2012016030

Cj zj34000

Por lo anterior, x2 entrar a ser bsica y S2 dejar de ser bsica.

Al elemento que se encuentra en la interseccin de la fila pivote y la columna pivote se le conoce como pivote.

Paso 5: Si la solucin bsica factible no es ptima, entonces reoptimice utilizando reduccin gaussiana.

Iteracin 1Bsica3400Lado derechoRazn

x1x2S1S2

S101/2011/21020

x241/2103060

Cj zj1002120

La sbf actual no es ptima

Iteracin 2Bsica3400Lado derechoRazn

x1x2S1S2

x13102120

x24011120

Cj zj0021140

La solucin es ptima.

As, x1 = 20 y x2 = 20.

Empate para la variable bsica entranteCmo debe romperse el empate?, La respuesta es que la eleccin entre los contendientes se puede hacer de manera arbitraria. Tarde o temprano se llegar a la solucin ptima, sin importar cul de las variables empatadas se haya escogido, y no existe un mtodo conveniente para predecir cul lleva ah ms rpidamente.

Adaptacin a Otras Formas del Modelo

Hasta ahora hemos presentado los detalles del mtodo simplex con la suposicin de que el problema se encuentra en la forma estndar.El nico problema serio que introducen las otras formas de restricciones funcionales (=, que tienen lados derechos no negativos) es identificar una solucin bsica factible inicial. Antes, esta solucin inicial se encontraba en forma muy conveniente al hacer que las variables de holgura fueran las variables bsicas iniciales, donde cada una era igual a la constante no negativa del lado derecho de la ecuacin correspondiente. Ahora debe hacerse algo ms. El enfoque estndar que se utiliza en esos casos es la tcnica de variables artificiales. Esta construye un problema artificial ms conveniente introduciendo una variable ficticia (llamada variable artificial) en cada restriccin que lo requiera. Esta nueva variable se introduce slo con el fin de que sea la variable bsica inicial para esa ecuacin. Las restricciones usuales de no negatividad tambin se aplican sobre estas variables y la funcin objetivo se modifica para que imponga una penalizacin exorbitante en el caso de que adquieran valores mayores que cero. Las iteraciones del mtodo simplex automticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una, hasta que todas quedan fuera de la solucin; despus de esto se resuelve el problema real.

Restricciones en forma de igualdadPara convertir una restriccin de igualdad, en la forma apropiada del mtodo simplex. Construimos un problema artificial que tiene la misma solucin ptima que el problema real, haciendo dos modificaciones a este problema real.1. Introducimos una variable artificial no negativa como si fuera una variable de holgura.2. Asignamos una penalizacin enorme al coeficiente de la variable artificial en la funcin objetivo, el valor del coeficiente ser M, donde M simblicamente representa un nmero positivo muy grande.

Ahora se encuentra la solucin ptima para el problema real aplicando el mtodo simplex al problema artificial.

Restricciones de Mayor o IgualPara convertir una restriccin de mayor o igual a una restriccin de igualdad, sumaremos a la restriccin una variable artificial y restaremos una variable de holgura, penalizando adecuadamente la variable artificial.

MinimizacinEn lugar de cambiar las instrucciones del mtodo simplex se presentar una manera sencilla de convertir cualquier problema de minimizacin en un problema equivalente de maximizacin.

Minimizar es equivalente a Maximizar

Variables artificialesLas variables artificiales se introducen slo con el fin de que sea la variable bsica inicial para esa ecuacin que la requiere.Las restricciones usuales de no negatividad tambin se aplican sobre estas variables y la funcin objetivo se modifica para que imponga una penalizacin exorbitante en el caso que adquieran valores mayores que cero.Las iteraciones del mtodo simplex automticamente fuerzan a las variables artificiales a desaparecer (volverse cero) una a una, hasta que todas quedan fuera de la solucin, despus de esto se resuelve el problema real.

EjemploRicitos de Oro necesita encontrar por lo menos 12 libras de oro y al menos 18 libras de plata para pagar la renta mensual. Hay dos minas en las cuales Ricitos de Oro puede encontrar oro y plata. Cada da que Ricitos de Oro pasa en la mina 1 encuentra 2 lb de oro y 2 lb de plata. Cada da que Ricitos de Oro pasa en la mina 2 encuentra 1 lb de oro y 3 lb de plata. Plantee y resuelva un PL que ayude a Ricitos de Oro a cumplir con sus requerimientos pasando el menor tiempo posible en las minas.

SolucinSean x1: La cantidad de das que Ricitos de Oro debe pasar en la mina 1x2: La cantidad de das que Ricitos de Oro debe pasar en la mina 2

El respectivo modelo es:

Llevamos el problema a la forma estndar. Recordemos que por cada restriccin de debemos sumar una variable artificial y restar una variable de holgura.

Ahora, podemos convertir cualquier problema de minimizacin en un problema de maximizacin multiplicando la funcin objetivo por -1.

Ahora lo llevamos a la forma estndar

Llevamos el modelo a la tabla y resolvemos

Bsica110M0MLado derechoRazn

x1x2S1A1S2A2

A1M211100126

A2M230011189

Cj zj1 + 4M1 + 4MM0M0

Observemos que hay un empate entre las variables que entran a ser bsicas, como ste se resuelve arbitrariamente, entonces seleccionamos a x1 como la columna pivote.

Bsica110M0MLado derechoRazn

x1x2S1A1S2A2

x1111/21/21/200612

A2M02111163

Cj zj01/2 + 2M1/2 +M1/2 2MM06 6M

Bsica110M0MLado derechoRazn

x1x2S1A1S2A2

x11103/43/41/41/49/2

x21011/21/21/23

Cj zj001/4 1/4 M1/4 1/4 M15/2

Solucin ptima

Ricitos debe trabajar 4.5 das en la mina 1 y 3 das en la mina 2 con un mnimo de 7.5 das

Soluciones ptimas mltiplesUna vez que el mtodo simplex encuentra una solucin ptima, Cmo reconocer que existen otras y cmo se encuentran?Siempre que un problema tiene ms de una solucin factible ptima, al menos una variable no bsica tiene coeficiente cero en la fila Cj zj de la tabla simplex final, de manera que si aumenta su valor, el valor de la funcin z no cambia.

EjemploLa Dakota Furniture Company fabrica escritorios, mesas y sillas. Un escritorio se vende en 60 dlares, una mesa se vende a 35 dlares y una silla se vende en 20 dlares. Por ahora, se disponen de 48 pies tabla de madera, de 20 horas de acabado y 8 horas de carpintera. Dakota cree que la demanda de escritorios y sillas es ilimitada, pero se pueden vender a lo ms cinco mesas. Dakota quiere maximizar el ingreso total porque se han comprado ya los recursos. Cuntos artculos de cada tipo deben producir?

RECURSOESCRITORIOMESASILLA

Madera8 pies tabla6 pies tabla1 pie tabla

Horas de acabado4 horas2 horas1.5 horas

Horas de carpintera2 horas1.5 horas0.5 horas

SolucinSean x1: La cantidad de escritorios a producirx2: La cantidad de mesas a producirx3: La cantidad de sillas a producir

El modelo es:

Llevamos el problema a la forma estndar.

Llevamos el modelo a la tabla y resolvemos

Bsica6035200000Lado derechoRazn

x1x2x3S1S2S3S4

S10861100048

S20421.5010020

S3021.50.500108

S4001000015

Cj zj6035200000

Bsica6035200000Lado derechoRazn

x1x2x3S1S2S3S4

S108611000486

S20421.50100205

S3021.50.5001084

S4001000015

Cj zj60352000000

Bsica6035200000Lado derechoRazn

x1x2x3S1S2S3S4

S1000-110-4016

S200-11/201-2048

x16011/4001/20416

S4001000015

Cj zj0-10500-300240

Bsica6035200000Lado derechoRazn

x1x2x3S1S2S3S4

S100-2012-8024

x3200-2102-408

x16015/400-1/23/2028/5

S40010000155

Cj zj0000-10-100280

La solucin ptima es fabricar 2 escritorios y 8 sillas

Pero, en la tabla simplex final se observa que hay una variable no bsica con coeficiente cero en la fila Cj zj, entonces hay otra solucin ptima. Para encontrar la otra solucin, simplemente se convierte la variable x2 en bsica y se hacen las acostumbradas operaciones entre filas.

Bsica6035200000Lado derechoRazn

x1x2x3S1S2S3S4

S108/50016/5-28/50136/5

x3208/50106/5-8/5056/5

x2354/5100-2/56/508/5

S40-4/50002/5-6/5117/5

Cj zj0000-10-100280

La otra solucin ptima es producir 8/5 de mesas y 56/5 de sillas. Ms adelante veremos como trabajar con problemas enteros.

Cuando no hay variable bsica que sale - z no acotadaExiste otra posibilidad, aquella en la que ninguna variable califica como variable bsica que sale. Esta situacin puede ocurrir si la variable bsica entrante puede crecer indefinidamente sin que ninguna de las variables bsicas actuales adquiera valores negativos. En la forma tabular, esto significa que todos los coeficientes en la columna pivote son negativos o cero.

EjemploResuelva

SolucinLlevamos el problema a la forma estndar. Recordemos que por cada restriccin de debemos sumar una variable artificial y restar una variable de holgura.

Llevamos el modelo a la tabla y resolvemos

Bsica2100MLado derechoRazn

x1x2S1S2A2

S101110011

A2M2101163

Cj zj2 + 2M1 + M0M0

Bsica2100MLado derechoRazn

x1x2S1S2A2

S10111001

A2M0321144/3

Cj zj01 + 3M2 2MM0

Bsica2100MLado derechoRazn

x1x2S1S2A2

S10101/31/31/37/3

A2M012/31/31/34/3

Cj zj00 4/31/3M (1/3)10/3

Aunque la solucin no es ptima, si queremos seleccionar la fila pivote vemos que todos los elementos en la columna pivote son negativos y por tanto no podemos hallar la razn y en ese sentido no tendremos variable que deja de ser bsica. As, el problema es no acotado.

Problema de programacin Lineal No FactibleAhora veremos cmo reconocer en la tabla simplex final cuando un problema es No factible.

EjemploUna compaa automotriz produce automviles y camiones. Cada vehculo tiene que pasar por un taller de pintura y por un taller de montaje de la carrocera. Si en el taller de pintura se pintaran solamente camiones, se podran pintar 40 camiones al da. Si en el taller de pintura se pintaran solamente automviles, se podran pintar 60 automviles diariamente. Si el taller de carrocera produjera solamente automviles, podra fabricar 50 automviles al da. Si el taller de carrocera produjera solamente camiones, podra fabricar 50 camiones al da. Cada camin aporta 300 dlares a la utilidad, y cada automvil 200. Adems, los distribuidores de automviles requieren que la compaa automotriz produzca por lo menos 30 camiones y 20 automviles. Utilice la programacin lineal para determinar la produccin diaria que maximizar la ganancia de la compaa.

SolucinSean x1: La cantidad de automviles a producirx2: La cantidad de camiones a producir

El modelo es.

Llevamos el problema a la forma estndar.

Bsica200300000M0MLado derechoRazn

x1x2S1S2S3A3S4A4

S102310000012040

S20110100005050

A3M1000110020

A4M010000113030

Cj zj200+M300+M00M0M0

Bsica200300000M0MLado derechoRazn

x1x2S1S2S3A3S4A4

S10201000333015

S20100100112020

A3M100011002020

x23000100001130

Cj zj200+M000M0300300 M9000

Bsica200300000M0MLado derechoRazn

x1x2S1S2S3A3S4A4

x1200101/20003/23/215

S20001/21001/21/2510

A3M001/20113/23/2510/3

x2300010000113030

Cj zj00100 (1/2)M0M0(3/2)M(1/2)M12000

Bsica200300000M0MLado derechoRazn

x1x2S1S2S3A3S4A4

x12001000110015

S20001/311/31/3005

A4M001/302/32/3115

x2300011/302/3-2/30030

Cj zj00100 (1/3)M0(2/3)M (1/3)MM012000

Observemos que se ha alcanzado la solucin ptima pero qued una variable artificial como bsica, esto impedir que se alcance el mximo. As, cuando en una tabla simplex final hay una variable artificial bsica, el problema es no factible.

Degeneracin y Convergencia del Mtodo Simplex

Tericamente, quiz el teorema simplex no encuentre la solucin ptima de un PL. Sin embargo, los PL que se obtienen de aplicaciones reales, raras veces presentan este comportamiento desagradable. Sin embargo para que sea completo es estudio, analizamos ahora una situacin en la cual el mtodo simplex puede fallar.

Por el momento, suponga que el PL que estamos resolviendo, tiene la siguiente propiedad: en cada una de las soluciones bsicas factibles del PL, todas las variables bsicas son positivas ( > 0). Un PL con esta propiedad es un PL no degenerado.Si usamos el mtodo simplex para resolver un PL no degenerado, en cada iteracin del mtodo simplex aumentara z. Esto significa que utilizando el mtodo simplex para resolver un PL no degenerado, es imposible encontrar dos veces la misma solucin bsica factible. Ahora, recuerde que cada PL tiene solamente un nmero finito de soluciones bsicas factibles. Ya que no podemos repetir nunca una solucin bsica factible, este argumento muestra que, cuando utilizamos el teorema simplex para resolver un PL no degenerado, tenemos la seguridad de encontrar la solucin ptima despus de un nmero finito de iteraciones.

Sin embargo, el teorema simplex puede fallar en el caso de un PL degenerado

DefinicinUn PL se llama degenerado si tiene por lo menos una solucin bsica factible con una variable bsica igual a cero.

EjemploDoa Zoila de Plata tiene un milln de UM disponible para invertir. Un comisionista amigo le sugiere que invierta en dos tipos de acciones, A1 y A2. El tipo A1 tiene bastante riesgo y promete un inters anual de 36%, mientras que A2 es ms segura y paga un inters de 27% anual. Tras algunas consideraciones decide invertir segn las siguientes condiciones:Como mximo 60% de su dinero en A1 y como mnimo 20% en A2 e invertir al menos, tanto en A1, como lo invertido en A2. Qu cantidades debe invertir en cada tipo de accin para maximizar los intereses a recibir?

El siguiente PL es degenerado

El problema en la forma estndar es:

El problema en la tabla simplex es:

Bsica5200Lado derechoRazn

x1x2S1S2

S10111066

S201-10100

Cj zj52000

Como S2 es variable bsica y toma el valor cero, entonces la solucin es degenerada.

Bsica5200Lado derechoRazn

x1x2S1S2

S10021-163

x151-1010

Cj zj070-50

Bsica5200Lado derechoRazn

x1x2S1S2

x22011/2-1/23

x15101/21/23

Cj zj00-7/2-3/221

Solucin ptima

Ahora podemos explicar por qu el teorema simplex puede tener problemas al resolver un PL degenerado. Supngase que estamos resolviendo un PL degenerado para el cual el valor ptimo de z es 30. Si empezamos con una solucin bsica factible que tiene, por ejemplo, z = 20, sabemos que es posible que un pivoteo no cambie el valor de z. Esto significa que es posible observar una sucesin de pivoteos como la que se muestra a continuacin:

Solucin bsica factible inicial: z = 20Despus del primer pivoteo (sbf 2): z = 20Despus del segundo pivoteo (sbf 3): z = 20Despus del tercer pivoteo (sbf 4): z = 20Despus del quinto pivoteo (sbf 1): z = 20

En esta situacin, encontramos la misma sbf dos veces. Este hecho se llama periodicidad. Si se presenta la periodicidad, daremos vueltas para siempre, entre un conjunto de soluciones bsicas factibles, y nunca obtendremos la solucin ptima. La periodicidad puede ocurrir realmente. Afortunadamente, se puede modificar el mtodo simplex para asegurar que la periodicidad nunca se presente (vase Bland o Dantzig para ms detalles). En la prctica sin embargo, la periodicidad es algo extremadamente raro. Por tal motivo, la mayora de los programas de cmputo para PL, no se protegen contra la posibilidad de periodicidad.

Otros ejemplos

EjemploBrevco produce una bebida con sabor a naranja, Oranj, al mezclar refresco y jugo de naranja. Cada onza de refresco de naranja contiene 0.5 oz de azcar y 1 mg de vitamina C. Cada onza de jugo de naranja contiene 0.25 oz de azcar, y 3 mg de vitamina C. A Brevco le cuesta 2 centavos producir una onza de refresco de naranja y 3 centavos una onza de jugo de naranja. El departamento de mercadotecnia de Brevco ha decidido que cada botella de 10 oz de Oranj, debe contener por lo menos 20 mg de vitamina C, y a lo ms 4 oz de azcar. Utilice la programacin lineal para determinar cmo Brevco puede satisfacer los requerimientos del departamento de mercadotecnia, al menor costo.

EjemploEl administrador del sistema de suministro de agua de cierta ciudad debe hallar la manera de proporcionar por lo menos 10 millones de galones de agua potable por da (mgd). El agua se debe tomar de los depsitos locales o de una tubera hacia una poblacin vecina. Los depsitos locales pueden suministrar 5 mgd, cantidad que no puede ser excedida. La tubera, debido a su tamao, puede suministrar un mximo de 10 mgd. Adems, debido a una clusula contractual, debe bombear por lo menos 6 mgd. Por ltimo, el costo del agua del depsito es de $300 por milln de galones y el costo del agua de la tubera es de $500 por un milln de galones. En qu forma puede al administrador minimizar el costo diario del agua?

EjemploBreadco Bakeries produce dos tipos de pan: pan francs y pan de masa fermentada. Se puede vender cada barra de pan francs a 36 centavos de dlar, y cada pan fermentado a 30 centavos. Una barra de pan francs requiere 1 paquete de levadura y 6 onzas de harina, y un pan fermentado requiere 1 paquete de levadura y 5 onzas de harina. Actualmente Breadco tiene 5 paquetes de levadura y 10 onzas de harina. Se puede comprar paquetes adicionales de levadura a 3 centavos cada uno, y ms harina a 4 centavos/onza. Formule y resuelva un PL para maximizar las ganancias de Breadco (ingresos - costos)

Variables sin restriccin de signo

EjemploUn panadero tiene 30 onzas de harina y 5 paquetes de levadura. La produccin de un pan requiere de 5 onzas de harina y un paquete de levadura. Se puede vender cada pan a 30 centavos. El panadero puede comprar ms harina a 4 centavos por onza o vender el excedente de harina al mismo precio. Formule un PL para ayudar al panadero a maximizar sus ganancias (ingreso costos).

12