Metodo simplexx

Referencia: Publicación del Método por George Dantzig en 1947. Primera implementación computacional del Método Simplex el año 1952 en un problema de 71 variables y 48 ecuaciones, tarda 18 horas. En 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
Consideremos un modelo de Programación Lineal en su forma estandar, quedenotaremos en lo que sigue por:
Min          c1x1  + c2x2  + ... + cnxn
sa            a11x1 + a12x2 + ... + a1nxn = b1
                a21x1 + a22x2 + ... + a2nxn = b2
                ...          ...                  ...
                am1x1 + am2x2 + ... + amnxn = bm
                xi >=  0,   i = 1, 2, ..., n    y    m <= n

Matricialmente escrito como:

Min         cTxsa            Ax = b
                x >=  0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar.

EJEMPLO

P)            Max        9u + 2v + 5z
                sa            4u + 3v + 6z <=  50
                                u + 2v - 3z >=  8
                               2u – 4v + z = 5
                               u,v >=  0                               z e IR
1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia:  x* es también mínimo de  -f(x)
2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una(nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.
3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
Considerando lasiguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como: 

Min         - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
sa:              4x1 + 3x2 + 6x3 - 6x4 +    x5          = 50
                     x1 + 2x2 - 3x3 + 3x4             - x6  =  8
                   2x1 - 4x2 +  x3   -   x4                     =  5                   xi >=  0,    i=1,2,3,4,5,6.  
Ejemplo
|
Anuncios Google | |   Francis X1 |   Voggel |   Lineal Grate |   The Hillier |
|
Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

Max     40*X1 + 60*X2
s.a.     2*X1 + 1*X2 <= 70
            1*X1 + 1*X2 <= 40
            1*X1 + 3*X2 <= 90
             X1 >= 0  X2 >= 0
    
Para poderaplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:

 X1 |  X2 |  X3 |  X4 |  X5 |   |
 2 | 1  | 1  |  0 |  0 | 70  |
 1 | 1  | 0  | 1  | 0  | 40  |
 1 | ..... 3 | 0  |0  | 1  | 90  |
 -40 | -60  | 0  | 0 |  0 |  0 |

En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso,X2. 

Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable...