Javoblar chiziqsiz programmalashtirish

10.8. Chegaraviy shartlari tengsizlik tarzida bo`lgan masalalar Chegaraviy shartlari tenglik tarzida bo`lgan yuqoridagi masala uchun keltirilgan tasdiqlardan foydalanib, chegaraviy shartlari tengsizlik tarzida bo`lgan masalalar uchun ham ayrim natijalarni keltiramiz.
Faraz qilaylik, quyidagi masala qaralayotgan bo`lsin: f  X   min, (10.8.1) g_i X  0, i _1 ,m. (10.8.2)
Bu masalani tenglik tipidagi ushbu
f  X   min (10.8.3)
g_i X  x_{n i}²_  0, i _1 ,m (10.8.4) masalaga ekvivalentligini yuqorida keltirgan edik. Shu ekvivalentlikdan foydalanib, (10.8.3) va (10.8.4) masala uchun nisbiy shartli minimumning zaruriy va yetarli shartlarini ifodalaymiz.
Ta’rif. Biror g_k  X   0, 1_ k _ m chegaraviy shart X ⁰ joiz nuqtada aktiv
(faol) deyiladi, agar g_k X ⁰   0 bo`lsa hamda passiv (sust) deyiladi, agar g<sub>k</sub> X <sup>0</sup>   0 bo`lsa.
Ko`rsatish mumkinki, agar X <sup>0</sup> joiz nuqtada aktiv bo`lgan _i1,_i2,_...,ik indeksli barcha chegaraviy shartlar uchun

gi1 X 0 ,gi2 X 0 , ... ,gik X 0 , 1 i1  i2   ik  m (10.8.5)
x x x
vektorlar chiziqli erkli bo`lsa, (10.8.3)-(10.8.4) masala uchun

^X ⁰, g₁ X ⁰ _ ¹² , ... , _g_m X ⁰ _ ¹² _^ nuqta normal nuqta bo`ladi. Shu sababli,
<sub> </sub>
(10.8.5) vektorlarni chiziqli erkli deb faraz qilib, Lagranj normal funksiyasini yozamiz:
m
F X x , <sub>n1</sub>,x<sub>n2</sub>, ... ,x<sub>n m</sub> ,  f X  <sub>1</sub>g<sub>1</sub> X   ... <sub>m</sub>g<sub>m</sub> X   <sub>i</sub>x<sub>n i</sub><sup>2</sup><sub></sub> .
i1
Lagranj ko`paytuvchilari qoidasiga binoan, agar X ⁰ _X ⁰,x_n⁰_1,...,x_{n m}⁰_ 

(bu yerda x_{n i}⁰_  _ g_i X ⁰ _ ¹² , i _1,m) nuqta (10.8.3)-(10.8.4) masalaning nisbiy shartli minimum nuqtasi bo`lsa, bu nuqtada
F X <sup>0</sup>  f X <sup>0</sup>  g<sub>1</sub> X <sup>0</sup>  g<sub>m</sub> X <sup>0</sup> 
 <sup>1</sup>  ... <sup>m</sup>  0
x x x x
F X 0  0
 21xn1  0
x<sub>n1</sub> (10.8.6)
....................................
F X 0  0
 2mxn m  0 xn m
munosabatlarning o`rinli bo`lishi zarur.
Agar (10.8.3) va (10.8.4) masala uchun ham Lagranj funksiyasini
F X ,  f  X  ₁g₁  X  ..._m g_m  X _ kiritsak, nisbiy minimumning zaruriy sharti, ya’ni (10.8.6) munosabatlar
 F X 0,  0, (10.8.7)
x

_ix_{n i}⁰_  0 yoki _ig_i X ⁰   0, i 1,^m (10.8.8)
ko`rinishda ifodalanadi. Odatda, (10.8.7) shartni passivlikni to`ldiruvchi shart deyiladi.
Shunday qilib, (10.8.1), (10.8.2) masalada f  X  funksiya X ⁰ joiz nuqtada nisbiy shartli minimumga erishishi uchun shu nuqtada (10.8.7) va (10.8.8) shartlarning bajarilishi zarur.
Lagranj funksiyasining ikkinchi tartibli hosilalari matritsasi
²F X ⁰,  
 ₂ 0 
 x 
 2_1 0 ... 0  (10.8.9)
 
