Formuler modellen | Test og fejl | Løs modellen
Brug løsningen i Excel at finde maksimalt flow fra knude S til knude T i et dirigeret 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 maksimalt flow 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 strømmen på hver bue. For eksempel, hvis strømmen på SB er 2, er celle D5 lig med 2.
b. Hvad er begrænsningerne for disse beslutninger? Nettostrømmen (Flow Out - Flow In) for knude A, B, C, D og E skal være lig med 0. Med andre ord, Flow Out = Flow In. Hver bue har også en fast kapacitet. Flowet på hver bue skal være mindre end denne kapacitet.
c. Hvad er det overordnede mål for ydeevne for disse beslutninger? Det overordnede mål for ydeevne er det maksimale flow, så målet er at maksimere denne mængde. Det maksimale flow svarer til udstrømning fra knude S.
2. For at gøre modellen lettere at forstå skal du oprette følgende navngivne områder.
| Område navn | Celler |
|---|---|
| Fra | B4: B15 |
| Til | C4: C15 |
| Flyde | D4: D15 |
| Kapacitet | F4: F15 |
| Forsyningsbehov | K5: K9 |
| MaximumFlow | D17 |
3. Indsæt følgende funktioner.
Forklaring: SUMIF -funktionerne beregner nettostrømmen for hver node. For knude A summerer den første SUMIF -funktion værdierne i Flow -kolonnen med et "A" i kolonnen Fra (Flow Out). Den anden SUMIF -funktion summerer værdierne i Flow -kolonnen med et "A" i kolonnen Til (Flow In). Maksimumstrøm er lig med værdien i celle I4, som er strømmen ud af knude S. Fordi knude A, B, C, D og E har et nettostrøm på 0, vil Flow ud af knude S lig med Flow In for knude T.
Test og fejl
Med denne formulering bliver det let at analysere enhver prøveløsning.
1. For eksempel stien SADT med et flow på 2. Stien SCT med et flow på 4. Stien SBET med et flow på 2. Disse stier giver et samlet flow på 8.
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 MaximumFlow for målet.
3. Klik på Maks.
4. Indtast Flow for de skiftende variabelceller.
5. Klik på Tilføj for at angive følgende begrænsning.
6. Klik på Tilføj for at angive følgende begrænsning.
7. Marker 'Gør ubegrænsede variabler til ikke-negative', og vælg 'Simplex LP'.
8. Klik til sidst på Løs.
Resultat:
Den optimale løsning:
Konklusion: stien SADT med et flow på 2. Stien SCT med et flow på 4. Stien SBET med et flow på 2. Stien SCET med et flow på 2. Stien SACET med en strøm på 1. Stien SACDT med et flow på 1. Disse stier giver et maksimalt flow på 12.
