Qavariq programmalashtirish masalasi

Yuklangan vaqt:

08.08.2023

Ko'chirishlar soni:

0

Hajmi:

158.10546875 KB

Ko'chirib olish

Qavariq programmalashtirish masalasi
Reja:
1. Qavariq programmalashtirish masalasi .
2. Qavariq programmalashtirishning asosiy masalasi. Sodda xossalar.
3. Optimallikning zaruriy va yetarli shartlari. Kun-Takker teoremasi .
4. Lagranj funksiyasining egar nu q tasi.
Asosiy adabiyotlar
1. Р.Габасов, Ф.М.Кириллова. Оптималлаштириш усуллари. Т. Узбекистон,
1995.
Qo’shimcha adabiyotlar
2. Васильев Ф.П. Численные методы решения экстремальных задач. М.
Наука, 1988.
3. Галеев Е.М., Тихомиров В.М. Краткий курс теории экстремальных задач.
М: Изд МГУ. 1989.
4. Карманов В.Г. Математическое программирование. М.Наука.1998.
5. Сухарев А.Г., Тимохов А.Н., Фёдоров В.В. Курс методов оптимизации.
М. Наука 1988
6. Исроилов И., Отакулов С. Вариацион хисоб ва оптималлаштириш
усуллари. I -кисм. Самарканд. Сам ДУ нашри, 1999, II -кисм Самарканд,
СамДУ нашри, 2001

1 Qavariq programmalashtirish masalasi
  n R Q Q x x f    , min,
(1)
berilgan bo’lsin, bu yerda Q- qavariq to’plam,
  Q x f  da aniqlangan qavariq
funksiya.
1. Optimallik kriteriysi . Qavariq funksiyalarning ekstremumlari haqidagi
natijalar asosida , ( I ) masala uchun quyidagi optimallik kriteriysiga ega bo ’ lamiz .
I-teorema.
 x f funksiya Q x  nuqtada differensiallanuvchi qavariq
funksiya bo’lsin.
Q x  - (1) masalada optimal bo’lishi uchun

  Q x ,0 ) ( * *    
  x
x f x x T (2)
munosabatning bajarilishi zarur va yetarlidir.
Agar
Q x int bo’lsa, (2) munosabat,   0 /    x x f stasionarlik shartiga teng
kuchlidir.
Agar
  n j b x a R x Q j j j n ...,2,1 , :       n j b a j j .1 ,      bo’lsa,
(2) munosabat quyidagiga ekvivalent:

 





   
  
  

  

..1 , , ,0
, ,0
, ,0
n j b x агар
a x агар
b x a агар
x
xf
jj jj jjj
j
(3)
1-misol.
  .0 ,0 min, 2 4 2 5 2 3 1 3 3 2 2 1 23 22 21          x x x x x x x x x x x f (4)
Bu masalada
  3R x f  da qavariq funksiya,  . 0 , 0 : 3 0 1 3     x x R x Q Optimallik
kriteriysidan foydalanib ((3) munosabatga qarang),
,0 2 2 2 1 1
   
 x x x
f

  ,0 2 2 2 1 1   x x x ,0 4 2 4 3 1 2 2
    
 x x x x
f
,0 2 4 10 2 3 3
    
 x x x
f

  .0 2 4 10 233    x x x
sistemani tuzamiz. Bu sistemani yechi, yagona
 3/1,3/1,0   x
nuqtani topamiz.
Demak,
   4 3/1,3/1,0  x masalaning yagona yechimidir.

2. Qavariq programmalashtirishning asosiy masalasi. Sodda xossalar.nR P 
- qavariq tuplam,     P S i x g x f i   ,1 , , da qavariq funksiyalar,
  , ,1 , m S i b x a x g Ti i    
- chiziqli funksiyalar bo’lsin  . ,1 , , 10 m S i R b R a i n i    
      ,0 , ,1 ,0 , ,1 ,0 :             i Ti i i Ti i i n b x a x g k S i b x a x g S i x g R x Q
 P x m k i    , ,1
to’plamni qaraymiz. Qavariq to’plam va qavariq funksiyalarning
xossalariga asosan,
Q qavariq to’plamdir. Bu holda , (1) masala
      , ,1 ,0 , ,1 0 min, k S i b x a x g S i x g x f i Ti i i         

  . , ,1 ,0 P x m k i b x a x g i Ti i       (5)
ko’rinishda yoziladi va u qavariq programmalashtirishning asosiy masalasi deb
ataladi.
(5) masalaning qavariq funksiyalarning ekstremal xossalaridan kelib
chiquvchi quyidagi sodda, ammo muhim xossalarini sanab o’tamiz:
a) (5) masalaning lokal optimal rejasi uning global optimal rejasi ham bo’ladi;
b) (5) masalaning optimal rejalar to’plami qavariqdir;
v) agar
 x f - qatiy qavariq funksiya bo’lsa, (5) masalaning optimal rejasi