_ 0 ...................... _
 0 0 ... 2m 
ko`rinishda bo`ladi. Bu yerda ^{ 2 F X} ₂^{0 ,} ham _nn o`lchovli matritsadan x
iborat. (10.8.9) matritsaga nisbatan yozilgan kvadratik forma va (10.8.4) chegaraviy shartlar uchun yozilgan urinma gipertekisliklarni yozib, ayrim soddalashtirishlar bajarsak, (101.8.1),(10.8.2) masala uchun quyidagi yetarlilik shartini olamiz.
Ta’rif. Qaralayotgan (10.8.1), (10.8.2) masalada X ⁰ joiz nuqta shartli-statsionar nuqta deyiladi, agar shunday _{ }  ₁,..., _m  0 topilsaki, F X ,  f  X  ₁g₁  X  ..._m g_m  X _ Lagranj funksiyasi uchun
F X ⁰,
 0,
^x

_i g_i X ⁰   0, i 1,m
shartlar bajarilsa.
Teorema. (10.8.1), (10.8.2) masalada shartli-statsionar nuqtaning nisbiy minimum nuqta bo`lishi uchun, X <sup>0</sup> nuqtada aktiv bo`lgan _i1,_i2,_...,ik indeksli chegaraviy shartlarga nisbatan tuzilgan
 1 0  y  0, ... , gik X 0  y  0 gi X  
x x
gipertekislikda
y² F X 2⁰ ,^ y

x
kvadratik formaning aniq musbat bo`lishi yetarlidir.
Yuqoridagi shartlarni aniq bir masala uchun qo`llab ko`raylik.

Masala.

6. 
   x x ₁, ₂   x₁²  x₂² 12x₁ 16x₂  extr,
   
7. 
   x x ₁ 2 x22 25  0.
   

, 2   x1 
Bu masaladagi chegaraviy shart aktiv bo`lgan nuqtada
 g 

g x x 1x, 2   xg1   22xx12   0
    
x₂ 
bo`lgani uchun Lagranjning normal funksiyasini tuzamiz:
Fx<sub>1</sub>,x<sub>2</sub>,<sub></sub>  x<sub>1</sub><sup>2</sup>  x<sub>2</sub><sup>2</sup> 12x<sub>1</sub> 16x<sub>2</sub> <sub></sub>x<sub>1</sub><sup>2</sup>  x<sub>2</sub><sup>2</sup> 25
Chegaraviy shartlari tengsizlik tarzida bo`lgan masala uchun keltirilgan (10.8.7), (10.8.8) zaruriy shartga asosan, biror joiz nuqtada funksiya shartli ekstremumga erishsa, u nuqtada quyidagi tengliklar o`rinli bo`lishi zarur:
F
_{ x1}  2x1 12  2x₁  0,
^F _ 2x₂ 16 _ 2_x₂  0,
x₂
x12  x22  25 0.
Oxirgi tenglikda, _{ 0} bo`lsa (x<sub>1</sub><sup>2</sup> <sub></sub> x<sub>2</sub><sup>2</sup> <sub></sub>25 <sub></sub> 0), x<sub>1</sub>  6, x<sub>2</sub>  8 bo`lib, bu joiz nuqta bo`lmaydi, shu sababli <sub> 0</sub>. Demak, <sub>x1</sub><sup>2</sup> <sub> x2</sub><sup>2</sup> <sub> 25</sub> bo`lishi zarur.
Natijada, quyidagi sistemani yechib,
x₁ x₁  6,
x₂ _x₂ 8,
x12  x22 25.
A(+3; -4) va B(-3; +4) ekstremal nuqtalarga ega bo`lamiz. Bu yerda A nuqtaga <sub> 1</sub> va B nuqtaga <sub> 3</sub> qiymatlar mos keladi. Dastlab funksiyani A(3; -4) nuqtada tekshiraylik. Bu nuqtaga mos urinma tekislik
3у<sub>1</sub>  4у<sub>2</sub>
to`g`ri chiziqdan iborat bo`ladi. Ikkinchi tartibli kvadratik forma esa
у1 у24 0 у1  4у12  у22 0
0 4 у₂
aniq musbat bo`ladi. Demak funksiya A(3, 4) nuqtada shartli minimumga erishadi, hamda f<sub>min</sub>  f 3, <sub></sub> 4  75 bo`ladi.
Endi funksiyani B(-3; 4) nuqtada tekshiraylik. Bu nuqtaga mos urinma tekislik ham 3u₁=4u₂ bo`ladi. Mos ikkinchi tartibli kvadratik forma
у1 у2  4 0   у1   4у12  у22  0
0  4  у<sub>2</sub>
bo`lib, aniq manfiy bo`ladi. Bu esa B(-3, 4) nuqtada funksiya shartli maksimumga erishishini tasdiqlaydi:
f_max  f 3, 4 125.

