Linear Programming

Methoden

Modellierungsbeispiel

Das Beispiel Butter und Eiscreme stammt aus dem Buch Ferris, Mangasarian, Wright: Linear Programming with MATLAB. SIAM (Society for Industrial and Applied Mathematics), 2008.

Problemstellung: Ein Bauer hat 3 Kühe, die in Summe 22 Gallonen (1 Gallone \(\simeq\) 3.785 Liter) Milch pro Woche geben. Aus der Milch kann er Eiscreme und Butter machen. Er braucht 2 Gallonen Milch für 1 kg Butter und 3 Gallonen Milch für 1 Gallone Eiscreme. Es gibt keine Lagerrestriktionen für Butter. Er kann maximal 6 Gallonen Eiscreme lagern. Er hat 6 Arbeitsstunden pro Woche für die Herstellung zur Verfügung. Für 4 Gallonen Eiscreme benötigt er 1 Stunde, für 1 kg Butter benötigt er ebenfalls 1 Stunde. Die gesamte Produktion kann er zu folgenden Preisen verkaufen (vollständiger Absatz): 5 USD pro Gallone Eiscreme, 4 USD pro kg Butter. Wie viele Gallonen Eiscreme und wie viele kg Butter soll er herstellen, sodass er seinen Profit maximiert?

Modellierung: Entscheidungsvariablen:

\(x_1\): produzierte Gallonen Eiscreme
\(x_2\): produzierte kg Butter

Zielfunktion: Maximiere \(5x_1 + 4x_2\).

Nebenbedingungen:

Lagerung von Eiscreme: \(x_1 \leq 6\)
Arbeitszeit: \(\frac{1}{4}x_1 + x_2 \leq 6\)
verfügbare Milch: \(3x_1 + 2x_2 \leq 22\)
Positivität der Variablen: \(x_1\geq 0, x_2\geq 0\)

Matrixform: \[ \begin{aligned} \max\; 5 x_1 + 4 x_2 & \\ \text{s.t.}\; x_1 & \leq 6 \\ \frac{1}{4}x_1 + x_2 & \leq 6 \\ 3x_1 + 2x_2 & \leq 22 \\ x_1 & \geq 0 \\ x_2 & \geq 0 \end{aligned} \]

Matrixform

Ein lineares Programm (LP) besteht aus

einer linearen Zielfunktion, die maximiert oder minimiert wird und
linearen Nebenbedingungen, d. h. linearen Ungleichungen und linearen Gleichungen.

Durch Multiplikation der Zielfunktion mit -1 wird eine Maximierung zu einer Minimierung. Eine \(\geq\)-Ungleichung wird durch Multiplikation mit -1 zu einer \(\leq\)-Ungleichung. Daher kann ein LP immer in folgender Form geschrieben werden: \[ \begin{aligned} \min\; c_1 x_1 + c_2 x_2 + \ldots + c_n x_n & \\ \text{s. t.}\; A_{11} x_1 + A_{12} x_2 + \ldots + A_{1n} x_n & \leq b_1 \\ \vdots & \leq \vdots \\ A_{m1} x_1 + A_{m2} x_2 + \ldots + A_{mn} x_n & \leq b_m \\ G_{11} x_1 + G_{12} x_2 + \ldots + G_{1n} x_n & = h_1 \\ \vdots & = \vdots \\ G_{p1} x_1 + G_{p2} x_2 + \ldots + G_{pn} x_n & = h_p \end{aligned} \] Mit den entsprechenden Vektoren und Matrizen lässt sich das LP komfortabler als \[ \begin{aligned} \min \; c^T x & \\ \text{s. t.}\; A x & \leq b \\ G x & = h \end{aligned} \] schreiben. Die Vektoren \(c, b\) und \(h\) und die Matrizen \(A\) und \(B\) enthalten die vollständige Information des LP und können daher als Schnittstellenformat zu Solvern dienen. Wir werden den SciPy-Solver linprog und den in PulP enthaltenen Solver CbC verwenden, siehe Implementierung und PulP.

Lineare Funktionen

Definierende Eigenschaften: Eine lineare Funktion von \(\mathbb{R}^n\) nach \(\mathbb{R}\) ist gegeben durch das innere Produkt eines fixen Vektors \(c\) mit einem Variablenvektor \(x\): \[ f(x) = c^T x = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n. \] Jede lineare Funktion erfüllt die Linearitätseigenschaft \[ f(\alpha x + \beta y) = \alpha f(x) + \beta f(y), \] und jede Funktion, die die Linearitätseigenschaft erfüllt, ist von der Form \(f(x) = c^Tx\).

