2-mavzu: Iqtisodiy jarayonlarda optimallashtirish usullarini qo’llash. Chiziqli dasturlash masalasini umumiy qo’yilishi va iqtisodiy talqini

---

 

10

2-mavzu: Iqtisodiy jarayonlarda optimallashtirish usullarini qo’llash. 

Chiziqli dasturlash masalasini umumiy qo’yilishi va iqtisodiy talqini. 

 

Reja: 

1. 

 

Chiziqli  dasturlash  (CHD)  masalasining  qo’yilishi  va  uning  turli 

formalarda ifodalanishi. Asosiy tushunchalar. 

2. 

 

Chiziqli  dasturlash  masalasining  geometrik  talqini  va  uni  grafik  usulda 

yechish. 

 

1.  Ma’lumki,  chiziqli  dasturlash  matematik  dasturlashning  tarkibiy  qismi 

bo’lib hisoblanadi. Chiziqli dasturlash masalasini umumiy holda qaraymiz. 

n

n

x

c

x

c

x

c

f









...

2

2

1

1

   

 

 

 

 

 

 

(1) 

chiziqli funksiya va  







































,

...

,

..........

..........

..........

..........

..........

,

...

,

...

2

2

1

1

2

2

2

22

1

21

1

1

2

12

1

11

m

n

mn

m

m

n

n

n

n

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

 

 

 

 

 

 

(2) 

n

j

x

j

,...,

2

,

1

,

0





    

 

 

 

 

 

 

 

(3) 

chiziqli  cheklash  shartlari  sistemasi  berilgan  bo’lsin,  bunda   

i

ij

b

a

,

  va 

j

c

    lar 

berilgan o’zgarmas miqdorlar. 

Chiziqli dasturlash  masalasi, bu 

n

x

x

x

,...,

,

2

1

 o’zgaruvchilarning shunday 

qiymatlarini topish kerakki, ular (2), (3) cheklash sistemasini qanoatlantirib, (1) 

chiziqli funksiya minimum (maksimum) qiymatga ega bo’lsin. 

Chiziqli  dasturlash    masalasining  umumiy  qo’yilishini  bir  necha 

formalarda (shakllarda) yozish mumkin. 

1.

 

Vektorlar shaklida yozilishi. Ushbu belgilashlarni kiritamiz: 

,

...

,

...

,.......,

...

,

...

2

1

0

2

1

2

22

12

2

1

21

11

1

























































































































m

mn

n

n

n

m

m

b

b

b

A

a

a

a

A

a

a

a

A

a

a

a

A

 

)

,...,

,

(

),

,...,

,

(

2

1

2

1

n

n

x

x

x

X

c

c

c

C





 

bo’lib, 

n

n

x

c

x

c

x

c

CX









...

2

2

1

1

 

skalyar 

ko’paytma  bo’lsin.  Bu  holda  chiziqli  dasturlash  masalasini  vektor  ko’rinishda 

quyidagicha ifodalash mumkin: 

CX

Z



 

chiziqli funksiya minimumga ega bo’ladigan  

X

 vektorning  

0

,

...

0

2

2

1

1











X

A

x

A

x

A

x

A

n

n

 

 

 

 

 

 

(4) 

shartlarni qanoatlantiruvchi qiymatini toping. 

2. Matritsa shaklida yozilishi.   

0

,

0





X

A

AX

  shartlarni  qanoatlantiruvchi 

CX

Z



  chiziqli  funksiya 

minimum  qiymatga  ega  bo’ladigan 

X

  vektorning  qiymatini  toping,  bunda 

---

 

11

)

,...,

,

(

2

1

n

c

c

c

C



  satr  matritsa, 























n

x

x

X

...

1

  ustun  matritsa  va 

)

