Medoto Simplex Resumen

METODO SIMPLEX

El Método Simplex es un método analítico de solución de problemas deprogramación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

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 devariables que satisfaga un conjunto de inecuaciones lineales. El algoritmo simplex primal fue desarrollado por el matemático norteamericano 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 cualquieraexaminando en cada paso los vértices de un simplex .

ENTRADA DEL PROBLEMA

Considerar un problema de programación lineal,

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:

donde x son las variables desde la forma estándar, x s 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.

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.

ALGORITMO DEL METODO 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 del Mé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 estasituación, la solución actual es la óptima; si no, ir al siguiente paso.

3. Seleccionar la variable de salida de las variables básicas actuales.

4. Determinar la nueva solución al hacer la variable de entrada

...