Geometrische Darstellung:

Die Konturlinien einer linearen Funktion in der Ebene sind parallele Geraden, und die Null-Konturlinie geht durch den Ursprung.
Die Konturflächen einer linearen Funktion im Raum sind parallele Ebenen, und die Null-Konturfläche geht durch den Ursprung.

Der Koeffizientenvektor \(c\) der linearen Funktion \(f(x) = c^Tx\) ist orthogonal (=rechtwinklig) zu den Konturlinien bzw. Konturflächen.

Beispiel: Konturplot In Abbildung 1 ist ein Konturplot der linearen Funktion \[ f:\mathbb{R}^2 \rightarrow \mathbb{R}: f(x) = -2x_1 + 3x_2 \] dargestellt. Der Koeffizientenvektor ist \(c = \begin{pmatrix} -2 \\ 3 \end{pmatrix}\), d. h. \(f(x) = c^T x\).

Abbildung 1: Konturlinien einer linearen Funktion

Lineare (Un-)Gleichungen

Eine lineare Gleichung \[ c_1 x_1 + c_2 x_2 + \ldots + c_n x_n = b \] entspricht der Konturlinie/ebene/etc., allg. Hyperebene, \(c^T x = b\) der linearen Funktion \(f(x) = c^T x.\)

Eine lineare Ungleichung \[ c_1 x_1 + c_2 x_2 + \ldots + c_n x_n \leq b \] definiert in \(\mathbb{R}^n\) einen Halbraum und kann mittels der linearen Funktion \(f(x) = c^T x\) als \(c^T x \leq b\) geschrieben werden.

Lösungsstruktur

Wie im Abschnitt Matrixform beschrieben, kann jedes LP mit entsprechenden Vektoren und Matrizen in Vektor-/Matrixform als \[ \begin{aligned} \min \; c^T x & \\ \text{s. t.}\; A x & \leq b \\ G x & = h \end{aligned} \] geschrieben werden.

Begriffe

Eine Entscheidung \(x\) des Entscheidungsraums \(\mathbb{R}^n\) wird zulässiger Punkt (zulässige Entscheidung, zulässiger Entscheidungsvektor) genannt, wenn sie alle Nebenbedingungen (hier \(Ax \leq b\) und \(Gx = h\)) erfüllt.
Der zulässige Bereich eines LP ist die Menge aller zulässigen Punkte.
Der optimale Wert eines LP ist das Optimum (Minimum bzw. Maximum) der Zielfunktion unter den Nebenbedingungen. Er kann auch \(-\infty\) oder \(\infty\) sein.
Ein optimaler Punkt (eine Lösung) eines LP ist ein zulässiger Punkt, der den optimalen Wert erreicht.
Die optimale Menge eines LP ist die Menge aller optimalen Punkte des LP. Ungleichungsform von LPs:

Die Formulierung min. \(c^T x\) unter \(Ax \leq b\) und \(Gx = h\) kann man noch weiter vereinfachen, indem die vorkommenden Gleichungen zu \(\leq\) Ungleichungen umgeschrieben werden. Zum Beispiel entspricht die Gleichung \(3x_1 - 4x_2 = 5\) den beiden Ungleichungen \(3x_1 - 4x_2 \leq 5\) und \(3x_1 - 4x_2 \geq 5\), von denen die zweite durch Multiplikation mit -1 auch zu einer \(\leq\) Ungleichung gemacht wird. Dadurch kann die Gleichung durch die zwei \(\leq\) Ungleichungen \(3x_1 - 4x_2 \leq 5\) und \(-3x_1 + 4x_2 \leq -5\) ersetzt werden.

Jedes LP lässt sich somit auch in der Ungleichungsform \[ \begin{aligned} \min \; c^T x & \\ \text{s. t.}\; A x & \leq b \end{aligned} \] schreiben.

Geometrie

