Algoritmo de metodo simplex

ALGORITMO DEL MÉTODO SIMPLEX

En la teoría de optimización, el algoritmo símplex , descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Un método sin relación, pero llamado de manera similar, es el método Nelder-Mead o método símplex cuesta abajo, debido a Nelder y Mead (1965),que es un método numérico para optimización de problemas libres multidimensionales, perteneciente a la clase más general de algoritmos de búsqueda. El que permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono.

En ambos casos, el método usa el concepto de un símplex, que es un politopo de N + 1 vértices en N dimensiones: unsegmento de línea sobre una línea, un triángulo sobre un plano, un tetraedro en un espacio de tres dimensiones y así sucesivamente.
Entrada del problema
Considerar un problema de programación lineal,
maximizar
sujeto a
El algoritmo simplex 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 dematriz:
Maximizar Z 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 es típicamente no determinado, desde que el número de variables excede el número de ecuaciones. Ladiferencia 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 valoresde cero son llamadas variables no básicas en el algoritmo simplex.
Esta forma simplifica 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, 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 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 mayorque, 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.

EJEMPLO DE MÉTODO SIMPLEX

Resolver mediante el método simplex el siguiente problema:
Maximizar | Z = f(x,y) = 3x + 2y |
sujeto a: | 2x + y ≤18 |
  | 2x + 3y ≤ 42 |
  | 3x + y ≤ 24 |
  | x ≥ 0 , y ≥ 0 |
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + r = 18 |
2x + 3y + s = 42 |
3x +y + t = 24 |

2. Igualar la funciónobjetivo a cero
- 3x - 2y + Z = 0 |
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables básicas del problema y las variables de holgura/exceso. En las filas se observan, para cada restricción las variables de holgura con sus coeficientes de las igualdades obtenidas, y la última fila con los los valores resultantes de sustituir el valor de cada variable en la...