4-мавзу: ялпи юкларни ташишни маршрутлаштириш режа

4-мавзу: ЯЛПИ ЮКЛАРНИ ТАШИШНИ МАРШРУТЛАШТИРИШ
Режа:
1. Маршрутлаштиришнинг техник усуллари
2. Маршрутлаштиришни транспорт масаласига келтириб ечиш
3. Юксиз қатновларни оптимал режалаштириш

Маршрутлаштириш масаласи мазмуни ва очиш усулларининг хусусиятларига қараб икки группага – майда ва йирик партияли ташишга бўлинади. Йирик партияли юк ва йўловчилар ташишни маршрутлаштириш услубларини кўриб чиқайлик.

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

Юқоридаги келтирилган мисолимизнинг потенциаллар усули билан ечилишини кўрайлик. Биринчи навбатда минимал элемент усули билан бошланғич базис режани тузамиз. Бу режа жадвалда тузилган. Бунда биринчи, иккинчи ва ҳоказо навбатда ўзгарувчиларга қиймат берилган катаклар мос равишдаги номерлар билан белгиланган. Бу номерлар катакларнинг чап томонидаги пастки бурчакда ёзилган (8.2 жадвалга қаралсин). Масалан, биринчи навбатда берилган қиймат (катак №1), иккинчи навбатда - (катак №2), учинчи навбатда - (катак №3) ва ҳоказо.

Кейинги босқич тузилган базис режасининг оптималлигини текшириш ва у оптимал бўлмаса, бу режани оптимал даражагача ўзгартиришдан иборатдир. Юқорида келтирилган бошланғич базис режасини тузиш усуллари мусбат қийматларга эга бўлган ўзгарувчиларнинг шундай сонини берадики, (матрицадаги тўлдирилган катаклар сони), бу сон қийматига тенг ёки ундан кичик бўлади ( - матрицадаги қаторлар, - устунлар сони). Чунки ўзгарувчига ҳар бир қиймат берилган қатор ёки устун кейинги текширишдан чиқарилади (ўчирилади), охирги қиймат берилганда эса устун ва қатор бирдан ўчирилади (бунда тўлдирилган катаклар сони қийматига тенг бўлади). Баъзан ўзгарувчига қиймат берилганда устун ва қатор бир неча марта барваракайига ўчирилиши мумкин, бунда матрицадаги тўлдирилган катаклар сони қийматидан кичик бўлади. Бундай ҳолни бузилиш дейилади ва бунда кейинги ҳисобларда бир циклда кетма-кет тўхтаб қолиш, яъни чексиз итерациялар билан режани яхшилай олмаслик хавфи пайдо бўлади. Бунинг олдини олиш учун катаклар сунъий равишда исталганча кичик бўлган сон билан ёки ноллар билан тўлдирилади ва катаклар билан кейинги итерацияларда худди тўлдирилган катаклардек иш кўрилади.
Базис режасидан то оптимал режани топгунгача бўлган ҳисоблашларда цикллар сонини камайтириш мақсадида тўлдирилган катакларнинг маълум қийматини кўчириш мумкин. Қийматларни кўчириш ё қаторлар (горизонтал) ёки устунлар (вертикал) бўйлаб амалга оширилиши мумкин. Кўчиришда албатта қаторлар ва устунлар бўйича автотонналар баланси бузилмаслиги керак. Бошқача айтганда бир катакдаги қийматни иккинчи катакка кўчиришдан ҳосил бўлган баланснинг бузилиши бошқа бир кўчириш билан тўғриланиши керак. Шуни таъкидлаш лозимки, қийматлари камаядиган катаклар учун йиғиндиси кўпаядиган катаклардаги йиғиндисидан катта бўлиши лозим. Акс холда бундай кўчириш режани яхшилашга олиб келмайди. Масалан, катак қиймати 50-ни катагига, бунга мос равишда катак қийматидан 50-ни - га кўчириш мақсадга мувофиқдир. Бу кўчиришлар 1.2 таблицада стеркалар билан кўрсатилган.
Тузилган режанинг оптималлигини потенциаллар ёрдамида текшириб кўрилади. Потенциаллар бу ҳар бир устун ва қаторларга ёзиладиган махсус сонлардир.
Транспорт масаласини потенциаллар усули билан ечиш шундай ўзгарувчилар системасини топиш демакдирки, бунда қуйидаги шартлар бажарилсин:
бўлса,
бўлганда.
Ушбу шартлар бўйича оптимал режада ҳамма тўлдирилган катаклар учун қатор ва устунлар потенциаллар айирмаси мос катаклардаги қийматига тенг бўлиши ва барча бўш катакларда эса бу айирма қийматидан кичик бўлиши лозим.
Потенциаллар қуйидагича топилади.
● Бирор устун ёки қатор потенциалига 0 қиймат берилади, масалан . Бирор устун потенциалини топиш учун шу устундаги бирор тўлдирилган катак қаторининг потенциали маълум бўлиши керак ёки аксинча.
Бунда бирор қатор потенциалини топиш учун эса қатордаги бирор тўлдирилган катак устуни потенциалига шу катакдаги қиймати қўшилади, бирор устун потенциали топиш учун эса шу устундаги бирор тўлдирилган катак қатори потенциалидан катакдаги қиймати айирилади, яъни

