Metodo Simplex

HISTORIAS SIMPLEX

El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo.

FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL

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

EJEMPLO

Max 9u + 2v + 5z

sa 4u + 3v + 6z <= 50

u + 2v - 3z >= 8

2u - 4v + z = 5

u,v >= 0

z e IR

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)

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.

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.

Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.

Considerando la siguiente 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

...