т.е.
- U=C
Всі потенціали визначаються наступним чином. Для одного з стовпців (відправник) приймає потенціал «U», рівним нулю. При цьому доцільно прирівнювати до нуля потенціал того стовпця, в якому є завантажена клітка з найбільшою відстанню. Решта потенціали визначають по завантажених клітинам виходячи з таких формул:
Для стовпців U=VC
Для рядків V=U + C.
Таблиця 4 Матриця для перевірки оптимальності розподілу
Примітка:
1. До визначення потенціалів приступають за умови, якщо число завантажених клітин в матриці дорівнюватиме m + n - 1, де m - число основних рядків, n - число основних стовпців.
2. Якщо число завантажених клітин менше числа m + n - 1 то необхідно штучно завантажити відсутню кількість клітин матриці, записуючи в них 0 (нуль). У подальших розрахунках ця клітина вважається завантаженою. Нульова не вплине на баланс наявності та потреби вантажу. Нуль слід ставити в ту клітку, яка лежить на перетині рядка і стовпця, що не мають потенціали, з рядком або стовпцем, для яких потенціали вже визначені.
. Якщо число завантажених клітин більше числа m + n - 1, або при неправильній завантаженні клітин матриці, то визначаються потенціали будуть неоднозначними. Для ліквідації неоднозначного потенціалу будується замкнутий контур. Таке рішення задачі обов'язково призведе до ліквідації однієї із завантажених клітин і тим самим до однозначному визначенню потенціалу.
Після визначення всіх потенціалів розглядають всі незавантажені клітини і серед них відшукують такі, для яких різниця між відповідними їм потенціалами буде більше відстані, зазначеного в цій клітці, тобто V-U gt; C. Для кожної такої клітини визначається число d=VUC.
Такі підрахунки робляться для всіх незавантажених клітин. Розглядаючи таким чином всі незавантажені клітини не знаходимо клітин з позитивним значенням d. Значить, отримано оптимальний розподіл.
Примітка: якщо виявляється позитивне значення, то його покажемо безпосереднім в лівих кутах відповідних клітин таблиці цифрами в гуртках. Наявність таких клітин показує, що розподіл не є оптимальним і його можна поліпшити, тобто можна знайти більш кращий план перевезень. Щоб поліпшити отриманий план перевезень, знаходять клітку з максимальним числом d в гуртку і для цієї клітини будують «контур». Обчислення послідовно ведуть до тих пір, поки є клітини, де є позитивні значення d. Їх відсутність показує, що поліпшити розподіл не можна, що воно є оптимальним.
Результати отриманого рішення (див. табл. 5) вносять в заявочну матрицю (табл. 2) і отримують поєднану матрицю (табл. 6). Після цього приступають до складання маршрутів.
Таблиця 5 Суміщена матриця
Побудувавши поєднану матрицю, приступають до виявлення раціональних маршрутів руху автомобілів за допомогою побудови замкнутих контурів. У першу чергу виявляються митників маршрути із зворотним холостим пробігом, тобто з коефіцієнтом використання пробігу на маршрутах 0,5. Клітини, що містять дві цифри обсягу перевезень (тонн), обведені кружком і не обведена, вказують на маятниковий маршрут. Кількість вантажу перевезеного за цими маршрутами визначається за меншою цифрі (в гуртку чи без гуртка). Такими маршрутами у нас будуть:
Маршрут №1 Сівши. ? Сім. ? ? Сівши. =240 тис. Тонн
Маршрут №2 Сівши. ? А.? ? Сівши. =160 тис. Тонн
Маршрут №3 Сим. ? Б.? ? Сім. =10 тис. Тонн
Маршрут №4 Б.? Ф.? ? Б.=10 тис. Тонн
Отримані маршрути заносяться у відповідні графи спеціальної таблиці (див. табл. 11) - розшифровка отриманих маршрутів руху автомобілів.
Найменша кількість тонн, вбрання для маршруту, виключається з матриці, тобто вичитується з обох цифр. Коли всі митників маршрути знайдені і обсяги, що перевозяться по цих маршрутах виключені, в матриці будують чотирикутні контури так, щоб всі кути контуру чергувалися: одна в клітці з цифрою, що не обведеної гуртком, наступна за нею - у клітці з цифрою, обведеної кружком і т.буд. Побудова контуру починається обов'язково з клітини, в якій цифра не обведена кружком (пробіг автомобіля з вантажем). З цієї клітини проводиться пряма горизонтальна лінія до клітини з цифрою, обведеної гуртком, і т.д. до тих пір, поки лінія не замкнеться в тій клітці, звідки почали побудова контуру, тобто не утворюється замкнутий контур. Кількість перевезених за маршрутом тонн вантажу, визначається найменшим числом в кутах (вершинах) контура. Обрана кількість перевезень (найменше) виключається почергово з усіх кутів контуру.
Таблиця 6 Отримання маршрутів №5 А.? Сівши....
