Metodo Simplex

Método Simplex.
Variables de holgura: Siempre positivas, hacen que una restricción que sea desigualdad se transforme en igualdad, y sus coeficientes en la función objetivo son ceros. Variables ficticias o artificiales: Sirven para hallar fácilmente una solución básica inicial, sus coeficientes en la función objetivo son w si es minimización o -w si es maximización; w es un número mucho mayor quetodos los participantes. Luego de sumar las variables de holgura y/o artificiales necesarias para convertir las desigualdades en igualdades y para obtener los vectores unitarios (de la matriz identidad) para la base inicial se procede a ordenar los datos en una tabla Simples; después se prueba la solución para ver si es óptima, si no es óptima se realiza el siguiente procedimiento: Se calculanlos valores de zj multiplicando los coeficientes de la base por cada columna, uno a uno, y sumando esos resultados. Luego se calculan los valores de zj - cj; si es minimización el valor más grande de zj - cj designa a la columna clave, y si es maximización el valor más pequeño de zj - cj designa a la columna clave. Se calculan las razones entre la cantidad solución y sus correspondientes de lacolumna clave, para los valores positivos de la cantidad solución; el valor mínimo de estas razones designa a la fila clave. El elemento que se encuentra en la intersección de la columna clave con la fila clave se llama pivote. El vector de la fila clave se reemplaza por el de la columna clave en la base, luego se transforma la matriz ampliada (A | B) para que el pivote sea igual a 1 y los demáselementos de ese vector sean ceros; y se ordenan nuevamente estos datos en una tabla Simples.

La solución óptima se reconoce cuando la cantidad solución tiene sólo cantidades no negativas; si es minimización los valores de zj - cj son todos no positivos, y si es maximización los valores de zj - cj son todos no negativos.

Ejemplo 1
Minimizar C = 2x1 + 10x2 sujeta a 2x1 + x2 ≤ 6 5x1 + 4x2 ≥ 20 x1,x2 ≥ 0 En este caso son necesarias dos variables de holgura, x3 y x4, al agregarlas el problema queda: Minimizar C = 2x1 + 10x2 + 0x3 + 0x4 sujeta a 2x1 + x2 + x3 = 6 5x1 + 4x2 - x4 = 20 x1, x2 ≥ 0 ⎛2 1 1 0 6 ⎞ La matriz ampliada (A, B) queda ( A, B ) = ⎜ ⎜ 5 4 0 − 1 20 ⎟ ⎟ ⎝ ⎠ Es necesario agregar la variable artificial x5 para obtener lo siguiente: Minimizar C = 2x1 + 10x2 + 0x3 + 0x4 + wx5sujeta a 2x1 + x2 + x3 = 6 5x1 + 4x2 - x4 + wx5 = 20 x1, x2 ≥ 0 P1 P2 P3 P4 P5 ⎛2 1 1 0 0 6 ⎞ Se tiene la matriz ampliada ( A, B ) = ⎜ ⎜ 5 4 0 − 1 1 20 ⎟ , luego la base inicial es {P3, P5}. ⎟ ⎝ ⎠ Tabla Simplex N°1 Cj 2 10 Base P1 P2 0 P3 1 2 w P5 5 4 Zj 5w 4w Zj - Cj 5w - 2 4w - 10 0 P3 1 0 0 0 0 P4 0 -1 -w -w w P5 Cantidad solución 0 6 1 20 w 20w 0

Base inicial {P3, P5} Solución inicial {(6,20)} Zj - Cj máximo = 5w – 2, por lo que entra P1 a la base ⎧ 6 20 ⎫ 6 Mínimo ⎨ , ⎬ = , luego sale P3 de la base ⎩2 4 ⎭ 2 Pivote = 2 Calculando las nuevas entradas de la tabla Simplex:

0 0 3⎞ ⎛ 2 1 1 0 0 6 ⎞ (1/2) ⎛ 1 1 / 2 1 / 2 0 0 3 ⎞ (- 5) ⎛ 1 1 / 2 1 / 2 ⎜ ⎟ ⎟ ~⎜ ~⎜ ⎜ 5 4 0 − 1 1 20 ⎟ ⎜5 4 ⎜ 0 3 / 2 − 5 / 2 − 1 1 5⎟ ⎟ 0 − 1 1 20 ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

Tabla Simplex N°2 Cj 2 10 0 Base P1 P2 P3 2 P11 1/2 1/2 w P5 0 -5/2 3/2 Zj 2 1 + (3/2)w 1 – 5/2(w) Zj - Cj 0 -9 + (3/2)w 1 – 5/2(w) 0 P4 0 -1 -w -w w P5 Cantidad solución 0 3 1 5 w 6 + 5w 0

Nueva base {P1, P5} Solución {(3, 5)} Zj - Cj máximo = -9 + (3/2)w, por lo que entra P2 a la base 5 ⎫ 5 ⎧ 3 Mínimo ⎨ , luego sale P5 de la base , ⎬= ⎩1 / 2 3 / 2 ⎭ 3 / 2 Pivote = 3/2 Calculando las nuevas entradas de la tabla Simplex: ⎛1 ⎜ ⎜0 ⎝ ⎛1 ⎜ ⎜0⎝ 1/ 2 0 0 3⎞ 0 0 3 ⎞ ⎛ 1 1/ 2 1/ 2 ⎟ ⎟ (2/3) ~ ⎜ 0 1 − 5 / 3 − 2 / 3 2 / 3 10 / 3 ⎟ (- 1/2 ) ~ ⎜ ⎟ 3 / 2 − 5 / 2 − 1 1 5⎠ ⎝ ⎠ 0 4/3 1/ 3 − 1/ 3 4 / 3 ⎞ ⎟ 1 − 5 / 2 − 2 / 3 2 / 3 10 / 3 ⎟ ⎠ 1/ 2

Tabla Simplex N°3 2 Base P1 2 P1 1 10 P2 0 Zj 2 Zj - Cj 0 Cj 10 P2 0 1 10 0 0 P3 4/3 -5/3 -14 -14 0 w P4 P5 Cantidad solución 1/3 -1/3 4/3 -2/3 2/3 10/3 -6 6 36 -6 6 - w

Por lo tanto la solución...