(

ij

a

A



  sistema 

matritsasi hamda 























n

b

b

A

...

1

0

 ustun matritsa bo’ladi. 

3. Yig’indi belgisi orqali yozilishi. 

n

j

x

m

i

b

x

a

j

j

n

j

j

ij

,...,

2

,

1

,

0

;

,...,

2

,

1

,

1













 

shartlarni  qanoatlantiruvchi 







n

j

j

j

x

c

Z

1

  chiziqli  funksiya  minimumga  ega 

bo’ladigan 

j

x

 o’zgaruvchilarning qiymatini toping. 

1-ta’rif. (2) va (3) shartlarni qanoatlantiruvchi 

)

,...,

,

(

2

1

n

x

x

x

X



 vektorga chiziqli 

dasturlash    masalasining  mumkin  bo’lgan  yechimi  yoki  qisqacha  rejasi  (plani) 

deyiladi. 

2-ta’rif. (4) yoyilmaga kiruvchi 

i

x

 larning musbat hadli 

)

,...,

2

,

1

(

m

i

A

i



 vektorlari 

chiziqli  bog’lanmagan  bo’lsa, 

)

,...,

,

(

2

1

n

x

x

x

X



  rejaga  tayanch  reja  (yechim) 

deyiladi. 

)

,...,

2

,

1

(

m

i

A

i



  vektorlar 

m

  o’lchovli  bo’lganligi  uchun  tayanch  reja 

ta’rifidan  ko’rinadiki,  uning  musbat  hadli  koeffitsiyentlari  m  dan  katta 

bo’lmaydi. 

3-ta’rif.  Tayanch  reja  (yechim) 

m

  ta  musbat  komponentlarga  ega  bo’lsa,  unga 

maxsusmas, aks holda maxsus reja deyiladi. 

4-ta’rif.  Chiziqli  funksiya  minimum  (maksimum)  qiymatga  ega  bo’ladigan  reja 

(yechim)ga chiziqli dasturlash  masalasining optimal rejasi (yechimi) deyiladi. 

Chiziqli dasturlash masalasi yechimining ayrim xossalarini qaraymiz: 

1)  chiziqli  dasturlash  masalasi  cheklash  shartlari  sistemasining  rejalari 

(mumkin  bo’lgan  yechimlari)  to’plami  bo’sh  to’plamni  yoki 

Rn

 

  fazoning 

qavariq to’plamini tashkil etadi; 

2)  chiziqli  dasturlash  masalasining  rejalari  to’plami  bo’sh  to’plam 

bo’lmasa  va  maqsadli  funksiya  bu  to’plamda  yuqoridan  (quyidan) 

chegaralangan  bo’lsa,  masala  maksimum  (minimum)  optimal  yechimga  ega 

bo’ladi; 

3)  chiziqli  dasturlash  masalasining  optimal  yechimi  mavjud  bo’lsa,  bu 

yechim mumkin bo’lgan yechimlar to’plamining chegaraviy nuqtalarida bo’ladi. 

2. Chiziqli dasturlash   masalasining geometrik talqinini (tasvirini) 

2



n

, 

ayrim hollarda 

3



n

 bo’lganda ifodalash mumkin. Chiziqli dasturlash  masalasi 

quyidagicha berilgan bo’lsin: 

---

 

12

































0

,

0

,

8

.

2

2

,

9

3

2

2

1

2

1

2

1

2

1

x

x

x

x

x

x

x

x

 

tengsizliklar sistemasini qanoatlantiruvchi 

1

x

 va 

2

x

 o’zgaruvchilarning shunday 

qiymatini topish kerakki, 

2

1

x

x

f





 funksiya maksimum qiymatga ega bo’lsin. 

Yechish.  1) 

9

3

2

2

1







x

x

  tengsizlik  bilan  aniqlanadigan  geometrik 

tasvirni  aniqlaymiz.  Buning  uchun  oldin 

9

3

2

2

1







x

x

  to’g’ri  chiziqni 

2

1

Ox

x

 

koordinat  tekisligida  yasaymiz.  Ma’lumki,  to’g’ri  chiziq 

)

3

;

0

(

A

  va 

)

0

;

5

,

4

