¿Qué es la programación lineal entera?
Los problemas de programación lineal de enteros surgen cuando se intenta resolver sistemas lineales al especificar 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. Generalmente consisten en una ecuación que debe ser maximizada o minimizada y una o más ecuaciones restrictivas que ponen límites a 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 mayores que uno.
Los sistemas lineales regulares se pueden resolver fácilmente usando una computadora. El programa puede identificar una solución al encontrar la derivada y establecerla igual a cero. Luego puede verificar que el punto es un máximo o un mínimo al verificar su vecindad inmediata en la función. Mientras la derivada se defina en cada punto de la función, la computadora solo tiene un número limitado de posibles soluciones para verificar.
La programación lineal se convierte en 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 que se permiten fracciones; Sin embargo, es un reflejo 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 optar por vender una fracción de un producto.
Una vez que las restricciones de enteros están en su lugar, el problema de resolver el sistema lineal es NP-completo. Esto significa que el tiempo necesario para que una computadora resuelva el sistema es indeterminado. Con restricciones de enteros, las computadoras no pueden usar la herramienta de la derivada porque no hay garantía de que el punto cero de la derivada caiga en un entero. La solución será el número entero con el valor más alto o más bajo de todos los números 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 el algoritmo de ramificación y unión, en el cual la computadora resuelve una serie de problemas relacionados con el original para reducir el rango de valores disponibles a una solución. Sin embargo, para problemas complejos, esto puede llevar mucho tiempo.