A pesquisa operacional, a ciência de usar computadores para tomar decisões otimizadas, tem sido usada e aplicada em muitas áreas do software. Para dar alguns exemplos, as empresas de logística o usam para determinar a rota ideal para ir do ponto A ao ponto B, as empresas de energia o usam para determinar os cronogramas de produção de energia e as empresas de manufatura o usam para encontrar os padrões ideais de pessoal para suas fábricas.
Hoje, vamos explorar o poder da pesquisa operacional examinando um problema hipotético. Especificamente, usaremos a programação inteira mista (MIP) para determinar o padrão de pessoal ideal para uma fábrica hipotética.
Algoritmos de pesquisa operacional
Antes de mergulharmos em nosso problema de exemplo, é útil revisar alguns conceitos básicos em pesquisa operacional e entender um pouco das ferramentas que usaremos hoje.
Algoritmos de programação linear
A programação linear é uma técnica de pesquisa operacional usada para determinar o melhor resultado em um modelo matemático onde o objetivo e as restrições são expressos como um sistema de equações lineares. Um exemplo de modelo de programação linear pode ter a seguinte aparência:
Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2) Em nosso exemplo muito simples, podemos ver que o resultado ideal é 5, com a = 2 e b = 3. Embora este seja um exemplo bastante trivial, você provavelmente pode imaginar um modelo de programação linear que utiliza milhares de variáveis e centenas de restrições .
Um bom exemplo pode ser um problema de portfólio de investimento, onde você pode acabar com algo como o abaixo, em pseudo-código:
Maximize Subject to: Etc. ... O que seria bastante complexo e difícil de resolver manualmente ou por tentativa e erro. O software de pesquisa operacional usará vários algoritmos para resolver esses problemas rapidamente. Se você estiver interessado nos algoritmos subjacentes, recomendo aprender sobre o método simplex Aqui e o método do ponto interior Aqui .
Algoritmos de programação inteira
A programação inteira é como a programação linear com uma permissão adicional para que algumas ou todas as variáveis sejam valores inteiros. Embora isso possa não parecer uma grande melhoria no início, nos permite resolver muitos problemas que poderiam ter permanecido sem solução usando apenas a programação linear.
Um desses problemas é o problema da mochila, em que recebemos um conjunto de itens com valores e pesos atribuídos e somos solicitados a encontrar a combinação de itens de maior valor que podemos colocar em nossa mochila. Um modelo de programação linear não será capaz de resolver isso porque não há como expressar a ideia de que você pode colocar um item em sua mochila ou não, mas não pode colocar parte de um item em sua mochila - cada variável é contínua variável!
Um exemplo de problema de mochila pode ter os seguintes parâmetros:
| Objeto | Valor (unidades de $ 10) | Tamanho (unidades genéricas) |
|---|---|---|
| Câmera | 5 | 2 |
| Estatueta misteriosa | 7 | 4 |
| Garrafa enorme de cidra de maçã | 2 | 7 |
| Trompa francesa | 10 | 10 |
E o modelo MIP terá a seguinte aparência:
Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint) A solução ótima, neste caso, é a = 0, b = 1, c = 0, d = 1, com o valor do item total sendo 17.
qual é melhor c corp ou s corp
O problema que resolveremos hoje também exigirá programação inteira, já que um funcionário em uma fábrica pode ser escalado para um turno ou não - por uma questão de simplicidade, você não pode programar um funcionário para 2/3 de um turno nesta fábrica.
Para tornar a programação inteira possível, vários algoritmos matemáticos são usados. Se você estiver interessado nos algoritmos subjacentes, recomendo estudar o algoritmo de planos de corte e o algoritmo branch-and-bound Aqui .
Exemplo de problema: programação
Descrição do Problema
Hoje, vamos explorar o problema do pessoal de uma fábrica. Como gestão da fábrica, queremos minimizar os custos de mão de obra, mas queremos garantir cobertura suficiente para cada turno para atender à demanda de produção.
Suponha que temos cinco turnos com as seguintes demandas de pessoal:
| Turno 1 | Turno 2 | Turno 3 | Turno 4 | Turno 5 |
|---|---|---|---|---|
| 1 pessoa | 4 pessoas | 3 pessoas | 5 pessoas | 2 pessoas |
E, suponha que temos os seguintes trabalhadores:
| Nome | Disponibilidade | Custo por turno ($) |
|---|---|---|
| Melisandre | 1, 2, 5 | vinte |
| Farelo | 2. 3. 4. 5 | quinze |
| Cersei | 3. 4 | 35 |
| Daenerys | Quatro cinco | 35 |
| Theon | 2, 4, 5 | 10 |
| Jon | 1, 3, 5 | 25 |
| Tyrion | 2, 4, 5 | 30 |
| James | 2, 3, 5 | vinte |
| Arya | 1, 2, 4 | vinte |
Para simplificar o problema, vamos supor, por enquanto, que a disponibilidade e o custo são as únicas preocupações.
Nossas Ferramentas
Para o problema de hoje, usaremos um software branch-and-cut de código aberto chamado CBC. Faremos a interface com este software usando PuLP, que é uma biblioteca popular de modelagem de pesquisa de operações para Python. Você pode encontrar informações sobre isso Aqui .
O PuLP nos permite construir modelos MIP de uma maneira muito Pythônica e se integra perfeitamente ao código Python existente. Isso é muito útil, pois algumas das ferramentas mais populares de manipulação e análise de dados são escritas em Python, e a maioria dos sistemas de pesquisa de operações comerciais exige um processamento extensivo de dados antes e depois da otimização.
Para demonstrar a simplicidade e elegância do PuLP, aqui está o problema da mochila anterior e resolvido no PuLP:
como programar um robô com python
import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack 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 the problem prob = pl.LpProblem('knapsack', pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print('a', pl.value(a)) print('b', pl.value(b)) print('c', pl.value(c)) print('d', pl.value(d)) Execute isso e você deve obter o resultado:
Optimal a 0.0 b 1.0 c 0.0 d 1.0 Agora vamos ao nosso problema de agendamento!
Codificando nossa solução
A codificação de nossa solução é bastante direta. Primeiro, vamos definir nossos dados:
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 seguir, vamos definir o modelo:
# define the model: we want to minimize the cost prob = pl.LpProblem('scheduling', pl.LpMinimize) # some model variables 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']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement E agora é só pedir para resolver e imprimir os 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'])) Depois de executar o código, você verá os seguintes resultados:
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 Aumente um pouco a dificuldade: restrições adicionais
Mesmo que o modelo anterior seja interessante e útil, ele não demonstra totalmente o poder da programação inteira mista. Também poderíamos escrever facilmente um for loop para encontrar o mais barato x trabalhadores para cada turno, onde x é o número de trabalhadores necessários para um turno. Para demonstrar como o MIP pode ser usado para resolver um problema que seria desafiador de resolver de forma imperativa, vamos examinar o que aconteceria se adicionássemos algumas restrições extras.
Restrições Adicionais
Suponha que, devido aos novos regulamentos trabalhistas, nenhum trabalhador possa ser designado para mais de 2 turnos. Para compensar o aumento de trabalho, recrutamos a ajuda do Dothraki Staffing Group, que fornecerá até 10 trabalhadores Dothraki para cada turno a uma taxa de $ 40 por turno.
Além disso, suponha que, devido a alguns conflitos interpessoais em andamento fora de nossa fábrica, Cersei e Jaime não possam trabalhar em nenhum turno ao lado de Daenerys ou Jon. Além disso, Jaime e Cersei não conseguem trabalhar em nenhum turno juntos. Finalmente, Arya, que tem relacionamentos interpessoais particularmente complexos, não consegue trabalhar no mesmo turno com Jaime, Cersei ou Melisandre.
como aprender c ++ sozinho
O acréscimo dessas duas novas restrições e recursos de forma alguma torna o problema insolúvel por meios imperativos, mas torna a solução muito mais difícil, pois será necessário contabilizar os custos de oportunidade de programar um trabalhador para um turno específico.
Solução
Com a programação inteira mista, no entanto, é muito mais fácil. Simplesmente precisamos alterar nosso código da seguinte forma:
Defina a lista de banimentos e algumas restrições:
ban_list = { ('Daenerys', 'Jaime'), ('Daenerys', 'Cersei'), ('Jon', 'Jaime'), ('Jon', 'Cersei'), ('Arya', 'Jaime'), ('Arya', 'Cersei'), ('Arya', 'Melisandre'), ('Jaime', 'Cersei') } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45 Preencher variáveis para implementar as restrições de proibição e deslocamento 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) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost']) Adicione as variáveis 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 Também precisaremos de um loop ligeiramente modificado para calcular os requisitos de mudança e proibição:
# set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements 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 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2 E, finalmente, para imprimir os 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'])) E devemos estar prontos para ir. Execute o código e você verá a saída abaixo:
Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0 E aí está, um resultado que respeita a lista de trabalhadores proibidos, segue as normas trabalhistas e usa os trabalhadores dothraki de forma criteriosa.
Conclusão
Hoje, exploramos o uso de programação inteira mista para tomar melhores decisões. Discutimos os algoritmos e técnicas subjacentes usados na pesquisa operacional e vimos um exemplo de problema que é representativo de como a programação inteira mista é usada no mundo real.
Espero que este artigo tenha inspirado você a aprender mais sobre pesquisa operacional e feito você pensar sobre como essa tecnologia pode ser aplicada a seus projetos. Só vimos realmente a ponta do iceberg quando se trata do emocionante mundo dos algoritmos de otimização e pesquisa operacional.
Você pode encontrar todo o código relacionado a este artigo no GitHub . Se você gostaria de discutir mais, compartilhe seus comentários abaixo!
Compreender o básico
O que é programação linear?
A programação linear é uma técnica de pesquisa operacional usada para determinar o melhor resultado em um modelo matemático onde o objetivo e as restrições são expressos como um sistema de equações lineares.
O que é programação inteira?
A programação inteira é como a programação linear com uma permissão adicional para que algumas ou todas as variáveis sejam valores inteiros.
