Übung 07: Transportproblem

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Gegeben sei der folgende, mit Transportkosten je Mengeneinheit bewertete Graph eines klassischen Transportproblems. Die gestrichelten Pfeile repräsentieren nicht realisierte und die anderen Pfeile realisierte Transportverbindungen.

Bestimmen Sie die reduzierten Kosten der Nichtbasisvariablen.

Aufgabe 2

Gegeben sei das folgende klassische Transportproblem mit drei Produktionsstandorten und fünf Unternehmen:

$c_{ij}$	$j = 1$	$j = 2$	$j = 3$	$j = 4$	$j = 5$	Angebot $a_i$
$i = 1$	130	140	170	150	180	40
$i = 2$	210	150	170	130	130	60
$i = 3$	140	160	210	90	170	70
Nachfrage $b_j$	30	40	50	60	30

1. Bestimmen Sie mit der Vogelschen Approximationsmethode eine Startlösung.
2. Wenden Sie anschließend die MODI-Methode an.
3. Vergleichen Sie Ihre Lösung mit der Julia-Lösung.

HinweisAngebot und Nachfrage

Das Gesamtangebot (170) deckt die Gesamtnachfrage (210) nicht. Sie benötigen einen fiktiven Anbieter mit Angebot 40 und Transportkosten 0 (vgl. Vorlesung 7).

Ihre Lösung in Julia

Nennen Sie Ihr Modell modell. Sie können den fiktiven Anbieter als vierte Zeile der Kostenmatrix ergänzen oder mit Ungleichungen arbeiten, dann entfällt er:

using JuMP, HiGHS

a = [40, 60, 70]
b = [30, 40, 50, 60, 30]
c = [130 140 170 150 180;
     210 150 170 130 130;
     140 160 210  90 170]

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), 20800.0; atol = 1e-3) "Noch nicht korrekt, liefert der fiktive Anbieter wirklich kostenlos?"
println("Transportproblem korrekt: F* = ", objective_value(modell))