Grafik va Gomori usuli - Sh. A. Saipnazarov biznes matematika

4.2. Grafik va Gomori usuli
Aytaylik, chiziqli programmalashtirish masalasini simpleks usulda
yechganda uning optimal yechimi topilgan bo„lib, ushbu tenglamalar sistemasi
hosil qilingan, bunda
m
j
x
x
x
x
,
,
,
,
,
2
1
bazis o„zgaruvchilar bazis bo„lmagan
n
i
m
m
m
x
x
x
x
,
,
,
,
,
2
1
o„zgaruvchilar orqali ifodalangan bo„lsin, ya‟ni
,
..
..........
..........
..........
..........
..........
....
..........
..........
..........
..........
..........
,
,
1
1
1
1
2
1
1
2
2
2
1
1
1
1
1
1
n
mn
m
mm
m
m
n
in
m
im
i
i
n
n
m
m
n
n
m
m
x
x
x
x
x
x
x
x
x
x
x
x
(4.1)
bunda optimal yechim
0
,
0
,
0
,
,
,
,
,
*
2
1
m
i
.
Faraz qilaylik bunda
i
komponent butun bo„lmasin. U holda ushbu tengsizlik
0
1
1
n
in
m
im
i
x
x
(4.2)
tengsizlik (4.1) sistemaning barcha shartlarini qanoatlantirishini ko„rsatish
mumkin. (4.2) da
belgi sonning kasr qismini ifodalaydi.
a
a
a
a
a
,
sonining o„zidan katta bo„lmagan butun qismi.
46
Butun sonli chiziqli programmalashtirish masalasini yechish uchun Gomori
usulidan foydalanish algoritmi:
1. Chiziqli programmalashtirish masalasi butun sonli shartini hisobga
olmagan holda simpleks usulda yechiladi. Agar optimal yechimning barcha
komponentlari butun bo„lsa, unda masala optimal yechimga ega bo„lib, butun sonli
programmalash masalasi optimal yechimga ega bo„ladi. Agar dastlabki masala
optimal yechimga ega bo„lmasa, butun sonli programmalash masalasi ham optimal
yechimga ega bo„lmaydi.
2. Agar optimal yechimlar ichida butun bo„lmagan komponentlar bo„lsa, u
holda ularning kasr qismi. Katta bo„lgani tanlanadi va (4.2) kesim qo„llaniladi.
3. (4.2) tengsizlik nomanfiy butun yordamchi o„zgaruvchi kiritish bilan
tenglama ko„rinishga keltiriladi va uni cheklov shartlariga qo„shiladi.
0
1
1
1
n
n
in
m
im
i
x
x
x
(4.3)
4. Hosil qilingan kengaytirilgan masala simpleks metodi yordamida
yechiladi. Agar topilgan optimal reja butun sonli reja bo„lsa, u holda butun sonli
programmalashtirish masalasi yechilgan bo„ladi.
Yuqorida keltirilgan masala, Gomori usuli bilan yechtlsin. Masalaning
matematik modeli:
max
4
2
2
1
x
x
x
Z
10
3
3
19
2
4
2
1
3
2
1
x
x
x
x
x
x
0
,
0
2
1
x
x
butun
Yechish.
BU
1
x
2
x
3
x
4
x
OH
3
x
2
1
1
0
3
19
4
x
1
3
0
1
10
Z
-2
-4
0
0
0
BU
1
x
2
x
3
x
4
x
OH
3
x
3
5
0
1
3
1
3
2
x
3
1
1
0
3
1
3
10
Z
3
2
0
0
3
4
3
40
BU
1
x
2
x
3
x
4
x
OH
1
x
1
0
5
3
5
1
5
9
2
x
0
1
5
1
5
2
15
41
Z
0
0
5
2
5
6
15
218
3-qadamdagi 1-satr uchun qo„shimcha kesuvchi tenglama tuzamiz.
47
5
4
3
5
4
3
4
3
3
5
3
4
3
4
0
5
4
5
3
5
4
0
5
1
5
3
5
9
x
x
x
x
x
x
x
x
BU
1
x
2
x
3
x
4
x
5
x
OH
1
x
1
0
0
-1
1
1
2
x
0
1
0
3
2
5
1
3
3
x
0
0
1
3
4
3
5
3
4
Z
0
0
0
3
2
3
2
14
14
,
3
;
1
*
max
Z
X
4.3. Chegaraviy usulni tushunish
Chegaraviy metod – kombinator metodlardan biri hisoblanadi. Bu metodda
tartiblangan variantlar shunday tanlanadiki, bunda maqsadga tez yetkazuvchi
masalalar qaraladi, maqsaddan uzoqlashadiganlari tashlab yuboriladi.
Bu metod quyidagidan iborat masalaning joiz yechimlar to„plami qandaydir
usul yordamida qism to„plamlarga ajratiladi, xuddi shunday metod bilan yana qism
to„plamlarga ajratiladi. Bu jarayon optimal yechim topilguncha davom ettiriladi.
Aytaylik,
berilgan
masalaning
maksimumga
chimpleks
usulda
(o„zgaruvchilarni butunligi hisobga olinmagan holda) yechilgan bo„lib, har bir
butun o„zgaruvchining quyi va yuqori chegarasi ma‟lum bo„lsin
n
j
w
x
X
j
j
j
j
,
1
:
hamda
0
Z
chiziqli funksiyaning quyi chegarasi har qanday
X
rejada
0
Z
X
Z
bo„lsin. Aniqlik uchun faqat birinchi
*
1
x
komponent optimal
*
X
rejani butun sonli
shartini qanoatlantirmasin. U holda masalaning joiz yechimidan
1
*
1
*
1
*
1
x
x
x
,
soha olib tashlanadi, bunda
*
1
*
1
x
x
ning butun qismi. Natijada bu masaladan 2 ta
masala hosil bo„ladi. Dastlabki masalaga
1
*
1
*
1
1
x
x
va
1
*
1
*
1
1
w
x
x
shartlar qo„shiladi. Bu masalalardan birini ixtiyoriy tartibda yechamiz. Hosil
qilingan yechimdan masalalar ro„yxati ko„payadi yoki kamayadi. Agar bu 2 ta
masalalardan birini yechishdan hosil qilingan yechim butun sonli optimal reja
bo„lmasa, uning uchun
0
*
Z
x
Z
bo„lsa, u holda bu masala ro„yxatdan chiqariladi.
Agar
0
*
Z
x
Z
, bo„lsa u holda bu masaladan yana 2 ta masala hosil qilamiz. Agar
hosil qilingan
*
X
butun sonlilik shartini qanoatlantirsa va
0
*
Z
x
Z
bo„lsa, u
holda
0
Z
butun sonli optimal yechim sifatida qabul qilinadi. Bu jarayon ro„yxatdan
48
masalalar yo„qolguncha qadar davom etadi, ya‟ni barcha masalalar yechilmagunga
qadar.
Ushbu masalani yechamiz.
max
3
,
,
4
0
,
5
0
,
6
2
,
18
3
4
2
1
2
1
2
1
2
1
2
1
x
x
Z
бутун
x
x
x
x
x
x
x
x
Yechish.
Chiziqli funksiyaning quyi chegarasi sifatida
0
,
0
nuqtani olamiz,
uning qiymati bu nuqtada
0
0
;
0
0
Z
Z
.
1-qadam.
Berilgan masalani simpleks usulda yechib
4
;
5
,
0
;
5
,
1
;
0
;
0
;
5
,
4
*
1
X
da
13
max
Z
ni hosil qilamiz.
Ko„rinib turibdiki,
*
1
x
komponent kasr sondan iborat, u holda yechimlar
sohasidan
*
1
x
kasrli optimal qiymat yo„qotiladi, ya‟ni
5
4
1
x
. Shuning uchun
berilgan dastlabki masala 2 va 3 masalalarga bo„linadi.
masala 2
4
0
4
0
,
6
2
,
18
3
4
2
1
2
1
2
1
x
x
x
x
x
x
2
1
,
x
x
butun sonlar
max
3
2
1
x
x
Z
masala 3
4
0
5
5
,
6
2
,
18
3
4
2
1
2
1
2
1
x
x
x
x
x
x
2
1
,
x
x
butun sonlar
max
3
2
1
x
x
Z
Masalalar ro„yxati: 2 va 3. Chiziqli funksiyaning quyi chegarasi o„zgarmadi
0
0
Z
.
2-qadam.
Ro„yxatdagi masalalardan birini masalan, 3 ni simpleks usulda
yechamiz. Cheklov shartlari umumiy qismga ega emasligini aniqlaymiz.
3-qadam.
2 masalani simpleks usulda yechamiz va
3
10
;
0
;
3
2
;
0
;
3
2
;
4
*
2
x
da
3
2
4
max
Z
ni hosil qilamiz.
;
0
3
2
4
0
*
3
Z
x
Z
ammo hali ham
0
0
Z
yoki
3
x
reja butun sonli emas,
chunki
*
2
x
- kasr son, yechimlar sohasidan
1
0
2
x
chiziqni yo„qotamiz va 2
masalani ikkita 4 va 5 masalaga ajratamiz.
49
masala 4
0
0
4
0
,
6
2
,
18
3
4
2
1
2
1
2
1
x
x
x
x
x
x
2
1
,
x
x
butun sonlar
max
3
2
1
x
x
Z
masala 3
4
1
4
0
,
6
2
,
18
3
4
2
1
2
1
2
1
x
x
x
x
x
x
2
1
,
x
x
butun sonlar
max
3
2
1
x
x
Z
Masalalar ro„yxati: 4 va 5
0
0
Z
.
4-qadam.
4 masalani simpleks usulda yechamiz.
0
;
0
;
2
;
2
;
0
;
4
*
4
x
da
12
max
Z
hosil qilamiz.
Masalani
ro„yxatdan chiqaramiz, ammo
0
Z
ni
almashtiramiz
*
4
*
4
0
,
12
x
x
Z
Z
butun sonli.
5-qadam.
5 masalani simpleks usulda yechamiz.
3
,
0
;
25
,
0
;
25
,
0
;
0
;
1
;
75
,
3
*
5
x
da
25
,
12
max
Z
ni hosil qilamiz.
0
Z
o„zgarmayapti, ya‟ni
*
5
0
,
12
x
Z
butun sonli
emas,
*
1
x
kasr son, yechimlar sohasidan
4
3
1
x
chiziqni yo„qotamiz va 5
masalani 6 va 7 masalalarga bo„lamiz.
masala 6
4
1
3
0
,
6
2
,
18
3
4
2
1
2
1
2
1
x
x
x
x
x
x
2
1
,
x
x
butun sonlar
max
3
2
1
x
x
Z
masala 7
4
1
4
4
,
6
2
,
18
3
4
2
1
2
1
2
1
x
x
x
x
x
x
2
1
,
x
x
butun sonlar
max
3
2
1
x
x
Z
masalalar ro„yxati 6 va 7.
12
0
Z
.
6-qadam.
Ro„yxatdagi masalalardan biri masalan, 7 masalani simpleks
metod yordamida yechamiz.
Masalaning cheklov sharti umumiy qismga ega emas.
7-qadam.
6
masalani
simpleks
metod
yordamida
yechamiz.
5
,
2
;
5
,
0
;
0
;
0
;
5
;
1
;
5
,
1
,
3
*
6
x
da bunday holda masalani ro„yxatdan chiqaramiz.
Shunday qilib, ro„yxat oxirgi yetdi va dastlabki masalaning butun sonli
optimal yechimi
0
;
0
;
2
;
2
;
0
,
4
*
4
*
x
x
da
12
max
Z
.
|