Matematik programmalashtirishning hisoblash usullari

Загружено в:

08.08.2023

Скачано:

0

Размер:

257.7294921875 KB

Скачать

Matematik programmalashtirishning hisoblash usullari
Reja:
1. Bir o’lchovli funksiyani minimallashtirish usullari:
a) Oltin kesim usuli.
b) Urinmalar usuli.
2. Shartsiz minumum masalasi uchun gradiyentli usullar:
a) Gradiyentli eng tez tushish usuli.
b) Gradiyentli tushish usuli.
c) Iterasiya qadamini bo’lib borish usuli.
Asosiy adabiyotlar
1. Р.Габасов, Ф.М.Кириллова. Оптималлаштириш усуллари. Т. Узбекистон,
1995.
Qo’shimcha adabiyotlar
2. Васильев Ф.П. Численные методы решения экстремальных задач. М.
Наука, 1988.
3. Галеев Е.М., Тихомиров В.М. Краткий курс теории экстремальных задач.
М: Изд МГУ. 1989.
4. Карманов В.Г. Математическое программирование. М.Наука.1998.
5. Сухарев А.Г., Тимохов А.Н., Фёдоров В.В. Курс методов оптимизации.
М. Наука 1988
6. Исроилов И., Отакулов С. Вариацион хисоб ва оптималлаштириш
усуллари. I -кисм. Самарканд. Сам ДУ нашри, 1999, II -кисм Самарканд,
СамДУ нашри, 2001

