Resolvendo problema de transporte linear com lp.transport em R, usando lpSolve

O problema de transporte é um dos problemas clássicos ensinados nas aulas de programação linear . O problema, simplificado, afirma que um determinado conjunto de clientes com uma demanda específica deve ser atendido por outro conjunto de fornecedores com determinadas capacidades (“oferta”). Para obter uma explicação detalhada do problema de transporte, você pode, por exemplo, ler isto: https://econweb.ucsd.edu/~jsobel/172aw02/notes8.pdf .

O pacote lpSolve disponível em R pode ser usado para modelar e resolver o problema de transporte.

Vou mostrar como fazer isso. Defino um problema em que 3 fornecedores procuram satisfazer 4 clientes. Os fornecedores têm capacidades 100, 300 e 400, respectivamente. Os clientes têm demanda de 100, 100, 200 e 400, respectivamente. Além disso, o custo de abastecimento do cliente i pelo fornecedor j é definido para cada combinação possível e expresso em uma matriz de custos.

Usando essas informações, podemos modelar e resolver o problema de transporte (decidindo qual demanda atender por qual fornecedor) com o pacote lpSolve em R.

Primeiro, preparo a parte de modelagem:

library(lpSolve)

# specifying cost matrix 
cost.mat <- matrix(nrow=3,ncol=4)
cost.mat[1,] <- 1:4
cost.mat[2,] <- 4:1
cost.mat[3,] <- c(1,4,3,2)

# this is a minimization problem
direction = "min"

# capacity may not be exceeded
row.signs <- rep("<=",3)
row.rhs <- c(100,300,400)

# demand must be satisfied
col.signs <- rep(">=",4)
col.rhs <- c(100,100,200,400)

Então resolvo o problema:

# solve and assign lp object
solution <- lp.transport(cost.mat = cost.mat,
                         direction = direction,
                         row.signs = row.signs,
                         row.rhs = row.rhs,
                         col.signs = col.signs,
                         col.rhs = col.rhs)

Vamos revisar os custos “ótimos”:

solution

## Success: the objective function is 1400

Vamos revisar a solução ótima do problema de transporte (isto é, os fluxos ótimos de material para este problema):

solution$solution

##      [,1] [,2] [,3] [,4]
## [1,]    0  100    0    0
## [2,]    0    0  200  100
## [3,]  100    0    0  300

O problema de atribuição é outro problema clássico, e você pode ver como o resolvi em R aqui: Programação de produção de custo mínimo – resolvendo o problema de atribuição com lpSolve, usando lp.assign.