Chiziqli funksiyani minimumini izlash

28 
Yechish. 
Standart masalani kanonik ko„rinishga keltiramiz. 


0
2
3
6
,
1
0
5
6
5
2
3
3
2
5
2
3
2
1
6
3
2
1
5
3
2
1
4
3
2
1



















x
x
x
F
j
x
x
x
x
x
x
x
x
x
x
x
x
x
j
Simpleks jadvalni tuzamiz. 
BU 
1
x
2
x
3
x
4
x
5
x
6
x
OH 
4
x
-1 
-1 
-2 
1 
0 
0 
5 
5
x
2 
-3 
1 
0 
1 
0 
3 
6
x
2 
-5 
0 
0 
0 
1 
5 
F
 
1 
-3 
-2 
0 
0 
0 
0 
BU 
1
x
2
x
3
x
4
x
5
x
6
x
OH 
4
x
0 
2
5

2
3

1 
2
1

0 
2
13

1
x
1 
2
3

2
1
0 
2
1
0 
2
3
6
x
0 
-2 
5 
0 
-1 
1 
2 
F
 
0 
2
3

2
5

0 
2
5

0 
2
3

BU – bazis o„zgaruvchilar 
OH – ozod hadlar 
Simpleks jadvaldan foydalanib masalaning optimal yechimini aniqlaymiz. 


 
2
3
*
min
2
,
0
,
2
13
,
0
,
0
,
2
3
*



X
F
X
Minimum masalasini izlashda optimallik kriteriyasini bayon qilamiz: 
Agar maqsad funksiya ifodasida bazis bo„lmagan o„zgaruvchilar oldidagi 
koeffitsientlar ichida manfiy bo„lmaganlari bo„lmasa, yechim optimal bo„ladi. 
Bizning misolda 
5
3
2
2
5
2
5
2
3
2
3
x
x
x
F





. 
Simpleks metod algoritmi 
1. Yordamchi o„zgaruvchilarni kiritib chiziqli tenglamalar sistemasini 
kengaytirilgan sistema ko„rinishida yozib olamiz: 
0
,
,
,
2
2
1
1
2
2
1
1
2
2
2
2
22
1
21
1
1
1
2
12
1
11























n
n
m
n
m
n
mn
m
m
n
n
n
n
n
n
x
c
x
c
x
c
F
b
x
x
a
x
a
x
a
b
x
x
a
x
a
x
a
b
x
x
a
x
a
x
a




Bu yerda yordamchi o„zgaruvchilar ishorasi ozod hadlar ishorasi bilan bir xil 
bo„ladi, aks holda sun‟iy bazis usulidan foydalaniladi. 
2. Kengaytirilgan sistemani dastlabki simpleks jadvaliga joylashtiramiz. 
Jadvalning oxirgi satrida maqsad funksiya koeffitsientlari joylashtirilgan. Masalani 

29 
optimal yechimini, masalan maksimumini topishda, optimallik kriteriyasini 
bajarilishini tekshiramiz, agar jadvalning oxirgi satrida manfiy koeffitsientlar 
bo„lmasa, u holda yechim optimal bo„lib, uning qiymati jadvalning oxirgi ustuni va 
oxirgi satri kesishgan joyda bo„ladi. 
3. Agar optimallik kriteriyasi bajarilmasa, u holda oxirgi satrdagi manfiy 
koeffitsientni modul bo„yicha eng kattash hal qiluvchi ustun 
 S 
ni aniqlaydi. 
Har bir satr uchun baholash chegaralarini tuzamiz: 
1)
agar 
i
b
va 
is
a
turli ishorali bo„lsa, 

; 
2)
agar 
0

i
b
va 
0

is
a
bo„lsa, 

; 
3)
agar 
0

is
a
bo„lsa, 

; 
4)
agar 
0

i
b
va 
0

is
a
bo„lsa, 0; 
5)
agar 
0
i
a
va 
is
a
bir xil ishoraga ega bo„lsa, 
.
is
i
a
b






