9-mavzu. Chiziqli emas dasturlash masalasining qo’yilishi. Chiziqli emas dasturlash masalasining xususiy holatlari

9-MAVZU. Chiziqli emas dasturlash masalasining qo’yilishi. Chiziqli emas 

dasturlash masalasining xususiy holatlari 

Bu masala umumiy turda quyidagicha yoziladi: 

( )

(

)

(

)

max

min

,...,

,

2

1

→

=

n

x

x

x

f

x

f

,  

 

 

       (1) 

( )

(

)

1

2

,

,...,

,

1,

i

i

n

i

g x

g x x

x

b

i

s

=



=

, 

 

 

      (2) 

( )

(

)

1

2

,

,...,

,

1,

i

i

n

i

h x

h x x

x

b

i

s

m

=

=

= +

 

 

 

     (3) 

(

)

n

i

x

i

,

1

0

=



 

 

 

 

 

(4) 

f(x)  –  (1)-(4)-ChED  masalasining  maqsad  funksiyasi  ; 

( ) ( )

,

i

i

g x h x

-  chegaraviy 

shartlarning funksiyalari; 

i

b

 - chegaraviy shartlarning ozod hadlari bo’lib, oldindan 

berilgan  haqiqiy  sonlar.  ChED  masalasining  (2)-(4)-chegaraviy  shartlarini 

qanoatlantiruvchi 

(

)

1

2

,

,...,

n

x

x x

x

=

  nuqtasi  bu  masalaning  mumkin  bo’lgan  yechimi 

deb ataladi. 

(1)-(4)-ChED  masalasining  optimal  yechimi  deb,  uning  f(x)  maqsad 

funksiyasiga  minimum  yoki  maksimum  qiymat  beradigan  mumkin  bo’lgan 

yechimiga aytiladi. 

(1)-(4)-ChED  masalasini  akslantirib  har  xil  ko’rinishda  yozish  mumkin. 

Buning uchun quyidagi nisbatlardan foydalanadi: 

1) Agarda 

( )

0

i

g x =

 bo’lsa, bu tenglikni unga teng kuchli bo’lgan  

( )

( )

0

0

i

i

g x

g x

−











 

ikki tengsizlikning sistemasi bilan almashtirish mumkin; 

2) 

( )

0,

1,

i

g x

i

m

=

=

 sondagi tengliklar berilgan bo’lsa, unda uni yagona tenglik bilan 

almashtirish mumkin: 

2

1

( )

0

m

i

i

g x

=

=



 

3) Agarda 

( )

0

i

g x 

 tengsizligi berilgan bo’lsa, bu tengsizliklarni 

2

( )

0

i

g x

z

+

=

,    

1,

i

m

=

 

tengligi  ko’rinishida  tanlab  olish  mumkin.  Bu  yerda  z  ixtiyoriy  ravishda  tanlab 

olingan bazi bir funksiya. 

Berilgan (1)-(4)-ChED masalasini ko’rsatilgan har xil formada yozish mumkin. 

ChED masalasining ChD masalasidan farqi 

ChED masalalarining to’plami ChD  masalalarida solishtirganda ancha keng 

bo’ladi. Sababi ilmiy-texnik va murakkab amaliy masalalarning ko’pchiligi ChED 

masalasini  yechishga  keltiriladi.  Bu  masalaning  matematik  modeli  ChD 

masalasining  matematik  modeliga  qaraganda  haqiqiy  jarayonlarni  ancha  aniqroq 

tasvirlaydi. Quyida ular orasidagi farqlarga to’xtalib o’tamiz. 

1)  Mumkin bo’lgan yechimlarning to’plami doimo qavariq to’plam bo’ladi.  

2)  ChD masalasi doimo yagona global yechimga ega bo’ladi, local yechimga 

ega  bo’lmaydi.  Sababi  bu  masalaning  yechimi  D  qavariq  to’plamining 

chegarasidan  qidiriladi.  ChED  masalasida  ChD  masalasining  yuqorida 

keltirilgan xususiyatlari ko’p hollarda bajarilmaydi. Sababi: 

a)  Maqsad  funksiyasi  f(x)  va  chegaraviy  shartlarning  funksiyalari 

chiziqsiz  funksiyalar  bo’lgani  uchun  mumkin  bo’lgan  yechimlarning 

to’plami D ko’p hollarda qavariq emas to’plam bo’ladi. 

b)  ChED masalasining optimal yechimi D mumkin bo’lgan to’plamining 

ichida va chegarasida yotishi mumkin. 

c)  ChED masalasi local va global yechimlarga ega bo’ladi. Ko’p hollarda 

