Ўзбeкистон республикаси олий ва ўрта махсус таълим вазирлиги

1.Chiziqli programmalashtirish masalasini analitik yechish usuli (simpleks usul)

Dastlab berilgan chiziqli programmalashtirish masalasining chegaraviy shartlarida m ta o`zaro chiziqli bog`liq bo`lmagan birlik vektorlar mavjud deb faraz qilamiz. Umumiylikni buzmagan holda bu

vektorlar birinchi m ta
P₁ , P₂ ,..., P_m
vektorlardan iborat deylik. U holda

masala quyidagi ko`rinishda bo`ladi:

x₁  a_1,m1 x_m1  ... a_1n x_n  b₁ ,
x₂  a_2,m1 x_m1  ...  a_{2 n} x_n  b₂ , (2.5.1)
.............................................
x_m  a_m,m1 x_m1  ...  a_mn x_n  b_m ,

x _j  0 ,


j  1, n , (2.5.2)

^ymin
 c₁ x₂  c₂ x₂  ...  c_n x_n . (2.5.3)

(2.5.1) sistemani vektor ko’rinishda yozamiz:
P₁x₁  P₂ x₂ ...  P_m x_m  P_m1x_m1 ...  P_n x_n  P₀

(2.5.4)

P₁ , P₂ ,..., P_m
vektorlar n o`lchovli vektor fazodagi o`zaro chiziqli

bog`liq bo`lmagan birlik vektorlardan iborat bo`lib, bu fazoning bazisini

tashkil qiladi. (2.5.1) da
x₁ , x₂ ,..., x_m
o`zgaruvchilarni bazis o`zgaruvchilar,

x_m1 , x_m2 ,..., x_n
o`zgaruvchilarni esa bazis bo`lmagan (ozod) o`zgaruvchilar

deb qabul qilib, bazis bo`lmagan o`zgaruvchilarni nolga tenglaymiz. Natijada:

X₀  (x₁  b₁ , x₂  b₂ ,..., x_m  b_m , x_m1  0,..., x_n  0)
boshlang`ich yechimni hosil kilamiz. (5) yechimga quyidagi
P₁x₁  P₂ x₂  ...  P_n x_n  P₀
(2.5.5)

(2.5.6)

yoyilma mos keladi. Bu yoyilmadagi
P₁ , P₂ ,..., P_m
vektorlar o`zaro chiziqli

bog`liq bo`lmagan vektorlar bo`lganligi sababli, topilgan boshlang`ich (2.5.5) yechim tayanch yechim bo`ladi.
Endi boshlang`ich yechimdan foydalanib, yangi tayanch yechimni

topish mumkinligini ko`rsatamiz.
P<sub>1</sub> , P<sub>2</sub> , ... , P<sub>m</sub>
vektorlar n o`lchovli vektor

fazoning bazisini tashkil qilgani uchun
P₁ , P₂ ,..., P_m
vektorlarning

ixtiyoriysini P_j bazis vektorlar orqali faqat bir xil yoyilmasini topish
mumkin, ya’ni:

j  1, n
uchun
P_j  P₁x_{1 j}  P₂ x_{2 j} ... P_m x_mj
(2.5.7)

Faraz qilaylik, bazisga kirmagan birorta vektor, masalan
^Pm1
ning

yoyilmasidagi koeffitsientlardan kamida bittasi (masalan,
^x1,m1
) noldan

farqli bo`lsin:
^Pm1 ^{ P}1 ^x1,m1 ^{ P}2 ^x2,m1 ^{ ...  P}m ^xm,m1
(2.5.8)

Ixtiyoriy >0 ( - hozircha noma’lum son) ni olib, (2.5.8) tenglikning ikki tomonini unga ko`paytirib, hosil bo`lgan natijani (2.5.6) dan ayiramiz. Natijada quyidagi tenglikka ega bulamiz:
^{P1(x1  x1,m1)  P2 (x2  x2,m1)  ...  Pm (xm  xm,m1)   Pm1  P0} (2.5.9)

Agar
x₁  x_1,m1, x₂  x_2,m1 ,..., x_m  x_m,m1 , 
sonlarning har biri nomanfiy

