Wiskunde in wetenschap: Optimaliseren in netwerken

Wiskunde in wetenschap: Optimaliseren in netwerken

Wiskunde D doen in Delft In deze map treft u (gedeeltes) van enkele lesmodules aan met als onderwerp Optimaliseren in netwerken. Ook zijn er twee paragrafen van het Engelstalige leerboek “Introduction to Operations Research” van Hillier en Lieberman te vinden. Heeft u belangstelling voor het complete materiaal en overweegt u om het in uw klas te gaan gebruiken, dan kunt u via [email protected] contact met ons opnemen. U krijgt dan toegang tot de elektronische leeromgeving blackboard van de TU Delft en daarmee de beschikking over al het materiaal. Bovendien wordt u op de hoogte gehouden van nieuwe ontwikkelingen en van de mogelijkheden voor uw leerlingen om Delft te bezoeken in het kader van wiskunde D. Een bezoek van een van de kerngroepleden aan uw school om een en ander toe te lichten en ervaringen uit te wisselen behoort ook tot de mogelijkheden Regionale steunpunt wiskunde D Sinds de oprichting van het Regionale Steunpunt Wiskunde D in september 2006 heeft de Technische Universiteit Delft zich gericht op twee activiteiten op het gebied van wiskunde D vwo: het scholen van docenten voor alle domeinen en het ontwerpen van onderwijs voor het domein Wiskunde in wetenschap van dit nieuwe schoolvak. De scholing wordt in samenwerking met de Technische Universiteit Eindhoven, de Universiteit Twente en de Radboud Universiteit Nijmegen verzorgd onder de naam (Dieper) in zee met wiskunde D. Ook het werk voor Wiskunde in wetenschap is bij deze vier universiteiten op dezelfde manier aangepakt: door een 'kerngroep' van vwo-docenten, aangevuld met universitaire medewerkers, worden lesmateriaal en docentenhandleidingen gemaakt, in de klas uitgeprobeerd en bijgesteld. Door de kerngroepen in Eindhoven en Twente wordt gewerkt aan lesmateriaal met als onderwerpen (onder andere) Cryptografie respectievelijk Modelleren. De kerngroep in Nijmegen houdt zich bezig met het onderwerp Astrofysica. In Delft is gekozen voor het onderwerp Optimaliseren in netwerken.

Keuze van het onderwerp Dat we in Delft hebben gekozen voor Optimaliseren in netwerken heeft een aantal redenen. Dit onderwerp kan eenvoudig geïntroduceerd worden bij leerlingen in 4 vwo omdat geen wiskundige voorkennis van de bovenbouw nodig is en het kent voldoende mogelijkheden voor verdieping om ook voor 5 en 6 vwo interessant te zijn. Optimaliseren in netwerken bevat een aantal onderdelen die onafhankelijk van elkaar behandeld kunnen worden. Het gebied is rijk aan toepassingen en ook zeker doorstroomrelevant - het maakt deel uit van diverse opleidingen (zoals werktuigbouwkunde en technische wiskunde) in Delft - en het biedt de leerling een aardig inkijkje in wat wiskunde in het hoger onderwijs zou kunnen inhouden. Bovendien weet de Delftse kerngroep zich gesteund door de onderzoeksgroep Optimaliseren van de faculteit Elektrotechniek, Wiskunde en Informatica. Inhoud van de modules Als uitgangspunt diende een drietal teksten: het boek uit de Epsilonreeks “Operationele Analyse” van Henk Tijms, het Delftse collegedictaat “Optimaliseren in netwerken” van Kees Roos en het Amerikaanse studieboek “Introduction to Operations Research” van Hillier en Lieberman. Op advies van vakdeskundigen van de TU heeft de kerngroep een aantal optimaliseringsproblemen uitgekozen die elk met een eigen, specifiek op het betreffende probleem toegesneden methode opgelost kunnen worden. Lineair programmeren als aanpak voor een grotere klasse van optimaliseringsproblemen wordt bewaard voor een practicum voor vwoleerlingen aan de TU, waarop we hieronder terugkomen. Door in de modules de aandacht op de specifieke methoden te richten, kan een een breed scala aan algoritmen de revue passeren. Op deze manier wordt zowel de beoogde onderlinge onafhankelijkheid van de modules als de gewenste variatie in moeilijkheid bereikt. Gebruik van wiskundeboeken voor gevorderden Omdat de teksten van Tijms, Roos en Hillier en Lieberman niet zomaar geschikt zijn voor gebruik op school, zijn er leerlingenteksten geschreven op vwo-niveau, inclusief opgavenseries met antwoorden en toetsvragen. Het is echter nadrukkelijk de bedoeling om leerlingen de gelegenheid te geven ook de oorspronkelijke hoofdstukken uit Tijms en Hillier en Lieberman te bestuderen, als u dit in uw klas haalbaar acht. Bij sommige modules is daarom een handreiking geschreven om leerlingen hierbij te helpen. Aan de hand van ‘wiskundige tekstverklaringsvragen’ wordt de leerling door de tekst geleid. Voorbeelden van dergelijke vragen zijn: “Waarom worden de capaciteiten van de extra takken zo gekozen?”, “Verzin een voorbeeld bij deze alinea”, “Controleer met een figuur of de gegeven oplossing klopt.” Op die manier raakt hij al enigszins vertrouwd met het lezen en bestuderen van Nederlandse en Engelstalige wiskundeboeken voor gevorderden. U zou als docent er dan voor kunnen kiezen de leerlingen daarnaast leerlingenteksten niet of slechts gedeeltelijk te laten gebruiken.

De grafische rekenmachine Ten slotte richtten we ons op het schrijven van programmatuur voor de grafische rekenmachine. Diverse algoritmen voor het oplossen van optimaliseringsproblemen lenen zich daarvoor. Ook hier is het weer aan de docent om de programmaatjes al dan niet ter beschikking te stellen. De leerlingen kunnen ook uitgedaagd worden zelf zo’n programma te schrijven. Voor lessen en praktische opdrachten Wanneer u uw belangstelling kenbaar maakt, dan krijgt u de beschikking over al het materiaal. U kunt deze map verder vullen en gebruiken voor uw lessen wiskund D. De map is ook geschikt als achtergrondmateriaal voor leerlingen die een praktische opdracht over (een onderdeel van) Optimaliseren in netwerken maken. Hierdoor wordt bijgedragen aan realisering van de gedachte achter de huidige vernieuwingen van de tweede fase van havo en vwo om aan de school en aan de docent meer ruimte te laten en keuzes te bieden. De vijf modules Naast een korte 0. Inleidende module zijn er modules geschreven over 1. Minimale opspannende bomen 2. Kortste-pad-problemen 3. Maximale stromen 4. Steinerpunten 5. Minimale-kosten-maximale-stroom-problemen. Welke keuze u uit de vijf modules ook maakt, er zal altijd wel met de inleidende module 0 begonnen moeten worden. De module Minimale opspannende bomen is een goed vervolg, omdat deze van de overige modules het eenvoudigst is. Daarna zijn verschillende volgordes mogelijk. Afhankelijk van de keuzes die de docent maakt om materialen wel of niet in te zetten, is de verwachting dat met elke module ongeveer 4 tot 6 lessen gemoeid zijn. Leerlingen naar Delft De mogelijkheid bestaat ook om uw leerlingen een practicum te laten volgen aan de TU Delft. Het geleerde kan dan toegepast en uitgebreid worden, bijvoorbeeld door te werken met Excel-spreadsheets en te leren omgaan met Excel-add-ins die gebaseerd zijn op lineair programmeren. Een uitgebreidere opdracht wordt in een dag of dagdeel gemaakt en eventueel voltooid als huiswerk. In de toekomst wil de kerngroep ook vertrouwde Delftse activiteiten als “Wiskunde in actie” en het Scholierenlab gaan betrekken bij Wiskunde in wetenschap.

