Formuleer het model | Trial and Error | Los het model op
Gebruik de oplosser in Excel om de te vinden Kortste weg van knooppunt S naar knooppunt T in een ongericht netwerk. Punten in een netwerk worden knooppunten genoemd (S, A, B, C, D, E en T). Lijnen in een netwerk worden bogen genoemd (SA, SB, SC, AC, enz.).
Formuleer het model
Het model dat we gaan oplossen ziet er in Excel als volgt uit.
1. Om dit te formuleren kortste pad probleem, beantwoord dan de volgende drie vragen.
A. Wat zijn de te nemen beslissingen? Voor dit probleem hebben we Excel nodig om erachter te komen of een boog zich op het kortste pad bevindt of niet (Ja=1, Nee=0). Als SB bijvoorbeeld deel uitmaakt van het kortste pad, is cel F5 gelijk aan 1. Zo niet, dan is cel F5 gelijk aan 0.
B. Wat zijn de beperkingen van deze beslissingen? De nettostroom (stroom uit - stroom in) van elk knooppunt moet gelijk zijn aan vraag/aanbod. Knooppunt S mag slechts één uitgaande boog hebben (Nettostroom = 1). Knooppunt T mag slechts één ingaande boog hebben (Nettostroom = -1). Alle andere knooppunten moeten één uitgaande boog en één ingaande boog hebben als het knooppunt zich op het kortste pad bevindt (nettostroom = 0) of geen stroom (netstroom = 0).
C. Wat is de algemene prestatiemaatstaf voor deze beslissingen? De algemene prestatiemaatstaf is de totale afstand van het kortste pad, dus het doel is om deze hoeveelheid te minimaliseren.
2. Maak de volgende benoemde bereiken om het model begrijpelijker te maken.
| Bereiknaam | Cellen |
|---|---|
| Van | B4:B21 |
| Tot | C4:C21 |
| Afstand | D4:D21 |
| Gaan | F4:F21 |
| NetFlow | I4:I10 |
| Aanbod Vraag | K4:K10 |
| Totale afstand | F23 |
3. Voeg de volgende functies in.
Uitleg: De SUMIF-functies berekenen de nettostroom van elk knooppunt. Voor knooppunt S telt de functie SUMIF de waarden in de kolom Go op met een "S" in de kolom Van. Als gevolg hiervan kan alleen cel F4, F5 of F6 1 zijn (één uitgaande boog). Voor knooppunt T telt de functie SUMIF de waarden in de kolom Ga op met een "T" in de kolom Naar. Als gevolg hiervan kan alleen cel F15, F18 of F21 1 zijn (één ingaande boog). Voor alle andere knooppunten kijkt Excel in de kolom Van en Naar. Totale afstand is gelijk aan het somproduct van Distance and Go.
Vallen en opstaan
Met deze formulering wordt het gemakkelijk om elke proefoplossing te analyseren.
1. Het pad SBET heeft bijvoorbeeld een totale afstand van 16.
Het is niet nodig om trial and error te gebruiken. We zullen hierna beschrijven hoe de Excel Oplosser kan worden gebruikt om snel de optimale oplossing te vinden.
Los het model op
Voer de volgende stappen uit om de optimale oplossing te vinden.
1. Klik op het tabblad Gegevens in de groep Analyseren op Oplosser.
Opmerking: kunt u de knop Oplosser niet vinden? Klik hier om de Oplosser-invoegtoepassing te laden.
Voer de solverparameters in (lees verder). Het resultaat moet overeenkomen met de onderstaande afbeelding.
U hebt de keuze om de bereiknamen te typen of op de cellen in het werkblad te klikken.
2. Voer TotalDistance in voor de doelstelling.
3. Klik op Min.
4. Voer Go in voor de variabele cellen wijzigen.
5. Klik op Toevoegen om de volgende beperking in te voeren.
6. Vink 'Make Unconstrained Variables Non-Negative' aan en selecteer 'Simplex LP'.
7. Klik ten slotte op Oplossen.
Resultaat:
De optimale oplossing:
Conclusie: SADCT is de kortste weg met een totale afstand van 11.