yagonadir;
g)
 x f - uzluksiz kuchli qavariq funksiya,   P S i x gi   , ,1 , da uzluksiz qavariq
funksiyalar bo’lsa, (5) masalaning yagona optimal rejasi mavjud.
3. Optimallikning zaruriy va yetarli shartlari. Kun-Takker teoremasi.
(5) ko’rinishdagi qavariq programmalashtirish asosiy masalasi uchun
optimallikning zaruriy va yetarli shartlarini bayon qilamiz. (5) masala uchun

        m
i ii x g x f x F
10 , ~, ~   
 m    ,...., , ~
1 0 
umumlashgan Lagranj funksiyasi va

            m
i mii x g x f x F
1 1 ,...., , ,     

regulyar Lagranj funksiyasidan foydalanamiz.

2-teorema. Q x  nuqtaning (5) masalada optimal bo’lishi uchun shunday
  0 ,..., , ~
1 0       m   
topili, k i i ,1 ,0 ,0 0       

   , ~, ~ min ~, ~ *  x F x F Px
   (6)

  . ,1 ,0 * * k i x gi i    (7)
shartlarning bajarilishi zarur, 1
*0
bo’lganda esa, yetarli ќ amdir.
Isboti. Zaruriyligi: Quyidagi sistemani qaraymiz:
   
 
  




  
 
  
. ,1 ,0
,1 ,0
,0
m k i x g
k i x g
x f x f
i
i
(8)
Bu sistema
P x yechimga ega emas. Chunki, agar u biror P x yechimga ega
desak,
*x ning optimalligiga zid bo’lgan,     Q x xf x f   ,* munosabatga ega
bo’lamiz (bu yerda
Q (5) masalaning rejalar to’plami). (8) sistemaga Fan
teoremasini qo’llaymiz (9-§). Shu teoremaga asosan, bir vaqtda nolga teng
bo’lmagan shunday
, ,1 ,0 ,0 * *0 k i i      * *1 ,..., m k   
sonlar mavjudki,
        
     m
i ii P x x g xf x f
1 ***
0 ,0  

tengsizlik bajariladi. Bu yerdan

           m
i ii P x x g x f xf
1 **
0**
0 . ,   
(9)
tengsizlikni olamiz. (9) da *
x x
deb olsak,
  0 1 ** 
m
i ii x g 
bo’ladi. Ikkinchi
tomondan,
    m k i x g k i x g o i i i ,1 ,0 , ,1 ,0 , * * *        bo’lgani uchun,
  

m
i i i x g
1
* * 0 
(11)
tengsizlik bajariladi. (10), (11) munosabatlardan,
  
 m
i ii x g
1 ** 0 
(12)

tenglik kelib chiqadi. Lagranj funksiyasining ko’rinishini va (12) ni hisobga oli,
(9) dan quyidagi tengsizlikni olamiz:              . , ~, ~ ~, ~
*
1 1 **
0**
0****
0** P x x F x g x f xf x g xf x F m
i m
i iiii          
        
.
Demak, (6) tenglik isbotlandi.
(12) dan (7) tengliklar kelib chiqadi. Haqiqatan ham,
  k i x gi i ,1 ,0 * *   
bo’lganligidan, agar biror
K i i   * * 1, uchun   0 ** x g
ii 
desak,     m
i ii x g
1 ** 0 
ya’ni
(12) ga zid munosabatga ega bo’lamiz.
Yetarliligi. 1
*0
bo’lsin. U vaqtda (6) munosabat regulyar Lagranj
funksiyasi yordamida
    P x x F x F    , , , * * *  
