Formuleer het model | Trial and Error | Los het model op
Gebruik de oplosser in Excel om de te vinden maximale stroom van knooppunt S naar knooppunt T in een gericht 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 maximale stroom probleem, beantwoord dan de volgende drie vragen.
A. Wat zijn de te nemen beslissingen? Voor dit probleem hebben we Excel nodig om de stroom op elke boog te vinden. Als de stroom op SB bijvoorbeeld 2 is, is cel D5 gelijk aan 2.
B. Wat zijn de beperkingen van deze beslissingen? De Netto Flow (Flow Out - Flow In) van knooppunt A, B, C, D en E moet gelijk zijn aan 0. Met andere woorden, Flow Out = Flow In. Ook heeft elke boog een vaste capaciteit. De stroom op elke boog moet kleiner zijn dan deze capaciteit.
C. Wat is de algemene prestatiemaatstaf voor deze beslissingen? De algemene prestatiemaatstaf is de maximale stroom, dus het doel is om deze hoeveelheid te maximaliseren. De maximale stroom is gelijk aan de stroom uit knooppunt S.
2. Maak de volgende benoemde bereiken om het model begrijpelijker te maken.
| Bereiknaam | Cellen |
|---|---|
| Van | B4:B15 |
| Tot | C4:C15 |
| Stromen | D4:D15 |
| Capaciteit | F4:F15 |
| Aanbod Vraag | K5:K9 |
| Maximale Flow | D17 |
3. Voeg de volgende functies in.
Uitleg: De SUMIF-functies berekenen de nettostroom van elk knooppunt. Voor knooppunt A telt de eerste SUMIF-functie de waarden in de Flow-kolom op met een "A" in de From-kolom (Flow Out). De tweede SUMIF-functie telt de waarden in de Flow-kolom op met een "A" in de To-kolom (Flow In). Maximale stroom is gelijk aan de waarde in cel I4, de stroom uit knooppunt S. Omdat knooppunt A, B, C, D en E een netto stroom van 0 hebben, is Stroom uit knooppunt S gelijk aan Stroom binnen van knooppunt T.
Vallen en opstaan
Met deze formulering wordt het gemakkelijk om elke proefoplossing te analyseren.
1. Bijvoorbeeld het pad SADT met een stroom van 2. Het pad SCT met een stroom van 4. Het pad SBET met een stroom van 2. Deze paden geven een totale stroom van 8.
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 MaximumFlow in voor de doelstelling.
3. Klik op Max.
4. Voer Flow in voor de veranderende variabele cellen.
5. Klik op Toevoegen om de volgende beperking in te voeren.
6. Klik op Toevoegen om de volgende beperking in te voeren.
7. Vink 'Make Unconstrained Variables Non-Negative' aan en selecteer 'Simplex LP'.
8. Klik ten slotte op Oplossen.
Resultaat:
De optimale oplossing:
Conclusie: het pad SADT met een stroom van 2. Het pad SCT met een stroom van 4. Het pad SBET met een stroom van 2. Het pad SCET met een stroom van 2. Het pad SACET met een stroom van 1. Het pad SACDT met een stroom van 1. Deze paden geven een maximale stroom van 12.