I.Oltin kesim usuli .
Bu usul unimodal funksiyalar uchun qo’llaniladi.
3-ta’rif. Agar shunday ] , [ ba x
 nuqta mavjud bo’lsaki, f(x) funksiya 0
x
nuqtadan chapda kamayuvchi (ya’ni x
1 ,x
2 
[a,b],
) ( ) ( 2 1 2 1 x f x f x x x     ), o’ngda
esa o’suvchi (ya’ni x
1 ,x
2 
[a,b],
) ( ) ( 2 1 2 1 x f x f x x x    
 ), bo’lsa, bu funksiya
[a,b] kesmada unimodal deyiladi (I-chizma ).
Unimodal funksiya quyidagi xossalarga ega.

.10 Agar ) (x f funksiya ] , [ b а kecmada unimodal bo’lca, u ixtiyoriy
],[],[ badc 
kecmada ham unimodal bo’ladi.
2 0
. Agar
) (x f funksiya b] [a, kecmada uzlukciz va unimodal bo’lca, u
yagona lokal minimumga ega. Boshqacha aytganda, bunday funksiyalar
uchun lokal minimum global minimum ham bo’ladi.
3 0
.
b y x a b a y x      ], , [ , nuqtalar bo’yicha unimodal ) (x f funksiyaning
] , [ b а
, kecmadagi minimum nuqtacini lokallashtirish mumkin: agar ) (x f  ) (y f
bo’lca, lokallashtirish kecmaci -
] , [ y a , ) (x f  ) (y f bo’lganda eca lokallashtirish
kecmaci -
] , [ bx bo’ladi.
4-ta’rif. Agar kesmani shund a y ikkita teng bo’lmagan bo’laklarga bo’lish
mumkin bo’lsaki, kesma uzunligining uning katta qismi uzunligiga nisbati,
katta qism uzunligining kichik qism uzunligining nisbatiga teng bo’lsa, bu
bo’linish kesmaning oltin kecimi deb ataladi.
Quyidagi, ,),(),(2
yxabrayabrax 
nuqtalar
] , [ b a kecmada
oltin kecim hosil qiladilar (bu yerda
  , 618034,0 2/1 5   r   381966,0 2/ 5 3 2    r ).
Ta’rifga acocan,

y b
a y
a y
a b
a x
x b
x b
a b

  
  
  


$Kesmaning “oltin kecimi” quyidagi xossalarga ega. 1 0 . ] , [ b a kesmada oltin kesim hosil qiluvchi yx , nuqtalar kesmaning o’rtasiga nisbatan simmetrik joylashgan: . , , x b a y x b a y y b s x          2 0 . y x, nuqtalar ] , [ b a kesmada oltin kesim hosil qilsin. U holda; y x x y a y r a x      , ), (2 nuqtalr ],[],[ yaba  kesmada oltin kesim hosil qiladi. Lokallashtirish jarayoni (algoritmi) ) (x f - ] , [ b a kecmada uzlukciz unimodal funksiya bo’lsin. Oltin kesimning va unimodal funksiyalarning xossalaridan foydalanib, (1) masala ye chimini lokallashtirish quyidagicha bajariladi: 1)  0 0 2 0 0 0 0 , , a b r a x b b a a      deb, ) ( 0x f va )( 0yf larni hicoblaymiz; 1k deb, navbatdagi bandga o’tamiz. 2) agar ) ( 1kx f  ) ( 1ky f bo’lsa, 3-bandga, aks holda esa, 4-bandga o’tamiz. 3) 11 ,    kkkk y b a a deb olamiz. Agar   kk ab bo’lsa, hisoblash to’xtatiladi: 1kx nuqta taqribiy yechim deb olinadi; aks holda 1 , ), ( 1 2        k k x y a b r a x k k k k k k deb, 2-bandga qaytamiz. 4) 1 1,     k k k k b b x a deb olamiz. Agar   k k a f bo’lsa, hisoblash to’xtatiladi: 1ky nuqta taqribiy yechim deb olinadi: aks holda 1  k k y x , 1 ), ( _    k k a br x kkk deb, 2-bandga qaytamiz. E slatma. 1. n ta ( n 1) iteras i ya (qadam ) bajarilgandan so’ng hosil bo’lgan lokalashtirish kesmasi ] , [ n nb а ning uzunligi ) ( a b r a b n n n    bo’ladi. Bunda taqribiy yechim *nx ning aniq yechim nx dan chetlanishi (xato ) quyidagichadir: ) ( ) ( } , max{ 1 * * * a b r a br a x x b x x n n n n n n n n n         $

2. Har bir iteras i yadan so’ng kx va ky
larning faqat bittasining
o’zgarganligi t ufayli algoritmning 2-bandini bajarganda
) (x f ning faqat bitta
qiymati hisoblanca, yetarli.

2 1 ~ x x x 2 1 ~ x x x
a) Qavariq unimodal funsiya b) Qavariqmas unimodal funsiya
I-chizma.
1-misol. xxxf  2
)(
funksiyaning [0,2] kesmadagi minimum nuqtasini
2,0
aniqlik bilan lokallashtiring.
Yechilishi. Algoritmning 1-bandini bajaramiz:
2 ,0 0 0   b a ,
    , 764,0 5 3 2
5 3
000002
00           a b a a b r a x
    , 236,1 1 5 2
5 1
0000000            a b a a br a y
. 292,0 ) ( , 180,0 ) ( 0 0   y f x f
A lg o ritmning 2- band ig a o’t a miz. (1-it e r a siya)
) ( 0x f
< ) ( 0y f bo’lg a ni uchun, ,0
01  aa
. 236,1 0 1   y b    236,1 1 1 a b bo’lg a ni
uchun, ikkinchi it e r a siyag a o’t a miz.

  ,472,0
11112
11  baabrax
, 764,0 0 1   x y ) ( 249,0 ) ( 1 1 y f x f   .
D e m a k,
, 764,0 ,0 1 2 1 2     y b a a    764,0 2 2 a b . Uchinchi it e r a siyag a
o’t a miz.
  ;472,0,0298,0
22122222
22  xyxbaabrax

) ( 207,0 ) ( 2 2 y f x f  . D e m a k, . 472,0 , 764,0 , 292,0 332323       a b b b x a
Yan a
ikkit a it e r a siya b a j a rib, t a l a b qiling a n l o k a l a shtirish k es m as i
] 584,0; 403,0[ ] , [
55  b a
g a ega bo’l a miz.     181,0 55 a b
A
0 X
0 U
0 V
0
0 0,764 1,236 2
A
0 X
1 U
1 V
1
0 0,472 0,764 1,236 2
A
0 X
2 U
2 V
2
0 0,292 0,472 0,764 2
A
3 X
3 U
3 V
3
0 0,292 0,472 0,584 0,0,764 2
A
4 X
4 U
4 V
4
0 0,292 … … 0,584 2
A
4 V
4
0 0,403 0,584 2
2 chizma.

472,0 , 403,0 4 4   y x nuqtalar ] 584,0; 292,0[ ] , [ 4 4  b a kesmada oltin kesim hosil
qiladi hamda
, 241,0 ) ( 4  x f , 249 ) ( 4  y f ) ( 4x f > ) ( 4y f .
Demak,
472,0 4 y ni berilgan 2,0 aniqlikdagi taqribiy yechim deb olamiz.
1. Urinmalar usuli.
Bu usul qavariq funksiyalar uchun qo’llaniladi.
Taqribiy yechimlar to’plami. Qavariq
) (x f funksiyaning [a:b] kesmadagi
minumum nuqtasiga yaqinlashuvchi
n n b a x n ,...,2,1 ,] : [  
nuqtalar ketma-ketligini
qaraymiz. Shu maqsadda ,,),)(()(),( /
byfbxfycyfyfyxL 

funksiyadan foydalanamiz. x y x L ) , ( Har bir ] , [ b a y uchun x ning chiziqli
funksiyasi bo’lib, uninng grafigi
) (x f funksiya grafigiga ))(,( yfy
nuqtada
o’tgazilgan urinmadan iborat. Ixtiyoriy
] , [ 0 b a x  nuqtani boshlang’ich
yaqinlashishi deb ataymiz. Faraz qilaylik,
) , ( 0 b a x  bo’lganda a x x f   0 0 / :0 ) (
bo’lganda
b x x f   0 0 / :0 ) ( bo’lganda 0 ) ( 0 /  x f bo’lsin (aks holda qavariq
funksiyaning xossalariga asosan, x
0 nuqta (1) masalaning yechimi bo’ladi va { x
n }
ketma-ketlikni qurish jarayoni tugaydi.)
n n b a x n ,...,2,1 ,] : [  
nuqtalarni
) ( min ) ( 1 1 x P x P n bxa n n    
, ) , ( max ) ( ....2.1 1 i i n n x x L x P    shartdan aniqlaymiz (3-chizmada R
0 (x)
funksiyaning grafigi AE to’g’ri chiziqdan, R
1 (x) funksiyaning grafigi esa, AMND
siniq chiziqdan iborat.)
Teorema. Faraz qilaylik,
] , [ ) ( b a x f  kesmada uzliksiz differensiallanuvchi
qavariq funksiya bo’lsin va urinmalar usuli bo’yicha qurilgan
, ,...., , 1 0 nx x x ketma-
ketlikda
0 ) (/  x f shart bajarilsin . U vaqtda:
1)
) ( ) ( ) ( inf lim lim 1 x f x P x f
bxa n n n n n    
  ;
2) {x
n } ketma-ketlik limitik nuqtalari
ikkitadan ko’p bo’lmaydi va bu
limitik nuqtalar yoki x *
=infG
*, yoki
y *
=supG
* bilan ustma - ust tushadi, bu
yerda G
* -f(x) funksiyaning [a,b]
kesmadagi minumum nuqtalari
to’plami;
Agar G
* yagona x *
nuqtadan iborat bo’lsa,
n n n x x  lim bo’ladi.
Algoritm. Bayon qilingan urunmalar usuli bo’yicha (1) mfsalani
 aniqlikda
