Formulera modellen | Test och fel | Lös modellen
Använd lösaren i Excel att hitta kortaste vägen från nod S till nod T i ett ostyrt 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 kortaste vägproblem, svara på följande tre frågor.
a. Vilka beslut ska fattas? För detta problem behöver vi Excel för att ta reda på om en båge är på den kortaste vägen eller inte (Ja = 1, Nej = 0). Om SB till exempel är en del av den kortaste vägen är cell F5 lika med 1. Om inte är cell F5 lika med 0.
b. Vilka är begränsningarna för dessa beslut? Nettoflödet (utflöde - flöde in) för varje nod ska vara lika med Tillförsel/efterfrågan. Nod S bör bara ha en utgående båge (Net Flow = 1). Nod T bör bara ha en ingående båge (Net Flow = -1). Alla andra noder bör ha en utgående båge och en ingående båge om noden är på den kortaste vägen (Net Flow = 0) eller inget flöde (Net Flow = 0).
c. Vad är det övergripande måttet på prestanda för dessa beslut? Det övergripande måttet på prestanda är det totala avståndet till den kortaste vägen, så målet är att minimera denna mängd.
2. För att göra modellen lättare att förstå, skapa följande namngivna intervall.
| Intervallnamn | Celler |
|---|---|
| Från | B4: B21 |
| Till | C4: C21 |
| Distans | D4: D21 |
| Gå | F4: F21 |
| Nettoflödet | I4: I10 |
| Tillgång efterfrågan | K4: K10 |
| Totalt avstånd | F23 |
3. Sätt in följande funktioner.
Förklaring: SUMIF -funktionerna beräknar nätflödet för varje nod. För nod S summerar funktionen SUMMA värdena i kolumnen Gå med ett "S" i kolumnen Från. Som ett resultat kan endast cell F4, F5 eller F6 vara 1 (en utgående båge). För nod T summerar funktionen SUMMA värdena i kolumnen Gå med ett "T" i kolumnen Till. Som ett resultat kan endast cell F15, F18 eller F21 vara 1 (en ingående båge). För alla andra noder ser Excel i kolumnen Från och Till. Total distans är sumprodukten av Distance och Go.
Test och fel
Med denna formulering blir det enkelt att analysera vilken testlösning som helst.
1. Till exempel har sökvägen SBET ett totalt avstånd på 16.
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 TotalDistance för målet.
3. Klicka på Min.
4. Ange Gå för att ändra de variabla cellerna.
5. Klicka på Lägg till för att ange följande begränsning.
6. Markera "Gör obegränsade variabler icke-negativa" och välj "Simplex LP".
7. Klicka slutligen på Lös.
Resultat:
Den optimala lösningen:
Slutsats: SADCT är den kortaste vägen med ett totalt avstånd på 11.
