Tipos de método simplex
Contenidos
En este trabajo consideramos la aplicación de la programación lineal en la resolución de problemas de optimización con restricciones. Utilizamos el método simplex para encontrar el máximo de una función objetivo. Este método se aplica a un ejemplo real. Utilizamos la función “linprog” de MatLab para la resolución del problema. Mostramos cómo aplicar el método simplex en un problema del mundo real, y resolverlo mediante programación lineal. Finalmente investigamos la complejidad del método mediante la variación del tiempo de computación frente al número de variables de control.
Método Simplex con 4 variables
Según entiendo, dado que la solución de un programa lineal siempre se da en un vértice de su conjunto factible poliédrico (si existe una solución y el valor de la función objetivo óptima está acotado por abajo, suponiendo un problema de minimización), ¿cómo puede ser mejor una búsqueda por el interior de la región factible? ¿Converge más rápido? ¿En qué circunstancias sería ventajoso utilizar el método simplex sobre los métodos de punto interior? ¿Es uno más fácil de implementar en un código que el otro?
Basándome en mi experiencia personal, diría que los métodos simplex son marginalmente más fáciles de entender cómo se implementan que los métodos de punto interior, basándome en la experiencia personal de implementar tanto el método simplex primal como un método básico de punto interior en MATLAB como parte de una clase de programación lineal. Los principales obstáculos en el simplex primario son asegurarse de que se implementa correctamente la Fase I y la Fase II, y también que se implementa correctamente una regla de anticiclaje. Los principales obstáculos en la implementación de un método de punto interior para la programación lineal tienden a ser más acerca de la implementación del método iterativo correctamente, y la escala del parámetro de barrera en consecuencia.
Aplicación del método simplex en la empresa
La mayoría de las aplicaciones del método simplex son bastante sencillas, siempre que se disponga de los datos en la forma correcta. Las restricciones de tiempo, materiales, dinero y otros recursos suelen poder escribirse en forma de ecuaciones o desigualdades como funciones lineales de las variables. La función objetivo también suele ser lineal en estas variables. En ocasiones hay que cambiar la variable que se utiliza: en lugar de que la cantidad de cada producto que se fabrica sea la variable hay que utilizar otra medida, por ejemplo, el tiempo que se utiliza una máquina, o la cantidad de materia prima, o las proporciones que se mezclan. Este cambio de variable es a veces difícil de ver y en este capítulo se presentan algunas aplicaciones poco habituales. Están tomadas de otros tres métodos de Investigación Operativa: colas, camino crítico y teoría de juegos. Los demás ejemplos proceden del corte de papel, el corte de metales, el flujo de procesos y una modificación del problema del capítulo 3 sobre la producción de grasa. En las referencias encontrará otros ejemplos.
Ejemplos de problemas de palabras con el método simplex
El nombre del algoritmo se deriva del concepto de simplex y fue sugerido por T. S. Motzkin[2] En realidad, el método no utiliza simples, pero una interpretación del mismo es que opera sobre conos simpliciales, y éstos se convierten en simples propios con una restricción adicional[3][4][5][6] Los conos simpliciales en cuestión son las esquinas (es decir, las vecindades de los vértices) de un objeto geométrico llamado politopo. La forma de este politopo está definida por las restricciones aplicadas a la función objetivo.
George Dantzig trabajó en métodos de planificación para las Fuerzas Aéreas del Ejército de Estados Unidos durante la Segunda Guerra Mundial utilizando una calculadora de escritorio. En 1946, su colega le retó a mecanizar el proceso de planificación para evitar que aceptara otro trabajo. Dantzig formuló el problema como desigualdades lineales inspiradas en el trabajo de Wassily Leontief, sin embargo, en ese momento no incluyó un objetivo como parte de su formulación. Sin un objetivo, un gran número de soluciones pueden ser factibles y, por lo tanto, para encontrar la “mejor” solución factible, hay que utilizar “reglas básicas” especificadas por los militares que describen cómo se pueden alcanzar los objetivos, en lugar de especificar un objetivo en sí. La idea central de Dantzig fue darse cuenta de que la mayoría de esas reglas básicas pueden traducirse en una función objetivo lineal que hay que maximizar[7]. El desarrollo del método simplex fue evolutivo y se produjo a lo largo de un año[8].