bu  masalaning  local  yechimi  topiladi.  Lekin  uning  yordamida  global 

yechimni toppish mumkin bo’lmaydi. 

Shu  ko’rsatilgan  holatlarga  bog’iq  shu  paytgacha  ChED  masalalarini 

yechishga imkon beradigan universal usullar yaratilmagan. Faqatgina bu masalaning 

bazi xususiy hollarini yechishning yaxshi, natijali taqribiy usullari yaratilgan. 

 

ChED masalalarining bazi xususiy hollari 

ChED  masalasining  yechimlarini  aniqlashning  qulay,  taqribiy  usullari 

yaratilgan ba’zi xususiy hollarini keltirib o’tamiz. 

1)  Agarda  f(x)  maqsad  funksiyasi  va  chegaraviy  shartlarning   

( ) ( )

,

i

i

g x h x

 

funksiyalarichiziqli  funksiyalar  bo’lsa,  u  holda  yuqorida  qaralgan  ChD 

masalasiga ega bo’lamiz: 

( )

min

...

2

2

1

1

→

+

+

+

=

n

n

x

C

x

C

x

C

x

f

   

 

      (1) 

s

i

b

x

a

i

j

n

j

ij

,

1

,

1

=

=



=

   

 

 

 

      (2) 

m

s

i

b

x

a

i

j

n

j

ij

,

1

,

1

+

=





=

 

 

 

 

      (3) 

0,

1,

j

x

j

n



=

 

 

 

 

 

(4) 

2)  Agarda (1)-(4)-da m=0 bo’lsa  

( )

(

)

(

)

(

)

1

2

1

2

,

,...,

min max

,

,...,

n

n

n

f x

f x x

x

x

x x

x

E

=

→

=



   

 

(5) 

shartsiz ekstremum masalasi kelib chiqadi. 

3)  Agar (1)-(4)-chegaraviy masalasida faqatgina tenglik chegaraviy shartlari 

bor bo’lsa, 

 

( )

(

)

(

)

max

min

,...,

,

2

1

→

=

n

x

x

x

f

x

f

 

 

 

 

(6) 

( )

(

)

1

2

,

,...,

,

1,

i

i

n

i

g x

g x x

x

b

i

m

=

=

=

   

 

 

(7) 

(

)

n

i

x

i

,

1

0

=



   

 

 

 

 

(8) 

u holda chegaraviy shartlari tenglik bo’lgan ChED masalasi kelib chiqadi. 

(5),(6)-(8)-ChED  masalalarini  differensial  hisob  usullaridan  foydalanib  yechish 

mumkin bo’lgani sababli bunday masalalar klassik ekstremum masalalari deyiladi. 

4)  Hozirgi  paytda  qavariq  dasturlash  masalalari  deb  ataluvchi  masalalarni 

yechishning  hisoblash  maqsadlari  uchun  qulay  natijali  usullari  yaratilgan. Agarda 

mumkin bo’lgan to’plami D va f(x) funksiyasi qavariq funksiya bo’lsa u holda paydo 

bo’lgan  ChED  masalasi  qavariq  dasturlash  masalasi  deyiladi.  Bu  masalaning 

xususiy hollari quyidagilar bo’ladi: 

a) Kvadratik dasturlash masalasi: 

( )

(

)





=

=

=

→

+

=

n

j

n

i

n

j

j

i

ij

j

j

x

x

c

x

d

x

f

1

1

1

max

min

, 

 

 

  (9) 

m

i

b

x

a

n

j

i

j

ij

,

1

,

1

=





=

   

 

 

 

       (10) 

n

j

x

j

,

1

,

0

=



 

 

 

 

            (11) 

b) Separagraf programmalash masalasi: 

(

)

1

2

1

,

,...,

(

)

min(max)

n

n

j

j

j

j

f x x

x

d f x

=

=

→



   

 

 

(12) 

1

( )

,

1,

n

i

ij

j

i

j

g x

a x

b

i

m

=

=



=



 

 

 

 

(13) 

n

j

x

j

,

1

,

0

=



 

 

 

 

 

(14) 

Qavariq  dasturlash  masalalari  quyidagi  juda  ahamiyatli  xususiyatlarga  ega. 

Bu  masalaning  ixtiyoriy  local  yechimi  ularning  global  yechimi  ham  bo’ladi.  Bu 

xususiyatning  ahamiyati  shundan  iborat,  taqribiy  usullar  yordamida  doimo  ChED 

masalasining local yechimi topiladi. Shuning uchun qavariq dasturlash masalalarida 

bir vaqtda qo’yilgan masalaning global yechimi ham topiladi.