Multiobjektive lineare Optimierung mit PuLP in Python

In einigen meiner Beiträge habe ich lpSolve oder FuzzyLP in R verwendet um lineare Optimierungsprobleme zu lösen. Ich habe auch PuLP und SciPy.optimize in Python verwendet um solche Probleme zu lösen. Diese Probleme hatten alle nur eine einzige Zielfunktion.

In diesem Beitrag möchte ich ein Beispiel in Python bereitstellen, dass das PuLP-Modul zur Lösung eines linearen Optimierungsproblems mit mehreren Zielen bzw. Zielfunktionen verwendet.

Ein lineares Optimierungsproblem mit mehreren Zielen ist ein lineares Optimierungsproblem mit mehr als nur einer Zielfunktion. Dieser Bereich der linearen Programmierung wird auch als lineare Optimierung mit mehreren Zielen oder multiobjektive lineare Optimierung genannt.

Im Folgenden habe ich ein beispielhaftes lineares Optimierungsproblem mit zwei Zielfunktionen lösen:

Unter der Annahme, dass in der obigen Problemstellung die zwei Zielfunktionen zwei verschiedene Ziele darstellen, wie z.B. Kundenzufriedenheit und Gewinnspanne eines Produktportfolios teste ich zwei alternative Ansätze zur Lösung dieses Problems. Es ist ein multiobjektives Optimierungsproblem.

Der erste Ansatz besteht darin, zunächst eines der Ziele zu lösen. D.h. die zweite Zielfunktion wird zunächst ignoriert. Daraufhin wird ein zweiter Optimierungslauf durchgeführt. Dabei wird nun die erste Zielfunktion ignoriert. Zusätzlich wird dabei dir weitere Nebenbedingung berücksichtigt, dass der Optimalwert des ersten Optimierungslaufs (d..h. der ersten Zielfunktion) erreicht werden muss.

Der zweite Ansatz besteht darin, die beiden Ziele zu addieren, d.h. Sie durch Anwendung von Gewichten zu einer Zielfunktion zusammenzuführen. Durch Abtasten der Gewichte und dem Lösen der gewichteten Zielkombination wird so ein Werteraum der möglichen Zielgewichtungen ermittelt.

Ansatz 1: Maximere zunächst ein Ziel, füge es als Nebenbedingung hinzu und löse dann das zweite Ziel

Mit PuLP maximiere ich zuerst das erste Ziel, füge dann den Optimalwert dieser Zielfunktion als Einschränkung dem ursprünglichen Problem hinzu und maximiere das zweite Ziel unter Berücksichtigung aller Einschränkungen, einschließlich dieser zusätzlichen Einschränkung.

In der mathematischen Syntax kann das zuerst gelöste Problem wie folgt angegeben werden:

Hier ist die Implementierung der obigen Problemstellung in Python unter Verwendung des PuLP-Moduls:

# Importiere zuerst PuLP
import pulp

# Führe dann eine erste Problemerklärung durch
linearProblem = pulp.LpProblem("Maximizing for first objective",pulp.LpMaximize)

# Delcare-Optimierungsvariablen mit PuLP
x1 = pulp.LpVariable("x1",lowBound = 0) 
x2 = pulp.LpVariable("x2",lowBound = 0) 

# Füge (erste) Zielfunktion zur linearen Problemstellung hinzu
linearProblem += 2*x1 + 3*x2 

# Füge dem Problem die Einschränkungen hinzu
linearProblem += x1 + x2 <= 10
linearProblem += 2*x1 + x2 <= 15

# Mit Standardlöser lösen, um das erste Ziel zu maximieren
solution = linearProblem.solve()

# Informationen ausgeben, wenn das Optimum gefunden wurde, was der maximale Zielwert ist und was der optimale Punkt ist
print(str(pulp.LpStatus[solution])+" ; max value = "+str(pulp.value(linearProblem.objective))+
      " ; x1_opt = "+str(pulp.value(x1))+
      " ; x2_opt = "+str(pulp.value(x2)))

Optimal ; max value = 30.0 ; x1_opt = 0.0 ; x2_opt = 10.0

Jetzt wiederhole ich das ursprüngliche Problem so, dass die zweite Zielfunktion unter einer zusätzlichen Einschränkung maximiert wird. Diese zusätzliche Einschränkung erfordert, dass das erste Ziel mindestens den Wert 30 erreichen muss. Unter Verwendung der mathematischen Syntax kann das Problem, dass ich jetzt löse, wie folgt angegeben werden:

Hier ist die Implementierung der obigen Problemstellung in Python unter Verwendung von PuLP:

# die Problemstellung umgestalten
linearProblem = pulp.LpProblem("Maximize second objective",pulp.LpMaximize)
linearProblem += 4*x1 - 2*x2
linearProblem += x1 + x2 <= 10
linearProblem += 2*x1 + x2 <= 15
linearProblem += 2*x1 + 3*x2 >= 30

# Überprüfe die Problemstellung nach dem Umbau
linearProblem

Maximize_second_objective:
MAXIMIZE
4*x1 + -2*x2 + 0
SUBJECT TO
_C1: x1 + x2 <= 10

_C2: 2 x1 + x2 <= 15

_C3: 2 x1 + 3 x2 >= 30

VARIABLES
x1 Continuous
x2 Continuous

Jetzt löse ich dieses Problem mit dem Standardlöser in PuLP:

# Standardlöser anwenden
solution = linearProblem.solve()

# gibt eine Zeichenfolge aus, die zusammenfasst, ob das Optimum gefunden wurde und wenn ja, welche Lösung optimal ist
print(str(pulp.LpStatus[solution])+" ; max value = "+str(pulp.value(linearProblem.objective))+
      " ; x1_opt = "+str(pulp.value(x1))+
      " ; x2_opt = "+str(pulp.value(x2)))

Optimal ; max value = -19.999999999995993 ; x1_opt = 1.0018653e-12 ; x2_opt = 10.0

Dieser Ansatz legt nahe, dass x1 = 0 und x2 = 10 die optimale Lösung ist. Die optimalen Zielwerte wären 30 für Ziel #1und -20 für Ziel #2.

Ansatz 2: Kombiniere alle Ziele unter Verwendung von schrittweise-iterativ gewählten Gewichtungen

Wenn wir diesen Ansatz anwenden können wir das ursprüngliche Problem wie folgt notieren:

Die Frage ist nun, wie man α wählen soll.

Ein typischer Ansatz in einer solchen Situation besteht darin, eine effiziente Grenze zu identifizieren. In der Wirtschaft ist dies z.B. unter dem Begriff „Pareto-Optimalität“ bekannt. Eine Lösung ist Pareto-optimal wenn es keine andere Lösung gibt welche mindestens eines der Ziele verbessern kann ohne dabei die anderen Ziele zu verschlechtern. Um einen solchen Ansatz zu konstruieren wähle ich α in Schritten von 0,01. Für jeden α-Wert modelliere und löse ich das Problem erneut mit PuLP in Python.

Ich speichere meine Ergebnisse in einer Liste und visualisiere das Ergebnis mit matplotlib.pyplot:

# importiere matplotlib.pyplot
import matplotlib.pyplot as plt 

# Pandas und Numpy importieren, um Daten im DataFrame-Format speichern zu können
import numpy as np
import pandas as pd

# Schrittgröße definieren
stepSize = 0.01

# Initialisiere einen leeren DataFrame zum Speichern von Optimierungsergebnissen
solutionTable = pd.DataFrame(columns=["alpha","x1_opt","x2_opt","obj_value"])

# Durchlaufe mit stepSize Alpha-Werte von 0 bis 1 und schreiben Sie PuLP-Lösungen in solutionTable
for i in range(0,101,int(stepSize*100)):
        # das Problem erneut deklarieren
        linearProblem = pulp.LpProblem("Multi-objective linear maximization",pulp.LpMaximize)
        # Fügen Sie die Zielfunktion bei abgetastetem Alpha hinzu
        linearProblem += (i/100)*(2*x1+3*x2)+(1-i/100)*(4*x1-2*x2)
        # füge die Einschränkungen hinzu
        linearProblem += x1 + x2 <= 10
        linearProblem += 2*x1 + x2 <= 15
        # das Problem lösen
        solution = linearProblem.solve()
        # Lösungen in DataFrame schreiben
        solutionTable.loc[int(i/(stepSize*100))] = [i/100,
                                                     pulp.value(x1),
                                                     pulp.value(x2),
                                                     pulp.value(linearProblem.objective)]

# Visualisiere das Optimierungsergebnis mithilfe von matplotlib.pyplot
# - Figurengröße einstellen
plt.figure(figsize=(20,10))
# - Liniendiagramm erstellen
plt.plot(solutionTable["alpha"],solutionTable["obj_value"],color="red")
# - Achsenbeschriftungen hinzufügen
plt.xlabel("alpha",size=20)
plt.ylabel("obj_value",size=20)
# - Handlungstitel hinzufügen
plt.title("Optimal combined objective function value as a function of alpha",size=32)
# - Handlung zeigen
plt.show()