Kerngroep wiskunde D Delft Liesbeth Bos Wim Caspers Wim van Dijk Jan Moen Rob van Oord Sanne Schaap Jan Schrik Jeroen Spandaw Agnes Verweij website: contact:

Scala College Alphen aan den Rijn TU Delft / Adelbert College Wassenaar Montessori Lyceum Rotterdam Int. College Edith Stein Den Haag Coenecoop College Waddinxveen Marecollege Leiden Christelijk Lyceum Delft TU Delft TU Delft

www.wiskundedsteun.nl [email protected]

Inleiding optimaliseren in netwerken

Module 0 Inleiding optimaliseren in netwerken

Dit studiemateriaal is ontwikkeld door de kerngroep wiskunde D Delft en mag gratis gebruikt worden in het wiskundeonderwijs in het vo. Kerngroep wiskunde D Delft Liesbeth Bos Wim Caspers Wim van Dijk David Lans Jan Moen Rob van Oord Sanne Schaap Jan Schrik Jeroen Spandaw Agnes Verweij website: contact:

Scala College TU Delft / Adelbert College Montessori Lyceum Rotterdam Emmaus College Int. College Edith Stein Coenecoop College Marecollege Christelijk Lyceum Delft TU Delft TU Delft

module 0


Alle rechten voorbehouden. Niets uit deze uitgave mag worden verveelvoudigd, opgeslagen in een geautomatiseerd gegevensbestand, of openbaar gemaakt, in enige vorm of op enige wijze, hetzij elektronisch, mechanisch, door fotokopieën, opnamen, of op enige andere manier, zonder voorafgaande schriftelijke toestemming van de kerngroep.

Kerngroep Delft

Wiskunde D: Wiskunde in wetenschap

-2-


Module 0

Inleiding optimaliseren in netwerken

Theorie

-

Opdrachten

p. 5

Antwoorden

p. 6

Bestuderen van wetenschappelijk materiaal

p. 7

Woordenlijst

p. 8

Literatuur

Introduction to Operations Research, Hillier / Lieberman

Kerngroep Delft

paragraaf 9.1 en 9.2


-3-


Geachte docent, Ter inleiding op een of meer onderwerpen van Optimaliseren in netwerken kunt u op diverse wijzen gebruik maken van voorgenoemd materiaal. U kunt de opdrachten voorleggen aan de leerlingen en de antwoorden voor uzelf houden. U kunt er ook voor kiezen de antwoorden aan de leerlingen uit te delen. Om leerlingen van het begin af aan vertrouwd te maken met Engelstalig studiemateriaal op dit gebied kunt u ze ook direct de genoemde paragrafen uit Introduction to Operations Research (Hillier / Lieberman) voorleggen. Dit boek wordt aan universiteiten gebruikt. Wellicht kan de woordenlijst het lezen van dit universitair studiemateriaal bij volgende onderwerpen van Optimaliseren in netwerken vergemakkelijken.

Kerngroep Delft


-4-


Module 0 Inleiding Optimaliseren in netwerken 1

Huisje

Je hebt vast het huisje in figuur 1 wel eens gezien en daarbij de opdracht gekregen: “teken alle lijnen één keer zonder je pen van het papier te halen”. Wellicht is het je opgevallen, dat als je in een van de hoekpunten onderaan begint, het meestal (altijd?) wel lukt, maar als je ergens anders start dan lukt het zeker niet. ¾ Probeer uit te vinden hoe dit komt. 2

Figuur 1: elk huisje draagt zijn kruisje

Koningsberger bruggen

Een klassiek probleem is dat van de bruggen van Koningsbergen. Deze stad was gebouwd op twee eilanden in de rivier, waarbij bruggen de eilanden onderling en met de oever verbonden op de manier zoals in figuur 2. De vraag was of het mogelijk is in een wandeling precies één keer over alle bruggen te gaan. ¾ Leg uit waarom dit wel/niet kan. Aanwijzing: maak eerst een schema met de verbindingen tussen de twee eilanden en de beide oevers. Het antwoord op die vraag kun je vinden door op eenzelfde manier te redeneren als bij het huisje. 3

Figuur 2: Koningsberger bruggen

Veel deuren

In het derde probleem is er een huis met vijf kamers. Alle kamers die naast elkaar liggen, zijn verbonden door een deur; bovendien is er van elk van de kamers een deur naar de tuin. ¾ Hier is de vraag of het mogelijk is een rondgang te maken waarbij elke deur één keer gepasseerd wordt.

TIP: probeer een schematische tekening van de situatie te maken!

Kerngroep Delft

Figuur 3: veel deuren


-5-


Antwoorden 1

Huisje

Let op het aantal lijnstukken dat aan een punt grenst. Als bij het tekenen van het huisje een punt gepasseerd wordt, tekent men daarbij 2 lijnstukken (inkomend en vertrekkend). Bij elke passage is dit het geval; dus is bij bijna elk punt bij een rondgang het aantal inkomende en uitgaande lijnen een even aantal. De enige uitzonderingen kunnen het startpunt en het eindpunt zijn; als deze niet samenvallen, is dit een oneven aantal. Het aantal inkomende en uitgaande lijnen bij een punt wordt de graad van een punt noemen. Er is dus alleen een rondgang mogelijk als er twee punten of geen punten met een oneven graad zijn.

2

Figuur 4

Koningsberger bruggen

Als we de eilanden presenteren als een stip en de bruggen als een verbinding hiertussen, krijgen we figuur 5. Hier is de graad van alle vier de punten oneven, een rondgang is dus niet mogelijk. Dit hebben we vastgesteld in opgave 1. Figuur 5

3

Veel deuren

In een schematische voorstelling van de situatie tekenen we niet alleen punten voor de kamers A, B, C, D en E, maar ook één voor de tuin F. De verbindingen zijn de deuren. De graad van D en E is even, maar van de andere vier punten is hij oneven: er is géén rondgang mogelijk. Dit hebben we vastgesteld in opgave 1.

Figuur 6

Kerngroep Delft


-6-


