Њзбекистон республикаси олий ва њрта махсус

ТARMOQLI OPТIMIZATSION MAТEMAТIK MODELLAR

1. Тarmoqlar to‘g‘risida tushuncha

Fan va texnikaning rivojlanishi natijasida iqtisodiyotning barcha tarmoqlarida rejalashtirish, boshqarish ishlarida matematik usullarni qo„llash bilan bir qatorda tezkor boshqarishning tarmoq modellaridan ham keng foydalanilmoqda.

Тarmoqli model asosan grafikni tashkil etib, ma‟lum texnologik jarayonlar bo„ladigan jami ishlarning ketma-ket yoki parallel bajarilishini grafik ravishda ifodalashi mumkin. Masalan, rejalashtirish, murakkab kompleks ishlarni bajarish, inshootlar qurilishining hisob ishlarini bajarish kabi ishlar tarmoqli modellar yordamida amalga oshirilib, grafik shaklida ifodalanishi mumkin. Grafik shaklida ikki mantiqiy element - ish va hodisa tarmoqli modelni tashkil qiladi. Grafikda hodisalar aylana bilan, ishlar esa strelka bilan ifodalandi. Odatda hodisalar
«uskunalar sozlanib bo„ldi», «dvigatel o„rnatildi» yoki «qurilayotgan inshoot bitdi» kabi iboralar bilan ifodalanadi. Тarmoqli grafikda «uskunani sozlash tugallanganicha yo„q», «qurilayotgan fundament hali bitmadi» kabi noaniq iboralar qo„llanilmaydi.
Quyidagi 10.1-rasmda tarmoqli grafikka oid masalalar keltirilgan.
Тarmoqli grafikda quyidagi hollar ham mavjud bo„lishi mumkin. Ba‟zi bir ishlar tugagandan keyin (masalan, texnologik elementlarni yig„ish) ishni boshqa ishga aloqasi bo„lgan holda davom ettirish mumkin. Birinchi hodisadan keyin ikkinchi va uchinchi hodisa boshlanadi, uchinchi hodisadan keyin to„rtinchi hodisa bajariladi. Lekin birinchi hodisadan keyin ikkinchi hodisa bajarilib, undan keyin to„rtinchi hodisaning bajarilishi uchun 2-3 ish punktir strelka bilan ifodalandi. Ishning bunday ko„rsatilishi, bu ishni bajarish uchun hech qanday resurs sarf bo„lmaydi, hatto vaqt ham sarf bo„lmasligini ko„rsatadi. Bunday ishni soxta ish deb yuritiladi. Bunday soxta ish 2-4 ni tashkil qiladi.


10.1-rasm. Тarmoqli modellarning ko„rinishi

Aytaylik, ba‟zi bir agregatni yig„ish 10.1-rasmdagi b) dagidek ko„rsatilgan bo„lsin. Agregat ikki uzeldan iborat, ya‟ni 2-sonli uzel va 3-sonli uzel. Birinchi hodisa hamma ishning boshlanishini ko„rsatadi. Ikkinchi hodisa esa 2-sonli uzelni tamom bo„lishini, to„rtinchi hodisa 3-sonli uzelning tamom bo„lishini ko„rsatadi. Uchinchi hodisa esa agregatning boshlanishini ko„rsatadi. Aytaylik, 2-sonli uzel agregatni yig„ish sexining o„zida bajarilsin. 3-sonli uzel esa boshqa korxonalarda tayyorlanishi mumkin. U holda uchinchi va to„rtinchi hodisani birlashtiruvchi ish (3, 4) 3-sonli uzelni yig„ish sexiga yetkazib berish vazifasini bajaradi. Ikkinchi va to„rtinchi hodisani birlashtiruvchi ish (2, 4), 2-sonli uzel tayyor bo„lmaguncha agregatni yig„ish mumkin emasligini ko„rsatadi.

Demak, soxta ish hodisalar orasidagi mantiqiy bog„lanishni ifodalar ekan.
Тarmoqli grafik asosan quyidagi uchta talabga javob berishi kerak:

1. 
   Har qanday ikkita hodisa orasida faqat bitta ish bajarilishi lozim.
   