taqribiy yechish uchun bajariladigan ishlarni amaliyot nuqtai nazaridan qulay
bo’lgan quydagi sxemaga solish mumkin. f
xb=x
1x
2 x
3a x
0A
M N
E

1. a
1 =a, b
1 =b deb olib, ) (' ), (' 1 1 b f a f qiymatlarni hisoblaymiz. Agar
0)(
1/
af
( yoki
0 ) (1 /  b f ) bo’lsa, yechish jarayoni tugaydi: )*(* bxx 
(I)
masalaning yechimi bo’ladi. Agar 0)(
1/
af
, 0)(
1/
bf
bo’lsa,
) (1a f va + ) (1b f
qiymatlarni ham hisoblab hamda k=1 deb, 2-punktga o’tamiz
2. Agar
  k k a b bo’lsa, yechish prosessi tugaydi: taqribiy yechim *kx
ni
)} ( ), ( min{ *) ( k k k b f a f x f  shartdan aniqlaymiz. Agar   k k a b bo’lsa,
) (' ) ('
)] ( ) ( [ ) ( ) ('
kk kkkkkk
k
a f b f
a f b f a a f b b f x 
   
(2)
nuqtani aniqlab, f ( x
k ) va f ’( x
k ) qiymatlarni hisoblaymiz.
3. Agar f ’( x
k )=0 bo’lsa, yechish jarayoni tugaydi: x
k nuqta (1) masalaning
yechimi bo’ladi . Agar f ’( x
k ),<0 bo’lsa, a
k +1 = x
k , b
k +1 = b
k deb, f ’( x
k ),>0 bo’lganda
esa, a
k +1 =a
k , b
k +1 =x
k deb olamiz.
4. k ni k+1 bilan almashtirib , algaritmning 2 – punktga qaytamiz.
Izoh (2) fortula bilan aniqlanachi x
k nuqta
) )( ( ) ( ) , ( ) )( ( ) ( ) , ( / /
k k k k k k k k в x в f в f в x L ва a x a f a f a x L      
u
rinmalarning kesishish nuqtasini aniqlaydi.
2-Misol
]2,0[ min, 3 3 ) ( 3      x x x x f
masalani 3,0  aniqligida yeching.
Yechilishi f(x)=x 3
-3x+3 funksiya [0,=+
 ) da uzluksiz diffrensiyallanuvchi
qavariq funksiyadir.
Algaritm I-punktini bajaramiz: a
1 =a=0, b
1 =b=0, f /
(x)=3x 2
-3,f /
(a
1 )=f /
(0)=-3, f
/
(b
1 )=f /
(2)=9, f(a
1 )=3, f /
(b
1 )=5.
k=1 uchun algoritmning 2-punktini bajaradi:
(1) formulaga asosan :

.3
7 )3
4( ) ( , 2
37 )3
4( ) (
;3
4
)3 ( 9
3 5 2*9
) ( ) (
)] ( ) ( [ ) ( ) (
/ 1 / 1
1 / 1 / 1 1 1 1 / 1 1 /
1
   
  
   
   
f x f f x f
a f b f
a f b f a a f b b f x

Algaritmni 3-punktini bajaramiz. f /
( x
1 )>0 bo’lgani uchun, a
2 = a
1, b
2 = x
1 deb olamiz.
k=2 deb, algoritmni 2-punktiga qaytamiz. b
2 -a
2 =x
1 -a
1 =4/3>E (2)-formula
bo’yicha.0 029.0 ) ( , 036.1 ) (
889,0
3 3
7
3 27
37
3
4
3
7
) ( ) (
)] ( ) ( [ ) ( ) (
2 / 2
2 / 2 / 2 2 2 2 / 2 2 /
2
  


  
 
   
x f x f
a f b f
a f b f a a f b b f x
,
bo’lgani uchun, a
3 =x
2 ; b
3 =b
2 deb olamiz , b
3 –a
3 =0,444>
 . (2) formulaga ko’ra,
3x
nuqtani topamiz:
126.1
623.0 3
4
036.1 27
37 899.0 823.0 3
4
3
4
) ( ) (
)] ( ) ( [ ) ( ) (
33 333333
3 

    
   
      a f b f
a f b f a a f b b f x
0 804.0 ) ( , 050.1 ) ( 3 3     x f x f
bo’lgani uchun, 126.1,899.0
3434  bbaa
bo’ladi.
   237.0 4 4 a b . Talab qilingan aniklikka erishildi.
)}(),(min{)(,050.1)()(,036.1)()(
4443424 bfafafxfbfxfaf 
. Demak,
3.0 
anikligidagi taqribiy yechim
889.0 2 4   x a bo’ladi.
2.Shartsiz minimum masalasi uchun gradiyentli usullar
Shartsiz minumum masalasi
n
Rxxf  min,)(
(1)
uchun taqribiy yechish usullaridan gradiyentli usullarni qaraymiz.
Gradiyentli usullarda
,...,2,1,0 ,) ( 1  
    k x
x f x x
k
k k k 
(2)
formula bo’yicha
kx ketma-ketlik quriladi, bu yerda 0x - boshlang’ich nuqta,
,...,2,1,0,  kconst
k

.
(2) formula yordamida
kx nuqtadan 1kx nuqtaga o’tishga iterasiya deyiladi.
x x f k k   /) ( 
ga iterasiya yo’nalishi k ga esa iterasiya qadami deyiladi.

Har bir iterasiyada 0 /) (    x x f k
shart tekshirilib turiladi. Agar 0 /) (    x x f k
bo’lib qolsa, (2) prosess tugaydi:
) (x f xk
funksiya stasionar nuqtasi bo’ladi. Bu holda kx nuqta atrofida
qo’shimcha tekshirishlar o’tgazilib
) (x f funksiya x k
nuqtada minumumga
erishadimi, yo’qmi aniqlab olinadi.
Masalan, agar
)2( ) ( C x f  bo’lsa, optimallikni ikkinchi tartibli zaruriy sharti va
yetarli shartidan foydalanish mumkin; agar f(x)- qavariq funksiya bo’lsa, x k
stasionar nuqta (I) masala yechimi bo’ladi.
Umumiy holda (2) iterasion jarayon cheksizdir. Bu holda , f(x) funksiyaga
ma’lum shartlar qo’yilganda, (2) formula bo’yicha qurilgan {x k
} ketma-ketlik
minimallashtiruvchi (yani
) ( inf ) ( lim x f x f n Rx
k
k   
) bo’ladi va bu ketma-ketlik (yoki
uning qismiy ketmaketligi) (1) masala yechimiga yaqinlashadi.
Amaliyotda iterasiyalar ma’lum bir kriteriy bajarilguncha davom ettiriladi.
Shunday kriteriy sifatida,
3 2 1 1 1
)(
,)()(,    

  
x xf
xfxfxx k k k k k
shartlardan birortasi yoki ularning barchasi bir vaqtda bajarilishini talab qilish
mumkin, bu yerda
3,2,1 ,0   i i – berilgan son bo’lib, taqribiy yechim aniqligini
xarakrterlaydi.
(2) formulada iterasiya qadami
k ni tanlashning xar xil usullari mavjud.
Shulardan ba’zilarini qaraymiz.
I. Gradiyentli eng tez tuzish usuli.
Agar (2) formulada iterasiya qadami
k ni







     x
x f x f g g g
k k k k k k
) ( ) ( ), ( min ) ( 0     
(3)
shartdan aniqlasak, gradiyetli eng tez tushush usuliga ega bo’lamiz.

1-Teorema. Faraz qilaylik,    ) ( inf, ) ( )1( x f C x f n Rx
bo’lsin va x x f   /) (
gradiyent Lipshits shartini qanoatlantirsin:
; , , , ) ( ) (
n R y x const L y x L x
y f
x
x f     
 


nR x 0 - ixtiyoriy boshlang’ich nuqta,  kx ketma-ketlik (2), (3) formulalar
bo’yicha qurilgan bo’lsin. U holda,
0 ) ( lim  

 x
x f k
k . Agar bundan tashqari, ) (x f
funksiya qavariq va
 ) ( ) ( | ) ( 00 x f x f R x x M n   
to’plam chegaralangan bo’lsa,
 kx
-minimallashtiruvchi ketma-ketlik bo’ladi va uning ixtiyoriy limitik nuqtasi (1)
masalaning yechimidan iborat. Minimum nuqtasi yagona bo’lganda esa,
 kx
ketma-ketlik unga yaqinlashadi.
Gradiyentli eng tez tushish usulini qo’llab (1) masalani taqribiy yechish
quyidagi algoritm bo’yicha bajarilishi mumkin:
a) boshlang’ich
0x nuqta olib, x
x f

 ) ( 0 gradiyentni hisoblaymiz. Agar
0 ) ( 0
 

x
x f
bo’lsa,
0x - stasionar nuqta bo’ladi va iterasiya jarayoni tugaydi: aks
holda
0k deb, b) bandga o’tiladi.
b) skalyar
0  argumentli x
x f x f g
k k k 
   ) ( ( ) (   funksiyani tuzamiz va
0 min, ) (    
k g
masalaning k yechimini topamiz.
v)
x
x f x x
k
k k k

    ) ( 1  nuqtani aniqlaymiz va x
x f k

 ) ( 1 ni hisoblaymiz. Agar
x
x f k

 ) ( 1
=0 bo’lsa,
1kx - stasionar nuqta bo’ladi va iterasiya jarayoni tugaydi; aks
holda navbatdagi bandga o’tamiz.
g)








    
x
x f x f x f x x
k k k k k ) ( ,) ( ) ( , max 1 1 (4)

shartni tekshiramiz. Agar (4) shart bajarilsa, (1) masalani yechish jarayoni tugaydi: 1kx
aniqlikdagi taqribiy yechim bo’ladi. Agar (4) shart bajarilmasa, 1 k k
deb, b) bandga o’tiladi.
1-misol. 2
212
22
1 min,742)( Rxxxxxxf 
, boshlang’ich nuqta





 10
5 0x
bo’lsin.
0
16
8
4 2
2 2 ) ( ,
4 2
2 2 ) (
105 2
1 0
2
1
21
 




  





















 xx x
x
x
x f
x
x
x
x f
Iterasiya qadami 0

ni aniqlaymiz.







 




 




 
  
   16 10
8 5
16
8
10
5 ) ( 2 0
x
x f x
82 320 320 7 ) 16 10(4 ) 8 5(2 ) 16 10( ) 8 5( )) ( ( ) ( 2 2 2 2 0 0             
           x
x f x f g
0

qadam 0 min, 82 320 320 ) ( 2 0          g masalaning yechimidan iboratdir.
0640)(,
21
0320640)(
10 10      gg
. Demak , 2
1   . (2) formulaga asosan
x 1
nuqtani hisoblaymiz:





  






 







 




 




 

  
 0
0
4 2
2 2 ) (
2
1
16
8
2
1
10
5 ) (
21 2
1 2
2
0 0 1
21xx x
x
x
x f
x
x f x x 
Shunday qilib,





 2
1 1x - f(x) funksiyaning stasionar nuqtasidir. Iterasiyalar tugadi.
7 4 2 ) ( 2 1 22 21      x x x x x f
funksiya qavariq bo’lgani uchun, 




 2
1 1x nuqta
berilgan masalaning yechimidan iborat.
2-misol.





      1
2 ; min, 2 2 ) ( 0 2 1 22 21 x R x x x x x f – boshlang’ich nuqta bo’lsin.

0 4
2 ) ( , 4
2 2 ) ( 0
2
1 




 






   

x
x f
x
x
x
x f
Algoritmning b), v) bandlariga asoslanib, 1- iterasiyani bajaramiz( k=0 ).








 




 




 
  
   4 1