Bestuderen van wetenschappelijk materiaal In bovenstaande problemen was het steeds handig een schematische voorstelling van de situatie te maken. Zo’n schematische voorstelling noemen we een graaf. De verbindingen heten takken of kanten (in het Engels: edges); de punten die door de takken verbonden worden, heten knooppunten of kortweg knopen (in het Engels: vertices, enkelvoud: vertex). In de voorbeelden hadden de takken geen gewicht, deed het er niet toe hoe “duur” het doorlopen van een tak was. Bij veel praktische problemen doet het er wél toe hoe de takken gewogen worden. Denk bijvoorbeeld aan een routeplanner voor een auto. Daar is het van belang dat de route zo kort mogelijk is (km), zo snel mogelijk (uur) of zo goedkoop mogelijk (euro). Soms kan men zijn prioriteit instellen: verschillende instellingen geven dan mogelijk verschillende oplossingen. In het onderdeel optimaliseren is één van de problemen hoe zo’n route gepland wordt en hoe zo’n berekening efficiënt aangepakt kan worden. Het gaat dan steeds om het vinden van een optimale oplossing. De routeplanner lost het zogenaamde kortste pad probleem op. Hierbij kan kort afstand betekenen, maar in een andere context ook tijd, of geld. In de inleiding en §9.1 uit Hillier en Lieberman worden behalve het kortste pad probleem ook het probleem van de minimaal opspannende boom en dat van de maximale stroom met minimale kosten beschreven. Dit zijn ook voorbeelden van optimaliseringsproblemen.

1

Lees §9.1 en denk daarbij aan de verschillende betekenissen die knopen, verbindingen en stromen kunnen hebben. Kun je zelf het lijstje met voorbeelden uitbreiden? knopen kruispunten luchthavens schakelpunten pompstations …

takken wegen luchtwegen draden leidingen/buizen …

stroom voertuigen vliegtuigen boodschappen vloeistoffen …

In §9.2 van Hillier en Lieberman kom je beschrijvingen van begrippen tegen die bij netwerkproblemen worden gebruikt. 2

Lees §9.2. Zoek bij een (vetgedrukt) Engels begrip steeds de Nederlandse vertaling en omschrijf het vervolgens in het Nederlands. Voor de vertalingen van de vetgedrukte woorden kun je gebruik maken van de volgende (alfabetische) lijst. Je mag ook woorden combineren. boom bron capaciteit cykel (kring) gericht

Kerngroep Delft

knoop netwerk ongericht opgespannen pad

pijl put tussenstation verbinding verbonden


-7-


Woordenlijst Engels-Nederlands

Kerngroep Delft

ENGELS

NEDERLANDS

adjacent arc arc progression bounded chain conformal flows connected graph cut directed distance edge feasible flow graph intermediate .. link path reach saturated set sink source spanning tree tree undirected value of the flow vertex vertices

aangrenzend pijl/verbinding pijlenreeks begrensd keten gelijkgerichte stromen samenhangende graaf snede gericht afstand tak toelaatbaar stroom graaf tussenverbinding pad bereik verzadigd verzameling put bron voortbrengende boom boom niet-gericht waarde van de stroom knooppunt knooppunten


-8-

Minimaal opspannende bomen

Module 1 Minimaal opspannende bomen



module 1


Alle rechten voorbehouden. Niets uit deze uitgave mag worden verveelvoudigd, opgeslagen in een geautomatiseerd gegevensbestand, of openbaar gemaakt, in enige vorm of op enige wijze, hetzij elektronisch, mechanisch, door fotokopieën, opnamen, of op enige andere manier, zonder voorafgaande schriftelijke toestemming van de kerngroep.

Kerngroep Delft


-2-


Module 1 Theorie

Minimaal opspannende boom p. 5-11

Opgaven Antwoorden

Neem voor de rest van Module 1 contact op

Bestuderen van wetenschappelijke literatuur

met de kerngroep via [email protected]

Programmeren Toetsopgaven Extra opgaven Antwoorden extra opgaven Literatuur

Kerngroep Delft

Introduction to Operations Research, Hillier / Lieberman

paragraaf 9.1 en 9.2


-3-


Geachte docent, Om uw leerlingen zich het onderwerp Minimaal opspannende bomen eigen te laten maken kunt u op diverse wijzen gebruik maken van het materiaal in deze module. U kunt de moduletekst voorleggen aan de leerlingen en de genoemde literatuur gebruiken voor uzelf, als achtergrondinformatie. U kunt het materiaal gebruiken om een eigen vorm te geven aan uw lessen. U gebruikt de diverse onderdelen om uw eigen verhaal over het onderwerp voor te bereiden. De opdrachten uit de module gebruikt u dan bijvoorbeeld als oefenmateriaal. De leerlingen kunnen zich verdiepen in het onderwerp door middel van eigen onderzoek. U heeft dan materiaal en literatuur beschikbaar als achtergrondinformatie. Om leerlingen vertrouwd te maken met wetenschappelijk studiemateriaal kunt u ze ook direct de genoemde paragraaf uit Introductions to Operations Research (Hillier / Lieberman) voorleggen. Voor de Engelstalige literatuur kan de woordenlijst van module 0 en de oefening met het lezen van universitair studiemateriaal van dienst zijn. Bij dit onderwerp kan de grafische rekenmachine ook een rol spelen. Ook voor dat materiaal geldt dat u het de leerlingen direct kunt verstrekken of maar u kunt het ze ook zelf proberen te laten schrijven. Ook toetsopgaven maken deel uit van het volledige materiaal. Neem contact op met de kerngroep via wiskunded@tudelft.

Kerngroep Delft


-4-


Module 1 Minimaal opspannende bomen Een aantal boorplatforms moet onderling en met de kust A worden verbonden via een zo goedkoop mogelijk pijpleidingennet. De kosten (in kosteneenheden) van elke mogelijke pijpleiding zijn bekend, zoals weergegeven in figuur 1.

Figuur 1: kosten van mogelijke pijpleidingen

We gaan nu bekijken hoe hoog de kosten zijn van verschillende leidingennetten. Deze gaan we optimaliseren, zodat er netten ontstaan die met een minimaal aantal leidingen, de boorplatforms onderling en met de kust verbinden. Bovendien moeten de kosten van die leidingen ook minimaal zijn.

In dit geval is het minimale aantal leidingen 6 (bedenk zelf waarom!). In de figuren 2 en 3 zijn twee mogelijke leidingennetten getekend met dat minimaal aantal verbindingen, waarbij alle platforms onderling en met de kust verbonden zijn.

Figuur 2

Figuur 3

De kosten bedragen respectievelijk 41 en 32 kosteneenheden. De vraag is of er misschien een toegestaan leidingennet bestaat met nog minder kosten. Oefening

1. Zoek in de hierboven beschreven situatie een mogelijk leidingennet op

met een waarde van 24 kosteneenheden. 2. Probeer na te gaan of er een mogelijke leidingennet is met een waarde van minder dan 24 kosteenheden.

Kerngroep Delft


-5-


In deze oefening hebben we een leidingennet gevonden met minimale kosten. Dit netwerk noemen we optimaal.

Een paar begrippen Voordat we twee efficiënte oplossingsmethoden van het probleem van de boorplatforms zullen bespreken zijn een paar begrippen van belang. We bekijken in dit gedeelte grafen (netwerken) die samenhangend zijn, dat wil zeggen dat ieder punt verbonden is met elk ander punt via de verbindingslijnen en punten van de graaf.

Figuur 4: onsamenhangende graaf

Figuur 5: samenhangende graaf

