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

f (x_o



)  __j ( g_j
j1
(x ₀
)  b_j
)  f (x_o
m

)  _ ( g
m
j
j 1
_j (x ₀
)  b_j
m

)  f (x )  _ ( g
( 0)
j
j 1
_j (x )  b_j )
(4.23)

tengsizlik quyidagi tengsizliklarga teng kuchlidir.

m
 (g (x
)  b
)  m ⁽⁰⁾ (g (x  b )
(4.24)

^ j j 0 j1
j ^ j j 0 j i1

f(x
)  m ⁽⁰⁾ (g (x
)  b
)  f(x) 
^m _( 0) _(g
(x)  b )
(4..25)

0 ^ j j 0 j j1
^ j j j j1

Тa‟rifga asosan (4.23) tengsizlik hamma, _j=0 da ham bajarilishi kerak. Bu holda (4.24 dan)

g_j (x_o)-b_j< 0 (4.26)
ekanligi kelib chiqadi. Ikkinchi tomonidan (7)

^m ^(o) (g (x )  b
)  0
(4.27)

^ j j o j



 0
j1


kelib chiqadi. Biroq
( o ) j
 0 shartga va (4.26) tengsizlikka asosan
( o ) j
bo„lganda

(4.24) tengsizlikning faqat
yoki qisqacha


_{ }( 0) <sub>(g


j</sub> (x₀

)  b

_j )  0

j

0 o
^' (g(x )  b)  0
(4.28)

bo„lgandagina o„rinli bo„lishligi kelib chiqadi (4.28) ga asosan (4.25) dan quyidagi

f(x_o
)  f(x) 
m

j

j1
^o (g
_j (x)  b _j )


tengsizlikka ega bo„lamiz. Bu tengsizlikda
g _j (x)  b _j  0 bo„lgani uchun
( o ) j
va (4.19) ga asosan

 0
^m _( 0 ) _(g
(x)  b
)  0

Demak,
^ j j j j1

f(x₀ )  f(x)
tengsizlik qavariq Q to„plamdagi hamma x lar uchun  uchun o„rinlidir. Shuning uchun
, x₀ qavariq dasturlash masalasining yechimidir. Тeorema isbot bo„ldi.
Isbot qilingan teoremaga asosan, agar Lagranj funksiyasining egar nuqtasi mavjud bo„lsa, qavariq dasturlash masalasining yechimi mavjud degan muhim xulosaga kelamiz.
Lagranj funksiyasining egar nuqtasi mavjudligi haqidagi teoremani birinchi marta amerikalik olimlar Kun va Тakkerlar tomonidan isbotlangan bo„lib, bu teoremani shu olimlarning nomi bilan Kun-Тakker teoremasi deb yuritiladi. Quyida biz shu teoremaning shartlari va isbotini keltiramiz.
3⁰. Kun-Тakker teoremasi. Bizga n o„lchovli R_n fazoda aniqlangan, qavariq,
uzluksiz, ikki marta differensiallanuvchi f(x)= f(x₁, … ,x_n) va g_j(x₁, … , x_n)

funksiyalar berilgan bo„lsin va erkli o„zgaruvchi

10. 
    R _n
    

o„zining qiymatlarini birorta

qavariq Q to„plamida albatta qabul qilishi shart qilib olinmagan bo„lsin. Agar yuqoridagi mulohazalar o„rinli bo„lganda
f (x₁ , … , x_n) (4.30)

funksiyaning quyidagi
C_j(x₁,..., x_n )  b _j  g_j(x₁,..., x_n )  0; j  1,m
(4.31)

cheklanish shartlarini qanoatlantiradigan minimumini topish talab qilingan bo„lsa quyidagi teorema o„rinlidir.

2. 
   teorema. Agar х
   

 (х^{( 0 )} ,..., х^{( 0 )} )
o„rinli nuqta qavariq dasturlash masalasi (4.30) ,

0 1 n

(4.31) ning yechimi bo„lsa, shunday 
 0,  (^{( 0 )} ,..., ^{( 0 )} ) vektor mavjud bo„ladiki, x₀ va

0 0 1 n

₀ lardan tuzilgan { x₀ ,₀ } juft Lagranj funksiyasining egar nuqtasi tashkil qiladi.

Boshqacha qilib aytganda, hamma   0 va xR₁ lar uchun quyidagi
F (x₀,)  F (x₀,₀)  F (x₀ , ₀) (4.32)
tengsizlik o„rinli bo„ladi.

Isbot.
х  (х^{( 0 )} ,..., х^{( 0 )} )
nuqta qavariq dasturlash masalasi (4.30), (4.31) ning yechim

0 1 n



m
bo„lsin. U holda shu nuqtada Lagranj funksiyasining minimum mavjudligining birinichi tartibli zaruriy sharti bajarilishi kerak, ya‟ni

^{F(x0 0 )}  0,^' g(x

)  0,бу
ерда
F (x, )  f(x)   g (x)

_x 0 0

yoki aniqrog„i

^ j j
j1

f(x^{( 0 )} ,..., x^{( 0 )} ) ^{m g (x}( 0 ) ^{,..., x}( 0 )

1 n _{  }^{( 0 ) j 1
n}  0
i  1,n
(4.33)

x_i
j
j1
x₁

m ^{( 0 )}g (x^{( 0 )} ,. , x^{( 0 )} )  0
(4.34)

^ j j 1 n j1


Qavariq funksiyalarnin ikkinchisi xossasiga asosan

f(x₁,..., x_n ),g_j (x₁,..., x_n ),
j  1,m
funksiyaning ham qavariq ekanligi kelib chiqadi.

Shuning uchun (14)ni nazarda tutsak, hamma x  R₁ larda

m
F(x  )  f(x^{( 0 )} ,..., x^{( 0 )} )  (x^{( 0 )} ,..., x^{( 0 )}  f(x .,,,.x
)  m ^{( 0 )g1} (x ,..., x )  F(x, )
(4.35)

0 0 1

n ^ 1 n j1
1 n ^ j 1 n 0
j1

bo„ladi
x  (x^{( 0 )} ,..., x^{( 0 )} )
nuqtani o„rinli nuqta deb faraz qilganimiz uchun

0 1 n

g (x )  g (x^{( 0 )} ,..., x^{( 0 )} )  0,

j  1,m

bo„lib, hamma   0 uchun

1 0 i 1 n

m  g (x^{( 0 )} ,..., x^{( 90 )} )  0

^ j j 1 n j1

tengsizlik o„rinlidir. Ikkinchi tomondan, (15) ni nazarda tutsak
F(x )  f(x^{( 0 )} ,..., x^{( 0 )} )  m  g (x^{( 0 )} ,..., x^{( 0 )} )  f(x^{( 0 )} ,..., x^{( 0 )} )  F(x  )
(4.36)

0 1 n

^ j j 1 n 1 n 0 0 j1

ekanligiga ishonch xosil qilamiz (4.35) va (4.36) tengsizliklardan (4.33) ning to„g„riligi, ya‟ni teoremaning to„g„ri ekanligi kelib chiqadi.

2. 
   teorema. F (x) va g_j(x), j= 1,m; xR_n funksiyalar ikki marta differensiallanuvchi funksiyalar bo„lsin. U holda o„rinli nuqta x₀ ning quyidagi.
   

F (x)  min (4.37)

g_j(x)  0,
x  0,
j  1,m
(4.38)

masalaning yechim bo„lishiligi uchun shunday ₀  0 mavjud bo„lishiligi va hamma x > 0,   0 uchun

m n
^{F(x,)  f(x) } ^_k^g_k ^(x)
k 1
(4.39)

tengsizlikning bajarilishi zarur va yetarlidir.
Isbot. Bu teoremani isbot qilish uchun (4.37) va (4.38) masalani (4.30) (4.31) masala ko„rinishiga keltirish kifoyadir. Buning uchun (4.38) dagi qo„shimcha x  0

yoki
^{хш  0,}i1,n
cheklanish shartlarini g_m+i(x)=-x_i belgilash yordamida

g_mn (x)  0, i 1, n ko„rinishga keltiramiz. U holda (4.38) ni umumiy

g_k(x)  0,
k  1,(m  n)
(4.40)

ko„rinishda yozish mumkin. Endi (4.37) va (4.40) masalaning qo„yilishiga nazar tashlasak, bu masala uchun Lagranj funksiyasining ko„rinishi (4.39) formulada ko„rsatilgandek bo„lishigiga va qo„yilgan masalaning (4.30), (4.31) masalaning qo„yilishi bilan bir xil ekanligiga ishonch hosil qilamiz. Shuning uchun, bu teoremaning bundan keyingi isboti xuddi 2-teoremaning isboti kabi bo„ladi.

Тayanch iboralar

Chiziqsiz dasturlash, maqsad funksiya, chegaraviy shartlari, qavarik funksiya, maqsad funksiya, egar nuqta, cheklanish shartlar, butun sonli dasturlash, kasr- chiziqli dasturlash, Lagranj funksiyasi, separabel dasturlash, Kun-Тakker teoremasi, gradiyent usuli.

Тakrorlash uchun savollar

1. 
   Qavariq dasturlash masalasini qo„yilishini tushuntirib bering.
   
2. 
   Qavariq dasturlash uchun Lagranj funksiyasi qanday tuziladi?
   
3. 
   Lagranj funksiyasi egar nuqtasi nimani bildiradi?
   
4. 
   Kun-Тaker teoremasini tushuntirib bering.
   
5. 
   Kasr chiziqli dasturlash masalasining qo„yilishini tushuntirib bering.
   

5-BOB

DINAMIK DASТURLASHNING MAТEMAТIK MODELLARI

1. Dinamik dasturlash to‘g‘risida asosiy tushunchalar. Optimallik tamoyili

Chiziqli va chiziqsiz dasturlash masalalarida iqtisodiy jarayonlar vaqtga bog„liq emas deb qaraladi, shuning uchun masalaning optimal yechimi rejalashtirishning faqat bir bosqichi uchun topiladi. Bunday masalalar bir bosqichli masalalar deyiladi.

Dinamik dasturlash masalalarida iqtisodiy jarayonlar vaqtga bog„liq deb qaraladi hamda butun jarayonning optimal rivojini ta‟minlovchi bir qator (ketma-ket, har bir bosqich uchun alohida) optimal yechimlar topiladi. Dinamik dasturlash masalalari ko„p bosqichli yoki ko„p qadamli deb ataladi.
Dinamik dasturlash – vaqtga bog„liq va ko„p bosqichli boshqariluvchi iqtisodiy jarayonlarni optimal rejalashtirish usullarini o„rgatuvchi matematik dasturlashning bir bo„limidir.
Agar iqtisodiy jarayonning kechishiga ta‟sir ko„rsatish mumkin bo„lsa, bunday jarayon boshqariluvchi deyiladi. Jarayonning kechishiga ta‟sir etish uchun qabul qilinuvchi qarorlar to„plamiga boshqarish deb ataladi. Iqtisodiy jarayonlarda boshqarishni rejalashtirishning har bir bosqichida resurslarni taqsimlash, mablag„ ajratish va shu kabilar bilan ifodalanishi mumkin. Masalan, istalgan korxonada ishlab chiqarish – boshqariluvchi jarayondir, chunki u ishlab chiqarish vositalarining tarkibi, xomashyo ta‟minoti, moliyaviy mablag„lar miqdori va boshqa bir qator omillar bilan aniqlanadi. Rejalashtirish davridagi har bir yil boshida xomashyo bilan ta‟minlash, ishlab chiqarish uskunalarini almashtirish, qo„shimcha mablag„lar miqdori haqida qarorlar qabul qilinadi. Bunday qarorlar to„plami boshqarishdan iboratdir. Тabiiyki, eng ko„p miqdorda mahsulot ishlab chiqarish uchun korxonaga mumkin bo„lgan uskunalarning hammasini berish va ishlab chiqarish uskunalaridan
(texnika, stanoklar, texnologik liniyalar va boshqalardan) to„la foydalanish zarurdek tuyuladi. Lekin bu jihozlarni tezda eskirishiga (ishdan chiqishiga) va kelgusida mahsulot ishlab chiqarish hajmining kamayishiga olib kelishi mumkin. Demak, korxonaning faoliyatida salbiy oqibatlardan holi bo„lgan holda eskirgan jihozlarni almashtirish yoki o„rnini to„ldirish choralari belgilanishi lozim bo„ladi. Bu esa dastlabki davrda mahsulot ishlab chiqarish kamaysa ham, keyingi davrlarda korxonaning butun ishlab chiqarish faoliyatini kuchayishiga olib kelishi mumkin. Shunday qilib, yuqoridagi iqtisodiy jarayonlar har bir davrda uning rivojlanishiga ta‟sir etuvchi bir qancha bosqichlardan iborat deb qaralishi mumkin. Ko„p bosqichli iqtisodiy jarayonlarni rejalashtirish uchun, har bir oraliq bosqichda alohida qaror qabul qilishda, butun jarayonning tub maqsadi ko„zlanadi. Butun jarayonning yechimi o„zaro bog„langan yechimlar ketma-ketligidan iborat bo„ladi. O„zaro bog„langan bunday yechimlar ketma-ketligi strategiya deb ataladi. Oldindan tanlangan mezonga nisbatan eng yaxshi natijani ta‟minlovchi strategiya optimal strategiya deb ataladi. Boshqacha aytganda, optimal strategiya ko„p bosqichli iqtisodiy jarayonning optimal rivojlanishini ta‟minlovchi strategiyadir.
Dinamik dasturlash ko„p bosqichli tuzilishga ega bo„lgan yoki bunday
tuzilishga keltiriladigan masalalarning optimal yechimini topish uchun ishlatiladigan matematik vositadir.
Ko„plab iqtisodiy hodisa va jarayonlar o„z-o„zidan bosqichlarga bo„linadigan bo„ladi. Masalan, bir yillik rejalarni tuzishda har bir bosqich sifatida kvartal, oy, dekadalarni ko„rsatish mumkin. Lekin ba‟zi masalalar vaqtga bog„liq bo„lmasligi ham mumkin. Masalan, eng qisqa yo„l bilan ko„zlangan marraga (joyga) borish masalasi vaqtga bog„liq emas. Lekin bu masalani ko„p bosqichli masalaga aylantirib, uni dinamik dasturlash usuli yordamida yechish mumkin.
Ko„p bosqichli iqtisodiy masalalarni yechish uchun ularni yagona matematik modelini yoki bo„lmasa, har bir bosqichga mos keluvchi statik modellar tizimini tuzib, so„ngra uni dinamik dasturlash usullari bilan yechish lozim.
Shunday qilib, ko„p bosqichli jarayon sifatida ifodalanuvchi matematik dasturlash masalalarini yechish dinamik dasturlashning predmetini tashkil etadi.
Ko„p bosqichli jarayon deganda, vaqtga bog„liq ravishda rivojlanuvchi va o„z taraqqiyotida bir necha bosqichlarga bo„linuvchi jarayon tushuniladi.
Dinamik dasturlash quyidagi xususiyatlarga ega:

1. 
   dinamik dasturlash ko„p bosqichli jarayonning birdan-bir yagona yechimini emas, balki har bir bosqichga mos keluvchi va tub manfaatni ko„zlovchi yechimlar ketma-ketligini topishga yordam beradi;
   
2. 
   dinamik dasturlash yordami bilan yechilayotgan ko„p bosqichli masalaning ma‟lum bir bosqichi uchun topilgan yechimi undan oldingi bosqichlarda topilgan yechimlarga bog„liq bo„lmaydi. Unda faqat shu bosqichni ifodalovchi faktlar nazarga olinadi;
   
3. 
   dinamik dasturlash yordami bilan ko„p bosqichli masalani yechish jarayonining har bir bosqichida tub maqsadni ko„zlovchi yechimni aniqlash kerak, ya‟ni yechimlar orasida pirovard maqsadga erishishga maksimal hissa qo„shuvchi yechimni topish kerak.
   

Demak, ma‟lum bir bosqichda topilgan optimal reja faqat shu qadam nuqtai nazaridan emas, balki butun jarayonning tub (pirovard) maqsadi nuqtai nazaridan optimal reja bo„lishi kerak. bunday tamoyil “dinamik dasturlashning optimallik tamoyili” deb ataladi.
Optimallik tamoyiliga amal qilish har bir qadamda qabul qilingan yechimni kelgusida qanday oqibatlarga olib kelishini nazarga olib borish demakdir. Bundan tashqari optimallik tamoyilini yana quyidagicha talqin qilish mumkin.
Har bir bosqichdan avval tizimning holati qanday bo„lishidan qat‟iy nazar shu bosqichdagi optimal yutuq bilan undan keyingi bosqichlardagi optimal yutuqlarning yig„indisini maksimallashtiruvchi boshqarishni tanlash kerak. Demak, boshqarishning optimal strategiyasini topish uchun eng avval n -qadamdagi optimal strategiyani topish
kerak, keyin n va n 1-qadamlardagi optimal strategiyani va hokazo, barcha qadamlardagi
optimal strategiyani topish kerak.
Bu tamoyilga asosan dinamik dasturlash masalasini oxirgi n -qadamdagi optimal strategiyasini topishdan boshlash kerak. Buning uchun undan oldingi qadamdagi yechim haqida ayrim taxminlar qilinadi va bu asosda W mezonni

U

n
maksimallashtiruvchi ⁰ boshqarish tanlanadi. Bunday boshqarishga shartli

boshqarish deb ataladi. Demak, optimallik tamoyili har bir qadamda undan oldingi qadamning mumkin bo„lgan ixtiyoriy bir natijasi uchun shartli optimal boshqarishni topishni talab qiladi.

Keyingi paragraflarda dinamik dasturlash usullari bilan yechiladigan bir nechta iqtisodiy masalalar ko„rib chiqiladi.

2.