(



B

 

nuqtalardan o’tadi. 

Endi 

9

3

2

2

1







x

x

  tengsizlikka  mos  geometrik  tasvirni  aniqlash  uchun, 

berilgan  tengsizlikka  koordinatlar  boshi 

)

0

;

0

(

O

  nuqtaning  koordinata-larini 

qo’yamiz: 

9

0

3

0

2











  yoki 

9

0



  tengsizlik  bajariladi,  shuning  uchun 

9

3

2

2

1







x

x

  tengsizlik  bilan  aniqlanadigan  geometrik  tasvir  koordinatlar 

boshi, 

)

0

;

0

(

O

 nuqtani o’z ichiga olgan yarim tekislikdan iborat bo’ladi. 

2)  Xuddi  yuqoridagidek  kolgan  tengsizliklarga  mos  kelgan  yarim 

tekisliklarni  yasaymiz. 

2

2

2

1





x

x

,  bu  to’g’ri  chiziq 

)

0

;

2

(

),

1

;

0

(

1

1

B

A



 

nuqtalardan o’tadi. 

2

0

,

2

0

2

0

,

2

2

2

1













x

x

 tengsizlik bajariladi.  

В

1 

В

2 

В

 

А

 

С

 

А

1 

Д

С

х

2 



 0 

х

1 



 0 

А

2 

I

 

II

 

III

 

х

1 

 

х

2 

 

l (a=4) 

l (a=2) 

l (a=0

)

 

O

 

q(1,-1) 

 

1-chizma 

3) 

8

2

1





x

x

 to’g’ri chiziq 

)

0

;

8

(

),

8

;

0

(

2

2

B

A

 nuqtalardan o’tadi. 

---

 

13

8

0

,

8

0

0

,

8

2

1











x

x

 bo’ladi. 

4) 

0

,

0

2

1





x

x

 yarim tekisliklarni ham yasaymiz: 

Shunday  qilib,  berilgan  tengsizliklar  sistemasini  qanoatlantiradigan 

mumkin bo’lgan  yechimlar to’plami - 

ОАСДВ

 yechimlar ko’pburchagini  hosil 

qildik.  Ma’lumki,  bu  to’plam  qavariq  to’plamdan  iborat,  ya’ni  birinchi  xossa 

bajariladi (1-chizma). 

Endigi  masala  bu  to’plamning  shunday  nuqtasini  topish  kerakki, 

2

1

x

x

F





  chiziqli  funksiya  max   qiymatga  ega  bo’lsin.  Tekislikda 

F

    bir  xil 

qiymatlar  qabul  qiladigan  nuqtalarning  joylanishini  topamiz.  Buning  uchun 

a

F



  deb olamiz.  Bu  holda 

a

x

x





2

1

 tenglama  hosil bo’lib, bu 

F

  funksiya 

bir  xil 

a

  qiymat  qabul  qiladigan  to’g’ri  chiziqdir. 

a

ning  o’rniga  har  xil 

qiymatlar  qo’yish  bilan 



  parallel  to’g’ri  chiziqlarni  hosil  qilamiz.  Bu  to’g’ri 

chiziqlarning  har  biriga  sath  chizig’i  (ya’ni  funksiya  bir  xil  qiymatlar  qabul 

qiluvchi to’g’ri chiziq) deyiladi. 

Chiziqli funksiya koeffitsiyentlaridan tuzilgan 

)

1

,

1