Die Zielfunktion \(c^T x\) eines LP ist eine lineare Funktion, deren Konturlinien Hyperebenen im Entscheidungsraum \(\mathbb{R}^n\) sind.
Die Matrixungleichung \(Ax \leq b\) besteht aus übereinandergestapelten linearen Ungleichungen, die im Entscheidungsraum \(\mathbb{R}^n\) jeweils Halbräume definieren. Der zulässige Bereich des LP, d. h. die Menge aller Entscheidungen \(x\), die die Bedingung \(Ax \leq b\) erfüllen, entspricht somit dem Durchschnitt all dieser Halbräume. Der Durchschnitt von Halbräumen wird Polyeder genannt.

Bemerkungen: Ein Polyeder ist konvex, d. h. für zwei beliebiege Punkte des Polyeders liegt deren Verbindungslinie vollständig im Polyeder: \(\forall x,y\in P=\{x\rvert Ax\leq b\}\) und \(\forall \lambda\) mit \(0\leq \lambda\leq 1\) ist \(\lambda x + (1-\lambda) y \in P\). Der Ausdruck \(\lambda x + (1-\lambda) y\) mit \(0\leq \lambda\leq 1\) wird konvexe Kombination von \(x\) und \(y\) genannt und ergibt einen Punkt auf der Verbindungslinie zwischen \(x\) und \(y\).

Fälle

Ein LP fällt in einen der folgenden fünf Fälle.

Fall A: Es gibt eine eindeutige Lösung an einer Ecke des Polyeders, also genau einen optimalen Punkt. Der optimale Wert ist endlich.
Fall B: Alle Punkte auf einer endlichen Kante des Polyeders sind optimale Punkte. Es gibt somit \(\infty\)-viele Lösungen, die konvexen Kombinationen der optimalen Ecken bilden die optimale Mengen. Der optimale Wert ist endlich.
Fall C: Alle Punkte auf einer unendlichen Kante des Polyeders sind optimale Punkte. Es gibt somit \(\infty\)-viele Lösungen, die keine konvexe Kombinationen von optimalen Ecken sind. Der optimale Wert ist endlich.
Fall D: Das Polyeder ist leer. Es gibt keine zulässigen Punkte. Die Nebenbedingungen schließen sich aus. Das LP heißt unzulässig (engl. infeasible). Der optimale Wert eines Minimierungs-LP ist \(+\infty\), jener eines Maximierungs-LP ist \(-\infty\).
Fall E: Das Polyeder ist unbeschränkt in Richtung der Zielfunktion. Das LP heißt unbeschränkt (engl. unbounded). Der optimale Wert des Minimierungs-LP ist \(-\infty\), jener eines Maximierungs-LP ist \(+\infty\).

Zusammenfassung für Minimierungs-LP:

LP	Polyeder	optimaler Wert	optimale Menge
unzulässig	leer	\(+\infty\)	leer
unbeschränkt	unbeschränkt in Richtung der Zielfunktion	\(-\infty\)	leer
andernfalls	andernfalls	endlich	besteht aus einer oder \(\infty\)-vielen Lösungen

Vergleich mit Status-Rückgabewerten des SciPy LP-Solvers linprog:

status : An integer representing the exit status of the optimization:
    0 : Optimization terminated successfully.
    1 : Iteration limit reached.
    2 : Problem appears to be infeasible.
    3 : Problem appears to be unbounded.
    4 : Numerical difficulties encountered.

Ecken-Theorem

Falls das Polyeder der Nebenbedingungen mindestens eine Ecke hat und der optimale Wert endlich ist, dann gibt es zumindest eine Ecke des Polyeders, die ein optimaler Punkt ist.**

Folgerung: Daher könnte man so vorgehen, dass man zuerst alle Ecken bestimmt und dann jene Ecke(n) mit dem besten Zielfunktionswert als optimale(n) Punkt(e) identifiziert. Diese Vorgehensweise ist für große LP aber nicht effizient.

Simplexalgorithmus: Der Simplexalgorithmus löst ein LP, indem von einer Ecke zu einer nächsten Ecke gesprungen wird, deren Zielfunktionswert besser ist, bis dies nicht mehr möglich ist und dadurch eine Lösung gefunden wurde.

Implementierung

Grafisch

Wir setzen das obige Modellierungsbeispiel fort und betrachten zuerst den Zulässigkeitsbereich und die Konturlinien der Zielfunktion. Aus der Abbildung 2 erkennen wir, dass wir im Fall A sind. Die eindeutige Lösung lautet \((4, 5)\), und der optimale Wert ist 40. Die optimale Menge besteht aus genau einem Punkt, nämlich \((4, 5)\).

