¿Qué es la programación lineal entera?
Los problemas de programación lineal entero surgen cuando se intenta resolver sistemas lineales mientras especifica que todas las variables desconocidas deben ser enteros o números enteros. Los sistemas lineales son conjuntos de ecuaciones que describen una situación para la cual el programador intenta encontrar una solución. Por lo general, consisten en una ecuación que debe maximizarse o minimizarse y una ecuación restrictiva o más restrictiva que pone límites a las variables desconocidas. Para que el sistema sea lineal, cada restricción debe ser una ecuación lineal; Es decir, no debe contener instancias de la variable desconocida con exponentes superiores a uno.
Los sistemas lineales regulares pueden resolverse fácilmente usando una computadora. El programa puede identificar una solución al encontrar el derivado y establecerlo igual a cero. Luego puede verificar que el punto es un máximo o mínimo al verificar su vecindario inmediato en la función. Mientras la derivada se define en cada punto a lo largo de la función, la computadora solo tiene un número limitado de posiblese soluciones para verificar.
La programación lineal se convierte en una programación lineal entera con la adición de la restricción entera. Esto significa que el problema sigue siendo el mismo, pero la respuesta debe consistir en valores enteros para los valores desconocidos: deben ser números enteros. A veces, esto significa que la solución será subóptima en comparación con el caso en el que se permiten fracciones; Sin embargo, es reflexivo del mundo real, en el que los artículos a menudo vienen en unidades discretas e indivisibles. Esto hace que la programación lineal entera sea importante para las aplicaciones comerciales, ya que las empresas desean maximizar las ganancias tanto como sea posible, pero no pueden elegir vender una fracción de un producto.
Una vez que las restricciones enteras están en su lugar, el problema de resolver el sistema lineal es NP-complete. Esto significa que el tiempo que es necesario para que una computadora resuelva el sistema es indeterminado. Con restricciones enteras, computadoraS no puede usar la herramienta del derivado porque no hay garantía de que el punto cero del derivado caiga en un entero. La solución será el entero con el valor más alto o más bajo de todos los enteros, por lo que la computadora tendría que verificarlos a todos, un proceso que podría tomar una cantidad infinita de tiempo.
Los programadores han desarrollado heurísticas, o métodos de resolución de problemas, para lidiar con la complejidad de estos problemas. Un método para resolver problemas de programación lineal de enteros es la rama y el algoritmo límite, en el que la computadora resuelve una serie de problemas relacionados con el original para reducir el rango disponible de valores a una solución. Para problemas complejos, sin embargo, esto puede llevar mucho tiempo.