Temas I.O

1. Método Simplex Dual
El método simplex dual está basado en la teoría de la dualidad que dice que cada problema de programación lineal tiene un segundo problema asociado con él. Uno se denomina primal y el otro dual. Se puede considerar que el método simplex dual es la imagen en un espejo del método simple
El método simplex dual es muy útil en algunas situaciones especiales. Lo normal es quesea más fácil encontrar una solución inicial básica que sea factible, que una factible dual, aunque en ocasiones es necesario introducir muchas variables artificiales para construir una solución inicial básica factible artificialmente
Las reglas para el método simplex dual son muy parecidas a las del método simplex, de hecho, una vez que los métodos se inician, la única diferencia entre ellos esel criterio para elegir las variables básicas que entran y salen y la regla para detener el algoritmo.

Ejemplo de método simplex dual en forma de maximización:
Z= – 4y1 – 12y2 – 18y3
Sujeto a:
Y1+3y3 ≥ 3
2y2 +2y3 ≥ 5
y1, y2 ,y3 ≥ 0

Como ahora se permiten valores negativos en el lado derecho, no es necesario introducir variables artificiales como variables básicas iniciales. En sulugar, solo se convierten las restricciones funcionales a la forma ≤ y se introducen las variables de holgura para que desempeñen este papel. El conjunto inicial de ecuaciones se muestra en la iteración 0 de la tabla 7.1 Observe que todos los coeficientes de la ecuación (0) son negativos, con lo que la solución es óptima si es factible. La solución básica inicial es y1=0, y2=0, y3=0, y4= -3, y5 =-5 con z= 0, que no es factible porque tiene valores negativos. La variable básica que sale es y5 (5>3), y la variable básica entrante es y2 (12/2<18/2), lo que conduce al segundo conjunto de ecuaciones que se muestra como la iteración 1 de la tabla 7.1. La solución básica correspondiente es y1=0, y2= 5/2, y3=0, y4= -3, y5=0, con z=-30 que no es factible. La siguiente variable básica quesale es y4 y la que entra es y3 (6/3 < 4/1), por lo que da lugar al conjunto final de ecuaciones presentado en la tabla 7.1. La solución básica correspondiente es y1=0, y2= 3/2, y3=1 y4= 0 y5=0, con Z= -36 que es factible y por lo tanto óptima. Note que la solución óptima para el dual de este problema es x1=2 x2=6 x3=2 x4=0 5=0 que es la misma que se obtuvo en la tabla 4.8 mediante el métodosimplex

2. Método Simplex en dos fases
Su nombre comúnmente se abrevia a Método de las dos fases y se considera un método alternativo al método de las M en la resolución del problema aumentado (PA) del problema original (PO). Desde un punto de vista computacional, este método presenta varias ventajas sobre el método de la M Desde un punto de vista computacional, este método presenta variasventajas sobre el método de las M
La idea general de este método es muy simple y consiste en que el problema de Programación Lineal se resuelve en dos partes o fases. Primero, en el PA se trata de que todas las variables artificiales lleguen a nivel cero, con lo cual seguramente se arribaran a una SBFI de Problema Original. Y segundo, a partir de la SBFI del PO, si es que se obtuvo, se trata deencontrar la solución óptima del PO. A la primera parte se le llama Fase I y a la segunda Fase II.
Fase I.
En esta primera fase se trata exclusivamente de expulsar a las VA fuera de la base del PA, lo cual equivale a buscar una SBFI para el PO; en realidad, se está llevando a cabo formalmente el paso 1 del método simplex original. Para obligar a que las variables VA tomen valor de cero no se recurre,como en el método de las M, a una penalización en el objetivo, sino al planteamiento de un nuevo objetivo, el cual consiste en minimizar
Fase II.
La segunda fase es la resolución del PO a partir de la SBFI encontrada en la fase I, si es que se encontró una. Esta fase equivale a los pasos 2 y 3 del método simplex original. La función objetivo, al ser optimizada, es ahora por lo que la última...