2 2
4
2
1
2 ) ( 0 0
x
x f x
0
9 498
4 22
)( ,
91913
42
18 5
1 2
)( 18 5
072)( 18 5
02072)( ,0min,22036)( ,22036)22(2)41(2)22())(
()(
91913
211 0
01 0
00 2
0 2220
0
0
2 1 








 

 















 



   


 
x x
xx
x xf x xf
xxggg x xf
xfg



  
   
      
Taqribiy yechimi
5,0  aniqlik bilan izlaylik.

     9
25 ) ( ) ( ,2 ) ( ,9
7 ) ( 2121 x f x f x f x f
2- iterasiyani bajaramiz (ya’ni algoritmning b), v)punktlarning k=1 uchun
takrorlaymiz):
 
 
 
















    




















 



 













27 227 29
9 498
12 5
91913
)( ,
12 5
0
81192
)( 12 5
080192
81 1
)( ,0min,638096
81 1
)( ,638096
81 1
98
913
2
9 4
91
2
98
913)(
)( ,
9 4
91 98
913
9 498
91913
)(
1
12 111 2
1 222
1
1
2 2
1
x xf
xxggg x xf
xfg x xf
x

 
  
   
      


 

(4) shartni tekshiramiz:
5,0
27 55)(
,)()(,max ,
27 55
27 5
27 10
,
27 5 2710 ,
27 54)()()(
,
27 827 4
)( 243 50
)()( ,
243239
)(
122
1212 22
1212 2
2 22
1 222 122




 








 






 


















  
xx
x xf
xfxfxx xxxx x xf
x xf
x xf
x xf xfxf xf
Demak, talab qilingan aniqlikga erishildi.
5,0  aniqlikdagi taqribiy yechim

 
 
 27
2, 27
29 2 x x
bo’ladi.
2.Gradiyentli tushish usuli .
Faraz qilaylik, (2) formulada ,...2,1,0,  kconst
k
 
bo’lsin:
,...2,1,0 ,) ( 1  
    k x
x f x x
k k k 
(5)
Taqribiy yechimni (5) formula bo’yicha quruvchi usulga gradiyentli tushish usuli
deyiladi. Bu usul bo’yicha har bir iterasiyada
x
x f k
k 
 ) (  yo’nalishda o’zgarmas

qadam qo’yiladi.
2-teorema. Faraz qilaylik,
nR x x f  ), ( , funksiya 1-teoremaning shartlarini
qanoatlantirsin. U holda ixtiyoriy
nR x bolang’ich nuqta va
 
10,10
   
L
,, shartni qanoatlantiruvchi
0  uchun qurilgan (5) ketma-
ketlikda 1- teoremaning barcha tasdiqlari o’z kuchini saqlaydi, bu yerda
0 ) (  
 x
x f L
gradiyent uchun Lipshits o’zgarmasidir.

Shunday qilib, x
x f

 ) ( gradiyent uchun Lipshits o’zgarmasi L ma’lum
bo’lganda, taqribiy yechimlarning ketma-ketligini qurish algoritmi soddadir: biror
1 0,   
uchun
 
L
    1 ni hisoblab, (5) formula yordamida
 kx ketma-ketlik
quramiz;
0 ) (  

x
x f k bo’lsa yoki talab qilingan
 aniqlikga erishilsa, iterasiyalar
prosessi to’xtatiladi.
3-misol.
2 2 2 2 1 min, )2 (2 )1 ( ) ( R x x x x f      
y x y x y x x
y f
x
x f
x
x
x
x f       
 








  
 4 ) ( 16 ) (4 ) ( ) ( , 8 4
2 2 ) ( 2 2 2 21 1 2
1
Demak,
x
x f

 ) ( uchun Lipshis o’zgarmasa L=4. (5) formula iterasiya qadami
8
1
4
)2
1 1( ) 1( 

   L
 
deb olamiz ( 2
1   deb oldik). Boshlang’ich nuqta





 4
2 0x
bo’lsin. Iterasiyalar bajaramiz:
1-iterasiya ;
347
8 2
81
42
)(
,
8 2
)( 0
010























x xf
xx
x xf


2-iterasiya
;
2
5
16
25
4
2
3
8
1
3
4
7 ) ( ,
4
2
3 ) ( 1
121


























 
   







 

x
x f x x x
x f 
3-iterasiya
;
4
9
64
91
2
8
9
8
1
2
5
16
25
) ( ,
2
8
9 ) ( 2
232





























 
   







 

x
x f x x x
x f 
4-iterasiya
;
8
17
256
337
1
32
27
8
1
4
9
64
91
) ( ,
1
32
27 ) ( 3
343





























 
   







 

x
x f x x x
x f 
Shunday davom yetib, ,..., 21
xx
ketma-ketlikni qurish mumkin:

...,, 65536
8609 ) ( , 4096
1241 ) ( , 256
209 ) ( , 16
41 ) ( 4322     x f x f x f x f

ya’ni ...)()()()( 4321
 xfxfxfxf
Agar )2,0 ( ) ( ) ( 1       k k x f x f
kriteriydan foydalansak, iterasiyalarni
4x ni hisoblash bilan to’xtashish mumkin,
chunki

2,0 65536
11243 ) ( ) ( 34    x f x f
.
3. Iterasiya qadamini bo’lib borish
Gradiyentli metodlarning praktikada kup kullanadigan yana bir varianti
interasiya qadamini keyingi interasialarida bo’lib (kichraytirib) borishga
asoslangan bo’lib , quyidagi algoritm bo’yicha amalga oshiriladi:
a) xєЄRⁿ - boshlang’ich nuqta olib
 ѓ(xє)/∂x ni hisoblaymiz .  ѓ(xє)/∂x ═ 0