Als een graaf een of meer cykels heeft dan wil dit zeggen dat je rondjes kunt lopen in de graaf. Definitie 1: Een pad tussen twee punten is een verzameling van verschillende verbindingslijnen die deze twee punten met elkaar verbinden.

Definitie 2: Een pad dat begint en eindigt in hetzelfde punt wordt een cykel genoemd. Definitie 3: Een opspannende boom van een samenhangende graaf is een deelgraaf die alle punten van de graaf bevat en een boom is.

Definitie 4: Een boom is een samenhangende graaf die geen cykels bevat. Van onderstaande graaf (figuur 6) is een aantal opspannende bomen te maken. In de figuren 7 en 8 zie je er twee.

Figuur 6: een voorbeeld Kerngroep Delft


-6-


Figuur 7: een opspannende boom

Figuur 8: een opspannende boom

Oefening Teken van onderstaande graaf drie verschillende opspannende bomen.

Zoals je gezien hebt in het voorbeeld van de boorplatforms wordt er aan verbindingslijnen soms een waarde gegeven. In het leidingennet van de platforms werden zo de kosten aangegeven. Maar zo kan ook het aantal kilometers tussen twee plaatsen, of de tijd die het kost om van de ene plaats naar de ander plaats te gaan genoteerd worden. In plaats van waarde wordt ook wel het woord gewicht gebruikt. Een graaf voorzien van gewichten wordt een gewogen graaf genoemd of een netwerk. De verbindingslijnen worden ook wel takken of wegen genoemd. Net als bij het boorplatformprobleem zijn we geïnteresseerd in het totale gewicht van een opspannende boom van een netwerk. Denk maar aan het voorbeeld uit de inleiding.

Kerngroep Delft


-7-


Oefening Gegeven is de gewogen graaf hieronder. 1. Teken twee opspannende bomen, één met totaal gewicht 16 en één met totaal gewicht 26. 2. Kun je een opspannende boom tekenen met een totaal gewicht kleiner dan 16?

Vaak is het vinden van een opspannende boom waarvan het totale gewicht minimaal (zo klein mogelijk) is van belang, bijvoorbeeld om een zo goedkoop mogelijk netwerk aan te leggen. Een dergelijke boom heet een minimaal opspannende boom. De netwerken die we tot nu toe bekeken hebben, zijn redelijk eenvoudig. Een minimaal opspannende boom is met een beetje geluk nog wel te vinden. Je kunt je voorstellen dat voor ingewikkelde situaties het handig zou kunnen zijn om een soort recept ter beschikking te hebben. Er zijn diverse algoritmes (een algoritme is een soort recept van hoe je iets moet doen) die ons in staat stellen minimaal opspannende bomen te vinden. We bespreken het algoritme van Kruskal en het algoritme van Prim.

Het algoritme van Kruskal Hoe dit algoritme werkt, zullen we aan de hand van de graaf uit de laatste oefening bekijken, (zie figuur 9). Stap 1 Zoek een verbindingslijn met het kleinste gewicht. Dit is in dit voorbeeld de lijn van A naar B (zie figuur 10a)

Figuur 9

Kerngroep Delft


-8-


Stap 2 Voeg nu toe een lijn met het laagste gewicht zonder dat er een cykel ontstaat. Dit is hier bijvoorbeeld de lijn van E naar D (zie figuur 10b) Stap 3 Herhaal stap 2 totdat geen nieuwe lijn meer gekozen kan worden. Zie de figuren 10c en 10d. Figuur 10a

Figuur 10b

Figuur 10c Figuur 10d

Deze minimaal opspannende boom heeft een waarde (gewicht) van 13.

Het algoritme van Prim Ook nu gebruiken we weer de graaf uit de laatste oefening om uit te leggen hoe dit algoritme werkt (zie figuur 11). Stap 1 Kies een willekeurig punt van de graaf, bijvoorbeeld C. Neem nu een met dit punt verbonden lijn waarvan het gewicht zo laag mogelijk is. Dit is de lijn van C naar E (zie figuur 12a) Stap 2 Zoek onder alle verbindingslijnen tussen een niet verbonden punt en een inmiddels wel verbonden punt, de lijn met het laagste gewicht. Dit is bijvoorbeeld de lijn van A naar E (zie figuur 12b)

Figuur 11

Stap 3 Herhaal stap 2 totdat een opspannende boom is ontstaan. Zie de figuren 12c en 12d.

Kerngroep Delft


-9-


Figuur 12a

Figuur 12b

Figuur 12c

Figuur 12d

Het algoritme van Prim werkt Gegeven is een (niet-gerichte) samenhangende graaf G, bestaande uit een verzameling knooppunten en een aantal wegen tussen die knooppunten. Het algoritme van Prim levert als volgt een boom op. Noem de verzameling van knooppunten die tot de boom gaan behoren K en de verzameling wegen die tot de boom gaan behoren W. Om te beginnen stoppen we een willekeurig knooppunt (k1) in K. Vervolgens bepalen we het knooppunt dat het dichtste bij het eerste knooppunt ligt (k2) en dat stoppen we ook in K. De weg w1 die de twee knooppunten met elkaar verbindt, stoppen we in W. Als volgende stap bepalen we een knooppunt k3 dat nog niet in K zit en het dichtste bij één van de knooppunten in K zit. De weg die die verbinding vormt, w2 stoppen we in W. Die laatste stap wordt herhaald, en zo vinden we k4 en w3. Enzovoorts, totdat alle knooppunten in K zijn gestopt. Als de oorspronkelijke graaf n knooppunten heeft, dan zitten er uiteindelijk n-1 wegen in W. Bijvoorbeeld, als de graaf 18 knooppunten heeft, dan levert het algoritme van Prim een verzameling knooppunten k1, k2, ..., k18 en een verzameling wegen w1, w2, ..., w17.

Kerngroep Delft


- 10 -


Levert dit algoritme nu ook een minimaal opspannende boom? De boom die het algoritme, uitgaande van graaf G, levert noemen we P. De vraag is dan: is P een minimaal opspannende boom. G heeft in ieder geval wel minimaal opspannende bomen. We noemen de minimaal opspannende boom die het meest op P lijkt T. Uiteindelijk zal blijken dat P hetzelfde is als T, en dus is P al die tijd al een opspannende boom geweest. Wat bedoelen we met “T lijkt het meeste op P”. Een boom T lijkt op P, wanneer een aantal wegen, bijvoorbeeld w1, w2, w3, ..., w9 van P ook deel uit maken van T. Een boom T lijkt meer op P als zelfs het rijtje w1, w2, w3, ..., w9, w10, w11 deel uit maakt van T. De boom die het meeste lijkt op P heeft het langste rijtje w1, w2, w3, ..., wk-1 dat deel uit maakt van P. Als T niet hetzelfde is als P, dan zit de weg wk zit in dat geval niet in T. De weg wk zit wel in P en verbindt daar twee knooppunten A en B. Stel nou eens dat T niet hetzelfde is als P. Splits de boom T in twee stukken. Een stuk met alle knooppunten die horen bij de wegen w1, w2, w3, ..., wk-1 en een stuk met de andere knooppunten. A zit in het ene stuk en B zit in het andere stuk. Hoewel wk niet in T zit, is er wel een pad in T dat A met B verbindt. Dat pad begint met een aantal wegen uit het ene stuk (een aantal wegen van w1, w2, w3, ..., wk-1) gevolgd door een aantal wegen uit het andere stuk om bij B te komen. In dat pad is een weg die het ene stuk met het andere stuk van T verbindt. Deze verbindingsweg heeft een gewicht dat groter is dan (of gelijk is aan) het gewicht van wk. Immers: anders zou in het algoritme van Prim wel gekozen zijn voor die verbindingsweg in plaats van wk. We slopen de verbindingsweg uit T en in plaats daarvan voegen we de weg wk toe. Dat levert opnieuw een minimaal opspannende boom S op. (Daar moet je wel even over nadenken ...) Die boom S heeft behalve w1, w2, w3, ..., wk-1 ook nog eens wk gemeenschappelijk met P. Maar dat was niet de afspraak. T was de boom die het meeste op P leek. Kortom: er is iets mis met die boom S die gemaakt is door het toevoegen van wk Blijkbaar zaten alle wegen w1, w2, w3, ..., wk-1, wk. al in T, oftewel T is hetzelfde als P. En dus is P een minimaal opspannende boom.

