Lineært heltalsprogram i R med lpSolve

I det forrige indlæg ( http://www.supplychaindataanalytics.com/solving-a-simple-linear-programming-problem-using-lpsolve-in-r/ ) demonstrerede jeg, hvordan et simpelt lineært optimeringsproblem kan modelleres og løses vha. lpSolve-pakken i R.

I dette indlæg vil jeg tilføje emnet modellering af heltalsvariabler.

I det forrige indlæg maksimerede vi objektivfunktionen 2x + 3y, med den begrænsning, at x + y <= 3. Når begge variabler er kontinuert ikke-negative, er løsningen y=3 med den optimale værdi af objektivfunktionen lig med 9.

I dette indlæg tilføjer vi som en anden begrænsning, at y skal være et heltal. Desuden justerer jeg den indledende begrænsning således, at nu x + y <= 3,9. Ved at bruge lpSolve-pakken i R kan heltalsvariablens begrænsning overvejes ved at specificere int.vec-parameteren, der repræsenterer en vektor med indekserne for de heltalsvariabler, der skal tages i betragtning af problemet. I dette tilfælde er indekset 2, da y er et heltal.

Jeg starter med at løse et simpelt lineært programmeringsproblem, der ligner det tidligere, kun at x + y <= 3,9 (i stedet for 3,0). Den objektive funktion er uændret – derfor er dette ikke-heltalsproblemet (der tjener som benchmark):

library(lpSolve)
f.obj <- c(2,3)
f.con <- matrix(c(1,1),nrow=1,byrow=TRUE)
f.dir <- c("<=")
f.rhs <- c(3.9)

solution <- lp(direction = "max",
               objective.in = f.obj,
               const.mat = f.con, 
               const.dir = f.dir, 
               const.rhs = f.rhs
               )

solution

## Success: the objective function is 11.7

Den optimale løsning på ikke-heltalsproblemet med begrænsningen x + y <= 3,9 har følgende optimum (= maksimum).

solution$solution

## [1] 0.0 3.9

Nu modellerer og løser jeg ovenstående model igen – men med y angivet som en heltalsvariabel.

library(lpSolve)
f.obj <- c(2,3)
f.con <- matrix(c(1,1),nrow=1,byrow=TRUE)
f.dir <- c("<=")
f.rhs <- c(3.9)
f.intvec <- c(2)

solution <- lp(direction = "max",
               objective.in = f.obj,
               const.mat = f.con, 
               const.dir = f.dir, 
               const.rhs = f.rhs,
               int.vec = f.intvec
               )

solution

## Success: the objective function is 10.8

Den maksimale værdi af objektivfunktionen i betragtning af den ekstra heltalsbegrænsning er sænket. Det optimale punkt er nu:

solution$solution

## [1] 0.9 3.0

Som vi kan se, er den optimale løsning ikke længere, at y er 3,9, men i stedet at y er lig med 3 – hvilket i sandhed er en heltalsværdi!

Hvis du er interesseret i lineær programmering, så tjek venligst mine andre blogindlæg om dette emne . Også, hvis du er interesseret – tjek mine indlæg om ikke-lineær og kvadratisk programmering . Til sidst er du måske også interesseret i at læse mit indlæg om lineær programmering i Python ved hjælp af SciPy-modulet.