Kvadratik programmalashtirish masalasi

Kvadratik programmalashtirish masalasi Reja: Kvadratik programmalashtirish masalasining matematik modeli. Yordamchi masala tuzish. Masalani yechish usuli. Kvadratik programmalash masalasi chiziqsiz programmalash masalasining xususiy xolidan iboratdir. Uning matematik modelidagi chegaraviy shartlar chiziqli tenglama va tengsizliklardan, maqsad funksiyasi esa umumiy holda chiziqli va kvadratik formalarning yig'indisidan iborat bo'ladi. , (1) xj0, (2) Z=f(x)= (3) Yeki matritsa formada: AX, B, (4) X0 (5) Z=SX+X DXmax(min) (6) Bu yerda A mxn o'lchovli matritsa, D n o'lchovli kvadrat matritsa, V m o'lchovli, X, S n o'lchovli vektorlar. Shunday qilib (1)-(3) eki (4)-(6) ko'rinishda berilgan masalani kvadratik programmalash masalasi deb ataymiz. Bu masala chiziqli programmalash masalasidan shu bilan farq kiladiki, uning maqsad funksiyasida kvadratik forma X DX katnashadi. Bu kvadratik formaga bog'liq ravishda f(X) maqsad funksiya pastga eki yuqoriga kavarik bo'lishi mumkin. Ana shunday xollar uchun, yani kvadratik programmalash masalasi yagona optimal (global) yechimga ega bo'lgan xollar uchun masalani effektiv yechish usullari yaratilgan. Kvadratik programmalash masalasi (1)-(3) berilgan bulsin. maqsad funksiyaning minimumi kidiriladigan masalani uning maksimumi kidirilgan masalaga keltirish mumkin bo'lganligi sababli (3) ning o'rniga bundan keyin Z=f(x)= (6) funksiyani eki matritsali formadagi Z=SX+X'DXmax(min) (7) funksiyani kuramiz. Bundan keyin f(x) funksiyani yuqoriga kavarik funksiya , yani Z=X'DX kvadratik formani yuqoriga kavarik funksiya deb faraz kilamiz. Bu holda (1)-(3) shartlarni kanoatlantiruvchi planlar to'plami kavarik to'plam bo'lgani uchun kvadratik programmalash masalasi yagona optimal yechimga ega bo'ladi. Masalaning (1) shartlarini qo'shimcha o'zgaruvchilar kiritish erdamida tenglamalarga keltirish mumkin bo'lgani uchun (1) -(3) masalani quyidagi ko'rinishda ifodalaymiz: , i=1,m (8) xj0, j=1,n (9) Z=f(x)= (10) eki matritsali formada AX B, (11) X0 (12) Z= f(x)=C X+X DXmax (13) Bu masalaning plani optimal plan bo'lishining zaruriy va etarlilik shartlarini aniklaymiz. Buning uchun Lagranj funksiyasini tuzamiz. F(X,)= (14) F(X,) funksiyadan xj va i bo'yicha xususiy hosilalar olamiz: (15) yuqoridagi munosabatlarga asoslanib, Kun- Takkerning shartlarini ezamiz: (16) Agar shunday 0 vektor mavjud bo'lib, X0, 0 lar uchun (1)-(6) shartlar urinli bulsa, X0 vektor berilgan kvadratik programmalash masalasi (11)-(13) ning optimal yechimi bo'ladi. Endi (1) tengsizlikni qo'shimcha o'zgaruvchilar kiritish erdamida tenglamaga aylantiramiz: S+2DX0-A0+V*=0 Bundan V*= A0+2DX0 - S (17) Bu holda kvadratik programmalash masalasi planining optimal plan bo'lishlik sharti kuyidagicha bo'ladi: S+2DX*-A*+V*=0, (18) X*V*=0, X*0, V*0 (19) Berilgan masaladagi (11) shartlar tenglama ko'rinishida bo'lganligi sababli ga musbat bo'lishlik sharti kuyilmaydi. Bundan tashqari, (14)-(15) shartlar ixtieriy tayanch planlar uchun urinli bo'lganligi sababli ularni tashlab yuborish mumkin. Demak, xulosa qilib shuni aytish mumkinki, quyidagi AX=V, (20) 2DX- A*+V+ S=0, (21) XV=0, (22) X0, V0 (23) shartlarni kanoatlantiruvchi xar ...