Javoblar chiziqsiz programmalashtirish

Teorema. f X( ) funksiya egar nuqtaga ega bo`lishi uchun maqsad funksiyaning minimumi qidiriladigan (11.1.1) – (11.1.3) masala uchun (11.1.10) – (11.1.13) shartlarning, maqsad funksiyaning maksimumi qidiriladigan (11.1.4) – (11.1.6) masala uchun (11.1.14) – (11.1.17) shartlarning bajarilishi zarur va yetarlidir (Teoremani isbotsiz qabul qilamiz).
Qavariq programmalashtirish masalasi (11.1.1) – (11.1.3) ning ekstremumi mavjudligining zaruriy va yetarlilik shartlari qanday hosil bo`lishi bilan tanishamiz. Buning uchun masalaga m+n ta S_i (i _1 ,m) va t _j ( j _1 ,n) qo`shimcha o`zgaruvchilar kiritib, uni quyidagi ko`rinishda
yozamiz:

g xi ( 1, x2, , xn )  Si  bi , i 1,^m	(11.1.18)
xj t j  0, j 1, ,n	(11.1.19)
Si  0, t j  0	(11.1.20)
Z  f x( 1, x2, ,xn )  ^min.	(11.1.21)

(11.1.18) - (11.1.20) tengsizliklar berilgan masalaning chegaraviy shartlaridan iborat bo`lib, noma’lumlarga nomanfiylik sharti qo`yilganligidan dalolat beradi. (11.1.18) – (11.1.21) masala uchun Lagranj funksiyasini tuzamiz:
m m

_i[b_i S_i  g x_i ( ₁, ,x_n )]__j (t _j  x_j ). (11.1.22)
i1 j1
Lokal ekstremum mavjudligining zaruriy shartidan:
^{0 0}

F X( ,  )  0, j  1 , n, xj			(11.1.23)
F X( ^0, ^0)  0, F X( ^0, ^0)  0, i  1 , m,	j  1, n^.		(11.1.24)

_j _j
(11.1.23) tenglikni tahlil qilamiz. Uni quyidagicha yoyib yozish mumkin:

Bundan tashqari	0 i j  xj i1 xj
	bi  Si  g xi ( 10 , x20 , , xn0 )  0,  0j 0 t j  x 		(11.1.26)

0 F X( 0 ) m 0 gi (X 0 ) 0 0. (11.1.25) tengliklar o`rinli.