bo’lsa, xє - stasionar nuqta bo’ladi va yechish jarayoni tugaydi. Aks xolda k ═ 0,
α═ά ( ά – biror musbat son) deb b) band ga o’tamiz.
b) x
     к л лк х х  1 /∂x nuqtani xisoblaymiz.
v) agar ∂ѓ(
1кх )/∂x═0 bo’lsa, iterasiya prrosessi tugaydi: 1кх - stasionar nuqta
bo’ladi.
g) agar ѓ(x 1к
)<ѓ(x
к ) bo’lsa, d) punktga o’tamiz.
Aks xolda iterasiya qadamini bo’lib (ya’ni α═άγ, 0<γ<1 deb) b) punktga qaytamiz
(ya’ni
1кх ni kichraytirilgan α qadam bilan qayta hisoblaymiz).
d) interasiyalarni to’xtatish kriteriyasi (masalan, (4) shar t ni) tekshiramiz. Shu
kriteriy bajarilganda intersiya prosessi to’xtatiladi. Aks xolda k═k+1 deb b)
punktga qaytamiz (ya’ni, yangi iterasiyaga o’tiladi).
Eslatmalar. 1) Iterasiya qadami α ning dastlabki qiymati ά sifatida
g(α)═ƒ(xє α
 



 k f )→min, α ≥0 masalaning yechimini olish mumkin.
