Formuler modellen | Test og fejl | Løs modellen
Brug løsningen i Excel at finde korteste vej fra knude S til knude T i et ikke -styret netværk. Punkter i et netværk kaldes noder (S, A, B, C, D, E og T). Linjer i et netværk kaldes buer (SA, SB, SC, AC osv.).
Formuler modellen
Den model, vi skal løse, ser ud som følger i Excel.
1. At formulere dette korteste vej problem, besvar følgende tre spørgsmål.
en. Hvad er de beslutninger, der skal træffes? Til dette problem har vi brug for Excel for at finde ud af, om en bue er på den korteste vej eller ej (Ja = 1, Nej = 0). For eksempel, hvis SB er en del af den korteste vej, er celle F5 lig med 1. Hvis ikke, er celle F5 lig med 0.
b. Hvad er begrænsningerne for disse beslutninger? Netstrømmen (Flow Out - Flow In) for hver node skal være lig med Supply/Demand. Node S bør kun have en udgående bue (Net Flow = 1). Node T bør kun have en indgående bue (Net Flow = -1). Alle andre noder skal have en udgående bue og en indgående bue, hvis noden er på den korteste vej (Net Flow = 0) eller ingen flow (Net Flow = 0).
c. Hvad er det overordnede mål for ydeevne for disse beslutninger? Det overordnede mål for ydeevne er den samlede afstand af den korteste vej, så målet er at minimere denne mængde.
2. For at gøre modellen lettere at forstå skal du oprette følgende navngivne områder.
| Område navn | Celler |
|---|---|
| Fra | B4: B21 |
| Til | C4: C21 |
| Afstand | D4: D21 |
| Gå | F4: F21 |
| NetFlow | I4: I10 |
| Forsyningsbehov | K4: K10 |
| Total afstand | F23 |
3. Indsæt følgende funktioner.
Forklaring: SUMIF -funktionerne beregner nettostrømmen for hver node. For node S summerer SUMIF -funktionen værdierne i kolonnen Gå med et "S" i kolonnen Fra. Som et resultat kan kun celle F4, F5 eller F6 være 1 (en udgående bue). For knude T summerer SUMIF -funktionen værdierne i kolonnen Gå med et "T" i kolonnen Til. Som et resultat kan kun celle F15, F18 eller F21 være 1 (en indgående bue). For alle andre noder ser Excel i kolonnen Fra og Til. Total distance er lig med sumproduktet for Distance og Go.
Test og fejl
Med denne formulering bliver det let at analysere enhver prøveløsning.
1. For eksempel har stien SBET en samlet afstand på 16.
Det er ikke nødvendigt at bruge trial and error. Vi skal derefter beskrive, hvordan Excel -løsning kan bruges til hurtigt at finde den optimale løsning.
Løs modellen
For at finde den optimale løsning skal du udføre følgende trin.
1. Klik på Solver i gruppen Analyse under fanen Data.
Bemærk: kan du ikke finde knappen Solver? Klik her for at indlæse tilføjelsesprogrammet Solver.
Indtast løsningsparametrene (læs videre). Resultatet skal være i overensstemmelse med billedet herunder.
Du har valget mellem at skrive områdets navne eller klikke på cellerne i regnearket.
2. Indtast TotalDistance for målet.
3. Klik på Min.
4. Indtast Gå til de skiftende variabelceller.
5. Klik på Tilføj for at angive følgende begrænsning.
6. Marker 'Gør ubegrænsede variabler til ikke-negative', og vælg 'Simplex LP'.
7. Klik til sidst på Løs.
Resultat:
Den optimale løsning:
Konklusion: SADCT er den korteste vej med en samlet afstand på 11.