(13)
ko’rinishi oladi. Endi (7) va (13) dan foydalani, ixtiyoriy
Q x uchun quyidagiga
ega bo’lamiz:

                ***
1 **** , ,    x F x F x g xf xf m
i ii       
 
m
i i i x f x g x f
1
* . 

Demak,
    Q x x f xf    , *
, ya’ni *x -(5) masalaning optimal rejasidir. 
1-t a’ r i f. Agar (5) masalaning
*x - optimal rejasida bajarilishi zarur bo’lgan
(6) shartda
0 *0  bo’lsa, qavariq programmalashtirish asosiy masalasi regulyar
deyiladi.
Regulyar masalada 1
*0
deb olish mumkin. (5) masalaning rejalar to’plami
Q
uchun quyidagi shartlarni qaraymiz:
a)
P -poliedr,  x f va barcha   m i x gi ,1 ,  , funksiyalar chiziqli;
b)
m k (ya’ni tenglik ko’rinishdagi cheklashlar yo’q) va shunday P x~ nuqta
mavjudki,
  m i x gi ,1 ,0 ~   (Sleyter sharti);
v)
P -poliedr, W W P ,  - nisbiy ochiq qavariq to’plam,  x f W riW ,  ,   , ,1 , S i x gi 
funksiyalar W
da qavariq va shunday
Q x~ topiladiki,   S i x gi ,1 ,0 ~   ;

g) shunday Q riP x  ~ nuqta mavjudki,   S i x gi ,1 ,0 ~   .
Bu shartlarga (5) masalaning uchun regulyarlik shartlari deyiladi.
3-teorema. (5) masala a), b), v), g), regulyarlik shartlaridan birortasini
qanoatlantirsin. U vaqtda
*x rejaning optimal bo’lishi uchun, shunday  * *1 * ,..., m   
topili,
, ,1 ,0
* k i
i  
   
 



 

kixg xFxF
ii Px
,1,0 ,,min,
** *** 
 
(14)
munosabatlarning bajarilishi zarur va yetarlidir.
Isboti. Teoremaning yetarlilik qismi 2-teoremadan kelib chiqadi.
Zaruriyligi. Teoremaning zaruriylik qismini a) yoki b) regulyarlik shartlari
bajarilganda isbotlash bilan cheklanamiz. Uning v) yoki g) regulyarlik shartlari
bajarilgandagi isbotini [11] dan ko’rish mumkin.
1)
P - poliedr,       xgxgxf
m,...,,
1
funksiyalar chiziqli, rejalar to’plami Q
bo’sh bo’lmasin. Quyidagi sistemani qaraymiz:
    0 *  xf x f
(15)

 
  


  
 
. ,1 ,0
,1 ,0
m k i x g
k i x g ii
(16)
Q x *
- optimal reja bo’lgani uchun (15) – (16) sistema P x yechimga ega emas.
Ammo farazimizga ko’ra, (16) sistema
P x yechimga ega. U vaqtda 9-§ dagi 3-
teoremaga asosan, shunday
0 ,...0 * *1   m  mavjudki,
      P x o x g xf x f
m
i ii      
 , 1 ** 
tengsizlik bajariladi. Bu yerdan ,
      P x x g x f x f
m
i ii     
 , 1 ** 
munosabatni olamiz. S hundan keyin, 1-teoremaning z a ruriylik q ismdagi kabi
mulo h aza yuriti, (14) munosabatga ega b o ’lamiz.

2) (5) masalada tenglik ko ’ rinishida bog ’ lanishlar qatnashmasin  m k va
Sleyter sharti bajarilsin , ya ’ ni biror
P x uchun   ,0 x gi bo ’ lsin . U va q tda

    ,0 *   xf x f

  m i x g ,1 ,0   .
sistema x P
yechimga ega emas, ammo uning qismi,
  P x m i x gi    ,1 ,0
yechimga egadir. Natijada, 9-§ dagi 2-teoremani qo’llab va yuqoridagi kabi
mulohaza yuriti, teorema isbotiga ega bo’lamiz. 
3-teorema adabiyotda Kun-Takker teoyermasi sifatida ma’lum. Bu tipdagi
dastlabki natija
    S i x g x f i ,1 , , 
