Transport-, Routing- en Schedulingproblemen Wi4062TU / Wi487TU / a86G Uitwerkingen 28-03-2002
1
Vervangingsstrategie auto
Onderdeel a Zij V = {0, 1, 2, 3, 4, 5, 6}, waarbij knoop i staat voor het einde van jaar i. Zij de verzameling E = {(i, j) : i, j ∈ V, j > i} takken met kosten cij die het gevolg zijn van het aanschaffen van een wagen aan het einde van jaar i, en die te gebruiken tot het einde van jaar j. In tabel 1 zijn deze kosten weergegeven. Tabel 1: Kosten cij in $ i i i i i i
= = = = = =
0 1 2 3 4 5
j=1 3.300
j=2 4.800 3.300
j=3 7.600 4.800 3.300
j=4 9.800 7.600 4.800 3.300
j=5 12.400 9.800 7.600 4.800 3.300
j=6 15.600 12.400 9.800 7.600 4.800 3.300
Zij G = (V, E). De goedkoopste vervangingsstratie komt neer op het bepalen van het kortste pad van knoop 0 naar knoop 6 in de graaf G. Het kortste pad probleem luidt:
min o.d.v.
6 P 6 P
cij xij i=0 j=0 6 P x0j = 1 j=0 6 P xi6 = 1 i=0 6 6 P P xij − xji j=0 j=0
(1) = 0 i = 1, 2, 3, 4, 5
xij ∈ {0, 1}
i, j ∈ {0, 1, 2, 3, 4, 5, 6}
Hierbij zij opgemerkt dat de aanschafskosten van $ 10.000 aan het begin van jaar 1 al gemaakt zijn. Deze kosten mogen dus van de gevonden oplossing afgetrokken worden.
1
Onderdeel b We lossen dit kortste pad probleem op met behulp van Dijkstra’s algoritme. In tabel 2 zijn de verschillende iteraties weergegeven. De kosten zijn in duizenden guldens getoond. Tabel 2: Dijkstra’s algoritme Iteratie 1 2 3 4 5 6 7
Kandidaten {0} {1, 2, . . . , 6} {2, 3, . . . , 6} {3, 4, 5, 6} {4, 5, 6} {5, 6} {6}
Spilknoop 0 1 2 3 4 5 6
l(1) 3.300 3.300 3.300 3.300 3.300 3.300 3.300
l(2) 4.800 4.800 4.800 4.800 4.800 4.800 4.800
l(3) 7.600 7.600 7.600 7.600 7.600 7.600 7.600
l(4) 9.800 9.800 9.600 9.600 9.600 9.600 9.600
l(5) 12.400 12.400 12.400 12.400 12.400 12.400 12.400
l(6) 15.600 15.600 14.600 14.600 14.400 14.400 14.400
Het label van knoop 6 is als laatste aangepast in iteratie 5, uitgaande van spilknoop 4. Het label van knoop 4 is als laatste aangepast in iteratie 3, uitgaande van spilknoop 2. Het label van knoop 2 is als laatste aangepast in iteratie 1 uitgaande van spilknoop 0. Het kortste pad is dus {(0, 2), (2, 4), (4, 6)}. Door aan het einde van jaar 2 en aan het einde van jaar 4 een nieuwe auto te kopen, worden de kosten (aanschaf + operationeel - inruilwaarde) om zes jaar lang een auto te bezitten en te gebruiken geminimaliseerd. De kosten hiervoor zijn $ 14.400. Er van uitgegaan dat er aan het begin van jaar 1 net een nieuwe wagen is gekocht kan gesteld worden dat de kosten $14.400 - $ 10.000 = $ 4.400 zijn.
2
Fabriek
Onderdeel a Het totale aanbod is 3.000 + 5.000 + 5.000 = 13.000. De minimale vraag waaraan voldaan moet worden is 4.000 + 3.000 + 3.000 = 10.000. Klant 3 en 4 willen beide zoveel mogelijk van de overige 3.000 produkten afnemen. Om dit probleem te modelleren kunnen een aantal mogelijkheden gebruikt worden. Je zou klant 4 een vraag van 3.000 kunnen geven en een dummy klant (extra produkten leveren aan klant 3) kunnen toevoegen. Dan is er echter weer een tekort in aanbod en er is dus ook een dummy fabriek nodig (met aanbod 3.000), die alleen mag leveren aan klant 4 en aan de dummy klant. Een compacter model is deze. Geef klant 4 een vraag van 3.000. Gebruik de volgende winsten ei4 = max{wi3 , wi4 }. In tabel 3 zijn de te gebruiken kosten gegeven, waarbij rekening is w gehouden met het feit dat in het transportprobleem een minimalisatie wordt opgelost en het hier gaat om een winstmaximalisatie.
2
Tabel 3: Kostenmatrix Klant 1 -65 -68 -63
Fabriek 1 Fabriek 2 Fabriek 3
Klant 2 -63 -67 -60
Klant 3 -62 -65 -59
Klant 4 -64 -65 -60
Het gebalanceerde transportprobleem luidt nu: 3 P 4 P
min o.d.v.
cij xij i=1 j=1 4 P xij = ai j=1 3 P xij =bj i=1
i = 1, 2, 3
xij ≥ 0
1 ≤ i ≤ 3, 1 ≤ j ≤ 4
(2)
bj = 1, 2, 3, 4
Waarbij a = {3.000, 5.000, 5.000} en b = {4.000, 3.000, 3.000, 3.000} en cij gegeven is in tabel 3. Onderdeel b We lossen dit toewijzingsprobleem op met behulp van het αβ-algoritme. We starten met de duale oplossing volgens: 1≤j≤3
βj = min cij i
αi = min (cij − βj ) 1 ≤ i ≤ 3
(3)
j
Dus β = (−68, −67, −65, −65) en α = (1, 0, 5). In tabel 4 is een overzicht gegeven van cij − αi − βj . Tabel 4: Iteratie 1: cij − αi − βj 1 0 5
-68 2 0 0
-67 3 0 2
-65 2 0 1
-65 0 0 0
In figuur 1 is het bijbehorende netwerk Nx weergegeven, waarbij van onder naar boven takken verzadigd zijn.
3
Figuur 1: Van onder naar boven takken verzadigd Vanuit knoop s kan fabriek 3 gelabeld worden. Vanuit fabriek 3 kunnen klant 1 en klant 4 gelabeld worden. Vanuit klant 4 wordt fabriek 1 gelabeld. Hier stopt het labelproces. Er geldt: I + = {1, 3} J + = {1, 4}
(4)
De grootst mogelijke keuze voor δ is dus (zie tabel 4): δ=
min
i∈I + ,j ∈J / +
cij − αi − βj = 1
(5)
Op basis van deze keuze voor δ kan een betere duale oplossing gevonden worden volgens: (
αi − δ ( αi βj + δ βj∗ = βj
αi∗ =
i ∈ I− i ∈ I+ j ∈ J− j ∈ J+
In tabel 5 is cij − αi − βj weergegeven voor de verbeterde α en β. Tabel 5: Iteratie 2: cij − αi − βj 1 -1 5
-68 2 1 0
-66 2 0 1
4
-64 1 0 0
-65 0 1 0
(6)
In het hulpnetwerk moeten de volgende tak worden toegevoegd: (f3 , k3 ). De takken (f2 , k1 ) en (f2 , k4 ) moeten worden verwijderd. In figuur 2 is het resultaat hiervan weergegeven.
Figuur 2: Tak (f3 , k3 ) toegevoegd, takken (f2 , k1 ) en (f2 , k4 ) verwijderd Uitgaande van de reeds gevonden labels kan vanuit fabriek 3 nu klant 3 gelabeld worden. Vanuit klant 3 kan knoop t gelabeld worden. Er is een doorbraak. In figuur 3 is het resultaat hiervan weergegeven.
Figuur 3: Optimale stroom Alle takken uit knoop s zijn verzadigd, de stroom is dus optimaal. De kosten bij deze stroom (in 1000 dollar) zijn: 3 × −64 + 3 × −67 + 2 × −65 + 4 × −63 + 1 × −59 = −834
(7)
Ter controle: 3 X i=1
αi ai +
4 X
βj bj =23 − 857 = −834
(8)
j=1
Dus fabriek 1 levert 3.000 eenheden aan klant 4 ($ 64 is meer dan $ 62 van klant 3). Fabriek 2 levert 3.000 aan klant 2 en 2.000 aan klant 3. Fabriek 3 levert 1.000 eenheden aan klant 3 en 4.000 eenheden aan klant 1. De totale winst is $ 834.000.
3
Handelsreizigersprobleem
Zij 5
(
xij =
1 handelsreiziger reist vanuit stad i naar stad j 0 anders
(9)
Het handelsreizigsprobleem luidt dan als volgt: Minimaliseer de lengte (kosten van de route):
min
n X n X
cij xij
(10)
i=1 j=1
onder de voorwaarden: n X
xij = 1 1 ≤ j ≤ n
(11)
i=1
Alle steden moeten tenslotte precies 1 keer bezocht worden. Dit zijn dus n restricties. Evenzo moeten alle steden precies 1 keer verlaten worden (wederom n restricties): n X
1≤i≤n
xij = 1
(12)
j=1
Tenslotte moeten circuits voorkomen worden. Dit kan door de volgende restricties: XX
xij ≤ |S| − 1
∀S ⊆ {1, 2, . . . n}, S 6= ∅, S 6= {1, 2, . . . , n}
(13)
i∈S j∈S
Hierdoor wordt voorkomen dat in een willekeurige subset S van steden, er meer dan |S| − 1 takken zijn. Wanneer het aantal takken |S| of groter is, is er namelijk sprake van een circuit. Het aantal mogelijke deelverzamelingen (subsets) van een verzameling bestaande uit n elementen is 2n . Omdat de lege verzameling en de volledige verzameling moeten worden uitgesloten is het aantal restricties om te voorkomen dat er een circuit gevormd wordt gelijk aan 2n − 2. Het totaal aantal restricties komt daarmee op: 2n + 2n − 2
4
(14)
Knapzakprobleem
Zij a1 , a2 , . . . , aq , b een instantie van het knapzakprobleem (DKP). Definieer nu een F3 kCmax instantie als volgt. Introduceer n = q + 1 taken J1 , J2 , . . . , Jn . Iedere taak Ji bestaat dus uit drie deeltaken Ji1 , Ji2 en Ji3 . De procestijden voor taak Jij (1 ≤ i ≤ q) zijn: 6
(
pij =
0 j = 1, 3 ai j = 2
(15)
De procestijden voor taak Jn zijn:
pnj =
b
j=1 j=2
0
q P ai − b j = 3 d=
(16)
i−1
Om deze instantie van het F3 kCmax op te lossen moet een taakvolgorde gevonden worden (voor machine M1 , M2 en M3 is deze taakvolgorde gelijk), zodanig dat de totale procestijd cmax minimaal is. In figuur 4 is een mogelijk productieschema gegeven. In dit productieschema is aangenomen dat de taakvolgorde beschreven wordt door de nummering 1, 2, . . . , q, hetgeen natuurlijk vrij te kiezen is.
Figuur 4: Productieschema bij het knapzak probleem Kennelijk geldt:
cmax =
q X
ai + δ
(17)
i=1
Hierin is δ ≥ 0. Er geldt δ = 0 dan en slechts dan als het DKP probleem een ja-instantie P is (d.w.z. i∈B ai = b, voor zekere B). De deelverzameling B is eenvoudig af te lezen uit het gevonden productieschema (het zijn de indices die precies onder de procestijd b vallen op machine M1 .
7