Abbildung 2: Zulässigkeitsbereich und Konturlinien der Zielfunktion

Nun modellieren lösen wir das LP mit dem Solver linprog aus dem Paket SciPy und anschließend mit dem Paket PuLP und dem darin enthaltenen Solver CbC.

SciPy

Wir “füttern” den Solver linprog mit den Daten des Problems, d. h. mit den Vektoren und Matrizen, die die Zielfunktion und die Nebenbedingungen eindeutig beschreiben:

Code

from scipy.optimize import linprog

c = np.array([-5, -4])      # negativ für Minimierung
A = np.array([[   1,  0],   # Lager
              [0.25,  1],   # Zeit
              [   3,  2]])  # Milch
b = np.array([6, 6, 22])
res = linprog(c, A_ub=A, b_ub=b) # by default bounds are (0, None)!
print("Resultate gesamt:\n", res)
print("optimaler Wert:", -res.fun)
print("optimaler Punkt:", res.x)

Resultate gesamt:
         message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: -40.0
              x: [ 4.000e+00  5.000e+00]
            nit: 2
          lower:  residual: [ 4.000e+00  5.000e+00]
                 marginals: [ 0.000e+00  0.000e+00]
          upper:  residual: [       inf        inf]
                 marginals: [ 0.000e+00  0.000e+00]
          eqlin:  residual: []
                 marginals: []
        ineqlin:  residual: [ 2.000e+00  0.000e+00  0.000e+00]
                 marginals: [-0.000e+00 -8.000e-01 -1.600e+00]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0
optimaler Wert: 40.0
optimaler Punkt: [4. 5.]

Varianten und ihre Solverantworten:

Fall B: Alle Punkte auf einer endlichen Kante des Polyeders sind optimale Punkte.

Code

c = np.array([-3, -2])   # Zielfunktion parallel zur Milch-Nebenbedingung
A = np.array([[   1,  0],
              [0.25,  1],
              [   3,  2]])
b = np.array([6, 6, 22])
res = linprog(c, A_ub=A, b_ub=b)
print(res)

# optimaler Wert des zurückgegebenen optimalen Punktes:
print(-np.dot(c, res.x)) 

# (4,5) ist auch optimaler Punkt:
y = np.array([4, 5]) 
print(-np.dot(c, y)) 

# konvexe Kombination:
lbd = 0.123
print(-np.dot(c, lbd*res.x + (1-lbd)*y))

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: -22.0
              x: [ 6.000e+00  2.000e+00]
            nit: 1
          lower:  residual: [ 6.000e+00  2.000e+00]
                 marginals: [ 0.000e+00  0.000e+00]
          upper:  residual: [       inf        inf]
                 marginals: [ 0.000e+00  0.000e+00]
          eqlin:  residual: []
                 marginals: []
        ineqlin:  residual: [ 0.000e+00  2.500e+00  0.000e+00]
                 marginals: [-0.000e+00 -0.000e+00 -1.000e+00]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0
22.0
22
22.0

Fall D: Das Polyeder ist leer. Der optimale Wert eines Minimierungs-LP ist \(+\infty\).

Code

# Ungleichheitszeichen aller Nebenbedingungen umdrehen:
c = np.array([-5, -4])
A = np.array([[   -1,  0],
              [-0.25,  -1],
              [   -3,  -2]])
b = np.array([-6, -6, -22])
res = linprog(c, A_ub=A, b_ub=b, bounds=(None, 0))  # bounds geändert
print(res)

       message: The problem is infeasible. (HiGHS Status 8: model_status is Infeasible; primal_status is At lower/fixed bound)
       success: False
        status: 2
           fun: None
             x: None
           nit: 0
         lower:  residual: None
                marginals: None
         upper:  residual: None
                marginals: None
         eqlin:  residual: None
                marginals: None
       ineqlin:  residual: None
                marginals: None

Fall E: Das Polyeder ist unbeschränkt in Richtung der Zielfunktion. Der optimale Wert des Minimierungs-LP ist \(-\infty\).

Code

c = np.array([5, 4])  # Vorzeichen geändert
A = np.array([[   1,  0],
              [0.25,  1],
              [   3,  2]])
b = np.array([6, 6, 22])