(



q

 vektorni qaraymiz. 

Bu vektorga perpendikulyar 



 chiziqni o’tkazamiz (bu sath chiziqlardan biri) va 

uni  o’ziga  parallel  mumkin  bo’lgan  yechimlar  to’plami  bilan  kesishmay 

qolguncha  siljitamiz.  Bu  yerda,  masalada  maksimal  qiymat  topilishi  kerak 

bo’lsa,  vektorning  yo’nalishi  bo’yicha,  minimal  qiymat  topilishi  kerak  bo’lsa, 

vektorning yo’nalishiga qarama-qarshi tomonga siljitiladi. 



  to’g’ri  chiziqni  o’ziga-o’zini  parallel  qanchalik  siljitilmasin,  bari  bir 

mumkin  bo’lgan  yechimlar  to’plamini  kesib  o’taversa,  chiziqli  funksiya 

yuqoridan  (minimal  qiymatlar  uchun  quyidan)  chegaralanmagan  bo’ladi  va 

optimal  yechimga  ega  bo’lmaydi.  Qaralayotgan  masalada 



  chiziqni  parallel 

siljitilganda 

ОАСДВ

  mumkin  bo’lgan  yechimlar  to’plami  bilan  D  nuqtada 

oxirgi umumiy nuqtada ega bo’lib, bu nuqtada funksiya maksimal qiymatga ega 

bo’ladi.  Ma’lumki,  bu  nuqta 

2

2

2

1





x

x

, 

8

2

1





x

x

  to’g’ri  chiziqlarning 

kesishgan  nuqtasi  bo’lib,  ularni  birgalikda  yechib  nuqtaning  koordinatalarini 

aniqlaymiz: 

2

8

2

2

2

1

2

1















x

x

x

x

 

2

,

4

2

,

2

2

6

,

6

,

18

3

2

2

2

1

1

















x

x

x

x

x

. 

Shunday  qilib,  D  nuqtaning 

2

,

6

2

1





x

x

  koordinatalari  masala  yechimi 

bo’ladi. 

4

2

6

max







F

. 

Bu  bilan  chiziqli  dasturlash  masalasining  3-xossaning  ham  bajarilishini 

ko’rsatdik. 

 

3.  Chiziqli  dasturlash    masalasini  yechishning  simpleks  usuli.  Payqash 

mumkinki,  yechimlar  ko’pburchagining  shunday  burchak  nuqtasi  mavjudki,  bu 

nuqtada  chiziqli  funksiya  optimal  qiymatga  ega  bo’ladi.  Yechimlar 

ko’pburchagining har bir burchak nuqtasiga birorta tayanch yechim mos keladi. 

---

 

14

Tayanch  yechim 

m

  ta  chiziqli  bog’lanmagan  vektorlar  sistemasi  orqali 

aniqlanib, bu sistemada 

n

 ta 

n

A

A

A

,...,

,

2

1

 vektorlar qatnashadi. Optimal yechimni 

topish  uchun  faqat  tayanch  yechimlar  tekshiriladi.  Bunday  masalada  tayanch 

yechimlar  sonining  yuqori  chegarasi 

m

n

C

  guruhlashlar  soni  bilan  aniqlanadi. 

m

 

 

va 

n

  lar  katta  sonlar  bo’lganda  optimal  yechimni,  hamma  tayanch  yechimlarni 

saralab  (tekshirib)  topish  juda  katta  murakkablikka  olib  keladi.  Shuning  uchun, 

biror  tartiblangan  sxema  bo’yicha  bir  tayanch  yechimdan  ikkinchi  tayanch 

yechimga o’tish algoritmiga ega bo’lishga  to’g’ri keladi.  Bunday sxema bo’lib, 

simpleks usul hisoblanadi. 

Chiziqli  dasturlash    masalasini  simpleks  usul  bilan  yechishga  ko’pincha 

rejani  (yechimni)  ketma-ket  yaxshilash  usuli  ham  deb  yuritiladi.  Bunday 

atalishida  usulning  asosiy  g’oyasi,  quyidagi  ketma-ket  amalga  oshiriladigan 

qadamlardir: 

1-qadam, boshlang’ich mumkin bo’lgan yechim topiladi; 

2-qadam, topilgan yechimning optimalligi tekshiriladi; 

3-qadam,  yechim  optimal  bo’lmasa,  2-qadamda  optimal  yechimga 

yaqinroq boshqa mumkin bo’lgan yechimga o’tiladi. Keyin, yana 2-qadamga va 

hakozo  optimal  yechim  olinguncha  davom  ettiriladi.  Masala  yechimga  ega 

bo’lmasa  yoki  maqsadli  funksiya  yechimlar  ko’pburchagida  chegaralanmagan 

bo’lsa,  simpleks  usul  bilan  yechish  jarayonida  buni  aniqlash  imkoniyati 

yaratiladi. 

Bazis  rejani  topish.  Quyidagi  chiziqli  dasturlash  masalasi  qo’yilgan 

bo’lsin: 

n

n

x

c

x

c

x

c

z









...

2

2

1

1

 chiziqli  funksiyaning 











































)