is
i
i
a
b
min
ni aniqlaymiz. Agar chekli minimum bo„lmasa, u holda chekli minimum 
bo„lmasa, u holda chekli optimumga ega bo„lmaydi 




max
F
. Agar minimum 
chekli bo„lsa, u holda 
 q
satrni tanlaymiz va uni ham hal qiluvchi satr deb ataymiz. 
Hal qiluvchi ustun va hal qiluvchi satr kesishmasida 
qs
a
element hal qiluvchi 
element bo„ladi. 
4. Navbatdagi jadvalga quyidagi qoida bo„yicha o„tamiz: chap ustunda yangi 
bazisni kiritamiz: 
a) bazis o„zgaruvchi 
q
x
o„rniga 
s
x
ni kiritamiz; 
b) bazis o„zgaruvchiga mos ustunlarda nollar va 1 qo„yamiz. O„zining 
qarshisida 1, boshqa o„zgaruvchilar qarshisida nollar qo„yiladi. 
v) 
q 
nomerli yangi satrni hal qiluvchi 
qs
a
elementga bo„lish yo„li bilan 
aniqlaymiz.
g) qolgan barcha 
ij
a
elementlarni to„g„ri to„rtburchak qoidasiga ko„ra 
hisoblaymiz:
qs
qj
is
ij
ij
a
a
a
a
a



_
_
_
_
_
____
is
ij
a
a
qs
q
is
i
i
a
b
a
b
b



_
_
_
_
_
____
qs
qj
a
a
va shu yo„sinda algoritmga o„tamiz. 
2.3. Suniy bazis usuli 
Kanonik holga keltirilgan chiziqli programmalashtirish masalasining 
o„zgaruvchilariga qo„yilgan cheklovlar sistemasining boshlang„ich yechimi joiz 
bo„lmasa, bunday holda masalani simpleks jadval yordamida yechganda 
M 
– 

30 
metod yoki sun‟iy bazis usulidan foydalanish qo„lay bo„ladi. Bu metodni bayon 
qilamiz. 
Bazis yechimda manfiy yechim beradigan har bir tenglamaga nomanfiy 
sun‟iy 
k
u
u
u
,
,
,
2
1

o„zgaruvchilarni ozod hadlar qanday ishorada bo„lsa xuddi 
shunday ishorada kiritamiz. Yangi chiziqli 
 


k
u
u
M
F
x
f





1
funksiyani 
kiritamiz, bunday 
M 
– ixtiyoriy katta son va uning maksimumini izlaymiz (1-
masala). 


k
u
u
M



1
ifodani 
M 
– funksiya deb yuritamiz. Quyidagi teorema 
o„rinli (isbotini keltirmaymiz).
1. Agar 
f 
–masalaning optimal yechimida barcha sun‟iy o„zgaruvchilar nolga 
teng bo„lsa, u holda unga mos boshqa o„zgaruvchilar dastlabki masalaning optimal 
yechimini beradi 
,
(
max
max
F
f

agar 
)
0
2
1




k
u
u
u

, ya‟ni 
M 
–funksiyaning 
minimumi 0 ga teng. 
2. Agar 
f 
masalaning optimal yechimida hech bo„lmaganda bitta sun‟iy 
o„zgaruvchi noldan farqli bo„lsa, u holda dastlabki masalaning cheklovlar sistemasi 
ham joyni bo„lmaydi. 
3. Agar 


max
f
bo„lsa, u holda dastlabki masala yechimga ega emas, yo 


max
F
, yoki masalaning sharti ziddiyatga ega bo„ladi.
Teorema shartidan kelib chiqadiki, dastlab 
M 
– funksiyaning minimumi 
topiladi. Agar u nolga teng bo„lsa va barcha sun‟iy o„zgaruvchilar nolga aylansa, u 
holda bu o„zgaruvchilar tashlab yuboriladi va joiz bazis yechimlar hosil bo„ladi. 
Hosil bo„lgan masalani optimal yechimi topiladi. Amaliyotda 
M 
–funksiyani 
minimumi emas, balki 


