Resolvendo o problema de atribuição (lpSolve)

O problema de atribuição é um problema clássico em programa linear . Se, por exemplo, você tiver n trabalhos que precisam ser fabricados durante o próximo turno (em uma fábrica) e tiver m máquinas para produzir essas tarefas, você deseja atribuir os trabalhos às máquinas de maneira otimizada. Neste caso, você pode querer reduzir os custos de fabricação incorridos, portanto, você deseja encontrar o plano de produção de custo ideal. A restrição, neste exemplo, é que cada máquina só pode realizar um trabalho durante o próximo turno. Todos os trabalhos precisam ser agendados, ou seja, atribuídos a uma máquina.

O problema pode ser declarado em um modelo matemático. Abaixo, o problema é apresentado para um caso em que existem 3 tarefas e 3 máquinas. O custo de produção do trabalho 1 na máquina 1 USD, mas 2 USD ao produzi-lo na máquina 2. O trabalho 2 custa 2 USD na máquina 1 e 3 USD na máquina 2. O trabalho 3 custa 5 USD na máquina 1 e 1 USD na máquina 2. A máquina 3 pode executar o trabalho 1 por 2 USD e os trabalhos 2 e 3 por 3 USD, respectivamente.

O modelo matemático para isso é o seguinte:

Podemos modelar e resolver este problema com o pacote lpSolve em R, um pacote para programação linear (para problemas contínuos e inteiros). A função lp.assign pode fazer o trabalho:

library(lpSolve)

# prepare the cost matrix
cost.mat <- rbind(c(1,2,3),
                     c(2,3,3),
                     c(5,1,3))

# model and solve with lp.assign
solution <- lp.assign(cost.mat=cost.mat,
                      direction="min")

lp.assign é uma função especificamente destinada a resolver o problema de atribuição. O problema de atribuição, por definição, é um problema em que todas as variáveis de decisão são variáveis inteiras. Portanto, não precisamos dizer especificamente a lp.assign que as variáveis de decisão devem ser consideradas como variáveis inteiras.

Vejamos os custos mínimos que devemos enfrentar durante o próximo turno:

solution

## Success: the objective function is 5

Vejamos o plano de produção de custo mínimo para o próximo turno:

solution$solution

##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    0    0    1
## [3,]    0    1    0

O problema do transporte é outro problema clássico. Você pode me ver resolvendo em R – aqui: Resolvendo o problema de transporte de Bronson com lpSolve, usando lp.transport.