,...,

2

,

1

(

0

,

...

,

..........

..........

..........

..........

..........

,

...

,

...

2

2

1

1

2

2

2

22

1

21

1

1

2

12

1

11

n

j

x

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

j

m

n

mn

m

m

n

n

n

n

 

 

 

cheklash  shartlarini  qanoatlantiruvchi  minimum  qiymatini  topish  talab  etiladi. 

Bunda 

)

,...,

2

,

1

(

,

0

m

j

b

j





.  Bunday  qo’yilgan  masalaga  chiziqli  dasturlashning 

kanonik masalasi deyiladi. 

Cheklash shartlari 

m

 ta vektorlar bo’lsin. Bu holda 

n

n

x

c

x

c

x

c

z









...

2

2

1

1

,   

 

 

 

 

 

 

 (5) 

chiziqli funksiyaning  







































,

...

,

..........

..........

..........

..........

..........

,

...

,

...

2

2

1

1

2

2

2

22

1

21

1

1

2

12

1

11

m

n

mn

m

m

n

n

n

n

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

    

 

 

 

 

(6) 

)

,...,

2

,

1

(

0

n

j

x

j





,   

 

 

 

 

 

 

 

(7) 

cheklash  shartlarini  qanoatlantiruvchi  minimum  qiymatni  topish  masalasi  hosil 

bo’ladi. (6) sistemani vektor shaklida yozsak: 

0

1

1

2

2

1

1

...

...

A

A

x

A

x

A

x

A

x

A

x

n

n

m

m

m

m

















  

 

 

 

(8) 

---

 

15

yoyilma hosil bo’ladi, bunda 

,

...

,....,

...

,

1

...

0

0

,...,

0

...

1

0

,

0

...

0

1

,

...

2

1

1

,

1

,

2

1

,

1

1

2

1

2

1

0





























































































































































































mn

n

n

n

m

m

m

m

m

m

m

a

a

a

A

a

a

a

A

A

A

A

b

b

b

A

 

m

A

A

A

,...,

,

2

1

  vektorlar 

m

  o’lchovli  fazoning  chiziqli  bog’lanmagan  birlik 

vektorlari  bo’ladi.  Bular  bu  fazoning  bazisini  tashkil  etadi.  Shuning  uchun,  (8) 

yoyilmada  bazis  o’zgaruvchilari  uchun 

m

x

x

x

,...,

,

2

1

  larni  olib,  ozod 

n

m

m

x

x

x

,...,

,

2

1





  o’zgaruvchilarni  0  ga  teng  deb,  hamda 

)

,...,

2

,

1

(

,

0

m

j

b

j





 

ekanligini hisobga olib, 

m

A

A

A

,...,

,

2

1

 birlik vektorlar bo’lganligi uchun 





0

,...,

0

,

0

,

,...,

,

2

1

2

2

1

1

0



















n

m

m

m

m

x

x

x

b

x

b

x

b

x

X

   

(9) 

boshlang’ich rejani hosil qilamiz. (9) reja 

0

2

2

1

1

...

A

A

x

A

x

A

x

m

m









  

 

 

 

 

 

 

(10) 

yoyilmaga  mos  kelib, 

m

A

A

A

,...,

,

2

1

  vektorlar  chiziqli  bog’lanmagan,  demak 

boshlang’ich olingan reja tayanch reja ham bo’ladi.