Yuk oqimlarini marshrutlashtirishni chiziqli programmalashtirishning umumiy masalasiga keltirish Yuqorida biz marshrutlashtirishni transport masalasiga keltirib yechish metodlarini ko‘rib chiqdik. Bu metodlarning asosiy kamchiliklari marshrut tuzishda yuk tashish praktikasi talabalardan chiqadigan cheklashlarni xisobga olib bo‘lmasligi, bu jarayon butunlay avtomatlashtirish borasidagi qiyinchiliklar va buning natijasida hisob-kitoblarni ko‘lda olib borishga extiyoj tug‘ilishi xisoblanadi.
Marshrutlashtirish chiziqli programmalashtirishning umumiy masalasi sifatida qaralganda, bu kamchiliklar bir muncha kamayadi. Chizikli programmalashtirish metodini qo‘llab, marshrutlashtirish masalasi bir xil ko‘rinishda qo‘yilishi mumkin.
Masalani qo‘yilishi va matematik modeli Aytaylik, bizga Ai yuk jo‘natuvchi va Bj yuk oluvchilar o‘rtasidagi yuk tashish rejasi {Xij.} berilgan Ular o‘rtasidagi yukli qatnovlar sonini v bilan belgilaymiz. xar bir yuk oqimi punktlararo but yurish yo‘llarining matritsasi || Cij || berilgan. Xar bir tuziladigan marshrutni S bilan va praktika talablariga javob beradigan xamma marshrutlar to‘plamini Nbelgilaymiz, Bunda xar bir S marshrutlarapo bog‘langan Aiva Bj punktlar ketma-ketligidan iborat buladi. Kuyidagi kattaliklar berilgan:
ys- xar bir S marshrutda tashiladigan yuk miqdori yoki kerak bo‘lgan avtomobil qatnovlar soni;
dts - xar bir marshrutda 1 t yuk tashilganda yoki 1 avtomobil qatnovi bajarilganda Smarshrutning i liniyasida tashiladigan yuk miqdorini ko‘rsatadigan koeffitsiyent;
cij- xar bir Smarshrutda ys o‘zining bir birlik qiymatiga ega bo‘lganida bosib o‘tiladigan yuksiz yo‘l uzunligi.
Masalani matematik modeli quyidagicha yoziladi:
xar bir S marshrutda ys-ning shunday musbat qiymatlarini topish kerakki,
(10.19)
bunda xar bir liniyadagi yuk tashish rejasi bajarilsin
(bu yerda Mt - t - liniyalarni uz ichiga oladigan marshrutlar to‘plami) va hamma marshrutlardagi yuksiz yo‘llar yig‘indisi minimal bo‘lsin.
marshrutlashtirishni chiziqli programmalashtirishning umumiy masalasiga keltirib yechish metodikasini oldingi paragrfda keltirgan misolimizda ko‘rib chiqaylik. Aytaylik. yuk tashish rejasi x1 = 1300t: x12 = 400 t; x23 = 600 t; x34 = 550 t; x45 = 700 t; x56 = 500 t; x67 = 300 t bo‘lsin. Bunda bajarilishi lozim bo‘lgan yuk oqimlari xt kuyidagicha:
х 1 = х11 = 1300 т; хг = х12 = 400 т. Va hokazo x7 = х57 = 300 т.
№
S
Звенолар сони
Маршрут схемаси
Юксиз йўл узунлиги
1
1
X1(X11)
20
2
1
X2 (Х12)
30
3
1
Х3 (Х23)
30
4
1
Х4 (Х34)
30
5
1
х5 (Х45)
57
6
1
Х6 (Х46)
35
7
1
х7(х57)
47
8
2
X1-X5 (Х11-Х45)
15+37=52
9
2
Х4-Х5 (Х34-Х45)
17+10=27
10
2
Х1-Х6 (Х11-Х46)
15+10=25
11
2
Х2-Х3 (X12-X23)
1
12
3
Х1-Х2-Х3 (Х11-Х45-Х23)
15+40+10—65
Masalani yechish uchun avvalo, yuk tashish praktikasi talablariga javob beradigan marshrutlar (bu marshrutlarni biz mumkin bo‘lgan marshrutlar deymiz) variantlariga ega bo‘lishimiz kerak. Aytaylik, hamma yuklarni 1 zvenoli mayatnik marshrutlarda, 2 va 3 zvenoli marshrutlarda tashish mumkin. xar bir variantdagi marshrutga maʼlum yuksiz yo‘l uzunligi to‘g‘ri keladi. Mumkin bo‘lgan marshrut variantlari va ularga to‘g‘ri keladigan yuksiz yo‘l uzunliklari kuyidagi jadvalda berilgan.
Agar marshrut 2 yoki undan ortiq zvenoli bo‘lsa, uni aylanma marshrut deymiz. Aylanma marshrutlar uchun yuksiz yo‘l uzunligi xar bir yukli qatnovdan keyingi yuksiz yo‘llar uzunliklari yig‘indisi tarzda topiladi. Masalan, S=8 marshrut uchun C/s = C8 = C14 + C51 = 15+37=52 km, S=9 marshrut uchun esa – C0 = S44 + S53 = 17+10=27 km va shunga o‘xshash.
Endi baʼzi bir belgilashlar kiritamiz:
Y1 -1 - chi marshrutda (S = 1), y2 -2-chi marshrutda va hokazo, . . . .y11—11 — chi marshrutda tashiladigan yuk miqdorlari bo‘lsin. αts koeffitsiyentining qiymatlarini quyidagi 10.15- jadvalda keltiramiz.
10.15-жадвал
αts — кийматлари
S t
1
2
3
4
5
6
7
8
9
10
11
12
1
1
0
0
0
0
0
0
1
0
1
0
1
2
0
1
0
0
0
0
0
0
0
0
1
0
3
0
0
1
0
0
0
0
0
0
0
1
1
4
0
0
0
1
0
0
0
0
1
0
0
0
5
0
0
0
0
1
0
0
1
1
0
0
0
6
0
0
0
0
0
1
0
0
0
1
0
1
7
0
0
0
0
0
0
1
0
0
0
0
0
αts koeffitsiyentlarining tablitsada keltirilgan qiymatlari quyidagi maʼnoga ega. Agar tablitsaning biror t va s qiymatlariga moys katagida 1 bo‘lsa, bu t yuk 8.15-jadvalga muvofiq va s marshrutda tashilishi mumkinligi, agar 0 bo‘lsa, mumkin emasligini ko‘rsatadi. Masalan, t=1 yuk 1-chi; 8- chi; va 10-chi marshrutlarda tashilishi mumkin. Misolimizning matematik modelini yozamiz:
o‘zgaruvchining manfiy bo‘la olmasligi sharti
berilgan yuk tashish xajmlarining bajarilishi lozimligi
umumiy yuksiz yo‘l uzunligining yoki yo‘qotiladigan (yuksiz yurish hisobiga) transport ishining minimal bo‘lish kerakligi
20 y1 +30 у2 +30y3 +30у4 +57у5 +36y6 +47у7 +62y8 +27у9 +25у10 + +1у11 +65у12 → min (10.24) Yuqoridagi modelni chiziqli programmalashtirishning simpleks jadval ko‘rinishida xam yozish mumkin (10.16 -jadval).
(10.22-10.24) modelini yechish bilan bog‘liq; bo‘lgan baʼzi tushunchalarni ko‘rib chiqamiz. (10.23) cheklash tenglamalarini kuyidagi tarzda yozish mumkin:
