Formuler modellen | Prøve og feil | Løs modellen
Bruk løseren i utmerke å finne korteste vei fra node S til node T i et ustyrt nettverk. Punkter i et nettverk kalles noder (S, A, B, C, D, E og T). Linjer i et nettverk kalles buer (SA, SB, SC, AC, etc).
Formuler modellen
Modellen vi skal løse ser ut som følger i Excel.
1. For å formulere dette korteste veiproblem, svar på følgende tre spørsmål.
en. Hva er avgjørelsene som skal tas? For dette problemet trenger vi Excel for å finne ut om en bue er på den korteste banen eller ikke (Ja = 1, Nei = 0). For eksempel, hvis SB er en del av den korteste banen, er celle F5 lik 1. Hvis ikke, er celle F5 lik 0.
b. Hva er begrensningene i disse avgjørelsene? Nettoverstrømningen (utstrømning - innstrømning) for hver node skal være lik Tilførsel/etterspørsel. Node S skal bare ha en utgående bue (netto strømning = 1). Node T skal bare ha en inngående bue (netto strømning = -1). Alle andre noder bør ha en utgående bue og en inngående bue hvis noden er på den korteste banen (netto flyt = 0) eller ingen strøm (netto strømning = 0).
c. Hva er det generelle målet for ytelse for disse avgjørelsene? Det totale ytelsesmålet er den totale distansen til den korteste banen, så målet er å minimere denne mengden.
2. For å gjøre modellen lettere å forstå, opprett følgende navngitte områder.
| Områdenavn | Celler |
|---|---|
| Fra | B4: B21 |
| Til | C4: C21 |
| Avstand | D4: D21 |
| Gå | F4: F21 |
| NetFlow | I4: I10 |
| Tilbud etterspørsel | K4: K10 |
| Total distanse | F23 |
3. Sett inn følgende funksjoner.
Forklaring: SUMIF -funksjonene beregner nettostrømmen for hver node. For node S summerer SUMIF -funksjonen verdiene i Go -kolonnen med et "S" i From -kolonnen. Som et resultat kan bare celle F4, F5 eller F6 være 1 (en utgående bue). For node T summerer SUMIF -funksjonen verdiene i Go -kolonnen med et "T" i Til -kolonnen. Som et resultat kan bare celle F15, F18 eller F21 være 1 (en inngående bue). For alle andre noder ser Excel i Fra og Til -kolonnen. Total distanse er sumproduktet av Distance og Go.
Prøve og feil
Med denne formuleringen blir det enkelt å analysere enhver prøveløsning.
1. For eksempel har banen SBET en total avstand på 16.
Det er ikke nødvendig å bruke trial and error. Vi skal beskrive neste hvordan Excel -løsning kan brukes til raskt å finne den optimale løsningen.
Løs modellen
For å finne den optimale løsningen, utfør følgende trinn.
1. Klikk på Solver i gruppen Analyser i kategorien Data.
Merk: finner du ikke Solver -knappen? Klikk her for å laste inn Solver-tillegget.
Angi løsningsparametrene (les videre). Resultatet skal stemme overens med bildet nedenfor.
Du kan velge mellom å skrive områdene eller klikke på cellene i regnearket.
2. Skriv inn TotalDistance for målet.
3. Klikk Min.
4. Skriv Gå for de endrede variabelcellene.
5. Klikk på Legg til for å angi følgende begrensning.
6. Merk av for "Gjør ubegrensede variabler ikke-negative" og velg "Simplex LP".
7. Til slutt klikker du på Løs.
Resultat:
Den optimale løsningen:
Konklusjon: SADCT er den korteste veien med en total avstand på 11.
