Toshkent axborot texnologiyalari universiteti huzuridagi dasturiy mahsulotlar va apparat dasturiy majmualar yaratish

x₁  0, x₂  0, , x_m  0,

^Ymax ^

c₀ 

c₁x₁ 

c₂ x₂   

c_mx_m

Chzizqli dasturlash masalalari. Chiziqli dasturlash masalasi umumiy holda quyidagicha ifodalanadi:

_a₁₁x₁  a₁₂ x₂      a_1nx_n  ()b₁

^a x a x      a x  ()b

^ 21 1 22 2


m2 m 2
(1)

_.................................................

^_a_m1x₁  a_m2 x₂      a_mn x_n  ()b_m

x₁  0, x₂  0, , x_n  0,
(2)

^Ymin(max) ^

c₀ 

c₁x₁ 

c₂ x₂   

c_nx_n
(3)

1. va (2) shartlarni qanoatlantiruvchi noma’lumlarning shunday qiymatlarini topish kerakki, ular (3) chiziqli funktsiyaga minimal (maksimal) qiymat bersin. Masalaning (1) va (2) shartlari uning chegaraviy shartlari deb, (3) chiziqli funktsiya esa masalaning maqsadi yoki maqsad funktsiyasi deb ataladi.

   
   

Masaladagi barcha chegaralovchi shartlar va maqsad funktsiya chiziqli ekanligi ko’rinib turibdi. SHuning uchun ham (1)–(3) masala chiziqli dasturlash masalasi deb ataladi.

Konkret masalalarda (1) shart tenglamalar sistemasidan, «» yoki «» ko’rinishdagi tengsizliklar sistemasidan yoki aralash sistemadan iborat bo’lishi mumkin. Lekin ko’rsatish mumkinki, (1)–(3) ko’rinishdagi masalani osonlik bilan quyidagi ko’rinishga keltirish mumkin.


_a₁₁x₁  a₁₂ x₂      a_1n x_n  b₁

^a x a x      a x  b

^ 21 1 22 2 2n n 2
(4)

^



^_a_m1x₁  a_m2 x₂      a_mn x_n  b_m

x₁  0, x₂  0,
, x_n  0,
(5)

^Ymin ^

c₀ 

c₁x₁ 

c₂ x₂   

c_n x_n
(6)

(4)-(6) ko’rinish chiziqli dasturlash masalasining kanonik ko’rinishi deb ataladi. (4)–(6) masalani vektorlar yordamida quyidagicha ifodalash mumkin:

P₁x₁ 

P₂ x₂   

P_n x_n  P₀
(7)

X  0 (8)

Y_min  CX
 ^b₁ 

	^^a11  a p   21  a	  ^a12   a ^ 2 ...   a		  ^, ...,   	^^a1n  a p   2n  a	     
bu yerda

 _b 
(9)

^, p  ^{ 22}
, p  ^{ 2 },

^{1 }...

^{n }...

^{0 }... ^

 _b 

 m1   m2

 mn
 m 

^{S } <sup>C1, C2,

X </sup>  <sup>X1, X2,

, Cn</sup>  <sup>– vektor–qator.

, Xn</sup>  ^{– vektor–ustun.}

(4)-(6) masalaning matritsa ko’rinishdagi ifodasi quyidagicha yoziladi:

AX  P₀ (10)
X  0, (11)
Y_min  CX (12)

bu yerda

^{S } <sup>C1, C2,

, Cn</sup> 
– qator vektor,


A  _a_{ij }
– (4) sistema

koeffitsientlaridan tashkil topgan matritsa;

^{X }  <sup>X1, X2,

, Xn</sup>  ^va

P₀ 

^{b1, b2,}

^{, bn} 
– ustun vektorlar.

n
_a_ij x_j  b_i , (i  1,..., m)

j1
(13)

x_j  0, ( j 1,..., n)
(14)

^Ymin ^{ C}j ^X j j1
(15)

(4)-(6) masalani yig’indilar yordamida ham ifodalash mumkin:

1. 
   
   ta’rif. Berilgan (4)–(6) masalaning mumkin bo’lgan echimi yoki rejasi
   

deb, uning (4) va (5) shartlarni qanoatlantiruvchi

aytiladi.


^{X }  <sup>x1, x2,

, xn</sup> 
vektorga

2. 
   
   ta’rif. Agar (7) yoyilmadagi musbat x_i
   

koeffitsientli

P_i ,
^{i  1,, m}

vektorlar o’zaro chiziqli bog’iq bo’lmasa, u holda X

reja deb ataladi.


^  <sup>x1, x2,

, xn</sup> 
reja tayanch

3. 
   
   ta’rif. Agar
   

^{X }  <sup>x1, x2,

, xn</sup> 
tayanch rejadagi musbat komponentalar

soni m ga teng bo’lsa, u hoda bu reja aynimagan tayanch reja, aks holda aynigan tayanch reja deyiladi.

