Overzicht
• Inleiding
• Modellering
• Duaal probleem
• αβ-algoritme
• Maximale stroom probleem
• Voorbeeld
Transportprobleem
1
Inleiding
a1
W1
b1
W2
b2
Wn
bn
D1
a2
D2
am
Dm depots
warenhuizen
cij zijn de kosten om een produkteenheid te vervoeren van depot Di naar warenhuis Wj . P P Als i ai = j bj dan is het transportprobleem gebalanceerd.
Een niet gebalanceerd probleem kan gebalanceerd worden door een dummy depot of warenhuis toe te voegen.
Transportprobleem
2
Modellering Primaal probleem (P ) min
m P
n P
cij xij
i=1 j=1 n P o.d.v. xij = ai j=1 m P xij = bj i=1 xij ≥ 0
1≤i≤m 1≤j≤n 1 ≤ i ≤ m, 1 ≤ j ≤ n
Duaal probleem (D) max
m P
i=1
Transportprobleem
αi ai +
n P
j=1
βj bj
o.d.v. αi + βj ≤ cij αi ∈ R
1 ≤ i ≤ m, 1 ≤ j ≤ n 1≤i≤m
βj ∈ R
1≤j≤n 3
Dualiteitsstelling
Zij x een toelaatbare stroom voor P en α, β toelaatbaar voor D. Dan geldt: m P
n P
i=1 j=1
cij xij ≥
m P
n P
αi + βj xij
i=1 j=1 n m m n P P P P = αi xij + βj xij j=1 i=1 i=1 j=1 m n P P = αi ai + βj bj i=1 j=1
Volgens de dualiteitsstelling geldt: min x
n m X X
cij xij = max
m X
(α,β) i=1
i=1 j=1
αi ai +
n X
βj bj
j=1
Optimaliteit dan en slechts dan als xij > 0 Transportprobleem
⇒
αi + βj = cij 4
αβ-algoritme Start met een toelaatbare oplossing (α, β): βj = min cij i
1≤j≤n
αi = min cij − βj j
1≤i≤m
Bij deze duale oplossing zoeken we een stroom x die toelaatbaar is voor P en waarvoor geldt: αi + βj < cij
⇒
xij = 0
(1)
Als dat lukt zijn we klaar. Meestal zal dit echter niet meteen lukken. Afzwakken van P De voorwaarden in P worden afgezwakt tot: n P
j=1 m P
i=1
xij ≤ ai 1 ≤ i ≤ m (2) xij ≤ bj 1 ≤ j ≤ n
Stroom x met xij = 0 voldoet aan (1) en (2). Transportprobleem
5
Maximale stroom probleem
max
m P
n P
xij
i=1 j=1 n P o.d.v. xij ≤ ai 1 ≤ i ≤ m j=1 m P xij ≤ bj 1 ≤ j ≤ n i=1 xij ≥ 0 1 ≤ i ≤ m, 1 ≤ j ≤ n
xij = 0
αi + βj < cij
Als een stroom x ter waarde i ai = j bj gevonden wordt, dan is deze stroom een oplossing voor het transport probleem. P
P
P Als de waarde van de maximale stroom kleiner is dan i ai kunnen we de stroom x gebruiken om een betere duale oplossing (α∗, β ∗) te construeren.
Bij die oplossing wordt een nieuwe x bepaald. Etc.
Transportprobleem
6
Hulpnetwerk Zij Eαβ de verzameling takken (i, j) waarvoor geldt: αi + βj = cij . W1 a1 D1
W2
D2
b1 b2
s a2 am D m Wn
t
bn
takken in Eαβ Zij x een stroom op dit netwerk. Maak een hulpnetwerk Nx: • Als (i, j) ∈ Eαβ en xij > 0, dan voegen we tak (j, i) toe aan het netwerk. • Als xsi = ai dan verwijderen we tak (s, i). • Als xjt = bj dan verwijderen we tak (j, t). Transportprobleem
7
Ford & Fulkerson We labellen knoop s met * en vervolgens ook alle knopen die in Nx vanuit s te bereiken zijn. Als knoop t op deze wijze een label * krijgt betekent dit dat er een pad bestaat van s naar t in Nx. Dit pad bevat ´ e´ en tak (s, i) voor zekere i, ´ e´ en tak (j, t) voor zekere j en een of meer (omgekeerde) takken uit Eαβ . De gegeven stroom x kan nu vermeerderd worden door extra stroom over het gevonden pad te sturen. Deze nieuwe stroom x∗ heeft een grotere stroomwaarde dan x. Vervolgens vormen we het bij deze stroom behorende hulpnetwerk Nx∗ en onderzoeken of er een doorbraak mogelijk is, etc. Na een eindig aantal iteraties vinden we dus een stroom x waarvoor in Nx geen doorbraak mogelijk is. Deze stroom is de oplossing van het maximale stroom probleem. Transportprobleem
8
Eind situatie van het labelproces
J−
I−
s
t
xij = 0 I+
J+
• Er zijn geen takken in Nx vanuit I + naar J − (omdat de knopen in J − niet gelabeld zijn). • De takken van I − naar J + zijn stroomloos (anders zouden de knopen in I −) gelabeld zijn. • Verder zijn de takken (s, i) i ∈ I − en (j, t) j ∈ J + verzadigd. Transportprobleem
9
Constructie α∗, β ∗ Zij nu δ > 0 en definieer α∗, β ∗ volgens: α∗i =
(
αi − δ i ∈ I − αi i ∈ I+
βj∗ =
(
βj + δ j ∈ J − βj j ∈ J+
Merk op dat voor elke stroomvoerende tak (i, j) in Eαβ geldt: α∗i + βj∗ = αi + βj = cij Dus bevat Eα∗β ∗ alle takken die bijdragen aan de maximale stroom in het netwerk N behorend bij (α, β).
Transportprobleem
10
Keuze van δ (α∗, β ∗) is een duale oplossing als: α∗i + βj∗ ≤ cij
∀i, j
Merk op dat αi + βj ≤ cij ∀i, j. Voorts geldt α∗i + βj∗ > αi + βj alleen als i ∈ I + en j ∈ J −. Dus (α∗, β ∗) is een toelaatbare als: αi + βj + δ ≤ cij ∀i ∈ I +, ∀j ∈ J − De grootst mogelijke keuze voor δ is dus: δ=
min
i∈I + ,j∈J −
cij − αi − βj
Voor deze waarde van δ geldt α∗i + βj∗ = cij voor minstens ´ e´ en tak ∈ / Eαβ . Omdat Eα∗β ∗ alle takken bevat die bijdragen aan de maximale stroom in het netwerk dat bij Eαβ behoort, kunnen we uitgaande van deze stroom het betreffende maximale stroom subprobleem van Eα∗β ∗ oplossen. Transportprobleem
11
Voorbeeld Een reder heeft 20 even grote tankers, verspreid bij 3 oliedepots, als volgt: Depot # Schepen
1 8
2 7
3 5
Olie moet worden vervoerd naar 5 raffinaderijen, met de vraaag: Raffinaderij # Schepen
1 2
2 4
3 5
4 5
5 3
De volgende tabel is een schatting van de kostenmatrix voor reizen tussen de depots en de raffinaderijen: Raffinaderij 1 2 3 4 Depot
1 2 3
2 7 22
7 8 15
11 25 18
14 20 9
5 19 12 16
Probeer zo goedkoop mogelijk aan de vraag te voldoen. Transportprobleem
12
