Formulera modellen | Test och fel | Lös modellen
Använd lösaren i Excel att hitta maximalt flöde från nod S till nod T i ett riktat nätverk. Punkter i ett nätverk kallas noder (S, A, B, C, D, E och T). Linjer i ett nätverk kallas bågar (SA, SB, SC, AC, etc).
Formulera modellen
Modellen vi ska lösa ser ut enligt följande i Excel.
1. För att formulera detta maximalt flödesproblem, svara på följande tre frågor.
a. Vilka beslut ska fattas? För detta problem behöver vi Excel för att hitta flödet på varje båge. Till exempel, om flödet på SB är 2, är cell D5 lika med 2.
b. Vilka är begränsningarna för dessa beslut? Nettoflödet (utflöde - flöde in) för nod A, B, C, D och E ska vara lika med 0. Med andra ord Flöde ut = Flöde in. Varje båge har också en fast kapacitet. Flödet på varje båge bör vara mindre än denna kapacitet.
c. Vad är det övergripande måttet på prestanda för dessa beslut? Det övergripande måttet på prestanda är det maximala flödet, så målet är att maximera denna mängd. Det maximala flödet är lika med utflödet från nod S.
2. För att göra modellen lättare att förstå, skapa följande namngivna intervall.
| Intervallnamn | Celler |
|---|---|
| Från | B4: B15 |
| Till | C4: C15 |
| Flöde | D4: D15 |
| Kapacitet | F4: F15 |
| Tillgång efterfrågan | K5: K9 |
| MaximumFlow | D17 |
3. Sätt in följande funktioner.
Förklaring: SUMIF -funktionerna beräknar nätflödet för varje nod. För nod A summerar den första SUMIF -funktionen värdena i flödeskolumnen med ett "A" i kolumnen Från (flöde ut). Den andra SUMIF -funktionen summerar värdena i flödeskolumnen med ett "A" i kolumnen Till (flöde in). Maximalt flöde är lika med värdet i cell I4, vilket är flödet från nod S. Eftersom nod A, B, C, D och E har ett nettoflöde på 0, kommer Flöde ut från nod S att vara lika med Flöde In i nod T.
Test och fel
Med denna formulering blir det enkelt att analysera vilken testlösning som helst.
1. Till exempel sökvägen SADT med ett flöde av 2. Vägen SCT med ett flöde av 4. Banan SBET med ett flöde av 2. Dessa vägar ger ett totalt flöde av 8.
Det är inte nödvändigt att använda trial and error. Vi kommer att beskriva nästa hur Excel -lösning kan användas för att snabbt hitta den optimala lösningen.
Lös modellen
För att hitta den optimala lösningen, utför följande steg.
1. På fliken Data, i gruppen Analysera, klicka på Lösare.
Obs: hittar du inte Solver -knappen? Klicka här för att ladda tilläggsprogrammet Solver.
Ange lösningsparametrarna (läs vidare). Resultatet ska överensstämma med bilden nedan.
Du kan välja att skriva intervallnamnen eller klicka på cellerna i kalkylarket.
2. Ange MaximumFlow för målet.
3. Klicka på Max.
4. Ange flöde för de ändrade variabelcellerna.
5. Klicka på Lägg till för att ange följande begränsning.
6. Klicka på Lägg till för att ange följande begränsning.
7. Markera "Gör obegränsade variabler icke-negativa" och välj "Simplex LP".
8. Slutligen klickar du på Lös.
Resultat:
Den optimala lösningen:
Slutsats: sökvägen SADT med ett flöde av 2. Vägen SCT med ett flöde av 4. Banan SBET med ett flöde av 2. Banan SCET med ett flöde av 2. Banan SACET med ett flöde av 1. Banan SACDT med ett flöde på 1. Dessa vägar ger ett maximalt flöde på 12.
