Транспорт логистикаси” кафедраси

Боғланишлар жадвали воситасида маршрутларни тузиш

Бунда иккита жадвалдан фойдаланилади: боғланишлар 1-жадвалига (БТ-1) берилган юк ташиш режаи , 2-таблицасига (БТ-2) эса топилган юксиз қатновлар оптимал режаи (8.10 жадвал) ёзилади.

Масалани ечиш билан боғлиқ бўлган бир қатор тушунчалар киритамиз.
Маршрут занжири деб бир-бири билан маълум тарзда боғланган юкли ва юксиз қатновлар кетма-кетлигига айтамиз. Айтайлик юкли ва юксиз қатновлар бўлсин. Юкли қатнов юксиз қатнов билан боғланган деймиз, қачонки улардаги тушириш пунктларининг индекслари бир-бирига мос келса, яъни бўлса.

А гар маршрутда биргина юкли ва юксиз қатновлар бўлиб, улар боғланган бўлса, буни биз бир звеноли маршрут деймиз. Масалан, . Маршрутдаги звенолар сонини билан ва маршрутлар номерини билан белгилаймиз.

Б ир звеноли маршрутни ёпиқ дейиш учун унинг биринчи ва охирги пунктлари бир жойда бўлиши керак, яъни бўлиши лозим.
И

кки звеноли маршрут занжири ёпиқ бўлиши учун, биринчи юкли қатновдаги ортиш пунктининг индекси иккинчи юксиз қатнов охирида бориладиган пункт индекси билан бир хил бўлиши лозим. Бундай маршрутни айланма маршрут дейилади.

Маршрутлар занжири қуйидаги тартибда шакллантирилади.
Боғланишлар таблицасида юкли ва юксиз қатновлар қийматларини олиб, бир звеноли боғланган маршрутлар занжирларини тузиб чиқамиз. Масалан юкли қатнов ва юксиз қатновлар билан бир звеноли боғланган маршрутлар занжирини ҳосил қиламиз:
1) ; 2) .
Бошқа ҳамма бир звеноли боғланган маршрутларни ёзиб чиқамиз:
3) ; 4) ; 5) ; 6) ; 7) ; 8) ;
9) ; 10) ; 11) .
Юқоридаги бир звенолик маршрутлардан фақат биттаси ёпиқ маршрутдир: . Бу маршрутда ташиладиган юк миқдори ва қийматларидан кичигига тенг бўлади.
т.
Энди ва қийматлари ўзгаради, яъни
т;
Бу ўзгарувчилардан бошқаларининг қийматлари ўзгармайди ва уларни ва устунларининг мос катакларига ёзиб қўямиз.
Энди 2-звеноли ёпиқ маршрутларни тузишга киришамиз. Бунинг учун юқоридаги бир звеноли маршрутларни кетма-кет жуфтлаштириб улар ёпиқми-йўқми текшириб чиқиш керак бўлади. Бунда қуйидаги 2-звеноли маршрутиларни топамиз:

т,


т,



т,


т,

Худди шу тарзда текширишни давом эттириб қуйидаги 3-звеноли маршрутни топиш мумкин:

т,

Боғланиш таблицаларидан кўриниб турибдики, ўзгарувчилар ва катталикларнинг қолган қийматлари 4-звеноли маршрутни ташкил этади.

т,

Боғланишлар жадвали усули билан маршрутлар тузиш ЭҲМ ёрдамида амалга оширилиши мумкин бўлса-да баъзи бир камчиликлардан ҳоли эмас. Масалан, тузилган маршрутларда юк ташиш практикасининг муҳим талаблари ҳисобга олинмаслиги мумкин (маршрут узунлигининг автомобиль бир кунда босиб ўтадиган йўлдан ошиб кетмаслиги ва шу кабилар). Юқорида кўриб ўтилган “қўшма режалар” ва “боғланишлар таблицаси” усуллари битта умумий камчиликка эга, у ҳам бўлса, тузилган маршрутларнинг автотранспорт корхоналарига биркитиб тузилмаслигидир.

Юк ташиш режаси.

№ п/п		қиймати
1		1300	950	800	800	500	500	300	0
2		400	400	400	0	0	0	0	0
3		600	600	600	200	200	200	0	0
4		550	550	550	550	550	300	300	0
5		700	700	550	550	550	300	300	0
6		500	500	500	500	200	200	0	0
7		300	300	300	300	300	300	300	0
		4350	4000	3700	2900	2300	1800	1200	0

Юксиз қатновлар оптимал режаси

№ п/п		қиймати
1		350	0	0	0	0	0	0	0
2		950	950	800	800	500	500	300	0
3		400	400	400	0	0	0	0	0
4		600	600	600	200	200	200	0	0
5		250	250	250	250	250	0	0	0
6		300	300	300	300	300	300	300	0
7		150	150	0	0	0	0	0	0
8		550	550	550	550	550	300	300	0
9		300	300	300	300	0	0	0	0
10		200	200	200	200	200	200	0	0
11		300	300	300	300	300	300	300	0
		4350	4000	3700	2900	2300	1800	1200	0

Агар маршрутлардаги юкларни ташиш бир неча автотранспорт корхоналари автомобиллари орқали амалга ошириладиган бўлса, тузилган маршрутларни бу корхоналарга биркитиш лозим.

Юкиз юриш оптимал режаини ташиш ҳажмларидаги
фарқни кетма-кет камайтириш усули

Маълумки самарали маршрутлаштиришниниг аосида юксиз қатновларнинг оптимал режаини топиш ётади. Юксиз юриш оптимал режаини ташиш ҳажмларидаги фарқларни кетма-кет камайтириш усули билан топиш мумкин. Бу усулнинг моҳияти қуйидаги мулоҳазалардан келиб чиқади.

