SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
33
TURISTIK KOMPANIYALAR UCHUN XARAJATLARNI
MINIMALLASHTIRISHDA MATEMATIK DASTURLASH USULLARI
Mamatova Zilolaxon Xabibulloxonovna
Farg‘ona davlat universiteti dotsent, pedagogika
fanlari bo‘yicha falsafa doktori (PhD)
E-mail: mamatova.zilolakhon@gmail.com
ORCID ID 0009-0009-9247-3510
Abdumalikov Axmadali Abdulhamid o‘g‘li
Farg‘ona Davlat Universiteti Amaliy matematika yo‘nalishi 3-kurs talabasi
E-mail: axmadali.of@gmail.com
Jo‘rayev Ahliddin Ravshanjon o‘g‘li
Farg‘ona Davlat Universiteti Amaliy matematika yo‘nalishi 3-kurs talabasi
E-mail: tdaxshat@gmail.com
https://doi.org/10.5281/zenodo.15305075
Anotatsiya:
Mazkur ilmiy tadqiqotda turistik kompaniyalar faoliyatida
xarajatlarni minimallashtirish muammosi matematik dasturlash usullari
yordamida hal etilishi ko‘rib chiqiladi. Xususan, bu maqolada turistik
xizmatlarning transport tizimiga taalluqli xarajatlarni optimallashtirishda
Transportation Problem (TP) modelidan foydalanishning samaradorligi tahlil
qilinadi. Turistik kompaniyalar uchun transport xarajatlari, ayniqsa, yirik
miqyosdagi xizmatlar, ekskursiyalar va sayohatlar tashkil etishda muhim
ahamiyatga ega bo‘lib, ularni samarali boshqarish va minimallashtirish iqtisodiy
jihatdan muhim hisoblanadi.
Transportation Problem (TP) - bu turli manbalardan talablar manzillariga
resurslarni minimal xarajatlar bilan taqsimlashni maqsad qilgan matematik
model bo‘lib, ko‘plab sohalarda, jumladan, turizm sohasida keng qo‘llaniladi. TPS
algoritmi,
ayniqsa,
transport
xizmatlarini
rejalashtirishda,
turistik
kompaniyalarning resurslarini eng samarali taqsimlashga yordam beradi.
Mazkur algoritm yordamida turistlarni manzillarga eng kam xarajat bilan
yo‘naltirish imkoniyati yaratiladi, bu esa kompaniyaning rentabelligini
oshirishga va logistika jarayonlarini optimallashtirishga xizmat qiladi.
Kalit so‘zlar
: Turistik kompaniyalar, matematik dasturlash,
Transportation Problem, xarajatlarni minimallashtirish, TPS algoritmi, logistika
optimallashtirish, transport xarajatlari, samaradorlik.
Kommivoyajyor masalasi – kombinatorik optimizatsiya sohasidagi muhim
masalalardan biri bo‘lib, uning maqsadi bir nechta shaharlarga tashrif buyurib,
minimal yo‘l uzunligi bilan boshlang‘ich nuqtaga qaytadigan eng qisqa
yo‘nalishni topishdir. Ushbu masala transport logistikasi, ishlab chiqarish
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
34
jarayonlarini optimallashtirish va elektron sxemalar loyihalash kabi sohalarda
qo‘llaniladi.
Yechish usullari:
Bruteforce (To‘liq ko‘rib chiqish),dinamik dasturlash
(Held-Karp algoritmi),ochko‘z algoritm (Greedy Algorithm),genetik algoritm,
simulyatsiyalangan tavlanish (Simulated Annealing), chiziqli dasturlash va
shaxmat bo‘lishi (Branch and Bound)
Maqsad:
Kommivoyajyor masalasining maqsadi – berilgan shaharlarga
tashrif buyurish uchun kom-mivoyajyorning eng qisqa va eng samarali yo‘lini
topishdir. Bunda, har bir shahar faqat bir marta ziyorat qilinishi kerak va oxirida
kom-mivoyajyor boshlang‘ich shaharga qaytib kelishi lozim. Masalaning asosiy
maqsadi, shaharlarga tashrif buyurishdagi masofani minimal qilish va shu orqali
vaqt
va
xarajatlarni
kamaytirishdir.
TSPni
yechishda,
maqsadni
optimallashtirish orqali, real dunyoda transport, logistika va resurslarni
boshqarish kabi sohalarda samaradorlikni oshirishdir. Shuningdek, TSPni
yechish uchun ishlab chiqilgan algoritmlar va metodlar boshqa ko‘plab
optimallashtirish masalalariga ham tatbiq etilishi mumkin.
Berilgan n ta shaharni har biriga faqat bir marta tashrif etish bilan eng qisqa
vaqt(yo‘l, xarajat) davomida aylanib chiqish sik li topilsin. Bunda sikllar soni
ko‘pi bilan
(
1)!
n
ta bo‘ladi. Bu masala minimal uzunlikdagi Gamilton siklini
topish masalasi bilan bog‘langan. Kommivoyajyor masalasini yechishda
"Tarmoqlar va chegaralar"usulini qo‘llash mumkin. Bu usul siklsiz va sirtmoq siz
bog‘langan graf, hamda jadvallar tuzish yordamida olib boriladi.
Namunaviy variant.
Jadvalni keltirish tushunchasini kiritamiz. Buning
uchun, avval jadval satrlari keltiriladi, ya’ni jadvalning har bir satr
elementlaridan shu satrning kichigi mos ravishda ayirib tashlanadi. Shundan
so‘ng jadval ustunlariga nisbatan ham xuddi shu amal bajarilib, jadval ustunlari
keltiriladi. Barcha satrlari va ustunlari keltirilgan jadval keltirilgan deb ataladi.
Jadval satr va ustunlari eng kichik elementlarining yig‘indisi h bilan belgilanib, u
jadvalning keltirish koeffitsienti deyiladi. Misol sifatida quyidagi O‘zbekiston
bo‘ylab avia sayohat jadvalini ko‘raylik:
Belgilashlarni kiritib olamiz
1.O‘zbekiston-Qozog’iston – 42 $
O‘zbekiston-Rossiya – 85 $
O‘zbekiston-Germaniya – 61 $
O‘zbekiston-Fransiya – 19 $
O‘zbekiston-Italiya – 78 $
O‘zbekiston-Turkiya – 34 $
O‘zbekiston-Amerika – 91 $
2.Qozog’iston-O‘zbekiston– 23 $
Qozog’iston-Rossiya – 73 $
Qozog’iston-Germaniya – 66 $
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
35
Qozog’iston-Fransiya – 38 $
Qozog’iston-Italiya – 98 $
Qozog’iston-Turkiya – 87 $
Qozog’iston-Amerika – 47 $
3.Rossiya-O‘zbekiston– 37 $
Rossiya-Qozog’iston – 59 $
Rossiya -Germaniya – 50 $
Rossiya -Fransiya – 27 $
Rossiya -Italiya – 63 $
Rossiya -Turkiya – 70 $
Rossiya -Amerika – 18 $
4.Germaniya-O‘zbekiston– 64 $
Germaniya -Qozog’iston – 21 $
Germaniya -Rossiya – 90 $
Germaniya-Fransiya – 53 $
Germaniya -Italiya – 88 $
Germaniya -Turkiya –49 $
Germaniya -Amerika – 35 $
5.Fransiya -O‘zbekiston– 77 $
Fransiya -Qozog’iston – 40 $
Fransiya -Rossiya – 66 $
Fransiya - Germaniya – 85 $
Fransiya -Italiya – 44 $
Fransiya -Turkiya – 92 $
Fransiya -Amerika – 25 $
6.Italiya -O‘zbekiston– 69 $
Italiya -Qozog’iston – 53 $
Italiya -Rossiya – 39 $
Italiya -Germaniya – 32 $
Italiya -Fransiya – 98 $
Italiya -Turkiya – 61 $
Italiya -Amerika – 14 $
7.Turkiya -O‘zbekiston–55 $
Turkiya -Qozog’iston – 84 $
Turkiya -Rossiya –36 $
Turkiya -Germaniya – 17 $
Turkiya -Fransiya – 29 $
Turkiya -Italiya – 76 $
Turkiya -Amerika – 62 $
8.Amerika -O‘zbekiston– 31 $
Amerika -Qozog’iston – 60 $
Amerika -Rossiya – 22 $
Amerika -Germaniya – 97 $
Amerika -Fransiya – 81 $
Amerika -Italiya – 35 $
Amerika -Turkiya – 26 $
B/S
1
2
3
4
5
6
7
8
Satr
bo‘yicha eng
kichik
1
∞
42
85
61
19
78
34
91
19
2
23
∞
73
66
38
94
87
45
23
3
37
59
∞
50
27
63
70
18
18
4
64
21
90
∞
53
88
49
35
21
5
77
40
66
85
∞
44
92
25
25
6
69
53
39
32
98
∞
61
14
14
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
36
7
55
84
36
17
29
76
∞
62
17
8
31
60
22
97
81
35
26
∞
22
1-jadval.
1-jadval satrlarini keltirish uchun uning o‘ng tarafiga mos satrning eng
kichik elementini yozib chiqamiz va satr elementlaridan uni ayirib quyidagi 2-
jadvalga ega bo‘lamiz.
2-jadval
Hosil bo‘lgan 2-jadvalning ustunlarini keltirish maqsadida jadval ostiga mos
ustunning eng kichik elementi yoziladi va ustun elementlaridan ayirib chiqiladi,
natijada quyidagi 3-jadval hosil bo‘ladi.
B/S
1
2
3
4
5
6
7
8
1
∞
23
66
42
0
59
15
72
2
0
∞
50
43
15
71
64
22
3
19
41
∞
32
9
45
52
0
4
43
0
69
∞
32
67
28
14
5
52
15
41
60
∞
19
67
0
6
55
39
25
18
84
∞
47
0
7
38
67
19
0
12
59
∞
45
8
9
38
0
75
59
13
4
∞
ustun bo‘yicha
eng kichik
element
0
0
0
0
0
13
4
0
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
37
3-jadval
3-jadval keltirilgan bo‘lib, uning har bir satr va ustunida kamida bittadan
nol element bor. Ko‘rilayotgan jadvalning keltirish koeffitsienti h quyidagi songa
teng
h=19+23+18+21+25+14+17+22+0+0+0+0+0+13+4+0=176
h1=19+23+18+21+25+14+17+22+0+0+0+0+0+13+4+0=176
Umuman, tarmoqlar va chegaralar usuli ikkita muhim bosqich dan
iboratdir:
1) tarmoqlash;
2) quyi chegaralarni aniqlash.
Masalani yechish davomida ikkala bosqich parallel ravishda olib boriladi.
Bu bosqichlarni amalga oshirish uchun, quyidagi ishlarni ketma-ket bajarish
kerak. A) boshlang‘ich jadvalni keltirish; B) keltirish koeffitsenti h ni aniqlash; C)
keltirilgan jadvalning nol elementlari darajasini aniqlash; D) bu darajalar
asosida tarmoqlashni amalga oshirish; E) tarmoqlanish natijalarini tashkil
etuvchi sikllarning quyi chegaralarini aniqlash; F) jadval o‘lchamini bittaga
kamaytirish; G) to‘la bo‘lmagan sikllar hosil bo‘lib qolishdan saqlanish; H) bu
jarayonni (2x2) jadval hosil bo‘lgunga qadar davom ettirish; I) oxirgi tarmoq
natijasiga mos siklni aniqlash; J) barcha chegara (ba holarni) solishtirish; K)
zarurat bo‘lsa, eng kam chegaraviy natijaga mos jadval tiklanib tarmoqlashni
davom ettirish.
Bu usulni qo‘llash davomida, barcha hisob-kitoblar berilgan jadval
yordamida olib borilib, uning natijalari alohida tuzilgan grafda ko‘rsatib boriladi.
Bu jarayon oxirida mukammal(eng kam xarajatli) sikl aniqlanadi.
Graf o‘zaro birlashtirilgan doirachalardan iborat bo‘lib, ular ning har biri
ma’lum bir xossali sikllar to‘plamini aniqlaydi. Bu doirachalar yoniga yozilgan
B/S
1
2
3
4
5
6
7
8
1
∞
23
66
42
0
46
11
72
2
0
∞
50
43
15
58
60
22
3
19
41
∞
32
9
32
48
0
4
43
0
69
∞
32
54
24
14
5
52
15
41
60
∞
6
63
0
6
55
39
25
18
84
∞
43
0
7
38
67
19
0
12
46
∞
45
8
9
38
0
75
59
0
0
∞
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
38
chegara-sonlar esa, shu doiraga tegishli bo‘lgan sikllarga mos xarajatlarning quyi
chegarasini bildiradi. Grafning boshlang‘ich qismi 1-rasm ko‘rinishida bo‘ladi.
Bunda birinchi boshlang‘ich doiracha barcha sikllarni o‘z ichiga olgan to‘plamni
aniqlab, ixtiyoriy sikl bo‘yicha ketadigan xarajat h sonidan kichik bo‘lmasligini
bildiradi. Yuqorida ko‘rilgan misolda h=176 edi, demak, xarajati 176 dan kichik
bo‘lgan sikl yo‘q ekan.
Darajasi eng katta bo‘lgan nol joylashgan satr va ustun lar topilib, bo‘yicha
tarmoqlanadi. Mabodo, katta darajali nollar bir nechta bo‘lsa, ularning ixtiyoriy
bittasi tanlab olinadi. Bunda, o‘ng tarafdagi doiracha i shahardan j shaharga
o‘tishni o‘z ichiga olgan barcha sikllarning to‘plamini bildiradi va u bilan
belgilanadi, chap tarafdagi doiracha esa, aksincha, i shahardan j shaharga
o‘tishni o‘z ichiga olmagan marshrutlarning to‘plamini bildiradi va u bilan
belgilanadi.
Darajasi eng kata 30 bo‘lgan nol element c
74
=0
(30)
dir, demak, tarmoqlanish grafi
1-rasm ko‘rinishida bo‘ladi.Chap doiracha yoniga eng kam xarajat keltirish
koeffitsienti h
1
=176 ga nolning eng katta darajasi 30 qo‘shilib hosil bo‘lgan 206
soni yoziladi.
'
1
( )
h
O‘ng tarafdagi doirachaga mos keluvchi xarajatlarning quyi
chegarasini aniqlash uchun 3-jadvalning 7-satri va 4-ustuni tashlab (o‘chirib)
yuboriladi (demak, jadvalning o‘lchami bittaga kamayadi). Bunda, shuni alohida
ta’kidlash lozimki, shaharlarning tartib raqamlari albatta saqlanib (yozilib)
qolishi shart,aks holda chalkashliklar kelib chiqadi. Shundan so‘ng, barcha to‘la
B/S
1
2
3
4
5
6
7
8
1
∞
23
66
42
0
(20)
46
11
72
2
0
(24)
∞
50
43
15
58
60
22
3
19
41
∞
32
9
32
48
0
(9)
4
43
0
(29)
69
∞
32
54
24
14
5
52
15
41
60
∞
6
63
0
(6)
6
55
39
25
18
84
∞
43
0
(18)
7
38
67
19
0
(30)
12
46
∞
45
8
9
38
0
(19)
75
59
0
(6)
0
(11)
∞
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
39
bo‘lmagan sikllar hosil bo‘lishi taqiqlanadi, masalani
(
i
j
i i
j
belgii-
shahardan-shaharga o‘tishni bildiradi) yo‘qotiladi, buning uchun
ji
c
element
belgisiga almashtirilib yozib qo‘yiladi,).
Yana jadvallarni tuzib ishimizni davom ettiramiz.
B/S
1
2
3
5
6
7
8
1
∞
23
66
0
46
11
72
0
2
0
∞
50
15
58
60
22
0
3
19
41
∞
9
32
48
0
0
4
43
0
69
32
54
24
14
0
5
52
15
41
∞
6
63
0
0
6
55
39
25
84
∞
43
0
0
8
9
38
0
59
0
0
∞
0
0
0
0
0
0
0
0
4-jadval.
2-rasm.
5-jadval.
(
42
)
29
0
c
24
c
'
2
2
1
176
29
205
h
h
h
B/S
1
2
3
5
6
7
8
7,4
7, 4
Barcha sikllar
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
40
2-rasmni va shunga o‘xshagan grafiklarni oxirida jamlab tuzib qo‘ysak ham bo‘ladi.
6-jadval.
3
2
3
'
176
25
201
h
h
h
(25)
83
0
c
1
∞
23
66
0
(20)
46
11
72
2
0
(24)
∞
50
15
58
60
22
3
19
41
∞
9
32
48
0
(9)
4
43
0
(29)
69
32
54
∞
14
5
52
15
41
∞
6
63
0
(6)
6
55
39
25
84
∞
43
0
(25)
8
9
38
0
(25)
59
0
(6)
0
(11)
∞
B/S
1
3
5
6
7
8
1
∞
66
0
(20)
46
11
72
0
2
0
(24)
50
15
58
60
22
0
3
19
∞
9
32
48
0
(9)
0
5
52
41
∞
6
63
0
(6)
0
6
55
25
84
∞
43
0
(25)
0
8
9
0
(25)
59
0
(6)
0
(11)
∞
0
0
0
0
0
0
0
0
B/S
1
5
6
7
8
1
∞
0
(0)
40
0
(28)
72
0
2
0
(25)
15
52
49
22
0
3
10
0
(10)
17
28
∞
0
5
52
∞
0
(17)
52
0
(0)
0
6
55
84
∞
32
0
(32)
0
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
41
7-jadval.
4
3
4
'
202
32
209
h
h
h
(32)
68
0
c
8-jadval.
'
5
4
5
202
69
271
h
h
h
(69)
56
0
c
9-jadval.
6
5
6
'
202
28
230
h
h
h
(28)
17
0
c
7
202 25
227
h
0
0
0
0
0
B/S
1
5
6
7
1
∞
0
(0)
40
0
(28)
0
2
0
(25)
15
52
49
0
3
10
0
(10)
17
28
0
5
52
∞
0
(69)
52
0
0
0
0
0
B/S
1
5
7
1
∞
0
(0)
0
(28)
0
2
0
(25)
15
49
0
3
10
0
(10)
28
0
0
0
0
B/S
1
5
2
∞
15
15
3
10
∞
10
B/S
1
5
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
42
Eng qisqa yo‘l (optimal marshrut):
1
7
4
2
5
6
8
3
1
Minimal masofa: 227 birlik.
2
∞
0
0
3
0
∞
0
Barcha sikllar
7,4
7, 4
4,2
8,3
8,3
6,8
5,6
1,7
2,5
6,8
1,7
2, 5
4,2
5,6
176
176
176
202
202
202
227
206
205
8
201
209
271
230
SOLUTION OF SOCIAL PROBLEMS IN
MANAGEMENT AND ECONOMY
International scientific-online conference
43
Xulosa. Kommivoyajyor masalasi real hayotdagi ko‘plab muammolarni
modellashtirish va optimallashtirish uchun ishlatiladigan klassik matematik
masaladir. Optimal yechimni topishning hisoblash murakkabligi tufayli,
ko‘pchilik hollarda taxminiy algoritmlar yoki heuristik yondashuvlar qo‘llaniladi.
Foydalanilgan adabiyotlar:
1.
Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial Optimization:
Algorithms and Complexity. Dover Publications.
2.
Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2006). The Traveling
Salesman Problem: A Computational Study. Princeton University Press.
3.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1985).
The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.
Wiley.
4.
Gutin, G., & Punnen, A. P. (2002). The Traveling Salesman Problem and Its
Variations. Springer.
5.
Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for
TSP Applications. Springer.