Kerngroep Delft


- 11 -


Kerngroep Delft


- 12 -

Steinerpunten

Module 4 Steinerpunten



module 4


Alle rechten voorbehouden. Niets uit deze uitgave mag worden verveelvoudigd, opgeslagen in een geautomatiseerd gegevensbestand, of openbaar gemaakt, in enige vorm of op enige wijze, hetzij eletronisch, mechanisch, door fotokopieën, opnamen, of op enige andere manier, zonder voorafgaande schriftelijke toestemming van de kerngroep.

Kerngroep Delft


-2-


Module 4 Theorie

Steinerpunten Pagina’s 5 t/m 10

Opgaven

Neem voor meer materiaal contact op met

Uitwerkingen

de kerngroep via [email protected]

Toetsopgaven Uitwerkingen van de toetsopgaven Op het internet

Kerngroep Delft

http://space.geocities.jp/flashr0d/steinertree.html


-3-


Geachte docent, Deze module vereist als voorkennis de inhoud van Module 1: minimaal opspannende bomen. Om uw leerlingen zich het onderwerp Steinerpunten eigen te laten maken kunt u op diverse wijzen gebruik maken van het materiaal in deze module. U kunt de moduletekst voorleggen aan de leerlingen en de genoemde internetverwijzingen gebruiken voor uzelf, als achtergrondinformatie. U kunt het materiaal gebruiken om een eigen vorm te geven aan uw lessen of u gebruikt de diverse onderdelen om uw eigen verhaal over het onderwerp voor te bereiden. De opdrachten uit de module gebruikt u dan bijvoorbeeld als oefenmateriaal. De leerlingen kunnen zich verdiepen in het onderwerp door middel van eigen onderzoek. U heeft dan materiaal en internetverwijzingen beschikbaar als achtergrondinformatie. Het materiaal vanaf pagina 10 is verkrijgbaar door contact op te nemen met de kerngroep via [email protected]. Module 1 is geschikt om in klas 4 te behandelen. Deze vervolgmodule kan beter in klas 5 of klas 6 worden doorgenomen.

Kerngroep Delft


-4-


Module 4 Steinerbomen Bij het zoeken naar een minimaal opspannende boom in een netwerk wordt steeds uitgegaan van de wegen en de knopen waaruit dat netwerk bestaat. Uitgaande van het netwerk in onderstaande figuur bijvoorbeeld werd gezocht naar een boom met zo klein mogelijk totaal gewicht die alle knopen verbindt. Wanneer nu de knopen supermarkten voorstellen, dan is het natuurlijk reuze interessant om te weten wat de kortste verbinding tussen die supermarkten onderling is. Het is ook mogelijk dat de eigenaar van de supermarktketen veel meer geïnteresseerd is in het antwoord op de vraag waar hij zijn distributiecentrum moet bouwen om zijn winkels zo goedkoop mogelijk te bevoorraden. Het distributiecentrum hoeft niet in één van die knopen gebouwd te worden en misschien moet hij wel meer dan één distributiecentrum bouwen. Om een dergelijk probleem op te lossen, voeg je knopen toe aan het netwerk (de plekken waar een distributiecentrum moet komen). Je weet alleen niet precies waar. Je weet alleen wel dat knopen zo economisch mogelijk geplaatst moeten worden en de verbindingswegen naar de oorspronkelijke knopen (de supermarkten) samen zo kort mogelijk moeten zijn. In het bovenstaande geval kun je je voorstellen dat er extra knopen ergens tussen de bestaande knopen geplaatst moeten worden. Maar waar precies? Dat is nog niet zo eenvoudig. Laten we wat eenvoudiger beginnen; met drie supermarkten die op de hoekpunten van een gelijkzijdige driehoek liggen. Een verstandige plaats om een distributiecentrum te bouwen is misschien het zwaartepunt. In het voorbeeld hieronder gaan we dit eens nader bekijken. Voorbeeld Gegeven is de gelijkzijdige driehoek ABC met zijden van lengte 1. De minimale-opspannende boom heeft lengte 2. In het figuur hiernaast is het zwaartepunt Z van driehoek ABC geconstrueerd. Met behulp van de stelling van Pythagoras of met behulp van de goniometrie is de lengte van AD te berekenen; AD = 12 3 (Ga dit zelf na)

Kerngroep Delft


-5-


Een bekende eigenschap van zwaartelijnen in een driehoek is dat

AZ : ZD = CZ : ZF = BZ : ZE = 2 :1 Dus: AZ = 2 ⋅ 1 3 = 1 3 3 2 3 1 1 Op dezelfde manier: BZ = 3 en CZ = 3. 3 3

Na toevoeging van Z aan het netwerk is de gevraagde minimaal opspannende boom hiernaast getekend. De totale lengte is

3 ⋅ 13 3 = 3

en dit is kleiner dan de

lengte van de oorspronkelijke minimaal opspannende boom. Vraag: Toon aan: ∠AZB = ∠BZC = ∠CZA = 1200

Definitie Het vinden van een lijnenstelsel dat een aantal punten in het vlak met elkaar verbindt met minimale lengte, heet het vinden van een Steinerboom. De punten die toegevoegd worden heten Steinerpunten. In het voorbeeld zie je in het tweede plaatje de Steinerboom getekend en Z is het Steinerpunt, tenminste wanneer er niet een boom te verzinnen is die de drie hoekpunten verbindt, met een nog kleinere totale lengte. Wees gerust, zo’n boom is niet te vinden. We komen hier later op terug. In een driehoek is het toevoegen van één Steinerpunt voldoende en in een gelijkzijdige driehoek is dat het zwaartepunt. In een niet gelijkzijdige driehoek kan het Steinerpunt ook redelijk eenvoudig geconstrueerd worden. In het speciale geval van een driehoek heet het Steinerpunt ook het punt van Toricelli (1609-1647) of punt van Fermat (1601-1665).

Kerngroep Delft


-6-


