¿Qué es la programación lineal entera?
Significado | Concepto | Definición:
Los problemas de programación lineal de enteros surgen cuando se intenta resolver sistemas lineales mientras se 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 que el programador intenta encontrar una solución. Por lo general, constan de una ecuación que debe maximizarse o minimizarse y una o más ecuaciones restrictivas que ponen 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 mayores que uno.
Hombre, tenencia, computadora
Los sistemas lineales regulares se pueden resolver fácilmente usando una computadora. El programa puede identificar una solución encontrando la derivada y estableciéndola igual a cero. Luego puede verificar que el punto sea máximo o mínimo verificando su vecindad inmediata en la función. Siempre que la derivada esté definida 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 el que se permiten fracciones; sin embargo, es un reflejo del mundo real, en el que los elementos 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 quieren maximizar las ganancias tanto como sea posible, pero no pueden optar por vender una fracción de un producto.
Una vez que se aplican las restricciones de números enteros, el problema de resolver el sistema lineal es NP-completo. Esto significa que el tiempo que necesita una computadora para resolver el sistema es indeterminado. Con restricciones de números 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 sobre un número 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 todos, un proceso que podría llevar una cantidad infinita de tiempo.
Los programadores han desarrollado heurísticas, o métodos de resolución de problemas, para hacer frente a la complejidad de estos problemas. Un método para resolver problemas de programación lineal de enteros es el algoritmo de bifurcación y cota , en el que 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.
Mira estos Artículos