Formulovať model | Pokus a omyl | Vyriešte model
Použite riešič v Excel nájsť maximálny prietok z uzla S do uzla T v smerovanej 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 s maximálnym prietokom, odpovedzte na nasledujúce tri otázky.
a. Aké rozhodnutia treba urobiť? Na tento problém potrebujeme program Excel, aby našiel tok v každom oblúku. Ak je napríklad tok na SB 2, bunka D5 sa rovná 2.
b. Aké sú obmedzenia týchto rozhodnutí? Čistý prietok (Flow Out - Flow In) uzla A, B, C, D a E by mal byť rovný 0. Inými slovami, Flow Out = Flow In. Každý oblúk má tiež pevnú kapacitu. Prietok v každom oblúku by mal byť menší ako táto kapacita.
c. Aká je celková miera výkonnosti týchto rozhodnutí? Celková miera výkonu je maximálny prietok, takže cieľom je maximalizovať toto množstvo. Maximálny prietok sa rovná prietoku z uzla S.
2. Aby bol model zrozumiteľnejší, vytvorte nasledujúce pomenované rozsahy.
| Názov rozsahu | Bunky |
|---|---|
| Od | B4: B15 |
| Komu | C4: C15 |
| Prietok | D4: D15 |
| Kapacita | F4: F15 |
| Dodávka Dopyt | K5: K9 |
| MaximumFlow | D17 |
3. Vložte nasledujúce funkcie.
Vysvetlenie: Funkcie SUMIF vypočítavajú čistý tok každého uzla. Pre uzol A prvá funkcia SUMIF sčíta hodnoty v stĺpci Flow s „A“ v stĺpci From (Flow Out). Druhá funkcia SUMIF sčítava hodnoty v stĺpci Tok s „A“ v stĺpci Do (Prietok). Maximálny prietok sa rovná hodnote v bunke I4, čo je tok z uzla S. Pretože uzol A, B, C, D a E majú čistý tok 0, prietok z uzla S sa bude rovnať prietoku v uzle T.
Pokus a omyl
S touto formuláciou je ľahké analyzovať akékoľvek skúšobné riešenie.
1. Napríklad cesta SADT s tokom 2. Cesta SCT s tokom 4. Cesta SBET s tokom 2. Tieto cesty poskytujú celkový tok 8.
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 MaximumFlow.
3. Kliknite na položku Max.
4. Zadajte tok pre meniace sa variabilné bunky.
5. Kliknutím na položku Pridať zadajte nasledujúce obmedzenie.
6. Kliknutím na položku Pridať zadajte nasledujúce obmedzenie.
7. Začiarknite políčko „Nastaviť neviazané premenné ako záporné“ a vyberte možnosť „Simplex LP“.
8. Nakoniec kliknite na položku Vyriešiť.
Výsledok:
Optimálne riešenie:
Záver: cesta SADT s tokom 2. Cesta SCT s tokom 4. Cesta SBET s tokom 2. Cesta SCET s tokom 2. Cesta SACET s tokom 1. Cesta SACDT s prietokom 1. Tieto cesty poskytujú maximálny prietok 12.