бу ерда тўлдирилган катак индекслари.
● Ҳамма потенциаллар топилгандан кейин бошланғич базис режа оптималлигини текшириш мумкин.
● Агар ҳамма бўш катаклар учун шарт бажарилса, яъни ҳамма бўш катакларда ва потенциаллар айирмаси дан кичик ёки унга тенг бўлса, топилган режа оптимал бўлади. Бошқача айтганда бу режа барча чеклаш тенглмаларини қаноатлантиради ва самарадорлик функциясини экстремал қийматини таъминлайди.
● Агар оптималлик шарти бажарилмаса (бизнинг мисолимизда оптималлик шарти масалан катагида бажарилмайди) бу катак учун оптималлик шартини қанчага бажарилмаслиги ( ) топалади. Масалан катаги учун
бўлади.

Агар бундай катаклар бир неча бўлса (бизнинг мисолимизда ), уларнинг ҳаммаси учун топилади ва унинг қиймати энг кўп бўлган катакдан бошлаб ёпиқ контур чизилади.

● Ёпиқ контур горизонтал ва кертикал чизиқлардан иборат бўлиб, контурнинг бир учи қиймати нолдан ката бўлган катакда, бошқа ҳамма учлари тўлдирилган катакларда ётади. Контур қуйидагича кўрилади. қийматли катакдан қатор (ёки устун) бўйича тўғри чизиқ, то тўлдирилган катаккача ўтказилади ва бу ердан чизиқ йўналиш тўғри бурчакка ўзгартирилиб, тўғри чизиқ устун (ёки қатор) бўйича яна бирорта тўлдирилган катаккача давом эттирилади. Шуни ҳиобга олиш керакки, Контур чизиқлари доимо қийматлик катаккача давом эттирилади ва ҳамма вақт контур учларининг сони жуфт бўлади. Бунда контур чизиқларининг кесишишидан ҳосил бўлган бурчакларни, уни учлари деб қаралмайди. Контур учларига фақат унинг тўлдирилган катакларда ётадиган бурчаклари киради. Бизнинг миолимизда контур учлари катакларида ётади.
Тузилган контур учларига кетма-кет (-) ва (+) ишораларни берамиз. Биринчи катакка (-) белгиси берилади ва (+) ишорали тўлдирилган катаклар қийматларидан энг кичигини танлаб оламиз. Мисолимизда бундай катак бўлиб,унинг қиймати – 200. Шу миқдордаги юкни ҳамма (+) ишорали катаклар қийматларидан айирамиз ва (-) ишорали катаклар қийматларига қўшамиз. Бундай операциялардан кейин янги режа ҳосил қиламиз.
● Янги режа учун яна потенциаллар топилади ва улар ёрдамида режани оптималлигини қайтадан текширилади.