Algoritmo símplex

Un sistema de desigualdades lineales define un poliedro como una región factible. El algoritmo Símplex comienza en un vértice y se mueve a lo largo de las aristas del poliedro hasta que alcanza el vértice de la solución óptima.

En optimización matemática, el término algoritmo Símplex habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo Símplex primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. Un algoritmo Símplex es un algoritmo de pivote.

Un método llamado de manera similar, pero no relacionado al anterior, es el método Nelder-Mead (1965) o método de descenso (o ascenso) símplex; un método numérico que busca un mínimo (o máximo) local de una función cualquiera examinando en cada paso los vértices de un simplex.

El algoritmo del método Símplex fue elegido como uno de los 10 algoritmos más importantes del siglo XX (SIAM News, Volume 33, Number 4).

Entrada del problema

Considerar un problema de programación lineal,

maximizar
sujeto a

El algoritmo Símplex requiere que la matriz del problema esté en su forma aumentada. El problema puede ser descrito como sigue:

Maximizar en:

donde x son las variables desde la forma estándar, xs son las variables de holgura introducidas en el proceso de aumentación, c contiene los coeficientes de optimización, describe el sistema de ecuaciones contraídas, y Z es la variable a ser maximizada.

El sistema está típicamente no determinado, ya que el número de variables excede el número de ecuaciones. La diferencia entre el número de variables y el número de ecuaciones nos da los grados de libertad asociados al problema. Cualquier solución, óptima o no, incluirá un número de variables de valor arbitrario. El algoritmo Símplex usa cero como valor arbitrario, y el número de variables con valor cero es igual a los grados de libertad.

Las variables con valores diferentes de cero serán llamadas "variables básicas", las demás "variables no básicas".

Esta forma simplifica el encontrar la solución factible básica inicial, dado que todas las variables de la forma estándar pueden ser elegidas para ser no básicas (cero), mientras que todas las nuevas variables introducidas en la forma aumentada, serán básicas (diferentes de cero), dado que su valor puede ser calculado trivialmente ( para ellas, dado que la matriz problema aumentada en diagonal es su lado derecho)

En cada una de las desigualdades que se plantean en el modelo matemático de programación lineal, se plantean desigualdades de <, >, ≤, ≥ o =; estas desigualdades se convierten en igualdades completando con variables de holgura si se trata de menor o igual que, o menor que; en el caso de que sea mayor o igual que o mayor que, se completa con variables de excedente, estas con signo negativo ya que como su nombre lo indica, es una cantidad que esta de excedente y hay que quitar para convertirla en igualdad; en caso se maneje el =, se manejan las variables artificiales.

Other Languages