, funksiyalardan differensiallanuvchanlik talab
qilingan holda, amarikalik matematiklar G.V. Kun va A.V. Takker tomonidan
olingan.
(5) masalada
    S i x g x f i ,1 , ,  funksiyalardan differensiallanuvchanlik talab
qilingan holda, regulyarlik shartlari quyidagicha bo’ladi:
a )
P – poliedr, barcha   m i x gi ,1 ,  funksiyalar chiziqli;
b)
 ;
c )
P - poliedr,     S i x g x f i ,1 , ,  funksiyalar R da qavariq va shunday Q x~
mavjudki,
  S i x gi ,1 ,0   ;
d )
Г  .
Bu shartlar bajarilgan holda Kun-Takker teoremasi quyidagi ko’rinishni
oladi.
4-teorema. Faraz qilaylik, (5) qavariq programmalashtirish masalasida
    k i x g x f i ,1 . , 
funksiyalar Q x * nuqtada differensiallanuvchi bo’lsin va a  ), b  ),
v  ), g  ) regulyarlik shartlaridan birortasi bajarilsin. U holda
Q x * rejaning optimal
bo’lishi uchun
 * *1 * ,..., m    topili, , ,1 ,0 * k i
i  

   
  


 
   
 
k i x g
P x x
x F x x
ii T
,1 ,0
. ,0 ,
** **
*


(17)

munosabatlarning bajarilishi zarur va yetarlidir.
Isboti. Zaruriyligi. a  ) regulyarlik sharti bajarilganda *x optimal reja uchun
(17) munosabatlarning bajarilishi 14-§ dagi 2-lemmmadan kelib chiqadi.
b  ) va g  ) regulyarlik shartlari mos holda b  ) va g  ) regulyarlik shartlari bilan
ustma-ust tushadi. Shuning uchun, 3-teoremaga ko’ra, (14) munosabatlar
bajariladi. Endi
   * * * , , min   x F x FPx   tenglikka 1-teoremani qo’lla,

    P x x
x F x x T    
  ,0 ,* * * 
munosabatga ega bo’lamiz.
v  ) regulyarlik sharti bajarilgan holda esa, teoremaning isbotini [11] dan qarash
mumkin.
Yetarliligi. 1-teoremaga asosan,
        P x x
x F x x x F x F T    
    ,0 , , , min
* * * * * *   
(18).
teorema isbotining yetarlilik qismi, (18) munosabatni hisobga olgan holda, 2-
teoremadan kelib chiqadi. 
Shunday qili, 4-teoremaning shartlari bajarilganda, (5) masalaning shartli-
stasionar rejasi (ya’ni (17) munosabatlarni qanoatlantiruvchi
Q x * nuqta) uning
optimal rejasi bo’ladi.
2-misol.
 



    
 
0 , ,1
min ,
2112
22
22
1 221
x x x x x x
x x x f
(19)
Bu masalada
2R P  va tengsizlik ko’rinishida uchta bog’lanish mavjud:
      0 ,0 ,0 1 2 1 3 22 1 2 22 21 1           x x x g x x x g x x x g
. Rejalar to’plami Sleyter
shartini qanoatlantiradi (masalan,
 2/1,2/1 x ) nuqtada   3,2,1 ,0 ~   i x gi .
Demak, b) regulyarlik sharti o’rinlidir. Regulyar Lagranj funksiyasini
tuzamiz:

       2 1 3 22 1 2 22 21 1 2 1 , x x x x x x x x F              . 2R P  bo’lgani uchun, (17)
sistema quyidagicha bo’ladi:
,02/
32111 
   xxF
0 2 2 1 / 22 21 2       x x x F   ,

        0 ,0 1 2
222222
22
1111         x x x g x x x g    
,

    0 ,0 ,0 ,0 32121333             x x x g
.
Bu sistemaning
 * *, x yechimlari orasidan
 0 , ,1 :
2112
22
22
12*         x x x x x x R x Q x
, shartni qanoatlantiruvchisini, ya’ni
shartli-stasionar rejani izlaymiz.
 2/2 ,2/2  x - yagona shartli-stasionar reja
bo’ladi (unga
2/1 ,0 ,2 2/1 *3 *2 *1       Lagranj ko’paytuvchilari mos keladi). 4-
teoremaga asosan,
 2/2 ,2/2 *   x - (19) masalaning optimal rejasi bo’ladi.
