Transport-, Routing- en Schedulingproblemen Wi4062TU / Wi487TU / a86G Uitwerkingen 08-04-2005
1
Transportprobleem
Onderdeel a Fabriek 1 kan 120 ton staal fabriceren in 40 uur. Voor fabriek 2 is dit 150 ton staal en voor fabriek 3 160 ton staal. Het totale aanbod komt daarmee op: 120 + 150 + 160 = 430. De totale vraag naar staal is 300 ton. Om het transportprobleem te balanceren voeren we daarom een dummy vraagknoop in. De vraag bij deze dummy knoop is 130 ton. De kosten van iedere fabriek naar deze vraagknoop is gelijk aan 0. min o.d.v.
3 P 4 P
cij xij i=1 j=1 4 P xij = ai j=1 3 P xij = bj i=1
xij ≥ 0
1≤i≤3 1≤j≤4 1≤i≤3 1≤j≤4
Waarbij a = (120, 150, 160) en b = (100, 100, 100, 130). De bijbehorende kostenmatrix cij is: S1 60 50 43
F1 F2 F3
S2 40 30 20
S3 28 30 20
S3 0 0 0
Onderdeel b We lossen het transport probleem 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 j
Dus β = (43, 20, 20, 0) en α = (0, 0, 0). In tabel 1 is een overzicht gegeven van cij − αi − βj .
1
Tabel 1: Iteratie 1: cij − αi − βj 43 17 7 0
0 0 0
20 20 10 0
20 8 10 0
0 0 0 0 100
S1 [0,100]
[0,120]
F1
120 60
s
[0,150]
F2
S2 [0,100] [0,100]
10
t
S3 [0,160]
F3 [0,130] S4
Figuur 1: Van boven naar beneden takken verzadigd In figuur 1 is het bijbehorende netwerk Nx weergegeven, waarbij van boven naar onder takken verzadigd zijn. Het labelproces wordt gestart vanuit s. Nu kan alleen knoop F 2 gelabeld worden (naar F 1 en naar F 3 zijn geknipt, omdat de capaciteit verbruikt is!). Vanuit knoop F 2 kan knoop S4 gelabeld worden. Via de omgekeerde rode tak kan dan F 1 gelabeld worden. Hier stopt het labelproces. Er geldt: I + = {1, 2} J + = {4} De grootst mogelijke keuze voor δ is dus (zie tabel 1): δ=
min
i∈I + ,j ∈J / +
cij − αi − βj = 7
(1)
Op basis van deze keuze voor deze keuze van δ kan een betere duale oplossing gevonden worden volgens: αi∗ βj∗
=
(
αi − δ i ∈ I − αi i ∈ I+
=
(
βj + δ j ∈ J − βj j ∈ J+ 2
In tabel 2 is cij − αi − βj weergegeven voor de verbeterde α en β. Tabel 2: Iteratie 2: cij − αi − βj 50 10 0 0
0 0 -7
27 13 3 0
27 1 3 0
0 0 0 7
Het bijbehorende netwerk Nx is weergegeven in figuur 2. Ten opzichte van figuur 1 is de tak van F 2 naar S1 naar er bij gekomen, terwijl de tak van F 3 naar S4 verwijderd is (N.B.: dit was dus geen stroomdragende tak!). S1 [0,100] [0,120]
F1
100
120
60 s
[0,150]
F2
S2 [0,100] [0,100]
10
t
S3 [0,160]
F3 [0,130] S4
Figuur 2: Tweede iteratie Het labelproces zetten we nu voort vanuit F 2. Vanuit F 2 kan nu ook S1 gelabeld worden. Vanuit S1 kan F 3 gelabeld worden. Vanuit F 3 kan zowel S2 als S3 gelabeld worden. Vanuit zowel S2 als S3 kan knoop t gelabeld worden. Er zijn dus twee mogelijke doorbraken: s → F 2 → S1 → F 3 → S2 → t en s → F 2 → S1 → F 3 → S3 → t. Over het eerste pad kan maximaal 40 extra stroom verstuurd worden (dan is de capaciteit bij S2 verbruikt. Over het tweede pad kan vervolgens maximaal 60 extra stroom verstuurd worden (dan is de capaciteit bij S1 verbruikt). In figuur 3 is de resulterende stroom getekend. Het labelproces wordt opnieuw gestart. Vanuit knoop s kan alleen knoop F 2 gelabeld worden. Vanuit knoop F 2 kunnen de knopen S1 en S4 gelabeld worden. Vanuit knoop S4 kan knoop F 1 gelabeld worden. Hier stopt het labelproces. Er geldt: I + = {1, 3} J + = {1, 4} De grootst mogelijke keuze voor δ is dus (zie tabel 3): δ=
min
i∈I + ,j ∈J / +
cij − αi − βj = 1 3
100
S1 [0,100]
[0,120]
F1
120 100
s
[0,150]
F2
[0,100] [0,100]
10 60
[0,160]
S2 t
S3
F3 [0,130] S4
Figuur 3: Iteratie 2, na de doorbraken In tabel 3 zijn de nieuwe duale variabelen gegeven op basis van deze keuze voor δ. Tabel 3: Iteratie 2: cij − αi − βj 0 0 -8
50 10 0 1
28 12 2 0
28 0 2 0
0 0 0 8
Het bijbehorende netwerk Nx is weergegeven in figuur 4. Ten opzichte van figuur 3 is de tak van F 1 naar S3 erbij gekomen, terwijl de tak van F 3 naar S1 verwijderd is. 100
S1 [0,100]
[0,120]
F1 120
s
[0,150]
F2
100
[0,100] [0,100]
10 60
[0,160]
S2 t
S3
F3 [0,130] S4
Figuur 4: Iteratie 3 Het labelproces kan worden voortgezet. Vanuit knoop F 1 kan knoop S3 gelabeld worden. Vanuit knoop S3 kan knoop t gelabeld worden. Er is sprake van een doorbraak via het pad: s → F 2 → S4 → F 1 → S3 → t. Over dit pad kan 40 extra stroom verstuurd worden. Het labelproces kan dan worden voortgezet. Vanuit knoop C kan knoop F gelabeld worden en vanuit knoop F kan t gelabeld worden. Er is een doorbraak: s → D → E → C → F → t. 4
100
S1 [0,100]
[0,120]
F1
40 80
s
[0,150]
F2
100
S2 [0,100] [0,100]
50
t
S3 60 [0,160]
F3 [0,130] S4
Figuur 5: Optimale stroom Over dit pad kan 4 extra stroom verstuurd worden. In figuur 6 is de resulterende stroom getoond. Alle takken vanuit s zijn nu verzadigd dus is het transport probleem opgelost. A
9
[0,9]
E [0,6] s
[0,15]
6 B
[0,7]
F
3 C
[0,13]
t
4 6
[0,9]
G
[0,3]
3
D
Figuur 6: Oplossing van het transportprobleem Fabriek 1 produceert 40 ton staal van type 3. Fabriek 2 produceert 100 ton staal van type 1. Fabriek 3 produceert 100 ton staal van type 2 en 60 ton staal van type 3. De bijbehorende kosten zijn: 40 × 28 + 100 × 50 + 100 × 20 + 60 × 20 = 9.320 Ter controle wordt hier ook de waarde van de doelfunctie van het duale probleem gegeven: 3 X i=1
αi ai +
4 X
βj bj = −1.280 + 10.600 = 9.320
j=1
5
2
Bekabeling van hoofdkantoor en bijkantoren
Onderdeel a Dit probleem komt neer op het vinden van een minimale opspannende boom. We doen dit met behulp van het algoritme van Kruskal. We sorteren de takken (niet de diagonaal) op oplopende kosten: (B1, B5) (H, B4) (B1, B3) (B4, B5) (H, B3) (B2, B4) (B3, B4) (H, B1) (B2, B3) (H, B5) (B2, B5) (B1, B4) (B4, B5) (H, B2) (B1, B2)
50 70 80 100 115 120 140 160 175 190 215 220 240 270 310
Zij B = ∅ We selecteren de takken uit de gesorteerde lijst, waarbij we takken die een circuit vormen met eerder gevonden takken verwerpen, totdat we n − 1 = 5 takken gekozen hebben. De eerste vier takken worden gekozen: B = {(B1, B5), (H, B4), (B1, B3), (B4, B5)}. Tak (H, B3) vormt een circuit: H → B3 → B1 → B5 → B4 → H en wordt dus verworpen. De volgende tak (B2, B4) kan echter worden toegevoegd. De minimale opspannende boom is dus: B = {(B1, B5), (H, B4), (B1, B3), (B4, B5), (B2, B4)}. Er loopt dus een kabel van het hoofdkantoor H naar bijkantoor B4. Vanuit B4 loopt een kabel naar B2, B5. Vanuit B5 loopt een kabel naar B1 en vanuit B1 loopt een kabel naar B3. De kosten zijn: 50 + 70 + 80 + 100 + 120 = 420. Onderdeel b Dit probleem komt neer op het oplossen van het handelsreizigersprobleem op de volgende afstandsmatrix.
6
0 1 2 3 4 5
0 ∞ 0 0 0 0 0
1 160 ∞ 310 80 220 50
2 270 310 ∞ 175 120 215
3 115 80 175 ∞ 140 240
4 70 220 120 140 ∞ 100
5 190 50 215 240 100 ∞
We reduceren de kolommen met 0, 50, 120, 80, 70, 50. De ondergrens is dan: 370.
0 1 2 3 4 5
0 ∞ 0 0 0 0 0
1 110 ∞ 260 30 170 0
2 150 190 ∞ 55 0 95
3 35 0 95 ∞ 60 160
4 0 150 50 70 ∞ 30
5 140 0 165 190 50 ∞
Met behulp van (2) bepalen we de mogelijke reducties bij ieder 0-element. pij = min cih + min chj h6=j
(2)
h6=i
Hieruit volgt: p04 = 65, p10 = 0, p13 = 35, p15 = 50, p20 = 50, p30 = 30, p40 = 0, p42 = 55, p50 = 0, p51 = 30. We vertakken dus op p04 . TS-routes zonder (0, 4) hebben dan als ondergrens 370 + 65 = 435. Voor TS-routes met (0, 4) geldt:
1 2 3 4 5
0 0 0 0 ∞ 0
1 ∞ 260 30 170 0
2 190 ∞ 55 0 95
3 0 95 ∞ 60 160
5 0 165 190 50 ∞
Let op dat (4, 0) nu kosten ∞ heeft. Nu volgt: p10 = 0, p13 = 60, p15 = 50, p20 = 95, p30 = 30, p42 = 105, p50 = 0, p51 = 30. We vertakken dus op (4, 2). TS-routes met (0, 4) maar zonder (4, 2) kosten dus minimaal 370 + 105 = 475. Voor TS-routes met (0, 4) en (4, 2) geldt:
7
1 2 3 5
0 0 ∞ 0 0
1 ∞ 260 30 0
3 0 95 ∞ 160
5 0 165 190 ∞
Om het circuit 0 → 4 → 2 → 0 te voorkomen heeft tak (2, 0) nu kosten ∞. We kunnen rij 2 reduceren met 95, waarmee de ondergrens van deze TS-routes gelijk is aan 370 + 95 = 465:
1 2 3 5
0 0 ∞ 0 0
1 ∞ 165 30 0
3 0 0 ∞ 160
5 0 70 190 ∞
Er volgt: p10 = p13 = p50 = 0, p15 = p23 = 70 en p30 = p51 = 30. We vertakken op (1, 5). TS-routes met (0, 4) en (4, 2), maar zonder (1, 5) kosten dus minimaal 465 + 70 = 535. Voor TS-routes met (0, 4), (4, 2) en (1, 5) geldt:
2 3 5
0 ∞ 0 0
1 165 30 ∞
3 0 ∞ 160
Let op tak (5, 1) heeft nu kosten ∞. We kunnen kolom 1 reduceren met 30, waarmee de ondergrens van deze routes gelijk is aan 465 + 30 = 495:
8
0 ∞ 0 0
2 3 5
1 135 0 ∞
3 0 ∞ 160
Er is nu een route af te maken op de nul-elementen: 0 → 4 → 2 → 3 → 1 → 5 → 0. Deze route kost dus 495. Nu moeten de volgende ‘bladen’ in de branch & bound boom nog worden uitgewerkt: • De situatie zonder (0, 4) met ondergrens 435 • De situatie met (0, 4), zonder (4, 2) met ondergrens 475 De situatie zonder (0, 4) In dit geval is de gereduceerde matrix gelijk aan:
0 1 2 3 4 5
0 ∞ 0 0 0 0 0
1 75 ∞ 260 30 170 0
2 115 190 ∞ 55 0 95
3 0 0 95 ∞ 60 160
4 ∞ 120 20 40 ∞ 0
5 105 0 165 190 50 ∞
Er volgt: p03 = 75, p10 = p13 = p40 = p50 = 0, p15 = 50, p20 = p54 = 20, p30 = p51 = 30, p42 = 55. We vertakken op (0, 3). Routes zonder (0, 4) en (0, 3) kosten minstens 435 + 75 = 510 en hoeven dus niet verder onderzocht te worden. Voor routes zonder (0, 4) maar met (0, 3) geldt:
1 2 3 4 5
0 0 0 ∞ 0 0
1 ∞ 260 30 170 0
2 190 ∞ 55 0 95
4 120 20 40 ∞ 0
5 0 165 190 50 ∞
Omdat (3, 0) nu ∞ kost, kan rij 3 gereduceerd worden met 30. De ondergrens komt nu dus op 465.
9
1 2 3 4 5
0 0 0 ∞ 0 0
1 ∞ 260 0 170 0
2 190 ∞ 25 0 95
4 120 20 10 ∞ 0
5 0 165 160 50 ∞
Er is een route te vinden over uitsluitend nul elementen: 0 → 3 → 1 → 5 → 4 → 2 → 0. Deze route kost 465 en is dus goedkoper dan de eerder gevonden route! De situatie met (0, 4), zonder (4, 2) met ondergrens 475 Deze situatie hoeft nu niet meer te worden uitgewerkt omdat er een goedkopere route gevonden is. Conclusie Er loopt een lijn vanuit het hoofdkantoor naar achtereenvolgens bijkantoor 3, 1, 5, 4 en 2. De lengte van deze lijn is 465. Onderdeel c Een Hamilton pad is een restrictie op een minimale opspannende boom. Een Hamilton pad is immers een opspannende boom waarbij elke knoop graad kleiner dan of gelijk aan 2 heeft.
3
Produktieplanning
Zonder verlies van algemeenheid mogen we aannemen dat het GANTT diagram de volgende vorm heeft:
De deeltaken op M1 zijn zover mogelijk naar links geschoven, zodat ze aansluitend uitgevoerd kunnen worden en de deeltaken op M2 zijn zover mogelijk naar rechts geschoven, zodat ook deze deeltaken aansluitend uitgevoerd kunnen worden. Voor wat betreft de taken Ji en Jj hebben we de volgende situatie: aj
ai
j
i
xj
j
i
bj
bi
Hierin stelt xj de tijd voor die verloopt na het be¨eindigen van deeltaak Jj1 op machine M1 voordat deeltaak Jj2 op machine M2 gestart wordt. Het is duidelijk dat: 10
ai ≤ bj + xj
(3)
Immers: bj + xj = ai + xi en xi ≥ 0. Bezien we nu wat er gebeurt als we de volgorde van i en j wisselen: ai
aj
i
j i
aj + xj
j
bi
De totale procestijd van het nieuwe schema is nog steeds dezelfde cmax . Als dit nieuwe schema toelaatbaar is, dan is het minstens zo goed als het originele schema. Het nieuwe schema is toelaatbaar dan en slechts dan als zowel voor Jj en Ji de deeltaak op machine M2 pas wordt gestart als de deeltaak op M1 uitgevoerd is. Dus x′i ≥ 0 en x′j ≥ 0. Dit is het geval indien: ( ai ≤ aj + xj (4) ai + aj ≤ aj + xj + bi Uit i ≺ j volgt: min(ai , bj ) ≤ min(aj , bi ). Als min(ai , bj ) = ai dan is zeker voldaan aan (4). Als min(ai , bj ) = bj dan volgt bj ≤ aj en bj ≤ bi . Samen met (3) levert dit: ai ≤ bj + xj ≤ aj + xj en ai ≤ bj + xj ≤ xj + bi Waarmee ook voldaan wordt aan (4). Het nieuwe produktieschema is dus toelaatbaar!
4
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 4 zijn deze kosten weergegeven. 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.
11
Tabel 4: 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
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
= 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. Onderdeel b We lossen dit kortste pad probleem op met behulp van Dijkstra’s algoritme. In tabel 5 zijn de verschillende iteraties weergegeven. De kosten zijn in duizenden dollars getoond. Tabel 5: 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)}. 12
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.
13
