Übung 03: Dualer Simplex

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Gegeben sei folgende Problemstellung:

maximiere F(X1,X2,X3)=25X1+20X2+15X3u.d.N.X1+X2+X3≥202X1+3X2+2X3≤453X1+2X2+X3≤40X1+4X2≥15X1,X2,X3≥0 \begin{aligned} \text{maximiere } \; & F(X_1, X_2, X_3) = 25 X_1 + 20 X_2 + 15 X_3 \\ \text{u.d.N.} \quad & X_1 + X_2 + X_3 \ge 20 \\ & 2 X_1 + 3 X_2 + 2 X_3 \le 45 \\ & 3 X_1 + 2 X_2 + X_3 \le 40 \\ & X_1 + 4 X_2 \ge 15 \\ & X_1, X_2, X_3 \ge 0 \end{aligned}

  1. Lösen Sie das Problem mit einem geeigneten Simplexverfahren.
  2. Geben Sie die Simplex-Multiplikatoren der einzelnen Iterationen an.
  3. Welche separaten Zielfunktionsänderungen sind zu erwarten, wenn Sie die rechte Seite um jeweils eine Einheit erhöhen?
  4. Bestimmen Sie iterativ eine ganzzahlige Lösung. In jeder Iteration ist eine obere Schranke für eine Variable festzulegen und das resultierende Problem durch Reoptimierung zu lösen.
  5. Wie hoch ist die sogenannte prozentuale Lücke (Solution Gap) zwischen der LP-Lösung und Ihrer ganzzahligen Lösung?
  6. Überprüfen Sie Ihre Lösungen mit Julia.

Ihre Lösung in Julia

Achten Sie auf die Richtungen der Nebenbedingungen (≥\ge und ≤\le gemischt). Nennen Sie Ihr Modell modell:

using JuMP, HiGHS

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

# IHR CODE HIER

optimize!(modell)
# Führen Sie diese Zelle nach Ihrer Lösung aus:
@assert isapprox(objective_value(modell), 1250 / 3; atol = 1e-3) "Noch nicht korrekt. Prüfen Sie die Richtungen der Nebenbedingungen."
println("LP-Lösung korrekt: F* = ", objective_value(modell))

Iterative Beschränkung

Beschränken Sie X1X_1 zunächst nach oben auf 8 (set_upper_bound(modell[:X][1], 8)), lösen Sie erneut, und prüfen Sie das Ergebnis. Heben Sie die Schranke danach wieder auf (delete_upper_bound(modell[:X][1])) und fordern Sie stattdessen X1≥9X_1 \ge 9 (set_lower_bound(modell[:X][1], 9)). Ist eine der beiden Lösungen ganzzahlig?

# Nach dem Teilproblem mit X1 >= 9:
@assert isapprox(objective_value(modell), 405.0; atol = 1e-3) "Noch nicht korrekt. Ist die obere Schranke wieder aufgehoben?"
println("Teilproblem korrekt: F = ", objective_value(modell))

Ganzzahlige Lösung

Ist Ihre Lösung nach der iterativen Beschränkung noch nicht ganzzahlig, müssten Sie von Hand weiter verzweigen. Lassen Sie stattdessen den Solver die beste ganzzahlige Lösung bestimmen: Deklarieren Sie die Variablen ganzzahlig (@variable(modell, X[1:3] >= 0, Int)) und lösen Sie erneut. Berechnen Sie anschließend die prozentuale Lücke zur LP-Lösung: Gap=1−Fganzzahlig/FLP\text{Gap} = 1 - F_{\text{ganzzahlig}} / F_{\text{LP}}.

@assert isapprox(objective_value(modell), 410.0; atol = 1e-3) "Noch nicht korrekt. Sind alle drei Variablen ganzzahlig deklariert?"
println("Ganzzahlige Lösung korrekt: F* = ", objective_value(modell))
println("Gap = ", round(1 - objective_value(modell) / (1250 / 3); digits = 3))