Het punt van Toricelli Op de zijden van een willekeurige driehoek ABC, waarvan de grootste hoek niet groter is dan 120 graden, zijn naar buiten gelijkzijdige driehoeken ACE, CBD en ABF getekend. Vervolgens zijn de lijnstukken AD, BE en CF getekend.

In de figuur is een beetje optimistisch de letter S geplaatst. Het lijkt erop dat de lijnen AD, BE en CF elkaar snijden in één punt en dat we daar dan die letter S bij kunnen zetten. Hieronder wordt bewezen dat die lijnen elkaar werkelijk snijden in één punt en meer dan dat. De naam S zal mooi blijken te zijn gekozen, aangezien het snijpunt het Steinerpunt is van de driehoek; voor elk ander punt G binnen de driehoek zal blijken dat AG + BG + CG groter is dan AS + BS + CS . Er valt nog meer te vertellen over dit punt S, ook bekend als het punt van Toricelli of het punt van Fermat. Er worden acht eigenschappen bewezen. (Totdat bewezen is dat de lijnen AD, BE en CF elkaar in één punt snijden, bedoelen we met S het snijpunt van de lijnen AD en BE.) Eigenschap 1

AD, BE en CF zijn even lang

Omdat driehoek ACE gelijkzijdig is geldt: AC = EC Omdat driehoek BCD gelijkzijdig is geldt: CD = CB

∠ACD = ∠ACB + ∠BCD = ∠ACB + 60 0 = ∠ACB + ∠ACE = ∠ECB Kerngroep Delft


(1) (2) (3) -7-


Uit (1), (2) en (3) volgt nu: ∆ACD ≅ ∆ECB ( ∆ACD is congruent met ∆ECB ) en dus is lijnstuk AD even lang als lijnstuk BE . Op dezelfde manier kun je ook bewijzen dat lijnstuk AD even lang is als lijnstuk CF . De drie lijnstukken zijn dus even lang. Eigenschap 2 Eigenschap 3 Eigenschap 4

∠BSC = ∠ASC = ∠ASB = 1200 AD, BE en CF snijden elkaar in één punt S. de zes hoeken bij dat snijpunt S zijn elk 60 0

We gaan bewijzen dat ∠BSD = ∠DSC = 600 , waarbij S het snijpunt is van AD en BE. Stel dat in ∆BCE geldt ∠SBC = p 0 , dan volgt uit de congruentie van ∆ACD en

∆ECB dat ook ∠SDC = p 0 . Verder geldt: omdat ∆DCB gelijkzijdig is, is

∠DBC = 600 Dus ∠BDS = 600 − ∠SDC = 600 − p 0 . In driehoek BDS geldt nu dat ∠BSD = 1800 − ∠BDS − ∠SBD = 1800 − (600 − p 0 ) − (600 + p 0 ) = 600 Bekijken we nu vierhoek BDCS dan liggen de punten B, D, C en S op een gemeenschappelijke cirkel, namelijk de omgeschreven cirkel van driehoek DSC. (Door de punten D, S en C gaat een cirkel en verder geldt dat ∠SDC even groot is als ∠SBC en dus staan ze op dezelfde boog CS.) Dus is vierhoek BDCS een koordenvierhoek en geldt: ∠BSC + ∠BDC = 1800 en daaruit volgt ∠BSC = 1200 . We kunnen nu concluderen dat ∠DSC = 1200 − ∠BSD = 600 . Op dezelfde manier als hier boven kunnen we ook bewijzen dat ∠ASC = 1200 en ∠ASE = ∠ESC = 600 . Verder volgt nu uit het voorgaande dat ∠ASB = 3600 − ∠ASC − ∠BSC = 1200 .

Aangezien ∠ASB + ∠AFB = 1200 + 600 = 1800 , is vierhoek ASBF een koordenvierhoek en liggen de punten A, S, B en F dus op één cirkel. Verder zijn ∠ASF en ∠ABF even groot, omdat ze op dezelfde koorde staan, dus ∠ASF = 60 0 . Uit het bovenstaande volgt nu dat ∠ASC + ∠ASF = 1200 + 600 = 1800 ; ∠CSF is een gestrekte hoek. Dus de lijn door de punten C en F gaat ook door het punt S. We concluderen dat de lijnen AD, BE en CF door één punt gaan; het punt S. Eigenschap 5

S ligt op de omgeschreven cirkels van de driehoeken ABF, BCD en ACE

Eerder werd al opgemerkt, dat vierhoek BDCS een koordenvierhoek is; de punten B, C, D en S liggen op een cirkel, de omgeschreven cirkel van driehoek BCD. Net zo wordt duidelijk dat S op de omgeschreven cirkels van de driehoeken ABF en ACE ligt.

Kerngroep Delft


-8-


Eigenschap 6

de som van de afstanden AS + BS + CS is minimaal.

In de volgende figuur is G een willekeurig gekozen punt in driehoek ABC.

Het punt H is zo gekozen, dat driehoek CGH gelijkzijdig is. Draaien van lijnstuk CG om punt C over een hoek van 600 , levert dus lijnstuk CH. Dezelfde draaiing van lijnstuk CA levert lijnstuk CE. Driehoek CGA gaat door deze draaiing over in driehoek CHE . Dan is driehoek CGA congruent met driehoek CHE en dus is GA = HE . Uit het bovenstaande volgt nu: BG + CG + AG = BG + GH + HE Het rechterlid is de lengte van het pad van punt B naar punt E. Deze lengte is minstens even groot als de lengte van lijnstuk BE. Dus BE ≤ AG + BG + CG . We voeren nu in het bijzonder deze constructie uit met punt S in de rol van G, en maken de gelijkzijdige driehoek CSH. De punten S en H liggen op lijnstuk BE. En we vinden AS + BS + CS = HE + BS + SH = BE . In het bijzonder:

AS + BS + CS ≤ AG + BG + CG

We hebben nu dus ook de volgende eigenschap bewezen: Eigenschap 7

AS + BS + CS = BE = AD = CF

De laatste eigenschap die we bewijzen is: Eigenschap 8

AS + BS + CS is kleiner of gelijk aan de lengte van de minimaal opspannende boom van driehoek ABC

Stel de lengte van de minimale-opspannende boom is gelijk aan AB + AC (in andere gevallen is het bewijs gemakkelijk aan te passen). We weten dat AC = AE . De lengte van de minimaal opspannende boom is dus ook gelijk aan AB + AE en deze lengte is groter dan de lengte van lijnstuk BE.

Kerngroep Delft


-9-


Steinerpunten in een driehoek In de vorige paragraaf werd duidelijk dat de Steinerboom van een driehoek, neerkomt op het construeren van het punt van Toricelli van die driehoek. We beperken ons dan wel tot driehoeken waarvan de grootste hoek kleiner is dan 1200 . Eigenschap 5 uit de vorige paragraaf levert een andere manier om S te construeren. 1) Bepaal de grootste hoek van driehoek ABC. Laat dit ∠C zijn en ∠C < 1200 . 2) Teken een gelijkzijdige driehoek met de langste zijde van driehoek ABC als een van de zijden. Aangezien tegenover de grootste hoek de langste zijde ligt, is de langste zijde dus zijde AB. Het derde hoekpunt D van deze gelijkzijdige driehoek ligt tegenover punt C. 3) Construeer een cirkel door de punten A, B en D van de gelijkzijdige driehoek ABD; de omgeschreven cirkel van driehoek ABD. Het middelpunt M van deze cirkel is het snijpunt van de middelloodlijnen van de zijden van driehoek ABD. 4) Trek een lijn van punt C naar punt D. Het Steiner-punt S is het snijpunt van die lijn tussen C en D met de cirkel.

