Formulovať model | Pokus a omyl | Vyriešte model
Použite riešič v Excel nájsť najkratšia cesta z uzla S do uzla T v neorientovanej sieti. Body v sieti sa nazývajú uzly (S, A, B, C, D, E a T). Riadky v sieti sa nazývajú oblúky (SA, SB, SC, AC atď.).
Formulovať model
Model, ktorý ideme riešiť, vyzerá v Exceli nasledovne.
1. Formulovať to problém najkratšej cesty, odpovedzte na nasledujúce tri otázky.
a. Aké rozhodnutia treba urobiť? Na tento problém potrebujeme, aby Excel zistil, či je oblúk na najkratšej ceste alebo nie (Áno = 1, Nie = 0). Ak je napríklad SB súčasťou najkratšej cesty, bunka F5 sa rovná 1. Ak nie, bunka F5 sa rovná 0.
b. Aké sú obmedzenia týchto rozhodnutí? Čistý tok (Flow Out - Flow In) každého uzla by sa mal rovnať ponuke/dopytu. Uzol S by mal mať iba jeden odchádzajúci oblúk (čistý tok = 1). Uzol T by mal mať iba jeden prichádzajúci oblúk (čistý tok = -1). Všetky ostatné uzly by mali mať jeden odchádzajúci oblúk a jeden prichádzajúci oblúk, ak je uzol na najkratšej ceste (čistý tok = 0) alebo žiadny tok (čistý tok = 0).
c. Aká je celková miera výkonnosti týchto rozhodnutí? Celková miera výkonu je celková vzdialenosť najkratšej cesty, takže cieľom je minimalizovať toto množstvo.
2. Aby bol model zrozumiteľnejší, vytvorte nasledujúce pomenované rozsahy.
| Názov rozsahu | Bunky |
|---|---|
| Od | B4: B21 |
| Komu | C4: C21 |
| Vzdialenosť | D4: D21 |
| Choď | F4: F21 |
| NetFlow | I4: I10 |
| Dodávka Dopyt | K4: K10 |
| Celková vzdialenosť | F23 |
3. Vložte nasledujúce funkcie.
Vysvetlenie: Funkcie SUMIF vypočítavajú čistý tok každého uzla. V prípade uzla S funkcia SUMIF sčíta hodnoty v stĺpci Prejsť so „S“ v stĺpci Od. Výsledkom je, že 1 bunka F4, F5 alebo F6 môže byť 1 (jeden odchádzajúci oblúk). V prípade uzla T funkcia SUMIF sčíta hodnoty v stĺpci Ísť s písmenom „T“ v stĺpci Do. V dôsledku toho môže byť 1 bunka F15, F18 alebo F21 iba 1 (jeden prichádzajúci oblúk). U všetkých ostatných uzlov vyzerá Excel v stĺpci Od a Do. Celková vzdialenosť sa rovná súčtu vzdialenosti a vzdialenosti.
Pokus a omyl
S touto formuláciou je ľahké analyzovať akékoľvek skúšobné riešenie.
1. Cesta SBET má napríklad celkovú vzdialenosť 16.
Nie je potrebné používať pokus a omyl. Ďalej popíšeme, ako Riešiteľ Excelu možno použiť na rýchle nájdenie optimálneho riešenia.
Vyriešte model
Ak chcete nájsť optimálne riešenie, vykonajte nasledujúce kroky.
1. Na karte Údaje v skupine Analyzovať kliknite na položku Riešiteľ.
Poznámka: Nemôžete nájsť tlačidlo Riešiteľ? Kliknutím sem načítate doplnok Riešiteľ.
Zadajte parametre riešiteľa (čítajte ďalej). Výsledok by mal byť v súlade s nasledujúcim obrázkom.
Na výber máte napísanie názvov rozsahov alebo kliknutie na bunky v tabuľke.
2. Ako cieľ zadajte TotalDistance.
3. Kliknite na položku Min.
4. Zadajte Choďte na zmenu variabilných buniek.
5. Kliknutím na položku Pridať zadajte nasledujúce obmedzenie.
6. Začiarknite políčko „Nastaviť neviazané premenné ako záporné“ a vyberte možnosť „Simplex LP“.
7. Nakoniec kliknite na položku Vyriešiť.
Výsledok:
Optimálne riešenie:
Záver: SADCT je najkratšia cesta s celkovou vzdialenosťou 11.