2. 
   Тarmoqli grafikda hodisalarga boshqa birorta ish kirmasligi (dastlabki ishdan tashqari) kerak, shuningdek, hodisalardan boshqa birorta ish chiqmaydigan (tugallangan ishdan tashqari) bo„lishi kerak.
   
3. 
   Тarmoqli grafikda berk kontur deb ataluvchi kontur bo„lmasligi, ya‟ni bitta yo„l ikki marta bir xil hodisadan o„tmasligi kerak. Ba‟zi bir texnologik jarayonlarni ketma-ket ishlashda yo„l qo„yilgan xato bo„lsa, tarmoqli grafik qo„llanilganda yo„l qo„yilgan xato aniqlanadi.
   

1-chizmaning d) ko„rinishidagi tarmoqli grafikni ko„rib o„taylik. Birinchi hodisadan keyin (1, 2) ish, ikkinchi va uchinchi hodisalardan keyin (1, 3) ish bajariladi, lekin to„rtinchi hodisa bajarilganda, (2, 4) bajarilib, undan keyin uchinchi hodisa (4, 3) ish boshlanib, yana ikkinchi hodisa beriladi. Bunda (2, 3) ish bajariladi. Grafikdan ko„rinib turibdiki 2, 4, 3 hodisalar yordamida berk kontur hosil bo„lgan. Bunday yo„l davr deb ataladi.
Demak, 10.1-rasmning d) ko„rinishidagi ko„rsatilgan grafikda berk kontur hosil bo„lganligi uchun ishlamaydi.
Тarmoqli grafikning (tarmoqli modelning) asosiy afzalliklari quyidagilardir:

1. 
   Har bir ish orasidagi bog„lanish yaqqol ko„rinib turadi.
   
2. 
   Eng kerakli uchastka ishlarini tezlashtirish kerak bo„lsa, yoki ba‟zi bir ishlar qilinayotgan bo„lsa, rahbarlikning e‟tiborini jalb qilish grafikda yaqqol ko„rinib turibdi.
   
3. 
   Ishlarning qanday bajarilishi haqidagi ma‟lumotlarni aniq aytib berish mumkin.
   
4. 
   Barcha resurslarni tezkor ravishda ishlarning borishiga qarab taqsimlash mumkin.
   
5. 
   Тarmoqli grafikning parametrlarini aniqlashda, ma‟lumotlarni qayta hisoblashda EHMlarni qo„llash katta ahamiyatga ega.
   

Quyidagi 10.2-rasmda oddiy tarmoq grafigi ko„rsatilgan.
10.2-rasmda boshlang„ich hodisa 1, oxirgisi 11-hodisa bilan tugallanadi. Har bir ish uchun qabul qilinadigan hodisa boshlang„ich va oxirgi hodisa bilan (strelka
bo„yicha) ifodalanadi. Chizmadan ko„rinib turibdiki, bajariladigan ishlar ketma-ket, ayrim hollarda esa parallel bajarilishi va mantiqiy tahlil qilinishi mumkin. Aytaylik, (1, 4) ishning bajarilishi uchun avvalo (1, 2); (1, 10) ish bajarilishi uchun esa (1, 6),
(1, 3), (3, 9) ishlar bajarilish shart. Oradagi hamma ishlar bajarilgandan keyin (1, 11) ish bajariladi.
10.2-rasm. Oddiy tarmoq grafigi

Тarmoqli grafik bo„yicha ketma-ket bajariladigan ishlarni «yo„l» bilan ifodalaymiz. Тo„liq yo„lni hosil qilish uchun ketma-ket bajariladigan ishlarning boshlang„ich va oxirgi hodisalari olinadi. Har bir bajariladigan ish bajariladigan vaqt bilan aniqlanadi. Ajratilgan vaqt strelkalarning tepasiga yozib qo„yiladi. 10.2-rasmda ko„rsatilgan modelda (1, 2) ish uchun 4 kun, (1, 5) ish uchun 6 kun, (1, 6) ish uchun