4.Lagranj funksiyasining egar nuqtasi. (5) masala uchun
        
         m
i im
ii k i R P x x g x f x F
1 ,1 ,0 : , , ,     
Lagranj funksiyasini tuzamiz.
2-t a’ r i f.
     * * * * , , ,   P x x nuqta berilgan bo’lsin. Agar barcha
   ,P x
uchun,
     
****
,,,    xFxFxF 
(20).
tengsizlik bajarilsa,
 * *, x - Lagranj funksiyasining P to’plamdagi egar nuqtasi
deyiladi.
1-lemma.
    P x **,
nuqta (5) masala Lagranj funksiyasining egar
nuqtasi bo’lishi uchun,
   * * * , min ,   x F x F Px 
(21).
  k i x gi i ,1 ,0 * *   
(22).
Q x *
(23).
shartlarning bajarilishi zarur va yetarlidir.

Isboti. Zaruriyligi.
    P x **,
egar nuqta bo’lsin, ya’ni barcha    ,P x
uchun (20) tengsizlik bajarilsin. U vaqtda (21) shart (20) dagi o’ng tengsizlikdan
iborat.
(20) dagi chap tengsizlikni Lagranj funksiyasining ko’rinishini hisobga oli,
quyidagicha yozamiz:
        . ,
1 ***
1 **       
    m
i iim
i ii x g x f x g x f
(24).
Bu yerdan
    
     m
i iii x g
1 ** . ,0   
(25).
(25) dan
Q x * munosabat kelib chiqishini ko’rsatamiz.
 
m   ,...,
1
nuqtaning koordinatalari m ij i k j i i j j ,1 , , , 1,1 * *           
bo’lsin.
  bo’ladi. Olingan  nuqta uchun (25) dan     0 1 *   x g
j
yoki
  k j x gj ,1 ,0 *  
tengsizlikni olamiz.
Endi
  , ,1 , , , 1 , * * * m ij i m j k x g i i j j j             koordinatali   m   ,...,
1
nuqtani olamiz. Tushunarliki,
  . Shu nuqta uchun (25) dan   0 2 *  x gj -, ya’ni
  m k j x gj ,1 ,0 *   
tenglikka ega bo’lamiz. Shunday qili,
  m k i x g P x i ,1 ,0 , * *    
, ya’ni Q x * . (23) munosabat isbotlandi.
Endi (22) ning bajarilishini ko’rsatamiz.
m ij i k j i i i j ,1 , , , ,0 *          ,
koordinatali
 m   ,...1  nuqtani olamiz,   bo’lishi ravshan. Shuning uchun,
(25) dan
  k j x gj j ,1 ,0 * *    kelib chiqadi. Ammo   k j x gj j ,1 ,0 ,0 * *     bo’lgani
uchun,
  k j x gj j ,1 ,0 * *    . Demak,   k i x gi i ,1 ,0 * *    .
Yetarliligi. Biror
    P x **,
nuqta uchun (21), (22), (23) munosabatlar
bajarilsin.
 * *, x - egar nuqta bo’lishini ko’rsatamiz. (21) dan egar nuqta ta’rifidagi

((20) ga q.) o’ng tengsizlik kelib chiqadi. Ta’rifdagi chap tengsizlikning
bajarilishini ko’rsatamiz. (23) shartga ko’ra,    m k i x g k i x g i i ,1 ,0 , ,1 ,0 * *     
.
Bu yerdan ixtiyoriy
  
m   ,...
1
uchun     m
i ii x g
1 * 0 
tengsizlik kelib chiqadi.
(22) shartdan va
  m k i x gi ,1 ,0 *    ekanligidan foydalani,     m
i ii x g
1 * 0 
tenglikni
olamiz.Demak,

                 m
i iim
i ii x g xf x g x f
1 **
1 *** ,   
,
ya’ni (20) dagi chap tengsizlik bajariladi. 
2-lemma. Agar
    P x **,
Lagranj funksiyasining egar nuqtasi bo’lsa, *x
- (5) masalaning optimal rejasi bo’ladi va maqsad funksiyasining optimal qiymati
   * * * , x F xf 
