Úkolem obchodníka je klasický optimalizační úkol, který vyžaduje najít nejkratší cestu, která prochází všemi danými body a vrací se do výchozího bodu. Řešení tohoto úkolu může být užitečné v mnoha oblastech, včetně logistiky, dopravního plánování a optimalizace tras.
V tomto článku se podíváme na to, jak používat program Excel k řešení úlohy obchodníka. Excel poskytuje sadu nástrojů a funkcí, které nám umožňují nastavit matici vzdáleností mezi body, určit počáteční řešení a provést iterační proces pro zlepšení nalezené cesty.
Pro začátek budeme potřebovat seznam bodů, kterými by naše trasa měla projít. Každý bod musí mít jedinečný identifikátor, například název města nebo číslo ulice. V Excelu můžeme vytvořit tabulku, kde každý řádek bude odpovídat jednomu bodu a každý sloupec bude obsahovat informace o něm, jako je název a souřadnice. Pro pohodlí lze body očíslovat v pořadí.
Poté je nutné vyplnit matici vzdáleností mezi body. To lze provést pomocí vzorců nebo ručně, v závislosti na počtu bodů. Pokud jsou vzdálenosti mezi body známé, můžete je vyplnit přímo do matice. V opačném případě mohou být vyžadovány další výpočty nebo použití externích datových zdrojů.
Jakmile je matice vzdáleností naplněna, můžeme se pustit do krok za krokem řešení úkolu obchodníka. V Excelu to lze provést iteračními funkcemi, jako je" MIN "a" VLOOKUP", které vám umožní najít nejmenší vzdálenost a odpovídající bod pro každý krok. Dále je třeba aktualizovat celkovou vzdálenost trasy a proces opakovat pro zbývající body.
Je důležité si uvědomit, že Excel je výkonným nástrojem pro řešení optimalizačních problémů, ale v případě úlohy obchodníka, zejména s velkým počtem bodů, může vyžadovat značné množství iterací a času, aby bylo dosaženo optimálního řešení.
Krok 1: Příprava dat
Než začnete řešit problém obchodníka v Excelu, musíte si připravit data. K tomu je třeba do tabulky vložit všechny potřebné parametry a hodnoty.
Nejprve si zjistěte seznam všech měst, která chcete navštívit. Zapište jejich názvy do jednoho sloupce. Města jsou obvykle označena písmeny nebo čísly. V tomto případě možná budete muset vytvořit sloupec s písmeny měst.
Dále je třeba vytvořit matici vzdáleností mezi městy. V každé buňce tabulky by měla být vzdálenost mezi příslušnými městy. Obvykle se vzdálenosti měří v kilometrech nebo mílích. Každá buňka tabulky musí obsahovat číselnou hodnotu vzdálenosti.
Všimněte si, že matice vzdáleností by měla být symetrická, to znamená, že vzdálenost od města a do města B by se měla rovnat vzdálenosti od města B do města a.pokud tomu tak není, musíte zkontrolovat data a opravit chybu.
Po vyplnění tabulky s daty by měla být tabulka uložena ve formátu .xlsx nebo .csv, abyste jej mohli použít v Excelu k vyřešení úlohy obchodníka.
Nyní, když jsou data připravena, je možné začít řešit úkol obchodníka.
Přehled údajů a úkolů obchodníka
Úkol obchodníka patří do třídy NP-obtížných úkolů a jeho hlavním cílem je najít optimální trasu po dané sadě měst, která navštíví všechna města přesně jednou a poté se vrátí do původního města. Zároveň je nutné minimalizovat celkové náklady na cestu (např. čas, vzdálenost nebo náklady).
V kontextu řešení úlohy obchodníka s Excelem jsou data obvykle prezentována jako matice, kde každý prvek označuje hodnotu (nebo vzdálenost) cesty mezi oběma městy. Pokud máme například 5 měst, matice bude mít rozměr 5x5 a každá položka bude obsahovat informace o nákladech na cestu mezi příslušnými městy.
Řešení úlohy obchodníka v Excelu je obvykle založeno na algoritmu plného přerušení, který zkontroluje všechny možné kombinace tras a vybere nejnižší náklady. Tento přístup však může být extrémně náročný na zdroje ve velkém počtu měst, takže pro optimalizaci použití aplikace Excel se doporučuje použít složitější algoritmy, jako je metoda větví a hranic nebo dynamické programování.
Je důležité si uvědomit, že Excel poskytuje různé funkce a nástroje, které mohou být užitečné při řešení úlohy obchodníka. Například funkce SUM, INDEX, MATCH, IF atd. Lze použít k výpočtu nákladů na cestu a optimalizaci trasy. Nástroj Solver navíc umožňuje automaticky najít optimální řešení úlohy na základě daných podmínek.
Krok 2: Vytvoření tabulky v Excelu
Než začnete řešit problém obchodníka, musíte vytvořit tabulku v programu Excel, kde se odrážejí počáteční data. Postupujte podle pokynů:
- Otevřete program Excel a vytvořte nový dokument.
- Do prvního řádku tabulky zadejte názvy sloupců. Obvykle jsou to "Města"a " vzdálenosti".
- V následujících řádcích zadejte názvy měst do prvního sloupce.
- Ve druhém sloupci zadejte vzdálenosti mezi každým párem měst. Vzdálenosti mohou být již známé nebo je třeba je spočítat.
- Ujistěte se, že jsou všechna data v tabulce zapsána správně a ve správném pořadí.
- Volitelně můžete na tabulku použít formátování, aby byla lépe čitelná.
Po dokončení dat tohoto kroku budete připraveni na další kroky řešení úlohy obchodníka pomocí aplikace Excel.
Vezměte v úvahu, že vytvořená tabulka bude použita jako základ pro výpočty a měla by být správně uspořádána. Zkontrolujte, zda jsou data správná, abyste získali spolehlivé výsledky.
Pokračujeme v dalším kroku.
Zadávání dat a formátování tabulky
Než začnete řešit problém obchodníka s aplikacemi Excel, musíte zadat data a správně naformátovat tabulku.
1. Vytvořte nový dokument v Excelu.
2. Zadejte názvy měst do prvního řádku tabulky.
3. Zadejte vzdálenosti mezi městy do příslušných buněk.
- Vzdálenosti lze zadat jak jako čísla, tak jako vzorce.
- Pokud vzdálenost mezi městy není známa, můžete zadat "-" nebo 0.
4. Zvýrazněte tabulku a vyberte požadované formátování:
- Změna písma a velikosti textu.
- Nastavení hranic pro buňky.
- Zvýraznění barvy pozadí pro buňky.
5. Zamyslete se nad tím, jaké informace mohou být také užitečné pro řešení úlohy obchodníka, a přidejte potřebné sloupce nebo řádky. Například sloupec s čísly měst nebo řádek s celkovým počtem vzdáleností.
Po zadání dat a formátování tabulky jsme připraveni přejít k řešení úlohy obchodníka v Excelu.
Krok 3: výpočet optimální trasy
Po vytvoření matice vzdáleností a nastavení vzorců můžeme začít vypočítávat optimální trasu obchodního cestujícího. K tomu použijeme algoritmus řešení problému obchodníka známého jako"nejbližší soused".
Algoritmus "nejbližšího souseda" lze představit jako následující kroky:
1. Vyberte libovolný startovní bod.
2. Najděte nejbližší bod k aktuální pozici.
3. Přesuňte se na nalezený bod a přidejte jej k trase.
4. Opakujte kroky 2 a 3, dokud nebudou všechny body navštíveny.
5. Zpět na původní místo dokončením trasy.
V Excelu lze tento algoritmus implementovat pomocí vzorců a funkcí.
Vytvořte nový sloupec "itinerář" a zadejte vzorec pro výpočet optimální trasy:
Poté tento vzorec natáhněte dolů, aby automaticky vyplnil všechny buňky ve sloupci itinerář.
Po dokončení výpočtů bude v buňce obsahující hodnotu " 1 " uveden výchozí bod. Výsledkem je, že celá trasa obchodního dopravce bude zobrazena ve sloupci "itinerář".