2.QAVARIQ PROGRAMMALASHTIRISH

11.1. Kun – Takker shartlari

Qavariq programmalashtirish optimallashtirish masalasining bir bo`limi bo`lib, u pastga (yuqoriga) qavariq funksiyani qavariq to`plamda minimallashtirish (maksimallashtirish) nazariyasini o`rgatadi.
Boshqacha qilib aytganda, qavariq programmalashtirish masalasi deganda

g_i (X )  g x_i ( ₁, x₂, , x_n )  b_i , i 1 ,m , (11.1.1) x_j  0, j _1,n , (11.1.2)
Z  f X( )  f x( ₁, x₂, , x_n )  min (11.1.3)
ko`rinishdagi masala nazarda tutiladi, bunda g X<sub>i</sub> ( ), f X( ) funksiyalar G <sub></sub> E<sub>n</sub> qavariq to`plamda aniqlangan pastga qavariq funksiyalar. Agar f X( ), g X_i ( ) funksiyalar G da aniqlangan yuqoriga qavariq funksiyalar bo`lsa, qavariq programmalashtirish masalasi quyidagi ko`rinishda beriladi:

g_i (X )  g x_i ( ₁, x₂, , x_n )  b_i , i 1 ,m (11.1.4) x_j  0, j _1,n (11.1.5)
Z  f X( )  f x( ₁, x₂, , x_n )  max (11.1.6)
(11.1.1) – (11.1.3) va (11.1.4) – (11.1.6) masalalarning yechimini aniqlashda klassik Lagranj usulining chegaraviy shartlari orasida tengsizliklar qatnashgan masalalar uchun umumlashtirishga ko`maklashuvchi Kun – Takker teoremasi markaziy o`rinni egallaydi. Kun – Takker teoremasi (11.1.1) – (11.1.3) yoki (11.1.4) – (11.1.6) masalaning optimal yechimi va bu masala uchun tuzilgan Lagranj funksiyasining egar nuqtasi orasidagi munosabatni o`rgatadi. (11.1.1) – (11.1.3) yoki (11.1.4) – (11.1.6) masalaga mos keluvchi Lagranj funksiyasini yuqorida ko`rilgan usul yordamida tuzamiz:

F x( ₁, x₂, , x_n ,    ₁, ₂, , _m )  f x( ₁, x₂, , x_n )  ^m
 _i (b_i  g x_i ( ₁, x₂, , x_n ))
i1 yoki
m
F X( , )  ₀ f X( )  _i g_i (X), (11.1.7)
i1
bu yerda _i (i  0,m) Lagranjning noma’lum ko`paytuvchilari bo`lib,

  ( ₀, ₁, ,_m), X  (x₁, x₂, ,x_n)^.