.
Isboti. 1-lemmadan va 2-teoremaning yetarlilik qismidan kelib chiqadi.
2-lemmaga asosan, (5) masalaning optimal rejasini topish uchun Lagranj
funksiyasining
P to’plamdagi egar nuqtasini aniqlash yetarlidir. Ammo har
qanday masala uchun Lagranj funksiyasi egar nuqtaga ega bo’lavermaydi. Birinchi
navbatda, 2-lemmaga ko’ra, agar (5) masala yechimga ega bo’lmasa, Lagranj
funksiyasining egar nuqtasi mavjud emas. Masala yechimga ega bo’lsada, uning
Lagranj funksiyasi egar nuqtaga ega bo’lmasligi mumkin.
4-misol.
    12
,0min, Rxxxgxxf 
.
Bu masalaning rejalar to’plami yagona
0x nuqtadan iborat. Demak, shu 0 * x
nuqta uning optimal rejasidir. Ammo
  0 , ,0 * *    ko’rinishdagi egar nuqta mavjud
emas. Haqiqatan ham, agar shunday
 * * ,0  x egar nuqta mavjud bo’lsa, 1-
lemmaga asosan,
   * * * , min ,   x F x F Px  shart bajarilishi zarur. Ammo

  ,, 2
xxxF   

    0 ,0 , * * *     F x F ,

   



 
      
,0 ,
0 , 4
1
inf , inf
*
* * ** *
1

    x x x F Rx Px

   . , inf , * * *   x F x F Px 
1- lemmadan foydalani, Kun-Takker teoremasini egar nuqta terminida
quyidagicha bayon qilish mumkin.
5-teorema. Faraz qilaylik, (5) masala a), b), v), g) regulyarlik shartlaridan
birortasini qanoatlantirsin. U vaqtda
Q x * rejaning optimal bo’lishi uchun,
shunday
 *
vektor topili,  * *, x juftning Lagranj funksiyasi uchun P
to’plamda egar nuqta bo’lishi zarur va yetarlidir.
Mustaqli yechish uchun mashqlar.
1. 4-teoremaning a  ) regulyarlik shartida
   x g x g 1 1 ,..., botiq funksiyalar
bo’lganda teorema tasdig’ining zaruriy qismi bajarilishini ko’rsating.
2. 4-teoremaning yetarlilik qismida
0 *
i 
bo’lganda   m i k x g i   1 ,
,
funksiyalarni qavariq de,
0 *
i 
bo’lganda esa, bu funksiyalarni botiq deb olish
mumkinligini ko’rsating.
3. Quyidagi masalalarni yeching:
a)
   
; ,1 ,4 5,6 2,1 ,6
min, 4 4 3 10
2 1 2 1 2 1 2 2 2 1
2 2 2 1
         
   
x x x x x x x x x x
x x ;
b)
   
;0 ,0 ,2 3 ,6 ,2 ,2
min, 2 2 25
2 1 2 1 2 2 2 2 2 1
2 2 2 1
         
   
x x x x x x x x x x
x x

Qavariq programmalashtirish masalasi Reja: 1. Qavariq programmalashtirish masalasi . 2. Qavariq programmalashtirishning asosiy masalasi. Sodda xossalar. 3. Optimallikning zaruriy va yetarli shartlari. Kun-Takker teoremasi . 4. Lagranj funksiyasining egar nu q tasi. Asosiy adabiyotlar 1. Р.Габасов, Ф.М.Кириллова. Оптималлаштириш усуллари. Т. Узбекистон, 1995. Qo’shimcha adabiyotlar 2. Васильев Ф.П. Численные методы решения экстремальных задач. М. Наука, 1988. 3. Галеев Е.М., Тихомиров В.М. Краткий курс теории экстремальных задач. М: Изд МГУ. 1989. 4. Карманов В.Г. Математическое программирование. М.Наука.1998. 5. Сухарев А.Г., Тимохов А.Н., Фёдоров В.В. Курс методов оптимизации. М. Наука 1988 6. Исроилов И., Отакулов С. Вариацион хисоб ва оптималлаштириш усуллари. I -кисм. Самарканд. Сам ДУ нашри, 1999, II -кисм Самарканд, СамДУ нашри, 2001