t ⁰_j noma’lumlar bilan bog`liq bo`lgan _⁰_j Lagranj ko`paytuvchisi uchun
0j t0j  0
shart bajarilishi kerak. t<sup>0</sup><sub>j</sub>  0 bo`lganda _ ⁰_j  0 bo`ladi va (11.1.25) ga asosan
0 f X(xj 0 ) im1 i0 g Xi (xj 0 )  0. (11.1.27)

Agar t<sup>0</sup><sub>j</sub>  0 (demak, x<sup>0</sup><sub>j</sub>  0 ) bo`lsa, u holda _ ⁰_j  0 noldan farqli bo`lishi ham mumkin. Uning ishorasi quyidagi mulohaza orqali aniqlanadi: agar x<sub>j</sub> t <sub>j</sub>  0 tenglikning o`ng tomonini manfiy songa o`zgartirsak, (11.1.1) – (11.1.3) masalaning aniqlanish sohasi kengayadi, chunki ixtiyoriy x <sub>j</sub>  0 miqdor x<sub>j</sub>  b<sub>j</sub> (b<sub>j</sub>  0) tenglikni qanoatlantiradi va Z <sup>0</sup> <sub></sub> f X( <sup>0</sup> ) miqdor o`zgarmaydi (ortmaydi), demak, ^{F X( 0 )} _ 0 yoki _{ j}⁰  0 . Shunday qilib, x _j  0
b_j
da zaruriy shart quyidagidan iborat bo`ladi:

F X( x0,j 0 ) 00 f X(xj 0 ) im1 i0 g Xi (xj 0 )  0, (11.1.28)
x0j F X( x0,j 0 )  00 f X( 0 ) im1 i0 g Xi (xj 0 ) X 0  0 (11.1.29)

Endi ^{F X( 0 , 0 )} _ 0, i _1,m tenglikni xuddi yuqoridagidek taxlil qilib,
_i
quyidagi zaruriy shartlarni hosil qilamiz:
^{F X( 0 , 0 )} _ 0, (11.1.30)
x_i
x_i^{0 F X( 0 , 0 )} _ 0, _i⁰ _ 0.
_i
(11.1.31)
(11.1.28) – (11.1.31) shartlar (11.1.4) – (11.1.8) masala uchun quyidagi ko`rinishda bo`ladi:
^{F X( 0, 0 )} _ 0 , (11.1.32)
x_j
x⁰_j ^{F X( 0, 0 )} _ 0, x⁰_j  0 , (11.1.33)
x_j
^{F X( 0 , 0 )} _ 0 , (11.1.34)
_i
xi0 F X( 0 , 0 )  0, i0  0. (11.1.35)
_i
Yuqoridagi (11.1.28) – (11.1.31), (11.1.32) – (11.1.35) shartlar berilgan qavariq programmalashtirish masalasining ekstremumi mavjudligining zaruriy va yetarlilik shartidan iborat.

11.2. Kun – Takker teoremasi

g X_i ( )  g x_i ( ₁, x₂, , x_n )  b_i , i 1,m (11.2.1) x_j  0, j _1,n (11.2.2)
Z  f X( )  f x( ₁, x₂, , x_n )  max (11.2.3) qavariq programmalashtirish masalasini ko`raylik.
Agar kamida bitta X <sub></sub>G nuqtada g<sub>i</sub> (X ) <sub></sub> b<sub>i</sub> (i <sub></sub>1 ,m) tengsizlik bajarilsa (bunga Sleyter sharti deyiladi), Kun-Takkerning quyidagi teoremasi o`rinlidir.
Teorema. X ⁰ _ 0 nuqta (11.2.1) - (11.2.3) masalaning optimal yechimi bo`lishi uchun bu nuqtada (11.1.32) - (11.1.35) shartlarning bajarilishi zarur va yetarlidir.
Isbot. Zarurligining isboti yuqoridagi (11.1.28) - (11.1.31) va (11.1.32) - (11.1.35) shartlarni keltirib chiqarish jarayonida ko`rsatilgan. Yetarliligi. Faraz qilaylik, X ⁰ nuqtada (11.1.32) - (11.1.35) shartlar bajarilsin. U holda shunday _{ }⁰ 0 mavjud bo`lib, (X <sup>0</sup>, <sub></sub><sup>0</sup> ) nuqta F X( , <sub></sub>) Lagranj funksiyasining egar nuqtasi bo`ladi, ya’ni bu nuqtada (11.2.4) munosabat o`rinli bo`ladi:
F X( , _⁰ ) _ F X( ⁰, _⁰) _ F X( ⁰, _), (11.2.4) bu yerda
m
F X( ,  ) f X( )_i (g X_i ( )b_i). (11.2.5)
i1
(11.2.5) dan foydalanib, (11.2.4) ni quyidagi ko`rinishda yozamiz:
m m
f X( ) <sub>i</sub><sup>0</sup> (g X<sub>i</sub> ( ) b <sub>i</sub> )  f X( <sup>0</sup> ) <sub>i</sub><sup>0</sup> (g X<sub>i</sub> ( <sup>0</sup> ) b <sub>i</sub> ) 
i1 i1 m
 f X( <sup>0</sup> ) <sub>i</sub> (g X<sub>i</sub> ( <sup>0</sup> ) b <sub>i</sub> ), X  0,  0. (11.2.6)
i1
(11.2.6) ning o`ng tomonidagi
m m

6. 
   X( ⁰)_i⁰(g X_i ( ⁰)b_i)  f X( ⁰)_i (g X_i ( ⁰)b_i)
   

i1 i1 munosabat ixtiyoriy _ 0 uchun o`rinli. Bunda (11.1.34) va (11.1.35) ga asosan
m g X_i ( ⁰ )  b_i)  0, _i⁰(g X_i ( ⁰)  b_i)  0. (11.2.7)
i1
Endi (11.2.6) ning chap tomonidagi tengsizlikdan, (11.2.7) ga asosan,
m
 X 0 uchun f X( ⁰)  f X( )  _i⁰(g X_i ( )  b_i). Bu yerda, Sleyter shartiga ko’ra
i1

6. 
   X_i ( )_b _i  0 va _i⁰ _ 0 . Demak,
   