res = linprog(c, A_ub=A, b_ub=b, bounds=(None, 0))  # bounds geändert
print(res)

       message: The problem is unbounded. (HiGHS Status 10: model_status is Unbounded; primal_status is At upper bound)
       success: False
        status: 3
           fun: None
             x: None
           nit: 0
         lower:  residual: None
                marginals: None
         upper:  residual: None
                marginals: None
         eqlin:  residual: None
                marginals: None
       ineqlin:  residual: None
                marginals: None

PuLP

PuLP ist eine Python-Bibliothek zur benutzerfreundlichen Modellierung und Lösung von LPs, siehe PuLP.

Code

import pulp

prob = pulp.LpProblem("Butter_Eiscreme", pulp.LpMaximize)
x1 = pulp.LpVariable("x1", 0, 6)     # 0 <= x1 <= 6, Lager
x2 = pulp.LpVariable("x2", 0, None)  # 0 <= x2
prob += 5*x1 + 4*x2        # Zielfunktion
prob += 0.25*x1 + x2 <= 6  # Arbeitszeit
prob += 3*x1 + 2*x2 <= 22  # Milch
prob.solve()  # Lösen des LP mit Cbc Solver
print("Status:", pulp.LpStatus[prob.status])
print("optimaler Wert:", pulp.value(prob.objective))
print("optimaler Punkt:", x1.varValue, x2.varValue)

Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - /home/kr/.local/lib/python3.11/site-packages/pulp/solverdir/cbc/linux/64/cbc /tmp/1dc5068b69c24d96ae71cebbdea4ffa9-pulp.mps -max -timeMode elapsed -branch -printingOptions all -solution /tmp/1dc5068b69c24d96ae71cebbdea4ffa9-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 7 COLUMNS
At line 14 RHS
At line 17 BOUNDS
At line 19 ENDATA
Problem MODEL has 2 rows, 2 columns and 4 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 2 (0) rows, 2 (0) columns and 4 (0) elements
0  Obj -0 Dual inf 8.9999998 (2)
0  Obj -0 Dual inf 8.9999998 (2)
3  Obj 40
Optimal - objective value 40
Optimal objective 40 - 3 iterations time 0.002
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

Status: Optimal
optimaler Wert: 40.0
optimaler Punkt: 4.0 5.0

Schattenpreise

Definition

Der Schattenpreis einer Nebenbedingung ist die Änderung des optimalen Wertes bei Lockerung der Nebenbedingung um eine Einheit.

SciPy

Code

c = np.array([-5, -4])
A = np.array([[   1,  0],    # Lager
              [0.25,  1],    # Zeit
              [   3,  2]])   # Milch
b = np.array([6 + 1, 6, 22]) # Lager um 1 erhöht
res = linprog(c, A_ub=A, b_ub=b)
print(-res.fun)
c = np.array([-5, -4])
A = np.array([[   1,  0],    # Lager
              [0.25,  1],    # Zeit
              [   3,  2]])   # Milch
b = np.array([6, 6 + 1, 22]) # Zeit um 1 erhöht
res = linprog(c, A_ub=A, b_ub=b)
print(-res.fun)
c = np.array([-5, -4])
A = np.array([[   1,  0],    # Lager
              [0.25,  1],    # Zeit
              [   3,  2]])   # Milch
b = np.array([6, 6, 22 + 1]) # Milch um 1 erhöht
res = linprog(c, A_ub=A, b_ub=b)
print(-res.fun)

40.0
40.8
41.6

PuLP

Um die Schattenpreise mit PuLP zu berechnen, verwenden wir eine ausführlichere Formulierung als bisher, vgl. das Beispiel im Abschnitt PuLP.

Code

prob = pulp.LpProblem("Butter_Eiscreme", pulp.LpMaximize)

x1 = pulp.LpVariable("x1", 0, None)  # 0 <= x1
x2 = pulp.LpVariable("x2", 0, None)  # 0 <= x2

prob += 5*x1 + 4*x2        # Zielfunktion

constraint_lager = x1 <= 6
prob += constraint_lager, "Lager"

constraint_zeit = 0.25*x1 + x2 <= 6
prob += constraint_zeit, "Zeit"

constraint_milch = 3*x1 + 2*x2 <= 22
prob += constraint_milch, "Milch"

print(prob)

