Cómo utilizar la programación entera lineal para resolver problemas de temporización en ingeniería
La programación lineal entera 0-1 es un caso especial de programación lineal entera y se usa ampliamente en la práctica. Aunque la variable sólo tiene dos valores, resolver este tipo de problemas es sorprendentemente difícil. Algunas soluciones relacionadas se resumen a continuación.
¿Método exhaustivo? Todas las soluciones posibles se generan una por una, y luego las soluciones que satisfacen las restricciones se comparan para hacer que la solución óptima de la función objetivo sea la solución óptima. Esta es una manera, pero no una buena. Si el tamaño del problema es grande, es posible que no sea posible encontrar la solución óptima en un tiempo aceptable. Ésta es también la dificultad para resolver la programación entera.
2.¿Método de enumeración implícita I? Es una mejora del método exhaustivo. La idea es dar primero una solución factible y luego sustituirla en la función objetivo para calcular el valor de la función y obtener un límite superior (si se busca el valor mínimo) o un límite inferior (si se busca el valor máximo). Luego verifique otras soluciones una por una. Si la solución es mayor que el límite superior o menor que el límite inferior, no es necesario verificar la viabilidad porque no puede ser la solución óptima. En caso contrario, comprobar la viabilidad. Si es una solución factible, modifique el límite superior o inferior y continúe comprobando otras soluciones. De lo contrario, no es necesario modificar los límites superior o inferior y comprobar directamente otras soluciones. Este método controla si se requieren pruebas de viabilidad a través de un límite superior o inferior, lo que mejora la eficiencia. Sin embargo, encontrar una solución viable llevará algún tiempo. Cuando hay muchas restricciones y variables, la carga de trabajo es extremadamente pesada. Para dar un paso atrás, incluso si la solución factible es fácil de encontrar, su límite superior es demasiado grande o su límite inferior es demasiado pequeño y el efecto de filtrado no es obvio. Éste es el defecto de este enfoque.
3. ¿Enumeración implícita II? Este método primero transforma el problema en una forma estándar y luego encuentra la solución óptima probando la menor cantidad posible de soluciones factibles según la idea del método de ramificación y limitación. Este método es más problemático y no puedo describirlo claramente aquí. Escribiré esta parte en unos días cuando la entienda completamente.
4. ¿Método de enumeración implícita tres? Esto fue propuesto por Cheng Dongshi y Zhang Shengnian en un artículo "Varios problemas sobre la programación entera 0-1" publicado en el "Journal of Jiangxi Electric Power Vocational and Technical College". La idea general es: sustituir todas las soluciones posibles en los valores calculados de la función objetivo y luego ordenar estos valores de la función objetivo. Si es el valor más grande, ordénelo en orden descendente, si es el valor más pequeño, ordénelo en orden ascendente. Luego, se prueba la viabilidad de las soluciones correspondientes una por una en este orden, y se obtiene la solución óptima cuando se encuentra la primera solución factible, porque otras soluciones no serán mejores que esta solución. Las deficiencias de este enfoque también son obvias. Si hay n variables, n valores de función objetivo deben ser 2 y luego deben ordenarse, lo cual es mucho trabajo. Otra cosa es que si el resultado de la clasificación es que la solución factible ocupa el último lugar, entonces aún es necesario probar 2 elevado a la enésima potencia.
4. ¿Algoritmo heurístico? Los algoritmos genéticos, los algoritmos de colonias de hormigas, etc. pueden entrar en esta categoría. Estos son algoritmos aleatorios. Para decirlo sin rodeos, es sólo una cuestión de resignación. Incluso si calcula la solución óptima, no sabe si es la solución óptima, porque la convergencia de este tipo de algoritmo es solo probabilística y solo Dios sabe si se ha optimizado durante el proceso de cálculo. La heurística sólo debe utilizarse como último recurso. Solo podemos garantizar que la solución obtenida por este método es mejor que la solución obtenida por otros métodos, pero no necesariamente representa la solución óptima.
La solución para la programación 0-1 aún está en investigación. Quizás encuentres un algoritmo eficiente.