T. M. Magrupov, B. M. Mirshaxodjayev

10.2. Simpleks usul
Tayanch yechimni topish
1.Ham m a ozod o ‘ zgaruvchilarga nol qiym ati beriladi.
(2 1 )
106

---

Bu tayanch yechim boMadi.
2. 
B a ’ zi bir o zo d o ‘ zgaruvchilam ing qiym ati m an fiy b o ‘ lganda 
tayanch yechim ni topish.
X l 
X2 ..................X s .......... X n 
Л
yi an ai
2
........... ais — ain ?i
у 7 321 
322 ................32s....... 32n b 2
y r 3rl 3r2
■3rs..... Зщ bj
Ут 3ml 3m2
(
22
)
W : ci C
2
...c s ...c n Q
(2 3 )
O zo d hadlar ichida birortasini tanlab olaylik.
Masalan: ar agar r chi qatordagi koeffitsiyentlar ichida m anfiy 
koeffitsiyen t boMmasa, bunday masala tayanch yechim ga hamda 
ch iziq li programmalash masalasi umuman yechim ga ega emas.
3. 
A g a r shu r chi qatordagi koeffitsiyentlar ichida m anfiy 
koeffitsiyentlar m avjud bo'Isa. bu koeffitsiyent turgan qator tanlab 
olinadi. Bu ustun asosiy ustun deyiladi. A s o s iy qator quyidagicha 
aniqlanadi. Buning uchun quyidagi nisbat aniqlanadi:
Bu nisbatni kichkinasi qaysi qatorga m os kelsa, shu qator 
asosiy qator hisoblanadi.
Buning 
uchun 
(1 8 ) 
chi jadvaldagi 
o x irg i 
qator 
( W )
koeffitsiyentlarini ishorasi quyidagicha bo‘ lishi mumkin.
1. Bu qator hamma elementlari musbat (c i, 
C 2 ,..., 
cs
cn )
2. B a ’ zi bir elementlari m anfiy.
O ptim al yechimni topish algoritm i.
107

---

A garda bu qator ( W ) elem entlari musbat b o is a , bu yechim
ch iziqli programmalash masalasini optimal yechim idir, bunga Q 
kirm aydi.
M isol:
1
. Birinchi bosqichda mumkin b o ‘ lgan bazis yechim topiladi.
2. Ikkinchi 
bosqichda 
esa 
bazis 
yechim ni 
optima I ligi 
tekshiriladi.
- 2 x , + x , + x 3 = 2
• x , - 2 x 2 + x 4 = 2 
x , + x 2 + x 5