Algoritmo S Mplex

Algoritmo símplex
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 simplex primal fue desarrollado por el matemáticonorteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. Un algoritmo simplex 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 losvértices de un simplex
Entrada del problema
Considerar un problema de programación lineal,
maximizar
sujeto a
El algoritmo símplex requiere que el problema de programación lineal esté en la forma aumentada de la programación lineal. El problema puede ser escrito como sigue, en forma de matriz:
Maximizar en:


donde x son las variables desde la forma estándar, xs son las variables de holguraintroducidas 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 es típicamente no determinado, desde 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 con el 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.
Valores diferentes de cero son llamados variables básicas, y valores de cero son llamadas variables no básicas en el algoritmo símplex.
Esta forma simplifica encontrar la solución factiblebá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, son 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 seplantean 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 cantidadque esta de excedente y hay que quitar para convertirla en igualdad; en caso se maneje el =, se manejan las variables artificiales.
Pasos del Método Simplex
Este proceso que se repite una y otra vez, siempre inicia en un punto extremo de la región factible que normalmente es el origen, en cada iteración se mueve a otro punto extremo adyacente hasta llegar a la solución óptima.
Los pasos delMétodo Simplex son los siguientes:
1. Utilizando la forma estándar, determinar una solución básica factible inicial igualando a las n-m variables igual a cero (el origen).
2. Seleccionar la variable de entrada de las variables no básicas que al incrementar su valor pueda mejorar el valor en la función objetivo. Cuando no exista esta situación, la solución actual es la óptima; si no, ir al siguientepaso.
3. Seleccionar la variable de salida de las variables básicas actuales.
4. Determinar la nueva solución al hacer la variable de entrada básica y la variable de salida no básica, ir al paso 2 (actualizar).
EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es...