1 Qavariq programmalashtirish masalasi   n R Q Q x x f    , min, (1) berilgan bo’lsin, bu yerda Q- qavariq to’plam,   Q x f  da aniqlangan qavariq funksiya. 1. Optimallik kriteriysi . Qavariq funksiyalarning ekstremumlari haqidagi natijalar asosida , ( I ) masala uchun quyidagi optimallik kriteriysiga ega bo ’ lamiz . I-teorema.  x f funksiya Q x  nuqtada differensiallanuvchi qavariq funksiya bo’lsin. Q x  - (1) masalada optimal bo’lishi uchun   Q x ,0 ) ( * *       x x f x x T (2) munosabatning bajarilishi zarur va yetarlidir. Agar Q x int bo’lsa, (2) munosabat,   0 /    x x f stasionarlik shartiga teng kuchlidir. Agar   n j b x a R x Q j j j n ...,2,1 , :       n j b a j j .1 ,      bo’lsa, (2) munosabat quyidagiga ekvivalent:                       ..1 , , ,0 , ,0 , ,0 n j b x агар a x агар b x a агар x xf jj jj jjj j (3) 1-misol.   .0 ,0 min, 2 4 2 5 2 3 1 3 3 2 2 1 23 22 21          x x x x x x x x x x x f (4) Bu masalada   3R x f  da qavariq funksiya,  . 0 , 0 : 3 0 1 3     x x R x Q Optimallik kriteriysidan foydalanib ((3) munosabatga qarang), ,0 2 2 2 1 1      x x x f   ,0 2 2 2 1 1   x x x ,0 4 2 4 3 1 2 2       x x x x f ,0 2 4 10 2 3 3       x x x f   .0 2 4 10 233    x x x sistemani tuzamiz. Bu sistemani yechi, yagona  3/1,3/1,0   x nuqtani topamiz. Demak,    4 3/1,3/1,0  x masalaning yagona yechimidir.

2. Qavariq programmalashtirishning asosiy masalasi. Sodda xossalar.nR P  - qavariq tuplam,     P S i x g x f i   ,1 , , da qavariq funksiyalar,   , ,1 , m S i b x a x g Ti i     - chiziqli funksiyalar bo’lsin  . ,1 , , 10 m S i R b R a i n i           ,0 , ,1 ,0 , ,1 ,0 :             i Ti i i Ti i i n b x a x g k S i b x a x g S i x g R x Q  P x m k i    , ,1 to’plamni qaraymiz. Qavariq to’plam va qavariq funksiyalarning xossalariga asosan, Q qavariq to’plamdir. Bu holda , (1) masala       , ,1 ,0 , ,1 0 min, k S i b x a x g S i x g x f i Ti i i            . , ,1 ,0 P x m k i b x a x g i Ti i       (5) ko’rinishda yoziladi va u qavariq programmalashtirishning asosiy masalasi deb ataladi. (5) masalaning qavariq funksiyalarning ekstremal xossalaridan kelib chiquvchi quyidagi sodda, ammo muhim xossalarini sanab o’tamiz: a) (5) masalaning lokal optimal rejasi uning global optimal rejasi ham bo’ladi; b) (5) masalaning optimal rejalar to’plami qavariqdir; v) agar  x f - qatiy qavariq funksiya bo’lsa, (5) masalaning optimal rejasi yagonadir; g)  x f - uzluksiz kuchli qavariq funksiya,   P S i x gi   , ,1 , da uzluksiz qavariq funksiyalar bo’lsa, (5) masalaning yagona optimal rejasi mavjud. 3. Optimallikning zaruriy va yetarli shartlari. Kun-Takker teoremasi. (5) ko’rinishdagi qavariq programmalashtirish asosiy masalasi uchun optimallikning zaruriy va yetarli shartlarini bayon qilamiz. (5) masala uchun         m i ii x g x f x F 10 , ~, ~     m    ,...., , ~ 1 0  umumlashgan Lagranj funksiyasi va             m i mii x g x f x F 1 1 ,...., , ,      regulyar Lagranj funksiyasidan foydalanamiz.

