La investigación operativa, la ciencia del uso de computadoras para tomar decisiones óptimas, se ha utilizado y aplicado en muchas áreas del software. Para dar algunos ejemplos, las compañías de logística lo usan para determinar la ruta óptima para llegar del punto A al punto B, las compañías eléctricas lo usan para determinar los programas de producción de energía y las compañías manufactureras lo usan para encontrar patrones de personal óptimos para sus fábricas.
Hoy exploraremos el poder de la investigación operativa pasando sobre un problema hipotético. Específicamente, utilizaremos la programación de enteros mixtos (MIP) para determinar el patrón de dotación de personal óptimo para una fábrica hipotética.
Algoritmos de Investigación de Operaciones
Antes de sumergirnos en nuestro problema de ejemplo, es útil repasar algunos conceptos básicos en la investigación de operaciones y comprender algunas de las herramientas que usaremos hoy.
Algoritmos de Programación Lineal
La programación lineal es una técnica de investigación de operaciones utilizada para determinar el mejor resultado en un modelo matemático donde el objetivo y las restricciones se expresan como un sistema de ecuaciones lineales. Un ejemplo de modelo de programación lineal podría verse así:
Maximize a + b (objetive)
Subject a:
a <= 2 (restriction 1)
b <= 3 (restriction 2)
En nuestro ejemplo simple, podemos ver que el resultado óptimo es 5, con a = 2 y b = 3. Si bien este es un ejemplo bastante trivial, es probable que puedas imaginar un modelo de programación lineal que utiliza miles de variables y cientos de restricciones.
Un buen ejemplo podría ser un problema de portafolio de inversión en el que podrías terminar con algo como lo siguiente, en un pseudo-código:
Maximize <expected profit from all stock investments>
Subject to:
<investment in the technology sector must be between 10% - 20% of portfolio>
<investment in the consumer staples must not exceed investment in financials>
Etc.
...
Lo cual sería bastante complejo y difícil de resolver a mano o por prueba y error. El software de investigación operativa utilizará varios algoritmos para resolver estos problemas rápidamente. Si estás interesado en los algoritmos subyacentes, te recomiendo que aprendas sobre el método símplex aquí y el método del punto interior aquí.
Algoritmos de Programación Enteros
La programación entera es como la programación lineal con una tolerancia adicional para que algunas o todas las variables sean valores enteros. Si bien esto puede no parecer una gran mejora al principio, nos permite resolver muchos problemas que podrían haberse quedado sin resolver utilizando únicamente la programación lineal.
Uno de estos problemas es el problema de la mochila, en el que se nos da un conjunto de elementos con valores y pesos asignados y se les pide que encuentren la combinación de los elementos que más cabe en nuestra mochila. Un modelo de programación lineal no podrá resolver esto, debido a que no hay forma de expresar la idea de que puedes poner un artículo en su mochila o no, pero no puedes poner parte de un artículo en tu mochila—¡cada variable es una variable continua!
Un ejemplo de problema de mochila podría tener los siguientes parámetros:
| Object | Value (units of $10) | Size (generic units) |
|---|---|---|
| Camera | 5 | 2 |
| Mysterious figurine | 7 | 4 |
| Huge bottle of apple cider | 2 | 7 |
| French horn | 10 | 10 |
Y el modelo MIP se verá así:
Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take)
Subject to:
2a + 4b + 7c + 10d <= 15 (space constraint)
La solución óptima, en este caso, es a=0, b=1, c=0, d=1, con el valor del ítem total siendo 17.
El problema que resolveremos hoy también requerirá una programación entera ya que un empleado en una fábrica puede programarse para un turno o no—en aras de la simplicidad, no puedes programar un empleado para 2/3 de turno en esta fábrica.
Para hacer posible la programación de enteros se usan varios algoritmos matemáticos. Si estás interesado en los algoritmos subyacentes, te recomiendo que estudies el algoritmo de planos de corte y el algoritmo de ramificación y enlace aquí.
Problema Ejemplo: Programación
Descripción del Problema
Hoy exploraremos el problema de dotar de personal a una fábrica. Como la gerencia de la fábrica, queremos minimizar los costos de mano de obra pero queremos asegurar una cobertura suficiente para cada turno para así satisfacer la demanda de producción.
Supongamos que tenemos cinco turnos con las siguientes demandas de personal:
| Shift 1 | Shift 2 | Shift 3 | Shift 4 | Shift 5 |
|---|---|---|---|---|
| 1 person | 4 people | 3 people | 5 people | 2 people |
Y supongamos que tenemos los siguientes trabajadores:
| Name | Availability | Cost per Shift ($) |
|---|---|---|
| Melisandre | 1, 2, 5 | 20 |
| Bran | 2, 3, 4, 5 | 15 |
| Cersei | 3, 4 | 35 |
| Daenerys | 4, 5 | 35 |
| Theon | 2, 4, 5 | 10 |
| Jon | 1, 3, 5 | 25 |
| Tyrion | 2, 4, 5 | 30 |
| Jaime | 2, 3, 5 | 20 |
| Arya | 1, 2, 4 | 20 |
Para mantener el problema simple, supongamos por el momento que la disponibilidad y el costo son las únicas preocupaciones.
Nuestras Herramientas
Para el problema de hoy, usaremos un software de corte y ramificación de código abierto llamado CBC. Interactuaremos con este software usando PuLP, que es una biblioteca de modelado de investigación de operaciones popular para Python. Puedes encontrar información al respecto aquí.
PuLP nos permite construir modelos MIP de una manera muy Pythonica y se integra muy bien con el código Python existente. Esto es muy útil ya que algunas de las herramientas de análisis y manipulación de datos más populares están escritas en Python, y la mayoría de los sistemas de investigación de operaciones comerciales requieren un extenso procesamiento de datos antes y después de la optimización.
Para demostrar la simplicidad y elegancia de PuLP, aquí está el problema de la mochila de antes y resuelto en PuLP:
import pulp as pl
# declarar algunas variables
# cada variable es una variable binaria que es 0 o 1
# 1 significa que el artículo irá a la mochila
a = pl.LpVariable("a", 0, 1, pl.LpInteger)
b = pl.LpVariable("b", 0, 1, pl.LpInteger)
c = pl.LpVariable("c", 0, 1, pl.LpInteger)
d = pl.LpVariable("d", 0, 1, pl.LpInteger)
# define el problema
prob = pl.LpProblem("knapsack", pl.LpMaximize)
# función objetivo - maximizar el valor de los objetos en la mochila
prob += 5 * a + 7 * b + 2 * c + 10 * d
# restricción: el peso de los objetos no puede exceder 15
prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15
estado = prob.solve() # resuelve usando el solucionador predeterminado, que es cbc
print(pl.LpStatus[status]) # imprime el estado legible por humanos
# imprime los valores
print("a", pl.value(a))
print("b", pl.value(b))
print("c", pl.value(c))
print("d", pl.value(d))
Ejecuta esto, y deberías obtener la salida:
Optimal
a 0.0
b 1.0
c 0.0
d 1.0
¡Ahora a nuestro problema de programación!
Codificando Nuestra Solución
La codificación de nuestra solución es bastante sencilla. Primero, definiremos nuestros datos:
import pulp as pl
import collections as cl
# data
shift_requirements = [1, 4, 3, 5, 2]
workers = {
"Melisandre": {
"availability": [0, 1, 4],
"cost": 20
},
"Bran": {
"availability": [1, 2, 3, 4],
"cost": 15
},
"Cersei": {
"availability": [2, 3],
"cost": 35
},
"Daenerys": {
"availability": [3, 4],
"cost": 35
},
"Theon": {
"availability": [1, 3, 4],
"cost": 10
},
"Jon": {
"availability": [0, 2, 4],
"cost": 25
},
"Tyrion": {
"availability": [1, 3, 4],
"cost": 30
},
"Jaime": {
"availability": [1, 2, 4],
"cost": 20
},
"Arya": {
"availability": [0, 1, 3],
"cost": 20
}
}
A continuación, debemos definir el modelo:
# define el modelo: queremos minimizar el costo
prob = pl.LpProblem("scheduling", pl.LpMinimize)
# algunos modelos de variable
cost = []
vars_by_shift = cl.defaultdict(list)
for worker, info in workers.items():
for shift in info['availability']:
worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger)
vars_by_shift[shift].append(worker_var)
cost.append(worker_var * info['cost'])
# establece el objetivo para que sea la suma del costo
prob += sum(cost)
# establece los requerimientos de cambio
for shift, requirement in enumerate(shift_requirements):
prob += sum(vars_by_shift[shift]) >= requirement
Y ahora, ¡le pedimos que resuelva e imprima los resultados!
status = prob.solve()
print("Result:", pl.LpStatus[status])
results = []
for shift, vars in vars_by_shift.items():
results.append({
"shift": shift,
"workers": [var.name for var in vars if var.varValue == 1],
})
for result in sorted(results, key=lambda x: x['shift']):
print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))
Una vez que ejecutas el código, deberías ver las siguientes salidas:
Result: Optimal
Shift: 0 workers: Arya_0
Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1
Shift: 2 workers: Bran_2, Jon_2, Jaime_2
Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3
Shift: 4 workers: Bran_4, Theon_4Aumenta un Poco la Dificultad: Restricciones Adicionales
Aunque el modelo anterior fue interesante y útil, no demuestra completamente el poder de la programación de enteros mixtos. También podríamos escribir fácilmente un ciclo
for para encontrar los trabajadores x más baratos para cada turno, donde x es la cantidad de trabajadores necesarios para un turno. Para demostrar cómo MIP se puede usar para resolver un problema que sería difícil de resolver de manera imperativa, examinemos qué pasaría si agregamos algunas restricciones adicionales.Restricciones Adicionales
Supongamos que debido a las nuevas regulaciones laborales, no se pueden asignar trabajadores a más de 2 turnos. Para dar cuenta del aumento del trabajo, hemos contratado la ayuda de Dothraki Staffing Group, que proporcionará hasta 10 trabajadores Dothraki por cada turno a una tasa de 40 dólares por turno.
Además supongamos que, debido a algunos conflictos interpersonales en curso fuera de nuestra fábrica, Cersei y Jaime no pueden trabajar en turnos ni con Daenerys ni con Jon. Además, Jaime y Cersei no pueden trabajar ningún turno juntos. Finalmente, Arya, que tiene relaciones interpersonales particularmente complejas, no puede trabajar en el mismo turno con Jaime, Cersei o Melisandre.
La adición de estas dos nuevas limitaciones y recursos de ninguna manera hace que el problema sea imposible de resolver a través de medios imperativos, pero hace que la solución sea mucho más difícil ya que uno tendrá que considerar los costos de oportunidad de programar a un trabajador para un turno en particular.
Solución
Con la programación de enteros mixtos, sin embargo, es mucho más fácil. Simplemente necesitamos enmendar nuestro código así:
Definir la lista de prohibiciones y algunas restricciones:
ban_list = {
("Daenerys", "Jaime"),
("Daenerys", "Cersei"),
("Jon", "Jaime"),
("Jon", "Cersei"),
("Arya", "Jaime"),
("Arya", "Cersei"),
("Arya", "Melisandre"),
("Jaime", "Cersei")
}
DOTHRAKI_MAX = 10
DOTHRAKI_COST = 45
Rellena algunas variables para implementar las restricciones de prohibición y cambio máximo:
for worker, info in workers.items():
for shift in info['availability']:
worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger)
# almacena algunos datos variables para que podamos implementar la restricción de prohibición
var_data = (worker,)
vars_by_shift[shift].append((worker_var, var_data))
# almacena vars por variable para que podamos implementar la restricción de cambio máximo
vars_by_worker[worker].append(worker_var)
cost.append(worker_var * info['cost'])
Agrega las variables Dothraki:
for shift in range(len(shift_requirements)):
dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger)
cost.append(dothraki_var * DOTHRAKI_COST)
dothrakis_by_shift[shift] = dothraki_var
También necesitaremos un bucle ligeramente modificado para calcular los requisitos de cambio y prohibición:
# establece los requerimientos de cambio
for shift, requirement in enumerate(shift_requirements):
prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement
# establece los requerimientos de prohibición
for shift, vars in vars_by_shift.items():
for var1 in vars:
for var2 in vars:
worker_pair = var1[1][0], var2[1][0]
if worker_pair in ban_list:
prob += var1[0] + var2[0] <= 1
# establece los estándares de trabajo:
for worker, vars in vars_by_worker.items():
prob += sum(vars) <= 2
Y finalmente, para imprimir los resultados:
status = prob.solve()
print("Result:", pl.LpStatus[status])
results = []
for shift, vars in vars_by_shift.items():
results.append({
"shift": shift,
"workers": [var[1][0] for var in vars if var[0].varValue == 1],
"dothrakis": dothrakis_by_shift[shift].varValue
})
for result in sorted(results, key=lambda x: x['shift']):
print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))
Y deberíamos estar listos. Ejecuta el código y deberías ver el resultado de la siguiente manera:
Resultado: Óptimo
Shift: 0 trabajadores: Arya dothrakis contratados: 0
Shift: 1 trabajador: Melisandre, Theon, Tyrion, Jaime dothrakis contratados: 0
Shift: 2 trabajadores: Bran, Jon dothrakis contratados: 1
Shift: 3 trabajadores: Bran, Daenerys, Theon, Tyrion, Arya dothrakis contratados: 0
Shift: 4 trabajadores: Melisandre, Jaime dothrakis contratados: 0
Y listo, un resultado que respeta la lista de trabajadores prohibidos sigue las regulaciones laborales y usa juiciosamente a los trabajadores Dothraki.
Este articulo fue escrito por Shanglun Wang. Originalmente publicado en Toptal.