Биринчи навбатда минимал элемент усули ёрдамида дастлабки режа тузилади. Бунда жўнатиш ҳажмлари ҳисобга олинмайди. Бошқача айтганда минимал элементларга эга бўлган истеъмолчиларга керагича юк ажратилади. Натижада баъзи жўнатувчиларга тўғри келадиган юк хажми уларнинг имкониятларидан ошиқ, баъзилари учун эса кам бўлиши мумкин.
Шундай қилиб берилган самарадорлик функцияси бўйича энг оптимал режа топилади. Айтиб ўтилганидек бу режа жўнатиш хажмларини қаноатлантирмайди ва кейинги итерацияларда жўнатиладиган фарқлар кетма-кет оптимал равишда камайтирилади. Итерациялар бу фарқлар қийматини ҳамма жўнатувчилар учун нолга тенглаштиргунча давом эттирилади. Натижада юксиз қатнов оптимал режаи топилади.
Усулнинг моҳиятини конкрет мисолда кўриб чиқайлик. Айтайлик юк жўнатиш ва қабул қилиш пунктлар берилган бўлиб, улар орасида юксиз юриладиган йўл масофалари ва ташиш ҳажмлари 8.11 жадвалда кўрсатилган. Юксиз юриш режаини оптимал режаини топиш керак.

Масала қуйидаги тартибда ечилади.

1. Дастлабки режа тузиш. Ҳар бир устун элементлари ичидан энг кичиги топилади. Мисолимизда бундай элементлар доира ичига олинган. Энг кичик элементларга эга бўлган катакларга шу пункт қабул қила оладиган юк хажмини ёзамиз, яъни . Бунда жўнатиш ҳажмлари ҳисобга олинмайди.
Масалани ечишни давом эттириш билан боғлиқ бўлган тушунчалар киритамиз. Матрица қаторларини классларга ажратиш лозим.
Бунинг учун ҳар бир қатор учун қуйидаги айирмани ҳисоблаймиз:

Бу фарқнинг қиймати:
биринчи қатор учун ;
иккинчи қатор учун ;
учинчи қатор учун эса .

Дастлабки режа

Топилган қийматларни жадвалнинг охирги устунига ёзамиз. Манфий фарқлар йиғиндисини шу устуннинг катагига ёзиб қўямиз.
Агар юқоридаги фарқнинг қиймати бирор қатор учун манфий ишорали бўлса, уни-манфий, мусбат бўлса – мусбат қатор деб атаймиз. Агар қатор учун бўлса, уни нейтрал қатор деймиз.
1. Нейтрал қаторлар шартли равишда мусбат ёки манфий бўлиши мумкин. Агар нейтрал қатор мусбат қатор билан боғлиқ бўлса, яъни бирор устунда иккала қаторга тегишли катакларда қиймати мавжуд бўлса – бунда нейтрал қатор шартли равишда мусбат бўлади. Агар у манфий қатор билан боғлиқ бўлса, шартли манфий бўлади.
2. - айирмаларни аниқлаш. Бунинг учун ҳар бир устун учун мусбат қаторлардаги қийматларидан энг кичиги топилади. ва бу қийматлардан манфий қаторларга тегишли устундан энг кичик айрилади, яъни

Мисолимизда айирмани 1, 2, ...., 5 устунлар учун қийматини топиш мумкин: .
Шу тарзда топиш мумкин. айирмалар қийматларини жадвалнинг охирги қаторига тўлдирамиз.
3. -айирмаларни ечувчи қўшилмалар дейилади. Уларни топишдан мақсад, маълум қоидалар асосида топилган қийматларидан бири танлаб олинади ва манфий қатор қийматларига қўшилади. Манфий қаторларнинг янги қийматларида яна режа тузилади ва қийматлари ҳисоблаб чиқилади. Бу ишлар то ҳамма учун қийматлари нолга тенглашгунча давом эттирилади.
Ечувчи қўшилма қийматини топилган қийматларидан кичигига тенг деб олиш мумкин, яъни

Итерациялар сонини камайтириш мақсадида қийматини Е.П. Нестерев томонидан қуйидагича топиш таклиф этилган. Топилган қийматларини ошиб бориш тартибида жойлаштирамиз, яъни

	5	1	3	2	4
	6	9	9	10	13

Ечувчи қўшилма катталиги бу қатордаги шундай қийматига тенг бўладики, қаторнинг бошидан устунгача бўлган қийматларининг йиғиндиси ( ) қийматига тенг ёки ундан катта бўлсин.

Мисолимизда чунки топилган қийматини жадвалнинг 1-устун манфий қаторига ёзиб қўямиз.
4. нинг янги шартли қийматларини топиш. Бунинг учун манфий қаторнинг ҳамма қийматларига =10 катталигини қўшиб чиқамиз ва уларнинг янги қийматларини топамиз: , .
5. Янги режа тузиш. Бунда ҳам дастлабки режа тузилганидек иш кўрилади. Биринчи навбатда ҳар бир устунда ягона энг кичик қийматига эга бўлган катаклар тўлдирилади. Энг кичик қийматига эга бўлган катаклар шундай тўлдириладики, бунда қатор иложи борича нейтрал қаторга айлансин.



Энг кичик ягона қийматли катаклар 1, 3, 4, 5, 6, 7 устунларда мавжуд. Бу катакларни биринчи навбатда тўлдирамиз. қаторда эса учта бир хил қийматли мавжуд. қатор нейтрал бўлиши учун - қатор учун эса - учун - бўлиши керак. Ҳамма қаторлар учун θ нолга тенг, демак, топилган режа оптималдир.