Formuler modellen | Prøve og feil | Løs modellen
Bruk løseren i utmerke å finne maksimal flyt fra node S til node T i et dirigert 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 maksimalt strømningsproblem, svar på følgende tre spørsmål.
en. Hva er avgjørelsene som skal tas? For dette problemet trenger vi Excel for å finne flyten på hver bue. For eksempel, hvis flyten på SB er 2, er celle D5 lik 2.
b. Hva er begrensningene i disse avgjørelsene? Nettostrømmen (utstrømning - innstrømning) til node A, B, C, D og E skal være lik 0. Med andre ord: Utstrømning = Innstrømning. Hver bue har også en fast kapasitet. Flyten på hver bue skal være mindre enn denne kapasiteten.
c. Hva er det generelle målet for ytelse for disse avgjørelsene? Det overordnede mål for ytelse er maksimal flyt, så målet er å maksimere denne mengden. Maksimal strømning tilsvarer utstrømning fra node S.
2. For å gjøre modellen lettere å forstå, opprett følgende navngitte områder.
| Områdenavn | Celler |
|---|---|
| Fra | B4: B15 |
| Til | C4: C15 |
| Strømme | D4: D15 |
| Kapasitet | F4: F15 |
| Tilbud etterspørsel | K5: K9 |
| MaximumFlow | D17 |
3. Sett inn følgende funksjoner.
Forklaring: SUMIF -funksjonene beregner nettostrømmen for hver node. For node A summerer den første SUMIF -funksjonen verdiene i Flow -kolonnen med et "A" i From -kolonnen (Flow Out). Den andre SUMIF -funksjonen summerer verdiene i Flow -kolonnen med et "A" i Til -kolonnen (Innstrømning). Maksimal gjennomstrømning er lik verdien i celle I4, som er strømmen ut av noden S. Fordi noden A, B, C, D og E har en netto strømning på 0, vil utstrømningen fra noden S være lik innstrømningen i noden T.
Prøve og feil
Med denne formuleringen blir det enkelt å analysere enhver prøveløsning.
1. For eksempel banen SADT med en flyt på 2. Banen SCT med en flyt på 4. Banen SBET med en strømning på 2. Disse banene gir en total flyt på 8.
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 MaximumFlow for målet.
3. Klikk på Maks.
4. Angi flyt for endring av variabelceller.
5. Klikk på Legg til for å angi følgende begrensning.
6. Klikk på Legg til for å angi følgende begrensning.
7. Merk av for "Gjør ubegrensede variabler ikke-negative" og velg "Simplex LP".
8. Til slutt klikker du på Løs.
Resultat:
Den optimale løsningen:
Konklusjon: banen SADT med en flyt på 2. Banen SCT med en flyt på 4. Banen SBET med en flyt på 2. Banen SCET med en flyt på 2. Banen SACET med en flyt på 1. Banen SACDT med en flyt på 1. Disse banene gir en maksimal flyt på 12.