2) Praktikada ko’pincha algoritmning g) puntida γ═
2
1 deb olinadi.
3) Yuqorida keltirilgan sxema bo’yicha {x
к } ketma-ketlik qurilganda ∂ѓ(x к
)/∂x→0,k→∞, shart bajarilmasligi va demak, {x
к } ketma-ketlik minimum

nuqtasiga yaqinlashmasligi mumkin. Shuning uchun iterasiya qadamini tanlaganda
ѓ(x 1к
)<ѓ(xк ) shart urniga
ѓ(x
к )-ѓ(x к -α
 



 k f )≥βα║  



 k f ║І, 0<β<1 (6)
shartning bajarilishini tekshirib borish kerak bo’ladi. (6) shartni xisobga olgan
holda kurilgan {x
к } ketma-ketlik uchun I- teorema o’z kuchida qoladi.
4) Ba’zi hollarda iterasiya qadami kichaytirilganda funksiyaning kamayishi
tezlashishi mumkin.
4- misol. ѓ(x)=
min 6 5 5 2 1 22 21    x x x x ,xЄRІ.
xє=

 

2
1 - boshlang’ich nuqta bo’lsin.

  , 6 10
6 10
1 2
2 1 






  

x x
x x
x
x f   .2
14
0

 
 
 
x
x f
Iterasiya qadami
4
1   bo’lsin.
      36 , 13 ,
2
3
2
3
4
1
2
1
102
140
01  












 
 
 
 
    xf xf x
x f x x 
.
   
0.1 xf x f 
bo’lgani uchun iterasiya qadamini bo’lamiz:
.8
1
4
1*2
1   
1 
no’qtani qayta xisoblaymiz:

     0 1
    4
