Муҳаммад ал Хоразмий номидаги Тошкент ахборот технологиялари университети

Yakuniy nazorat ishi Olimjonov Nodirbek

Муҳаммад ал Хоразмий номидаги Тошкент ахборот технологиялари университети “ТАД” кафедраси, “Амаллар тадқиқи асослари” фанидан оралиқ назорат саволлари
Вариант № 18
Цикллар хосил қилиш усули билан оптимал ечимни топиш.
Динамик дастурлашдаги икки асосий режалаштириш
Ресурсларни тақсимлаш масаласи
Кафедра мудири	Керимов К.Ф.

2. Dinamik dasturlash (DD) – Ko’p qadamli (ko’p bosqichli) operatsiyalarga asoslangan yechimlarning matemetik optimallashtirish usullari. Ko’plab operatsiyalar qadamlarda tabiy ravishda tarmoqlanib ketadi: masalan xo’jalik ishlari bilan shug’ullanadigan korxona faoliyatini optimallashtirishda operatsiyalar tabiiy ravishda xo’jalik yiliga bog’liq bo’ladi. Boshqa turdagi operatsiyalar esa su’niy ravishda qadamlarga bo’linadi: raketani orbitaga jo’natish jarayonida har bir qadamni ∆t ga bo’lib chiqish mumkun.

Har bir qadamda biror qaror qabul qilish talab qilinadigan operatsiyalar boshqariluvchi operatsiyalar deyiladi.

Operatsiyani boshqarish bir qator boshqariluvchi qadamlardan ibarat bo’ladi.

Tabiiy ko’p qadamli operatsiyani qaraylik

Olaylik m xo’jalik yilidan iborat bo’lgan T vaqtga mo’ljallangan П₁, П₂, …, П_к guruh tashkilotlari faoliyatini optimallashtirish talab qilinsin.

T davr bosh qismida tizimni rivojlantirish uchun asosiy resursning К₀, qismini П_i guruhlar orasida taqsimlash kerak bo’ladi. Tizim faoliyati ishlash davrida berilgan resurslar tabiiy ravishda qayta taqsimlanib ketadi. Bundan tashqari har bir П_i unga berilgan resursga qarab yiliga foyda keltirib turadi. Har bir xo’jalik yilining boshlanishida berilgan resurslar П_i lar ortasida qayta taqsimlanib ketadi.

Quydagicha savol qo’yiladi: har xo’jalik yilining boshida П_i larga shunday resurslarni taqsimlash kerakki , ular butun T davr ichida maksimal foyda keltirsin (T=m bo’ladi ).

Bu dinamik dasturlashning sodda masalasi hisoblanadi: Bu masalada boshqariluvchi jarayon sifatida korxona tizimining faoliyati qaraladi.

Boshqarish esa resurslarning taqsimoti bo’ladi. Boshqaruv qadamlari esa biror bir miqdordagi resursni П_i lar o’rtasida har xo’jalik yili boshida taqsimlash bo’ladi. Olaylik har i-chi yilning boshida П₁ П₂, …, П_к tashliklotlar uchun mos ravishda : resurslar ajratilsin. - larning to’plami i-chi qadamdagi boshqarish deyiladi va quyidagicha belgilanadi.

(1.1)

U boshqarish qadamlari umumiysi:

(1.2)

Boshqaruv operatsiyalar U ning samaradorligi E ko’rsatkich bilan aniqlanadi, E ko’rsatkichning umumiy qiymati butun masalaning samaradorlik miqdorini beradi. Misolimizda butun tizimda m yil bo’yicha keladigan E umumiy foyda maqsad fungsiyasi sifatida berilgan:

(1.3)

Shunday savol qo’yiladiki: E kattalik maksimumga erishishi uchun qanday qilib boshqaruv operatsiyalarni tanlash kerak.

Qo’yilgan masala boshqaruvni optimallashtirish masalasi deyiladi; E = max bo’ladigan boshqaruvlar esa optimal bo’shqaruv deyiladi.

Ko’p qadamli operatsiyani qadamma-qadam optimallashtirish dinamik dasturlashning asosiy prinsipi.

Optimal boshqaruvni U dan farqli u belgilaymiz. Ko’p qadamli jarayonda optimal [u] boshqaruvlar to’plami.:

(1.4)

Quyidagicha masala qo’yiladi: Har bir qadamga optimal boshqaruvlarni toppish, ya’ni butun U ni topish kerak.

Eslatib o’tamizki bizning masalada E har bir alohida xo’jalik yilidagi umumiy foyda miqdorini beradi:

(1.5)

Bu yerda - i-chi yildagi butun tizimning foydasi bo’ladi (1.5) xususiyatga ega bo’lgan E kattalik additiv kattalik deyiladi.

3. Ikkilanma masalalar.
To’g’ri va ikkilanma masalalar va ular yechimlarining iqtisodiy talqini.
Ikkilanma simpleks usul.
Chiziqli dasturlashning har bir masalasi ikkilanma (qo’shma) deb ataluvchi boshqa chiziqli masala bilan uzviy bog’langan. Bunda birinchi masalaga boshlang’ich yoki to’g’ri deyiladi. Bu masalalar birgalikda o’zaro ikkilanma masalalar juftini tashkil etib ulardan istalganini boshlang’ich deb qarash mumkin. Bulardan birining yechimini topish bilan ikkinchisining ham yechimini olish mumkin.