m
_i⁰ (g X_i ( )  b_i)  0
i1
Shuning uchun
f X( ⁰ )  f X( ), X  0.
Bundan X ⁰ berilgan masalaning optimal yechimi ekanligi ko`rinadi. Shu bilan teorema isbotlandi.
1–misol.
2x<sub>1</sub>  x<sub>2</sub>  2, 2x<sub>1</sub>  x<sub>2</sub>  8, x<sub>1</sub>  x<sub>2</sub>  6,
Z  f x( <sub>1</sub>, x<sub>2</sub> )  x<sub>1</sub><sup>2</sup>  x<sub>2</sub><sup>2</sup>  max
Masalani grafik usulda yechib, uning optimal yechimi X <sup>0</sup> <sub></sub> (0,8; 0,4) va f (0,8; 0,4) <sub></sub> 0,8 ekanini ko `rish mumkin.
Endi shunday _{ }⁰ 0 mavjud bo`lib, (X <sup>0</sup>,<sub></sub><sup>0</sup> ) da Kun-Takker shartlarining bajarilishini ko`rsatamiz.
Berilgan masala uchun Lagranj funksiyasini tuzamiz:
F X( ,   ) x₁²  x₂² ₁(2x₁  x₂ 2)₂ (82x₁  x₂ )₃(6 x₁  x₂ )
X ⁰ nuqtada masalaning 2-chegaraviy sharti qat’iy tengsizlikka aylanadi. Demak, bu masala uchun Sleyter sharti bajariladi. Bu holda masala normal bo`lib, <sub></sub><sup>0</sup> <sub></sub> 0 bo`ladi. Shuning uchun _⁰ _1 deb qabul qilinadi.
Lagranj funksiyasidan x x₁, ₂,_1, ₂, ₃ lar bo`yicha xususiy hosilalar olamiz:
<sup></sup>F  2x<sub>1</sub>  2 <sub>1</sub>  <sub>3</sub>, <sup></sup>F  2x<sub>2</sub>   <sub>1</sub>  <sub>2</sub>  <sub>3</sub>,
x<sub>1</sub> x<sub>2</sub>
<sup>F</sup>  2x<sub>1</sub>  x<sub>2</sub> 2, <sup>F</sup> 82x<sub>1</sub>  x<sub>2</sub>, <sup>F</sup>  6 x<sub>1</sub>  x<sub>2</sub>
<sub>1</sub> <sub>2</sub> <sub>3</sub>
<sup>F X( 0 ,0 )</sup> <sub></sub> 82 0 ,80,4  6  0,
<sub>2</sub>
<sup>F X( 0 ,0 )</sup> <sub></sub> 60,80,4  4,8  0.
<sub>3</sub>
i0 F X( 0 ,0 )  0
<sub>i</sub>
shartga ko`ra _2 va _3 larning qiymatlari nolga teng.
F X( 0 ,0 )  2 0 ,80,42  0
₁
bo`lgani uchun <sub>i</sub> nolga teng bo`lmagan qiymat qabul qilishi ham mumkin.
0j F X( 0, 0 )  0, x0j  0 .
_j
Demak, j=1, 2 qiymatlar uchun ^{F X( 0,0 )} _ 0 bo`lishi kerak, ya’ni
<sub>j</sub>
<sub></sub> 2 0,8  2<sub>1</sub> <sub>3</sub>  0
<sub></sub> 2 0, 4 <sub>1</sub> <sub>2</sub> <sub>3</sub>  0.
 <sub>2</sub>, <sub>3</sub>  0bo`lgani uchun _1  0,8 va _{ }⁰ (0, 8; 0, 0) . Demak,
(X ⁰, _⁰) _ (0,8; 0,4; 0,8; 0, 0) nuqtada, haqiqatan ham, Kun-Takker shartlari bajarildi, ya’ni u egar nuqta ekan.
2–misol. Kun-Takker shartlaridan foydalanib, X ⁰ _ (1,0) nuqta quyidagi chiziqsiz programmalashtirish masalasining yechimi ekanligi ko`rsatilsin:
f X( )  x<sub>1</sub><sup>2</sup>  2x<sub>1</sub> 3x<sub>2</sub><sup>2</sup>  max
4x<sub>1</sub> 5x<sub>2</sub>  8
2x<sub>1</sub>  x<sub>2</sub>  4 x<sub>1</sub>  0, x<sub>2</sub>  0.
Yechish.
X <sup>0</sup>  (1,0) nuqtada chegaraviy shartlar qat’iy tengsizlikka aylanadi, demak Sleyter sharti bajariladi. Bu holda <sub></sub><sup>0</sup> <sub></sub>1 deb qabul qilishimiz mumkin.
Shuning uchun Lagranj funksiyasi quyidagi ko`rinishda bo`ladi.
F x x( ₁, ₂,₁, ₂ )  x₁²  2x₁  3x₂² ₁(4x₁  5x₂ 8) ₂ (2x₁  x₂  4)^, x₁  0, x₂  0,  ₁  0, ₂  0.
Kun-Takker shartlarining bajarilishini tekshiramiz:
F X( ⁰ ,⁰ )

 _x⁰₁,⁰ )  (2x1 2 4 ₁  2 ₂ ⁾X0  0^,
F X(

 (6x
x_{2 2} 5 ₁  ₂ ⁾_X0  0,
F X( ⁰,⁰ )
 (4x₁ 5x₂ ⁸⁾_X0   4 0,
₁
F X( ⁰,⁰ ) F X( ⁰,⁰ ) ₀
 (2x₁  x₂ ⁸⁾_X0   2 0, x₁  0,
₂ x
^{0 0 0 0} 1
F X( , ) ₀ F X( , ) _{0 0}
x2  0, x x1, 2  0; 1  0  ( 4) 0 1  0,
x2 1
F X( 0,0 ) 0 0 0
₂  0  ( 2)₂  0 ₂  0.
₂
Shunday qilib, (X ⁰, _⁰ ) _ (1; 0; 0; 0) nuqta Kun-Takkerning hamma shartlarini qanoatlantiradi. Demak, u Lagranj funksiyasining egar nuqtasi bo`ladi. Shuning uchun X ⁰ _ (1,0) nuqta berilgan chiziqsiz programmalashtirish masalasining yechimidan iborat.