Metodo simplex

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Linealen caso de existir esta última.
La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
El Método Simplex hace uso de la propiedad de que la solución óptima de unproblema 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 enla evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formatoestándar el cual definiremos a continuación.
FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL
Consideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que siguepor:
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 = 0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su formaestándar:
• EJEMPLO
P) Max 9u + 2v + 5z
sa 4u + 3v + 6z = 8
2u - 4v + z = 5
u,v >= 0z 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 yx* es la solución óptima f(x*) >= f(x),...