4. 
   
   ^{ta’rif. CHiziqli funktsiya (6) ga eng kichik qiymat beruvchi X=(x}1^{, x}2^{, …, x}n^{) tayanch reja masalaning optimal rejasi yoki optimal echimi deyiladi.}
   

Chiziqli dasturlash masalasining geometrik talqini. Quyidagi ko’rinishda yozilgan chiziqli dasturlash masalasini ko’ramiz:

n

^aij ^x j ^{ a}i

j1
(i  1, m) (1)

x _j  0, ( j  1, n) (2)

n

^Ymax(min) ^{ c}j ^x j

j1
(3)

Ushbu chiziqli dasturlash masalasining geometrik talqini bilan tanishamiz.

^{Ma’lumki, n ta tartiblashgan x}1^{, x}2^{, …, x}n ^{sonlar n-ligi (birlashmasi) n} o’lchovli fazoning nuqtasi bo’ladi. Shuning uchun (1)-(3) chiziqli dasturlash masalasining rejasini n o’lchovli fazoning nuqtasi deb qarash mumkin. Bizga ma’lumki, bunday nuqtalar to’plami qavariq to’plamdan iborat bo’ladi. Qavariq to’plam chegaralangan (qavariq ko’pburchak), chegaralanmagan (qavariq ko’p qirrali soha) bo’lishi, bitta nuqtadan iborat bo’lishi yoki bo’sh to’plam bo’lishi ham mumkin.
Koordinatalari

a₁x₁ 

a₂ x₂   

a_n x_n  a

tenglamani qanoatlantiruvchi (x₁, x₂, …, x_n) nuqtalar to’plami gipertekislik deb ataladi. Shu sababli

c₁x₁ 

c₂ x₂   

c_nx_n  Y

ko’rinishda yozilgan maqsad funktsiyani Y funktsiyaning turli P qiymatlariga mos keluvchi o’zaro parallel gipertekisliklar oilasi deb qarash mumkin.
Har bir gipertekislikning ixtiyoriy nuqtasida Y funktsiya bir xil qiymatni qabul qiladi (demak, o’zgarmas sathda saqlanadi). SHuning uchun ular «sath tekisliklari» deyiladi. Geometrik nuqtai nazardan chiziqli dasturlash masalasini quyidagicha ta’riflash mumkin:

1. va (2) shartlarni qanoatlantiruvchi yechimlar ko’pburchagiga tegishli bo’lgan

   
   

shunday

X ^* 
(x ^*, x ^*,
, x ^*)
nuqtani topish kerakki, bu nuqtada Y maqsad

funktsiya maksimum (minimum) qiymat beruvchi (3) gipertekisliklar oilasiga tegishli bo’lgan gipertekislik o’tsin. Jumladan, n=2 da (1)-(3) masala quyidagicha

1 2

n

talqin qilinadi: (1)-(2) shartlarni qanoatlantiruvchi yechimlar ko’pburchagiga

1 2

tegishli bo’lgan shunday

X ^* 

_x ^*, x ^* _
nuqtani topish kerakki, bu nuqtadan Y

maqsad funktsiyaga eng katta (eng kichik) qiymat beruvchi va (3) daraja chiziqlar oilasiga tegishli bo’lgan chiziq o’tsin.

Chiziqli dasturlash masalasining geometrik talqiniga hamda oldingi ma’ruzalarda tanishgan chiziqli dasturlash masalasi yechimining xossalariga tayanib masalani ba’zi hollarda grafik usulda yechish mumkin.


_a₁₁x₁  a₁₂ x₂  b₁,

^a x a x  b ,

^ 21 1 22 2 2
(4)

^



^_a_m1x₁  a_m2 x₂  b_m ,

x₁  0,

x₂  0,
(5)

Y_max  c₁x₁  c₂ x₂
(6)

Ikki o’lchovli fazoda berilgan ushbu chiziqli dasturlash masalasini ko’ramiz. Faraz qilaylik, (4) sistema (5) shartni qanoatlantiruvchi yechimlarga ega bo’lsin. Hamda ulardan tashkil topgan to’plam chekli bo’lsin. (4) va (5)
tengsizliklarning har biri

a_i1x₁ 

a_{i 2} x₂ 

^bi ^{i  1,, m}^,

x₁  0, x₂  0
chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. Chiziqli funktsiya (6)

ham ma’lum bir o’zgarmas

C₀  const
qiymatda

s₁x₁ 

s₂ x₂ 

const
to’g’ri chiziqni

ifodalaydi. Yechimlardan tashkil topgan qavariq to’plamni hosil qilish uchun

a₁₁x₁ 

a₁₂ x₂ 

b₁, a₂₁x₁  a₂₂ x₂ 

b₂ ,
, a_m1x₁  a_m2 x₂ 


b_m , x₁  0, x₂  0
to’g’ri chiziqlar

bilan chegaralangan ko’pburchakni yasaymiz.

Faraz qilaylik, bu ko’pburchak ABCDE beshburchakdan iborat bo’lsin