Método De La "M" O De Penalización

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”, ú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  2.7

0.5x1 + 0.5x2 = 6

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

x6 = 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:

Maximizar Z = 3x1 + 5x2

sujeta a x1  4

2x2  12

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 artificial no 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,

...