Mirzo ulug`bek nomidagi o`zbekiston milliy universiteti jizzax filiali

Tarmoqli modellar.

Tarmoqli modellarning 3 turi mavjud

1. Tarmoqli modellar to‘g‘risida tushuncha.

2. Tarmoqli graflar va ularni tuzish yo‘llari.

3. Tarmoqli rejalashtirish masalasining algoritmi.

Tarmoqli tahlil (setevoy analiz) – loyiha xarakteridagi, ya’ni qoidaga ko‘ra operatsiyalari takrorlanmaydigan ishlarni rejalashtirish usulidir. Ushbu usuldan operatsiyalarni bajarishning kalendar rejasini tuzishda, qurilish ishlarining bajarilishini rejalashtirishda ko‘proq foydalaniladi.
Tarmoqli tahlil usullari katta miqdordagi o‘zaro bog‘liq operatsiyalarni o‘z ichiga olgan loyihalarni tahlil etishga imkon beradi. Ushbu usullar yordamida ishlar bajarilishining davom etish ehtimolligini, ularning qiymatini, vaqt va pul mablag‘larini tejash kabi ko‘rsatkichlarni hisoblash mumkin.
Tarmoq modellari - U asosiy tashkiliy asbob. Taqvim rejalashtirishga ruxsat berish, ishning davomiyligini kamaytirish, ishning narxini optimallashtirish, operatsion boshqaruvni tashkil etish va loyihani amalga oshirish monitoringi. Texnik ketma-ketlikda barcha zarur jarayonlar (boshqaruv vazifalari) tasvirlangan tarmoq modeli - yo'naltirilgan grafik.Tarmoq matritsasi UE jarayonining grafik tasviridir, unda barcha operatsiyalar, boshqaruv vazifalari, loyiha uchun zarur bo'lgan barcha operatorlar va kalendar kunlarining texnologik ketma-ketligi bo'yicha belgilanadi. Tarmoq matritsasidan foydalanish sizga barcha ish kompleksini tezda hisoblash va boshqaruv qarorlarini qabul qilishga imkon beradigan keng qamrovli ma'lumot loyihasini boshqarishga imkon beradi.
Bo'shliqlar daraxti.
Bo'sh joy uchun ajdodlar makonida yotgan barcha , uchlari ko'rinadi qolganlari ko'rinmas. "Ko'rinish" munosabati "istiqbollar" to'plami tartibida makonni guruhlash imkonini beradi. Ierarxik tarmoqlarni grafik tasvirlash uchun qoidalar yoki konventsiyalarni ko'rib chiqing: 1. bir xil bo'shliqdagi vertikal va yoylar to'g'ridan-to'g'ri yoki ko'pburchak bilan bog'langan; 2. yoy uning nomi joylashgan bo'sh joyga tegishli; 3. bo'sh joy i ichki bo'shliq tasvirlangan avlod deb hisoblanadi (ichki daraja), ya'ni. dan "Aftidan" . mavjud bo'lgan "eng yuqori" deb hisoblash mumkin . Semantik tarmoq tipidagi ma'lumotlar bazasida echim topish muammosi, etkazib berilgan tarmoqqa mos keladigan ma'lum bir pastki tarmoqqa mos keladigan tarmoq qismini topish muammosiga qadar kamayadi.
Graflar
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
qirra yoylar. Ilmoq – aynan bitta tugundan chiqib, yana shu tugunga kiruvchi qirra.
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.
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.