bo`lsa,
X ^  (x₁  x_1,m1, x₂  x_2,m1 ,..., x_m  x_m,m1 ,
 , 0, 0, ..., 0)
vektor yechim

bo`ladi. X dan farq qiluvchi X <sup></sup> yechim qidirilayotgani uchun  ning faqat
musbat qiymatlari qaraladi. Shuning uchun <sup>xi,m1</sup> >0 bo`lgan
komponentalarni ko`ramiz. Demak, shunday ^ >0 topishimiz kerakki,

hamma i lar uchun bajarilsin.
^x_i,m1 >0 , bo`lganda
x_i  x_i,m1  0
tengsizlik

Bunlardan, 0< ^ 
tengsizlik hosil bo` ladi.
x_i
^xi,i1

X ^ yechim
^xi,m1
>0 tengsizlik qanoatlantiriladigan  ( 0< ^  min ^xi )
x

i,i1
uchun yechimdir. Lekin tayanch yechim o`z ichiga m+1 ta komponentlarni olmaydi, shuning uchun X ^ yechimdagi kamida bitta komponentani nolga aylantirish kerak. Faraz qilaylik,

  
 min ^xi  ^xk

bajarilsin.

^{0 i} x x
i,m1 k ,m1
Bu holda X ^ yechimning k komponentasi x_k  x_{k ,m1} =0 bo`ladi.  ning
qiymatini (1.5.9) ga qo`yib quyidagi yoyilmani hosil qilamiz:
^P1 ^(x1 ^0 ^x1,m1 ^{)  P}2 ^(x2 ^0 ^x2, m1 ^{) } ... ^{ P}k 1 ^(xk 1 ^{ }0 ^xk 1,m1 ^{)  P}k 1 ^(xk 1 ^{ }0 ^xk 1,m1 ^{) }
...  P_m (x_m ₀ x_m,m1 )  P₀ .
Bu yoyilmaga
X ^  (x₁ ₀ x_1,m1, x₂ ₀ x_2,m1 ,..., x_{k 1} ₀ x_{k 1,m1} , x_{k 1} ₀ x_{k 1,m1} ,..., x_m ₀ x_m,m1 ,₀ , 0, 0, ..., 0)

yechim mos keladi. Demak, yangi yechimning komponentalari quyidagicha aniqlanar ekan:

^xi^{  x}i ^0 ^xi,m1 ^,

x_k^  0, x_m^ _2  ...  x_n^  0
^xm^ 1 ^{ }0
(2.5.10)

Bundan keyingi tayanch yechimni hosil qilish uchun bazisga

kirmagan ixtiyoriy vektorning
P₁ , P₂ ,..., P_m
bazis vektorlar orqali yoyilmasini

aniqlash hamda shunday   sonni topish kerakki, uning yordamida yangi vektor bazisga kirsin va eski bazis vektorlardan birortasi bazisdan chiqsin. Shunday qilib, yangi tayanch yechimlarni hosil qilish jarayoni bazisga kiritiladigan va bazisdan chiqariladigan vektorni tanlashdan iboratdir. Bazisga kiritiladigan vektorni tanlash kriteriysi simpleks usulning asosiy
elementlaridan biri hisoblanadi. Agar bazisga kiritilayotgan
^Pm1

vektorning yoyilmasida barcha
^xi,m1 ^{0 bo`lsa, (2.5.9) yoyilmadagi}

birorta vektorni bazisdan chikaruvchi  0 ni topib bo’lmaydi. Bu holda X ^

yechim m+1 musbat komponentalarni o`z ichiga oladi.
P₁ , P₂ ,..., P_{m ,}
^Pm1

vektorlar sistemasi esa o`zaro chiziqli bog`liq bo`lib, qavariq ko`pburchakning chetki nuqtasini emas, balki ichki nuqtasini ifodalaydi. Bu nuqtada esa chiziqli funksiya o`zining minimum qiymatiga erisholmaydi. Bu holda chiziqli funksiya quyidan chegaralanmagan bo`ladi.

Optimallik kriteriysi. Optimal yechimni topish

Quyidagi ko`rinishda berilgan chiziqli programmalashtirish masalasining

