Übung 05: Sonderfälle

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Das lineare Optimierungsproblem

$$\begin{aligned} \text{maximiere } \; & F(X_1, X_2) = X_1 + X_2 \\ \text{u.d.N.} \quad & X_1 + X_2 \le 4 \\ & X_1 \le 2 \\ & X_1, X_2 \ge 0 \end{aligned}$$

ist dual degeneriert (vgl. Vorlesung 5). Ist das duale Problem ebenfalls degeneriert? Überführen Sie dazu das primale Problem in das äquivalente duale Problem (Übung 4) und lösen Sie es.

Ihre Lösung in Julia

Modellieren Sie das primale Problem und nennen Sie Ihr Modell modell. Betrachten Sie anschließend die reduzierten Kosten der Nichtbasisvariablen (reduced_cost). Woran erkennen Sie die duale Degeneration?

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), 4.0; atol = 1e-4) "Noch nicht korrekt. Prüfen Sie Zielfunktion und Nebenbedingungen."
println("Aufgabe 1 korrekt: F* = ", objective_value(modell))

Aufgabe 2

Das lineare Optimierungsproblem

$$\begin{aligned} \text{maximiere } \; & F(X_1, X_2) = X_1 + 2 X_2 \\ \text{u.d.N.} \quad & X_1 + X_2 \le 4 \\ & X_1 \le 2 \\ & X_2 \le 2 \\ & X_1, X_2 \ge 0 \end{aligned}$$

ist primal degeneriert (vgl. Vorlesung 5). Ist das duale Problem ebenfalls degeneriert?

Ihre Lösung in Julia

Modellieren Sie das primale Problem als modell. Wie viele Basisvariablen haben in der optimalen Lösung einen Wert von null?

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

# IHR CODE HIER

optimize!(modell)

TippSelbstkontrolle

@assert isapprox(objective_value(modell), 6.0; atol = 1e-4) "Noch nicht korrekt. Haben Sie alle drei Nebenbedingungen erfasst?"
println("Aufgabe 2 korrekt: F* = ", objective_value(modell))

Aufgabe 3

Überprüfen Sie, ob das duale Problem von dem Primalproblem

$$\begin{aligned} \text{maximiere } \; & F(X_1, X_2) = X_1 + 2 X_2 \\ \text{u.d.N.} \quad & X_1 + X_2 \le 4 \\ & X_1 \ge 3 \\ & X_1 - X_2 \le 0 \\ & X_1, X_2 \ge 0 \end{aligned}$$

eine zulässige Lösung besitzt.

Ihre Lösung in Julia

Dualisieren Sie das Problem von Hand und modellieren Sie das duale Problem als modell. Lesen Sie den Status mit termination_status(modell) ab. Was sagt er über das primale Problem aus (vgl. Vorlesung 4 und 5)?

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

# IHR CODE HIER

optimize!(modell)
termination_status(modell)

TippSelbstkontrolle

@assert termination_status(modell) == DUAL_INFEASIBLE "Noch nicht korrekt. Erwartet wird ein unbeschränktes duales Problem."
println("Aufgabe 3 korrekt: das duale Problem ist unbeschränkt. Das primale Problem hat keine zulässige Lösung.")

Aufgabe 4

Überprüfen Sie, ob das duale Problem von dem Primalproblem

$$\begin{aligned} \text{maximiere } \; & F(X_1, X_2) = X_1 + 2 X_2 \\ \text{u.d.N.} \quad & X_1 - X_2 \le 4 \\ & X_1 + X_2 \ge 4 \\ & X_1, X_2 \ge 0 \end{aligned}$$

eine optimale Lösung besitzt.

Ihre Lösung in Julia

Modellieren Sie wieder das duale Problem als modell und lesen Sie den Status ab:

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

# IHR CODE HIER

optimize!(modell)
termination_status(modell)

TippSelbstkontrolle

@assert termination_status(modell) == INFEASIBLE "Noch nicht korrekt. Erwartet wird ein unzulässiges duales Problem."
println("Aufgabe 4 korrekt: das duale Problem ist unzulässig. Das primale Problem ist unbeschränkt.")