Metodo Simplex

RESUMEN:

EL MÉTODO SIMPLEX

En el año 1947 el doctor George Dantzig presentó el algoritmo que desarrolló y que denominó SIMPLEX. A partir de este logro se pudieron resolver problemas que por más de un siglo permanecieron en calidad de estudio e investigación con modelos formulados pero no resueltos. El desarrollo paralelo de la computación digital, hizo posible su rápido desarrollo y aplicación empresarial a todo tipo de problemas.

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. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo.

Actividades Fundamentales:

El método simplex consta de tres actividades fundamentales:

 Prueba de optimalidad de la solución.

 Identificación de las variables que entran y salen.

 Análisis de la tabla característica para desarrollar una nueva solución.

Procedimientos Simplex

 Estandarizar el método de programación lineal (PL).

 Construir la tabla característica.

 Identificar la variable que entra y la que sale.

 Determinar la nueva solución básica.

 Probar la optimalidad de la solución.

Para resolver un problema de maximización se realizan los siguientes pasos:

1. Convertir las desigualdades en igualdades.

2. Igualar la función objetivo a cero.

3. Escribir la tabla inicial simplex.

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base.

5. Encontrar

...