prob.solve(pulp.COIN(msg=False))
print(f"Schattenpreis Lager: {constraint_lager.pi}")
print(f"Schattenpreis Zeit:  {constraint_zeit.pi}")
print(f"Schattenpreis Milch: {constraint_milch.pi}")

Butter_Eiscreme:
MAXIMIZE
5*x1 + 4*x2 + 0
SUBJECT TO
Lager: x1 <= 6

Zeit: 0.25 x1 + x2 <= 6

Milch: 3 x1 + 2 x2 <= 22

VARIABLES
x1 Continuous
x2 Continuous

Schattenpreis Lager: -0.0
Schattenpreis Zeit:  0.8
Schattenpreis Milch: 1.6

Beispiele

TODO: Beispiele aus Aufgaben?

TODO: Maximaler Fluss -> Praxisbeispiel

TODO: Schattenpreise

Aufgaben

TODO: Aufgaben von ETW-AM 3: Aufgaben, Kurztestfragen, Programmierprojekte?, Lösungen in PuLP und linprog angeben, Aufgaben zu Schattenpreisen (erweitern)

Verständnisfragen und kurze Aufgaben

Ein LP-Solver liefert als Rückgabe die Meldung The LP is infeasible (Anm. deutsch: unzulässig). Was schließen Sie über den zulässigen Bereich des LP?
Ein LP-Solver liefert als Rückgabe die Meldung Optimal value = 123.45. Wie viele Lösungen hat das LP?
Erklären Sie den Begriff Schattenpreis.
Ein LP-Solver liefert als Rückgabe die Meldung The LP is unbounded (Anm. deutsch: unbeschränkt). Was schließen Sie über den zulässigen Bereich des LP?
Erklären Sie die Begriffe “Polyeder” und “optimale Menge eines LP”?
Bringen Sie das LP max. \(3x_1 + 4x_2\) s. t. \(x_1 + x_2 = 1\) und \(2x_1 - 3x_2 \geq 6\) in die Ungleichungsform min. \(c^T x\) s. t. \(Ax \leq b\), d. h., bestimmen Sie \(c\), \(A\) und \(b\).
Bringen Sie das LP max. \(x_1 + x_2\) s. t. \(3x_1 - x_2 \geq 1\) und \(2x_1 + x_2 \leq 6\) in die Ungleichungsform min. \(c^T x\) s. t. \(Ax \leq b\), d. h., bestimmen Sie \(c\), \(A\) und \(b\).
Welche mögliche Lösungsstrukturen (Anzahl der Lösungen und zugehöriger optimaler Wert) haben lineare Optimierungen min \(c^Tx\) s. t. \(Ax\leq b\)?
Ein LP-Solver liefert als Rückmeldung The LP is unbounded (deutsch: unbeschränkt). Welche Aussage können Sie über den zulässigen Bereich treffen, und was ist der optimale Wert des linearen Optimierungsproblems bei einer Minimierung der Zielfunktion?
Wie viele Lösungen kann ein lineares Optimierungsproblem mit Nebenbedingungen \(Ax\leq b\) haben?
Ein Mobilfunkbetreiber möchte seinen monatlichen Gewinn durch einen neuen Handytarif maximieren. Zum Tarif Speedy um 10 EUR/Monat kommt der Tarif Basic um 5 EUR/Monat dazu. Wie lautet die Zielfunktion des linearen Optimierungsproblems bei einer Formulierung als Minimierungsproblem min. \(c^T x\)?
Für beide Tarife aus Aufgabe 11) wird ein monatliches Datenvolumen von 5 GB angeboten. Die vertraglich zugesicherte Downloadgeschwindigkeit beträgt beim Tarif Speedy 30 Mbit/s und beim Tarif Basic 5 Mbit/s. Beim Tarif Speedy sind darüber hinaus 4 GB EU-Datenroaming inkludiert. Der Mobilfunkbetreiber kann ingesamt ein monatliches Datenvolumen von maximal 1000 GB, eine maximale Downloadgeschwindigkeit von 2000 Mbit/s sowie bis zu 240 GB EU-Datenroaming bereitstellen. Formulieren Sie sämtliche Nebenbedingungen des linearen Optimierungsproblems in der Form \(Ax\leq b\).
Lösen Sie das in den Aufgaben 11) und 12) definierte lineare Optimierungsproblem graphisch. Zeichnen Sie den Punkt ein, bei dem sich für den Mobilfunkbetreiber der maximale monatliche Gewinn ergibt. Sollten Sie Aufgabe 4) nicht lösen können, lösen Sie in dieser Aufgabe stattdessen das lineare Optimierungsproblem, das durch das nachfolgende Ungleichungssystem und die Zielfunktion aus Aufgabe 3) gegeben ist: \[ \begin{pmatrix} 0 & 2 \\ 15 & 2 \\ -1 & 0 \\ 0 & -1 \\ 40 & 40 \\ \end{pmatrix} x \leq \begin{pmatrix} 350 \\ 1000 \\ 0 \\ 0 \\ 8000 \\ \end{pmatrix} \]

