300 Exempel

Maximalt flödesproblem

Maximum Flow Problem

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.





Maximalt flödesproblem 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.

Infoga funktioner

Förklaring: The SUMIF funktioner beräknar nettoflö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 alla testlösningar.

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.

Testlösning

hur skapar du en tabell i Excel

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. Klicka på Solver i gruppen Analysera på fliken Data.

Klicka på Solver

Obs: hittar du inte Solver -knappen? Klicka här för att ladda Tilläggsprogram för lösare .

Ange lösningsparametrarna (läs vidare). Resultatet ska överensstämma med bilden nedan.

Lösarparametrar

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.

Nettoflödebegränsning

6. Klicka på Lägg till för att ange följande begränsning.

Kapacitetsbegränsning

7. Markera 'Gör obegränsade variabler icke-negativa' och välj 'Simplex LP'.

8. Slutligen klickar du på Lös.

Resultat:

Resultat för lösare

Den optimala lösningen:

Maximalt flödesproblem

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.

5/7 klar! Läs mer om lösaren>
Gå till nästa kapitel: Analys ToolPak



^