UNIDAD DIDÁCTICA: PROGRAMACIÓN LINEAL
	Curso: 2º Bachillerato de Ciencias Sociales

10.    EL ALGORITMO DEL SIMPLEX.

        Según el teorema fundamental de la Programación Lineal, si un problema de Programación Lineal tiene solución óptima finita, ésta se alcanza en un vértice de la región factible. Los vértices se obtienen como solución de sistemas de ecuaciones lineales determinados por las restricciones. Al haber un número finita de restricciones, hay también un número finito de vértices. Por tanto la solución del problema se puede obtener evaluando la función objetivo en un número finito de puntos.

Sin embargo, el número de vértices de la región factible puede ser muy grande y por tanto el cálculo de la solución óptima puede resultar bastante entretenido. Sería interesante un procedimiento que escoja unos cuantos vértices sin necesidad de trabajar con todos. Esto el lo que intenta el algoritmo del simplex descubierto por G. B. Dantzig. El nombre del método es debido a que en una de sus primeras aplicaciones, la región factible estaba formada por un "simplex", es decir, un poliedro convexo generado por (n+1) puntos de Rⁿ, no situados en una misma variedad lineal (n-1)-dimensional.

Este procedimiento parte de un vértice cualquiera y mediante algoritmos se va pasando a vértices adyacentes que mejoran el valor de la función objetivo en el vértice anterior, obteniendo la solución óptima en un número de pasos bastante inferior al de evaluar la función objetivo en todos los vértices.

Por ejemplo, supongamos que una hormiga se encuentra con la estructura de un complicado poliedro convexo y quiere subir al vértice situado en lo más alto siguiendo las aristas del poliedro. ¿Cuál es la forma más rápida de conseguirlo? Parece lógico que desde el suelo escoja la arista con más pendiente y suba por ella hasta llegar al vértice en el que finaliza. Después escoger de todas las aristas que salen de dicho vértice la que tiene mayor inclinación y subir por ella hasta un nuevo vértice. Repitiendo este procedimiento llegará al vértice más alto en el menor número de pasos posible.

El desarrollo del algoritmo del simplex se sale de los contenido del curso 2º de Bachillerato.

---

PÁGINA ANTERIOR

ÍNDICE

PÁGINA SIGUIENTE

---

1. INTRODUCCIÓN	2. PLANTEAMIENTO DIDÁCTICO	3. UN POCO DE HISTORIA	4. DEFINICIÓN Y TERMINOLOGÍA	5. TIPOS DE PROBLEMAS	6. INECUACIÓN LINEAL
7. SISTEMA DE INECUACIONES	8. MÉTODOS DE SOLUCIÓN	9. APLICACIONES	10. EL ALGORITMO DEL SIMPLEX	11. EJERCICIOS	12. BIBLIOGRAFÍA