x₁  a_1,m1 x_m1  ...  a_1n x_n  b₁ ,
x₂  a_2,m1 x_m1  ...  a_2n x_n  b₂ ,
.............................................
x_m  a_m,m1 x_m1  ...  a_mn x_n  b_m ,
(2.5.11)

x _j  0 ,


j  1, n ,

y_min  c₁ x₂  c₂ x₂  ...  c_n x_n
yechimlari mavjud va ular xosmas deb faraz qilamiz, ya’ni barcha b_i>0,
i  1, m . Masalaning
X  (x₁ , x₂ ,..., x_m ) (2.5.12)
tayanch yechimi va unga mos keluvchi o`zaro chiziqli bog`liq bo`lmagan

P₁ , P₂ ,..., P_m
vektorlar sistemasi ma’lum bo`lsin. U holda
P₁x₁  P₂ x₂  ...  P_n x_n  P₀

(2.5.13)

va
y₀  c₁x₁  c₂ x₂ ...  c_n x_n .

(2.5.14)

Bu yerda y₀ - chiziqli funksiyaning X tayanch yechimdagi qiymati,

x_i  0
va c_j


j  1, n

• 
  chiziqli funksiyaning koeffisientlari.
  

P₁ , P₂ ,..., P_m
vektorlar o`zaro chiziqli bog`liq bo`lmagan vektorlar

bo`lganligi sababli ixtiyoriy bazis bo`lmagan orqali faqat bitta yoyilmasini topish mumkin:
P_j vektorning bu vektorlar

x_{1 j} P₁  x_{2 j} P₂ ...  x_mj P_m  P_j ,
Bu vektorga chiziqli funksiyaning
c₁x_{1 j}  c₂ x_{2 j} ...  c_mx_mj  y_j ,


j  1, n
(2.5.16)

qiymati mos keladi. P_j vektorga mos keluvchi chiziqli funksiyaning
koeffitsientini ^{c j} bilan belgilaymiz.
j  1, n.
(2.5.15)

ChPM yechimlarining shunday to`plamini tuzish mumkinki, ularning

har biri uchun tengsizlik o`rinlidir.
y  y₀
(y – ChPM maqsad funksiyasining qiymati)

1. 
   hol. y-sonlarining quyi chegarasi cheklangan bo`lsa, shunday yangi
   

yechim topish mumkinki, u o`zidan oldingisiga qaraganda kichik qiymatga ega bo`ladi.

2. 
   hol. y - sonlarining quyi chegarasi cheksiz bo`lsa, shunday yangi yechim topilishi mumkinki, uning koordinatalari m+1 ta musbat sonlardan tashkil topib, qiymati har qancha kichik bo`lishi mumkin.
   

Yuqorida keltirilganlarni isbotsiz qabul qilamiz.
Berilgan boshlang`ich yechimdan boshlab tayanch yechimlar ketma- ketligini hosil qilib, jarayonni optimal yechim topilguncha davom ettirish mumkin. Bu jarayon simpleks usuldan iborat. Endi simpleks usulning algoritmi bilan tanishaylik.
Faraz qilaylik: 1) m ta chiziqli bog`liqsiz vektorlar tanlanganki, ular biror tayanch yechimning bazislari bo`lsin; 2) masalaning chegaraviy shartlari m - nchi tartibli birlik matritsaga ega bo`lsin.
Birinchi hol uchun m ta chiziqli bog`liqsiz vektorlar - P₁ , P₂ ,..., P_m va

masalaning boshlang`ich tayanch yechimi -
X  (x<sub>1</sub> , x<sub>2</sub> ,..., x<sub>m</sub> )
bo`lsin. Bu

vektorlardan tashkil topgan ( P₁ , P₂ ,..., P_m ) matritsani B bilan belgilaymiz. U
holda BX  P₀ .
Bundan: X=B^-1P₀
va

j j
^{X  B 1P} , x  0
i

kelib chiqadi. Bu yerda
X  (x₁ , x₂ ,..., x_m ) , ( x_i  0 ) va
X _j  (x_{1 j} , x_{2 j} ,..., x_mj ) -

vektor ustunlar. Simpleks jarayonni boshlashdan avval masalaning vektorlarini quyidagidek guruhlaymiz:
(R₀| P₁, P₂,...,P_m | P_m+1,...,P_n)