25 , 8
1
2
1 1 4
5
4
1
2
14
0
 





 
 
 
 
  xf x
xf
Demak ,
) ( ) ( '  x f x f 
. Endi interasiya qadamini o’zgartirmay )8
1 (  
x 2
nuqtani hisoblaymiz:

;
8
78
1
5
11
8
1
4
14
5 ) ( , 5
11 ) ( 1 1 2 1







 

 






 
   
 

  

x
x f x x x
x f  ) ( ) ( , 16
73 ) ( 2 2 x f x f x f  .
Demak, interasiya qadami
8
1  ni keyingi iterasiyada ( 3x ni hisoblash uchun)
foydalanish mumkin. Ammo qaralayotgan misolda interasiya qadamini yanada
kichraytirish funksiyaning kamayishini tezlashtiradi.
16
1
8
1*2
1    deb olamiz.
Bu holda
;
32
932
9
2
192
13
16
1
8
78
1 ) ( ,
2
192
13 ) ( 2 2 3 2












 





  
  





  

x
x f x x x
x f 
) ( ) ( , 256
81 ) (
233 x f x f x f   4x
ni hisoblaymiz ( 16
1   );
;
128
27128
27
8
98
9
16
1
32
932
9 ) ( ,
8
98
9 ) ( 3 3 4 3




















 
  






 

x
x f x x x
x f 
) ( ) ( , 16
9
256
81 ) (
344 x f x f x f   
, 15,0 16
7
256
81 ) ( ) ( 34     x f x f
Agar interasiyalarni to’xtatish uchun
) 15,0 ( , ) ( ) ( 1       k k x f x f k riteriydan
foydalansak.
4x nuqta berilgan masalaning 15,0 aniqlikdagi taqribiy yechimi
bo’ladi.

Matematik programmalashtirishning hisoblash usullari Reja: 1. Bir o’lchovli funksiyani minimallashtirish usullari: a) Oltin kesim usuli. b) Urinmalar usuli. 2. Shartsiz minumum masalasi uchun gradiyentli usullar: a) Gradiyentli eng tez tushish usuli. b) Gradiyentli tushish usuli. c) Iterasiya qadamini bo’lib borish usuli. Asosiy adabiyotlar 1. Р.Габасов, Ф.М.Кириллова. Оптималлаштириш усуллари. Т. Узбекистон, 1995. Qo’shimcha adabiyotlar 2. Васильев Ф.П. Численные методы решения экстремальных задач. М. Наука, 1988. 3. Галеев Е.М., Тихомиров В.М. Краткий курс теории экстремальных задач. М: Изд МГУ. 1989. 4. Карманов В.Г. Математическое программирование. М.Наука.1998. 5. Сухарев А.Г., Тимохов А.Н., Фёдоров В.В. Курс методов оптимизации. М. Наука 1988 6. Исроилов И., Отакулов С. Вариацион хисоб ва оптималлаштириш усуллари. I -кисм. Самарканд. Сам ДУ нашри, 1999, II -кисм Самарканд, СамДУ нашри, 2001