Deze manier van construeren komt van pas in het vervolg, wanneer we op zoek gaan naar Steinerbomen en –punten van vierhoeken, vijfhoeken, enzovoorts...

Kerngroep Delft


- 10 -

Hillier−Lieberman: Introduction to Operations Research, Eighth Edition

9. Network Optimization Models

9.1

Text

PROTOTYPE EXAMPLE

© The McGraw−Hill Companies, 2004

283

375

A network representation is essential because of the flow of goods through several stages: purchase of crude oil from various suppliers, shipping it to refineries, refining it into various products, and sending the products to distribution centers and product storage terminals for subsequent sale. As discussed in Sec. 3.5, the modeling system enabled the company to reduce its petroleum products inventory by over $116 million with no drop in service levels. This resulted in a savings in annual interest of $14 million as well as improvements in coordination, pricing, and purchasing decisions worth another $2.5 million each year, along with many indirect benefits. In this one chapter we only scratch the surface of the current state of the art of network methodology. However, we shall introduce you to five important kinds of network problems and some basic ideas of how to solve them (without delving into issues of data structures that are so vital to successful large-scale implementations). Each of the first three problem types—the shortest-path problem, the minimum spanning tree problem, and the maximum flow problem—has a very specific structure that arises frequently in applications. The fourth type—the minimum cost flow problem—provides a unified approach to many other applications because of its far more general structure. In fact, this structure is so general that it includes as special cases both the shortest-path problem and the maximum flow problem as well as the transportation problem and the assignment problem from Chap. 8. Because the minimum cost flow problem is a special type of linear programming problem, it can be solved extremely efficiently by a streamlined version of the simplex method called the network simplex method. (We shall not discuss even more general network problems that are more difficult to solve.) The fifth kind of network problem considered here involves determining the most economical way to conduct a project so that it can be completed by its deadline. A technique called the CPM method of time-cost trade-offs is used to formulate a network model of the project and the time-cost trade-offs for its activities. Either marginal cost analysis or linear programming then is used to solve for the optimal project plan. The first section introduces a prototype example that will be used subsequently to illustrate the approach to the first three of these problems. Section 9.2 presents some basic terminology for networks. The next four sections deal with the first four problems in turn, and Sec. 9.7 then is devoted to the network simplex method. Section 9.8 presents the CPM method of time-cost trade-offs.

■ 9.1

PROTOTYPE EXAMPLE SEERVADA PARK has recently been set aside for a limited amount of sightseeing and backpack hiking. Cars are not allowed into the park, but there is a narrow, winding road system for trams and for jeeps driven by the park rangers. This road system is shown (without the curves) in Fig. 9.1, where location O is the entrance into the park; other letters designate the locations of ranger stations (and other limited facilities). The numbers give the distances of these winding roads in miles. The park contains a scenic wonder at station T. A small number of trams are used to transport sightseers from the park entrance to station T and back. The park management currently faces three problems. One is to determine which route from the park entrance to station T has the smallest total distance for the operation of the trams. (This is an example of the shortest-path problem to be discussed in Sec. 9.3.) A second problem is that telephone lines must be installed under the roads to establish telephone communication among all the stations (including the park entrance). Because the installation is both expensive and disruptive to the natural environment, lines will be installed under just enough roads to provide some connection between every pair

284


376


CHAPTER 9


Text

NETWORK OPTIMIZATION MODELS

A 7

2

2

T

5 5

O

4

B

D

3 ■ FIGURE 9.1 The road system for Seervada Park.

1

1

4 C

4

7

E

of stations. The question is where the lines should be laid to accomplish this with a minimum total number of miles of line installed. (This is an example of the minimum spanning tree problem to be discussed in Sec. 9.4.) The third problem is that more people want to take the tram ride from the park entrance to station T than can be accommodated during the peak season. To avoid unduly disturbing the ecology and wildlife of the region, a strict ration has been placed on the number of tram trips that can be made on each of the roads per day. (These limits differ for the different roads, as we shall describe in detail in Sec. 9.5.) Therefore, during the peak season, various routes might be followed regardless of distance to increase the number of tram trips that can be made each day. The question pertains to how to route the various trips to maximize the number of trips that can be made per day without violating the limits on any individual road. (This is an example of the maximum flow problem to be discussed in Sec. 9.5.)

■ 9.2

THE TERMINOLOGY OF NETWORKS A relatively extensive terminology has been developed to describe the various kinds of networks and their components. Although we have avoided as much of this special vocabulary as we could, we still need to introduce a considerable number of terms for use throughout the chapter. We suggest that you read through this section once at the outset to understand the definitions and then plan to return to refresh your memory as the terms are used in subsequent sections. To assist you, each term is highlighted in boldface at the point where it is defined. A network consists of a set of points and a set of lines connecting certain pairs of the points. The points are called nodes (or vertices); e.g., the network in Fig. 9.1 has seven nodes designated by the seven circles. The lines are called arcs (or links or edges or branches); e.g., the network in Fig. 9.1 has 12 arcs corresponding to the 12 roads in the road system. Arcs are labeled by naming the nodes at either end; for example, AB is the arc between nodes A and B in Fig. 9.1. The arcs of a network may have a flow of some type through them, e.g., the flow of trams on the roads of Seervada Park in Sec. 9.1. Table 9.1 gives several examples of flow in typical networks. If flow through an arc is allowed in only one direction (e.g., a oneway street), the arc is said to be a directed arc. The direction is indicated by adding an arrowhead at the end of the line representing the arc. When a directed arc is labeled by listing two nodes it connects, the from node always is given before the to node; e.g., an arc that is directed from node A to node B must be labeled as AB rather than BA. Alternatively, this arc may be labeled as A B.



9.2


Text

THE TERMINOLOGY OF NETWORKS

285

377

■ TABLE 9.1 Components of typical networks Nodes

Arcs

Flow

Intersections Airports Switching points Pumping stations Work centers

Roads Air lanes Wires, channels Pipes Materials-handling routes

Vehicles Aircraft Messages Fluids Jobs

