Виродженість опорного плану транспортної задачі
Щоб не потрапити в глухий кут при вирішенні транспортної задачі, необхідно мати уявлення про вирожденність і невироджені опорного плану.
Опорний план транспортної задачі називається невироджених, якщо число базисних осередків одно r = n + m-1, де m - кількість рядків, n - кількість стовпців транспортної задачі. Якщо число перевезень менше ніж r = n + m-1, то такий план називається виродженим.
На початковому етапі вирішення транспортної задачі необхідно отримати початковий опорний план. Як це зробити, детально описано в статті Як вирішити транспортну задачу. Після отримання опорного плану необхідно перевірити його на невироджені.
Правило: кількість базисних (заповнених) клітин в початковому плані ЗАВЖДИ має дорівнювати m + n - 1, де m - кількість постачальників, n - кількість споживачів транспортної задачі.
Що ж робити, якщо кількість заповнених осередків опорного плану менше необхідного?
На певному етапі отримання початкового плану може скластися ситуація, коли одночасно задовольняються потреби магазину і спустошується склад. В цьому випадку відбувається "втрата" базисної клітини. Це призводить до того, що система визначення потенціалів має не єдине рішення.
Щоб обійти цю ситуацію, додамо до базисних осередкам відсутню кількість осередків з нульовими значеннями. Нульове значення поставимо в клітку, що стоїть поруч з базисної кліткою, яка зумовила "пропажу" базисного значення.
Виродженість опорного рішення транспортної задачі - приклад 1:
Побудувати початковий план для наступної ситуації:
Кількість постачальників (складів) = 3, кількість споживачів (магазинів) = 4
60 + 30 + 40 = 40 + 50 + 10 + 30 - попит дорівнює пропозиції - завдання закрита.
Методом північно - західного кута отримаємо опорний план.
Починаємо з самої верхньої лівої комірки.
Потреби першого магазину виконані повністю, але на складі ще залишився вантаж. Заповнюємо далі.
Залишки вантажу з першого складу 60 - 40 = 20 перевозимо в магазин другий. При цьому, перший склад спорожнів, але потреби магазину не виконані повністю.
Переходимо до другого складу. Всі 30 одиниць вантажу переносимо в магазин другий, потреби якого збіглися з пропозицією складу 50 - 20 = 30.
При цьому розподілі склад спустошується і потреби другого магазину виконуються повністю. Відбувається втрата базисної клітини!
В даному випадку необхідно до базисних клітин додати клітку з нульовим значенням, розташовану поруч з тільки що заповненої, яка зумовила втрату.
З третього складу направимо 10 одиниць вантажу в магазин 4 для повного виконання його потреб. На 3-му складі залишається 40 - 10 = 30 одиниць вантажу, які перенесемо в останній магазин.
Опорний план складений.
Кількість базисних осередків дорівнює 6 = 3 + 4 - 1. Умова невироджені виконано!
Виродженість опорного рішення транспортної задачі - приклад 2:
Три торгових складу поставляють продукцію в чотири магазини. Наявність продукції на складах і потреби магазинів наведені в наступній таблиці. Побудуємо початковий план транспортної задачі:
4 + 18 + 8 + 6 = 36
Початковий план отримаємо методом північно - кута.
Почнемо з заповнення осередки (1; 1).
Запаси першого складу розподілили по першому і другому магазину, при цьому запаси складу вичерпані, а потреба другого магазину не задоволена. Переходимо до другого складу.
Всі 10 одиниць вантажу направляємо в другій магазин, потреби якого на даний момент рівні 18 - 8 = 10. Зауважимо, що на даному етапі одночасно задовольняються потреби другого магазину і закінчилися запаси другого складу. Відбулася втрата одного базисного значення.
Нічого страшного, якщо ви пропустіть цей момент при отриманні опорного плану. Головне не забути перевірити умова невироджених перед перевіркою плану на оптимальність. Проаналізувавши вже отримане розподіл вантажу, неважко знайти момент, коли була "втрачена" базисна клітина.
Щоб компенсувати втрату, ми повинні ввести нульову комірку, поруч із заповненою. Чи можемо помістити її правіше, лівіше або нижче значення 10.
Закінчимо заповнення таблиці:
Отримали початковий план методом північно - західного кута. Кількість базисних осередків дорівнює 4 + 3 - 1 = 6.
Можна приступати до вирішення завдання методом потенціалів!