Тошкент Ахборот Технологиялари Университети Кафедраси: дт гурух: 216-05 иту

Ўзбекистон Алоқа ва Ахборотлаштириш Агентлиги
Тошкент Ахборот Технологиялари Университети


Кафедраси: ДТ


Гурух: 216-05 ИТу
Бажарди: Абдиев Н.
Текширди:Неъматов А.


\
Тошкент -2007.
Кўпгина оптималлаш масалаларини бирор бир босқичда 1 бир ўзгарувчили функцияларни мунималлаштириш масаласига келтирилади. Шунинг учун оптималлаш масалаларини ечиш самарадорлиги 1 ўзгарувчили функцияларни минималлаштириш усулларини танлашга боғлиқдир. 1 ўзгаурвчили функцияларни анъанавий (классик) усуллардан тақари юқори самарага эга бўлган оптималлаштиришни қидирув усулларидан фойдаланилади. Бу усулларнинг кўпчилиги шунга мўлжалланганки оптималлаштирилаётган функция у(х) бирор бир оралиқда берилган (аниқланган), узлуксиз ва унимодал, яъни берилган оралиқда [a,b] 1 та минимумга эгадир. Унимодал функциялар учун қуйидаги ифодалар ўринли:

1. 
   Агар бўлса, у ҳолда y(x₁)2) бўлади.
   
2. 
   Агар x₁2* бўлса, у ҳолда y(x₁)>y(x₂) бўлади, бу ерда x^* - min нуқтаси.
   

Дихатомия усули. Дихатомиясўзи – грекча сўз бўлиб, бирор бир кемани тенг иккига бўлиш маъносини англатади. Бу жуда содда ва самарали усулдир. Ҳар бир қадамда min ётган интервал тенг иккига бўлинади ва min ётмаган ярим бўлак ташлаб юборилади.
Фараз қилайлик функция min и қуйидаги кесмада .

1. 
   қ адамда кесма тенг иккига бўлинади
   

нуқтадан функция min и қайси тарафда ётганлигини аниқлаш учун функцияни (х₁) ва (х₂) даги қийматлари ҳисобланади . - ҳисоблаш аниқлиги ёки ноаниқлик.
Агар бажарилса, функция min нуқтаси нуқтадан чап томонда жойлашган бўлади ва кесманинг ўнг томони ташлаб юборилади. Акс ҳолда кесманинг чап тарафи ташлаб юборилади. Натижада қолган кесма (ташланмагани) яна тенг иккига бўлинади ва ҳисоблаш жараёни юқоридаги сингари давом эттирилади. Бу жараён берилган марта давом эттирилади ёки бирор-бир ҳисоблаш аниқлиги бажарилгунча давом эттирилади. Дихатомия усулида бирор k- қадамдаги амаллар тартиби қуйидагича:

1. 
   Кесманинг ўртаси аниқланади .
   
2. 
   
   
3. 
   Функциянинг ва нуқталардаги қийматлари солиштирилади, агар бўлса, унда
   
4. 
   Ҳисоблаш жараёнини тўхтатиш шарти таҳлил этилади:
   

а) Агар бўлса, 1- пунктга ўтилади;
б) Агар бўлса, у ҳолда оҳирги кесманинг ўртаси олинади.
Бу усулда ҳисоблш жараёнининг натижалари жадвал шаклида келтириш жуда қулайдир. Бу жадвал 9 та устун ва k та қатордан иборат, бу ерда k- қидирув қадамлар сони кесманинг узунлиги.

k		x^++(k)	l^(k)
1		x^++(1)	l^(1)
2		x^++(2)	l^(2)
k		x^++(k)	l^(k)
k+1		x^++(k+1)	l^(k+1)

Юқоридаги келтирилганлар асосида қуйидаги мисолни кўриб чиқамиз:

У =2х³-12х²+5х-5 ε=0.05

k		x^++(k)	l^(k)
1	0	0.5	0.5	0.25	0.225	0.275	-4.4597188	-4.4909064
2	0.25	0.5	0.25	0.375	0.35	0.4	-4.63425	-3.64
3	0.25	0.375	0.125	0.3125	0.2875	0.3375	-4.5068472	-4.6024878
4	0.3125	0.375	0.0625	0.34375	0.3225	0.36875	-4.5684906	-4.6876854
5	0.34375	0.375	0.03125	0.359375

Ҳулоса
Бу жадвалда , x^++(k) лар берилган [0; 0.5] оралиқ (кесма)нинг 1- ва 2- нуқталларидир. 1- қадамда кесма тенг 2 га бўлинади

нуқтадан функция min и қайси тарафда ётганлигини аниқлаш учун функцияни (х₁) ва (х₂) даги қийматлари ҳисобланади .
Бунда бизда > бўлгани учун нуқтадан ўнг томонда жойлашганлиги маълум бўлди.

2. 
   қадамда , x⁺⁺⁽²⁾ нуқталар [0.25; 0.5] ва l⁽²⁾=0.25, =0.375, =0.35, =0.4, =-4.63425, =-3.64 қийматлар келиб чиқди.
   
3. 
   Қадамда < бўлгани учун функция min нуқтаси нуқтадан чап томонда жойлашганлиги маълум бўлди. , x⁺⁺⁽³⁾ нуқталар [0.25; 0.375] ва l⁽³⁾=0.125, ³=0.3125, =0.2875, =0.3375, =-4.5068472, =-4.6024878 қийматлар келиб чиқди.
   
4. 
   Қадамда > бўлгани учун функция min нуқтаси нуқтадан ўнг томонда жойлашганлиги маълум бўлди. , x⁺⁺⁽⁴⁾ нуқталар [0.3125; 0.375] ва l⁽⁴⁾=0.0625, ⁴=0.34375, =0.3225, =0.36875, =-4.5684906, =-4.6876854 қийматлар келиб чиқди.
   
5. 
   Қадамда > бўлгани учун функция min нуқтаси нуқтадан ўнг томонда жойлашганлиги маълум бўлди. , x⁺⁺⁽⁵⁾ нуқталар [0.34375; 0.375] ва l⁽⁵⁾= 0.03125, ⁵=0.34375, қийматлар келиб чиқди ва ε<0.05 бўлгани учун ҳисоблаш тўхтатилди.
   

x^*= y_max=-4.5684906.