1-Mavzu: Butun sonli chiziqli programmalash modellari

Tarmoqli 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. Tarmoqli grafikda «uskunani sozlash tugallanganicha yo‘q», «qurilayotgan fundament hali bitmadi» kabi noaniq iboralar qo‘llanilmaydi.
Quyidagi 1-rasmda tarmoqli modellarga oid misollar keltirilgan.

1-chizma. Tarmoqli modellarning ko‘rinishi
Tarmoqli grafik asosan quyidagi uchta talabga javob berishi kerak:
1. Har qanday ikkita hodisa orasida faqat bitta ish bajarilishi lozim.
2. Tarmoqli grafikda hodisalarga boshqa birorta ish kirmasligi (dastlabki ishdan tashqari) kerak, shuningdek, hodisalardan boshqa birorta ish chiqmaydigan (tugallangan ishdan tashqari) bo‘lishi kerak.
3. Tarmoqli 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.
Tarmoqli rejalashtirish masalasining algoritmi.
Bajariladigan ishlar oddiy bo‘lsa, yuqorida ko‘rib o‘tgan grafik usuli yordamida rejalashtiriladi. Agarda bajariladigan kompleks ishlar murakkab bo‘lsa (ayrim hollarda ishlar soni va mantiqiy aloqalar mingdan va undan ortiq bo‘lishi mumkin), albatta EHM yordamida hal qilinishi uchun ishlarning aniq ketma-ketligi yoki algoritmi tuzib olinadi.
Tarmoqli grafikning algoritmini tuzish uchun quyidagi 1-jadvaldan foydalanamiz.
1-jadval
Tarmoq grafigini tuzish uchun ma’lumotlar

№	ai ish	Qaysi ishga asoslanib bajariladi	ti vaqt
1	a1	-	t1
2	a2	-	t 2
3	a3	-	t 3
4	a4	a1, a2	t 4
5	a5	a1, a3, a4	t 5
6	a6	a2, a3	t 6
7	a7	a4	t 7
8	a8	a4, a5	t 8
9	a9	a4, a5, a6	t 9
10	a10	a6, a7, a8, a9	t 10

Bu jadvalda bajariladigan ishlar va bu ishlar qaysi ishlarga asoslanib bajarilishi hamda har bir ish uchun ketadigan vaqt aniq ko‘rsatilgan.
1-jadvaldagi bajariladigan ishlar va ular orasidagi aloqalarning matematik formulasini yozib olamiz. Buning uchun belgilashlar kiritamiz.
ish bajarilishining minimal boshlanish vaqtini bilan, ishning minimal tugash vaqtini esa bilan belgilab olamiz. Har qanday ishning minimal tugash vaqti

formula bilan aniqlanadi. Bu yerda, - ishning bajarilishi uchun ketgan vaqt bo‘yicha aniqlanadi.
Mana shu ifoda yordamida hamma kompleks ishlarda bo‘ladigan mantiqiy aloqalarni formulalar bilan ifodalaymiz. Aytaylik, ish ishlarga asoslanib bajarilsin. U holda ish faqat bajariladi. Bu aloqani quyidagi ko‘rinishda yozamiz:
.
Bu formulani har bir ish uchun ketma-ket ravishda tatbiq qilib, barcha ishlarning minimal tamom bo‘lish vaqtini aniqlaymiz.
Endi “kritik yo‘l” usulini ko‘rib o‘tamiz. (CPM – Critical Path Method). Bu usul asosida yangi mahsulotni yaratish, bino va inshootlar qurilishi, murakkab uskunani ta’mirlash masalalarini yechish mumkin. Loyihani amalga oshirishda ishlarni bajarish grafigi tuziladi. Bunda murakkab omil bo‘lib, ishlarning o‘zaro bog‘liqligi hisoblanadi. Ayrim ishlar boshqa ishlarning bajarilishiga bog‘liq va boshqa ishlar bajarilmasdan turib ushbu ishlar boshlanmaydi. “Kritik yo‘l” usulining asosiy sharti bo‘lib, har bir ishni bajarish vaqti aniq hisoblanadi.
“Kritik yo‘l” usulini qo‘llash uchun dastlabki qadam bo‘lib, loyihani bajariladigan ishlar va ularning o‘zaro bog‘liqligi ko‘rinishida ifodalab olinadi. Loyihani ifodalash uchun jadval va grafik usullaridan foydalaniladi.
“Kritik yo‘l” usulini qo‘llash uchun quyidagi belgilashlarni kiritamiz:
i va j – loyiha cho‘qqilari yoki hodisalar, (i,j) – loyiha ishi, s – “loyiha boshlanishi” hodisasi, f – “loyiha tugallanishi” hodisasi, T – kritik yo‘l uzunligi bo‘lsin.
t(i,j) - (i,j) ishlarni bajarish vaqti;
ES(i,j) - (i,j) ishlarni eng erta boshlash vaqti;
EF(i,j) - (i,j) ishlarni eng erta tugallash vaqti;
LS(i,j) - (i,j) ishlarni eng kech boshlash vaqti;
LF(i,j) - (i,j) ishlarni eng kech tugalllash vaqti;
E_i - i – hodisani eng erta boshlanish vaqti;
L_i - i – hodisani eng kech boshlanish vaqti;
R(i,j) - (i,j) ishlarni bajarishga vaqtning to‘liq rezervi;
r(i,j) - (i,j) ishlarni bajarishga vaqtning erkin rezervi.

2-chizma.

Ta’riflar: