2-Amaliy mashg’ulot Mavzu: Eng qisqa yo‘l tarmog‘ini aniqlash. Mashg’ulotning maqsadi: Yuk jo’natuvchi va qabul qiluvchi punktlar orasidagi eng qisqa yo’l tarmog’ini aniqlash ko’nikmalarini hosil qilish Reja

2-Amaliy mashg’ulot
Mavzu:Eng qisqa yo‘l tarmog‘ini aniqlash.


Mashg’ulotning maqsadi: Yuk jo’natuvchi va qabul qiluvchi punktlar orasidagi eng qisqa yo’l tarmog’ini aniqlash ko’nikmalarini hosil qilish
Reja:
1. Eng qisqa yo’l tarmog’ini aniqlash masalasining asosiy tushunchalari.
2. Yuk jo’natuvchi va qabul qiluvchi punktlarni bog’lovchi eng qisqa yo’l tarmog’ini aniqlash.
Ishni bajarish tartibi:
1. Eng qisqa yo’l tarmog’ini aniqlash masalasining asosiy tushunchalari.
Vazifa: Eng qisqa yo’l tarmog’ini aniqlash masalasining asosiy tushunchalari haqida blits-so’rov.
2. Yuk jo’natuvchi va qabul qiluvchi punktlarni bog’lovchi eng qisqa yo’l tarmog’ini aniqlash.
Eng qisqa yo’l tarmog’ini aniqlashning bir necha usullari mavjud.
Ulardan eng keng tarqalganlari sifatida
1) potentsiallar,
2) “supurgi” va
3) dinamik dasturlashtirish usullarini ko’rsatish mumkin. Quyida biz potentsiallar usulida eng qisqa bog’lovchi yo’l tarmog’ini aniqlaymiz.
Potentsiallar usuli. Masalaning qo’yilishi quyidagicha shakllanadi:
Transport tarmog’i berilgan. Transport tarmog’i manzillari uning cho’qqilaridan iborat bo’lib, 0 dan boshlab oshib boruvchi tartibda rim raqamlari bilan belgilangan. CHo’qqilar orasidagi masofa (yoki xarajatlar hajmi), ya’ni tarmoq zvenolari va ularning uzunligi(masofa yoki xarajatlar birligida) berilgan.
1. Tarmoqning boshlang’ich manzili(cho’qqisi), ya’ni qaysi cho’qqidan boshlab eng qisqa yo’lni aniqlash lozimligi belgilanadi . Boshlang’ich cho’qqini 1 raqami bilan belgilaymiz va uning potentsiali Vi gaVi=V1=0 qiymat beramiz.
2. i=1 raqamli cho’qqidan chiquvchi zvenolar, ular tutashgan va potentsiali hali aniqlanmagan keyingi cho’qqilar potentsiallarini quyidagi ifoda yordamida aniqlaymiz:
V_j=V_i+S_ij
bu yerda: S_ij – (i-j) – zvenoning uzunligi(yoki xarajatdorligi), ya’ni i va j cho’qqilar orasidagi masofa.
Quyida berilgan tarmoq uchun potentsiaalarni aniqlash A punktidan boshlanadi. Unga V_A = 0 potentsial beramiz.

Keyingi bosqichlarda navbati bilan 1 dan 10 gacha punktlar ko’rib chiqiladi va jadval to’ldiriladi.

Eng qisqa yo’l tarmog’i

Bilimlarni mustahkamlash savollari:

1. Eng qisqa yo’l tarmog’ini aniqlashning zarurati nimadan iborat ?

2. Transport tarmog’i cho’qqisi deganda nimani tushunasiz ?
3. Yuk oqimlari qanday optimallashtiriladi?
4. Optimallashtirish qanday bosqichlardan iborat?
5. Potentsial usulining mohiyatini tushuntirib bering.