8 kun, (1, 3) ish uchun 5 kun, (3, 6) ish uchun 2 kun, (3, 9) ish uchun 9 kun, (9, 10)
ish uchun 6 kun, (6, 10) ish uchun 11 kun, (5, 7) ish uchun 3 kun, (7, 10) ish uchun 1
kun, (4, 8) ish uchun 13 kun, (8, 11) ish uchun 15 kun, (10, 11) ish uchun 22 kun vaqt ajratilgan. Umuman olganda (1, 11) ish uchun 117 kun vaqt sarf bo„ladi. Тarmoqli grafikda eng uzoq cho„ziladigan yo„lni kritik yo„l deb yuritiladi. Oxirgi kritik yo„lning bajarilishi uchun oldingi bosqichdagi ishlar bajarilishi kerak. Bajariladigan ishning eng qisqa kritik yo„li aniqlanadi.
Kritik yo„l bajariladigan ishga ketadigan vaqtni aniqlab beradi. Modeldagi eng uzun kritik yo„l (1, 2), (2, 4), (4, 8), (8, 11) ishlarga 44 kunni tashkil qilib, modelda (4, 5) va (8,
7) ishlar punktir strelka bilan birlashtirilgan. Demak, bunday holda soxta ish bajariladi, ya‟ni 5 hodisa 4 hodisa bajarilgandagina bajariladi, 7 hodisa esa 8 hodisa bajarilgandan keyin bajariladi. Umuman (4, 5) va (8, 7) bog„lanish mantiqiy bog„lanishni tashkil qiladi, (4, 5) va (8, 7) hodisalar uchun vaqt ham sarf bo„lmaydi. Shu sababli ham punktir strelkalar ustiga 0 soni yozib qo„yilgan.
Тarmoqli grafikdan ko„rinib turibdiki, har bir ishni bajarish uchun aniq vaqt ajratilgan. Bu ishlar belgilangan vaqtda bajarilishi kerak. Bunday murakkab ishlarni bajarilishida rahbarlar tarmoqli grafik bo„yicha ish qanday sur‟atda bajarilayotganligini ko„rib, boshqarib boradilar. Shuning uchun ham tarmoqli grafikdan turli sohalarda keng miqyosda foydalanilmoqda, ayniqsa, qurilish ishlarida, harbiy ishlarda tarmoqli grafikning ahamiyati katta.
Ilmiy tekshirishlarni koordinatsiyalash markazi ko„rsatkichlarni baholashda (birorta ishni bajarish uchun sarf bo„ladigan vaqt) quyidagi ikkita asosiy usulni taklif etgan.
Birinchisi, ikki marta baholash, ya‟ni bajariladigan ishni ikki marta, vaqt

bo„yicha baholash: ishning minimal davom etishi
^tmin
(«optimistik baholash» ham

deb yuritiladi) va ishning maksimal ravishda davom etishi
^tmax
(«pessimistik

baholash»). Bu ikkala vaqt tarmoqli grafikda muhim rol o„ynaydi. Тarmoqli grafikka

oid hisob ishlarini davom ettirishda kutish vaqtini
quyidagicha aniqlanadi:
^tкутиш
aniqlashga to„g„ri keladi. U

^tкутиш
_ ^3tmin ^{ 2t}max _.
5

Ikkinchi usul, uch marta baholash, ya‟ni
^tmin
^{va t}max
lardan tashqari uchinchi

ishning normal borishi uchun
^tээ
ni baholash kerak bo„ladi. Bu yerda
^tээ

• 
  ishning
  

normal borishi uchun eng ehtimolli bo„lgan vaqt, uch marta baholash usuli kutish

vaqti
^tкутиш
quyidagicha aniqlanadi:


^tкутиш


_ ^tmin ^{ t}ээ ^{ t}max _.
6

Haqiqatda tarmoqli grafik yordamida bajariladigan ishlar tasodifiy ta‟sirlar natijasida shu ishlarni bajarish uchun ketadigan aniq vaqt kutish vaqtidan biroz ortiq bo„lishi mumkin, lekin shunga qaramasdan, yuqorida aytib o„tgan usullar turli ishlarni bajarishda keng qo„llanilmoqda.

2.