Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.9.2. Метод потенціалів на мережі

Розглянемо без доведення розв’язування транспортної задачі на мережі методом потенціалів. Зобразимо задачу у вигляді мережі (рис. 5.2.), де на кожній дузі цифрами у кружечках позначені вартості перевезень одиниці продукції; для спрощення вважатимемо ці вартості однаковими в обох напрямках ребра, а пропускні здатності ребер необмеженими зверху. Зауважимо, що .

Пункти відправлення і запаси в них позначимо відповідними цифрами (що дорівнюють запасам) із знаком «плюс», а пункти доставки — цифрами, що дорівнюють потребам, із знаком «мінус» (стоять у дужках).

На першому етапі складаємо початковий план перевезень: напрям вантажопотоків показуємо стрілками, а кількість вантажів — цифрою над (під) відповідною стрілкою.

Рис. 5.3

Як видно з рис. 5.3, початковий план утворюють змінні:

,

.

Якщо сіть містить m вершин, то система (5.42) складається з m рівнянь, а її ранг має дорівнювати . У нашому прикладі план містить рівно відмінних від нуля базисних змінних, отже, він невироджений.

Скористаємося без доведення теоремою [28]: для того, щоб деяка частина графа відповідала базисним змінним задачі (5.42)—(5.44), необхідно і достатньо, щоб вона була деревом.

У нашому прикладі початковий план не утворює контурів, тобто відповідає множині базисних змінних, отже, є опорним планом задачі.

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

;

;

;

.

Третій етап полягає в перевірці плану на оптимальність, причому використовується звичайна ознака оптимальності плану транспортної задачі, яка формулюється в термінах і позначеннях транспортної задачі на мережі. Для ребер мережі, вільних від перевезень, тобто для , невід’ємна різниця потенціалів вершин, які їх обмежують (стоять на їх кінцях), має бути меншою від відповідної вартості перевезення або дорівнювати їй. Складаємо відповідні співвідношення:

;

;

;

;

.

Для базисних ребер відповідні різниці точно дорівнюють вартостям перевезень, що є однією з умов оптимальності плану транспортної задачі. Отже, умова оптимальності порушена лише один раз на ребрі (4; 3). Якщо таких порушень більше ніж одне, то вибираємо ребро з найбільшим порушенням. Утворимо цикл з базисних ребер і небазисного ребра (4; 3), що проходить через вершини (4, 3, 1, 5, 6, 2, 4). Напрям обходу збігається з напрямом потоку, який планується вести по ланці (4; 3) — від вершини 4 до вершини 3, оскільки маємо нерівність . Отже, обходимо цикл проти руху стрілки годинника. Обмеження (5.42) не будуть порушені, якщо ми, вибравши в цьому циклі найменший зустрічний потік у ланці (2; 6), відніматимемо його величину від зустрічних потоків у ланках циклу і додаватимемо до потоків, напрями яких збігаються з напрямом обходу. Тоді ланка (2; 6) стає вільною від потоку, а ланка (4; 3) — базисною (рис 5.4).

Рис. 5.4

Перевіримо план на оптимальність. Для цього визначимо нову систему потенціалів, виправивши попередню:

.

Перевірку слід зробити лише для тих вільних ребер, для яких хоча б в одній з вершин змінилося значення потенціалу, а саме – для (1, 2), (2, 6):

;

.

Отже, всі умови оптимальності задовольняються і оптимальний план знайдено:

.

Зауважимо, що при розв’язуванні наведеної сітьової задачі методом потенціалів можуть траплятися випадки виродження. Ознакою виродження є план, що складається з двох або більше окремих дерев базисних ребер, не з’єднаних між собою. Для усунення цього треба ввести в базис вільну ланку, яка з’єднувала б означені дерева базисних ланок між собою.

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

У літературі [28] можна знайти детальніший опис розв’язання сітьових транспортних задач.