If flow through an arc is allowed in either direction (e.g., a pipeline that can be used to pump fluid in either direction), the arc is said to be an undirected arc. To help you distinguish between the two kinds of arcs, we shall frequently refer to undirected arcs by the suggestive name of links. Although the flow through an undirected arc is allowed to be in either direction, we do assume that the flow will be one way in the direction of choice rather than having simultaneous flows in opposite directions. (The latter case requires the use of a pair of directed arcs in opposite directions.) However, in the process of making the decision on the flow through an undirected arc, it is permissible to make a sequence of assignments of flows in opposite directions, but with the understanding that the actual flow will be the net flow (the difference of the assigned flows in the two directions). For example, if a flow of 10 has been assigned in one direction and then a flow of 4 is assigned in the opposite direction, the actual effect is to cancel 4 units of the original assignment by reducing the flow in the original direction from 10 to 6. Even for a directed arc, the same technique sometimes is used as a convenient device to reduce a previously assigned flow. In particular, you are allowed to make a fictional assignment of flow in the “wrong” direction through a directed arc to record a reduction of that amount in the flow in the “right” direction. A network that has only directed arcs is called a directed network. Similarly, if all its arcs are undirected, the network is said to be an undirected network. A network with a mixture of directed and undirected arcs (or even all undirected arcs) can be converted to a directed network, if desired, by replacing each undirected arc by a pair of directed arcs in opposite directions. (You then have the choice of interpreting the flows through each pair of directed arcs as being simultaneous flows in opposite directions or providing a net flow in one direction, depending on which fits your application.) When two nodes are not connected by an arc, a natural question is whether they are connected by a series of arcs. A path between two nodes is a sequence of distinct arcs connecting these nodes. For example, one of the paths connecting nodes O and T in Fig. 9.1 is the sequence of arcs OB–BD–DT (O B D T), or vice versa. When some of or all the arcs in the network are directed arcs, we then distinguish between directed paths and undirected paths. A directed path from node i to node j is a sequence of connecting arcs whose direction (if any) is toward node j, so that flow from node i to node j along this path is feasible. An undirected path from node i to node j is a sequence of connecting arcs whose direction (if any) can be either toward or away from node j. (Notice that a directed path also satisfies the definition of an undirected path, but not vice versa.) Frequently, an undirected path will have some arcs directed toward node j but others directed away (i.e., toward node i). You will see in Secs. 9.5 and 9.7 that, perhaps surprisingly, undirected paths play a major role in the analysis of directed networks. To illustrate these definitions, Fig. 9.2 shows a typical directed network. (Its nodes and arcs are the same as in Fig. 3.13, where nodes A and B represent two factories, nodes D and E represent two warehouses, node C represents a distribution center, and the arcs represent shipping lanes.) The sequence of arcs AB–BC–CE (A B C E) is a directed path from

286


378


CHAPTER 9


Text

NETWORK OPTIMIZATION MODELS

D

A

C

■ FIGURE 9.2 The distribution network for Distribution Unlimited Co., first shown in Fig. 3.13, illustrates a directed network.

B

E

node A to E, since flow toward node E along this entire path is feasible. On the other hand, BC–AC–AD (B C A D) is not a directed path from node B to node D, because the direction of arc AC is away from node D (on this path). However, B C A D is an undirected path from node B to node D, because the sequence of arcs BC–AC–AD does connect these two nodes (even though the direction of arc AC prevents flow through this path). As an example of the relevance of undirected paths, suppose that 2 units of flow from node A to node C had previously been assigned to arc AC. Given this previous assignment, it now is feasible to assign a smaller flow, say, 1 unit, to the entire undirected path B C A D, even though the direction of arc AC prevents positive flow through C A. The reason is that this assignment of flow in the “wrong” direction for arc AC actually just reduces the flow in the “right” direction by 1 unit. Sections 9.5 and 9.7 make heavy use of this technique of assigning a flow through an undirected path that includes arcs whose direction is opposite to this flow, where the real effect for these arcs is to reduce previously assigned positive flows in the “right” direction. A path that begins and ends at the same node is called a cycle. In a directed network, a cycle is either a directed or an undirected cycle, depending on whether the path involved is a directed or an undirected path. (Since a directed path also is an undirected path, a directed cycle is an undirected cycle, but not vice versa in general.) In Fig. 9.2, for example, DE–ED is a directed cycle. By contrast, AB–BC–AC is not a directed cycle, because the direction of arc AC opposes the direction of arcs AB and BC. On the other hand, AB–BC–AC is an undirected cycle, because A B C A is an undirected path. In the undirected network shown in Fig. 9.1, there are many cycles, for example, OA–AB–BC–CO. However, note that the definition of path (a sequence of distinct arcs) rules out retracing one’s steps in forming a cycle. For example, OB–BO in Fig. 9.1 does not qualify as a cycle, because OB and BO are two labels for the same arc (link). On the other hand, DE–ED is a (directed) cycle in Fig. 9.2, because DE and ED are distinct arcs. Two nodes are said to be connected if the network contains at least one undirected path between them. (Note that the path does not need to be directed even if the network is directed.) A connected network is a network where every pair of nodes is connected. Thus, the networks in Figs. 9.1 and 9.2 are both connected. However, the latter network would not be connected if arcs AD and CE were removed. Consider a connected network with n nodes (e.g., the n 5 nodes in Fig. 9.2) where all the arcs have been deleted. A “tree” can then be “grown” by adding one arc (or “branch”) at a time from the original network in a certain way. The first arc can go anywhere to connect some pair of nodes. Thereafter, each new arc should be between a node that already



9.2


Text

THE TERMINOLOGY OF NETWORKS

287

379

is connected to other nodes and a new node not previously connected to any other nodes. Adding an arc in this way avoids creating a cycle and ensures that the number of connected nodes is 1 greater than the number of arcs. Each new arc creates a larger tree, which is a connected network (for some subset of the n nodes) that contains no undirected cycles. Once the (n 1)st arc has been added, the process stops because the resulting tree spans (connects) all n nodes. This tree is called a spanning tree, i.e., a connected network for all n nodes that contains no undirected cycles. Every spanning tree has exactly n 1 arcs, since this is the minimum number of arcs needed to have a connected network and the maximum number possible without having undirected cycles. Figure 9.3 uses the five nodes and some of the arcs of Fig. 9.2 to illustrate this process of growing a tree one arc (branch) at a time until a spanning tree has been obtained. There are several alternative choices for the new arc at each stage of the process, so Fig. 9.3 shows only one of many ways to construct a spanning tree in this case. Note, however, how each new added arc satisfies the conditions specified in the preceding paragraph. We shall discuss and illustrate spanning trees further in Sec. 9.4. Spanning trees play a key role in the analysis of many networks. For example, they form the basis for the minimum spanning tree problem discussed in Sec. 9.4. Another prime example is that (feasible) spanning trees correspond to the BF solutions for the network simplex method discussed in Sec. 9.7. Finally, we shall need a little additional terminology about flows in networks. The maximum amount of flow (possibly infinity) that can be carried on a directed arc is referred to as the arc capacity. For nodes, a distinction is made among those that are net generators of flow, net absorbers of flow, or neither. A supply node (or source node or source) has the property that the flow out of the node exceeds the flow into the node. The reverse case is a demand node (or sink node or sink), where the flow into the node exceeds the flow out of the node. A transshipment node (or intermediate node) satisfies conservation of flow, so flow in equals flow out.

■ FIGURE 9.3 Example of growing a tree one arc at a time for the network of Fig. 9.2: (a) The nodes without arcs; (b) a tree with one arc; (c) a tree with two arcs; (d) a tree with three arcs; (e) a spanning tree.

A

D

A

C B

D C

E

E (d )

(a)

A

D (b)

A

D

A

D C

E (c)

B

E (e)

Wiskunde in wetenschap: Optimaliseren in netwerken

Recommend Documents