2.4. Мережний спосіб розв’язку транспортної задачі методом потенціалів

Цей спосіб не вимагає складання матриці перевезень, а дозволяє робити розрахунок прямо на схемі шляхів сполучення - мережі. Схема (рис. 1) складається з вершин (відправників і одержувачів) і ребер (шляхів між відправниками й одержувачами). Нумерація вершин порядкова. Ребра позначаються номерами обмежуючих їхніх вершин. На кожному ребрі відзначено

Рис. 1. Схема транспортної мережі

вартість перевезення С_ij за данним шляхом. У кожної станції в дужках показані розміри відправлення зі знаком плюс або розміри прибуття вантажу зі знаком мінус. Ребро називається завантаженим, якщо по ньому проходить який-небудь вантажопотік x_ij>0. Завдання полягає в тому, щоб розподілити перевезення між постачальниками і споживачами з найменшими витратами.

Потенціали - це умовні числа, приписані певним чином кожній вершині мережі. Суть методу полягає у відшуканні системи потенціалів, щоб дотримувалася наступна умова оптимальності: для кожного ребра абсолютна величина різниці потенціалів його вершин не повинна перевищувати, а для завантажених ребер точно дорівнює вартості перевезення між ними

(2.4)

при x_ij=0;

при x_ij>0.

2.4.1. Побудова початкового плану

Основна вимога - вивезти весь вантаж від усіх постачальників і задовольнити всіх споживачів. Вантажопотоки зображують біля відповідних ребер стрільцями, що показують напрямок, і цифрами їхньої величини (рис. 2). Загальна величина вантажопотоку, що виходить від відправника, дорівнює навантаженню плюс вхідні (транзитні) потоки, а вхідного до споживача - його потреби плюс вихідні (транзитні) потоки.

2 .4.2. Обчислення потенціалів

Одній з вершин присвоюють довільний потенціал і, використовуючи умову оптимальності (2.4) для завантажених ребер, визначають потенціали усіх інших вершин.

Для цього, рухаючись по завантажених ребрах від вершини з відомими потенціалами до вершин з невідомими потенціалами, визначають останні, додаючи вартість перевезення на ребрі до попереднього потенціалу, якщо рух попутній напрямкові вантажопотоку, і віднімаючи з попереднього потенціалу, якщо рух зворотній. Привласнимо якій-небудь вершині, наприклад, першій, потенціал 100 (див. рис. 2). Потенціал вершини 2 поки визначити не можна, тому що ребро 1.2 не завантажене. Потенціал вершини 7 дорівнює ₇=100-20=80, тому що рух від вершини I до вершини 7 протилежний вантажопотокові на ребрі 1.7.

Далі потенціал вершини 6 дорівнює ₆=80+15=95, тому що рух від вершини 7 до вершини 6 попутній вантажопотокові на ребрі 7,6. Аналогічно знаходимо потенціали всіх інших вершин:

₅=95-40=55; ₃=22+30=52;

₄=55-33=22; ₂=52-10=42.

У випадку, коли мережа по вантажопотоках поділяється на не досить зв'язані між собою системи (випадок виродження), тоді по деяких ділянках пропускають умовний нульовий потік.

2.4.3. Перевірка незавантажених ребер за умовою оптимальності (2.4)

Порушення цієї умови, тобто перевищення абсолютною величиною різниці потенціалів перевезення записують у відповідних ребрах зі знаком плюс. Це свідчить про те, що план не оптимальний, а ребро називається потенційним. Завантаження такого ребра знижує загальну вартість перевезень. У нашому випадку потенційне ребро 1.2 з порушенням +33.