I.Oltin kesim usuli . Bu usul unimodal funksiyalar uchun qo’llaniladi. 3-ta’rif. Agar shunday ] , [ ba x  nuqta mavjud bo’lsaki, f(x) funksiya 0 x nuqtadan chapda kamayuvchi (ya’ni x 1 ,x 2  [a,b], ) ( ) ( 2 1 2 1 x f x f x x x     ), o’ngda esa o’suvchi (ya’ni x 1 ,x 2  [a,b], ) ( ) ( 2 1 2 1 x f x f x x x      ), bo’lsa, bu funksiya [a,b] kesmada unimodal deyiladi (I-chizma ). Unimodal funksiya quyidagi xossalarga ega. .10 Agar ) (x f funksiya ] , [ b а kecmada unimodal bo’lca, u ixtiyoriy ],[],[ badc  kecmada ham unimodal bo’ladi. 2 0 . Agar ) (x f funksiya b] [a, kecmada uzlukciz va unimodal bo’lca, u yagona lokal minimumga ega. Boshqacha aytganda, bunday funksiyalar uchun lokal minimum global minimum ham bo’ladi. 3 0 . b y x a b a y x      ], , [ , nuqtalar bo’yicha unimodal ) (x f funksiyaning ] , [ b а , kecmadagi minimum nuqtacini lokallashtirish mumkin: agar ) (x f  ) (y f bo’lca, lokallashtirish kecmaci - ] , [ y a , ) (x f  ) (y f bo’lganda eca lokallashtirish kecmaci - ] , [ bx bo’ladi. 4-ta’rif. Agar kesmani shund a y ikkita teng bo’lmagan bo’laklarga bo’lish mumkin bo’lsaki, kesma uzunligining uning katta qismi uzunligiga nisbati, katta qism uzunligining kichik qism uzunligining nisbatiga teng bo’lsa, bu bo’linish kesmaning oltin kecimi deb ataladi. Quyidagi, ,),(),(2 yxabrayabrax  nuqtalar ] , [ b a kecmada oltin kecim hosil qiladilar (bu yerda   , 618034,0 2/1 5   r   381966,0 2/ 5 3 2    r ). Ta’rifga acocan, y b a y a y a b a x x b x b a b           

Kesmaning “oltin kecimi” quyidagi xossalarga ega. 1 0 . ] , [ b a kesmada oltin kesim hosil qiluvchi yx , nuqtalar kesmaning o’rtasiga nisbatan simmetrik joylashgan: . , , x b a y x b a y y b s x          2 0 . y x, nuqtalar ] , [ b a kesmada oltin kesim hosil qilsin. U holda; y x x y a y r a x      , ), (2 nuqtalr ],[],[ yaba  kesmada oltin kesim hosil qiladi. Lokallashtirish jarayoni (algoritmi) ) (x f - ] , [ b a kecmada uzlukciz unimodal funksiya bo’lsin. Oltin kesimning va unimodal funksiyalarning xossalaridan foydalanib, (1) masala ye chimini lokallashtirish quyidagicha bajariladi: 1)  0 0 2 0 0 0 0 , , a b r a x b b a a      deb, ) ( 0x f va )( 0yf larni hicoblaymiz; 1k deb, navbatdagi bandga o’tamiz. 2) agar ) ( 1kx f  ) ( 1ky f bo’lsa, 3-bandga, aks holda esa, 4-bandga o’tamiz. 3) 11 ,    kkkk y b a a deb olamiz. Agar   kk ab bo’lsa, hisoblash to’xtatiladi: 1kx nuqta taqribiy yechim deb olinadi; aks holda 1 , ), ( 1 2        k k x y a b r a x k k k k k k deb, 2-bandga qaytamiz. 4) 1 1,     k k k k b b x a deb olamiz. Agar   k k a f bo’lsa, hisoblash to’xtatiladi: 1ky nuqta taqribiy yechim deb olinadi: aks holda 1  k k y x , 1 ), ( _    k k a br x kkk deb, 2-bandga qaytamiz. E slatma. 1. n ta ( n 1) iteras i ya (qadam ) bajarilgandan so’ng hosil bo’lgan lokalashtirish kesmasi ] , [ n nb а ning uzunligi ) ( a b r a b n n n    bo’ladi. Bunda taqribiy yechim *nx ning aniq yechim nx dan chetlanishi (xato ) quyidagichadir: ) ( ) ( } , max{ 1 * * * a b r a br a x x b x x n n n n n n n n n         

2. Har bir iteras i yadan so’ng kx va ky larning faqat bittasining o’zgarganligi t ufayli algoritmning 2-bandini bajarganda ) (x f ning faqat bitta qiymati hisoblanca, yetarli. 2 1 ~ x x x 2 1 ~ x x x a) Qavariq unimodal funsiya b) Qavariqmas unimodal funsiya I-chizma. 1-misol. xxxf  2 )( funksiyaning [0,2] kesmadagi minimum nuqtasini 2,0 aniqlik bilan lokallashtiring. Yechilishi. Algoritmning 1-bandini bajaramiz: 2 ,0 0 0   b a ,     , 764,0 5 3 2 5 3 000002 00           a b a a b r a x     , 236,1 1 5 2 5 1 0000000            a b a a br a y . 292,0 ) ( , 180,0 ) ( 0 0   y f x f A lg o ritmning 2- band ig a o’t a miz. (1-it e r a siya) ) ( 0x f < ) ( 0y f bo’lg a ni uchun, ,0 01  aa . 236,1 0 1   y b    236,1 1 1 a b bo’lg a ni uchun, ikkinchi it e r a siyag a o’t a miz.   ,472,0 11112 11  baabrax , 764,0 0 1   x y ) ( 249,0 ) ( 1 1 y f x f   . D e m a k, , 764,0 ,0 1 2 1 2     y b a a    764,0 2 2 a b . Uchinchi it e r a siyag a o’t a miz.   ;472,0,0298,0 22122222 22  xyxbaabrax

) ( 207,0 ) ( 2 2 y f x f  . D e m a k, . 472,0 , 764,0 , 292,0 332323       a b b b x a Yan a ikkit a it e r a siya b a j a rib, t a l a b qiling a n l o k a l a shtirish k es m as i ] 584,0; 403,0[ ] , [ 55  b a g a ega bo’l a miz.     181,0 55 a b A 0 X 0 U 0 V 0 0 0,764 1,236 2 A 0 X 1 U 1 V 1 0 0,472 0,764 1,236 2 A 0 X 2 U 2 V 2 0 0,292 0,472 0,764 2 A 3 X 3 U 3 V 3 0 0,292 0,472 0,584 0,0,764 2 A 4 X 4 U 4 V 4 0 0,292 … … 0,584 2 A 4 V 4 0 0,403 0,584 2 2 chizma. 472,0 , 403,0 4 4   y x nuqtalar ] 584,0; 292,0[ ] , [ 4 4  b a kesmada oltin kesim hosil qiladi hamda , 241,0 ) ( 4  x f , 249 ) ( 4  y f ) ( 4x f > ) ( 4y f . Demak, 472,0 4 y ni berilgan 2,0 aniqlikdagi taqribiy yechim deb olamiz. 1. Urinmalar usuli. Bu usul qavariq funksiyalar uchun qo’llaniladi. Taqribiy yechimlar to’plami. Qavariq ) (x f funksiyaning [a:b] kesmadagi minumum nuqtasiga yaqinlashuvchi n n b a x n ,...,2,1 ,] : [   nuqtalar ketma-ketligini qaraymiz. Shu maqsadda ,,),)(()(),( / byfbxfycyfyfyxL 

Matematik programmalashtirishning hisoblash usullari

08.08.2023

0

257.7294921875 KB

Похожие