Übung 04: Zweiphasenmethode und Dualität

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Gegeben sei folgendes primales Problem:

$$\begin{aligned} \text{minimiere } \; & F(X_1, X_2, X_3) = X_1 + X_2 + X_3 \\ \text{u.d.N.} \quad & X_1 + X_3 \ge 7 \\ & X_1 + X_2 \ge 20 \\ & X_2 + X_3 \ge 14 \\ & X_3 \ge 20 \\ & X_1, X_2, X_3 \ge 0 \end{aligned}$$

1. Wie viele Schlupfvariablen und künstliche Variablen benötigen Sie bei Anwendung der Zweiphasenmethode?
2. Lösen Sie das Problem mit der Zweiphasenmethode.
3. Dualisieren Sie die Problemstellung.
4. Lösen Sie das duale Problem mit einem geeigneten Simplexverfahren.
5. Geben Sie die optimalen Werte von $F$, $X_1$, $X_2$ und $X_3$ (optimale Lösung des primalen Problems) an.
6. Überprüfen Sie Ihre Lösungen mit Julia.

Ihre Lösung in Julia: primales Problem

Modellieren Sie das primale Problem und nennen Sie Ihr Modell modell:

using JuMP, HiGHS

modell = Model(HiGHS.Optimizer)
set_silent(modell)

# IHR CODE HIER

optimize!(modell)

TippSelbstkontrolle

# Führen Sie diese Zelle nach Ihrer Lösung aus:
@assert isapprox(objective_value(modell), 40.0; atol = 1e-4) "Noch nicht korrekt. Prüfen Sie die vier Nebenbedingungen."
println("Primales Problem korrekt: F* = ", objective_value(modell))

HinweisMehrdeutige Lösung

Das primale Problem hat mehrere optimale Ecklösungen (wird in Vorlesung 5 vertieft): Der Solver kann Ihnen andere Werte für $X_1$ und $X_2$ liefern als Ihre Handrechnung. Beide sind korrekt, solange der Zielfunktionswert der Selbstkontrolle standhält.

Ihre Lösung in Julia: duales Problem

Modellieren Sie nun das duale Problem mit den Dualvariablen $W_1, \dots, W_4$ und nennen Sie das Modell wieder modell. Lesen Sie anschließend die primalen Werte aus den Schattenpreisen der dualen Nebenbedingungen ab (shadow_price):

modell = Model(HiGHS.Optimizer)
set_silent(modell)

# IHR CODE HIER

optimize!(modell)

TippSelbstkontrolle

@assert isapprox(objective_value(modell), 40.0; atol = 1e-4) "Noch nicht korrekt. Maximierung? Drei Nebenbedingungen (eine je primaler Variable)?"
println("Duales Problem korrekt: F* = ", objective_value(modell))

HinweisWas fällt auf?

Primales und duales Problem haben denselben optimalen Zielfunktionswert, und jedes enthält die Lösung des jeweils anderen: die Schattenpreise des dualen Endtableaus sind die primalen Variablenwerte (und umgekehrt).