2.2. Методи побудови початкового плану

2.2.1. Метод північно-західного кута (діагональний). Таку назву одержав тому, що призначення перевезень починає ліворуч зверху (з північно-західного кута матриці) із клітки I.I (див. табл.6),

Таблиця 6

споживачі

ресурси

споживачів

ресурси постачальників

Для призначення першого перевезення порівнюємо ресурси першого постачальника (підсумок першого рядка) 20 - з потребою першого споживача (підсумок першого стовпця) 15. Меншу величину (15) поміщаємо в клітку 1.1 і віднімаємо з обох порівнюваних величин. У підсумку першого стовпця ставимо букву "до" (потреба першого споживача задоволена), а в підсумку першого рядка проставляємо залишок 20-15=5. Перший стовпець з подальшого розгляду виключаємо. Оскільки залишок залишився в першому рядку, то перевезення призначаємо в сусідню клітку рядка 1.2. Порівнюючи підсумки першого рядка і другого стовпця, установлюємо перевезення рівне 5, віднімаючи її з порівнюваних величин. У підсумку першого рядка ставимо букву "до" (ресурси першого постачальника вичерпані), з подальшого розгляду його виключаємо, а у підсумку другого стовпця проставляємо залишок 25-5=20.

Оскільки залишок залишився в другому стовпці, те наступне перевезення призначаємо в цьому стовпці в клітку 2.2 і так доти, поки в підсумках усіх рядків і стовпців не буде стояти буква "до". У такому початковому плані перевезення розташовані, приблизно, за діагоналлю матриці.

2.2.2. Метод найменшої вартості

В

Таблиця 7

елемент матриці (табл. 7) з мінімальною вартістю (клітка 4.4) поміщаємо максимально можливе перевезення. Для цього порівнюємо підсумки четвертого стовпця 14 і четвертого рядка (40). Менший з них поміщаємо в розглянуту клітку і віднімаємо з розглянутих величин. У підсумку четвертого стовпця залишається нуль, ставимо "до", а в підсумку четвертого рядка - 26. Четвертий стовпець з подальшого розгляду виключаємо, а в клітках матриці, що залишилися, шукаємо наступний елемент із мінімальною вартістю. Ні буде клітка 1.1.

Визначаємо величину перевезення, яку необхідно помістити в неї, і продовжуємо процес до розподілу всього обсягу перевезень.

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

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

2.2.4. Випадок виродження

При побудові початкового плану будь-яким методом після призначення чергового перевезення з подальшого розгляду виключається або рядок, або стовпець, а після призначення останнього перевезення - і рядок, і стовпець. Тому що сума рядків і стовпців m+n, те призначених перевезень m+n-1, тобто знайдено план - базисний розв’язок задачі. Однак іноді одночасно виключаються і рядок, і стовпець до призначення останнього перевезення, наприклад, тоді підсумки в стовпці і рядку виявилися рівні. Такий випадок називається «випадком виродження». Розв’язати задачу при цьому більшістю методів неможливо.

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

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