300 Pavyzdžių

Trumpiausio kelio problema

Shortest Path Problem

Suformuluokite modelį | Bandymas ir klaida | Išspręskite modelį





Naudokite sprendėją „Excel“ rasti trumpiausias kelias iš mazgo S į mazgą T nukreiptame tinkle. Taškai tinkle vadinami mazgais (S, A, B, C, D, E ir T). Tinklo linijos vadinamos lankais (SA, SB, SC, AC ir kt.).

Suformuluokite modelį

Modelis, kurį ketiname išspręsti, „Excel“ atrodo taip.





Trumpiausia kelio problema „Excel“

„Excel“ formulę padidinti procentais

1. Suformuluoti tai trumpiausio kelio problema , atsakykite į šiuos tris klausimus.



a. Kokie sprendimai turi būti priimti? Norėdami išspręsti šią problemą, mums reikia „Excel“, kad sužinotume, ar lankas eina trumpiausiu keliu, ar ne (taip = 1, ne = 0). Pavyzdžiui, jei SB yra trumpiausio kelio dalis, ląstelė F5 yra lygi 1. Jei ne, ląstelė F5 lygi 0.

b. Kokie yra šių sprendimų apribojimai? Kiekvieno mazgo grynasis srautas (išėjimas - srautas) turi būti lygus pasiūlai/paklausai. S mazgas S turi turėti tik vieną išeinantį lanką (grynasis srautas = 1). T mazgas turi turėti tik vieną įeinantį lanką (grynasis srautas = -1). Visuose kituose mazguose turi būti vienas išeinantis lankas ir vienas įeinantis lankas, jei mazgas eina trumpiausiu keliu (grynasis srautas = 0) arba nėra srauto (grynasis srautas = 0).

c. Koks yra bendras šių sprendimų rezultatų matas? Bendras našumo matas yra bendras trumpiausio kelio atstumas, todėl tikslas yra sumažinti šį kiekį.

2. Kad modelį būtų lengviau suprasti, sukurkite šį pavadinti diapazonai .

Diapazono pavadinimas Ląstelės
Nuo B4: B21
Į C4: C21
Atstumas D4: D21
Eik F4: F21
„NetFlow“ I4: I10
Tiekimo paklausa K4: K10
TotalDistance F23

3. Įdėkite šias funkcijas.

Įterpti funkcijas

Paaiškinimas: SUMIF funkcijos apskaičiuoja kiekvieno mazgo grynąjį srautą. S mazgo funkcija SUMIF funkcija sumuoja stulpelyje „Eiti“ esančias vertes, o „S“ stulpelyje „Nuo“. Dėl to tik langelis F4, F5 arba F6 gali būti 1 (vienas išeinantis lankas). T mazgo funkcija SUMIF funkcija apibendrina stulpelio Eiti reikšmes, o stulpelyje „Kam“ nurodo „T“. Dėl to tik langelis F15, F18 arba F21 gali būti 1 (vienas įeinantis lankas). Visų kitų mazgų atveju „Excel“ ieško stulpelio „Nuo“ ir „Kam“. Bendras atstumas lygus suminis produktas iš „Distance and Go“.

Bandymas ir klaida

Naudojant šią formuluotę tampa lengva išanalizuoti bet kokį bandomąjį sprendimą.

1. Pavyzdžiui, kelio SBET bendras atstumas yra 16.

Bandomasis sprendimas

Nebūtina naudoti bandymų ir klaidų. Toliau aprašysime, kaip „Excel“ sprendėjas galima greitai rasti optimalų sprendimą.

Išspręskite modelį

Norėdami rasti optimalų sprendimą, atlikite šiuos veiksmus.

1. Skirtuko Duomenys grupėje Analizuoti spustelėkite Sprendėjas.

Spustelėkite Sprendėjas

Pastaba: nerandate „Solver“ mygtuko? Spustelėkite čia norėdami įkelti Sprendėjo priedas .

Įveskite sprendėjo parametrus (skaitykite toliau). Rezultatas turėtų atitikti žemiau pateiktą paveikslėlį.

formulė pašalinti tekstą

Sprendimo parametrai

Galite pasirinkti įvesti diapazonų pavadinimus arba spustelėti skaičiuoklės langelius.

2. Tikslui įveskite TotalDistance.

3. Spustelėkite Min.

4. Įveskite „Go“, kad pakeistumėte kintamas ląsteles.

kaip palyginti stulpelį

5. Spustelėkite Pridėti, kad įvestumėte šį apribojimą.

Grynojo srauto apribojimas

6. Pažymėkite „Padaryti nevaržomus kintamuosius kaip neigiamus“ ir pasirinkite „Simplex LP“.

7. Galiausiai spustelėkite „Išspręsti“.

Rezultatas:

Sprendėjų rezultatai

Optimalus sprendimas:

Trumpiausio kelio problemos rezultatas

Išvada: SADCT yra trumpiausias kelias, kurio bendras atstumas yra 11.

4/7 baigtas! Sužinokite daug daugiau apie sprendėją>
Eiti į kitą skyrių: Analizės įrankių paketas



^