Løsning af det klassiske lineære transportproblem med lp.transport i R (lpSolve-pakken)

Transportproblemet er et af de klassiske lineære optimeringsproblemer. Problemet består i, at et givet sæt kunder med en specificeret efterspørgsel skal betjenes af et andet sæt leverandører med en bestemt kapacitet. Spørgsmålet er så: Hvordan kan vi tilfredsstille kundernes efterspørgsel og samtidigt overholde leverandørernes kapacitetsrestriktioner? For en detaljeret forklaring af transportproblemet kan du f.eks. læse denne Artikel: https://econweb.ucsd.edu/~jsobel/172aw02/notes8.pdf.

Den lpSolve-pakke, der er tilgængelig i R, kan bruges til modellering og løsning af transportproblemet. Den har faktisk en funktion som er defineret til netop ovenstående klassiske transportproblem. Og jeg vil vise, hvordan man kan anvende den tilgængelige funktion i lpSolve-pakken.

Jeg definerer et problem hvor 3 leverandører søger at tilfredsstille 4 kunder. Leverandørerne har henholdsvis kapacitet 100, 300 og 400. Kunderne har henholdsvis efterspørgsel 100, 100, 200 og 400. Desuden defineres omkostningerne til levering af kunde i af leverandør j for hver mulig kombination og angives i en omkostningsmatrix. Denne omkostningsmatrix er dokumenteret i R-koden forneden. Ved hjælp af disse oplysninger kan vi modellere og løse transportproblemet.

Her forbereder jeg modelleringsdelen:

library(lpSolve)

# angiver omkostningsmatrix
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)

# dette er et minimeringsproblem
direction = "min"

# kapacitet må muligvis ikke overskrides
row.signs <- rep("<=",3)
row.rhs <- c(100,300,400)

# efterspørgsel skal være opfyldt
col.signs <- rep(">=",4)
col.rhs <- c(100,100,200,400)

Derefter løser jeg problemet:

# løse og tildele lp-objekt
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)

Jeg kan nu angive de “optimale” omkostninger:

solution
## Success: the objective function is 1400

Jeg kan også angive den optimale løsning:

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

Leave a Reply

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Close

Meta