Sh. A. Saipnazarov biznes matematika

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
.

50 

Download 3,82 Mb.