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_4
Entradas
0 comments:
Publicar un comentario