Formulovat model | Pokus a omyl | Vyřešte model
Použijte řešič v Vynikat najít nejkratší cesta z uzlu S do uzlu T v neorientované 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 nejkratší cesty, 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 zjistil, zda je oblouk na nejkratší cestě nebo ne (Ano = 1, Ne = 0). Pokud je například SB součástí nejkratší cesty, buňka F5 se rovná 1. Pokud ne, buňka F5 se rovná 0.
b. Jaká jsou omezení těchto rozhodnutí? Čistý tok (Flow Out - Flow In) každého uzlu by měl být stejný jako nabídka/poptávka. Uzel S by měl mít pouze jeden odchozí oblouk (čistý tok = 1). Uzel T by měl mít pouze jeden příchozí oblouk (čistý tok = -1). Všechny ostatní uzly by měly mít jeden odchozí oblouk a jeden příchozí oblouk, pokud je uzel na nejkratší cestě (čistý tok = 0) nebo žádný tok (čistý tok = 0).
C. Jaká je celková míra výkonu těchto rozhodnutí? Celková míra výkonu je celková vzdálenost nejkratší cesty, takže cílem je toto množství minimalizovat.
2. Aby byl model srozumitelnější, vytvořte následující pojmenované rozsahy.
| Název rozsahu | Buňky |
|---|---|
| Z | B4: B21 |
| Na | C4: C21 |
| Vzdálenost | D4: D21 |
| Jít | F4: F21 |
| Síťový tok | I4: I10 |
| Nabídka poptávka | K4: K10 |
| Celková vzdálenost | F23 |
3. Vložte následující funkce.
Vysvětlení: Funkce SUMIF vypočítávají čistý tok každého uzlu. U uzlu S funkce SUMIF sčítá hodnoty ve sloupci Přejít se „S“ ve sloupci Od. Výsledkem je, že pouze buňka F4, F5 nebo F6 může být 1 (jeden odchozí oblouk). U uzlu T funkce SUMIF sčítá hodnoty ve sloupci Přejít s „T“ ve sloupci Komu. Výsledkem je, že pouze buňka F15, F18 nebo F21 může být 1 (jeden příchozí oblouk). U všech ostatních uzlů vypadá Excel ve sloupci Od a Do. Celková vzdálenost se rovná součtu vzdálenosti a vzdálenosti.
Pokus omyl
S touto formulací je snadné analyzovat jakékoli zkušební řešení.
1. Například cesta SBET má celkovou vzdálenost 16.
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 TotalDistance.
3. Klikněte na Min.
4. Zadejte Přejít na změnu proměnných buněk.
5. Kliknutím na Přidat zadejte následující omezení.
6. Zaškrtněte políčko „Vytvořit neomezené proměnné jako záporné“ a vyberte „Jednostranné LP“.
7. Nakonec klikněte na Vyřešit.
Výsledek:
Optimální řešení:
Závěr: SADCT je nejkratší cesta s celkovou vzdáleností 11.
