Hamiltono ciklai: UAB "Baldeks"

UAB „Baldeks“ – įmonė gaminanti virtuvės baldus. Įmonė yra įkūrusi penkis filialus Lietuvos didžiuosiuose miestuose, centrinis filialas ir gamykla įkurta Šiauliuose.
Įmonė yra pakankamai jauna ir norint konkuruoti šioje rinkoje, reikia dirbti kuo efektyviau ir gaminius pateikti kuo mažesnėmis kainomis. Tame tarpe mažinant produkcijos tiekimo sąnaudas, t.y. naudojant kuo mažesnes laiko bei kelio sąnaudas. Įmonės tiekėjas turi pristatyti produkciją skirtingai išsidėsčiusiuose Lietuvos miestuose: Šiauliuose, Panevėžyje, Vilniuje, Kaune ir Klaipėdoje. Reikia rasti optimalų maršrutą aplankant kiekvieną mieste esančią parduotuvę ir grižti atgal į gamyklą.
Kelių atstumai tarp įmonės teikiamų prekių parduotuvių skirtinguose miestuose pateikiami 1-oje lentelėje.
Vilnius
Kaunas
Klaipėda
Šiauliai
___
71
214
143
145
Panevėžys
71
___
128
101
226
Vilnius
214
128
___
102
312
Kaunas
143
101
102
___
212
Klaipėda
145
226
312
212
___
2. Uždavinio sprendimas
Remdamiesi atstumų lentele, sudaromas projekto orgrafas (1 pav.).
Naudojami sutrumpinimai: S – Šiauliai, P – Panevėžys, V – Vilnius, K – Kaunas, L – Klaipėda.
1 pav. Svorinis grafas.
2.1. Pigiausios jungties algoritmas
Grafe pažymima pigiausia briauna (nuo bet kurios vietos). Taip pat pažymima kita trumpiausia briauna, taip aplankomas kiekvienas miestas po vieną sykį. Gaunamas Hamiltono ciklas (gautas ciklas perrašomas nuo namų viršūnės):
SPLVKS = SP+PL+LV+VK+KS = 71+226+312+102+143 = 854
2 pav. Pigiausios jungties algoritmo svorinis grafas
2.2. Artimiausio kaimyno algoritmas
Grafe pažymima pigiausia briauna, pradedama nuo namų – Šiaulių, toliau pažymima kita pigiausia briauna. Tai daroma kol bus aplankytas kiekvienas miestas po vieną sykį. Gaunamas Hamiltono ciklas:
SPKVLS = SP+PK+KV+VL+LS = 71+101+102+312+145 = 731
3 pav. Artimiausio kaimyno algoritmo svorinis grafas.
2.3. Kartotinis artimiausio kaimyno algoritmas
Pasirenkama bet kokia viršūnė ir taikomas artimiausio kaimyno algoritmas su pradiniu tašku pasirinktoje viršūnėje. Atliekame tokius veiksmus su visomis grafo viršūnėmis. Iš visų gautų Hamiltono ciklų išsirenkamas mažiausios kainos sprendinys, jis perrašomas pradiniu tašku pasirinkus namų viršūnę (2 lentelė).
Žemiau pateikti (4-8 pav.) kartotinio artimiausio kaimyno algoritmo svoriniai grafai.
2 lentelė
4 pav. Ciklas, sudarytas nuo S viršūnės. SPKVLS.
5 pav. Ciklas, sudarytas nuo P viršūnės. SPLVKS.
6 pav. Ciklas, sudarytas nuo V viršūnės. SPKVLS.
7 pav. Ciklas, sudarytas nuo K viršūnės. SPKVLS.
8 pav. Ciklas, sudarytas nuo L viršūnės. SPKVLS.
2.4. Jėgos algoritmas
Remiantis jėgos algoritmu randami visi įmanomi...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!