Випадок виродження опорного плану ТЗ

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

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

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

Нехай маємо такі умови транспортної задачі та початковий опорний план, що подані в табл. 1.1.

Таблиця 1.1