Oblikujte model | Poskus in napaka | Rešite model
Rešitelj uporabite v Excel da bi našli najkrajša pot od vozlišča S do vozlišča T v neusmerjenem omrežju. Točke v omrežju se imenujejo vozlišča (S, A, B, C, D, E in T). Linije v omrežju se imenujejo loki (SA, SB, SC, AC itd.).
Oblikujte model
Model, ki ga bomo rešili, je v Excelu naslednji.
1. To formulirati problem najkrajše poti, odgovorite na naslednja tri vprašanja.
a. Kakšne odločitve je treba sprejeti? Za to težavo potrebujemo Excel, da ugotovimo, ali je lok na najkrajši poti ali ne (Da = 1, Ne = 0). Na primer, če je SB del najkrajše poti, je celica F5 enaka 1. Če ni, je celica F5 enaka 0.
b. Kakšne so omejitve pri teh odločitvah? Neto tok (Flow Out - Flow In) vsakega vozlišča mora biti enak ponudbi/povpraševanju. Vozlišče S bi moralo imeti samo en odhodni lok (neto pretok = 1). Vozlišče T bi moralo imeti samo en vhodni lok (neto pretok = -1). Vsa druga vozlišča morajo imeti en odhodni lok in en vhodni lok, če je vozlišče na najkrajši poti (neto pretok = 0) ali brez pretoka (neto pretok = 0).
c. Kakšno je splošno merilo uspešnosti teh odločitev? Splošno merilo uspešnosti je skupna razdalja najkrajše poti, zato je cilj zmanjšati to količino.
2. Za lažje razumevanje modela ustvarite naslednje imenovane obsege.
| Ime obsega | Celice |
|---|---|
| Od | B4: B21 |
| Za | C4: C21 |
| Razdalja | D4: D21 |
| Pojdi | F4: F21 |
| NetFlow | I4: I10 |
| SupplyDemand | K4: K10 |
| TotalDistance | F23 |
3. Vstavite naslednje funkcije.
Pojasnilo: Funkcije SUMIF izračunajo neto tok vsakega vozlišča. Za vozlišče S funkcija SUMIF sešteje vrednosti v stolpcu Pojdi z "S" v stolpcu Od. Posledično je lahko samo celica F4, F5 ali F6 1 (en odhajajoči lok). Za vozlišče T funkcija SUMIF sešteje vrednosti v stolpcu Pojdi s "T" v stolpcu Za. Posledično je lahko samo celica F15, F18 ali F21 1 (en vhodni lok). Za vsa druga vozlišča Excel pogleda v stolpcu Od in Do. Skupna razdalja je enaka suproizvodu Distance and Go.
Poskušanje
S to formulacijo postane enostavno analizirati vsako poskusno rešitev.
1. Pot SBET ima na primer skupno razdaljo 16.
Uporaba poskusov in napak ni potrebna. V nadaljevanju bomo opisali, kako Excel Solver lahko uporabite za hitro iskanje optimalne rešitve.
Rešite model
Če želite poiskati optimalno rešitev, izvedite naslednje korake.
1. Na zavihku Podatki v skupini Analiza kliknite Reševalnik.
Opomba: ne najdete gumba Solver? Kliknite tukaj za nalaganje dodatka Solver.
Vnesite parametre reševalca (preberite dalje). Rezultat mora biti skladen s spodnjo sliko.
Imate možnost, da vnesete imena obsegov ali kliknete celice v preglednici.
2. Vnesite TotalDistance za cilj.
3. Kliknite Min.
4. Vnesite Pojdi za spreminjanje spremenljivih celic.
5. Kliknite Dodaj, da vnesete naslednjo omejitev.
6. Potrdite polje »Naj neomejene spremenljivke postanejo negativne« in izberite »Simplex LP«.
7. Na koncu kliknite Reši.
Rezultat:
Optimalna rešitev:
Zaključek: SADCT je najkrajša pot s skupno razdaljo 11.
