TRANSPORT LOGISTIKASIDA GRAFLAR TATBIQ ETISH
![TRANSPORT LOGISTIKASIDA GRAFLAR TATBIQ ETISH
MUNDARIJA
KIRISH……………………………………………………………… 3
1-BOB LOGISTIKA VA TRANPORT LOGISTIKASI, UNING
ASOSIY TUSHUNCHASI ………………………............................. 6
1 .1 Logistika haqida asosiy tushunchalar………………………………... 6
1.2 Transport logistikasi…………………………………………………. 13
1.3 Ttansport logistikasida mash’rutlarni tashkil etish…………………... 20
1.4 Graflar nazariyasi elemenlari (graf, orgraf, zanjir, mashrut, grafni
hosil qilish)
…………………………………………………………… 25
2-BOB TRANSPORT LOGISTIKASIDA GRAFLARNI TATBIQ
ETISH……………………………………………………………….. 30
2.1 Grafni hosil qilish.…………………………………………………… 30
2.2 Graf mashrutlarni hosil qilish. ............................................................. 36
2.3 Eng qisqa mashrutni aniqlash……………………………………….. 41
2.4 Graflar ustida amallar bajarish dasturiy ta’minoti…………………... 50
Xulosa……………………………………………………………….. 55
Foydalanilgan adabiyotlar.………………..……………………….. 56
Ilovalar
1](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_1.png)
![Kirish
Masalaning qo‘yilishi. Transport logistikasida graflar tatbiq etish va
daromad olish masalalarini tadqiq qilish va graflar ustida amallarni bajarish uchun
qulay interfeysga ega bo‘lgan dasturiy ta‘minot yaratish.
Mavzuning dolzarbligi. Jamiyatning barcha sohalarida transport
logistikasini optimallashtirish muhum masala hisoblanadi. Ayniqsa bugungi kunda
rivojlanayorgan, shiddat bilan sanoatlashayotgan jamiyatda, tabiiy holda
raqobatning kuchayishi ortidan transport logistikasini optimal rejalashtirish va
optimal daromad olish eng dolzarb masalalardan biri bo‘lib qolmoqda.
Transport logistikasini optimallashtirish masalalari nazariy jihatdan, ya’ni
ularning matematik modellarini yaratish ularni yechish va hakozolar, birmuncha
yaxshiroq o‘rganilgan bo‘lishiga qaramay amaliy jihatda o‘rganishga yetarlicha
ishlar mavjud bo‘lib bulardan biri bu nazariy tomondan yaratilgan modellar uchun
dasturiy ta’minot yaratish.
Shuning uchun bu ishda transport logistikasini samarali rejalashtirish va
daromad olish masalalari uchun dasturiy taminot yaratish masalasi qaraladi.
Ishning maqsad va vazifalari. Bitiruv malakaviy ishning asosiy maqsad va
vazifasi bu tranport logistikasida graflar nazariyasini qullagan holda logistik
joylashuv va boshqa parametrlariga ko‘ra transport logistikasidan eng samarali
foydalanish yullarini aniqlash.
Ilmiy-tatqiqot usullari. Ushbu bitiruv malakaviy ishida transport
logistikasida graflarni tatbiq etish orqali ransport logistikasidan eng samarali
foydalanish yullarini aniqlash dasturlash masalasiga keladigan hollar uchun
o‘rganilgan bo‘lib bu modelni yechish uchun yaratilgan dasturiy ta’minot graflar
nazariyasiga asoslangan.
Mavzuning o‘rganilish darajasi. T ransport logistikasida graflarni tatbiq
etish ni optimallashtirish masalasi nazariy jihatdan ko‘plab olimlar tomonida yaxshi
o‘rganilgan bo‘lib ular ushbu masalaning turli xil modellarini yaratish va ularni
yechish kabi natijalarni olishgan. Bu kabi natijalar keltirilgan ko‘plab adabiyotlar
2](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_2.png)
![mavzuni tadqiq qilishda o‘rganilgan. Mavzuning o‘rganilishi boshlang‘ch darajada
bo‘lib, bu mavzuni o‘rganish natijasida olingan natija ya’ni yaratilga dasturiy
ta’minot sodda bo‘lib u faqat bir yo‘nalishga mo‘ljallangan hisob kitoblarni
bajaradi. Bu dasturiy ta’minotni kelajakda yanada mukammallashtirish
rejalashtirilgan.
Tadqiqotning ilmiy yangiligi. Bitiruv malakaviy ishida olingan natijalar
amaliy-uslubiy xarakterga ega bo‘lib, ishda graflar nazariyasi ustida amallarni
bajarishning ga mo‘ljallangan dasturiy ta’minot yaratligan. Bu dasturiy ta’minot
JAVA dasturlash tilida yaratilgan bo‘lib, u vizuallashgan qulay interfeysga ega.
Tadqiqot predmeti va ob’yekti. Tadqiqotning predmeti “Jarayonlar
tadqiqoti”, “Transport logistikasi”, “Graflar nazariyasi”, “Matematik dasturlash” ,
“Java dasturlash tili” va shu kabi fan sohalari bo‘lib, ob’ekti ishlab chiqarishni
rejalshtirish masalalarining matematik modellaridan iborat.
Tatqiqotnig ilmiy va amaliy ahamiyati. Ishda olingan natijalar va unda
qo‘llanilgan usullardan turli iqtisodiy, ijtimoiy sohalarning ko‘pgina amaliy
masalalari, jumladan, transport logistikasida graflar nazariyasi tatbig‘i va samarali
daromad olish masalalarini tadqiq qilishda, “Jarayonlar tadqiqoti”, “Transport
logistikasi tadqiqoti”, “Transport logistikasida graflar nazariyasi tatbig‘ini
matematik modellashtirish” va shu kabi fanlarning amaliy mashg‘ulotlari o‘quv
jarayonlarida dasturiy vosita sifatida foydalanish mumkin.
Ishning tuzilishi. Ushbu ish kirish, ikki bob, xulosa, foydalanilgan
adabiyotlar ro‘yxati va ilovalardan iborat.
I bob to‘rtta paragrafdan iborat bo‘lib, unda adabyotlardan foydalanilgan
holda, bitiruv malakaviy ishiga qo‘yilgan “T ransport logistikasida graflar
nazariyasi tatbig‘i” masalasi ni tavfislash va natija olish uchun zarur bo‘lgan asosiy
tushunchalar, ta’riflar, tasdiqlar va matematik modellar keltirilgan.
II bob to‘rtta paragrafdan iborat bo‘lib, transport logistikasida graflar
nazariyasi tatbig‘ini tashkil etishda samarali reja va daromad olish masalalarining
matematik modellari haqida so‘z yuritilgan, ikkinchi paragrafda bu modellardan
foydalanilgan holda graflar ustida amallarni bajarishga asoslangan JAVA
3](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_3.png)
![dasturlash tilida qulay interfeysga ega bo‘lgan dasturiy ta’minotning funksional
sxemasi keltirilgan hamda turli masalalarni yechish orqali dasturiy ta’minotdan
foydalanuvchilar uchun ko‘rsatmalar berilgan . Uchinchi paragrafda dasturiy
ta’minotning to‘gri ishlashini tekshirish uchun bir nechta mavjud standartlashgan
dasturiy ta’minotlar bilan taqqoslashlar o‘tkazilgan.
Olingan natijalarning qisqacha mazmuni. Bitiruv malakaviy ishida
transport logistikasida graflar nazariyasi tatbig‘i masalalari va ularni yechish
uchun olingan matematik modellar bilan tanishib chiqildi hamda bu modellardan
foydalanilgan holda graflar ustida amallarni bajarishga asoslangan dasturiy
ta’minot yaratildi.
Bu dasturiy ta’minotdan foydalanib, graflar ustida ko‘plab amallarni bajarish
mumkin bo‘lib, bu masalalarni transport logistikasida qo‘llash va samarali
daromad olish masalalarining asosiy matematik modellaridan biri hisoblanadi.
Ushbu yaratilgan dasturiy ta’minot graflar nazariyasiga asoslangan. Dasturiy
ta’minot yordamida olingan yechimi transport logistikasidan foydalanishni optimal
rejalashtirish va optimal daromad olishning yechimi bo‘ladi, ya’ni maqsad
funksiyasining maksimumi optimal daromad olishga va shu funksiyani
maksimumga erishtiruvchi o‘zgaruvchilarning qiymati optimal rejalarga mos
keladi.
4](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_4.png)
![I BOB. LOGISTIKA VA TRANPORT LOGISTIKASI, UNING ASOSIY
TUSHUNCHASI
1.1 Logistika haqida asosiy tushunchalar
Logistika tushunchasi juda qadimiy tarixga ega bo‘lib, birinchi marta harbiy
fan sifatida vujudga kelgan. IX asrda Vizantiyada bu tushunchaga qo‘shinni barcha
kerakli narsalar bilan bilan o‘z vaqtida aniq ta’minlash jangning muvaffaqiyatini
belgilovchi omil deb qaralgan. Vizantiya imperiyasida «logist» mansabi joriy
etilgan boiib ular oziq-ovqat taqsimoti bilan shug‘ullanganlar.
Ispan huquqshunosi va iqtisodchisi Polo de Ondegardoning 1572-yilda xabar
berishicha ink Imperiyasi chinovniklari tomonidan ink saroyi uchun zarur bo‘lgan
oziq-ovqat miqdorining hisobi olib borilgan. Bunda ularni qayerdan tashib
keltirilishi, yetkazib kelish vaqti va tashish masofalarining hisoblari olib borilgan.
XIX asrda fransuz olimi A.G. Jomini logistikani armiya va front orqasini
boshqarish, tashishni rejalashtirish va tashkil etish bo‘yicha fan deb talqin etadi.
1850-yilda Sankt-Peterburgda chop etilgan «Harbiy ensiklopedik leksion»da
logistika deb uzoqda va dushman yaqinida qo‘shinni ko‘chirishni boshqarish,
qo‘shinni orqadan ta’minlashni tashkil etish san'ati deb tushuncha berilgan.
Ikkinchi Jahon urushi davrida Amerika armiyasida logistik yondoshuv keng
qo‘llanilgan. AQSh Ovrupoda jang qilganiga qaramay qo‘shinning ta’minoti juda
yaxshi yo‘lga qo‘yilgan edi. Katta ingliz-rus lug‘atida hozir ham logistika
tushunchasi harbiy ma’noda keltirilgan bo‘lib 1) front orqasi ta’minoti, 2)
moddiytexnik ta’minot, 3) front orqasidagi ishlami bajarish va tashkil etish
ma’nosida qo‘llaniladi.
Respublikamizda va chet ellarda chop etilayotgan iqtisodiyotga oid
adabiyotlarda logistika tushunchasi keng ma’noda qo‘llanilmoqda. Bugungi kunda
iqtisodiy tizimdagi odamlar, moliyaviy, energetik va boshqa oqimlarni
boshqarishlarga logistika fanining predmeti deb qaralyapti. Hozirda bank
5](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_5.png)
![logistikasi, axborot logistikasi, ishlab chiqarish logistikasi kabi tushunchalar paydo
bo‘ldi.
Logistikaga oid adabiyotlarni kuzatar ekanmiz, xattiharakatlarni aniq
rejalashtirish va muvofiqlashtirish zarur bo‘lgan joyda logistika atamasi
qo‘llanilayotganini ko‘ramiz.
Masalan paxta ekish kompaniyasini o‘z vaqtida, arzon va sifatli o‘tkazish
belgilangan dalaga kerakli vaqtda rejalashtirilgan chigit navini kerakli hajmda
yetkazib berish, ishchi kuchi va seyalkalar hamda traktorlami o‘z vaqtida yoqilg‘i
bilan yoki boshqa misol asfalt ishlab chiqaruvchi zavodni chaqir tosh, qum va
gudron moyi hamda m a’lum harorat bilan kerakli vaqtda va kerakli joyda
ta’minlash jarayonlarini logistikasiz tasavvur etib bo‘lmaydi.
Hozirgi kunda logistika atamasiga o‘nlab tushunchalar berilgan bo‘lib
shulardan ba’zilarini ko‘rib chiqaylik.
1. D.S. Nikolayev tahriri ostida chop etilgan «Tashqi savdo transport
operatsiyalari va logistika» o‘quv qo‘llanmamasida (M. ANXIL, 1999) logistikaga
«ta’minot masalalarini, sanoat ishlab chiqarishni, tovarlaming taqsimlanishini,
tayyor mahsulotni sotishni tashkil etishni o‘z ichiga oluvchi, ishlab chiqarish,
transport va taqsimot tizimini yondoshish orqali ratsion tashkil etish» haqidagi fan
deb ta’rif berilgan.
2. Xalqaro ekspeditor (1998, №9) jumalida: a) logistikaga Materiallar va
axborot oqimlarini va ular orasidagi aloqalami boshqarish muammolarini o‘z
ichiga oluvchi fandagi kompleks yo‘nalish, b) Tizimlarda oqimlarni boshqarish
haqidagi fan deb tushuncha berilgan.
3. O.N.Larin logistika moddiy oqimlar, resurslar, tovarlar va yo‘lovchilar
ko‘rinishidagi obyektlarning harakatini tadqiqot qilish hamda ularni bir necha
mezonlar (vaqt, tezlik, narx va masofa) bo‘yicha optimallashtirish haqidagi fan deb
ta’rif beradi.
3. Mualliflarning fikricha, prof. Sh.O.Butayev va uning shogirdlari
tomonidan chop etilgan «Logistika» kitobida «logistika» atamasiga berilgan
ta’rifni, boshqa ta’riflarni inkor etmagan holda, eng to‘liqroq ta’rif deyish mumkin:
6](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_6.png)
![Logistika - oxirgi bosqichdagi iste’molchilaming mahsulot sifatiga va
ko‘rsatiladigan xizmatlarga qo‘yadigan talablarini qondirish maqsadida moddiy va
servis hamda ularga mos keluvchi moliyaviy va axborot oqimlarini eng kam
xarajatlar bilan boshqarish haqidagi fan.
«Logistika» fanini o‘rganish samaradorligi, avvalo, jarayonlarga logistik
yondoshuvning asosiy g‘oyalarini qanday tushunishga bog‘liqdir. Logistik
yondoshuvning avvalgi an’anaviy yondoshuvlardan asosiy farqi shundaki, u har xil
xo‘jalik yurituvchi subyektlaming faoliyatini alohida emas, bir butun holda
o‘rganib, materiallami ishlab chiqarishdan tortib to iste’molchiga yetkazib
berilgunicha optimallashtirishga qaratiladi.
Logistikaning asosiy maqsadi, masalalari va tushunchalari
Logistikaning asosiy maqsadi raqobat bozorida boshqa raqobatchilardan
yaxshiroq holatda boMish va ko‘proq foyda olishni ta’minlashdir. Bu maqsadga
erishish moddiy oqimlarni boshqarish jarayonlarida quyidagi qoidalarga amal
qilishni taqozo etadi (logistikaning yetti qoidasi):
- MAHSULOT yoki OBYEKT (SUBYEKT) - zarur mahsulot, mos obyekt
(subyekt);
- SIFAT - mos keladigan sifat;
- MIQDOR - kerakli miqdorda;
- VAQT - kerakli vaqtda yetkazilishi kerak;
- JOY - kerakli joyga;
- XARAJATLAR - kam xarajatlar bilan;
- ISTE'MOLCHl - kerakli (mos) iste’molchiga.
Hozirgi paytda logistika sohasidagi nazariy va amaliy natijalarni
ommalashtirish, ulaming samaradorligini oshirish maqsadida turli mamlakatlarda
logistik tashkilotlar faoliyat ko‘rsatmoqdalar. «Ishlab chiqarish va zaxiralami
boshqarish muammolari Amerika jamiyati», «Menejment muammolari bo‘yicha
Amerika kengashi», «Logistika Vft transportlashtirish bo‘yicha Amerika
jamiyati», «Material boshqaruvi bo‘yicha Xalqaro jamiyat», «Rossiya logistika
bo‘yicha muvofiqlashtirish kengashlari» va boshqalar.
7](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_7.png)
![1990-yillarga kelib logistika fani xalq xo‘jaligining barcha Sohalarida
qo‘liana boshlandi. Hozirgi kunda logistikanig quyidagi Sohalari (yo‘nalishlari)
vujudga keldi:
- axborot logistikasi;
- xarid logistikasi; '
- ishlab chiqarish logistikasi;
- taqsimot logistikasi;
- zaxiralar logistikasi;
- omborlar logistikasi;
- transport logistikasi;
- bojxona logistikasi va boshqalar.
Axborot logistikasi . Moddiy oqimlami samarali boshqarish ntrkazida
logistik tizimda aylanib yuruvchi axborotlami qayta lihlash va ulami samarali
boshqarish yotadi.
Logistik axborot - bu logistik tizimlami boshqarish Jirayonlarini
ta’minlovchi bilimlar majmuasidir.
Logistikani axborot ta’minotining maqsadi - moddiy oqimlar bwftkatini
kompleks rejalashtirish, nazorat qilish va samarali boshqarish uchun m a’lumotlar
bilan ta’minlashdir.
Xarid logistikasi - bu korxonani moddiy resurslar: xomashyo materiallari va
tovarlar hamda butlovchi mahsulotlar bilan ta’minlash jarayonida moddiy
oqimlarni boshqarish faoliyatidir. Bu faoliyat barcha turdagi moddiy resurslarni
tashkil etish, yetkazib beruvchidan xarid qilib olish, tashib keltirish, qabul qilish,
saqlash va boshqa shunga o‘xshash ishlarni qamrab oladi.
Ishlab chiqarish logistikasi. M a’lumki moddiy oqimlar birlamchi
xomashyo manbaidan oxirga iste’molchiga zarur bo‘lgan tovar ko‘rinishida yetib
borgunicha bir qancha ishlab chiqarish zvenolaridan o ‘tadi. Bu bosqichlarda
moddiy oqimlarni boshqarish ishlab chiqarish logistikasi deb ataladi.
Ishlab chiqarish logistikasining asosiy maqsadi moddiy oqimlarni
korxonaning ishlab chiqarish uchastkalarida ishlov berib tayyor mahsulotga
8](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_8.png)
![aylanishida unga sarflanadigan xarajatlarni kamaytirish va mahsulot sifatini
ta’minlashdir.
Taqsimot logistikasi. Taqsimot logistikasi - bu moddiy oqimlarni har xil
xaridorlar o‘rtasida taqsimlash jarayonida amalga oshiriladigan kompleks
vazifalardir.
Taqsimot logistikasining asosiy maqsadi kerakli tovarlarni kerakli joyga,
kerakli vaqtda va kerakli sifatini ta’minlagan holda eng kam xarajatlar bilan
yetkazib berishdir.
Omborlar logistikasi. Omborlar logistik tizimlaming asosiy elementlaridan
biri hisoblanadi. Yetkazib berish zanjirlarida moddiy oqimlarni boshqarish
samaradorligi ombor xo‘jaligining qanday ishlashiga bogMiqdir. Ombor xo‘jaligi
mahsulot sifatining saqlanishi, ishlab chiqarish va transportning bir maromda
ishlashini, korxona maydonidan samarali foydalanishni, transport vositalarining
ortiqcha turib qolishini kamaytirish imkonini beradi.
Transport logistikasi. Birlmachi ishlab chiqaruchidan to oxirgi
iste’molchiga moddiy oqimlarni yetkazib berishda bajariladigan asosiy logistik
operatsiyalar transport vositalarinig ishtirokida amalga oshiriladi. Transportning
mahsuloti bu moddiy narsalami ishlab chiqish emas, balki iste’mllchilarga
transport xizmatini ko‘rsatishdir.
Logistika obyekti. Logistikaning asosiy obyekti bu moddiy va yo‘lovchilar
oqimi bo‘lib, ularni harakatga keltirish va boshqarish uchun yordam beradigan
axborot, moliya va shunga o‘xshash boshqa oqimlardir.
Logistikaning tamoyillari - moddiy va servis oqimlarni optimallashtirish
asosida korxonalar faoliyati samaradorligini oshirishga yo‘naltirilgan tizimli
qarashlardir. Logistika tamoyillari tizimli yondoshuv asosida amalga oshiriladi.
Logistik vazifalar (funksiyalar) - logistik tizim maqsadlarini amalga oshirishga
yo‘naltirilgan logistik operatsiyalar majmuasidir. Masalan, asfalt zavodiga
karyerdan shag‘al yetkazib berish bir qanCha bosqichlardan iborat bo‘ladi:
shag‘alni yumshatish, shag‘alni atomobillarga ortish, zavodga tashib (yetkazib)
berish operatsiyalari. Ko‘rinib turganidek, bu ishlar bir maqsadga, ya’ni zavodni
9](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_9.png)
![shag‘al bilan ta’minlab berishga qaratilgan operatsiyalardan iborat bo‘lib Ulami
bitta qilib logistik funksiyaga misol deb atash mumkin. Logistik operatsiyalar -
moddiy va axborot oqimlarini o‘zgartishiga qaratilgan alohida harakatlar majrruasi.
Masalan, shag‘alni yumshatish, avtomobilga ortish va yetkazib berishni uchta
opeTttsiyaga ajratish mumkin.
Logistika zanjiri - biron-bir moddiy yoki nomoddiy oqimlarni ishlab
chiqaruvchidan iste’molchiga yetkazib berish mumkin bo‘lgan variantlar
majmuasi.
Yuklarni bir joydan ikkinchi joyga ko‘chirishda har xil sxemalarda olib
boriladi, bitta va har xil transport turlari qatnashishi mumkin.
1-rasm. Logistika zanjiri
˗ logistik tizimlar faoliyatining har xil matematik modellarini ishlab chiqish;
˗ ta’miniash, ishlab chiqarish, tahlil qilish;
˗ tayyor raahsulotlarni sotish va jo‘natish ishlarini birgalikda hal qilishning
kompleks rejalashtirish usuilarini ishlab chiqish.
Bu masalalardan ko‘rinib turibdiki, logistikani ishlab chiqarish va muomala
sohasida moddiy oqimlarni boshqarish bo‘yicha xo‘jalik faoliyatini yo‘naltiruvchi
fan deb qarash ham mumkin ekan.
Moddiy oqimlarni logistikaning asosiy obyekti sifatida birlamchi hom
ashyodan to iste’molchiga mahsulot ko‘rinishida yetib borgunicha bo‘lgan
jarayonni ko‘rib chiqaylik (2-rasm).
10](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_10.png)
![Rasmdan ko‘rinib turganidek, moddiy oqimni shartli ravishda ikkiga bo‘lish
mumkin:
- moddiy oqimning ishlab chiqarish texnik maqsadidagi harakatlanishi;
- moddiy oqimni iste’mol buyum ko‘rinishidagi harakatlanishi.
Birinchi bosqichda material xom ashyo sifatida bir ishlab chiqaruvchidan
ikkinchisiga o‘tib borar ekan, uning tarkibi va ko‘rinishi ham o‘zgarib boradi va
oxirgi ishlab chiqarishda iste’mol qilish uchun tovar ko‘rinishiga aylanadi.
Bu yerda yana shuni ham eslatib o‘tish kerakki, har bir ishlab chiqarishning
ichida ham homashyo bir uchastkadan ikkinchisiga xom ashyo, yarim va tayyor
mahsulot ko‘rinishiga kelgunicha harakatlanadi, to‘planadi, omborda saqlanadi va
saralanadi. n-chi ishlab chiqarishda iste’mol uchun tayyor mahsulot ya’ni tovar
ko‘rinishiga kelgan mahsulot unga bo‘lgan talabga qarab iste - molchilar o‘rtasida
taqsimlanadi.
Moddiy oqimlarning yuqorida ko‘rib o‘tilgan harakatlanish sxemasini asfalt-
beton zavodi misolida ko‘rib chiqaylik.
Zavod tayyor mahsulot, ya’ni asfalt-beton qorishmasini tayyor holatga
keltirish uchun bir qancha ishlar amalga oshiriladi:
- shag‘alni tashib keltirish uchun avtotransport vositalariga buyurtma berish;
- ortish mexanizmlari va avtotransportning o‘zaro uzluksiz ishlashini tashkil
etish;
11](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_11.png)
![- shag‘al (xomashyo)ni tosh maydalash va qumni ajratib olish qurilmasiga
yetkazib berishni tashkil etish;
- qurilma uzluksiz ishlashini ta’minlash uchun m a’lum zaxirani (omborni)
yaratish;
- tosh maydalash qurilmasiga shag‘alni uzatishni tashkil etish;
- asfalt sexining uzluksiz ishlashini ta’minlash uchun gudron moyi zaxirasini
tashkil etish;
- ombordagi qum va chaqir toshlarni hamda gudron moyini asfalt tayyorlash
qurilmasiga uzatish;
- tayyor mahsulotni olish va uni sotishni (taqsimlashni tashkil etish) tashkil
etish;
- asfalt qorishmasini kerakli joyga belgilangan vaqtda va kerakli hajmda
yetkazib berish (agar zavod mahsulotlarni yetkazib berish majburiyatini
olgan bo‘lsa).
Bulardan ko‘rinib turibdiki logistika obyektiga marketolog, moliyachi,
ishlab chiqarishni rejalashtiruvchi va boshqaruvchi menejer nuqtayi nazaridan
qarash ham mumkin ekan.
1.2 Transport logistikasi
Transport logistikasida oqimlar va ularning turlari
Logistikani boshqarish va logistikani fan sifatida tadqiq qilishning obe‘kti
moddiy, axborot, moliya, servis va boshqa omillar hisoblanadi.
Oqim o‘zida bir qancha vaqt (interval) oralig`ida va aniq davr uchun
absolyut birlik bo‘lib, o‘lchanuvchi jarayon sifatida bir butun deb qabul qilinuvchi
obektlar jamligini aks ettiradi.
Oqim ko‘rsatkichlari bu yuz berayotgan jarayonlarni tavsiflovchi
ko‘rsatkichlardir.
Oqimni tavsiflovchi asosiy ko‘rsatkichlar uning boshlang`ich va oxirgi
punktlari, harakat trayektoriyasi, yo‘l uzunligi, harakat vaqti va tezligi, oraliq
12](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_12.png)
![punktlar, jadallik hisoblanadi.
Oqimlar quyidagi ko‘rsatkichlar boyicha tavsiflanadi:
Ko‘rilayotgan tizimga aloqasi bo‘yicha;
- ichki oqimlar – tizim ichida aylanuvchi;
- tashqi oqimlar – tizim tashqarisida aylanuvchi.
Uzluksizlik darajasiga ko‘ra:
- uzluksiz oqimlar – vaqtning har onida oqim trayektoriyasi bo‘yicha
obektlarning ma'lum soni joylashadi;
- diskret oqimlar – har xil vaqt oralig`ida joylashuvchi obektlardan
tashkil topadi.
Muntazamlilik darajasi bo‘yicha:
- determinallashgan oqimlar – vaqtning har bir daqiqasida
ko‘rsatkichlarning aniqligi bilan tavsiflanadi;
- stoxastik oqimlar – vaqtning har bir daqiqasida ma'lum ehtimollik
darajasi bilan aniqlangan ko‘rsatkichlarning tasodifiy tavsiflari.
Barqarorlik darajasi bo‘yicha:
- barqaror oqimlar – ma'lum vaqt oralig`idagi ahamiyatli
ko‘rsatkichlarning doimiyligi bilan xarakterlanadi;
- barqaror bo‘lmagan oqimlar – oqimlar ko‘rsatkichlarining o‘zgarishi
bilan tavsiflanadi.
O‘zgaruvchanlik darajasi bo‘yicha:
- statsionar oqimlar – o‘rnatilgan jarayon uchun xarakterli bo‘lib, ularning
jadalligi doimiy hisoblanadi;
- nostatsionar oqimlar – o‘rnatilmagan jarayon uchun xarakterli, ularning
jadalligi ma'lum davr oralig`ida o‘zgarib turadi.
Oqim elementlarining joylashish xarakteri bo‘yicha:
- teng o‘lchamli oqimlar – obektlarning joylashish tezligining doimiyligi bilan
xarakterlanadi shunindek, obektlarning boshlang`ich va oxirgi harakat
intervallari ham teng;
- notekis o‘lchamli oqimlar – joylashish tezligi o‘zgarishi bilan
13](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_13.png)
![xarakterlanadi, bunda tezlashish, sekinlashish, yo‘lda turib qolish, jo‘natish
va yetib kelish oralig`ida o‘zgarishlar bo‘ladi.
Davriylik darajasi bo‘yicha:
- davriy oqimlar – ko‘rsatkichlarning doimiyligi yoki ma'lum davrdan keyin
xarakterlar doimiyligining o‘zgarishi bilan xarakterlanadi.
Tashish darajasining chastotasiga nisbatan:
- ritmli;
- ritmsiz.
Murakkablik darajasi bo‘yicha:
- oddiy oqimlar – boshqaruv tizimi tomonidan boshqaruv ta'siriga adekvat
javob beradi;
- boshqarib bo‘lmaydigan oqimlar – boshqaruv ta'siriga javob bermaydigan
material oqimi tushunchasi logistikada birlamchi hisoblanadi.
Moddiy oqimlar transportirovkalash, omborlashtirish, va boshqa xomashyo,
yarim tayyor va tayyor mahsulotlar bilan birinchi manbaadan iste'molchigacha
bo‘ladigan operatsiyalar orqali yuzaga keladi. Moddiy oqimlari har xil korxonalar
orasidan yoki korxona ichidan ham o‘tishi mumkin.
Moddiy oqimlar harakatida korxona nazoratini tashkil etish jarayoni bir
butun o‘lchov sifatida qaraladi, ayniqsa, moddiy oqimlarning korxona ichidagi
harakati, ularni rejalashtirish va zahiralarning boshqaruvi haqida fikr yuritish
mumkin. Shuni qayd etmoq kerakki, aksariyat tadqiqotlarda korxona yoki ombor
mustaqil o‘lchov sifatida qaraladi va moddiy oqimning kirimi va chiqimi bilan
bog‘liq bo‘lgan operatsiyalarga asosiy e‘tibor qaratiladi Biroq masalaga bunday
yondoshilganda ixtiyoriy operatsiyani (yuklash,. yo‘ldagi vaqt) asosiy oqimlar
uchun zarur vaqt va opersiyalarni boshlash uchun xaqiqatda kerakli vaqt yetakchi
boshqaruv omillaridan hisoblanadi.
Iste‘molchi mahsulotni mintaqaviy ombor orqali yoki bevosita ishlab
chiqaruvchining o‘zidan olishi mumkin. Aniqki, buyurtmalarni bajarish muddati
turlichadir. Ombordan mavjud mahsulotlarni saqlash uchungina emas, balki
mahsulotlarni o‘z vaqtida yetkazib berish uchun ham foydalaniladi.
14](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_14.png)
![Buyurtmalarning o‘z vaqtida bajarilishi transport vositalari, buyurtmalarni
tayyorlash texnikalariga ham bog‘liq Tjtnk+LV nj+tgon m
1-jadval
Turli xil transportlarda yuklarni yetkazib berish muddatini hisoblashning metodik
ko‘rsatmasi .
Transport turi Yetkazib berish muddatini hisoblash
formulasi
1. Temir yo‘l
Tjtnk+LV nj+tgon m
2. Dengiz yo‘li T
mk LV
kom V
komk LV
sut + 2 LPTIM + t ; m / + don
3. Daryo Tp
k ¿ + LFV
n P + t p
; don
4. Avtomobil
Ta kTnK +LFV EK
Bu yerda:
tnk
-operatsiyaning boshlanish-tugash vaqti,
L- tashib keltirish uchun o‘tilgan masofa, km, mil.
VnjVnP
- 1 sutkada vagon yoki kemaning normadagi yo‘lda yurishi;
tptgon m
t -daryo, dengiz va temir yo‘l transportida qo‘shimcha operatsiyalar
uchun vaqt;
VEK
- foydalanish tezligi, km/soat; Vkom - Tijorat tezligi, Mil/sutka;
Vsut
-mazkur liniyada ishlovchi kemadan foydalanish tezligi mil/sutka; α -yuk
ko‘tarish mashinasidan foydalanish koeffitsiyenti;
R
t -kemaning yuk ko‘tarish quvvati, t;
M-portda bir sutkada o‘rtacha yuk tashish ishlari, t/sutka;
To -yuklarni to‘plash, rasmiylashtirish va jo‘natish vaqtlari, sutka.
Transport vositalarining ish unumiga ta’sir etuvchi asosiy logistik
ko‘rsatkichlar
Transport vositalari ish unumiga ta‘sir etuvchi asosiy logistik
ko‘rsatkichlarni baholashda,asosiy yo‘nalishlardan biri logistik xarajatlarni
minimallashtirish lozim.
Logistik harajatlar – logistik muomalalarni bajarish bilan bog‘liq bo‘lgan
15](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_15.png)
![harajatlar: materiallar uchun buyurtmalarni joylashtirish; tayyor mahsulotni
omborlarga joylash; yuklash, xuddi shuningdek harajatlarning boshqa turlari:
xodimlarga, jixozlarga, binolarga, ombordagi xazinalar, yig‘ish, buyurtmalar
haqida malumotlarni uzatish va saqlash.
C hiqi m lar – to‘ l o v ni ng s a l b iy oqi m i,‖ y a n i o b e k t ni ng to‘ l o v v o s i t a la r i n i
kamaytirish.
Qiymat – istemolchi mahsulotni olish uchun to‘laydigan mablag‘.
Mahsulotni (xizmatni) tannarxi – chiqimlarni mablag‘ ko‘rinishida
ifodalash, asosiy fondlar, xom-ashyo, materiallar, yoqilg‘i,energiyalarni ishlab
chiqarish jarayo‘nida foydalanish bilan bog‘liq.
Logistik sistemalar samaradorligi – umumiy logistik harajatlarni berilgan
darajasida logistik sistemalarni funksiyalash sifatini darajasini xarakterlaydigan
ko‘rsatkich. Istemolchi nuqtai nazaridan logistik sistemalar samaradorligi
buyurtmaga xizmat ko‘rsatish sifatini darajasini aniqlaydi.
Har qanday uskuna yoki jihozlarning ish unumi deyilganda ularning vaqt
birligida ishlab chiqargan mahsuloti tushuniladi. Avtomobillar yuklarni ma‘lum
masofaga tashib berishini hisobga olib, ularning unumi vaqt birligida tashilgan yuk
miqdori va tonna kilometrlarda o‘lchanuvchi transport ishidan iboratdir. Masalan,
avtomobilning yuk bilan bir qatnovdagi unumi:
Q qH
CT , t
bo‘lsa, tonna-kilometrda bajargan transport ishi
P Q lYUK qH
CT lYUK , tkm
iborat bo‘ladi.
Aytilganlarga ko‘ra, bir ish kuni davomida avtomobilning unumi:
QК
qH CT ZYUK , t
PК qH CT lYUK * ZYUK ,
tkm
Bunda Z
yuk – bir ish kuni davomida yukli qatnovlar soni.
O‘z navbatida nolinchi qatnovga ham sarflangan vaqtni hisobga olinsa bir
ish kuni davomida yukli qatnovlar soni.
16](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_16.png)
![ОТZ
yuk = T
ish
t
ayl
bunda T
ish – avtomobilning ishda bo‘lish vaqti, soat: t
ayl – bir to‘liq qatnov uchun
zarur vaqt, soat.
Bir to‘liq qatnov uchun zarur vaqt , avtomobilning yuk ortish punktidan uni
tushirish punktigacha yukli qatnovi vaqti , yuk tushirish punktidan navbatdagi yuk
ortish punktigacha bo‘sh qatnov vaqti hamda ortish - tushirish vaqti yig‘indisidan
iborat bo‘ladi :
t
ayl = t x
yuk + t x
bk + t
O − T soat
bunda: t
yuk - avtomobilning yukli qatnovdagi harakat vaqti; t
bk - bo‘sh
qatnovdagi harakat vaqti; t
O-T - transport vositasining yuk ortish-tushirishda turish
vaqti.
Harakat vaqtini aniqlash uchun yukli va bo‘sh qatnovlar masofasini, harakat
tezligiga bo‘lish lozim:
tX= LM
VT
= lYUK +lbk
VT
= lYUK
β∗VT
bunda: l
YUK - avtomobilning yukli qatnov masofasi, km; l
bk - bo‘sh qatnov
masofasi, km; V
T - transport vositasi texnik harakat tezligi, km/soat.
Avtomobilning yukli qatnovlar masofasi va yo‘l qatnovidan foydalanish
koeffitsiyenti ma‘lum bo‘lsa, avtomobilning harakat vaqtini yukli qatnovlar
miqdorini, uning texnik harakat tezligi (km/soat) va marshrutdagi yo‘ldan
foydalanish koeffitsiyenti ko‘paytmasiga nisbati bilan aniqlanadi:
tX= LYUK
VT∗β
, soat
Bir aylanish vaqti esa
t
ayl = l
YUK
V
T β + t
O − T = l
YUK + V
T β t
O − T
β ∗ V
T
Aylanish vaqti va avtomobilning marshrutda bo‘lish vaqti ma‘lum bo‘lsa, ish
kuni davomidagi qatnovlar miqdorini quyidagi formula bo‘yicha hisoblab topish
mumkin:
ZYUK = TISh
tayl
= TISh∗VT∗β
lYUK +β∗VT∗tO−T
17](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_17.png)
![Yukli qatnovlar sonini aniqlash formulasini bir qancha almashtirishlardan
so‘ng quyidagi ko‘rinishga keltiramiz:
Q
k = T
ISh q
H γ
CT V
T β
l
YUK + β V
T t
O − T , tRk= TISh qHγCT VTβlYUK
lYUK +βVTtO−T
, tkm
Transport vositalari bir soatlik unumdorligi quyidagi formulaga binoan
hisoblanadi:
W Q= Qk
TISh
W P= Rk
TISh
bunda: W
Q – transport vositasi birligining t/soatda o‘lchanuvchi bir soatlik
unumdorligi;
W P – transport vositasi birligining tkm/soatda o‘lchanuvchi bir
soatlik unumdorligi.
Yuqoridagi formulalarga transport vositalarining 1 kunlik unumini qo‘yilsa,
yuqoridagi formulaning ko‘rinishi:
W
Q = q
H γ
CT β V
T
l
YUK + β V
T t
O − T t/soat
W P= qHγ∂βVTlYUK
lYUK +βVTtO−T
tkm/soat
bo‘ladi.
Bu formulalarga ko‘ra avtomobil (avtopoyezd)lar unumdorligiga ta‘sir
etuvchi omillar: transport vositasi yuk ko‘tarish qobiliyati (
qH ), yuk ko‘tarish
qobiliyatidan foydalanish koeffitsiyenti ( ) , yukli qatnov masofasi (
lYUK ), yo‘ldan
foydalanish koeffitsiyenti ( ), ortish va tushurish operatsiyalarida bekor turish
vaqti (
tO−T ), avtomobilning texnik harakat tezligi ( VT ) dan iborat bo‘ladi.
Odatda avtotransport saroyida har xil tip va modeldagi transport vositalari
bo‘lib, ularning yuk ko‘taruvchanliklari hamda ish unumi har xil bo‘lgani uchun
avtotransport saroyi ro‘yxatida bor avtomobillarning bir avtomobil-tonna
quvvatiga soatlik ish unumi aniqlanadi:
18](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_18.png)
![W QIT = γCT βVT
lYUK +βVTtO−T t/soat
W PIT = γ∂βVTlYUK
lYUK +βVTtO−T
tkm/soat
formulalarni navbati bilan
βVT va βVTtO−T ga bo‘linsa formulalar kurinishi
o‘zgaradi.
W Q= qHγCT
lYUK
βVT
+tO−T
t/soat
W
P = q
H γ
∂
l
β V
T + t
O − T
l
YUK tkm/soat
W
Q 1 = γ
CT
l
YUK
β V
T + t
O − T t/soat
W
P = γ
∂
l
β V
T + t
O − T
l
YUK tkm/soat
Yuqoridagi formulalardan ko‘rinib turibdiki, logistik ko‘rsatkichlar, , , V
T ,
lyuk, to-t avtomobil saroyining umumiy yuk ko‘taruvchanligi va rejadagi davrda
ish avtomobil-soatlar miqdorini bildirgan xolda transport vositalarining va
avtotransport saroyining ish unumini hisoblash mumkin.
1.3 Ttansport logistikasida mash’rutlarni tashkil etish
Logistikada marshrutlashtirishni o‘rni
Zamonaviy iqtisodiy matematik uslublar va modellarni, hamda hisoblash
texnikasini keng qo‘llamay turib, logistik tizimni ishlab chiqish va amalga oshirish
mumkin emas. Bunday tasdiq shunga asoslanadiki, logistik tizim tashkil bo‘lishi,
faoliyat yuritishi axborat va moddiy oqimlarni boshqarishda talab qilinadigan
g‘oyat kata miqdordagi hisob-kitob operatsiyalari ,hamda ko‘p variantli hisob-
kitoblar bilan bog‘liq.
Logistik tizimning asosiy maqsadi tovar harakati bilan bog‘liq xarajatlarni
19](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_19.png)
![kamaytirish bo‘lganligi sababli logistik tizim elementlari, xususan ta‘minotchilar,
iste‘molchilar va transport tashkilotlari o‘rtasidagi eng ma‘qul xo‘jalik
aloqalarini o‘rnatish bo‘ladi.
Har qanday logistik tizimlarni boshqarishning samaradorligini miqdoriy
baholash uchun tizimdagi jarayonlaniing matematik modeli ishlab chiqish kerak.
Bugungi kunda logistik jarayonlarniing (shu jumladan tashish
jarayonlarining) matematik modellarini shartli ravishda ikki turga analitik va
statistik modellarga ajratish mumkin. Bunda matematik modellar asosida
marshrutlashtirishga to‘xtalamiz.
Ayni paytda mazkur masalaga oid qator xususiyatlar masalan yuk oluvchi
(yoki jo‘natuvchi) tutashma manzilni tashish hajmiga bo‘lgan ehtiyojining
texnologik xarakteri, mazkur ehtiyojni qondirilishi marshrutlar yo‘nalishlarida
unga jo‘natuvchilardan olib kirilayotgan (yoki undan olib chiqilayotgan) yuk
oqimlariga bog‘liqligi va bu oqimlar esa avtokorxona avtotransport
vositalari(AV)ni yo‘nalishlarga samarali taqsimlash asosida logistik boshqarilishi
mumkinligi, yo‘nalishlarga taqsimlanayotgan AV soni ularning yuk jo‘natish (yoki
qabul qilish) imkoniyatlaridan to‘la foydalanish va tashish harajatlarini
minimallashtirish mezonlariga muvofiq aniqlanishi lozimligi va shu kabi muhim
holatlar hisobga olinmagan.
Marshrutlashtirish topografiya metodida, seyfdan yoki dispetcher tablosidan
foydalanish kabi texnik usullar yordamida amalga oshirilish mumkin.
Topografiya usulida yuk tashiladigan rayonning sxemasi bo‘lib, unda
hamma yuk jo‘natuvchi manzillar, avtokorxona va ularni bog‘lovchi yo‘l seti
beriladi. Bu sxemaga ko‘shimcha tarzda manzillararo masofalar jadvali ham
kiritiladi. Berilgan buyurtmalar asosida yuk tashish kunlik rejasi tuziladi va bu reja
bo‘yicha bajarilishi lozim bo‘lgan yuk oqimlari kalka qog‘oziga chizib olinadi.
Buning uchun yuk tashish rayoni sxemasi ustiga kalka qog‘ozini qo‘yib, real
manzillararo bajarilishi lozim bo‘lgan yuk oqimlari strelkalar tarzida chizib
olinadi. Rasm (1). Tashiladigan yuk miqdori strelkalar ustida ko‘rsatiladi. Keyin
esa yuk oqimlari marshrutlarga taqsimlanadi. Bunda tashiladigan yukning xili va
20](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_20.png)
![qo‘llaniladigan harakatlanuvchi sostav turlari hisobga olinadi. Kalkada ko‘rsatilgan
yuk tashishni graf ko‘rinishdagi plani topogramma
deyiladi va u marshrut tuzishni ancha
osonlashtiradi.
Aylanma marshrutlar tuzganda, bu
marshrutlarda harakatlanuvchi sostavni mumkin
qadar yuqori ish unumdorligiga erishishini
ta‘minlash kerak bo‘ladi.
Har bir kvadratda tirqish bo‘lib, u maxsus
kartochkalarni qistirib quyishiga mo‘ljallangan. Ha bir tashiladigan yuk uchun
maxsus kartochka to‘ldiriladi. Bu kartochkada yuk ortish, tushirish manzillari va
miqdori yukning nomi ko‘rsatiladi. Keyin kartochkalar mos tirqishlariga qistirib
chiqiladi (rasm.2.)
Marshrutlar tuzish quyidagicha bajariladi. Biror yacheykadan kartochka
olinadi va yukni qayerga olib borish kerakligi aniqlanadi. Shu yuk olib boriladigan
yacheykadagi kartochkadan qaysi yo‘nalishlarda tashiladigan yuk borligi Rasm. 2
Marshrutlashtirish seyfi, aniqlanadi. Agar shu yacheykadan tashiladigan yuklar
bo‘lmasa, uni atrofidagi qo‘shni yacheykalardagi kartochkalar tekshiriladi.
Birinchi marshrut tuzilgadan keyin ikkinchi va hokazo marshrutlar
Maxsus avtomobillar talab qiladigan yuklar uchun boshqa seyflarda
foydalaniladi.
Seyf usulining boshqacha ko‘rinishi-dispetcher tablosidan foydalanib
21](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_21.png)
![marshrutlashtirishdir. Tablo ikkita gorizontal va vertikal qismlardan iborat bo‘lib,
vertikal qismga yuk tashiladigan rayon kartasi yopishtiriladi. Bu qismlar har
birining yuzi 1 km 2
teng kvadratlarga bo‘linadi. Kvadratlar harf va raqamlar
vositasida belgilanadi. Kartada hamma yuk jo‘natadigan va qabul qiladigan
manzillar ko‘rsatiladi. Har bir yacheykada ikkita
teshik bo‘lib, unga mixchalar tiqish mumkin.
Mixchalar ikki xil rangda bo‘yaladi va yuk
punktlarini o‘rnini ko‘rsatadi: qizil mih
jo‘natuvchi, ko‘k esa yuk qabul qiluvchipunktlarni
ko‘rsatadi. Tablo komplektida yana har xil
uzunlikdagi rezina shnurlar bo‘ladi (rasm 3).
Tabloning gorizontal qismida ham huddi
vertikal qismidagidek kvadrat yacheykalarga mavjud bo‘lib, ularga yuk tashish
buyurtmalari solinadi (qar. 3-rasm). Dispetcher tablosi – Dispetcher gorizontal
yacheykalardan biridagi buyurtmani olib, yukning qayerga olib borilishini
aniqlayda va bu yuk tashish sxemasini mihchalarga rezina shnur tortib belgilab
qo‘yadi. Keyin shu yuk borgan mikrorayondan yoki uni atrofidan teskari
yo‘nalishda tashilishi lozim bo‘lgan yuk axtariladi. Shu tarzda hamma buyurtmalar
tekshirilib chiqiladi va ratsional marshrutlar tanlab olinadi.
Shu ta‘kidlash lozimki, yuqorida ko‘rib chiqilgan usullar yuk jo‘natuvchi va
oluvchi punktlar unchalik ko‘p bo‘lmaganda samarali natijalar beradi. Bunda
tuzilgan marshrutlar sifati dispetcherning tajribasiga ko‘p jihatdan bog‘liqdir.
Manzillar soni ancha ko‘p bo‘lganda bu usullar bilan samarali marshrutlar tuzish
qiyinlashadi. Chunki bunda tuzish mumkin bo‘lgan marshrutlar varianti nihoyatda
ko‘p bo‘lib, ular orasida optimal marshrutlar sistemasini topish mushkuldir.
Bunday hollarda marshrutlashtirish matematik metodlar va EHM vositasida
amalga oshiriladi.
Marshrutlashtirishda transport masalasi
Yirik partiyali yuk tashishni marshrutlashtirishda bir-biridan farqli ikki
yo‘nalish mavjud. Birinchi yo‘nalishda marshrutlashtirish transport masalasiga
22](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_22.png)
![keltirib yechiladi, ikkinchi sida esa u chiziqli programmalashtirishning umumiy
masalasiga keltiriladi.
Birinchi yo‘nalish metodlarini ko‘rib chiqamiz. Chiziqli dasturlashning
transport masalasi birmuncha sodda yechish metodikasiga ega bo‘lib,
marshrutlashtirish masalasi ilk bor ilmiy tahlil etilgan paytlardayoq shu masalaga
keltirib yechilgan edi.
Marshrutlashtirish masalasini bir necha holda quyish mumkin:
- avtotransport korxonalarining (ATK) joylashishini hisobga olmasdan
berilgan rayondagi yuk tashishni marshrutlashtirish, keyin esa topilgan
marshrutlarni korxonalarga birkitish (yagona ATK uchun marshrutlar tuzganda
masalani bu ko‘rinishda qo‘yish mumkin);
- marshrutlarni korxonalarning joylanishini hisobga olib tuzish.
Birinchi ko‘rinishda qo‘yilgan marshrutlashtirish masalasini ko‘rib chiqaylik.
Klark – rayt metodi asosida marshrutlashtirish
Yuqoridagidan bizga ma‘lum bo‘ladiki, eng qisqa bog‘lovchi tarmoq asosida
marshrutlar tuzilganda bir-biriga bog‘liq bo‘lgan ikki masala ketma-ket yechiladi:
1) manzillarga yuk olib borishning ratsional ketma-ketligini aniqlash;
2) avtomobil yuk ko‘taruvchanligini hisobga olgan holda punktlarni
marshrutlarga kiritish.
Klark – Rayt metodi bu ikki masalani birvarakayiga yechishga imkon
beradi, ya‘ni har xil yuk ko‘taruvchanlikka ega bo‘lgan harakatlanuvchi tarkiblar
uchun ratsional marshrutlar tuziladi.
Metodning mohiyati quyidagidan iborat.
Birinchi navbatda yuk tashishning dastlabki plani tuziladi. Bunda har bir
oluvchiga alohida mayatnik marshrut ajratilib, tashiladigan yuk miqdoriga mos
keladigan ko‘taruvchanlikdagi avtomobil ajratiladi.
Keyingi iteratsiyalarda ikkita mayatnik marshrut o‘zaro juftlashtiriladi va
natijada tarqatish marshruti hosil qilinadi. Qolgan mayatnik marshrutlar va
tarqatish marshruti o‘zaro birlashtiriladi va bunda shunday variant tanlanadiki,
juftlashtirish natijasida tashish xarajatlari maksimal kamaysin.
23](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_23.png)
![1.4 Graflar nazariyasi elemenlari (graf, orgraf, zanjir, mashrut, grafni hosil
qilish)
Graflar nazariyasi h aqida umumiy ma’lumotlar. 1736 yilda L . Eyler
tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan
Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar
nazariyasining paydo bo‘lishiga asos bo‘ldi .
Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa
ba’zi sodda tushunchalarni keltiramiz. V qandaydir bo‘shmas to‘plam bo‘lsin.
Uning
v1∈V va v2∈V elementlaridan tuzilgan ¿v1,v2>¿¿ ko‘rinishdagi barcha
juftliklar (kortejlar) to‘plamini (
V to‘plamning o‘z-o‘ziga Dekart ko‘paytmasi ni)
V×V
bilan belgilaymiz.
Graf deb shunday
¿V,U>¿¿ juftlikka aytiladiki, bu yerda V≠∅ va U –
¿v1,v2>¿¿
( v1∈V , v2∈V ) ko‘rinishdagi juftliklar korteji bo‘lib, V×V to‘plamning
elementlaridan tuzilgandir.
Bundan buyon grafni belgilashda
¿V,U>¿¿ yozuv o‘rniga (V,U) yozuvdan
foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda
uni lotin alifbosining bitta harfi, masalan,
G bilan belgilaymiz.
G=(V,U )
graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning
uchlari ,
V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi.
Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi
ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi
iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan
keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham
keltirishga harakat qilamiz.
G=(V,U )
grafning ta’rifiga ko‘ra, U bo‘sh kortej bo‘lishi ham mumkin.
Agar
U bo‘sh bo‘lmasa, u holda bu kortej (a,b) ( a∈V , b∈V ) ko‘rinishdagi
juftliklardan tashkil topadi, bunda
a=b bo‘lishi hamda ixtiyoriy (a,b) juftlik U
kortejda istalgancha marta qatnashishi mumkin.
24](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_24.png)
![(a,b)∈U juftlikni tashkil etuvchi a va b uchlarning joylashish tartibidan
bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash
mumkin. Agar
(a,b) juftlik uchun uni tashkil etuvchilarning joylashish tartibi
ahamiyatsiz, ya’ni
(a,b)=(b,a) bo‘lsa, (a,b) juftlikk a yo‘naltirilmagan
( oriyentirlanmagan ) qirra (yoki, qisqacha, qirra ) deyiladi. Agar bu tartib
muhim, ya’ni
(a,b)≠(b,a) bo‘lsa, u holda (a,b) juftlikka yoy yoki yo‘naltirilgan
( oriyentirlangan ) qirra deyiladi.
U
kortejning tarkibiga qarab, uni yo grafning qirralari korteji , yo yoylari
korteji , yoki qirralari va yoylari korteji deb ataymiz.
Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.
G=(V,U )
graf elementlari ning soni ( |V|+|U | )ga tengdir, bu yerda G grafning
uchlari soni
|V|≠0 va |U| bilan uning qirralari (yoylari) soni belgilangan.
Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida
(a,b) ,
yoki
ab , yoki (a;b) ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi:
masalan, yoy uchun
(⃗a,b) yoki (⃗a,b) , qirra uchun (⃗a,b) , yoy yoki qirra uchun u
(ya’ni uchlari ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda.
Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini
ta’kidlaymiz, ya’ni
(a,b) va (b,a) yozuvlar bir-biridan farq qiluvchi yoylarni
ifodalaydi. Agar yoy
(a,b) ko‘rinishda ifodalangan bo‘lsa, u holda a uning
boshlang‘ich uch i ,
b esa oxirgi uch i deb ataladi. Bundan tashqari, yoy (a,b)
ko‘rinishda yozilsa, u haqida
a uchdan chiquvchi ( boshlanuvchi ) va b uchga
kiruvchi ( uchda tugovchi ) yoy deb aytish ham odat tusiga kirgan.
Qirra uchun uning
(a,b) yozuvidagi harflar joylashish tartibi muhim rol
o‘ynamaydi va
a va b elementlar qirraning uchlari yoki chetlari deb ataladi.
Agar grafda yo
(a,b) qirra, yo (a,b) yoy, yoki (b,a) yoy topillsa, u holda a
va
b uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi
qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni
bo‘lmagan uchlar deb aytiladi.
25](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_25.png)
![Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga
( yoyga ) insident , o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi.
Grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar
( yoylar ) deyiladi.
Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli,
insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni
ifodalaydi.
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni m va
qirralar ( yoylar ) soni
n ga qarab belgilanadi va bu holda grafni (m,n) -graf deb
ataydilar.
Agar
G=(V,U ) grafda U kortej faqat qirralardan iborat bo‘lsa, u holda
yo‘naltirilmagan ( oriyentirlanmagan ) va faqat yo‘naltirilgan (oriyentirlangan)
qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan
( oriyentirlangan ) graf deb ataladi. Oriyentirlangan graf, qisqacha, orgraf deb
ham ataladi.
Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham
bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar
deb ataladi.
Agar
G=(V,U ) grafning (orgrafning) U korteji tarkibida V×V to‘plamdan
olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel
qirralar ( yoylar ) deb ataladi. Karrali qirralari yoki yoylari bo‘lgan graf multigraf
deyiladi.
Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy),
ya’ni grafning
(a,a)∈U elementi sirtmoq deb ataladi. Sirtmoq, odatda,
yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan
graf psevdograf deyiladi.
Umumiy holda uchlar to‘plami
V va (yoki) qirralar (yoylar, qirra va yoylar)
korteji
U cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin V to‘plam va U
26](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_26.png)
![kortej faqat chekli bo‘lgan G=(V,U ) graflarni qaraymiz. Bunday graflar chekli
graflar deb ataladi.
Hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan ( ajralgan ,
xolis , yalong‘och ) uch deb ataladi.
Faqat yakkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va
yoylar bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. Uchlari soni
m ga teng
bo‘lgan bo‘sh grafni
Om yoki Nm kabi belgilash qabul qilingan.
Istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz
oriyentirlanmagan graf to‘la graf deb ataladi. Uchlari soni
m ga teng bo‘lgan to‘la
graf
Km bilan belgilanadi. Ravshanki, Km grafning qirralar soni Cm2= m(m−1)
2
bo‘ladi .
Agar orgrafning istalgan ikkita uchini har bir yo‘nalishda tutashtiruvchi
faqat bittadan yoy mavjud bo‘lsa, u holda unga to‘la orgraf deb ataladi.
Ravshanki, to‘la grafdagi qirralarning har birini ikkita (yo‘nalishlari bir-biriga
qarama-qarshi bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi.
Shuning uchun, to‘la orgrafdagi yoylar soni oriyentirlanmagan to‘la grafdagi
qirralar sonidan ikki baravar ko‘pdir, ya’ni uchlari
m ta bo‘lgan to‘la orgrafdagi
yoylar soni
2Cm2=m(m−1) bo‘ladi.
Agar grafning uchlariga qandaydir belgilar, masalan,
1,2 ,...,m sonlari mos
qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi.
Agar
G=(V,U ) va G'=(V',U ') graflarning uchlari to‘plamlari, ya’ni V va V'
to‘plamlar orasida uchlarning qo‘shnilik munosabatini saqlaydigan o‘zaro bir
qiymatli moslik o‘rnatish mumkin bo‘lsa, u holda
G va G' graflar izomorf graflar
deb ataladi. Bu ta’rifni quyidagicha ham ifodalash mumkin: agar
∀ x,y ∈V va
ularga mos bo‘lgan
x',y'∈V' ( x↔ y , x'↔ y' ) uchun xy ↔ x'y' ( xy ∈U , x'y'∈U' )
bo‘lsa, u holda
G va G' graflar izomorfdir. Agar izomorf graflardan biri
oriyentirlangan bo‘lsa, u holda ikkinchisi ham, albatta, oriyentirlangan bo‘lishi va
ulardagi mos yoylarning yo‘nalishlari ham bir-birlariga mos bo‘lishlari shart.
27](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_27.png)
![Graf uchiga insident qirralar soni shu uchning lokal darajasi , yoki,
qisqacha, darajasi , yoki valentligi deb ataladi. Grafdagi a uchning darajasini ρ(a)
bilan belgilaymiz.
Sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga
olish kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra deb ham,
ikkita qirra deb ham hisoblash mumkin. Ravshanki, ajralgan uchning darajasi
nolga teng. Darajasi birga teng uch chetki (yoki osilgan ) uch deb ataladi. Chetki
(osilgan) uchga insident qirra ham chetki (yoki osilgan ) qirra deb ataladi.
Agar grafning barcha uchlari bir xil
r darajaga ega bo‘lsa, u holda bunday
graf
r darajali regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki
uch valentli ) graf deb ataladi.
Om graf nol darajali regulyar graf ekanligini, Km esa
(
m−1 ) darajali regulyar graf ekanligini ta’kidlaymiz.
Ko‘rinib turibdiki, oriyentirlanmagan grafda barcha uchlar darajalarining
yig‘indisi qirralar sonining ikki baravariga teng juft son bo‘ladi, chunki qirralarni
sanaganda har bir qirra hisobda ikki marta qatnashadi. Shunday qilib, XVIII
asrdayoq L. Eyler tomonidan isbotlangan quyidagi tasdiq o‘rinlidir.
28](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_28.png)
![II BOB TRANSPORT LOGISTIKASIDA GRAFLARNI TATBIQ ETISH
2.1 Grafni hosil qilish
Bugungi kunda graflar eng rivojlangan soha sifatida rivojlanib kelmoqda quyida
graf ma'lumotlar strukturasiga misol keltiramiz:
Yuqorida G graf misoli keltirilgan. G graf uchlar to‘plami {A,B,C,D,E} va
qirralar to‘plami {(A,B),(B,C),(A,D), (D,E),(E,C),(B,E),(B,D)}.
Grafning turlari - yo‘naltirilgan va yo‘naltirilmagan graf
Qirralari yo‘nalishga ega bo‘lmagan graf yo‘naltirilmagan graf deb ataladi.
Yuqorida ko‘rsatilgan graf yo‘naltirilmagan grafdir.
Qirralari ular bilan bog‘langan yo‘nalishlarga ega bo‘lgan graf yo‘naltirilgan
graf deb ataladi.
Quyida yo‘naltirilgan graf misoli keltirilgan.
Yuqorida ko‘rsatilgan yo‘naltirilgan grafda qirralar tartiblangan juftlikni
hosil qiladi, bunda har bir chekka bir uchdan boshqa uchga o‘ziga xos yo‘lni
29](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_29.png)
![ifodalaydi. Yo‘l boshlanadigan uch "Boshlang‘ich tugun" deb ataladi, yo‘l
tugaydigan uch esa "Terminal tugun" deb ataladi.
Shunday qilib, yuqoridagi grafda uchlar to‘plami {A, B, C, D, E} va qirralar
to‘plami {(A,B),(A,D),(B,C),(B,E). ),(D,E)(E,C)}.
Biz graf terminologiyasini yoki quyidagi grafga nisbatan ishlatiladigan
umumiy atamalarni muhokama qilamiz.
Graf tasvirlash
Graf ma'lumotlar strukturasini xotirada saqlash usuli "vakolat" deb ataladi.
Graf ketma-ket tasvir yoki bog‘langan tasvir sifatida saqlanishi mumkin.
Bu ikkala tur ham quyida tavsiflanadi.
Ketma-ket vakillik
Graflarni ketma-ket tasvirlashda biz qo‘shnilik matritsasidan foydalanamiz.
Qo‘shni matritsa n x n o‘lchamdagi matritsa bo‘lib, bu erda n - grafdagi uchlar
soni.
Qo‘shni matritsaning satrlari va ustunlari grafdagi uchlarni ifodalaydi.
Matritsa elementi uchlar orasida chekka mavjud bo‘lganda 1 ga o‘rnatiladi. Agar
chekka mavjud bo‘lmasa, element 0 ga o‘rnatiladi.
Quyida uning qo‘shnilik matritsasini ko‘rsatadigan misol graf
keltirilgan.
.
Yuqoridagi graf uchun qo‘shnilik matritsasini ko‘rdik. E'tibor bering, chunki
bu yo‘naltirilmagan graf va biz chekka ikkala yo‘nalishda ham mavjud deb
aytishimiz mumkin. Masalan, AB qirrasi mavjud bo‘lganligi sababli, BA chekkasi
ham mavjud degan xulosaga kelishimiz mumkin.
30](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_30.png)
![Qo‘shni matritsada biz matritsa elementlari bo‘lgan uchlarning o‘zaro
ta'sirini ko‘rishimiz mumkin, ular chekka mavjud bo‘lganda 1 ga va chekka yo‘q
bo‘lganda 0 ga o‘rnatiladi.
Endi yo‘naltirilgan grafning qo‘shnilik matritsasini ko‘rib chiqamiz.
Yuqorida ko‘rsatilganidek, qo‘shni matritsadagi kesishish elementi 1 ga teng
bo‘ladi, agar bir uchdan ikkinchisiga yo‘naltirilgan chekka mavjud bo‘lsa.
Yuqoridagi grafda bizda A uchsining ikkita qirrasi bor. Bir qirrasi B uchsiga,
ikkinchisi esa C uchga tugaydi. Shunday qilib, qo‘shni matritsada A va B kesishuvi
A va C chorrahasi sifatida 1 ga o‘rnatiladi.
Keyinchalik, vaznli graf uchun ketma-ket tasvirni ko‘ramiz.
Quyida vaznli graf va unga mos keladigan qo‘shnilik matritsasi
berilgan.
Biz vaznli grafning ketma-ket tasvirlanishi boshqa turdagi graflardan farq
qilishini ko‘rishimiz mumkin. Bu erda qo‘shni matritsadagi nolga teng bo‘lmagan
qiymatlar chekkaning haqiqiy og‘irligi bilan almashtiriladi.
AB chetining og‘irligi = 4 ga ega, shuning uchun qo‘shni matritsada biz A
va B ning kesishishini 4 ga o‘rnatamiz. Xuddi shunday, boshqa barcha nolga teng
bo‘lmagan qiymatlar o‘zlarining tegishli og‘irliklariga o‘zgartiriladi.
31](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_31.png)
![Qo‘shnilar ro‘yxatini amalga oshirish va kuzatish osonroq. O‘tish, ya'ni bir
uchdan ikkinchisiga chekka mavjudligini tekshirish O (1) vaqtni oladi va chetni
olib tashlash O (1) vaqtini oladi.
Graf siyrak (kamroq qirralar) yoki zich bo‘ladimi, u har doim ko‘proq joy
oladi.
Bog‘langan vakillik
Grafning bog‘langan ko‘rinishi uchun biz qo‘shnilik ro‘yxatidan
foydalanamiz. Qo‘shnilik ro‘yxati tasviri grafning har bir tugunini va ushbu
tugunga qo‘shni bo‘lgan tugunlarga havolani saqlaydi. Barcha qo‘shni tugunlarni
kesib o‘tganimizda, biz ro‘yxat oxirida keyingi ko‘rsatkichni null ga o‘rnatamiz.
Keling, birinchi navbatda yo‘naltirilmagan grafni va uning qo‘shnilik
ro‘yxatini ko‘rib chiqaylik.
Yuqorida ko‘rsatilganidek, bizda har bir tugun uchun bog‘langan ro‘yxat
(qo‘shnilar ro‘yxati) mavjud. A uchsidan B, C va D uchlariga qirralarimiz bor.
Shunday qilib, bu tugunlar mos keladigan qo‘shnilik ro‘yxatidagi A tuguniga
bog‘langan.
Keyinchalik, yo‘naltirilgan graf uchun qo‘shnilik ro‘yxatini tuzamiz.
Yuqoridagi grafda biz E uchsidan kelib chiqadigan qirralarning yo‘qligini
ko‘ramiz. Demak, E uchi uchun qo‘shnilik ro‘yxati bo‘sh.
32](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_32.png)
![Keling, tortilgan graf uchun qo‘shnilik ro‘yxatini tuzamiz.
Og‘irlangan graf uchun biz yuqorida ko‘rsatilganidek, chekka og‘irligini
belgilash uchun qo‘shnilik ro‘yxati tuguniga qo‘shimcha maydon qo‘shamiz.
Qo‘shnilar ro‘yxatiga vertex qo‘shish osonroq. Shuningdek, u bog‘langan
ro‘yxatni amalga oshirish tufayli joyni tejaydi. Bir uchdan ikkinchisiga chekka
bor-yo‘qligini aniqlashimiz kerak bo‘lganda, operatsiya samarali bo‘lmaydi.
Graflar uchun asosiy operatsiyalar
Quyida biz graf ma'lumotlar strukturasida bajarishimiz mumkin bo‘lgan
asosiy operatsiyalar:
Uch qo‘shish: Grafga uch qo‘shadi.
Chet qo‘shish: Grafning ikkita uchsi orasiga chekka qo‘shadi.
Graf uchlarini ko‘rsatish: Grafning uchlarini ko‘rsatish.
Qo‘shnilik ro‘yxati yordamida C++ grafigini amalga oshirish
Endi biz qo‘shnilik ro‘yxatidan foydalangan holda oddiy grafni namoyish
qilish uchun C++ dasturini taqdim etamiz.
Bu erda biz vaznli yo‘naltirilgan graf uchun qo‘shnilik ro‘yxatini
ko‘rsatamiz. Grafning qo‘shnilik ro‘yxati va qirralarini ushlab turish uchun ikkita
tuzilmadan foydalandik. Qo‘shnilar ro‘yxati (start_vertex, end_vertex, vazn)
sifatida ko‘rsatiladi.
C++ dasturi quyidagicha:
#include <iostream>
using namespace std;
// qo‘shni ro‘yxat elementlarini saqlaydi
struct adjNode {
33](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_33.png)
![int val, cost;
adjNode* next;
};
// qirralarni saqlash uchun tuzilish
struct graphEdge {
int start_ver, end_ver, weight;
};
class DiaGraph{
// berilgan grafdan qo‘shnilar ro‘yxatiga yangi tugunlarni qo‘shing
adjNode* getAdjListNode(int value, int weight, adjNode* head) {
adjNode* newNode = new adjNode;
newNode->val = value;
newNode->cost = weight;
newNode->next = head; // yangi tugunni joriy boshga yo‘naltiring
return newNode;
}
int N; // grafdagi tugunlar soni
public:
adjNode **head; //ko‘rsatkichlar massivi sifatida qo‘shnilik ro‘yxati
// Konstruktor
DiaGraph(graphEdge edges[], int n, int N) {
// yangi tugunni ajratish
head = new adjNode*[N]();
this->N = N;
// barcha uchlari uchun bosh ko‘rsatgichni ishga tushiring
for (int i = 0; i < N; ++i)
head[i] = nullptr;
// unga qirralar qo‘shish orqali yo‘naltirilgan grafni tuzing
for (unsigned i = 0; i < n; i++) {
int start_ver = edges[i].start_ver;
int end_ver = edges[i].end_ver;
int weight = edges[i].weight;
// boshida kiriting
adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
// bosh ko‘rsatgichni yangi tugunga yo‘naltiring
head[start_ver] = newNode;
}
}
// Destruktor
~DiaGraph() {
for (int i = 0; i < N; i++)
delete[] head[i];
delete[] head;
}
};
// berilgan uchning barcha qo‘shni uchlarini chop eting
34](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_34.png)
![void display_AdjList(adjNode* ptr, int i)
{
while (ptr != nullptr) {
cout << "(" << i << ", " << ptr->val
<< ", " << ptr->cost << ") ";
ptr = ptr->next;
}
cout << endl;
}
// grafni amalga oshirish
int main()
{
// Graf qirralari massivi.
graphEdge edges[] = {
// (x, y, w) -> og‘irligi w bilan x dan y gacha bo‘lgan chekka
{0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
};
int N = 6; // Grafdagi uchlar soni
// qirralarning sonini hisoblash
int n = sizeof(edges)/sizeof(edges[0]);
// graf qurish
DiaGraph diagraph(edges, n, N);
// grafning qo‘shnilik ro‘yxati tasvirini chop etish
cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
for (int i = 0; i < N; i++)
{
// i uchsining qo‘shni uchlarini ko‘rsatish
display_AdjList(diagraph.head[i], i);
}
return 0;
}
2.2 Graf mashrutlarni hosil qilish
Graf va uning tasvirlari
Graf ma'lumotlar strukturasi bo‘lib, quyidagi ikkita komponentdan iborat:
1. Uchlarning chekli to‘plami tugunlar deb ham ataladi.
2. (u, v) ko‘rinishdagi tartiblangan juftlikning chekli to‘plami chekka deb
ataladi. Juftlik tartiblangan, chunki (u, v) yo‘naltirilgan graf (di-graf) holatida (v,
u) bilan bir xil emas. Shakl juftligi (u, v) uch u dan v uchgacha chekka borligini
bildiradi. Qirralarda og‘irlik/qiymat/narx bo‘lishi mumkin.
35](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_35.png)
![Graflar ko‘plab real hayot ilovalarini ko‘rsatish uchun ishlatiladi: Graflar
tarmoqlarni ifodalash uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog‘i
yoki elektron tarmoqdagi yo‘llarni o‘z ichiga olishi mumkin. Graflar linkedIn,
Facebook kabi ijtimoiy tarmoqlarda ham qo‘llaniladi. Masalan, Facebook-da har
bir shaxs tepa (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilma bo‘lib, shaxs
identifikatori, ismi, jinsi va mahalliy til kabi ma'lumotlarni o‘z ichiga oladi.
Grafning qo‘shimcha ilovalari uchun buni ko‘ring.
Quyida 5 ta burchakli yo‘naltirilmagan graf misoli keltirilgan.
Quyidagi ikkitasi grafning eng ko‘p ishlatiladigan tasvirlari.
1. Qo‘shnilik matritsasi
2. Qo‘shnilar ro‘yxati
Insidans matritsasi va Insidans List kabi boshqa ko‘rinishlar ham mavjud.
Graf tasvirni tanlash vaziyatga xosdir. Bu butunlay bajariladigan operatsiyalar
turiga va foydalanish qulayligiga bog‘liq.
Qo‘shnilik matritsasi:
Qo‘shnilik matritsasi - bu V x V o‘lchamdagi 2D massiv, bu erda V -
grafdagi uchlar soni. 2D massiv adj[][] bo‘lsin, slot adj[i][j] = 1 i -uchdan j -
uchgacha qirra (yoy) borligini bildiradi. Yo‘naltirilmagan graf uchun qo‘shnilik
matritsasi har doim simmetrikdir. Qo‘shnilik matritsasi vaznli graflarni ko‘rsatish
uchun ham ishlatiladi. Agar adj[i][j] = w bo‘lsa, u holda i uchdan j uchgacha w
og‘irligi bilan chekka mavjud.
Yuqoridagi misol graf uchun qo‘shnilik matritsasi:
36](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_36.png)
![Taqqoslash mumkinki, vakillikni amalga oshirish va kuzatish osonroq.
Chetni olib tashlash O (1) vaqtni oladi. “u” uchsidan “v” uchsiga chekka bor-
yo‘qligi kabi so‘rovlar samarali va O(1) ni bajarish mumkin.
Kamchiliklari: O(V^2) ko‘proq joy sarflaydi. Graf siyrak bo‘lsa ham
(kamroq chekkalarni o‘z ichiga oladi), u bir xil joyni egallaydi. Uch qo‘shilishi
O(V ^ 2) vaqtidir. Bir uchning barcha qo‘shnilarini hisoblash O (V) vaqtni oladi
(samarali emas).
Iltimos, qo‘shnilik matritsasining Python ilovasi namunasi uchun buni
ko‘ring.
Qo‘shni matritsa uchun kirishni amalga oshirish C++ da
#include <iostream>
using namespace std;
int main()
{
// n uchlari soni
// m - qirralarning soni
int n, m;
cin >> n >> m ;
int adjMat[n + 1][n + 1];
for(int i = 0; i < m; i++){
int u , v ;
cin >> u >> v ;
adjMat[u][v] = 1 ;
adjMat[v][u] = 1 ;
}
return 0;
}
37](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_37.png)
![Qo‘shnilar ro‘yxati:
Ro‘yxatlar massivi ishlatiladi. Massivning o‘lchami uchlari soniga teng.
Massiv [] massiv bo‘lsin. Kirish massivi[i] i-chi uchga qo‘shni uchlar ro‘yxatini
ifodalaydi. Ushbu tasvirdan vaznli grafni ifodalash uchun ham foydalanish
mumkin. Qirralarning og‘irligi juftliklar ro‘yxati sifatida ifodalanishi mumkin.
Quyida yuqoridagi grafning qo‘shnilik ro‘yxati ko‘rsatilgan.
E'tibor bering, quyida keltirilgan dasturda biz bog‘langan ro‘yxat o‘rniga
qo‘shni ro‘yxatlarni ko‘rsatish uchun dinamik massivlardan (Java'da
C++/ArrayList'dagi vektor) foydalanamiz. Vektorni amalga oshirish kesh
qulayligining afzalliklariga ega.
// STL yordamida grafning oddiy tasviri
#include <bits/stdc++.h>
using namespace std;
// Kengay qo‘shish uchun yordamchi dastur
// yo‘naltirilmagan graf.
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Qo‘shnilar ro‘yxatini chop etish uchun yordamchi dastur
// graf tasviri
void printGraph(vector<int> adj[], int V)
{
for (int v = 0; v < V; ++v) {
cout << "\n Adjacency list of vertex " << v
38](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_38.png)
![<< "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
// asosiy kodi
int main()
{
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj, V);
return 0;
}
Natija
0 uchsining qo‘shnilik ro‘yxati
head -> 1-> 4
1-uchning qo‘shnilik ro‘yxati
head -> 0-> 2-> 3-> 4
2-uchning qo‘shnilik ro‘yxati
head -> 1-> 3
3 uchsining qo‘shnilik ro‘yxati
head -> 1-> 2-> 4
4-uchning qo‘shnilik ro‘yxati
head -> 0-> 1-> 3
Taroziga soling: joyni tejaydi O(|V|+E|) . Eng yomon holatda, grafda C(V,
2) chekka soni bo‘lishi mumkin, shuning uchun O(V^2) bo‘sh joy sarflanadi. Uch
qo‘shish osonroq. Bir uchning barcha qo‘shnilarini hisoblash optimal vaqtni oladi.
Kamchiliklari: U uchdan v uchgacha chekka bor-yo‘qligi kabi so‘rovlar
samarali emas va O(V) ni bajarish mumkin.
Hayotiy masalalarda graflar siyrak (E| <<|V|2). Shuning uchun qo‘shni
ro‘yxatlar Ma'lumotlar strukturasi odatda graflarni saqlash uchun ishlatiladi.
Qo‘shnilik matritsasi bunday algoritmlar uchun vaqtga bog‘liq murakkablikni (|V|
2) amalga oshiradi.
39](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_39.png)
![2.3 Eng qisqa mashrutni aniqlash
Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi)
to‘plamidan iborat bo‘lgan abstrakt matematik ob’ektdir.
Grafning elementlari tarkibi va munosabatlar tuzilishi beriladi. Grafning
tarkibiy qismlari bu uning tugunlari va qirralaridir.
Tarmoq
Bir nechta juft tugunlararo qirralardan iborat bo‘lgan turlicha yo‘llar
to‘plami mavjud bo‘lishi mumkin. Yopiq
yo‘llar – sikllarning mavjud bo‘lishi
tarmoqlarga xos xususiyatdir.
Yonaltirilmagan graf yoki simmetrik
bog‘liqlik
Yonaltirilmagan graf yoki
nosimmetrik bog‘liqlik qirra (yoy)lar
Ilmoq – aynan bitta tugundan chiqib, yana shu tugunga kiruvchi qirra.
40К С
ОИ
Н
I
II III
IV](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_40.png)
![Deykstra algoritmi
Gollandiyalik olim Edsger Deykstra algoritmi grafning boshlang‘ich
berilgan tugunidan boshlab qolgan barcha tugunlargacha bo‘lgan barcha eng qisqa
yo‘llarni topadi. Uning yordamida, agar barcha zarur ma'lumotlar berilgan bo‘lsa,
masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta shahardan
boshqa shaharlarning har biriga borish uchun qaysi yo‘llar ketma-ketligini tanlash
afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy tomoni shundaki,
manfiy vaznga ega bo‘lgan qirralari mavjud bo‘lgan graflarni qayta ishlash
imkonining mavjud emasligi, ya'ni, masalan, ba'zi tizim birorta kompaniya uchun
foydasiz bo‘lgan marshrutlarni taqdim qilsa, u holda u bilan ishlash uchun
Dijkstraning algoritmidan foydalanib bo‘lmaydi.
Algoritmni dasturiy ta'minotini amalga oshirish uchun ikkita massiv kerak
bo‘ladi: mantiqiy toifadagi visited - tashrif buyurilgan tugunlar haqidagi
ma'lumotlarni saqlash uchun va topilgan eng qisqa yo‘llar kiritiladigan butun
toifadagi - distance . G={V,E} graf berilgan bo‘lsin. V to‘plamga tegishli barcha
tugunlar dastlab tashrif buyurilmagan deb belgilanadi, ya’ni visited massivining
elementlariga false qiymat berib chiqiladi. Eng afzal yo‘lni topish masalasi
qaralyapti. Distance massivining har bir elementiga shunday qiymat beriladiki,
ixtiyoriy potensial yo‘ldan katta bo‘lsin (odatda, bu qiymatni cheksiz katta qiymat
deb qaraladi, ammo dasturda berilgan toifaning qiymatlar diapazonidagi eng katta
qiymat sifatida olinadi). Boshlang‘ich nuqta sifatida s tugun tanlanadi va unga nol
yo‘l belgilanadi: distance [s] = 0, chunki s-dan s-gacha hech qanday qirra yo‘q (bu
usulda ilmoqlar qaralmaydi).
Shundan keyin, barcha qo‘shni tugunlar topiladi (s dan chiquvchi qirralar
orqali) [ularni t va u deb belgilaylik] va ular birma-bir tekshirib ko‘riladi, ya'ni s
tugundan har bir tugungacha birma-bir marshrut bahosi hisoblanadi:
- distance[t]=distance[s]+ s va t orasidagi qirraning vazni;
- Distance[u]=distance[s]+ s va u orasidagi qirraning vazni.
41](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_41.png)
![Ehtimoldan xoli emaski, u yoki bu tugunga s dan bir qancha yo‘llar bo‘lishi
mumkin. Shu sababli, distance massivida bu tugunga bo‘lgan yo‘lning vaznini
qayta ko‘rib chiqish kerak bo‘ladi. Shunda kattaroq (nooptimal) qiymat yo‘qotiladi
va tugunga mos yo‘lning vazniga kichikroq qiymat beriladi. s tugun bilan
qo‘shni bo‘lgan va qarab chiqilgan tugunlar tashrif buyurilgan sifatida belgilab
chiqiladi, yani visited[s]=true va natijada, s dan chiquvchi, minimal vaznga ega
bo‘lgan yo‘l eltuvchi tugun faol element sifatida belgilab olinadi. Faraz qilamiz, s
dan u gacha masofa t ga qaraganda qisqa bo‘lsin. Kelib chiqadiki, u tugun
faollashadi va yuqoridagi kabi uning qo‘shnilari ( s dan tashqari) o‘rganilib
chiqiladi. u tugun tashrif buyurilgan deb belgilanadi: visited[u]=true, endi t tugun
faollashadi va yuqoridagi prosedura uning uchun takrorlanadi. Deykstra algoritmi s
tugundan borish mumkin bo‘lgan barcha tugunlar tadqiq qilinmaguncha davom
ettiriladi.
C++ da dastur kodi
#include <iostream>
using namespace std;
#include <limits.h>
// Grafdagi uchlar soni
#define V 9
// Minimal masofa qiymatiga ega uchni topish uchun yordamchi funktsiya, dan
// eng qisqa yo‘l daraxtiga hali kiritilmagan uchlar to‘plamiint minDistance(int dist[], bool
sptSet[])
{
// Minimal qiymatni ishga tushiring
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// Tuzilgan masofa massivini chop etish uchun yordamchi funksiya
void printSolution(int dist[])
{
cout <<"Vertex \t Distance from Source" << endl;
42](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_42.png)
![for (int i = 0; i < V; i++)
cout << i << " \t\t"<<dist[i]<< endl;
}
// Dijkstraning yagona manbali eng qisqa yo‘l algoritmini amalga oshiradigan funksiya
// qo‘shni matritsa ko‘rinishidan foydalangan holda tasvirlangan graf uchun
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// src dan i gacha bo‘lgan masofa
bool sptSet[V]; // sptSet[i] i uch eng qisqasiga kiritilgan bo‘lsa rost bo‘ladi
// yo‘l daraxti yoki src dan i gacha bo‘lgan eng qisqa masofa yakunlandi
// Barcha masofalarni INFINITE va stpSet[] ni noto‘g‘ri deb boshlang
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Manba uchsining o‘zidan masofa har doim 0 ga teng
dist[src] = 0;
// Barcha uchlar uchun eng qisqa yo‘lni toping
for (int count = 0; count < V - 1; count++) {
// Yo‘q uchlar to‘plamidan minimal masofa uchsini tanlang
// hali qayta ishlangan. u birinchi iteratsiyada har doim src ga teng.
int u = minDistance(dist, sptSet);
// Tanlangan uchni qayta ishlangan deb belgilang
sptSet[u] = true;
// Tanlangan uchning qo‘shni uchlarining dist qiymatini yangilang.
for (int v = 0; v < V; v++)
// dist[v] ni yangilash faqat sptSet da bo‘lmasa, dan chekka mavjud
// u dan v gacha va src dan v gacha bo‘lgan yo‘lning umumiy og‘irligi
// dist[v] ning joriy qiymatidan kichikroq
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// tuzilgan masofa massivini chop eting
printSolution(dist);
}
// Yuqoridagi funktsiyani sinab ko‘rish uchun bajaruvchi dasturi
int main()
{
43](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_43.png)
![/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
dijkstra(graph, 0);
return 0;
}
Bellman-Ford algoritmi
Algoritm tarixi uchta mustaqil matematiklar bilan bog‘liq: Lester Ford,
Richard Bellman va Edward Moore. Ford va Bellman algoritmni 1956 va 1958
yillarda nashr etishdi, Moore esa 1957 yilda taqdim qilgan. Va ba'zan uni Bellman-
Ford-Moore algoritmi deb ham atashadi. Usul ba'zi vektorli-marshrutlash
protokollarida, masalan, RIPda (Routing Information Protocol) qo‘llaniladi.
Deykstra algoritmi singari, Bellman-Ford algoritmi ham vaznga ega bo‘lgan
graflarda bitta tugundan qolgan barcha tugunlarga bo‘lgan eng qisqa masofani
aniqlashda ishlatiladi. Bu algoritm manfiy vaznga ega bo‘lgan graflar bilan
ishlashda ham qo‘llanilishi mumkin (istisno holatlar ham mavjud).
s tugundan qolgan barcha tugunlargacha bo‘lgan qisqa masofani Bellman-
Ford algoritmidan foydalanib topish dinamik dasturlashtirish usulini qo‘llash
demakdir, ya’ni uni qism masalalarga ajratib, ularni yechimi orqali umumiy asosiy
masalani hal qilishdir. Bunda qism masala bo‘lib, bitta alohida qaralayotgan
tugundan boshqasigacha eng qisqa yo‘lni aniqlash masalasi hisoblanadi. Algoritm
natijalarini saqlash uchun d[] bir o‘lchovli massiv qabul qilamiz. Uning har bir i-
elementida s gundan i-elementgacha qisqa masofa qiymatini saqlanadi (agar
mavjud bo‘lsa). Dastlab, d[] massiv elementlariga shartli sheksiz katta qiymat
berib chiqiladi, d[s] ga 0 o‘zlashtiriladi.
44](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_44.png)
![G={V, E}, n=|V|, m=|E| graf berilgan bo‘lsin. Qo‘shni tugunlarni v va u deb,
(v,u) orasidagi qirrani w deb belgilab olamiz. Boshqacha aytganda, v tugundan
chiquvchi va u tugunga kiruvchi qirra vazni w ga teng. U holda, Bellman-Ford
algoritmining muhim qismi quyidagicha ko‘rinishga ega bo‘ladi:
• I=1 dan n-1 gacha bajaramiz выполнять
j=1 dan m gacha bajaramiz
agar d[v] + w(v, u) < d[u] bo‘lsa, u holda
d[u] < d[v] + w(v, u)
Har bir n-qadamda d[] massiv elementlari qiymatlarini yashilashga harakat
qilinadi: agar w(v,u) qirra vazni va d[v] element qiymati yig‘indisi d[u] qiymaridan
kichik bo‘lsa, u holda bu qiymat d[u] ga o‘zlashtiriladi.
#include "stdafx.h"
#include <iostream>
#define inf 100000
using namespace std;
struct Edges{
int u, v, w;
};
const int Vmax=1000;
const int Emax=Vmax*(Vmax-1)/2;
int i, j, n, e, start;
Edges edge[Emax];
int d[Vmax];
//Bellman-Ford algoritmi
void bellman_ford(int n, int s)
{
int i, j;
for (i=0; i<n; i++) d[i]=inf;
d[s]=0;
for (i=0; i<n-1; i++)
for (j=0; j<e; j++)
if (d[edge[j].v]+edge[j].w<d[edge[j].u])
d[edge[j].u]=d[edge[j].v]+edge[j].w;
for (i=0; i<n; i++) if (d[i]==inf)
cout<<endl<<start<<"->"<<i+1<<"="<<"Not";
else cout<<endl<<start<<"->"<<i+1<<"="<<d[i];
}
//asosiy funksiya
void main()
{
45](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_45.png)
![int w;
cout<<"tugunlar soni > "; cin>>n;
e=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<" Вес "<<i+1<<"->"<<j+1<<" > "; cin>>w;
if (w!=0)
{
{
edge[e].v=i;
edge[e].u=j;
edge[e].w=w;
e++; } }
cout<<"boshlang‘ich tugun > "; cin>>start;
cout<<"qisqa masofalar ro‘yhati:";
bellman_ford(n, start-1);
system("pause>>void"); }
Bu yerda graf soddalashtirilgan qirralar ro‘yhati ko‘rinishida ifodalangan va
foydalanuvchi tomonidan vazn matrisasi kiritiladi. Bellman-Ford algoritmining
asosiy qismi m*(n-1) marta bajariladi, tashqi sik n-1 marta takrorlanadi, ichki sikl
esa m marta. N-iterasiyadan voz kechish esa maqsadga muvofiqdir, chunki
algoritm n-1 ta iterasiyada ham o‘z vazifasini to‘liq amalga oshira oladi. Ammo
tashqi siklni n marta amalga oshirish grafda manfiy sikl mavjudligini aniqlashga
imkon beradi.
Floyd-Uorshell algoritmi
Bu usulning nomlanishi 1962 yilda bir vaqtning o‘zida kashf etgan ikkita
amerikalik tadqiqotchilar Robert Floyd va Stiven Uorshell sharafiga qo‘yilgan.
Nomlanishning boshqa variantlari kamroq tarqalgan: Roy - Uorshall algoritmi yoki
Roy - Floyd algoritmi. Roy - bu algoritmni hamkasblaridan 3 yil oldin (1959 yilda)
ishlab chiqqan professorning familiyasidir, ammo uning kashfiyoti nashr qilimay
qolgan. Floyd-Uorshell algoritmi – grafning har bir tugunigacha bo‘lgan qisqa
masofalarni hisoblashning dinamik algoritmidir. Bu metodni musbat va manfiy
vaznga ega bo‘lgan graflarda qo‘llash mumkin, faqat manfiy sikllardan tashqari.
Shu sababli oldin ko‘rib o‘tilgan Deykstra algoritmiga qaraganda umumiyroq
46](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_46.png)
![hisoblanadi. Floyd-Uorshell algoritmini amalga oshirish uchun har bir tuguni 1 dan
|V| gacha nomerlangan G=(V,E) grafning qo‘shma matrisasi D[][] ni tashkil
etamiz. Bu matrisa |V|x|V| o‘lchamga ega bo‘ladi va har bir D[i][j] elementga i dan
j gacha bo‘lgan qirralarning vazni o‘zlashtiriladi. Algoritm bajarilishi mobaynida
ushbu matrisa qayta yoziladi: uning har bir yacheykasiga i tugundan j tugungacha
hisoblangan eng optimal, qisqa masofa yoziladi. Endi algoritmning asosiy qismini
tuzishdan oldin, eng qisqa yo‘llarning matritsasi tarkibini tushunish kerak. Uning
har bir elementi D[i][j] mavjud bo‘lgan marshrutlarning eng kichikini o‘z ichiga
olishi kerakligi sababli, biz darhol ayta olamizki, yagona tugundan uchun u nolga
teng, hattoki pastadir (manfiy sikllar hisobga olinmaydi), shuning uchun asosiy
diagonalning barcha elementlari (D[i][i]) ni 0 qilish kerak.
Diagonalda bo‘lmagan 0 qiymatli elementlar (matrisaning i va j tugunlari
o‘rtasida bevosita qirra mavjud bo‘lmagan joylarida nollar bo‘lishi mumkin)
ularning qiymatini iloji boricha o‘zgartirish uchun biz ularni cheksizlik bilan
tenglashtiramiz, bu dasturda bo‘lishi mumkin, masalan, grafda mumkin bo‘lgan
maksimal yo‘l, yoki shunchaki katta son. Algoritmning uchta - sikl, ifoda va shartli
operatordan iborat asosiy qismi juda ixcham tarzda yoziladi:
- k=1 dan |V| gacha bajariladi
- i=1 dan |V| gacha bajariladi
- j=1 dan |V| gacha bajariladi
- agar D[i][k]+D[k][j]<D[i][j] bo‘lsa, u holda D[i][j] ←D[i][k]+D[k][j]
i tugunidan j tugunigacha eng qisqa yo‘l ular orqali va boshqa tugunlar
to‘plamidan o‘tishi mumkin k ∈ (1, ..., |V|). i dan j gacha bo‘lgan yo‘l k tugundan
o‘tishi yoki o‘tmasligi ham mumkin. Agar boshqa yo‘l mavjud bo‘lsa, u i dan k ga,
keyin k dan j gacha o‘tishini anglatadi, shuning uchun u qisqa yo‘lning qiymati
D[i][j] ni D[i][k] + D[k][j] yig‘indi bilan almashtirish kerak.
Floyd-Worshell algoritmining to‘liq kodini C ++ va Paskalda ko‘rib chiqamiz
va keyin u bajaradigan harakatlar ketma-ketligini batafsil tahlil qilamiz.
47](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_47.png)
![C++ da dastur kodi:
#include "stdafx.h"
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
// Floyd-Uorshall algoritmi
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<V; i++) D[i][i]=0;
for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];
for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
} }
// asosiy funksiyasi
void main()
{
setlocale(LC_ALL, "Rus");
cout<<" Grafdagi uchlar soni > "; cin>>n;
cout<<" Kenar og‘irlik matritsasini kiriting:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";
cin>>GR[i][j];
}
cout<<" Eng qisqa yo‘l matritsasi:"<<endl;
FU(GR, n);
system("pause>>void");
}
Tasavvur qilaylik, har bir elementi vazn haqida ma’lumot saqlovchi qo‘shma
matritsa quyidagicha berilgan bo‘lsin:
48](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_48.png)
![Quyidagi grafda tugunlar soni 3 ga teng va u quyidagi matrisa bilan berilgan.
Algoritm masalasi:
Matrisani shunday qayta yozish kerakki, undagi har bir element i va j tugun
orasidagi qirra vaznini emas, balki I dan j gacha qisqa yo‘l vaznini saqlasin. Misol
uchun kichik bir graf olamiz. Shu sababli undagi qiymatlar deyarli o‘zgarmasligi
ham mumkin. Ammo dastur narijasida unda 2ta element qiymati almashganligini
ko‘rish mumkin.
Ushbu jadvalda algoritmning asosiy qismini ifodalovchi 27ta bosqichi
keltirilgan. Usulning bajarilish vaqti O(|V| 3
) bo‘lganligi sababli bosqichlar soni
shunchalik ko‘p. Graf 3 ta tugunga ega va 3 3
=27 ga teng. Birinchi o‘zgarish k = 1, i
= 2 va j = 3 bo‘lgandagi iteratsiyada sodir bo‘ladi. Bunda D[2][1]=1, D[1][3]=2,
D[2][3]=4. Shart to‘g‘ri, ya'ni D[1][3] + D[3][2] = 3 va 3 <4, shuning uchun D[2]
[3] matritsa elementi yangi qiymat oladi. Keyingi qadam, shart bajarilganda
ikkinchi satr va uchinchi ustunda joylashgan elementga haqiqatan ham o‘zgarishlar
kiritiladi.
2.4 Graflar ustida amallar bajarish dasturiy ta’minoti
Ushbu dasturiy ta’minotni yaratishda men Java dasturlash tilidan
foydalandim. Ushbu dasturiy ta’minot kompyuterlarda foydalanish uchun
muljallangan bo‘lib vizuallashgan qulay interfeysga ega. Ushbu dasturiy
49](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_49.png)
![ta’minotga men “graflar ustida amallar bajarish dasturi” deb nom berdim. Dasturiy
ta’minotning asosiy kurinishi quyidagicha.
Dasturiy ta’minotni yaratishda vizuallashgan qulay interfeysga ega bo‘lishi
uchun ko‘proq e’tibor qaratganman
Asosiy oyna sarloha satri, menyular satri va asosiy ish maydoniga bo‘lingan.
Ushbu dasturiy ta’minotda graf tugunlarini yaratish juda oson. Shunchaki
sichqonchani ish maydoniga olib kelinadi va chap tugmasi bir marta bosiladi.
Shundan sung dasturiy ta’minot shu joyning kordinatalarida graf tuguni bor deb
qabul qiladi va belgilab quyadi. Yaratilgan tugunlarni sozlash uchun ham barcha
parametrlar kuritilgan. Tugun parametrlaridan foydalanish uchun ish maydonidagi
chap tomonda joylashgan uskunalar ichida ranglarni ifodalaydigan piktogrammasi
bosiladi va shu yerda tugun parametrlari mavjud bo‘lib ulardan foydalanishimiz
mumkin bo‘ladi. Bundan tashqari ortiqcha tugun belgilasak uning ustida ham
amallar bajarishimiz mumkin yani usha tugunni ustiga sichqonchaning o‘ng
50](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_50.png)
![tugmasi bosiladi va kontes menyusi orqali kerakli amallar bajariladi. Bularni
quyida kurishimiz mumkin.
Endi yaratgan tugunlarimiz orqali yul yani qirra yaratishni kurib chiqamiz.
Buning uchun ish maydonidagi chap tomonda joylashgan uskunalar ichida
sozlashni ifodalaydigan piktogrammasi bosiladi. Bu yerda graf harakatlarini
tahrirlash uskunalari mavjud. Ular yordamida graf yullar (qirralari yaratiladi).
Bunga quyida misol keltiramiz
51](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_51.png)
![Tugunlarni yaratib bo‘lgach biz to‘liq graf yarating tugmasini bossak
yuqoridagi kabi to‘liq grafni yaratib beradi bizga. Yaratilgan qirralarnig kurinishi
boshqarish tugunlar kurinishini boshqarish kabi ish maydonidagi chap tomonda
joylashgan uskunalar ichida ranglarni ifodalaydigan piktogrammasidan
foydalanilgan holda amalga oshiriladi
Yuqorida grafni yaratib olding endi ixtiyoriy ikki tugun orasifagi eng qisqa
masofani aniqlash masalasini kurib chiqamiz. Bu masalani qichish uchun ish
maydonidagi o‘ng tarafdagi uskunalar ichidan qurishni ifodalaydigan
piktogrammani bosamiz va u yerdan uzimizga kerakli algoritmni tanlaymiz. Hozir
52](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_52.png)
![eng qishqa masofa algoritmini tanladik va boshlanish va tugash tugunlarini
kuritamiz o‘ngra boshlash tugmasini bossak bizga tanlangan ikkita tugun orasidagi
eng qisqa masofani aniqlab beradi dasturiy ta’minotimiz. Bunga quyida misol
keltiramiz.
Bu yerda biz boshlang‘ich va oxirgi mashrutlar sifatida mos ravishda 1 va 9-
tugunlarni oldik. Ushbu men yaratgan dasturiy ta’minot
53](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_53.png)
![Xulosa
Bitiruv malakaviy ishida transport logistikasi, graflar nazariyasi va transport
logistikasida graflar nazariyasining qullanilish modellar bilan tanishib chiqildi
hamda bu modellardan foydalanilgan holda graflar nazariyasi ustida amallarni
bajarish dasturiy ta’minoti yaratildi..
Bu dasturiy ta’minotdan foydalanib, turli xil graflar ustida amallarni bajarish
mumkin, bu graflar ustida amallarni bajarish tatbig‘ini transport logistikasida
qullash orqali logistikadan foydalanishning anchagina optimal yullarini aniqlash
mumki. Bu esa o‘z navbatida transport harajatlarining anchagina qisqarishiga olib
keladi. Dasturiy ta’minot yordamida olingan graflar nazariyasi transport
logistikasini optimal rejalashtirish va optimal daromad olishning yechimi bo‘ladi,
ya’ni maqsad funksiyasining maksimumi optimal daromad olishga va shu
funksiyani maksimumga yetishtiruvchi o‘zgaruvchilarning qiymati optimal
rejalarga mos keladi.
Ishda olingan natijalar va unda qo‘llanilgan usullardan turli iqtisodiy,
ijtimoiy sohalarning ko‘pgina amaliy masalalari, jumladan, transport logistikasini
samarali rejalashtirish va daromad olishni tadqiq qilishda, ularning dasturiy
ta’minotini yaratishda, “Jarayonlar tadqiqoti”, “Transport logistikasi” va shu kabi
fanlarining amaliy mashg‘ulotlari o‘quv jarayonlarida dasturiy vosita sifatida
foydalanish mumkin.
54](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_54.png)
![Foydalanilgan adabiyotlar
1. Вагнер Г. Основы исследований операции. Т. 1–3. М.: Мир. 1972-73.
2. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир,
1974.
3. Зайченко Ю. Б. Исследование операций. Киев. 1979.
4. Таха Х. Введение в исследование операций. Т. 1, 2. М.: Мир. 1981.
5. Q. Safayeva. Matematik dasturlash. Darslik. TMI-2003y.
6. Волков И. К., Загоруйко Е. А. Исследование операций. М.:Изд. МГТУ
им. Н. Э. Баумана.- 2000.
7. Конюховский П. В. Математические методы исследования операций.
Ст. Петербург. Изд. Питер.- 2001.
8. Вентцель Е. С. Исследование операций. Задачи, принципы,
методология. М.: Высшая школа.- 2001.
9. Афанасьев М. Ю., Суворов Б. П. Исследование операций в экономике:
модели, задачи, решения. М.: Инфра – М.- 2003.
10. PHP 7 Д. В. Котеров И. В. Симдянов СПб.: БХВ – Петербург, 2016. -
1088
11. . https://www.w3schools.com/java/default.asp
55](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_55.png)
![Ilovalar
_____________________________________________________________________________
____
AlgorithmView.fxml
<?xml version="1.0" encoding="UTF-8"?>
<?import javafx.geometry.Insets?>
<?import javafx.scene.control.Button?>
<?import javafx.scene.control.ChoiceBox?>
<?import javafx.scene.control.Label?>
<?import javafx.scene.control.TextField?>
<?import javafx.scene.control.Tooltip?>
<?import javafx.scene.layout.HBox?>
<?import javafx.scene.layout.VBox?>
<?import javafx.scene.text.Font?>
<?import org.controlsfx.control.ToggleSwitch?>
<?import org.kordamp.ikonli.javafx.FontIcon?>
<VBox alignment="CENTER" minWidth="0.0" prefWidth="250.0" spacing="3.0"
xmlns="http://javafx.com/javafx/17"
xmlns:fx="http://javafx.com/fxml/1"
fx:controller="com.todense.view.AlgorithmView">
<padding>
<Insets bottom="7.0" left="7.0" right="7.0" top="7.0"/>
</padding>
<Label alignment="CENTER" prefHeight="13.0" prefWidth="190.0"
styleClass="darkLabel" text="Algoritm"
textFill="#2c2c2c">
<font>
<Font size="9.0"/>
</font>
</Label>
<ChoiceBox fx:id="algorithmChoiceBox" maxWidth="1.7976931348623157E308"
minHeight="-Infinity" minWidth="-Infinity">
<VBox.margin>
<Insets bottom="5.0"/>
</VBox.margin>
</ChoiceBox>
<VBox fx:id="optionsParentVBox" alignment="CENTER">
<VBox.margin>
<Insets bottom="7.0"/>
</VBox.margin>
<Label alignment="CENTER" prefHeight="13.0" prefWidth="190.0"
styleClass="darkLabel" text="Variantlar"
textFill="#2c2c2c">
<font>
<Font size="9.0"/>
</font>
56](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_56.png)
![<VBox.margin>
<Insets bottom="2.0" top="5.0"/>
</VBox.margin>
</Label>
<VBox fx:id="optionsVBox" alignment="TOP_CENTER"
maxHeight="1.7976931348623157E308"
maxWidth="1.7976931348623157E308" minWidth="-Infinity"
spacing="3.0" styleClass="subsection">
<ToggleSwitch fx:id="hcConnToggleSwitch" alignment="CENTER"
contentDisplay="CENTER" graphicTextGap="0.0"
maxWidth="1.7976931348623157E308" selected="true"
text="Ulanishni tekshiring">
<font>
<Font size="10.0"/>
</font>
<VBox.margin>
<Insets left="5.0" right="5.0" top="2.0"/>
</VBox.margin>
</ToggleSwitch>
</VBox>
</VBox>
<HBox fx:id="startingNodeHBox" alignment="CENTER"
maxWidth="1.7976931348623157E308" minWidth="-Infinity"
spacing="3.0" VBox.vgrow="ALWAYS">
<Label maxHeight="1.7976931348623157E308"
maxWidth="1.7976931348623157E308" minWidth="-Infinity"
text="Start node" HBox.hgrow="ALWAYS">
<font>
<Font size="10.0"/>
</font>
</Label>
<TextField fx:id="startNodeTextField" alignment="CENTER"
editable="false" maxHeight="1.7976931348623157E308"
maxWidth="1.7976931348623157E308" minHeight="-Infinity"
prefWidth="20.0" text="Belgilanmagan"
HBox.hgrow="ALWAYS">
<font>
<Font size="10.0"/>
</font>
</TextField>
<VBox.margin>
<Insets left="5.0" right="5.0"/>
</VBox.margin>
</HBox>
<HBox fx:id="goalNodeHBox" alignment="CENTER" minWidth="-Infinity"
spacing="3.0" VBox.vgrow="ALWAYS">
<Label maxHeight="1.7976931348623157E308"
maxWidth="1.7976931348623157E308" text="tugash tuguni"
HBox.hgrow="ALWAYS">
57](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_57.png)
![<font>
<Font size="10.0"/>
</font>
</Label>
<TextField fx:id="goalNodeTextField" alignment="CENTER"
editable="false" maxWidth="1.7976931348623157E308"
minWidth="-Infinity" prefWidth="20.0" text="Belgilanmagan"
HBox.hgrow="ALWAYS">
<font>
<Font size="10.0"/>
</font>
</TextField>
<VBox.margin>
<Insets left="5.0" right="5.0"/>
</VBox.margin>
</HBox>
<Label alignment="CENTER" prefHeight="13.0" prefWidth="190.0"
styleClass="darkLabel" text="Vizual tasvirlar"
textFill="#2c2c2c">
<font>
<Font size="9.0"/>
</font>
<VBox.margin>
<Insets top="5.0"/>
</VBox.margin>
</Label>
<VBox fx:id="algorithmsVBox1" alignment="CENTER"
maxWidth="1.7976931348623157E308" styleClass="subsection"
VBox.vgrow="ALWAYS">
<HBox layoutX="21.0" layoutY="62.0" maxWidth="1.7976931348623157E308"
VBox.vgrow="ALWAYS">
<ToggleSwitch fx:id="endpointsToggleSwitch"
contentDisplay="CENTER" maxWidth="1.7976931348623157E308"
minWidth="-Infinity" selected="true" text="Yakuniy
nuqtalarni ko‘rsatish" HBox.hgrow="ALWAYS">
<font>
<Font size="10.0"/>
</font>
<HBox.margin>
<Insets left="5.0" right="5.0"/>
</HBox.margin>
</ToggleSwitch>
</HBox>
</VBox>
<HBox alignment="CENTER" maxWidth="-Infinity" minWidth="-Infinity"
spacing="3.0">
<Button fx:id="algorithmStartButton" alignment="CENTER"
mnemonicParsing="false" onAction="#startAlgorithmAction"
prefHeight="25.0" prefWidth="140.0" text="Boshlash">
58](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_58.png)
![<graphic>
<FontIcon iconColor="#08ae34" iconLiteral="fas-play"
styleClass="start-icon"/>
</graphic>
<font>
<Font size="11.0"/>
</font>
</Button>
<Button minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" onAction="#stopAlgorithmAction"
prefHeight="25.0" prefWidth="25.0">
<font>
<Font size="11.0"/>
</font>
<graphic>
<FontIcon iconColor="#e14444" iconLiteral="fas-stop"
iconSize="15" selectionStart="0"
styleClass="stop-icon"/>
</graphic>
<tooltip>
<Tooltip showDelay="0.1s" text="To‘xtatish"/>
</tooltip>
</Button>
<VBox.margin>
<Insets top="10.0"/>
</VBox.margin>
</HBox>
</VBox>
_____________________________________________________________________________
____
BackgroundPopOverView.fxml
<?xml version="1.0" encoding="UTF-8"?>
<?import javafx.geometry.Insets?>
<?import javafx.scene.control.Button?>
<?import javafx.scene.layout.VBox?>
<?import javafx.scene.text.Font?>
<VBox fx:id="nodeVBox" alignment="CENTER" maxHeight="-Infinity" maxWidth="-Infinity" minWidth="-
Infinity"
prefWidth="130.0" spacing="5.0" xmlns="http://javafx.com/javafx/11.0.1"
xmlns:fx="http://javafx.com/fxml/1"
fx:controller="com.todense.view.BackgroundPopOverView">
<padding>
<Insets bottom="5.0" top="5.0"/>
</padding>
<Button maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false"
onAction="#pasteAction" prefHeight="25.0" prefWidth="120.0" text="Subgrafni joylashtirish">
59](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_59.png)
![<font>
<Font size="10.0"/>
</font>
</Button>
</VBox>
_____________________________________________________________________________
____
MainView.fxml
<?xml version="1.0" encoding="UTF-8"?>
<?import java.lang.String?>
<?import javafx.geometry.Insets?>
<?import javafx.scene.control.Button?>
<?import javafx.scene.control.ColorPicker?>
<?import javafx.scene.control.Label?>
<?import javafx.scene.control.Menu?>
<?import javafx.scene.control.MenuBar?>
<?import javafx.scene.control.MenuItem?>
<?import javafx.scene.control.ProgressIndicator?>
<?import javafx.scene.control.ScrollPane?>
<?import javafx.scene.control.Separator?>
<?import javafx.scene.control.SplitPane?>
<?import javafx.scene.control.TextArea?>
<?import javafx.scene.control.ToggleButton?>
<?import javafx.scene.control.Tooltip?>
<?import javafx.scene.input.KeyCodeCombination?>
<?import javafx.scene.layout.AnchorPane?>
<?import javafx.scene.layout.ColumnConstraints?>
<?import javafx.scene.layout.GridPane?>
<?import javafx.scene.layout.HBox?>
<?import javafx.scene.layout.Pane?>
<?import javafx.scene.layout.RowConstraints?>
<?import javafx.scene.layout.VBox?>
<?import javafx.scene.text.Font?>
<?import org.kordamp.ikonli.javafx.FontIcon?>
<VBox alignment="CENTER" prefHeight="617.0" prefWidth="1357.0"
xmlns="http://javafx.com/javafx/17" xmlns:fx="http://javafx.com/fxml/1"
fx:controller="com.todense.view.MainView">
<VBox>
<HBox alignment="CENTER" style="-fx-background-color: fx-darker; -fx-
border-width: 0 0 1 0; -fx-border-color: fx-light;">
<MenuBar>
<Menu mnemonicParsing="false" text="File">
<MenuItem mnemonicParsing="false" onAction="#openAction"
text="Grafni ochish...">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fas-folder-
open" iconSize="15" />
60](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_60.png)
![</graphic>
<accelerator>
<KeyCodeCombination alt="UP" code="O" control="DOWN"
meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
<MenuItem mnemonicParsing="false" onAction="#saveAction"
text="Grafni saqlash...">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fas-save"
iconSize="15" />
</graphic>
<accelerator>
<KeyCodeCombination alt="UP" code="S" control="DOWN"
meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
</Menu>
<Menu mnemonicParsing="false" text="Graph">
<MenuItem mnemonicParsing="false" onAction="#resetAction"
text="Qayta o‘rnatish">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="icm-loop2"
iconSize="15" />
</graphic>
<accelerator>
<KeyCodeCombination alt="UP" code="R" control="DOWN"
meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
<MenuItem mnemonicParsing="false" onAction="#deleteAction"
text="O‘chirish">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="icm-bin"
iconSize="15" />
</graphic>
<accelerator>
<KeyCodeCombination alt="UP" code="DELETE"
control="DOWN" meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
<MenuItem mnemonicParsing="false"
onAction="#randomGraphAction" text="Tasodifiy graf yaratish">
<accelerator>
<KeyCodeCombination alt="UP" code="Q" control="DOWN"
meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
61](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_61.png)
![<MenuItem mnemonicParsing="false"
onAction="#presetGraphAction" text="Oldindan yaratish">
<accelerator>
<KeyCodeCombination alt="UP" code="E" control="DOWN"
meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
</Menu>
<Menu mnemonicParsing="false" text="Camera">
<MenuItem mnemonicParsing="false" onAction="#adjustAction"
text="Kamerani grafaga sozlang">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fa-
crosshairs" iconSize="15" />
</graphic>
<accelerator>
<KeyCodeCombination alt="UP" code="J" control="DOWN"
meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
</Menu>
<Menu mnemonicParsing="false" text="Window">
<MenuItem fx:id="fullScreenItem" mnemonicParsing="false"
onAction="#fullScreenAction" text="To‘liq ekran">
<graphic>
<FontIcon fx:id="fullScreenIcon" iconColor="#d0d0d0"
iconLiteral="fas-expand-arrows-alt" iconSize="15" />
</graphic>
<accelerator>
<KeyCodeCombination alt="UP" code="F11" control="DOWN"
meta="UP" shift="UP" shortcut="UP" />
</accelerator>
</MenuItem>
</Menu>
<Menu mnemonicParsing="false" text="Help">
<MenuItem mnemonicParsing="false" onAction="#helpAction"
text="Foydalanuvchi uchun qoʻllanma">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fa-question"
iconSize="15" />
</graphic>
</MenuItem>
</Menu>
</MenuBar>
<HBox HBox.hgrow="ALWAYS" />
<ColorPicker fx:id="appColorPicker" prefHeight="22.0"
prefWidth="31.0" styleClass="app-color-picker">
<HBox.margin>
<Insets right="2.0" />
62](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_62.png)
![</HBox.margin>
<tooltip>
<Tooltip text="App Theme" />
</tooltip>
</ColorPicker>
</HBox>
</VBox>
<SplitPane dividerPositions="0.861646234676007" orientation="VERTICAL"
VBox.vgrow="ALWAYS">
<HBox alignment="CENTER">
<VBox alignment="CENTER" prefHeight="200.0" prefWidth="50.0"
spacing="3.0" style="-fx-background-color: fx-darker;">
<ToggleButton fx:id="graphAppearanceMenuButton" maxHeight="-
Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" prefHeight="40.0" prefWidth="40.0"
styleClass="sidemenu-button">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fas-palette"
iconSize="20" />
</graphic>
<font>
<Font size="6.0" />
</font>
<VBox.margin>
<Insets left="5.0" right="5.0" />
</VBox.margin>
</ToggleButton>
<Separator prefWidth="200.0">
<VBox.margin>
<Insets left="10.0" right="10.0" />
</VBox.margin>
</Separator>
<ToggleButton fx:id="generateGraphMenuButton" layoutX="17.0"
layoutY="253.0" maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-
Infinity" minWidth="-Infinity" mnemonicParsing="false" prefHeight="40.0"
prefWidth="40.0" styleClass="sidemenu-button">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="ci-development"
iconSize="23" />
</graphic>
<font>
<Font size="6.0" />
</font>
</ToggleButton>
<Separator layoutX="20.0" layoutY="408.0" prefWidth="200.0">
<VBox.margin>
<Insets left="10.0" right="10.0" />
</VBox.margin>
</Separator>
63](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_63.png)
![<ToggleButton fx:id="operationsMenuButton" layoutX="17.0"
layoutY="165.0" maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-
Infinity" minWidth="-Infinity" mnemonicParsing="false" prefHeight="40.0"
prefWidth="40.0" styleClass="sidemenu-button">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fas-tools"
iconSize="20" />
</graphic>
<font>
<Font size="6.0" />
</font>
</ToggleButton>
<Separator layoutX="20.0" layoutY="228.0" prefWidth="200.0">
<VBox.margin>
<Insets left="10.0" right="10.0" />
</VBox.margin>
</Separator>
<ToggleButton fx:id="propertiesMenuButton" maxHeight="-Infinity"
maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" prefHeight="40.0" prefWidth="40.0"
styleClass="sidemenu-button">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="icm-stats-bars"
iconSize="20" />
</graphic>
<VBox.margin>
<Insets left="5.0" right="5.0" />
</VBox.margin>
</ToggleButton>
</VBox>
<GridPane prefHeight="181.0" prefWidth="790.0" HBox.hgrow="ALWAYS">
<columnConstraints>
<ColumnConstraints hgrow="SOMETIMES" minWidth="10.0"
prefWidth="100.0" />
</columnConstraints>
<rowConstraints>
<RowConstraints minHeight="10.0" prefHeight="30.0"
vgrow="SOMETIMES" />
</rowConstraints>
<AnchorPane fx:id="mainAnchor" maxHeight="1.7976931348623157E308"
maxWidth="1.7976931348623157E308" minHeight="0.0" minWidth="0.0"
prefHeight="0.0" prefWidth="0.0" GridPane.hgrow="ALWAYS"
GridPane.vgrow="ALWAYS">
<fx:include source="CanvasView.fxml" />
<HBox fx:id="leftContentHBox" alignment="CENTER"
AnchorPane.bottomAnchor="0.0" AnchorPane.leftAnchor="0.0"
AnchorPane.topAnchor="0.0">
<padding>
64](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_64.png)
![<Insets bottom="-1.0" left="-1.0" right="-1.0" top="-
1.0" />
</padding>
<ScrollPane fx:id="leftSideMenuContentScrollPane"
fitToWidth="true" minWidth="0.0" HBox.hgrow="ALWAYS">
<padding>
<Insets right="-1.0" />
</padding>
<VBox fx:id="leftSideMenuContentBox"
alignment="TOP_CENTER" minWidth="0.0" spacing="10.0">
<fx:include fx:id="graphAppearanceView"
source="GraphView.fxml" />
<fx:include fx:id="backgroundAppearanceView"
source="BackgroundView.fxml" />
<fx:include fx:id="propertiesView"
source="PropertiesView.fxml" />
<fx:include fx:id="operationsView"
source="OperationsView.fxml" />
<fx:include fx:id="randomGeneratorView"
source="RandomGeneratorView.fxml" />
<fx:include fx:id="presetGeneratorView"
source="PresetCreatorView.fxml" />
</VBox>
</ScrollPane>
<Pane fx:id="leftResizeHandle" maxWidth="-Infinity"
minWidth="-Infinity" prefWidth="4.0" style="-fx-background-color: fx-darker;"
/>
</HBox>
<HBox fx:id="rightContentHBox" alignment="CENTER_RIGHT"
AnchorPane.bottomAnchor="0.0" AnchorPane.rightAnchor="0.0"
AnchorPane.topAnchor="0.0">
<padding>
<Insets bottom="-1.0" left="-1.0" right="-1.0" top="-
1.0" />
</padding>
<Pane fx:id="rightResizeHandle" maxWidth="-Infinity"
minWidth="-Infinity" prefWidth="5.0" style="-fx-background-color: fx-darker;"
/>
<ScrollPane fx:id="rightSideMenuContentScrollPane"
fitToWidth="true" minWidth="0.0" prefHeight="432.0" prefWidth="252.0"
HBox.hgrow="ALWAYS">
<padding>
<Insets left="-1.0" />
</padding>
<VBox fx:id="rightSideMenuContentBox"
alignment="TOP_CENTER" minWidth="0.0">
<fx:include fx:id="basicAlgorithmsView"
source="AlgorithmView.fxml" />
<fx:include fx:id="tspView" source="AntsView.fxml" />
65](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_65.png)
![<fx:include fx:id="layoutView"
source="LayoutView.fxml" />
</VBox>
</ScrollPane>
</HBox>
</AnchorPane>
</GridPane>
<VBox alignment="CENTER" prefWidth="50.0" style="-fx-background-
color: fx-darker;">
<ToggleButton fx:id="basicAlgorithmsMenuButton" maxHeight="-
Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" prefHeight="40.0" prefWidth="40.0"
styleClass="sidemenu-button">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fas-shapes"
iconSize="20" />
</graphic>
<font>
<Font size="6.0" />
</font>
</ToggleButton>
<Separator layoutX="20.0" layoutY="248.0" prefWidth="200.0">
<VBox.margin>
<Insets left="10.0" right="10.0" top="5.0" />
</VBox.margin>
</Separator>
<ToggleButton fx:id="layoutMenuButton" layoutX="17.0"
layoutY="166.0" maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-
Infinity" minWidth="-Infinity" mnemonicParsing="false" prefHeight="40.0"
prefWidth="40.0" styleClass="sidemenu-button">
<font>
<Font size="6.0" />
</font>
<VBox.margin>
<Insets top="5.0" />
</VBox.margin>
<graphic>
<Pane maxHeight="-Infinity" maxWidth="-Infinity"
minHeight="-Infinity" minWidth="-Infinity" prefHeight="25.0"
prefWidth="22.0">
<styleClass>
<String fx:value="layout-icon" />
<String fx:value="custom-icon" />
</styleClass>
</Pane>
</graphic>
</ToggleButton>
<Separator layoutX="20.0" layoutY="205.0" prefWidth="200.0">
<VBox.margin>
66](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_66.png)
![<Insets left="10.0" right="10.0" top="5.0" />
</VBox.margin>
</Separator>
<ToggleButton fx:id="tspMenuButton" layoutX="17.0"
layoutY="206.0" maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-
Infinity" minWidth="-Infinity" mnemonicParsing="false" prefHeight="40.0"
prefWidth="40.0" styleClass="sidemenu-button">
<font>
<Font size="6.0" />
</font>
<VBox.margin>
<Insets bottom="5.0" top="5.0" />
</VBox.margin>
<graphic>
<Pane maxHeight="-Infinity" maxWidth="-Infinity"
minHeight="-Infinity" minWidth="-Infinity" prefHeight="25.0"
prefWidth="22.0">
<styleClass>
<String fx:value="tsp-icon" />
<String fx:value="custom-icon" />
</styleClass>
</Pane>
</graphic>
</ToggleButton>
</VBox>
</HBox>
<HBox alignment="CENTER" spacing="3.0"
SplitPane.resizableWithParent="false">
<SplitPane dividerPositions="0.31411677753141165" prefHeight="160.0"
prefWidth="200.0" HBox.hgrow="ALWAYS">
<TextArea fx:id="eventTextArea" editable="false"
focusTraversable="false" scrollLeft="10.0" scrollTop="10.0" wrapText="true">
<opaqueInsets>
<Insets />
</opaqueInsets>
</TextArea>
<HBox alignment="TOP_CENTER" fillHeight="false"
prefWidth="925.0">
<padding>
<Insets right="50.0" />
</padding>
<VBox alignment="TOP_CENTER" prefHeight="200.0">
<HBox.margin>
<Insets />
</HBox.margin>
<padding>
<Insets top="-2.0" />
</padding>
67](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_67.png)
![<HBox alignment="CENTER" fillHeight="false" spacing="2.0"
style="-fx-border-insets: 1 1 1 1; -fx-border-color: fx-light; -fx-border-
width: 0 1 1 1; -fx-border-radius: 2;">
<padding>
<Insets bottom="3.0" left="3.0" right="3.0" top="3.0"
/>
</padding>
<VBox.margin>
<Insets />
</VBox.margin>
<ToggleButton fx:id="eraseModeToggleButton" maxHeight="-
Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" prefHeight="22.0" prefWidth="22.0">
<graphic>
<FontIcon iconColor="#d0d0d0" iconLiteral="fas-
trash-alt" iconSize="16" />
</graphic>
<tooltip>
<Tooltip showDelay="0.1s" text="Oʻchirish
rejimi" />
</tooltip>
</ToggleButton>
<ToggleButton fx:id="lockToggleButton" maxHeight="-
Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" prefHeight="22.0" prefWidth="22.0">
<graphic>
<FontIcon fx:id="lockIcon" iconColor="#d0d0d0"
iconLiteral="fa-unlock" iconSize="18" />
</graphic>
<tooltip>
<Tooltip showDelay="0.1s" text="Bloklangan rejimni
tahrirlash" />
</tooltip>
<HBox.margin>
<Insets />
</HBox.margin>
</ToggleButton>
</HBox>
<Label style="-fx-font-size: 11; -fx-text-fill: gray;"
text="Modes">
<font>
<Font size="10.0" />
</font>
<padding>
<Insets top="-2.0" />
</padding>
</Label>
</VBox>
<VBox alignment="TOP_CENTER" prefHeight="200.0">
68](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_68.png)
![<padding>
<Insets top="-2.0" />
</padding>
<HBox.margin>
<Insets left="10.0" />
</HBox.margin>
<HBox alignment="CENTER" fillHeight="false" spacing="2.0"
style="-fx-border-insets: 1 1 1 1; -fx-border-color: fx-light; -fx-border-
width: 0 1 1 1; -fx-border-radius: 2;">
<padding>
<Insets bottom="3.0" left="1.0" right="3.0" top="3.0"
/>
</padding>
<ToggleButton fx:id="pauseButton" minHeight="-Infinity"
minWidth="-Infinity" mnemonicParsing="false" prefHeight="22.0"
prefWidth="22.0" textAlignment="CENTER">
<font>
<Font size="10.0" />
</font>
<graphic>
<FontIcon iconColor="#bfbfbf" iconLiteral="fas-
pause" />
</graphic>
<tooltip>
<Tooltip showDelay="0.1s" text="Pauza
(Ctrl+Space)" />
</tooltip>
</ToggleButton>
<Button minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" onAction="#nextStepAction" prefHeight="22.0"
prefWidth="22.0">
<font>
<Font size="10.0" />
</font>
<graphic>
<FontIcon iconColor="#bfbfbf" iconLiteral="fas-
step-forward" />
</graphic>
<tooltip>
<Tooltip showDelay="0.1s" text="Keyingi qadam
(Ctrl+Right)" />
</tooltip>
<HBox.margin>
<Insets />
</HBox.margin>
</Button>
<Button fx:id="stopButton" disable="true" minHeight="-
Infinity" minWidth="-Infinity" mnemonicParsing="false" onAction="#stopAction"
prefHeight="22.0" prefWidth="22.0">
69](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_69.png)
![<font>
<Font name="Font Awesome 5 Free Regular"
size="11.0" />
</font>
<graphic>
<FontIcon iconColor="#e14444" iconLiteral="fas-
stop" iconSize="14" selectionStart="0" styleClass="stop-icon" />
</graphic>
<tooltip>
<Tooltip showDelay="0.1s" text="Joriy algoritmni
to‘xtatish (Ctrl+Backspace)" />
</tooltip>
</Button>
</HBox>
<Label style="-fx-font-size: 11; -fx-text-fill: gray;"
text="Ishga tushirish">
<font>
<Font size="10.0" />
</font>
<padding>
<Insets top="-2.0" />
</padding>
</Label>
</VBox>
<VBox alignment="CENTER" layoutX="525.0" layoutY="10.0">
<padding>
<Insets top="-2.0" />
</padding>
<HBox.margin>
<Insets left="10.0" />
</HBox.margin>
<HBox alignment="CENTER" fillHeight="false" maxHeight="-
Infinity" prefHeight="24.0" spacing="2.0" style="-fx-border-insets: 1 1 1 1;
-fx-border-color: fx-light; -fx-border-width: 0 1 1 1; -fx-border-radius:
2;">
<padding>
<Insets bottom="3.0" left="3.0" right="3.0" top="3.0"
/>
</padding>
<VBox.margin>
<Insets />
</VBox.margin>
<ToggleButton fx:id="animationToggleButton" maxHeight="-
Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" prefHeight="22.0" prefWidth="40.0">
<graphic>
<FontIcon iconLiteral="fas-film" iconSize="18"
selectionEnd="1" wrappingWidth="15.5" />
</graphic>
70](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_70.png)
![<tooltip>
<Tooltip text="Animatsiyalarni ko‘rsatish" />
</tooltip>
</ToggleButton>
<HBox fx:id="animationHBox" />
</HBox>
<Label style="-fx-font-size: 11; -fx-text-fill: gray;"
text="Vizualizatsiya">
<font>
<Font size="10.0" />
</font>
<padding>
<Insets top="-2.0" />
</padding>
</Label>
</VBox>
<VBox alignment="CENTER" prefHeight="41.0">
<padding>
<Insets top="-2.0" />
</padding>
<HBox.margin>
<Insets left="10.0" />
</HBox.margin>
<HBox fx:id="layoutMenuHBox" alignment="CENTER"
fillHeight="false" maxHeight="-Infinity" prefHeight="24.0" spacing="2.0"
style="-fx-border-insets: 1 1 1 1; -fx-border-color: fx-light; -fx-border-
width: 0 1 1 1; -fx-border-radius: 2;">
<padding>
<Insets bottom="3.0" left="3.0" right="3.0" top="3.0"
/>
</padding>
<VBox.margin>
<Insets />
</VBox.margin>
<ToggleButton fx:id="autoLayoutToggleButton"
maxHeight="-Infinity" minHeight="-Infinity" mnemonicParsing="false"
prefHeight="22.0" prefWidth="26.0" textAlignment="RIGHT">
<graphic>
<FontIcon iconLiteral="fas-infinity" iconSize="14"
text=" " wrappingWidth="17.5" />
</graphic>
<tooltip>
<Tooltip text="Uzluksiz tartib (D3-Force
Algoritmi)" />
</tooltip>
</ToggleButton>
</HBox>
<Label style="-fx-font-size: 11; -fx-text-fill: gray;"
text="Tartib">
71](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_71.png)
![<font>
<Font size="10.0" />
</font>
<padding>
<Insets top="-2.0" />
</padding>
</Label>
</VBox>
</HBox>
</SplitPane>
</HBox>
</SplitPane>
<HBox alignment="CENTER_RIGHT" prefHeight="15.0" prefWidth="1357.0"
spacing="3.0" style="-fx-background-color: fx-darker; -fx-border-width: 1 0 0
0; -fx-border-color: fx-light;">
<HBox prefHeight="100.0" prefWidth="200.0" HBox.hgrow="ALWAYS">
<HBox.margin>
<Insets left="5.0" />
</HBox.margin>
<Label fx:id="mousePositionLabel" />
</HBox>
<ProgressIndicator fx:id="progressIndicator" maxHeight="-Infinity"
maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity"
prefHeight="15.0" prefWidth="15.0" progress="0.0" visible="false" />
<Label fx:id="infoLabel">
<HBox.margin>
<Insets bottom="1.0" right="3.0" top="1.0" />
</HBox.margin>
</Label>
</HBox>
</VBox>
_____________________________________________________________________________
__
OperationsView.fxml
<?xml version="1.0" encoding="UTF-8"?>
<?import javafx.geometry.Insets?>
<?import javafx.scene.control.Button?>
<?import javafx.scene.control.Label?>
<?import javafx.scene.layout.VBox?>
<?import javafx.scene.text.Font?>
<?import org.controlsfx.control.ToggleSwitch?>
<VBox alignment="CENTER" xmlns="http://javafx.com/javafx/17"
xmlns:fx="http://javafx.com/fxml/1"
fx:controller="com.todense.view.OperationsView">
<padding>
<Insets bottom="7.0" left="7.0" right="7.0" top="7.0" />
</padding>
72](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_72.png)
![<Label styleClass="darkLabel" text="Graf harakatlar" textFill="#8a8a8a">
<font>
<Font size="10.0" />
</font>
<VBox.margin>
<Insets bottom="3.0" top="5.0" />
</VBox.margin>
</Label>
<ToggleSwitch fx:id="editSubgraphToggleSwitch"
maxWidth="1.7976931348623157E308" minWidth="0.0" prefHeight="18.0"
text="Faqat tanlangan subgrafni tahrirlash">
<VBox.margin>
<Insets bottom="10.0" top="6.0" />
</VBox.margin>
</ToggleSwitch>
<VBox alignment="CENTER" spacing="5.0">
<Button alignment="CENTER" contentDisplay="CENTER" maxHeight="-
Infinity" maxWidth="1.7976931348623157E308" minHeight="-Infinity" minWidth="-
Infinity" mnemonicParsing="false" onAction="#pathAction" prefHeight="25.0"
text="Yo‘l yaratish" />
<Button contentDisplay="CENTER" maxHeight="-Infinity"
maxWidth="1.7976931348623157E308" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" onAction="#completeAction" prefHeight="25.0"
styleClass="success" text="To‘liq graf yarating" />
<Button contentDisplay="CENTER" maxHeight="-Infinity"
maxWidth="1.7976931348623157E308" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" onAction="#complementAction" prefHeight="25.0"
styleClass="success" text="To‘ldiruvchi graf yarating" />
<Button contentDisplay="CENTER" maxHeight="-Infinity"
maxWidth="1.7976931348623157E308" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" onAction="#subdivideAction" prefHeight="25.0"
styleClass="success" text="Qirralarni ajratish" />
<Button contentDisplay="CENTER" maxHeight="-Infinity"
maxWidth="1.7976931348623157E308" minHeight="-Infinity" minWidth="-Infinity"
mnemonicParsing="false" onAction="#deleteEdgesAction" prefHeight="25.0"
styleClass="success" text="Qirralarni o‘chirish" />
</VBox>
</VBox>
73](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_73.png)
TRANSPORT LOGISTIKASIDA GRAFLAR TATBIQ ETISH MUNDARIJA KIRISH……………………………………………………………… 3 1-BOB LOGISTIKA VA TRANPORT LOGISTIKASI, UNING ASOSIY TUSHUNCHASI ………………………............................. 6 1 .1 Logistika haqida asosiy tushunchalar………………………………... 6 1.2 Transport logistikasi…………………………………………………. 13 1.3 Ttansport logistikasida mash’rutlarni tashkil etish…………………... 20 1.4 Graflar nazariyasi elemenlari (graf, orgraf, zanjir, mashrut, grafni hosil qilish) …………………………………………………………… 25 2-BOB TRANSPORT LOGISTIKASIDA GRAFLARNI TATBIQ ETISH……………………………………………………………….. 30 2.1 Grafni hosil qilish.…………………………………………………… 30 2.2 Graf mashrutlarni hosil qilish. ............................................................. 36 2.3 Eng qisqa mashrutni aniqlash……………………………………….. 41 2.4 Graflar ustida amallar bajarish dasturiy ta’minoti…………………... 50 Xulosa……………………………………………………………….. 55 Foydalanilgan adabiyotlar.………………..……………………….. 56 Ilovalar 1
Kirish Masalaning qo‘yilishi. Transport logistikasida graflar tatbiq etish va daromad olish masalalarini tadqiq qilish va graflar ustida amallarni bajarish uchun qulay interfeysga ega bo‘lgan dasturiy ta‘minot yaratish. Mavzuning dolzarbligi. Jamiyatning barcha sohalarida transport logistikasini optimallashtirish muhum masala hisoblanadi. Ayniqsa bugungi kunda rivojlanayorgan, shiddat bilan sanoatlashayotgan jamiyatda, tabiiy holda raqobatning kuchayishi ortidan transport logistikasini optimal rejalashtirish va optimal daromad olish eng dolzarb masalalardan biri bo‘lib qolmoqda. Transport logistikasini optimallashtirish masalalari nazariy jihatdan, ya’ni ularning matematik modellarini yaratish ularni yechish va hakozolar, birmuncha yaxshiroq o‘rganilgan bo‘lishiga qaramay amaliy jihatda o‘rganishga yetarlicha ishlar mavjud bo‘lib bulardan biri bu nazariy tomondan yaratilgan modellar uchun dasturiy ta’minot yaratish. Shuning uchun bu ishda transport logistikasini samarali rejalashtirish va daromad olish masalalari uchun dasturiy taminot yaratish masalasi qaraladi. Ishning maqsad va vazifalari. Bitiruv malakaviy ishning asosiy maqsad va vazifasi bu tranport logistikasida graflar nazariyasini qullagan holda logistik joylashuv va boshqa parametrlariga ko‘ra transport logistikasidan eng samarali foydalanish yullarini aniqlash. Ilmiy-tatqiqot usullari. Ushbu bitiruv malakaviy ishida transport logistikasida graflarni tatbiq etish orqali ransport logistikasidan eng samarali foydalanish yullarini aniqlash dasturlash masalasiga keladigan hollar uchun o‘rganilgan bo‘lib bu modelni yechish uchun yaratilgan dasturiy ta’minot graflar nazariyasiga asoslangan. Mavzuning o‘rganilish darajasi. T ransport logistikasida graflarni tatbiq etish ni optimallashtirish masalasi nazariy jihatdan ko‘plab olimlar tomonida yaxshi o‘rganilgan bo‘lib ular ushbu masalaning turli xil modellarini yaratish va ularni yechish kabi natijalarni olishgan. Bu kabi natijalar keltirilgan ko‘plab adabiyotlar 2
mavzuni tadqiq qilishda o‘rganilgan. Mavzuning o‘rganilishi boshlang‘ch darajada bo‘lib, bu mavzuni o‘rganish natijasida olingan natija ya’ni yaratilga dasturiy ta’minot sodda bo‘lib u faqat bir yo‘nalishga mo‘ljallangan hisob kitoblarni bajaradi. Bu dasturiy ta’minotni kelajakda yanada mukammallashtirish rejalashtirilgan. Tadqiqotning ilmiy yangiligi. Bitiruv malakaviy ishida olingan natijalar amaliy-uslubiy xarakterga ega bo‘lib, ishda graflar nazariyasi ustida amallarni bajarishning ga mo‘ljallangan dasturiy ta’minot yaratligan. Bu dasturiy ta’minot JAVA dasturlash tilida yaratilgan bo‘lib, u vizuallashgan qulay interfeysga ega. Tadqiqot predmeti va ob’yekti. Tadqiqotning predmeti “Jarayonlar tadqiqoti”, “Transport logistikasi”, “Graflar nazariyasi”, “Matematik dasturlash” , “Java dasturlash tili” va shu kabi fan sohalari bo‘lib, ob’ekti ishlab chiqarishni rejalshtirish masalalarining matematik modellaridan iborat. Tatqiqotnig ilmiy va amaliy ahamiyati. Ishda olingan natijalar va unda qo‘llanilgan usullardan turli iqtisodiy, ijtimoiy sohalarning ko‘pgina amaliy masalalari, jumladan, transport logistikasida graflar nazariyasi tatbig‘i va samarali daromad olish masalalarini tadqiq qilishda, “Jarayonlar tadqiqoti”, “Transport logistikasi tadqiqoti”, “Transport logistikasida graflar nazariyasi tatbig‘ini matematik modellashtirish” va shu kabi fanlarning amaliy mashg‘ulotlari o‘quv jarayonlarida dasturiy vosita sifatida foydalanish mumkin. Ishning tuzilishi. Ushbu ish kirish, ikki bob, xulosa, foydalanilgan adabiyotlar ro‘yxati va ilovalardan iborat. I bob to‘rtta paragrafdan iborat bo‘lib, unda adabyotlardan foydalanilgan holda, bitiruv malakaviy ishiga qo‘yilgan “T ransport logistikasida graflar nazariyasi tatbig‘i” masalasi ni tavfislash va natija olish uchun zarur bo‘lgan asosiy tushunchalar, ta’riflar, tasdiqlar va matematik modellar keltirilgan. II bob to‘rtta paragrafdan iborat bo‘lib, transport logistikasida graflar nazariyasi tatbig‘ini tashkil etishda samarali reja va daromad olish masalalarining matematik modellari haqida so‘z yuritilgan, ikkinchi paragrafda bu modellardan foydalanilgan holda graflar ustida amallarni bajarishga asoslangan JAVA 3
dasturlash tilida qulay interfeysga ega bo‘lgan dasturiy ta’minotning funksional sxemasi keltirilgan hamda turli masalalarni yechish orqali dasturiy ta’minotdan foydalanuvchilar uchun ko‘rsatmalar berilgan . Uchinchi paragrafda dasturiy ta’minotning to‘gri ishlashini tekshirish uchun bir nechta mavjud standartlashgan dasturiy ta’minotlar bilan taqqoslashlar o‘tkazilgan. Olingan natijalarning qisqacha mazmuni. Bitiruv malakaviy ishida transport logistikasida graflar nazariyasi tatbig‘i masalalari va ularni yechish uchun olingan matematik modellar bilan tanishib chiqildi hamda bu modellardan foydalanilgan holda graflar ustida amallarni bajarishga asoslangan dasturiy ta’minot yaratildi. Bu dasturiy ta’minotdan foydalanib, graflar ustida ko‘plab amallarni bajarish mumkin bo‘lib, bu masalalarni transport logistikasida qo‘llash va samarali daromad olish masalalarining asosiy matematik modellaridan biri hisoblanadi. Ushbu yaratilgan dasturiy ta’minot graflar nazariyasiga asoslangan. Dasturiy ta’minot yordamida olingan yechimi transport logistikasidan foydalanishni optimal rejalashtirish va optimal daromad olishning yechimi bo‘ladi, ya’ni maqsad funksiyasining maksimumi optimal daromad olishga va shu funksiyani maksimumga erishtiruvchi o‘zgaruvchilarning qiymati optimal rejalarga mos keladi. 4
I BOB. LOGISTIKA VA TRANPORT LOGISTIKASI, UNING ASOSIY TUSHUNCHASI 1.1 Logistika haqida asosiy tushunchalar Logistika tushunchasi juda qadimiy tarixga ega bo‘lib, birinchi marta harbiy fan sifatida vujudga kelgan. IX asrda Vizantiyada bu tushunchaga qo‘shinni barcha kerakli narsalar bilan bilan o‘z vaqtida aniq ta’minlash jangning muvaffaqiyatini belgilovchi omil deb qaralgan. Vizantiya imperiyasida «logist» mansabi joriy etilgan boiib ular oziq-ovqat taqsimoti bilan shug‘ullanganlar. Ispan huquqshunosi va iqtisodchisi Polo de Ondegardoning 1572-yilda xabar berishicha ink Imperiyasi chinovniklari tomonidan ink saroyi uchun zarur bo‘lgan oziq-ovqat miqdorining hisobi olib borilgan. Bunda ularni qayerdan tashib keltirilishi, yetkazib kelish vaqti va tashish masofalarining hisoblari olib borilgan. XIX asrda fransuz olimi A.G. Jomini logistikani armiya va front orqasini boshqarish, tashishni rejalashtirish va tashkil etish bo‘yicha fan deb talqin etadi. 1850-yilda Sankt-Peterburgda chop etilgan «Harbiy ensiklopedik leksion»da logistika deb uzoqda va dushman yaqinida qo‘shinni ko‘chirishni boshqarish, qo‘shinni orqadan ta’minlashni tashkil etish san'ati deb tushuncha berilgan. Ikkinchi Jahon urushi davrida Amerika armiyasida logistik yondoshuv keng qo‘llanilgan. AQSh Ovrupoda jang qilganiga qaramay qo‘shinning ta’minoti juda yaxshi yo‘lga qo‘yilgan edi. Katta ingliz-rus lug‘atida hozir ham logistika tushunchasi harbiy ma’noda keltirilgan bo‘lib 1) front orqasi ta’minoti, 2) moddiytexnik ta’minot, 3) front orqasidagi ishlami bajarish va tashkil etish ma’nosida qo‘llaniladi. Respublikamizda va chet ellarda chop etilayotgan iqtisodiyotga oid adabiyotlarda logistika tushunchasi keng ma’noda qo‘llanilmoqda. Bugungi kunda iqtisodiy tizimdagi odamlar, moliyaviy, energetik va boshqa oqimlarni boshqarishlarga logistika fanining predmeti deb qaralyapti. Hozirda bank 5