Unidad Dos: Método Simplex

 
George Dantzing (creador del MS)

Teoría del método Simplex.
Forma tabular del método Simplex.


La forma estándar
1.    Variables de holgura: toda restricción lineal de la forma ∑aij Xi ≤ bi para convertirla en una igualdad es necesario sumar una nueva variable no negativa con el término de la izquierda de la desigualdad, de tal manera que esta absorba la diferencia entre el termino de la derecha y de la izquierda. A esta nueva variable se le llama variable de holgura.
Ejemplo:
         La restricción: 3X1 + 5X2 ≤ 50
         Se debe escribir: 3X1 + 5X2 + X3 = 50
         Dónde: X1 y X2 son variables reales  y X3  es variable de holgura
Sea:        X1 = 5      X2 = 4        X3 = 15
               X1 = 5      X2 = 7        X3 = 0
Nota: la variable no siempre tomará valores

2.    Variables superfluas: toda restricción lineal de la forma ∑aij Xi ≥ bi se puede convertir en igualdad restando una nueva variable no negativa al término de la izquierda de la desigualdad, de tal manera que absorba la diferencia entre el término de la izquierda y el de la derecha. A esta nueva variable se le llama variable superflua.
Ejemplo:
La restricción: 2X1 + X2 + 6X3 ≥ 48
Se debe escribir: 2X1 + X2 + 6X3 – X=48
Dónde: X1, X2 y X3 son variables reales  y X4  es variable superflua
Sea:        X1 = 10      X2 =10        X3 = 5    X4 = 12
       X1 = 10      X2 =10        X3 = 3    X4 = 0
Nota: la variable no siempre tomará valores

3.    Variables artificiales: después de que todas las restricciones normales se han convertido en igualdades, agregando variables de holgura y superfluas, ahora, agréguese una nueva variable en el lado izquierdo de la igualdad en aquella restricción que no aparezca una variable de holgura. Esta nueva variable recibe el nombre de variable artificial.


COSTOS DE PENALIZACIÓN
Las variables de holgura y superfluas no alteran ni a la naturaleza de las restricciones ni al objetivo del problema, por consiguiente se incorporan a la función objetivo con coeficiente cero; en cambio, las variables artificiales si alteran al conjunto de restricciones, ya que solo se agregaron de un solo lado. El nuevo sistema de restricciones es equivalente al anterior si las variables artificiales son cero. Para garantizar esto en la solución óptima, comparada con la solución inicial, las variables artificiales se incorporan a la función objetivo con coeficientes negativos muy grandes si el problema es de maximizar o con coeficientes positivos muy grandes si el problema es de minimizar. Estos coeficientes se suelen representar por –M o M, donde M se considera un número muy grande que representa el costo de penalización en que se ha caído al hacer una asignación unitaria en las variables artificiales.

Forma estándar
Un programa lineal está en forma estándar si todas las restricciones son igualdades y si se conoce una solución inicial factible. En la forma matricial la forma estándar se expresa:
Optimícese        X0 = CX
                               Sujeto a:
                                      
                               AX = B
                               X 0
Donde:
CT = coeficientes del costo o utilidad
X  = vector del conjunto de variables
A  = matriz de los coeficientes de las variables en las restricciones
B  = vector columna de lados derechos de las restricciones

LA TABLA SIMPLEX
El método simplex es un procedimiento matricial para resolver programas lineales expresados en la forma estándar. Para programas de optimización el método simplex utiliza la siguiente tabla en la cual C0 designa el vector del costo asociado con las variables X0.







Para problemas de maximización a los términos del último renglón, excepto la última columna, se le cambian signos.

El procedimiento del método simplex está basado en los siguientes pasos:

Paso 1: localizar el número más negativo del último renglón, excluyendo la última columna, a la columna donde se encuentre este número se le llama columna de trabajo, si existen más de un número negativo que sean iguales, se selecciona arbitrariamente solo uno.
Paso 2: dividir cada número de la última columna entre el elemento en el mismo renglón y en la columna de trabajo (únicamente números positivos). Al elemento de la columna de trabajo que dé la razón más pequeña se le denomina elemento pivote. Si hay números negativos únicamente en la columna de trabajo el problema NO TIENE SOLUCIÓN.
Paso 3: mediante operaciones elementales de renglones, convertir al elemento pivote en 1 y los demás elementos de la columna de trabajo en ceros.
Paso 4: reemplácese la variable Xi en el renglón pivote y en la primera columna por la variable Xi en el primer renglón y en la columna pivote, esta nueva primera columna contiene al conjunto de variables básicas.
Paso 5: repítanse los pasos del 1 al 4 hasta que el último renglón, excluyendo la última columna no queden números negativos.
Paso 6: la solución óptima se obtiene asignando a cada variable de la primer columna aquel valor en el renglón correspondiente y en la última columna. A todas las otras variables se les asigna el valor cero. El valor asociado X0*, último valor óptimo de la función objetivo es el número en el último renglón y última columna para un programa de maximización, pero es el negativo de ese número para uno de minimización.

MODIFICACIONES PARA PROGRAMAS QUE CONTIENEN VARIABLES ARTIFICIALES

Siempre que un programa contiene variables artificiales el último renglón de la tabla simplex contendrá el costo penal M, para evitar errores de redondeo se añaden los siguientes cambios:

Cambio 1: el último renglón de la tabla se descompone en dos reglones, el primer renglón comprende a aquellos términos que no contienen a M y el segundo a los coeficientes de M.
Cambio 2: se aplica el paso 1 del método simplex al último renglón generado en el cambio 1, seguido por los pasos 2, 3 y 4, hasta que el último renglón no contenga elementos negativos entonces se aplica el paso 1 a los elementos del penúltimo renglón que se encuentran situados sobre ceros en el último renglón.
Cambio 3: siempre que una variable artificial deja de ser básica, es decir, que se quita de la primer columna como resultado del paso 4 se elimina del renglón superior de la tabla al igual que toda la columna debajo de ella.
Cambio 4: el último renglón de la tabla puede eliminarse siempre que todos sus elementos sean ceros.
Cambio 5: si el conjunto básico final contiene variables artificiales diferentes de cero, el problema no tiene solución. En cambio cuando una o más de las ecuaciones de restricción originales es redundante, las variables artificiales de valor cero aparecen como variables básicas.