2D-Beispiel 1

Zulässigkeitsbereich, Konturlinien, optimaler Wert, optimale Punkte, Implementierung mit linprog:

Zeichnen Sie auf Papier den Zulässigkeitsbereich für folgende Nebenebedingungen \(x_1 + 2x_2 \leq 6\), \(2x_1 + x_2 \leq 6\), \(x_1 \geq 0\), \(x_2 \geq 0\).
Zeichnen Sie zusätzlich die Konturlinien der Profitfunktion \(f(x) = 2x_1 + 4x_2\).
Ermitteln Sie grafisch den optimalen Wert und alle optimalen Punkte des LP, die die Profitfunktion unter den Nebenbedingungen maximieren.
Überprüfen Sie das Ergebnis mit linprog.

2D-Beispiel 2

Zulässigkeitsbereich, Konturlinien, optimaler Wert, optimale Punkte, Implementierung mit linprog:

Zeichnen Sie auf Papier den Zulässigkeitsbereich für folgende Nebenebedingungen \(-2x_1 + x_2 \leq 1\), \(x_1 + 3x_2 \geq 2\), \(x_1 \geq 0\), \(x_2 \geq 0\)
Zeichnen Sie zusätzlich die Konturlinien der Kostenfunktion \(f(x) = 3x_1 + 2x_2\).
Ermitteln Sie grafisch den optimalen Wert und alle optimalen Punkte des LP, die die Kostenfunktion unter den Nebenbedingungen minimieren.
Überprüfen Sie das Ergebnis mit linprog.

Förster

Dieses Beispiel stammt aus dem Buch Linear Programming von Vasek Chvatal. Ein Förster hat 100 Hektar Wald mit Hartholz und hat folgende zwei Möglichkeiten.

Option 1: Hartholz fällen und anschließende Regeneration, Kosten 10 EUR/ha, späterer Erlös 50 EUR/ha
Option 2: Hartholz fällen und anschließend mit Pinien aufforsten, Kosten 50 EUR/ha, späterer Erlös 120 EUR/ha

Die daraus resultierenden späteren Gewinne sind somit 40 EUR/ha und 70 EUR/ha. Er hat momentan 4000 EUR zur Verfügung und fragt sich, wie viele der 100 Hektar er mit welcher Option bewirtschaften soll, um seinen Gewinn zu maximieren.

Formulieren Sie das lineare Problem (LP) der Profitmaximierung.
Lösen Sie das LP mit graphischen Mitteln durch händisches Rechnen.
Lösen Sie das LP in Python mit linprog und pulp.

Produktionsplanung

Gegeben seien 2 Produkte A und B, die aus dem Rohstoffen R\(_1\), R\(_2\), und R\(_3\) hergestellt werden können. Untenstehende Tabelle zeigt die für die Produktion nötigen Mengen zur Herstellung einer Einheit des jeweiligen Produkts sowie die zur Verfügung stehende Menge an Rohstoffen.

Rohstoff	Produkt A	Produkt B	verfügbare Menge
R\(_1\)	5	10	3000
R\(_2\)	0	3	750
R\(_3\)	4	2	1200

Der erwirtschaftete Profit für eine Einheit des Produkts A ist 200 EUR und 300 EUR für Produkt B.

Formulieren Sie das lineare Problem (LP) der Profitmaximierung.
Lösen Sie das LP graphisch.
Lösen Sie das LP in Python mit linprog und mit PuLP.

Kupfer-Zinn Legierung

Drei Klassen Altmetall werden geschmolzen, um 200 kg Kupfer-Zinn Legierung zu erhalten.

Klasse 1 enthält 80 % Kupfer, 20 % Zinn und kostet EUR 6 pro kg.
Klasse 2 enthält 40 % Kupfer, 60 % Zinn und kostet EUR 3 pro kg.
Klasse 3 enthält 10 % Kupfer, 90 % Zinn und kostet EUR 4 pro kg.

