• Unidad I

Método Simplex

Antes de hablar del Método Simplex, es necesario conocer en qué consiste la Programación Lineal, con cuyo nombre se identifica esta asignatura. La misma tuvo su origen después de la Segunda Guerra Mundial. Específicamente, en 1947, cuando el profesor, físico y matemático estadounidense Geoge Dantzing desarrolló investigaciones y aplicaciones para resolver problemas en distintos casos de operación militar que llevaba a cabo su país. Se puede decir que es una herramienta aplicable a diversos campos de optimización matemática, lo que significa que es un método que intenta maximizar o minimizar un objetivo establecido, como por ejemplo la maximización de utilidades o la reducción de los costos, razón por la cual, se la considera una herramien1a fundamental, pues, mediante su aplicación, se obtienen soluciones cuantitativas a problemas de todo tipo, buscando mejorar el resultado y una óptima Toma de Decisiones.

George Bernard Dantzig (1914 – 2004)

Uno de los algoritmos clave para este tipo de programación es el Algoritmo Simplex, conocido como Método Simplex, desarrollado por George_Dantzig en forma circunstancial. Su padre fue un matemático ruso de cierto prestigio que trabajó en la capital francesa con Henry Poincaré. La fortuna sonrió a la familia cuando decidió emigrar a Estados Unidos en busca de oportunidades. Se cuenta que cierto día de 1939, mientras Dantzig realizaba su doctorado en la Universidad de Berkeley, se retrasó en la asistencia a una de sus clases, algo que era inusual en él. Se encontró con el aula vacía y con dos problemas garabateados en la pizarra. Aquello no le sorprendió lo más mínimo, ya había sucedido en otras ocasiones. Su profesor de matemáticas, Jerzy Neyman, acostumbraba dejar anotados dos problemas para que sus estudiantes los resolvieran en casa y lo entregaran al comienzo de la clase siguiente. Dantzig anotó ambas tareas. Como más tarde él mismo reconocería, le parecieron más difíciles que de costumbre, pero no imposibles. Lo que no sabía este ilustre estudiante de doctorado, era que durante los primeros minutos de la clase el profesor había mencionado, que aquellos dos problemas estaban aún sin resolver. Su intención no era que los solucionaran, simplemente que los estudiantes tuviesen conocimiento de su existencia. El dato curioso, es que la impuntualidad había ayudado a Dantzig a resolver dos problemas estadísticos que habían mantenido en jaque a las mentes más lúcidas del planeta. Pasaron seis semanas hasta que el profesor Neyman se presentó un domingo, a primera hora de la mañana y sin aviso previo, en el domicilio de Dantzig. Con la emoción contenida, explicó a su estudiante que acababa de enviar la resultados para su publicación. A partir de aquí, George Bernard Dantzig, fallecido en el 2005, es considerado el Padre de la Programación Lineal.

Esta historia fue llevada a la gran pantalla por Hollywood. La película en cuestión se titula El indomable Will Hunting (1997) y cuenta en su reparto con: Matt Damon, Robin Williams y Ben Affleck. El protagonista es un joven Will, uno de los aseadores de la universidad, que encuentra anotados los problemas en la pizarra mientras barre el aula.

Al margen de los errores de la película, donde se indica que Einstein era suizo, en lugar de alemán, hay una inquietud que surge en la mente de los espectadores de la misma: si Dantzig hubiese sabido que los problemas no eran una tarea sino dos cuestiones sin resolver…¿Se habría desanimado ante la dificultad?, o quizá, ¿no habría aspirado a resolverlos?,¿usted qué opina?

Para conocer más sobre George Dantzig, y sus aportes al desarrollo humano a través de sus ideas, comparto este corto, pero entretenido video sobre su fructífera vida.

En términos generales se puede decir que, la programación lineal es un medio para determinar la mejor manera de distribuir una cantidad de recursos limitados en procura de lograr un objetivo, expresado en maximizar o minimizar una determinada cantidad. El modelo general de un problema consta de dos partes muy importantes: la función objetivo y las restricciones.

¿Qué es el Método Simplex?


El método simplex es un procedimiento iterativo para resolver problemas de programación lineal, donde se busca obtener la solución óptima de la función objetivo que logre cumplir el conjunto de restricciones.

Conceptos Básicos

Para comprender mejor el método simplex es necesario  revisar algunos conceptos, ya que parte de dos afirmaciones importantes:

1.- El conjunto de posibles soluciones o conjunto factible de cualquier problema de programación lineal puede representarse mediante un poliedro convexo.

2.- Si un problema de programación lineal tiene una solución óptima y finita, ésta estará en un vértice del poliedro convexo que representa al problema.

3.- El algoritmo simplex parte de uno de los vértices del poliedro, y verifica si es el óptimo; si no lo es, busca un nuevo vértice adyacente que va mejorando el valor de la función objetivo. Se continúa iterando hasta llegar al vértice que representa la solución óptima.

En la siguiente imagen se aprecia el poliedro que representa la solución factible y cómo realiza el recorrido el algoritmo simplex:

Pasos del Método Simplex

1.- Definir el problema en la forma estándar y generar la respectiva matriz.

2.- Determinar la solución básica inicial.

3.- Seleccionar la variable de entrada, utilizando la condición de optimalidad; es decir, la utilización de variables de holgura. Si no se puede seleccionar una variable de entrada, mencionada anteriormente, quiere decir que se está en la condición óptima y finalizan las iteraciones. De otro modo se continúa con el siguiente paso.

4.- Seleccionar la variable de salida utilizando la condición de factibilidad.

A fin de tener una mejor comprención de la Programación Lineal, y más específamente del Método Simplex, tratado en esta primera unidad, le invitamos a ver el siguiente video, aportado por el canal de @IngEDarwin. Interesante material, donde podrá extraer más informción dividida en cuatro partes, siendo una de ellas, la Comprobación del método tratado en esta unidad.

Free Web Hosting