Método Simplex

INTRODUCCIÓN

En la teoría de optimización, El Método 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étodonumé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: un segmento de línea sobreuna línea, un triángulo sobre un plano, un tetraedro en un espacio de tres dimensiones y así sucesivamente.
El método Simplex es un método secuencial de optimización, es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, elmétodo consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
Hasta ahora se han resuelto problemas de programación lineal a través de un método geométrico. Estemétodo no resulta práctico cuando el número de variables se aumenta a tres, y con más variables resulta imposible de utiliza; el método simplex, cuyo nombre está asociado en análisis más avanzados a un objeto geométrico al que se denomina simplex.
El método comienza con una solución factible y prueba si es o no óptima. Si no lo es, el método sigue a una mejor solución. Se dice mejor en el sentidode nueva solución no es óptima, entonces se repite el procedimiento. En algún momento el método simplex conduce a una solución óptima, si es que existe.
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ólotrabaja 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. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "=" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.
Además de ser eficiente, dicho método tiene otrasventajas. Es completamente mecánico (se utilizan matrices, operaciones elementales sobre renglones y aritmética básica). Asimismo, no implica el uso de geometría. Esto permite resolver problemas de programación lineal que tiene cualquier número de restricciones y variables.
Vale nombrar algunos Aspectos Fundamentales del Método Simplex, como son:
1. Encuentra una solución óptima
2. Es unmétodo de cambio de bases
3. Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como coeficiente 0
4. Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción.

ANTECEDENTES HISTICOS DE LA INVESTIGACIÓN DE OPERACIONES Y EL MÉTODO SIMPLEX.

A lo largo de la historia es frecuente encontrarse con la colaboración entrecientíficos y militares con el fin de dictaminar la decisión óptima en la batalla. Es por esto que muchos expertos consideran el inicio de la Investigación Operativa en el siglo III A.C., durante la II Guerra Púnica, con el análisis y solución que Arquímedes propuso para la defensa de la ciudad de Siracusa, sitiada por los romanos. Entre sus inventos se encontraban la catapulta, y un...