Übung 11: Algebraische Modellierung I

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Gegeben sei folgender Graph:

Die Kanten sind mit Kosten ($c_{ij}$) bewertet; z. B. die Kante $[1, 2]$ mit $c_{1,2} = 42$. Eine Kante $[i, j]$ korrespondiert zu den Pfeilen $(i, j)$ und $(j, i)$ mit identischen Bewertungen.

Formulieren Sie ein ganzzahliges Optimierungsproblem zur Bestimmung des kürzesten Wegs von dem Startknoten $q = 2$ (Quelle) zu dem Zielknoten $s = 7$ (Senke). Überprüfen Sie Ihren Ansatz mit Julia.

Ihre Lösung in Julia

Beachten Sie: Jede Kante liefert zwei Pfeile. Nennen Sie Ihr Modell modell:

using JuMP, HiGHS

kanten = [(1,2,42), (1,3,20), (1,4,55), (2,3,41), (2,5,34), (3,4,40),
          (3,5,30), (3,6,55), (4,6,62), (5,7,46), (6,7,65)]
pfeile = vcat([(i,j,c) for (i,j,c) in kanten], [(j,i,c) for (i,j,c) in kanten])

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), 80.0; atol = 1e-4) "Noch nicht korrekt, Quelle ist Knoten 2, Senke Knoten 7."
println("Kürzester Weg von 2 nach 7 korrekt: F* = ", objective_value(modell))

Aufgabe 2

Gegeben sei folgender Graph:

Die Pfeile sind mit Kosten ($c_{ij}$) und Zeiten ($t_{ij}$) bewertet; z. B. der Pfeil $(1, 2)$ mit $c_{1,2} = 42$ und $t_{1,2} = 8$.

Formulieren Sie ein Modell zur Bestimmung des Weges von Knoten $q = 1$ zum Knoten $s = 7$ mit minimalen Kosten, wobei der zeitliche Aufwand nicht mehr als 22 ZE betragen darf. Implementieren und lösen Sie Ihr Modell in Julia.

Ihre Lösung in Julia

pfeile = [(1,2,42,8), (1,3,20,9), (1,4,55,7), (2,3,41,9), (2,5,34,7),
          (3,4,40,9), (3,5,30,8), (3,6,55,7), (4,6,62,6), (5,7,46,8),
          (6,7,65,4)]

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

# IHR CODE HIER

optimize!(modell)

TippSelbstkontrolle

@assert isapprox(objective_value(modell), 140.0; atol = 1e-4) "Noch nicht korrekt, fehlt die Zeiteinhaltungsbedingung (≤ 22 ZE)?"
println("Zeitbeschränkter kürzester Weg korrekt: F* = ", objective_value(modell))