Formulovat model | Pokus a omyl | Vyřešte model
Použijte řešič v Vynikat najít maximální průtok z uzlu S do uzlu T v nasměrované síti. Body v síti se nazývají uzly (S, A, B, C, D, E a T). Řádky v síti se nazývají oblouky (SA, SB, SC, AC atd.).
Formulovat model
Model, který budeme řešit, vypadá v Excelu následovně.
1. Formulovat to problém s maximálním průtokem, odpovězte na následující tři otázky.
A. Jaká rozhodnutí je třeba učinit? K tomuto problému potřebujeme, aby Excel našel tok v každém oblouku. Pokud je například průtok na SB 2, buňka D5 se rovná 2.
b. Jaká jsou omezení těchto rozhodnutí? Čistý průtok (Flow Out - Flow In) uzlu A, B, C, D a E by měl být roven 0. Jinými slovy, Flow Out = Flow In. Každý oblouk má také pevnou kapacitu. Průtok na každém oblouku by měl být menší než tato kapacita.
C. Jaká je celková míra výkonu těchto rozhodnutí? Celkovým měřítkem výkonu je maximální průtok, takže cílem je toto množství maximalizovat. Maximální průtok se rovná průtoku z uzlu S.
2. Aby byl model srozumitelnější, vytvořte následující pojmenované rozsahy.
| Název rozsahu | Buňky |
|---|---|
| Z | B4: B15 |
| Na | C4: C15 |
| Tok | D4: D15 |
| Kapacita | F4: F15 |
| Nabídka poptávka | K5: K9 |
| MaximumFlow | D17 |
3. Vložte následující funkce.
Vysvětlení: Funkce SUMIF vypočítávají čistý tok každého uzlu. U uzlu A první funkce SUMIF sčítá hodnoty ve sloupci Flow s „A“ ve sloupci From (Flow Out). Druhá funkce SUMIF sčítá hodnoty ve sloupci Flow s „A“ ve sloupci Do (Flow In). Maximální průtok se rovná hodnotě v buňce I4, což je průtok z uzlu S. Protože uzel A, B, C, D a E mají čistý průtok 0, průtok z uzlu S se rovná průtoku v uzlu T.
Pokus omyl
S touto formulací je snadné analyzovat jakékoli zkušební řešení.
1. Například cesta SADT s tokem 2. Cesta SCT s tokem 4. Cesta SBET s tokem 2. Tyto cesty dávají celkový tok 8.
Není nutné používat pokus a omyl. Dále popíšeme, jak Řešitel aplikace Excel lze použít k rychlému nalezení optimálního řešení.
Vyřešte model
Chcete -li najít optimální řešení, proveďte následující kroky.
1. Na kartě Data ve skupině Analyzovat klikněte na Řešitel.
Poznámka: nemůžete najít tlačítko Řešitel? Kliknutím sem načtete doplněk Řešitel.
Zadejte parametry řešiče (čtěte dále). Výsledek by měl být v souladu s následujícím obrázkem.
Máte možnost zadat názvy rozsahů nebo kliknout na buňky v tabulce.
2. Jako cíl zadejte MaximumFlow.
3. Klikněte na Max.
4. Zadejte Flow pro měnící se proměnné buňky.
5. Kliknutím na Přidat zadejte následující omezení.
6. Kliknutím na Přidat zadejte následující omezení.
7. Zaškrtněte políčko „Vytvořit neomezené proměnné jako záporné“ a vyberte „Jednostranné LP“.
8. Nakonec klikněte na Vyřešit.
Výsledek:
Optimální řešení:
Závěr: cesta SADT s tokem 2. Cesta SCT s tokem 4. Cesta SBET s tokem 2. Cesta SCET s tokem 2. Cesta SACET s tokem 1. Cesta SACDT s průtokem 1. Tyto cesty dávají maximální průtok 12.