1–ta’rif. Agar X ⁰ _ (x₁⁰, x₂⁰, ,x_n⁰ ) nuqtada F X( ⁰, _) funksiya minimumga erishib, _{ }⁰ (_{  1}⁰, ₂⁰, , _m⁰ ) nuqtada F X( , _⁰) funksiya maksimumga erishsa, F X( ⁰, _⁰ ) nuqta Lagranj funksiyasi (11.1.7) ning egar nuqtasi deyiladi. Agar F X( ⁰, _⁰ ) nuqta (11.1.1) - (11.1.3) masala uchun tuzilgan Lagranj funksiyasi F X( , _) ning egar nuqtasi bo`lsa, X <sup>0</sup> <sub></sub> (x<sub>1</sub><sup>0</sup>, x<sub>2</sub><sup>0</sup>, ,x<sub>n</sub><sup>0</sup> ) ning kichik musbat <sub></sub> atrofidagi ( (<sub></sub> X <sup>0</sup> ) <sub></sub>{X / X <sub></sub> X<sub>0</sub> <sub></sub>}) ixtiyoriy x <sub>j</sub>  0 uchun va
<sup>0</sup> ning <sub></sub> atrofidagi ( (<sub> </sub><sup>0</sup> ) <sub> </sub>{ / <sub>  0</sub> <sub></sub>}) ixtiyoriy <sub></sub> 0 uchun
F X( <sup>0</sup>, <sub> </sub>) F X( <sup>0</sup>, <sub></sub><sup>0</sup>) <sub></sub> F X( , <sub></sub><sup>0</sup>) (11.1.8) munosabat o`rinli bo`ladi.
F X( , <sub></sub>) Lagranj funksiyasi (11.1.4) – (11.1.6) masala uchun tuzilgan bo`lsa, bu munosabat quyidagi ko`rinishda ifodalanadi:
F X( , <sub></sub><sup>0</sup> ) <sub></sub> F X( <sup>0</sup>, <sub></sub><sup>0</sup>) <sub></sub> F X( <sup>0</sup>, <sub></sub>). (11.1.9)
(11.1.8), (11.1.9) munosabatlar Lagranj funksiyasi (11.1.7) ning egar nuqtasining mavjudligi haqidagi, f X( ) va g X<sub>i</sub> ( ) (i <sub></sub>1 ,m) funksiyalar differensiallanuvchi bo`lmagan hol uchun zaruriy va yetarlilik shartlaridan iborat.
f X( ) va g_i (X ) (i _1 ,m) funksiyalar differensiallanuvchi bo`lgan holda Lagranj funksiyasi (11.1.7) ning egar nuqtasi mavjudligining zaruriy va yetarlilik shartlari (11.1.1) – (11.1.3) masala uchun quyidagicha ifodalanadi:
^{0 0}

F X( ,  )  0, xj			(11.1.10)
x0j F X( ^0, ^0)  0, xj	x^0j  0,		(11.1.11)
F X( 0 , 0 )  0, i			(11.1.12)
i0 F X( ^0, ^0)  0,	i0  0.		(11.1.13)

_i
Maqsad funksiyasining maksimumi qidiriladigan (11.1.4) – (11.1.6) masala uchun esa bu shartlar quyidagi ko`rinishga ega bo`ladi:
^{0 0}

F X( ,  )  0, xj			(11.1.14)
x0j F X( ^0, ^0)  0, xj	x^0j  0,		(11.1.15)
F X( 0 , 0 )  0, i			(11.1.16)
i0 F X( ^0, ^0)  0,	i0  0.		(11.1.17)

_i
Osonlik bilan ko`rsatish mumkinki, agar (11.1.10) – (11.1.13) va (11.1.14) – (11.1.17) munosabatlar bajarilsa, (11.1.8)–(11.1.9) munosabat o`z-o`zidan bajariladi. Shuning uchun, bundan keyin Lagranj funksiyasining egar nuqtasi mavjudligi haqida Kun – Takker shartlari sifatida (11.1.10) – (11.1.13) va (11.1.14) – (11.1.17) shartlarni tushunamiz. Bunda quyidagi teorema o`rinli bo`ladi.