22
ij
i
ij
i
ij
i
a
b
a
b
a
b
.
Teorema shartiga ko„ra
ij
i
ij
i
a
b
a
b
, demak
0
ij
i
ij
i
a
b
a
b
va demak,
0
i
b
.
Shuni isbotlash talab etilgan edi. Shunday qilib, agar ozod hadlari musbat
bo„lgan chiziqli tenglamalar sistemasini yechishda simpleks almashtirish bajarilsa,
u holda hosil qilingan bazis yechim nomanfiy bo„ladi (agar sistemaning nomanfiy
bazis yechimi mavjud bo„lsa). Aslida simpleks almashtirishni ketma – ket amalga
oshirish natijasida biz quyidagi sistemaga kelamiz.
0
0
1
0
,
0
1
0
1
1
1
0
1
,
1
1
m
n
mn
m
mn
m
m
n
n
m
m
b
x
a
x
a
x
b
x
a
x
x
a
x
Bu yerdan ma‟lumki,
n
m
x
x
,
,
1
larni nolga teng deb olib
0
0
,
,
0
0
1
m
b
b
bazis
yechimga ega bo„lamiz.
Agar hech bo„lganda bitta nomanfiy bazis cheim topilgan bo„lsa, u holda
simpleks almashtirish yordamida boshqa nomanfiy bazis yechimga o„tiladi (agar u
bor bo„lsa).
2.1-masala.
Ushbu chiziqli tenglamalar sistemasining
barcha nomanfiy
yechimlarini toping:
7
5
2
8
3
2
3
2
3
5
4
3
5
4
2
5
4
1
x
x
x
x
x
x
x
x
x
Yechish.
barcha ozod hadlarni nomanfiy holga keltiramiz.
7
5
2
8
3
2
3
2
3
5
4
3
5
4
2
5
4
1
x
x
x
x
x
x
x
x
x
Dastlabki jadvalni tuzamiz. Hal qiluvchi element sifatida 4-nchi ustundan 3
ni tanlaymiz:
2
7
;
2
8
;
3
3
min
3
3
25
2.2. Standart ko’rinishdagi masalani simpleks usulda yechish
Simpleks metodni birinchi bo„lib 1949 yilda amerikalik olim D.Dansig
tomonidan kiritilgan. Uning asosiy g„oyasi 1939 yilda sovet olimi
L.V.Kantorovich tomonidan ishlab chiqilgan.
Simpleks metod yordamida har qanday chiziqli
programmalashtirish
masalasini yechish mumkin, ya‟ni bu metod universal metod hisoblanadi. Hozirgi
paytda bu metoddan kompyuter hisoblarda foydalaniladi, ba‟zan oddiy masalalarni
qo„lda, simpleks usulni qo„llab yechish mumkin.
Simpleks metodni amalga oshirishda uchta asosy elementni o„zlashtirish
lozim:
1)
Boshlang„ich joiz bazis yechimni topish usulini aniqlash;
2)
Yaxshi yechimga o„tish (yomon bo„lmagan) qoidasini o„zlashtirish;
3)
Topilgan yechimni optimallik kriteriyasini tekshirish.
Simpleks metoddan foydalanganda chiziqli programmalashtirish masalasi
kanonik holga keltirilishi kerak, ya‟ni o„zgaruvchilarga qo„yilgan cheklov shartlari
tenglamalar ko„rinishida bo„lishi lozim.
Simpleks usulda hisoblash algoritmini misollarda ko„ramiz.
Chiziqli funksiyani maksimumini izlash
2.1-misol. Ushbu masalani simpleks usulda yeching.
max
3
2
0
,
0
21
3
5
16
2
18
3
2
1
2
1
1
2
2
1
2
1
x
x
F
x
x
x
x
x
x
x
x
Yechish.
Nomanfiy
qo„shimcha o„zgaruvchilarni kiritib, standart
ko„rinishdagi masalani kanonik ko„rinishida yozib olamiz.
Bu masalada
barcha tengsizliklar
"
"
ko„rinishda bo„lganligi uchun
yordamchi o„zgaruvchilarning barchasi “plyus” ishorada kiritiladi.
Cheklov tengsizliklarini quyidagi ko„rinishda yozamiz:
0
3
2
21
3
5
,
16
2
,
18
3
2
1
6
1
5
2
4
2
1
3
2
1
x
x
F
x
x
x
x
x
x
x
x
x
x
Boshlang„ich bazis yechimlarni topish uchun o„zgaruvchilarni ikki guruhga
ajratamiz – bazis va bazis bo„lmagan o„zgaruvchilar.
Bizning misolda
6
5
4
3
,
,
,
x
x
x
x
larni bazis o„zgaruvchi qilib olamiz, chunki bu
o„zgaruvchilar faqat bitta tenglamada ishtirok etmoqda.
Simpleks jadvalini tuzamiz.
26
2.2.1-jadval
BU
1
x
2
x
3
x
4
x
5
x
6
x
OH
3
x
1
3
1
0
0
0
18
4
x
2
1
0
1
0
0
16
5
x
0
1
0
0
1
0
5
6
x
3
0
0
0
0
1
21
x
F
-2
-3
0
0
0
0
0
BU – bazis o„zgaruvchi, OH – ozod had.
Boshlang„ich bazis yechim
21
;
5
;
16
;
18
;
0
;
0
1
X
bu yechim joiz yechim.
F
ning qiymatini oshirish uchun
1
x
va
2
x
o„zgaruvchilarning
katta
koeffitsientlarini tanlaymiz. Demak,
2
x
koeffitsienti tanlanadi. Aniqlovchi
elementni belgilaymiz.
5
;
1
5
;
1
16
;
3
18
min
2
x
5
x
ni bazisdan chiqaramiz va bazisga
2
x
ni kiritamiz.
2.2.2-jadval
BU
1
x
2
x
3
x
4
x
5
x
6
x
OH
3
x
1
0
1
0
-3
0
3
4
x
2
0
0
1
-1
0
11
2
x
0
1
0
0
1
0
5
6
x
3
0
0
0
0
1
21
F
-2
0
0
0
3
0
15
21
,
0
,
11
,
3
,
5
,
0
2
x
Aniqlovchi elementi o„rnida 1 hosil qilib,
undan boshqa shu ustundagi
barcha elementar nolga aylantiriladi. 2.2.2-jadvalning oxirgi satri, birinchi ustunda
– 2 bo„lganligi uchun, shu ustun aniqlovchi ustun bo„ladi.
3
3
21
;
;
2
11
;
1
3
min
1
x
3
x
o„zgaruvchi o„rniga
1
x
bazisga kiradi.
2.2.3-jadval
BU
1
x
2
x
3
x
4
x
5
x
6
x
OH
1
x
1
0
1
0
-3
0
3
4
x
0
0
-2
1
5
0
5
2
x
0
1
0
0
1
0
5
6
x
0
0
-3
0
9
1
12
F
0
0
2
0
-3
0
21
27
Hosil qilingan yechim ham optimal emas,
12
,
0
;
5
;
0
;
5
;
3
3
x
chunki maqsad
funksiya koeffitsientlarida bitta manfiy element – 3 bor.
Keyingi jadvalga o„tamiz,
1
9
12
;
5
;
5
5
min
5
x
bazisga
5
x
kiradi. Aniqlovchi element 5 uning o„rnida 1 hosil qilamiz va shu ustun
elementlarini (aniqlovchi elementdan boshqa) nolga aylantiramiz.
2.2.4-jadval
BU
1
x
2
x
3
x
4
x
5
x
6
x
OH
1
x
1
0
5
1
5
3
0
0
6
5
x
0
0
5
2
5
1
1
0
1
2
x
0
1
5
2
5
1
0
0
4
6
x
0
0
5
3
5
9
0
1
3
F
0
0
5
4
5
3
0
0
24
Optimallik sharti bajarildi, oxirgi satrda maqsad funksiya o„zgaruvchilari oldidagi
koeffitsientlar ichida manfiylari qolmadi. (2.2.4-jadval)
Maqsad funksiya bazis bo„lmagan o„zgaruvchilar
orqali
4
3
5
3
5
4
24
x
x
F
bog„landi. Optimal yechim
3
;
1
;
0
;
0
;
4
;
6
*
X
24
max
F
Demak, optimallik kriteriyasini umumiy holda bayon qilish mumkin. agar
masalada chiziqli funksiyaning maksimum izlanayotgan bo„lsa, chiziqli funksiya
bazis bo„lmagan o„zgaruvchilar orqali ifoda etilganda ularning koeffitsientlpri
ichida musbat elementlar, u holda bazis yechim optimal bo„ladi.
