Chiziqli funksiyani minimumini izlash

Chiziqli funksiyani minimumini izlash
Z
chiziqli funksiyaning minimumini izlashning ikki yo„li mavjud:
1.
Z
F
deb olib va
mzx
F
Z
min
ekanligini hisobga olib
F
funksiyaning
maksimumini izlash;
2. Har bir qadamda maqsad funksiya qiymatini chiziqli funksiya ifodasiga
kiruvchi manfiy koeffitsientli bazis bo„lmagan o„zgaruvchi hisobiga kamaytirib
borish yo„li bilan.
Buni quyidagi misolda ko„ramiz.
2.2-misol. Ushbu masalani simpleks usulda yeching.
3
,
1
0
5
6
5
2
3
3
2
5
2
3
2
1
3
2
1
3
2
1
j
x
x
x
x
x
x
x
x
x
x
j
shartlarni qanoatlantiruvchi
F
funksiya minimumini toping, ya‟ni
min
2
3
3
2
1
x
x
x
x
F
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
|