Método de la “M” o de Penalización
Enviado por Programa Chuletas y clasificado en Matemáticas
Escrito el en 
español con un tamaño de 30,61 KB
Método de la M o de Penalización.
Hasta este momento se han presentado los detalles del método símplex con la suposición de que el problema se encuentra en nuestra forma estándar(maximizar Z sujeta a las restricciones funcionales de la forma £ y restricciones de no negatividad sobre todas las variables) con bi ³ 0 para toda i = 1, 2, ..., m. En esta sección se establecerá cómo hacer los ajustes requeridos a otras formas legítimas de modelos de Programación Lineal. Se verá que todos estos ajustes se pueden hacer en el paso inicial, de manera que el resto del método símplex se aplica justo como se aprendió.
El único problema serio que introducen las otras formas de restricciones funcionales (= ó ³ ) es identificar una solución inicial básica factible. Antes, esta solución inicial se encontraba en forma muy conveniente al hacer que las variables de holgura fueran las variables básicas iniciales, donde cada una era igual a la constante no negativa del lado derecho de la ecuación correspondiente. Ahora debe hacerse algo más. El enfoque estándar que se utiliza es estos casos es la técnica de variables artificiales. Ésta construye un problema artificial más conveniente introduciendo una variable ficticia (llamada variable artificial) en cada restricción que lo requiera. Esta nueva variable se introduce sólo con el fin de que sea la variable básica inicial para esa ecuación. Las restricciones usuales de no negatividad también se aplican sobre estas variables y la función objetivo se modifica para que imponga una penalización exorbitante en el caso de que adquieran valores mayores que cero. Las iteraciones del método símplex automáticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una, hasta que todas quedan fuera de la solución; después de esto se resuelve el problema real.
Para ilustrar la técnica de las variables artificiales, primero se considerará el caso en que la única forma no estándar en el problema es la presencia de una o más restricciones en forma de igualdad.
Restricciones en forma de igualdad.
En realidad, cualquier restricción en forma de igualdad:
ai1x1 +ai2x2 + . . . + ainxn = bi
es equivalente a dos restricciones de desigualdad:
ai1x1 + ai2x2 + . . . + ainxn £ bi,
ai1x1 + ai2x2 + . . . + ainxn ³ bi
Sin embargo, en lugar de hacer esta sustitución e incrementar con ello el número de restricciones, es más conveniente usar la técnica de la variable artificial. Suponga que se modifica el problema de ejemplo presentado y resuelto en la sección anterior. El único cambio que sufre el modelo de programación lineal es que la tercera restricción, 3x1 + 2x2 £ 18, se convierte en una restricción de igualdad:
3x1 + 2x2 = 18
Aplicando la técnica de las variables artificiales se introduce una variable artificial no negativa (denotada por x5) en la última ecuación, como si fuera una variable de holgura:
3x1 + 2x2 + x5 =18
En resumen si tenemos una restricción funcional en forma de igualdad y deseamos pasarla a su forma de igualdad En resumen si tenemos una restricción funcional en forma de igualdad y deseamos pasarla a su forma de igualdad, únicamente debemos sumar una variable artificial.
Restricciones funcionales de la forma ³
Para ilustrar la manera en que la técnica de las variables artificiales maneja las restricciones de la forma ³ usaremos el siguiente ejemplo:
Minimizar Z = 0.4x1 + 0.5x2
sujeta a 0.3x1 + 0.1x2 sujeta a 0.3x1 + 0.1x2 £ 2.7
0.5x1 + 0.5x2 = 6
0.6x1 + 0.4x2 0.6x1 + 0.4x2 ³ 6
x1 ³ 0, x2 ³ 0
Notemos que la tercera restricción es del tipo ³ , por lo que para cambiarla a su forma de igualdad tendríamos que restar una variable de superávit (o de excedente), quedando de la siguiente manera:
0.6x1 + 0.4x2 - x5 = 6
Se ha restado la variable de excedente x5 (se utilizó x5 porque en la primera restricción agregamos una variable de holgura que sería x3 y en la segunda restricción agregamos también una variable artificial que sería x4; todo esto con el fin de convertir las desigualdades a su forma de igualdades) para que consuma el exceso de 0.6x1 + 0.4x2, o sea, lo que se pasa de 6. No obstante en este caso debe agregarse otra variable. Esta variable extra, llamada variable artificial se aumenta como sigue:
0.6x1 + 0.4x2 - x5 + x6 = 6
La razón de esto es que, si no se agrega la variable artificial, no se estarían cumpliendo las restricciones de no negatividad. Para comprenderlo, se dejará sin aumentar. El método símplex comienza por hacer todas las variables reales (originales) iguales a cero. Entonces:
0.6x1 + 0.4x2 - x5 = 6
Sea x1 = 0 y x2 = 0, entonces:
- x5 = 6
ó x5 = - 6 (que no cumple la restricción de no negatividad)
La variable artificial opera para mantener todas las variables no negativas cuando 0.6x1 + 0.4x2 es menor que 6. Si x1 = 0 y x2 = 0, entonces x5 = 0 y
0.6x1 + 0.4x2 - x5 + x6 = 6
x6x6 = 6
En resumen, una restricción de la forma ³ se convierte a su forma de igualdad restando una variable de excedente y sumando una variable artificial.
Consideremos el siguiente problema:
MaximizarZ=3x1+5x2
sujeta a x1 sujeta a x1 £ 4
2x2 £ 12
3x1 + 2x2 3x1 + 2x2 = 18
x1 ³ 0, x2 ³ 0
Como explicamos anteriormente, para resolver este problema, debemos construir un problema artificial que tiene la misma solución óptima que el problema real, haciendo dos modificaciones a este problema real.
1. Se aplica la técnica de las variables artificiales introduciendo una variable artificialno negativa (denotada por x5) en la última ecuación, como si fuera una variable de holgura:
3x1 + 2x2 + x5 =18
2. Se asigna una penalización enorme al hecho de tener x5 > 0, cambiando la función objetivo
Z = 3x1 + 5x2 a:
Z = 3x1 + 5x2 - Mx5,
donde M simbólicamente representa un número positivo muy grande. Este método que fuerza a x5 hasta el nivel de x5 = 0 en la solución óptima se llama método de la M.
Nota: Para el caso de minimización, penalizamos a la variable artificial, haciéndola aparecer en la función objetivo con un coeficiente de +M.
Ahora se encuentra la solución óptima para el problema real aplicando el método símplex al problema artificial.
Como x5 juega el papel de la variable de holgura en la tercera restricción del problema artificial, esta restricción es equivalente a 3x1 + 2x2 Como x5 juega el papel de la variable de holgura en la tercera restricción del problema artificial, esta restricción es equivalente a 3x1 + 2x2 £ 18.
En particular, el sistema de ecuaciones después de aumentar el problema artificial (en otras palabras, pasarlo a su forma de igualdades) es:
Maximizar Z,
sujeta a
Z - 3x1 - 5x2 + Mx5 = 0
x1 + x3 x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + x5 3x1 + 2x2 + x5 = 18
xj ³ 0 Para j = 1, 2, , 5
En este momento estamos preparados para pasar los coeficientes a la tabla símplex:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 -3 -5 0 0 M 0
x3 0 1 0 1 0 0 4
xx4 x4 0 0 2 0 1 0 12
x5 0 3 2 0 0 1 18
Esta tabla todavía no está en la forma apropiada porque el coeficiente de x5 es diferente de cero en la ecuación de Z (es M). Por lo tanto, antes de que el método símplex pueda aplicar la prueba de optimalidad y encontrar la variable básica entrante, debe pasarse esta tabla a la forma apropiada para que cumpla la condición símplex. Esta condición que debe cumplir toda tabla del método símplex para que pueda reportarnos la siguiente solución básica factible dice que: Toda variable básica debe tener un 1 en la intersección de su renglón y columna correspondiente y cero en los demás renglones incluido el renglón de Z, en otras palabras, que toda variable que sea básica solamente debe aparecer en el renglón de la restricción que representa. Para hacer cero el coeficiente M, utilizamos el renglón de x5 como renglón pivote multiplicándolo por - M y sumando el resultado al renglón de Z. Realizando el procedimiento anterior, la tabla símplex queda de la siguiente manera:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 -3M-3 -2M-5 0 0 0 - 18M - M x5 + Z
xx3 x3 0 1 0 1 0 0 4 (0, 0, 4, 12, 18)
x4 0 0 2 0 1 0 12 Z = - 18M
xx5 x5 0 3 2 0 0 1 18
Podemos observar que la tabla anterior ya se encuentra en la forma apropiada y podemos leer la solución básica factible actual, que es (0, 0, 4, 12, 18), la cual aplicando la prueba de optimalidad vemos que no es óptima ya que todavía tenemos coeficientes negativos en el renglón de Z (los correspondientes a x1 y x2). Aplicando el método símplex a la tabla anterior tenemos: el coeficiente negativo con el mayor valor absoluto corresponde a x1 ( - 3M - 3), recordemos que M es un número muy grande positivo, por lo tanto, x1 se convierte en la variable básica entrante, realizando los cocientes correspondientes, vemos que x3 se convierte en la variable básica saliente. El procedimiento completo para resolver este ejemplo se muestra en el siguiente conjunto de tablas:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 -3M-3 -2M-5 0 0 0 - 18M
x3 0 1 0 1 0 0 4 4/1 = 4 (0, 0, 4, 12, 18)
xx4 x4 0 0 2 0 1 0 12 Z = - 18M
x5 0 3 2 0 0 1 18 18/3 = 6
Z 1 0 -2M-5 3M+3 0 0 - 6M+12
x1 0 1 0 1 0 0 4 (4, 0, 0, 12, 6)
xx4 x4 0 0 2 0 1 0 12 12/2 = 6 Z = - 6M+12
x5 0 0 2 - 3 0 1 6 6/2 = 3
Z 1 0 0 - 9/2 0 M+5/2 27
x1 0 1 0 1 0 0 4 4/1 = 4 (4, 3, 0, 6, 0)
xx4 x4 0 0 0 3 1 - 1 6 6/3 = 2 Z = 27
x2 0 0 1 - 3/2 0 1/2 3
Z 1 0 0 0 3/2 M+1 36
x1 0 1 0 0 - 1/3 1/3 2 (2, 6, 2, 0, 0)
xx3 x3 0 0 0 1 1/3 - 1/3 2 Z = 36
x2 0 0 1 0 1/2 0 6 Óptima
MINIMIZACIÓN con el método símplex.
Una manera directa de minimizar Z con el método símplex es cambiar los roles de los coeficientes negativos y positivos en el renglón de la función objetivo, tanto para la prueba de optimalidad como para la parte 1 de una iteración. Se determina la variable básica entrante mediante la elección de la variable con el coeficiente positivo menor en la ecuación de Z. La solución básica factible actual es óptima si y sólo si todos los coeficientes de la ecuación de la función objetivo (renglón de Z) son no positivos ( £ 0 ). Si es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la nueva solución básica factible, lo que significa el cambio de una variable no básica por una básica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución (parte 3). Notemos que no se ha dicho nada con respecto a la forma de obtener la variable básica saliente Una manera directa de minimizar Z con el método símplex es cambiar los roles de los coeficientes negativos y positivos en el renglón de la función objetivo, tanto para la prueba de optimalidad como para la parte 1 de una iteración. Se determina la variable básica entrante mediante la elección de la variable con el coeficiente positivo menor en la ecuación de Z. La solución básica factible actual es óptima si y sólo si todos los coeficientes de la ecuación de la función objetivo (renglón de Z) son no positivos ( £ 0 ). Si es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la nueva solución básica factible, lo que significa el cambio de una variable no básica por una básica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución (parte 3). Notemos que no se ha dicho nada con respecto a la forma de obtener la variable básica saliente en una iteración, ya que este paso se realiza de la misma manera que cuando se está maximizando, es decir, se escoge aquella variable básica con el menor cociente. Ilustremos la forma de utilizar el método símplex para el caso de minimización. Consideremos el siguiente ejemplo:
Minimizar Z = 3x1 + 8x2
sujeta a x1 + 4x2 sujeta a x1 + 4x2 £ 4
x1 + 2x2 ³ 2
x1 ³ 0, x2 ³ 0 x1 ³ 0, x2 ³ 0
Pasando este problema a su forma de igualdades añadiendo las variables necesarias, obtenemos lo siguiente:
Minimizar Z,
sujeta a
Z - 3x1 - 8x2 - Mx5 = 0
x1 + 4x2 + x3 x1 + 4x2 + x3 = 4
x1 + 2x2 - x4 + x5 = 2
xj xj ³ 0 para j = 1, 2, , 5
Utilizando el método de la M para obtener una solución óptima por el método símplex, obtenemos el siguiente conjunto de tablas:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 - 3 - 8 0 0 - M 0
x3 0 1 4 1 0 0 4
xx5 x5 0 1 2 0 - 1 1 2
Z 1 M - 3 2M - 8 0 - M 0 2M (0, 0, 4, 0, 2)
x3 0 1 4 1 0 0 4 4/1 = 4 Z = 2M
xx5 x5 0 1 2 0 - 1 1 2 2/1 = 2
Z 1 0 - 2 0 - 3 - M+3 6 (2, 0, 2, 0, 0)
x3 0 0 2 1 1 - 1 2 Z = 6
xx1 0 1 2 0 - 1 1 2 Óptima x1 0 1 2 0 - 1 1 2 Óptima
Notemos que la primera tabla no se encontraba en la forma apropiada para el método símplex, ya que el coeficiente de la variable básica x5 era de - M en el renglón de Z, lo cual hacia que no se cumpliera la condición símplex.
Método de las dos Fases.
En el ejemplo presentado en la sección Restricciones funcionales de la forma ³, recordemos la función objetivo real:
Problema real: Minimizar Z = 0.4x1 + 0.5x2
Sin embargo, el método de la M utiliza la siguiente función objetivo a través de todo el procedimiento:
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
Como los dos primeros coeficientes (0.4 y 0.5) son despreciables comparados con M, el método de dos fases puede eliminar la M usando las siguientes dos funciones objetivo que definen Z de manera completamente diferente:
Método de las dos fases:
Fase 1: Minimizar Z = x4 + x6 (hasta que x4 = 0 y x6 = 0).
Fase 2: Minimizar Z = 0.4x1 + 0.5x2 (con x4 = 0 y x6 = 0).
La función objetivo de la fase 1 se obtiene dividiendo la función objetivo del método de la M entre M eliminando los términos despreciables, en otras palabras, la fase 1 consiste en la minimización de la suma de todas las variables artificiales que se introduzcan en el problema. Como la fase 1 concluye al obtener una solución básica factible para el problema real (aquella en la que x4 = 0 y x6 = 0), esta solución se usa como la solución básica factible inicial para aplicar el método símplex al problema real (con su función objetivo) en la fase 2. Antes de resolver el ejemplo de esta manera se hará un resumen de las características generales.
Resumen del método de dos fases.
Paso inicial: Se revisan las restricciones del problema original introduciendo variables artificiales según se necesite para obtener una solución básica factible inicial obvia para el problema artificial.
Fase 1: uso del método símplex para resolver el problema de programación lineal:
Minimizar Z = S de todas las variables artificiales, sujeta a las restricciones revisadas.
La solución óptima que se obtiene para este problema (con Z = 0) será una solución básica factible para el problema real.
Fase 2: se eliminan las variables artificiales (de todas formas, ahora todas valen cero). Comenzando con la solución básica factible que se obtuvo al final de la fase 1, se usa el método símplex para resolver el problema real.
Enseguida se resumen los problemas que deben resolverse por el método símplex en las fases respectivas para el ejemplo.
Problema para la fase 1:
Minimizar W = x4 + x6Minimizar W = x4 + x6,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.7
0.5x0.5x1 + 0.5x2 + x4 0.5x1 + 0.5x2 + x4 = 6
0.6x1 + 0.4x2 - x5 + x6 = 6
y
x1³ 0 x2³ 0 x3³ x4³ 0 x5³ 0 x6³ 0
Problema para la fase 2:
Minimizar Z = 0.4x1 + 0.5x2Minimizar Z = 0.4x1 + 0.5x2,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.7
0.5x0.5x1 + 0.5x2 0.5x1 + 0.5x2 = 6
0.6x1 + 0.4x2 - x5 = 6
y
x1³ 0 x2³ 0 x3³ x5³ 0
Las únicas diferencias entre estos dos problemas se encuentran en la función objetivo y en la inclusión (fase 1) o exclusión (fase 2) de las variables artificiales x4 y x6. Sin las variables artificiales, el problema para la fase 2 no tiene una solución básica factible inicial obvia. El único propósito de resolver el problema para la fase 1 es obtener una solución básica factible con x4 = 0 y x6 = 0 que se pueda usar como la solución básica factible inicial para la fase 2.
Las siguientes tablas muestran el resultado de aplicar el método símplex a este problema para la fase 1:
VariableVariable Básica W x x1 x x2 x x3 x x4 x x5 x x6 LadoLado derecho Cociente ¿Es óptima? Variable Básica W x1 x2 x3 x4 x5 x6 Lado derecho Cociente ¿Es óptima?
W 1 0 0 0 - 1 0 - 1 0
x3 0 0.3 0.1 1 0 0 0 2.7
xx4 x4 0 0.5 0.5 0 1 0 0 6
x6 0 0.6 0.4 0 0 -1 1 6
W 1 1.1 0.9 0 0 -1 0 12
x3 0 0.3 0.1 1 0 0 0 2.7 2.7/0.3=9 (0,0,2.7,6,0,6)
xx4 x4 0 0.5 0.5 0 1 0 0 6 6/0.5=12 W = 12
x6 0 0.6 0.4 0 0 -1 1 6 6/0.6=10
W 1 0 0.53 -3.66 0 -1 0 2.1
x1 0 1 0.33 3.33 0 0 0 9 9/0.33=27.2 (9,0,0,1.5,0,0.6)
xx4 x4 0 0 0.33 -1.66 1 0 0 1.5 1.5/0.33=4.5 W = 2.1
x6 0 0 0.2 -2 0 -1 1 0.6 0.6/0.2=3
W 1 0 0 1.64 0 1.65 -2.65 0.51
x1 0 1 0 6.63 0 1.65 -1.65 8.01 8.01/1.65=4.8 (8.01,3,0,0.51,0,0)
xx4 x4 0 0 0 1.64 1 1.65 -1.65 0.51 0.51/1.65=0.30 W = 0.51
x2 0 0 1 -10 0 -5 5 3
W 1 0 0 0 -1 0 -1 0
x1 0 1 0 5 -1 0 0 7.5 (7.5,4.5,0,0,0.3,0)
xx5 x5 0 0 0 0.99 0.60 1 - 1 0.3 W = 0
x2 0 0 1 - 5.05 3 0 0 4.5 Óptima fase 1
Notemos que ya hemos obtenido una solución óptima para la fase 1 que consistió en la minimización de la suma de todas las variables artificiales. Observemos también que la función objetivo W terminó con un valor de cero en la última tabla, lo que indica que las dos variables artificiales (x4 y x6) valen cero ó tienen valores recíprocos y se cancelan mutuamente para dar cero. En nuestro caso, las dos variables artificiales valen cero ya que no se encuentran en la columna de las variables básicas en la última tabla de la primera fase. La segunda fase consiste en resolver el problema original utilizando como tabla inicial de esta fase la última tabla de la primera fase pero sin considerar la columna de las variables artificiales ya que éstas tomaron el valor de cero en la primera fase. El método símplex aplicado a la segunda fase se muestra en el siguiente conjunto de tablas:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 x x6 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 x6 Lado derecho Cociente ¿Es óptima?
Z 1 - 0.4 - 0.5 0 0 0 0 0
x1 0 1 0 5 - 1 0 0 7.5
xx5 x5 0 0 0 0.99 0.60 1 - 1 0.3
x2 0 0 1 - 5.05 3 0 0 4.5
Z 1 0 - 0.5 2 0 3
x1 0 1 0 5 0 7.5
xx5 x5 0 0 0 0.99 1 0.3
x2 0 0 1 - 5.05 0 4.5
Z 1 0 0 - 0.52 0 5.25
x1 0 1 0 5 0 7.5 (7.5,4.5,0,0,0.3,0)
xx5 x5 0 0 0 0.99 1 0.3 Z = 5.25
x2 0 0 1 - 5.05 0 4.5 Óptima fase 2
Notemos que no fue necesario aplicar propiamente el método símplex a la primera tabla de la segunda fase, ya que únicamente aplicando operaciones con matrices para tratar de llevar esta tabla a la forma apropiada para el método símplex fue suficiente para resolver el problema planteado en la segunda fase. Es necesario aclarar que no siempre ocurrirá de esta manera, es decir, si después de dejar la tabla en la forma apropiada, es necesario aplicar el método símplex, se debe aplicar como lo hemos estudiado.
Nota: Independientemente de que el problema original (real) sea de maximización o minimización, la primera fase siempre consistirá en la minimización de la suma de todas las variables artificiales.
Hasta este momento se han presentado los detalles del método símplex con la suposición de que el problema se encuentra en nuestra forma estándar(maximizar Z sujeta a las restricciones funcionales de la forma £ y restricciones de no negatividad sobre todas las variables) con bi ³ 0 para toda i = 1, 2, ..., m. En esta sección se establecerá cómo hacer los ajustes requeridos a otras formas legítimas de modelos de Programación Lineal. Se verá que todos estos ajustes se pueden hacer en el paso inicial, de manera que el resto del método símplex se aplica justo como se aprendió.
El único problema serio que introducen las otras formas de restricciones funcionales (= ó ³ ) es identificar una solución inicial básica factible. Antes, esta solución inicial se encontraba en forma muy conveniente al hacer que las variables de holgura fueran las variables básicas iniciales, donde cada una era igual a la constante no negativa del lado derecho de la ecuación correspondiente. Ahora debe hacerse algo más. El enfoque estándar que se utiliza es estos casos es la técnica de variables artificiales. Ésta construye un problema artificial más conveniente introduciendo una variable ficticia (llamada variable artificial) en cada restricción que lo requiera. Esta nueva variable se introduce sólo con el fin de que sea la variable básica inicial para esa ecuación. Las restricciones usuales de no negatividad también se aplican sobre estas variables y la función objetivo se modifica para que imponga una penalización exorbitante en el caso de que adquieran valores mayores que cero. Las iteraciones del método símplex automáticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una, hasta que todas quedan fuera de la solución; después de esto se resuelve el problema real.
Para ilustrar la técnica de las variables artificiales, primero se considerará el caso en que la única forma no estándar en el problema es la presencia de una o más restricciones en forma de igualdad.
Restricciones en forma de igualdad.
En realidad, cualquier restricción en forma de igualdad:
ai1x1 +ai2x2 + . . . + ainxn = bi
es equivalente a dos restricciones de desigualdad:
ai1x1 + ai2x2 + . . . + ainxn £ bi,
ai1x1 + ai2x2 + . . . + ainxn ³ bi
Sin embargo, en lugar de hacer esta sustitución e incrementar con ello el número de restricciones, es más conveniente usar la técnica de la variable artificial. Suponga que se modifica el problema de ejemplo presentado y resuelto en la sección anterior. El único cambio que sufre el modelo de programación lineal es que la tercera restricción, 3x1 + 2x2 £ 18, se convierte en una restricción de igualdad:
3x1 + 2x2 = 18
Aplicando la técnica de las variables artificiales se introduce una variable artificial no negativa (denotada por x5) en la última ecuación, como si fuera una variable de holgura:
3x1 + 2x2 + x5 =18
En resumen si tenemos una restricción funcional en forma de igualdad y deseamos pasarla a su forma de igualdad En resumen si tenemos una restricción funcional en forma de igualdad y deseamos pasarla a su forma de igualdad, únicamente debemos sumar una variable artificial.
Restricciones funcionales de la forma ³
Para ilustrar la manera en que la técnica de las variables artificiales maneja las restricciones de la forma ³ usaremos el siguiente ejemplo:
Minimizar Z = 0.4x1 + 0.5x2
sujeta a 0.3x1 + 0.1x2 sujeta a 0.3x1 + 0.1x2 £ 2.7
0.5x1 + 0.5x2 = 6
0.6x1 + 0.4x2 0.6x1 + 0.4x2 ³ 6
x1 ³ 0, x2 ³ 0
Notemos que la tercera restricción es del tipo ³ , por lo que para cambiarla a su forma de igualdad tendríamos que restar una variable de superávit (o de excedente), quedando de la siguiente manera:
0.6x1 + 0.4x2 - x5 = 6
Se ha restado la variable de excedente x5 (se utilizó x5 porque en la primera restricción agregamos una variable de holgura que sería x3 y en la segunda restricción agregamos también una variable artificial que sería x4; todo esto con el fin de convertir las desigualdades a su forma de igualdades) para que consuma el exceso de 0.6x1 + 0.4x2, o sea, lo que se pasa de 6. No obstante en este caso debe agregarse otra variable. Esta variable extra, llamada variable artificial se aumenta como sigue:
0.6x1 + 0.4x2 - x5 + x6 = 6
La razón de esto es que, si no se agrega la variable artificial, no se estarían cumpliendo las restricciones de no negatividad. Para comprenderlo, se dejará sin aumentar. El método símplex comienza por hacer todas las variables reales (originales) iguales a cero. Entonces:
0.6x1 + 0.4x2 - x5 = 6
Sea x1 = 0 y x2 = 0, entonces:
- x5 = 6
ó x5 = - 6 (que no cumple la restricción de no negatividad)
La variable artificial opera para mantener todas las variables no negativas cuando 0.6x1 + 0.4x2 es menor que 6. Si x1 = 0 y x2 = 0, entonces x5 = 0 y
0.6x1 + 0.4x2 - x5 + x6 = 6
x6x6 = 6
En resumen, una restricción de la forma ³ se convierte a su forma de igualdad restando una variable de excedente y sumando una variable artificial.
Consideremos el siguiente problema:
MaximizarZ=3x1+5x2
sujeta a x1 sujeta a x1 £ 4
2x2 £ 12
3x1 + 2x2 3x1 + 2x2 = 18
x1 ³ 0, x2 ³ 0
Como explicamos anteriormente, para resolver este problema, debemos construir un problema artificial que tiene la misma solución óptima que el problema real, haciendo dos modificaciones a este problema real.
1. Se aplica la técnica de las variables artificiales introduciendo una variable artificialno negativa (denotada por x5) en la última ecuación, como si fuera una variable de holgura:
3x1 + 2x2 + x5 =18
2. Se asigna una penalización enorme al hecho de tener x5 > 0, cambiando la función objetivo
Z = 3x1 + 5x2 a:
Z = 3x1 + 5x2 - Mx5,
donde M simbólicamente representa un número positivo muy grande. Este método que fuerza a x5 hasta el nivel de x5 = 0 en la solución óptima se llama método de la M.
Nota: Para el caso de minimización, penalizamos a la variable artificial, haciéndola aparecer en la función objetivo con un coeficiente de +M.
Ahora se encuentra la solución óptima para el problema real aplicando el método símplex al problema artificial.
Como x5 juega el papel de la variable de holgura en la tercera restricción del problema artificial, esta restricción es equivalente a 3x1 + 2x2 Como x5 juega el papel de la variable de holgura en la tercera restricción del problema artificial, esta restricción es equivalente a 3x1 + 2x2 £ 18.
En particular, el sistema de ecuaciones después de aumentar el problema artificial (en otras palabras, pasarlo a su forma de igualdades) es:
Maximizar Z,
sujeta a
Z - 3x1 - 5x2 + Mx5 = 0
x1 + x3 x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + x5 3x1 + 2x2 + x5 = 18
xj ³ 0 Para j = 1, 2, , 5
En este momento estamos preparados para pasar los coeficientes a la tabla símplex:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 -3 -5 0 0 M 0
x3 0 1 0 1 0 0 4
xx4 x4 0 0 2 0 1 0 12
x5 0 3 2 0 0 1 18
Esta tabla todavía no está en la forma apropiada porque el coeficiente de x5 es diferente de cero en la ecuación de Z (es M). Por lo tanto, antes de que el método símplex pueda aplicar la prueba de optimalidad y encontrar la variable básica entrante, debe pasarse esta tabla a la forma apropiada para que cumpla la condición símplex. Esta condición que debe cumplir toda tabla del método símplex para que pueda reportarnos la siguiente solución básica factible dice que: Toda variable básica debe tener un 1 en la intersección de su renglón y columna correspondiente y cero en los demás renglones incluido el renglón de Z, en otras palabras, que toda variable que sea básica solamente debe aparecer en el renglón de la restricción que representa. Para hacer cero el coeficiente M, utilizamos el renglón de x5 como renglón pivote multiplicándolo por - M y sumando el resultado al renglón de Z. Realizando el procedimiento anterior, la tabla símplex queda de la siguiente manera:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 -3M-3 -2M-5 0 0 0 - 18M - M x5 + Z
xx3 x3 0 1 0 1 0 0 4 (0, 0, 4, 12, 18)
x4 0 0 2 0 1 0 12 Z = - 18M
xx5 x5 0 3 2 0 0 1 18
Podemos observar que la tabla anterior ya se encuentra en la forma apropiada y podemos leer la solución básica factible actual, que es (0, 0, 4, 12, 18), la cual aplicando la prueba de optimalidad vemos que no es óptima ya que todavía tenemos coeficientes negativos en el renglón de Z (los correspondientes a x1 y x2). Aplicando el método símplex a la tabla anterior tenemos: el coeficiente negativo con el mayor valor absoluto corresponde a x1 ( - 3M - 3), recordemos que M es un número muy grande positivo, por lo tanto, x1 se convierte en la variable básica entrante, realizando los cocientes correspondientes, vemos que x3 se convierte en la variable básica saliente. El procedimiento completo para resolver este ejemplo se muestra en el siguiente conjunto de tablas:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 -3M-3 -2M-5 0 0 0 - 18M
x3 0 1 0 1 0 0 4 4/1 = 4 (0, 0, 4, 12, 18)
xx4 x4 0 0 2 0 1 0 12 Z = - 18M
x5 0 3 2 0 0 1 18 18/3 = 6
Z 1 0 -2M-5 3M+3 0 0 - 6M+12
x1 0 1 0 1 0 0 4 (4, 0, 0, 12, 6)
xx4 x4 0 0 2 0 1 0 12 12/2 = 6 Z = - 6M+12
x5 0 0 2 - 3 0 1 6 6/2 = 3
Z 1 0 0 - 9/2 0 M+5/2 27
x1 0 1 0 1 0 0 4 4/1 = 4 (4, 3, 0, 6, 0)
xx4 x4 0 0 0 3 1 - 1 6 6/3 = 2 Z = 27
x2 0 0 1 - 3/2 0 1/2 3
Z 1 0 0 0 3/2 M+1 36
x1 0 1 0 0 - 1/3 1/3 2 (2, 6, 2, 0, 0)
xx3 x3 0 0 0 1 1/3 - 1/3 2 Z = 36
x2 0 0 1 0 1/2 0 6 Óptima
MINIMIZACIÓN con el método símplex.
Una manera directa de minimizar Z con el método símplex es cambiar los roles de los coeficientes negativos y positivos en el renglón de la función objetivo, tanto para la prueba de optimalidad como para la parte 1 de una iteración. Se determina la variable básica entrante mediante la elección de la variable con el coeficiente positivo menor en la ecuación de Z. La solución básica factible actual es óptima si y sólo si todos los coeficientes de la ecuación de la función objetivo (renglón de Z) son no positivos ( £ 0 ). Si es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la nueva solución básica factible, lo que significa el cambio de una variable no básica por una básica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución (parte 3). Notemos que no se ha dicho nada con respecto a la forma de obtener la variable básica saliente Una manera directa de minimizar Z con el método símplex es cambiar los roles de los coeficientes negativos y positivos en el renglón de la función objetivo, tanto para la prueba de optimalidad como para la parte 1 de una iteración. Se determina la variable básica entrante mediante la elección de la variable con el coeficiente positivo menor en la ecuación de Z. La solución básica factible actual es óptima si y sólo si todos los coeficientes de la ecuación de la función objetivo (renglón de Z) son no positivos ( £ 0 ). Si es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la nueva solución básica factible, lo que significa el cambio de una variable no básica por una básica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución (parte 3). Notemos que no se ha dicho nada con respecto a la forma de obtener la variable básica saliente en una iteración, ya que este paso se realiza de la misma manera que cuando se está maximizando, es decir, se escoge aquella variable básica con el menor cociente. Ilustremos la forma de utilizar el método símplex para el caso de minimización. Consideremos el siguiente ejemplo:
Minimizar Z = 3x1 + 8x2
sujeta a x1 + 4x2 sujeta a x1 + 4x2 £ 4
x1 + 2x2 ³ 2
x1 ³ 0, x2 ³ 0 x1 ³ 0, x2 ³ 0
Pasando este problema a su forma de igualdades añadiendo las variables necesarias, obtenemos lo siguiente:
Minimizar Z,
sujeta a
Z - 3x1 - 8x2 - Mx5 = 0
x1 + 4x2 + x3 x1 + 4x2 + x3 = 4
x1 + 2x2 - x4 + x5 = 2
xj xj ³ 0 para j = 1, 2, , 5
Utilizando el método de la M para obtener una solución óptima por el método símplex, obtenemos el siguiente conjunto de tablas:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 Lado derecho Cociente ¿Es óptima?
Z 1 - 3 - 8 0 0 - M 0
x3 0 1 4 1 0 0 4
xx5 x5 0 1 2 0 - 1 1 2
Z 1 M - 3 2M - 8 0 - M 0 2M (0, 0, 4, 0, 2)
x3 0 1 4 1 0 0 4 4/1 = 4 Z = 2M
xx5 x5 0 1 2 0 - 1 1 2 2/1 = 2
Z 1 0 - 2 0 - 3 - M+3 6 (2, 0, 2, 0, 0)
x3 0 0 2 1 1 - 1 2 Z = 6
xx1 0 1 2 0 - 1 1 2 Óptima x1 0 1 2 0 - 1 1 2 Óptima
Notemos que la primera tabla no se encontraba en la forma apropiada para el método símplex, ya que el coeficiente de la variable básica x5 era de - M en el renglón de Z, lo cual hacia que no se cumpliera la condición símplex.
Método de las dos Fases.
En el ejemplo presentado en la sección Restricciones funcionales de la forma ³, recordemos la función objetivo real:
Problema real: Minimizar Z = 0.4x1 + 0.5x2
Sin embargo, el método de la M utiliza la siguiente función objetivo a través de todo el procedimiento:
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
Como los dos primeros coeficientes (0.4 y 0.5) son despreciables comparados con M, el método de dos fases puede eliminar la M usando las siguientes dos funciones objetivo que definen Z de manera completamente diferente:
Método de las dos fases:
Fase 1: Minimizar Z = x4 + x6 (hasta que x4 = 0 y x6 = 0).
Fase 2: Minimizar Z = 0.4x1 + 0.5x2 (con x4 = 0 y x6 = 0).
La función objetivo de la fase 1 se obtiene dividiendo la función objetivo del método de la M entre M eliminando los términos despreciables, en otras palabras, la fase 1 consiste en la minimización de la suma de todas las variables artificiales que se introduzcan en el problema. Como la fase 1 concluye al obtener una solución básica factible para el problema real (aquella en la que x4 = 0 y x6 = 0), esta solución se usa como la solución básica factible inicial para aplicar el método símplex al problema real (con su función objetivo) en la fase 2. Antes de resolver el ejemplo de esta manera se hará un resumen de las características generales.
Resumen del método de dos fases.
Paso inicial: Se revisan las restricciones del problema original introduciendo variables artificiales según se necesite para obtener una solución básica factible inicial obvia para el problema artificial.
Fase 1: uso del método símplex para resolver el problema de programación lineal:
Minimizar Z = S de todas las variables artificiales, sujeta a las restricciones revisadas.
La solución óptima que se obtiene para este problema (con Z = 0) será una solución básica factible para el problema real.
Fase 2: se eliminan las variables artificiales (de todas formas, ahora todas valen cero). Comenzando con la solución básica factible que se obtuvo al final de la fase 1, se usa el método símplex para resolver el problema real.
Enseguida se resumen los problemas que deben resolverse por el método símplex en las fases respectivas para el ejemplo.
Problema para la fase 1:
Minimizar W = x4 + x6Minimizar W = x4 + x6,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.7
0.5x0.5x1 + 0.5x2 + x4 0.5x1 + 0.5x2 + x4 = 6
0.6x1 + 0.4x2 - x5 + x6 = 6
y
x1³ 0 x2³ 0 x3³ x4³ 0 x5³ 0 x6³ 0
Problema para la fase 2:
Minimizar Z = 0.4x1 + 0.5x2Minimizar Z = 0.4x1 + 0.5x2,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.7
0.5x0.5x1 + 0.5x2 0.5x1 + 0.5x2 = 6
0.6x1 + 0.4x2 - x5 = 6
y
x1³ 0 x2³ 0 x3³ x5³ 0
Las únicas diferencias entre estos dos problemas se encuentran en la función objetivo y en la inclusión (fase 1) o exclusión (fase 2) de las variables artificiales x4 y x6. Sin las variables artificiales, el problema para la fase 2 no tiene una solución básica factible inicial obvia. El único propósito de resolver el problema para la fase 1 es obtener una solución básica factible con x4 = 0 y x6 = 0 que se pueda usar como la solución básica factible inicial para la fase 2.
Las siguientes tablas muestran el resultado de aplicar el método símplex a este problema para la fase 1:
VariableVariable Básica W x x1 x x2 x x3 x x4 x x5 x x6 LadoLado derecho Cociente ¿Es óptima? Variable Básica W x1 x2 x3 x4 x5 x6 Lado derecho Cociente ¿Es óptima?
W 1 0 0 0 - 1 0 - 1 0
x3 0 0.3 0.1 1 0 0 0 2.7
xx4 x4 0 0.5 0.5 0 1 0 0 6
x6 0 0.6 0.4 0 0 -1 1 6
W 1 1.1 0.9 0 0 -1 0 12
x3 0 0.3 0.1 1 0 0 0 2.7 2.7/0.3=9 (0,0,2.7,6,0,6)
xx4 x4 0 0.5 0.5 0 1 0 0 6 6/0.5=12 W = 12
x6 0 0.6 0.4 0 0 -1 1 6 6/0.6=10
W 1 0 0.53 -3.66 0 -1 0 2.1
x1 0 1 0.33 3.33 0 0 0 9 9/0.33=27.2 (9,0,0,1.5,0,0.6)
xx4 x4 0 0 0.33 -1.66 1 0 0 1.5 1.5/0.33=4.5 W = 2.1
x6 0 0 0.2 -2 0 -1 1 0.6 0.6/0.2=3
W 1 0 0 1.64 0 1.65 -2.65 0.51
x1 0 1 0 6.63 0 1.65 -1.65 8.01 8.01/1.65=4.8 (8.01,3,0,0.51,0,0)
xx4 x4 0 0 0 1.64 1 1.65 -1.65 0.51 0.51/1.65=0.30 W = 0.51
x2 0 0 1 -10 0 -5 5 3
W 1 0 0 0 -1 0 -1 0
x1 0 1 0 5 -1 0 0 7.5 (7.5,4.5,0,0,0.3,0)
xx5 x5 0 0 0 0.99 0.60 1 - 1 0.3 W = 0
x2 0 0 1 - 5.05 3 0 0 4.5 Óptima fase 1
Notemos que ya hemos obtenido una solución óptima para la fase 1 que consistió en la minimización de la suma de todas las variables artificiales. Observemos también que la función objetivo W terminó con un valor de cero en la última tabla, lo que indica que las dos variables artificiales (x4 y x6) valen cero ó tienen valores recíprocos y se cancelan mutuamente para dar cero. En nuestro caso, las dos variables artificiales valen cero ya que no se encuentran en la columna de las variables básicas en la última tabla de la primera fase. La segunda fase consiste en resolver el problema original utilizando como tabla inicial de esta fase la última tabla de la primera fase pero sin considerar la columna de las variables artificiales ya que éstas tomaron el valor de cero en la primera fase. El método símplex aplicado a la segunda fase se muestra en el siguiente conjunto de tablas:
VariableVariable Básica Z x x1 x x2 x x3 x x4 x x5 x x6 LadoLado derecho Cociente ¿Es óptima? Variable Básica Z x1 x2 x3 x4 x5 x6 Lado derecho Cociente ¿Es óptima?
Z 1 - 0.4 - 0.5 0 0 0 0 0
x1 0 1 0 5 - 1 0 0 7.5
xx5 x5 0 0 0 0.99 0.60 1 - 1 0.3
x2 0 0 1 - 5.05 3 0 0 4.5
Z 1 0 - 0.5 2 0 3
x1 0 1 0 5 0 7.5
xx5 x5 0 0 0 0.99 1 0.3
x2 0 0 1 - 5.05 0 4.5
Z 1 0 0 - 0.52 0 5.25
x1 0 1 0 5 0 7.5 (7.5,4.5,0,0,0.3,0)
xx5 x5 0 0 0 0.99 1 0.3 Z = 5.25
x2 0 0 1 - 5.05 0 4.5 Óptima fase 2
Notemos que no fue necesario aplicar propiamente el método símplex a la primera tabla de la segunda fase, ya que únicamente aplicando operaciones con matrices para tratar de llevar esta tabla a la forma apropiada para el método símplex fue suficiente para resolver el problema planteado en la segunda fase. Es necesario aclarar que no siempre ocurrirá de esta manera, es decir, si después de dejar la tabla en la forma apropiada, es necesario aplicar el método símplex, se debe aplicar como lo hemos estudiado.
Nota: Independientemente de que el problema original (real) sea de maximización o minimización, la primera fase siempre consistirá en la minimización de la suma de todas las variables artificiales.