2-teorema. Q x  nuqtaning (5) masalada optimal bo’lishi uchun shunday   0 ,..., , ~ 1 0       m    topili, k i i ,1 ,0 ,0 0           , ~, ~ min ~, ~ *  x F x F Px    (6)   . ,1 ,0 * * k i x gi i    (7) shartlarning bajarilishi zarur, 1 *0 bo’lganda esa, yetarli ќ amdir. Isboti. Zaruriyligi: Quyidagi sistemani qaraymiz:                      . ,1 ,0 ,1 ,0 ,0 m k i x g k i x g x f x f i i (8) Bu sistema P x yechimga ega emas. Chunki, agar u biror P x yechimga ega desak, *x ning optimalligiga zid bo’lgan,     Q x xf x f   ,* munosabatga ega bo’lamiz (bu yerda Q (5) masalaning rejalar to’plami). (8) sistemaga Fan teoremasini qo’llaymiz (9-§). Shu teoremaga asosan, bir vaqtda nolga teng bo’lmagan shunday , ,1 ,0 ,0 * *0 k i i      * *1 ,..., m k    sonlar mavjudki,               m i ii P x x g xf x f 1 *** 0 ,0   tengsizlik bajariladi. Bu yerdan            m i ii P x x g x f xf 1 ** 0** 0 . ,    (9) tengsizlikni olamiz. (9) da * x x deb olsak,   0 1 **  m i ii x g  bo’ladi. Ikkinchi tomondan,     m k i x g k i x g o i i i ,1 ,0 , ,1 ,0 , * * *        bo’lgani uchun,     m i i i x g 1 * * 0  (11) tengsizlik bajariladi. (10), (11) munosabatlardan,     m i ii x g 1 ** 0  (12)

tenglik kelib chiqadi. Lagranj funksiyasining ko’rinishini va (12) ni hisobga oli, (9) dan quyidagi tengsizlikni olamiz:              . , ~, ~ ~, ~ * 1 1 ** 0** 0**** 0** P x x F x g x f xf x g xf x F m i m i iiii                    . Demak, (6) tenglik isbotlandi. (12) dan (7) tengliklar kelib chiqadi. Haqiqatan ham,   k i x gi i ,1 ,0 * *    bo’lganligidan, agar biror K i i   * * 1, uchun   0 ** x g ii  desak,     m i ii x g 1 ** 0  ya’ni (12) ga zid munosabatga ega bo’lamiz. Yetarliligi. 1 *0 bo’lsin. U vaqtda (6) munosabat regulyar Lagranj funksiyasi yordamida     P x x F x F    , , , * * *   (13) ko’rinishi oladi. Endi (7) va (13) dan foydalani, ixtiyoriy Q x uchun quyidagiga ega bo’lamiz:                 *** 1 **** , ,    x F x F x g xf xf m i ii          m i i i x f x g x f 1 * .  Demak,     Q x x f xf    , * , ya’ni *x -(5) masalaning optimal rejasidir.  1-t a’ r i f. Agar (5) masalaning *x - optimal rejasida bajarilishi zarur bo’lgan (6) shartda 0 *0  bo’lsa, qavariq programmalashtirish asosiy masalasi regulyar deyiladi. Regulyar masalada 1 *0 deb olish mumkin. (5) masalaning rejalar to’plami Q uchun quyidagi shartlarni qaraymiz: a) P -poliedr,  x f va barcha   m i x gi ,1 ,  , funksiyalar chiziqli; b) m k (ya’ni tenglik ko’rinishdagi cheklashlar yo’q) va shunday P x~ nuqta mavjudki,   m i x gi ,1 ,0 ~   (Sleyter sharti); v) P -poliedr, W W P ,  - nisbiy ochiq qavariq to’plam,  x f W riW ,  ,   , ,1 , S i x gi  funksiyalar W da qavariq va shunday Q x~ topiladiki,   S i x gi ,1 ,0 ~   ;

O'xshashlar

Chiziqli programmalashtirish masalasi

Qavariq funksiyalar va ularning xossalari. Funksiyalarning qavariqlik kriteriyalari. Qavariq funksiyalarning ekstremumlari.

Sun’iy bazis vektor usuli va chiziqli programmalash masalalarini sonli yechishga qo’llash.

RYUKZAK MASALASI

Chekli o’lchovli ekstremal masalalarning umumiy qo’yilishi, xossalari va sinflari. Ekstremal masala yechimining mavjudligi.