Lineare ganzzahlige Optimierung mit lpSolve

Im vorherigen Beitrag ( http://www.supplychaindataanalytics.com/solving-a-simple-linear-programming-problem-using-lpsolve-in-r/ ) habe ich gezeigt, wie ein einfaches lineares Optimierungsproblem modelliert und gelöst werden kann das lpSolve-Paket in R.

In diesem Beitrag möchte ich das Thema der Modellierung von Integer-Variablen hinzufügen.

Im vorherigen Beitrag haben wir die Zielfunktion 2x + 3y maximiert, mit der Einschränkung, dass x + y <= 3. Wenn beide Variablen kontinuierlich nichtnegativ sind, ist die Lösung y=3 mit einem optimalen Wert der Zielfunktion gleich 9.

In diesem Beitrag fügen wir als weitere Einschränkung hinzu, dass y eine ganze Zahl sein muss. Außerdem passe ich die anfängliche Einschränkung so an, dass jetzt x + y <= 3,9 ist. Unter Verwendung des lpSolve-Pakets in R kann die Beschränkung der Ganzzahlvariablen berücksichtigt werden, indem der Parameter int.vec angegeben wird, der einen Vektor mit den Indizes der Ganzzahlvariablen darstellt, die vom Problem berücksichtigt werden sollen. In diesem Fall ist der Index 2, da y eine ganze Zahl ist.

Ich beginne damit, ein einfaches lineares Programmierproblem zu lösen, das dem vorherigen ähnlich ist, nur dass x + y <= 3,9 (statt 3,0). Die Zielfunktion bleibt unverändert – daher das nicht ganzzahlige Problem (als Benchmark dienend):

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#,
               #int.vec = f.intvec,        
               #all.int = FALSE
               )

solution

## Success: the objective function is 11.7

Die optimale Lösung des nicht ganzzahligen Problems mit der Nebenbedingung x + y <= 3,9 hat folgendes Optimum (= Maximum).

solution$solution

## [1] 0.0 3.9

Jetzt modelliere und löse ich das obige Modell noch einmal – aber mit y als ganzzahlige Variable.

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

Der Maximalwert der Zielfunktion hat sich unter Berücksichtigung der zusätzlichen ganzzahligen Beschränkung verringert. Der optimale Punkt ist jetzt:

solution$solution

## [1] 0.9 3.0

Wie wir sehen, ist die optimale Lösung nicht mehr, dass y 3,9 ist, sondern dass y gleich 3 ist – was in der Tat ein ganzzahliger Wert ist!

Wenn Sie an linearer Programmierung interessiert sind, lesen Sie bitte meine anderen Blog-Beiträge zu diesem Thema . Bitte schauen Sie sich bei Interesse auch meine Beiträge zur nichtlinearen und quadratischen Programmierung an . Schließlich könnten Sie auch daran interessiert sein, meinen Beitrag zur linearen Programmierung in Python mit dem SciPy-Modul zu lesen.