Die Legierung soll maximal 60 % Kupfer und 50 % Zinn enthalten.

Formulieren Sie das lineare Problem (LP) der Kostenminimierung.
Lösen Sie das LP in Python mit linprog und mit PuLP.

Fluss in einem Netzwerk

Das folgende Beispiel stammt aus dem Buch Matousek, Gärtner: Understanding and Using Linear Programming. Springer 2007, section 2.2 p. 14ff.

Betrachten Sie den Graphen in der Abbildung unten, der beispielsweise ein Energie- oder Informationsnetzwerk modellieren könnte. Er hat die Knoten \(s\) (Quelle), \(a\), \(b\), \(c\), \(d\), \(e\) und \(t\) (Ziel). Die Knoten \(a\), \(b\), \(c\), \(d\) und \(e\) können keine Energie bzw. Information zwischenspeichern. Die Kanten haben die angegeben Kapazitäten (= maximale Transferraten).

Berechnen Sie in Python mit Hilfe eines LP die maximale Energie- bzw. Informationsübertragungsrate vom Knoten \(s\) zum Knoten \(t\).

Tierfuttermischung

Sie sollen die optimalen Mengen von drei Zutaten in einer Tierfuttermischung bestimmen. Das Endprodukt hat mehrere Nährstoffbedingungen zu erfüllen. Die möglichen Zutaten, ihre Nährstoffe (in kg Nährstoff pro kg Zutat) und die Zutatenpreise (in EUR pro Kilogramm) sind in der folgenden Tabelle dargestellt.

Zutat	Kalzium	Eiweiß	Balaststoffe	Preis
Kalk	0.380	0.00	0.00	10.0
Getreide	0.001	0.09	0.02	30.5
Sojamehl	0.002	0.50	0.08	90.0

Die Mischung muss die folgenden Bedingungen erfüllen:

Kalzium: mindestens 0.8 %, aber nicht mehr als 1.2 %
Eiweiß: mindestens 8 %
Balaststoffe: höchstens 5 %

Das Problem besteht darin, jene Zusammensetzung der Futtermittelmischung zu finden, die die Nebenbedingungen erfüllt und die Kosten minimiert. Formulieren Sie diese Problem als LP in der Form: \[ \begin{aligned} \min\; & c^Tx \\ \text{s. t.}\; & Ax\leq b \\ & Gx=h. \end{aligned} \]

Energiespeicher

Sie haben 24 Stunden Zeit, um einem Kunden 300 kWh Energie zur Verfügung zu stellen, indem Sie ihm einen anfänglich leeren Energiespeicher befüllen. Die maximale Einspeisleistung beträgt 20 kW, und Energie kann nicht aus dem Speicher zurück ins Energieversorgungsnetz geführt werden. Die Energiepreise sind für jede Stunde durch \(c_1, c_2, ..., c_{24}\) gegeben. Der Speicher hat einen Ladewirkungsgrad von 90 %, d. h. 90 % der in den Speicher eingespeisten Energie kann der Kunde tatsächlich nutzen.

Formulieren Sie das Optimerungsproblem, das die gesamtkostenoptimalen Einspeiseenergien für jede Stunde liefert.

Separation von Erzen

Erz aus drei verschiedenen Minen wird von einer Firma vor dem Weitertransport in drei unterschiedliche Güteklassen separiert. Die täglichen Produktionskapazitäten der Minen und ihre täglichen Betriebskosten sind in der folgenden Tabelle angeführt.

Mine	Tonnen/Tag hohe Güte	Tonnen/Tag niedrige Güte	Betriebskosten/Tag in 1000 EUR
1	4	4	20
2	6	4	22
3	1	6	18

Die Firma muss mindestens 54 Tonnen Erz hoher Güte und mindestens 65 Tonnen Erz niedriger Güte pro Woche liefern. Gesucht sind die Betriebstage pro Woche für jede Mine, sodass die Firma ihre Lieferversprechen bei minimalen Kosten einhält.

Formulieren Sie dieses lineare Problem in Matrixform.
Lösen Sie das Problem in Python mit linprog und mit PuLP.

Quelle: Schaum’ Outlines: Operations Research, Aufgabe 1.5, S. 5