Wanzi te enseña cómo implementar programación lineal con Python.
La programación lineal entera mixta es una extensión de la programación lineal. Maneja el problema donde al menos una variable toma números enteros discretos en lugar de valores continuos. Aunque a primera vista los problemas de enteros mixtos parecen similares a los problemas de variables continuas, tienen ventajas obvias en cuanto a flexibilidad y precisión.
Las variables enteras son importantes para representar correctamente cantidades que naturalmente se expresan como números enteros, como la cantidad de aviones producidos o la cantidad de clientes atendidos.
Una variable entera particularmente importante es una variable binaria. Sólo puede tomar el valor 0 o 1, lo cual es útil a la hora de tomar decisiones de sí o no, como por ejemplo si se debe construir una fábrica o si se debe encender o apagar una máquina. También puede utilizarlos para simular restricciones lógicas.
La programación lineal es una técnica de optimización fundamental que se ha utilizado en campos científicos y matemáticos intensivos durante décadas. Es preciso y relativamente rápido, lo que lo hace adecuado para una variedad de aplicaciones prácticas.
La programación lineal entera mixta permite superar muchas de las limitaciones de la programación lineal. Puede utilizar funciones lineales por partes para aproximar funciones no lineales, utilizar variables semicontinuas, modelar restricciones lógicas y más. Es una herramienta computacionalmente intensiva, pero los avances en hardware y software la hacen cada día más aplicable.
A menudo, cuando las personas intentan formular y resolver problemas de optimización, la primera pregunta es si pueden aplicar programación lineal o programación lineal entera mixta.
El siguiente artículo ilustra algunos casos de uso de programación lineal y programación lineal entera mixta:
Con una potencia informática cada vez mayor, algoritmos mejorados y soluciones de software más fáciles de usar Con la aparición de la programación lineal programación, especialmente programación lineal entera mixta, la importancia aumenta día a día.
El método básico para resolver problemas de programación lineal se llama programación lineal y tiene muchas variaciones. Otro método popular es.
Los problemas de programación lineal entera mixta se pueden resolver mediante métodos más complejos y computacionalmente intensivos, por ejemplo, que utilizan programación lineal interna. Algunas variaciones de este método son que implica el uso de planos de corte y.
Para la programación lineal y la programación lineal entera mixta, existen varias herramientas Python adecuadas y conocidas. Algunos de ellos son de código abierto, mientras que otros son propietarios. El hecho de que necesite herramientas gratuitas o de pago depende del tamaño y la complejidad del problema, así como de la necesidad de velocidad y flexibilidad.
Cabe mencionar que casi todas las bibliotecas de programación lineal y programación lineal entera mixta ampliamente utilizadas son nativas, escritas en Fortran o C o C++. Esto se debe a que la programación lineal requiere un trabajo computacional intensivo en matrices (a menudo muy grandes). Esta biblioteca de clases se llama solucionador. Las herramientas de Python son solo envoltorios de solucionadores.
Python es adecuado para crear contenedores alrededor de esta biblioteca porque funciona bien con C/C++. No necesitas C/C++ (o Fortran) para este tutorial, pero si quieres aprender más sobre esta interesante característica, consulta los siguientes recursos:
Básicamente, cuando defines y cuando resuelves un modelo, utiliza una función o método de Python para llamar a la biblioteca subyacente, que realiza el trabajo de optimización real y devuelve la solución a su objeto Python.
Varias bibliotecas gratuitas de Python están diseñadas para interactuar con solucionadores lineales o de enteros mixtos:
En este tutorial utilizará SciPy y PuLP para definir y resolver problemas de programación lineal.
En esta sección, verá dos ejemplos de problemas de programación lineal:
En la siguiente sección, utilizará Python para resolver estos dos problemas.
Considera el siguiente problema de programación lineal:
Necesitas encontrar x y ? Dejemos que el rojo, el azul y el amarillo no sean iguales, la desigualdad X 0 y? 0, satisfactorio. Al mismo tiempo, su solución debe corresponder al mayor valor posible de z.
Las variables independientes que necesitas encontrar (en este caso X e Y) se llaman variables de decisión. La función de la variable de decisión (en este caso z) que se va a maximizar o minimizar se llama función objetivo, función de costos o simplemente objetivo. Las desigualdades que debes satisfacer se denominan restricciones de desigualdad. También puede utilizar la igualdad en restricciones llamadas restricciones de igualdad.
Así te imaginas el problema:
¿La función representada por la línea roja es 2 X? = 20, el área roja de arriba indica que la desigualdad roja no se cumple. Nuevamente, la línea azul es la función 4 x 5 y = 10, y la región azul está prohibida porque viola la desigualdad azul. La línea amarilla es x 2 y = 2, y el área amarilla de abajo es donde la desigualdad amarilla no es válida.
Si ignoras las áreas roja, azul y amarilla, solo quedan las áreas grises. Cada punto en el área gris satisface todas las restricciones y es una solución potencial al problema. Esta área se llama región factible y sus puntos son soluciones factibles. En este caso, existen innumerables soluciones posibles.
Si se quiere maximizar z, la solución factible correspondiente a maximizar z es la solución óptima. Si se intenta minimizar una función objetivo, la solución óptima corresponderá a su mínimo factible.
Ten en cuenta que z es lineal. Puedes pensar en ello como un plano en un espacio tridimensional. Es por eso que la solución óptima debe estar en el vértice o esquina de la región factible. En este caso, la mejor solución es la intersección de las líneas roja y azul, como verás más adelante.
A veces, todo el borde de la región factible, o incluso toda la región, puede corresponder al mismo valor z. En este caso, tiene muchas soluciones óptimas.
Ahora puedes ampliar el problema con restricciones de igualdad adicionales que se muestran en verde:
La ecuación x 5 y = 15, escrita en verde, es nueva. Esta es una restricción de igualdad. Puedes visualizar la imagen anterior agregando la línea verde correspondiente:
La solución actual debe satisfacer la ecuación de Green, por lo que la región factible ya no es toda el área gris. Es la porción de la línea verde que pasa por el área gris desde su intersección con la línea azul hasta su intersección con la línea roja. Este último punto es la solución.
Si insertas el requisito de que todos los valores de x deben ser números enteros, obtendrás un problema de programación lineal entera mixta y el conjunto de soluciones factibles cambiará:
No más Línea verde, solo puntos con valores x enteros. Las soluciones viables son puntos verdes sobre un fondo gris donde la línea roja de disociación óptima es la más cercana.
Estos tres ejemplos ilustran problemas de programación lineal factibles porque tienen regiones factibles acotadas y soluciones finitas.
Si no hay solución, el problema de programación lineal es inviable. Esto suele ocurrir cuando ninguna solución satisface todas las restricciones simultáneamente.
Por ejemplo, considere lo que sucede si agrega la restricción x y 1. Entonces al menos una variable de decisión (x o y) debe ser negativa. Esto entra en conflicto con las restricciones dadas x 0 e y^0. Un sistema de este tipo no tiene solución viable y, por tanto, se dice que es inviable.
Otro ejemplo es agregar una segunda restricción de igualdad paralela a la línea verde. Las dos líneas no tienen nada en común, por lo que no habrá ninguna solución que satisfaga ambas restricciones.
Los problemas de programación lineal son ilimitados. Si la región factible es ilimitada, la solución no es finita. Esto significa que al menos una de sus variables no tiene restricciones y puede alcanzar el infinito positivo o negativo, lo que hace que el objetivo sea infinito.
Por ejemplo, supongamos que toma el problema inicial anterior y elimina las restricciones roja y amarilla. Quitar una restricción de un problema se llama relajar el problema. En este caso, xey no estarán acotados en el lado positivo. Puedes aumentarlos hasta el infinito positivo, obteniendo así infinitos valores z.
En la sección anterior, estudiaste un problema abstracto de programación lineal que no era relevante para ninguna aplicación del mundo real. En esta sección encontrará problemas de optimización más específicos y prácticos relacionados con la asignación de recursos de fabricación.
Supongamos que una fábrica produce cuatro productos diferentes. La producción diaria del primer producto es x. La salida del segundo producto es x^2 y así sucesivamente.
El objetivo es determinar el beneficio de cada producto y maximizar la producción diaria, teniendo en cuenta las siguientes condiciones:
El modelo matemático se puede definir de la siguiente manera:
La función objetivo ( beneficio) se define en la condición 1 . Las limitaciones humanas siguen la condición 2. Las restricciones sobre las materias primas A y B se pueden obtener a partir de las condiciones 3 y 4 sumando los requisitos de materia prima para cada producto.
Por último, la cantidad de producto no puede ser negativa, por lo que todas las variables de decisión deben ser mayores o iguales a cero.
A diferencia del ejemplo anterior, esto no se puede visualizar fácilmente porque tiene cuatro variables de decisión. Sin embargo, independientemente de las dimensiones del problema, el principio sigue siendo el mismo.
En este tutorial, utilizará dos paquetes de Python para resolver el problema de programación lineal descrito anteriormente:
SciPy es fácil de configurar. Una vez instalado, tendrás todo lo que necesitas para comenzar. Su subpaquete scipy.optimize se puede utilizar para optimización lineal y no lineal.
Pulp te permite elegir un solucionador y expresar tu problema de una forma más natural. El solucionador predeterminado utilizado por Pulp es el solucionador de monedas o ramas y cortes (CBC). Está conectado al solucionador de programación lineal (CLP) de monedas o cortes para relajación lineal y a la biblioteca generadora de monedas o cortes (CGL) para generación de cortes.
Otra gran solución de código abierto es el GNU Linear Programming Toolkit (GLPK). Algunas soluciones comerciales y patentadas conocidas y muy poderosas son Gurobi, CPLEX y XPRESS.
Además de brindar flexibilidad para definir problemas y la capacidad de ejecutar una variedad de solucionadores, PuLP no es tan complejo de usar como Pyomo o CVXOPT y requiere más tiempo y esfuerzo para dominarlo.
Para seguir este tutorial, necesitas SciPy y PuLP instalados. Los siguientes ejemplos utilizan SciPy 1.4.1 y PuLP 2.1.
Puedes instalar ambos usando pip de las siguientes maneras:
Es posible que necesites ejecutar pulptest o sudo pulptest para habilitar el solucionador predeterminado de PuLP, especialmente si usas Linux o Mac:
Como alternativa, puede descargar, instalar y utilizar GLPK. Es gratuito y de código abierto y está disponible para Windows, MacOS y Linux. Más adelante en este tutorial verás cómo usar GLPK (excepto CBC) con Pulp.
En Windows, puede descargar el archivo y ejecutar el archivo de instalación.
En MacOS, puedes usar homebrew:
En Debian y Ubuntu, instala glpk y glpk-utils usando apt:
En Fedora, usando dnf y glpk -utils:
Conda también puede resultarle útil para instalar GLPK:
Una vez completada la instalación, puede comprobar la versión de GLPK:
Para obtener más información Para obtener más información, consulte el tutorial de GLPK sobre la instalación utilizando ejecutables de Windows y paquetes de Linux.
En esta sección, aprenderá a utilizar la optimización SciPy y las bibliotecas raíz para la programación lineal.
Para usar SciPy para definir y resolver problemas de optimización, necesita importar scipy.optimize.linprog():
Ahora que se ha importado linprog(), puede comenzar a optimizar.
Resolvamos primero el problema de programación lineal anterior:
Linprog() solo resuelve el problema de minimización (no de maximización) y no permite restricciones de desigualdad mayores o iguales al signo ( ). Para resolver estos problemas, debe modificar su problema antes de comenzar la optimización:
Después de introducir estos cambios, obtendrá un nuevo sistema:
Este sistema es equivalente al sistema original. tendrá la misma solución. La única razón para aplicar estos cambios es superar las limitaciones de SciPy relacionadas con la formulación de problemas.
El siguiente paso es definir los valores de entrada:
Colocas los valores del sistema anterior en listas, tuplas o matrices NumPy apropiadas:
Nota: ¡preste atención al orden de las filas y columnas!
El orden de las filas en los lados izquierdo y derecho de la restricción debe ser el mismo. Cada fila representa una restricción.
El orden de los coeficientes del lado izquierdo de la función objetivo y la restricción deben coincidir. Cada columna corresponde a una variable de decisión.
El siguiente paso es definir los límites de cada variable en el mismo orden que los coeficientes. En este caso, todos están entre cero e infinito positivo:
Esta declaración es redundante porque linprog() toma estos límites (de cero a infinito positivo) de forma predeterminada.
Nota: Para el float ("inf") opuesto, puedes usar math.inf, numpy.inf o scipy.inf
Finalmente, es hora de optimizar el problema que están interesados en. Puedes hacer esto con linprog():
El parámetro c se refiere al coeficiente de la función objetivo. A_ub y b_ub están relacionados respectivamente con los coeficientes izquierdo y derecho de las restricciones de desigualdad. Asimismo, A_eq y b_eq también están sujetos a la igualdad referenciada. Puede utilizar límites para proporcionar límites superiores e inferiores a una variable de decisión.
Puede utilizar este método de parámetro para definir el método de programación lineal que se utilizará. Hay tres opciones:
Linprog() devuelve una estructura de datos con las siguientes propiedades:
Puedes acceder a los valores de forma individual:
Así es como obtienes el resultado de la optimización. También puedes mostrarlos gráficamente:
Como se mencionó anteriormente, la solución óptima a un problema de programación lineal se encuentra en el vértice de la región factible. En este caso, el área factible es sólo la línea verde entre las líneas azul y roja. La solución óptima es un cuadrado verde que representa la intersección de las líneas verde y roja.
Para excluir la restricción de igualdad (verde), simplemente elimine los parámetros A_eq y b_eq de la llamada a linprog():
La solución es diferente al caso anterior. Puedes ver esto en el diagrama:
En este caso, la solución óptima es el vértice morado en la región factible (gris) donde se cruzan las restricciones roja y azul. Otros vértices, como el vértice amarillo, tienen valores de función objetivo más altos.
Puedes usar SciPy para resolver el problema de asignación de recursos descrito en la sección anterior:
Como en el ejemplo anterior, necesitas extraer los vectores y matrices necesarios del problema anterior. Pásalos como parámetros. linprog(), y luego obtiene el resultado:
¿El resultado te dice que la ganancia máxima de 1900 corresponde a X? = 5 yx? =45. En determinadas condiciones, no es rentable producir el segundo y cuarto producto. Aquí puedes sacar varias conclusiones interesantes:
Opt.statusis0 y Opt. Los resultados muestran que el problema de optimización se resuelve exitosamente y se obtiene la solución óptima factible.
Las funciones de programación lineal de SciPy se utilizan principalmente para problemas más pequeños. Para problemas más grandes y complejos, es posible que otras bibliotecas sean más adecuadas por las siguientes razones:
Afortunadamente, el ecosistema Python proporciona varias soluciones alternativas para la programación lineal y, para problemas más complejos, las grandes preguntas son muy útil. Uno de ellos es la pulpa de papel, que verá en acción en la siguiente sección.
PuLP tiene una API de programación lineal más conveniente que SciPy. No es necesario que revise su problema matemáticamente ni utilice vectores y matrices. Todo está más limpio y menos propenso a errores.
Como siempre, primero importas lo que necesitas:
Ahora que has importado la pulpa, puedes solucionar tu problema.
Ahora usarás Pulp para resolver este sistema:
El primer paso es inicializar una instancia de LpProblem para representar tu modelo:
Puedes usar esto sense Parámetro para elegir si minimizar (LpMinimize o 1, que es el valor predeterminado) o maximizar (LpMaximize o -1). Esta elección afectará el resultado de su pregunta.
Una vez que tenga el modelo, puede definir las variables de decisión como instancias de la clase LpVariable:
Debe proporcionar un límite inferior, lowBound=0, porque el valor predeterminado es infinito negativo. El parámetro upBound define el límite superior, pero puede omitirlo aquí ya que por defecto es infinito positivo.
El parámetro opcional cat define la categoría de la variable de decisión. Si usa variables continuas, puede usar el valor predeterminado "continuo".
Puedes usar las variables x e y para crear otros objetos pulp que representen expresiones y restricciones lineales:
Cuando multiplicas una variable de decisión por un escalar o construyes múltiples variables de decisión Cuando se combinan linealmente, obtienes una instancia de pulp. LpAffineExpression representa una expresión lineal.
Nota: Las variables o expresiones se pueden sumar o restar, y sus constantes se pueden multiplicar, porque la clase pulp implementa algunos métodos especiales de Python, concretamente tipos de números analógicos con __add__(), __sub__() y _ Same. como _mul__(). Estos métodos se utilizan para personalizar el comportamiento de operadores como, - y *.
Del mismo modo, puedes utilizar los operadores = =, = para combinar expresiones lineales, variables y escalares para obtener una instancia de pulp. LpConstraint representa las restricciones lineales del modelo.
Nota: Las restricciones también se pueden construir utilizando métodos de comparación enriquecidos. _ __eq__(), _ __le__() y _ _ ge _ _() definen los operadores = =, =
Con esto en mente, el siguiente paso es crear las restricciones y la función objetivo y combinarlas. asignados al modelo. No es necesario crear una lista o matriz. Simplemente escriba expresiones de Python y adjúntelas al modelo usando el operador =:
En el código anterior, define una tupla que contiene las restricciones y sus nombres. LpProblem le permite agregar restricciones a su modelo especificándolas como tuplas. El primer elemento es una instancia de LpConstraint. El segundo elemento es el nombre legible por humanos de la restricción.
Configurar la función objetivo es muy similar:
Como alternativa, puedes usar una notación más corta:
Ahora que agregaste la función objetivo y definiste la modelo.
Nota: Puede adjuntar restricciones u objetivos a un modelo usando el operador = porque su clase LpProblem implementa métodos especiales. __iadd__(), para el comportamiento especificado =.
Para problemas más grandes, a menudo es más conveniente usar lpSum() en listas u otras secuencias que el operador de repetición. Por ejemplo, puede agregar la función objetivo al modelo usando la siguiente declaración:
Produce los mismos resultados que la declaración anterior.
Ahora puedes ver la definición completa del modelo:
La representación en cadena del modelo contiene todos los datos relevantes: variables, restricciones, objetivos y sus nombres.
Nota: Las representaciones de cadenas se construyen definiendo métodos especiales. __repr__(). Más detalles sobre. __repr__(), consulte Conversión de cadenas Pythonic OOP: _ _ REPR _ vs _ _ STR _ _.
Finalmente, estás listo para resolver el problema. Puedes hacerlo llamando. solve() tu objeto modelo. Si desea utilizar el solucionador predeterminado (CBC), no necesita pasar ningún parámetro:
. solve() llama al solucionador subyacente, modifica el objeto del modelo y, si se encuentra la solución óptima, devuelve el estado entero 1 de la solución. Consulte LpStatus[] para conocer los códigos de estado restantes.
Puedes utilizar los resultados de la optimización como modelo de atributos. Valor de función() y métodos correspondientes. value() devuelve el valor real del atributo:
Model.objective guarda el valor de la función objetivo model.constraints, incluido el valor de la variable de holgura. Los objetos X e Y tienen los valores óptimos. de las variables de decisión.
Model.variables() devuelve una lista de variables de decisión:
Como puedes ver, esta lista contiene el objeto exacto LpVariable creado con el constructor.
Los resultados son aproximadamente los mismos que obtendrías usando SciPy.
Nota: Presta atención a este método. solve() - ¡cambiará el estado del objeto, x e y!
Puedes ver qué solucionador. Utilice Solver llamando al siguiente método:
El resultado le informa que el solucionador es CBC. No especifica un solucionador, por lo que Pulp llama al solucionador predeterminado.
Si desea ejecutar un solucionador diferente, puede especificarlo como parámetro. resolver(). Por ejemplo, si desea utilizar GLPK y tenerlo instalado, puede usarlo con solver=GLPK(msg=False) en la última línea. Recuerde, también necesita importarlo:
Ahora que ha importado GLPK, puede usarlo allí. solve():
Este parámetro de mensaje se utiliza para mostrar información del solucionador. Msg=False desactiva la visualización de este mensaje. Si desea incluir información, simplemente omita msg o establezca msg=True.
Tu modelo ya ha sido definido y resuelto, por lo que puedes comprobar los resultados de la misma forma que en el caso anterior:
Los resultados obtenidos usando GLPK son los mismos que los obtenidos usando SciPy y CBC Los resultados son casi los mismos.
Veamos qué Solver se usa esta vez:
Como lo definiste en la declaración resaltada arriba, modelo. Resolver (Solver = GLPK (MSG = false)), el solucionador es GLPK.
También puedes utilizar pulp para resolver problemas de programación lineal entera mixta. Para definir una variable entera o binaria, simplemente pase cat="Integer " o cat="Binary " a LpVariable. Todo lo demás sigue igual:
En este caso tienes una variable entera y obtienes resultados diferentes:
Nowx es un número entero, como se especifica en el modelo. (Técnicamente, contiene un valor de coma flotante con ceros después del punto decimal. Este hecho cambia toda la solución. Mostrémoslo en un diagrama:
Como puedes ver, la solución óptima es la solución verde más a la derecha. punto sobre el fondo gris Este es el valor máximo de la solución factible X e Y.
GLPK también puede resolver este problema. Ahora puedes usar pulp para resolver el problema de asignación de recursos anterior:
La forma de definir y resolver el problema es la misma que en el ejemplo anterior:
En este caso, se utiliza un diccionario x para almacenar todas las variables de decisión. Este enfoque es muy conveniente porque el diccionario. puede almacenar el nombre o índice de la variable de decisión como clave y el objeto LpVariable correspondiente como valor.
El código anterior produce el siguiente resultado:
Como puede ver, esto. La solución es consistente con la obtenida usando SciPy. El escenario más rentable es producir 5.0 de los primeros productos por día, el tercer producto de 45.0
Supongamos que este problema. la fábrica no puede producir el primer y tercer producto al mismo tiempo debido a problemas en la máquina, ¿cuál es la solución más rentable?
Ahora tienes otra restricción lógica: si x es positiva, ¿entonces x debe? ser cero, y viceversa. Esta es una decisión binaria. Aquí es donde las variables son muy útiles. Utilizarás dos variables de decisión binaria y, que indicarán si generar el primer o el tercer producto:
En. Además de la fila resaltada, el código es muy similar al ejemplo anterior. Aquí están las diferencias:
Aquí está la solución:
Resulta que la mejor manera es excluir. el primer producto y sólo producir el segundo Tres productos.
Así como hay muchos recursos para ayudarte a aprender programación lineal y programación lineal entera mixta, también hay muchos solucionadores disponibles con contenedores de Python. Aquí hay una lista parcial:
Algunas de estas bibliotecas, como Gurobi, incluyen sus propios contenedores de Python. Otros usan envoltorios externos. Por ejemplo, puede ver que puede usar PuLP para acceder a CBC y GLPK.
Ahora ya sabes qué es la programación lineal y cómo utilizar Python para resolver problemas de programación lineal. También aprendió que la biblioteca de programación lineal de Python es solo una envoltura del solucionador nativo. Cuando el solucionador completa su trabajo, el contenedor devuelve el estado de la solución, los valores de las variables de decisión, las variables de holgura, la función objetivo, etc.