Ikkilanma masala - CHDning ko’makchi (yordamchi) masalasi bo’lib boshlang’ich masala shartlaridan aniq qoidalar yordamida bevosita olinadi. Ikkilanma masalani tuzish qoidalarini ifodalaymiz:
boshlang’ich masalada maqsadli funksiya maksimumi topilayotgan bo’lsa, ikkilanma masalada maqsadli funksiya minimumi topiladi;
boshlang’ich masala cheklash shartlari soni m ikkilanma masala o’zgaruvchilari soniga, boshlang’ich masala n o’zgaruvchilari soni esa ikkilanma masala cheklash shartlari soniga teng; Odatda ikkilanma masala o’zgaruvchilarini y_i (i = 1,2,...,m) bilan belgilanadi;
boshlang’ich masala o’zgaruvchilari, unga ikkilanma masalaning cheklash shartlari bilan bog’langanligi uchun har bir x_j > 0 o’zgaruvchiga
unga ikkilanma masalada “” (z ^ min bo’lsa) cheklash shartlari mos keladi;
biror belgi bilan cheklanmagan boshlang’ich masaladagi har bir x_j
o’zgaruvchiga, unga ikkilanma masalada “=” ko’rinishdagi shart mos keladi va aksincha;
boshlang’ich masalaning cheklash shartlaridagi b_i (i = 1,2,...,m) ozod hadlari, unga ikkilanma masalada y_t (i = 1,2,..., m) o’zgaruvchilarning maqsadli funksiyadgi koeffitsiyentlaridan, x_j larning boshlang’ich masala maqsadli funksiyasidagi koeffitsiyentlari c_} (j = 1,2,..., n) lar esa ikkilanma masala cheklash
shartlari ozod hadlaridan iborat bo’ladi;
boshlang’ich masala cheklash shartlari noma’lumlarining koeffitsiyentlari matritsasi A = (a_y.) unga ikkilanma masala cheklash shartlari
noma’lumlari matritsasida A^T - transponirlangan bo’ladi. Boshlang’ich va unga ikkilanma masalalarning bog’likligi ko’rinarli bo’lishi uchun uni quyidagi jadvalda yozamiz:

Boshlang’ich masala	Ikkilanma masala
1. F ^ max	1. z ^ min

2. m - cheklash shartlari soni;	2. yt (i = 1,2,...,m) o’zgaruvchilar;
3. xj (j = 1,2,...,n) o’zgaruvchilar;	3. n cheklash shartlari soni;
^4. X >^0;	4. j ta “>” ko’rinishdagi cheklash;
5. г ta cheklash “	5. yt > 0 ko’rinishda;
6. x j biror belgi bilan chegaralanmagan;	6. j ta “=” ko’rinishdagi belgili shart;
7. г ta “=” ko’rinishdagi shart;	7. yt hech qanday shart bilan chegaralanmagan;
8. Cheklash shartlaridagi ozod hadlar;	8. Maqsadli funksiyadagi noma’lumlar (bi) koeffitsiyentlari;
9. Maqsadli funksiyada xj larning (kj) koeffitsiyentlari	9. Cheklash shartlaridagi (ki) ozod hadlar;
10. Cheklash shartlari noma’lumlari koeffitsiyentlari matritsasi (A).	10. Cheklash shartlari noma’lumlari koeffitsiyentlari matritsasi transponirlangan (A^T).

CHD ning xususiy masalalaridan birini umumiy holda qaraymiz va u boshlang’ich masala bo’lsin.

F = c,x, + c_nx_n +... + c x ^ max

11 2 2 n n

ax + ax-i +... + ax

111 12 2 1n n 1 ⁵

a₂₁ ^Xj + a₂₂^x₂ + ... + a₂n^xn < ^b„

a_m1 x, + a, x ₂ + ... + a_mnx_n < b_m

m1 1 m2 2 mn n m
^xj > ^{0 (j} =^{1 n)}

Bu masalaga ikkilanma masala quyidagicha bo’ladi:

^z = ^b1 У1 + ^b2У2 + ... + ^ЬтУт ^ <sup>min

a</sup>11 У1 + ^a21У2 + ... + ^am1 Ут > ^

^a12У1 + ^a22У2 + ... + ^am2Ут > ^ ^a1nyj + ^a2пУ2 + ... + ^amnУm > ^Cn ^,

У_г > 0 (i = 1, m)

Oxirgi masalaga ikkilanma masalani tuzsak, boshlang’ich masalani olamiz.

Endi CHD boshlang’ich masalasi xususiy hollarining ularga ikkilanma masalalarini matritsa ko’rinishda yozamiz:

I va II ikkilanma masalalar juftiga simmetrik, III va IV masalalar juftiga esa “=” ko’rinishdagi cheklash shartlari bo’lganligi uchun simmetrik bo’lmagan masalalar deyiladi.