Метод подвійної переваги

У кожному з рядків транспортної таблиці необхідно знайти клітину з мінімальною вартістю позначити його знаком *. Потім те ж потрібно виконати в кожному стовпці. Деякі клітини (відзначені **) мають мінімальні значення як по рядку, так і по стовпці. В такі клітини записується максимально можливі перевезення, виключаючи із розгляду після кожного запису xij, відповідно, рядок або стовпець. Далі в частині матриці, що залишилася, записується максимально можливі перевезення в клоітини, відзначені знаком *. Після цього заповнюються непомічені клітини. Приклад одержання початкового плану приведено в табл. 2-8.

Таблиця 2-8

Призначимо перевезення в клітини, позначені **.

Призначимо перевезення в клітини, позначені *.

Призначимо перевезення в клітини, що залишились.

У даному початковому плані 6 базисних кліток, що відповідає числу постачальників і споживачів: 4+3-1=6. Якщо число базисних кліток більше m+n-1, то допущені помилки при складанні початкового плану. Якщо число базисних кліток менше m+n-1, то має місце випадок виродження. Загальна вартість виконання перевезень L =2·20+3·10+6·20+11·20+13·15+15·5=680 грн.

Випадок виродження початкового плану.

При вирішенні практичних задач можуть мати місце випадки, коли число базисних клітин менше m+n-1. В цьому випадку має місце випадок виродження. Виродження може статись, якщо призначення чергового перевезення призводить до одночасного виключення рядка і стовпця транспортної таблиці. Для побудови оптимального плану методом потенціалів необхідно збільшити число базисних кліток до m+n-1, уводячи " штучні нульові перевезення". Приклад складання початкового плану у випадку " виродження" наведено в табл. 9-11.

Призначимо перевезення x₁₁=20. В цьому випадку потреби пункту b1 будуть повністю покриті за рахунок a1 і з таблиці виключається перший рядок і перший стовпець. Помітимо цю клітину буквою В.

Далі призначимо перевезення методом подвійної переваги. Останню заповнену клітину позначимо буквою П.

В цій таблиці 4 базисних клітини, а повинно бути 3+3-1=5. Для того, щоб довести число базисних клітин до 5 призначаємо штучне нульове перевезення в клітину, що знаходиться на перетині рядка з міткою В та стовпця з міткою П, або стовпця з міткою В та рядка з міткою П:

6. Знаходження оптимального плану перевезень у транспортній таблиці.

Побудований опорний план перевезень необхідно перевірити на оптимальність. Це можна виконати за допомогою методу потенціалів. Потенціали представляють собою умовну суму, яку вносить кожний з пунктів призначення A_i (потенціал U_i) та кожний з пунктів призначення B_j (потенціал V_j) за перевезення одиниці вантажу деякому перевізнику. Всього потенціалів m + n.

Значення одного з потенціалів приймається довільним (звичайно нуль). Значення інших потенціалів розраховується по базисним (заповненим) клітинам таким чином, щоб для всіх базисних клітин виконувалась умова:

U_i + V_j = c_ij (3)

План перевезень буде оптимальним, якщо для всіх базисних клітин виконується умова (3), а для всіх вільних умова:

U_i + V_j ≤ c_ij (4)

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

1) цикл перерахування будується для вільної клітини, де порушення умови (4) буде максимальним, тобто: U_i + V_j – c_ij = max.

Цикл будується таким чином, щоб всі його вершини, крім початкової (вільної клітини), знаходились в базисних (зайнятих) клітинах. При цьому в кожній вершині виконується поворот на 90º. Цикли перерахування можуть приймати наступні форми:

2) вільну клітина, що вводиться в план перевезень, помічається знаком „+”. Далі по черзі помічаються всі базисні клітини циклу знаками „–“ та „+” і т.д.

3) клітина, що помічена „–“, яка має найменше значення перевезення X*, повинна бути виключена з базису і стати вільною.

4) обсяги перевезень в клітинах, помічених знаком „+”, збільшується на величину X *, а в клітинах, помічених знаком „–”, зменшується на цю величину.

5) після перерозподілу перевезень і зміни базису будується нова транспортна таблиця (план перевезень), яка знову перевіряється на оптимальність методом потенціалів.

Нижче наведено приклад розрахунку потенціалів та пошуку оптимального плану перевезень.