М

funksiyaning maksimumi topiladi. 
2.3-masala.
Simpleks jadvalidan foydalanib sun‟iy bazis metodi yordamida 
ushbu masalani yeching.
min
20
7
0
,
0
3
5
2
2
2
1
2
1
2
1
2
1









x
x
F
x
x
x
x
x
x
Yechish. 
Dastlab standart ko„rinishidagi masalani kanonik ko„rinishga 
keltiramiz. 
0
,
0
3
5
2
2
2
1
4
2
1
3
2
1








x
x
x
x
x
x
x
x
Yangi kiritilgan o„zgaruvchi 
3
x
va 
4
x
lar bazis o„zgaruvchi bo„lolmaydi. 
Sun‟iy bazis o„zgaruvchilarni kiritamiz. 


min
20
7
0
,
0
,
4
,
1
,
0
3
5
2
2
2
1
2
1
2
1
2
4
2
1
1
3
2
1

















u
u
M
x
x
f
u
u
j
x
u
x
x
x
u
x
x
x
j
Birinchi simpleks jadvalni tuzamiz. (2.4-jadval) 

31 
2.3.1-jadval 
BU 
1
x
2
x
3
x
4
x
1
u
2
u
OH 
1
u
1 
2 
-1 
0 
1 
0 
2 
2
u
1 
5 
0 
-1 
0 
1 
3 
F 
-7 
-20 
0 
0 
0 
0 
0 
M 
-2 
-7 
1 
1 
-1 
-1 
-5 
Oxirgi qator, bu 


M

funksiya, ya‟ni 


2
1
u
u
M


funksiya. Bu qatorni 
to„ldirish uchun 
1
u
va 
2
u
qatorlarni (-1) ga ko„paytirib ustun bo„yicha ularni 
qo„shamiz. 


M

funksiyani maksimumini izlashda optimallik kriteriyasini 
bajarilishini tekshirish maqsadida oxirgi qatorning manfiy elementlari ichida eng 
kichigini tanlaymiz, bu ikkinchi ustunda; demak, u hal qiluvchi element 5 bo„ladi. 
Sun‟iy bazis o„zgaruvchi 
2
u
ni keyingi jadvalga kiritmaymiz. Yangi 2.5-jadvalni 
tuzamiz. 
2.3.2-jadval 
BU 
1
x
2
x
3
x
4
x
1
u
OH 
1
u
3/5 
0 
-1 
2/5 
1 
4/5 
2
x
1/5 
1 
0 
-1/5 
0 
3/5 
F 
-3 
0 
0 
-4 
0 
12 
M 
-3/5 
0 
-1 
-2/5 
-1 
-4/5 
2.3.3-jadval 
BU 
1
x
2
x
3
x
4
x
OH 
1
x
1 
0 
-5/3 
2/3 
4/3 
2
x
0 
1 
1/3 
-1/3 
1/3 
F 
0 
0 
-5 
-2 
16 
M 
0 
0 
0 
0 
0 
Oxirgi qator shuni ko„rsatadiki, optimallik kriteriyasi bajariladi, 


0
max


M
, demak, 
0
min

M
, 
F 
funksiya uchun ham optimallik kriteriyasi 
bajarildi. 
16
0
;
0
;
3
1
;
3
/
4
*
min








F
X
. 
Agar 
0
min

M
bo„lib, 
F 
funksiya uchun optimallik kriteriyasi bajarilmasa, 
M
qatorni jadvaldan chiqarib tashlaymiz va masalani yechishni oxiriga yetkazib 
qo„yamiz. 
2.4-masala.
max
2
3
3
1
2
1
5
1
4
2
1
3
2
1













x
x
F
x
x
x
x
x
x
x
x

Download 3,82 Mb.