Este artículo fue publicado como parte del Blogatón de ciencia de datos.
Objetivo
“La verdadera optimización es la contribución revolucionaria a los procesos de decisión” – George Dantzig.
Este artículo analiza la solución de un problema de asignación de recursos mediante la programación lineal en Python. Encontraremos un valor óptimo para una ecuación lineal con diferentes restricciones lineales. Podemos resolver la programación lineal utilizando la biblioteca PuLP, y otras bibliotecas de Python que pueden realizar tareas similares son SciPy, Pyomo, CVXOPT. Analicemos los conceptos asociados y las declaraciones de problemas en detalle.
apreciando puLP
PuLP es un modelador de LP escrito en Python. Puede usar solucionadores como CBC, GLPK, CPLEX, MOSEK, etc., por nombrar algunos, para resolver problemas lineales. El solucionador predeterminado es CBC. Requiere Python 2.7 o Python >= 3.4. Algunas clases comúnmente utilizadas en PuLP son:
1. LpProblem: se utiliza para definir un problema
2. LpVariable: se utiliza para crear nuevas variables
3. LpConstraint: se utiliza para crear restricciones
4. Ipsum: para crear una expresión lineal de la forma a1*x1 + a2*x2
5. Valor: se utiliza para obtener el valor de la variable o expresión.
podemos referirnos a así documento para leer más
Podemos probar la pulpa después de importar como
importar pulpa pulpa.pulpTestAll()
El resultado puede verse como
Modelos de pulpa
Los modelos PuLP se pueden guardar, exportar y reutilizar en otra máquina o en otros momentos. Hay dos formas de exportar un modelo:
1. formato MDS
Podemos usar los siguientes comandos para almacenar el modelo
modelo.writeMPS("modelo.mps")
Podemos usar el siguiente control para recuperar el modelo.
var, modelo = LpProblem.fromMPS("modelo.mps")
Imprimiremos ambas variables para comprobar
imprimir (var) imprimir (modelo)
2. Formato de diccionario
Podemos utilizar
los siguientes comandos para almacenar el modelo en un diccionario
M1 = modelo.to_dict()
Podemos usar el
siguiente para recuperar el modelo
var, modelo = LpProblem.from_dict(M1)
Imprimiremos ambos para comprobar la salida.
imprimir (var) imprimir (modelo)
Programación lineal
Un programa lineal es un programa matemático que satisface tres condiciones:
1. Las variables de decisión deben ser reales.
2. La función objetivo debe ser lineal
3. La ecuación de restricción debe ser lineal
La programación lineal tiene como objetivo maximizar o minimizar un valor numérico, y se considera una de las muchas técnicas utilizadas para encontrar la utilización óptima de los recursos. Los diferentes aspectos de la programación lineal son las variables de decisión, las restricciones, los datos y la función objetivo, y los analizaremos en detalle en la siguiente sección. Las aplicaciones de optimización lineal se encuentran en la industria manufacturera, la industria del transporte, la ingeniería, la industria energética, etc.
Los pasos de optimización son:
1. Establecer una declaración del problema: por ejemplo, necesitamos asignar recursos de manera óptima en tres ubicaciones para dos obras
2. Formulación de ecuaciones: necesitamos identificar variables de decisión para formar una función objetivo. Por ejemplo, considerando el costo de los recursos, el número de obras y ubicaciones, se llegará a la función objetivo.
3. Resolviendo la ecuación: podemos usar cualquiera de los solucionadores mencionados anteriormente para llegar a valores óptimos
4. Análisis posterior: una vez que llegamos a la solución óptima, debemos ajustarla junto con el objetivo comercial para verificar si también se cumplen todas las restricciones comerciales.
5. Presentación de la solución: la solución óptima debe tener sentido y presentarse para que las partes interesadas tomen decisiones
Solucionador predeterminado
El solucionador predeterminado de PuLP es CBC (Coin-or branch and cut). Es un solucionador de programación de enteros mixtos de código abierto. Está escrito en C ++ y se puede usar con otros proyectos de monedas para obtener más funciones como Clp, Cgl, CoinUtils.
El puLP puede listar solucionadores usando los siguientes comandos:
importar pulpa como plp plp.listSolvers()
We
puede obtener los solucionadores deseados usando
obtenerSolver()
Problema de asignación de recursos
El problema de asignación de recursos es un problema de optimización. Busca encontrar la asignación óptima de recursos entre ubicaciones y tareas. Cada recurso tiene un coste asociado, y el número de recursos es fijo. En nuestro código, hemos tratado el número de recursos para cada trabajo como un número entero. La optimización de la asignación de recursos se puede aplicar en la planificación de la producción, las colas, la distribución de la carga, etc. El objetivo es minimizar el costo total y maximizar la producción.
Terminología
1. Función objetiva: Es una ecuación lineal que tratamos de maximizar o minimizar
2. Variables de decisión: Estas son variables utilizadas en la ecuación
3. Limitaciones: Son restricciones o limitaciones en las variables de decisión
4. Reglas no negativas: Decisión
los valores de las variables deben ser positivos
Ilustrando los cuatro términos a través de la siguiente ecuación
Planteamiento del problema
Hay tres ubicaciones: ubicación1, ubicación2, ubicación3. Hay dos trabajos: trabajo1, trabajo2. Cada ubicación tiene recursos, cada puesto requiere recursos y cada recurso tiene un costo asociado. Tenemos que asignar el trabajo de manera óptima en cada lugar para minimizar los costos generales de los recursos.
Implementación
Importando Bibliotecas
Usaremos las bibliotecas Pandas, NumPy y PuLP. Los detalles de la biblioteca PuLP se explican en las secciones anteriores.
importar pandas como pd importar pulpa como plp importar numpy como np
Creando las variables de entrada
Crearemos dos marcos de datos: para la ubicación y la restricción de recursos de trabajo y una matriz para el costo de los recursos. Estos tres valores de variables son entradas de muestra y podemos reemplazarlos con datos reales para obtener resultados reales.
location_df = pd.DataFrame({'ubicación': ['ubicación1', 'ubicación2', 'ubicación3'], 'max_resource':[500, 600, 250] }) work_df = pd.DataFrame({'work': [ 'trabajo1', 'trabajo2'], 'recurso_mínimo':[550, 300] }) costo_recurso = np.array([[150,200], [220,310], [210,440]])
Definición de modelo
Como es un problema de minimización, usaremos LpMinimize
modelo = plp.LpProblem("Resource_allocation_prob", plp.LpMinimize)
Crear función objetivo
Crearemos una función objetivo considerando la matriz de costos de recursos definida. Aquí 150, 200, etc. son el costo de los recursos R11, R12, etc. La siguiente imagen muestra el número de variables creadas en la función objetivo. R11, R12, R21, R22, R31, R32 son las variables de decisión.
no_of_ubicación = ubicación_df.shape[0] no_of_work = work_df.shape[0] x_vars_list = [] for l in range(1,no_of_location+1): for w in range(1,no_of_work+1): temp = str(l) +str(w) x_vars_list.append(temp) x_vars = plp.LpVariable.matrix("R", x_vars_list, cat = "Integer", lowBound = 0) final_allocation = np.array(x_vars).reshape(3,2) print(asignación_final) ecuación_res = plp.lpSum(asignación_final*costo_recurso) modelo += ecuación_res
Adición de restricciones
Hay dos restricciones y una está relacionada con la ubicación y la otra está relacionada con el trabajo. Cada ubicación tiene el máximo de recursos disponibles y, del mismo modo, cada trabajo requiere un mínimo de recursos para completarse. A continuación se muestra cómo podemos visualizar el problema.
for l1 in range(nº_de_ubicación): modelo += plp.lpSum(asignación_final[l1][w1] for w1 in range(nº_de_trabajo)) <= location_df['max_resource'].tolist()[l1] for w2 in range( no_of_work): modelo += plp.lpSum(final_asignación[l2][w2] for l2 in range(no_of_location)) >= work_df['min_resource'].tolist()[w2]
Imprimiendo el modelo
Usaremos una declaración de impresión para mostrar el modelo final. Podemos imprimir el modelo en pasos intermedios para comprobar cómo se está formando el modelo. El modelo final se ve a continuación.
imprimir (modelo)
Estoy ejecutando el modelo.
PuLP permite elegir solucionadores y formular problemas de forma más natural. El solucionador predeterminado utilizado por PuLP es COIN-OR Branch and Cut Solver (CBC)
model.solve() estado = plp.LpStatus[modelo.status] print(estado)
Comprobación del coste global óptimo de los recursos y el coste de cada combinación
print("Costo total óptimo de recursos: ",str(plp.value(model.objective))) para cada uno en model.variables(): print("Costo óptimo de ", each, ": "+str(each.value ()))
A continuación se muestra la distribución óptima de recursos. Es interesante ver cómo work2 puede ser manejado solo por location1. Los resultados siempre deben cotejarse con las partes interesadas para que sean más precisos. El modelo puede revisarse de acuerdo con las decisiones comerciales.
Conclusión
Espero que este artículo analice el funcionamiento de los problemas de optimización lineal que se pueden resolver con la biblioteca PuLP. Este artículo trata brevemente sobre la biblioteca pulp, los modelos pulp, la importación y exportación de modelos, el concepto de optimización y la programación lineal. Podemos probarlos en otros problemas de optimización y comprobar los resultados. Siempre es esencial que cualquier desarrollo se alinee con el negocio. Cuando se implementan a gran escala, deben obtener resultados productivos. La solución debe ser implementable para crear un impacto significativo. ¡Feliz codificación!
¿Le gustó mi artículo sobre la asignación óptima de recursos? Comparte en los comentarios abajo.
Dirígete a nuestro blog, para leer más artículos.
Fuentes de la imagen: Autor
Los medios que se muestran en este artículo no son propiedad de Analytics Vidhya y se utilizan a discreción del autor.
