Operatsiyalarni tekshirish fanining predmeti va asosiy tushunchalari

Operatsiyalar kompleksini qiymat bo'yicha optimallashtirish.
Operatsiyalar kompleksini qiymat(xarajatlar) bo'yicha optimallashtirishning xususiy xolini ko'rib chiqamiz. Faraz qilaylik, ma’lum operatsiyani bajarish uchun ketgan xarajatlar uni bajarish uchun ketgan vaqtga teskari proporsional bo'lsin. Bu xolda P_ij operatsiyaning qo'shimcha xarajatlar koeffitsienti K_ij quyidagi formula bilan xisoblanadi:

Bu yerda t_ij´– eng ko'p C_ij´ xarajatlar talab qiladigan operatsiyani tez bajarish rejimi, t_ij" – minimal C_ij" xarajatlar talab qiladigan operatsiyani normal bajarish rejimi. Qo`shimcha xarajatlar koeffitsienti operatsiyalar bajarish vaqtini bir birlikka kamaytirish operatsiyaga ketgan xarajatlarni qanchaga oshirishini ko'rsatadi. Kritik yo'l uzunligi minimal bo'lgan minimal xarajatli operatsiyalar kompleksidagi kritik yo'lni topish algoritmini keltiramiz
Dastlabki qadam. Qo'shimcha xarajatlar koeffitsientlari f larni topamiz.Xar bir operatsiyaning t_ij´ bajarilish vaqtidan foydalanib, kritik yo'lni, kritik yo'l uzun-ligi(kritik vakt) t_kp operatsiyalarning vakt buyicha tula rezervlari ni va operatsiyalar kompleksining umumiy bajarilish xarajatlari ni topamiz. Birinchi (umumiy) qadam. Kritik operatsiyalar ichida qo'shimcha xarajatlar koeffitsienti eng kichik bo'lganini topamiz. Agar topilgan operatsiya barcha kritik yo'llar uchun umumiy bo'lsa yoki kritik yo'l yagona bo'lsa, bu operatsiya vaqti qisqarishi kerak. Agarda topilgan operatsiya kritik yo'llar uchun umumiy bo'lmasa, lekin bunday yo'llar bir yoki bir necha umumiy operatsiyalarga ega bo'lsa, bu yo'llarning xar biri uchun qo'shimcha xarajatlar koeffitsienti kichik bo'lgan operatsiyani topamiz. Keyin bu operatsiyalar qo'shimcha xarajatlar koeffitsientlari yig'indisini xisoblaymiz va uni kritik yo'llar umumiy operasiyalarining eng kichik qo'shimcha xarajatlar koeffitsienti bilan solishtiramiz. Agar qo'shimcha xarajatlar koeffitsientlarining xosil qilingan yig'indisi kritik yo'llar umumiy operatsiyalarining minimal qiymatli qo'shimcha xarajatlar koeffitsientidan kichik bo'lsa, bu yig'indiga mos operatsiyalarning barchasining bajarilish vaqti qisqarishi kerak. Aks xolda kritik yo'llarning umumiy operatsiyasi bajarilish vaqti qisqarishi kerak. Agar kritik yo'llar umumiy operatsiyalarga ega bo'lmasa, ularning xar birida qo'shimcha xarajatlar koeffitsienti eng kichik bo'lgan operatsiya topiladi. Ikkinchi qadam. Operatsiyaning (operatsiyalarning) bajarilish vaqtini (ular) minimal t_ij qiymatga erishguncha yoki yangi kritik yo'l paydo bo'lguncha davom ettiramiz. Uchinchi qadam. Tarmoq grafigining xosil qilingan varianti uchun kritik yo'lni, uning uzunligi t_kp operatsiyalarning vaqt bo'yicha to'la rezervlari S_ij operatsiyalar kompleksining bajarilish xarajatlari ni topamiz. To'rtinchi qadam. Agar kritik yo'lning barcha operatsiyalari vaqt bo'yicha minimal bo'lsalar algoritmni to'xtatamiz, chunki kritik bo'lmagan operatsiyalarning vaqt bo'yicha qisqarishi kompleksini bajarish xarajatlarini ko'paytiradi, lekin kritik yo'l uzunligiga ta’sir qilmaydi. Agarda kritik yo'lning barcha operatsiyalari vaqt bo'yicha minimal bo'lmasalar 1-qadamni bajarishga qaytamiz. Operatsiyalar kompleksini resurslar bo'yicha optimallashtirish. Masalaning ko'yilishi. Operatsiyalar kompleksining tarmoq modeli G=(V ,É) orgrafdan iborat bo'lsin. M xilda R_s s=1‾m miqdorda resurslar bor deb xisoblaymiz. Xar bir P_ij operatsiya uning bajarilish vaqti t_ij va intensivligi  bilan xarakterlanadi. Operatsiyaning intensivligi deganda t_ij vaqt o'tishi mobaynida operatsiyaning bajarilishi uchun zarur bo'lgan resurs miqdoriga aytamiz. Tarmoq grafigidagi operatsiyalarni bajarishdan oldin kerakli bulgan resurslarni aniqlash va ularni bor bo'lgan resurslar bilan solishtirish kerak. Agar ba’zi vaqtlar oralig'ida bor bo'lgan resurslar operatsiyani bajarish uchun yetarli bo'lmasa quyidagi masalani xal qilish zarurati tug'iladi: Tarmoq grafigidagi operatsiyalarni bajarishning shunday boshlang'ich va oxirgi kalendar muddatlarini topingki, rejalashtirilayotgan vaqtda yetarlicha resurs mavjud bulib, operatsiyalar kompleksini bajarish vakti minimal bulsin. Bu masalani xal qilish algoritmini bayon kilganda intensivlik o'zgarmas va bir xil resurs bulgan xolni karaymiz. Quyidagi algoritm xamma vaqt xam optimal yechimni bermasada, unga yaqin yechimni beradi. Masalani yechish algoritmi. Dastlabki kadam. Operatsiyalar kompleksini bajarish chiziqli diagrammasini tuzamiz. Diagrammada xar bir operatsiya uzunligi uning bajarilish vaktiga teng bo'lgan kesma bilan ifodalanadi.Xar bir operatsiyaning boshlanishi undan oldingi operatsiyaning tugashaga to'g'ri kelishi kerak. Diagrammadan operatsiyalar kompleksining bajarilish kritik vaqti t_kp va kritik yo'lni topamiz. Birinchi qadam. 1)Vaqt o'qiga xar operatsiyani bajarish vaqtining boshlanishi (τ₀) va oxiri τ₁ ning proeksiyasini tushiramiz (τ₀, τ₁ ) oraliq uchun operatsiyalar to'la vaqt rezervlari S_ij ni topamiz. Tula vakt rezervlarini o'sish tartibida nomerlaymiz. To'la vaqt rezervlari bir xil bo'lgan operatsiyalarni intensivligi kamayish tartibida nomerlaymiz. (τ₀, τ₁ ) oraliqdan yuqorida joylashgan operatsiyalar intensivligini ularning nomerlari o'sishi tartibida yig'indisini olamiz va xosil bo'lgan yig'indilarni berilgan resurslar kattaligi R bilan solishtiramiz. Intensivliklari yig'indisi R intensivligini qo'shganda yigindi R dan oshib ketsa, bu operatsiyani qaraliyotgan oraliq uzunligiga unga suramiz va keyingi operatsiya intensivligini qo'shamiz va bu ishni (τ₀, τ₁ ) oraliqdan yuko-rida joylashgan barcha operatsiyalar qaralguncha davom ettiramiz. Bu amallarni bajarish natijasida yangi chiziqli diagramma paydo bo'ladi. (τ₁, τ_kp ) oraliq ustida joylashgan (i,j) operatsiyalarni shunday joylashtiramizki, ularning boshlari voqealarning sodir bo'lish vaqtlari ustma-ust joylashsin. Umumiy qadam. Faraz qilaylik algoritmning k qadami bajarilgan va qolgan qis-mining boshlanishi momentda bo'lgan operatsiyalar kompleksi chiziqli diagrammasi xosil bo'lgan bo'lsin. (τ_k, τ_kp ) oraliqdan yuqorida joylashgan operatsiyalar boshi va oxirining vaqt o'qiga proeksiyasini olamiz va τ_k, ga eng yakin bulganini τ_k+1, belgilaymiz. Shunday qilib yangi (τ_k, τ_k+1 ) oralik aniqlanadi. (τ_k, τ_k+1 ) oraliqdan yuqorida joylashgan operatsiyalarning to'la vaqt rezervlari S_ij larni topib ularni nomerlab chiqamiz. Nomerlashni to'la rezervlar o'sish tartibida bajaramiz. 3) Bu punktda birinchi qadamning 3-punktidagidek ish kilamiz. Ammo shu narsaga e’tibor kilish kerakki, agar τ_k, dan chapdagi (i,j) operatsiya surilishi kerak bo'lsa, birinchi xolda operatsiyani butunlay suramiz, ya’ni bu operatsiyaning boshini momentga qo'yamiz, ikkinchi xolda esa operatsiyani bo'laklarga bo'lamiz va operatsiyaning boshidan τ_k, gacha bo'lagini joyida qoldiramiz. Qolgan qismini , ya’ni τ_k, dan oxirigacha bo'lgan bo'lagini unga (τ_k, τ_k+1 ) oraliq uzunligigacha suramiz. Operatsiyalarning bo'laklarini keyinchalik yangi operatsiyalar deb xisoblab ularga mos voqealar nashrlarini beramiz. 4) Operatsiyalar kompleksidagi barcha operatsiyalar tekshirilgan bo'lsa, yechimni to'xtatamiz. Aks xolda umumiy qadamning 1-punktiga qaytamiz.