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

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

5.4. Випадок виродження опорного плану транспортної задачі

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

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

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

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

Таблиця 5.6

Перевіримо, чи є отриманий опорний план виродженим. Кількість постачальників , а кількість споживачів . Для невиродженого опорного плану кількість заповнених клітин таблиці 5.6 має дорівнювати . У наведеному опорному плані кількість заповнених клітин на одну менше (п’ять), отже, він вироджений. Позбудемося виродженості опорного плану введенням нульової поставки в одну з пустих клітин. Враховуючи необхідність збереження ациклічності опорного плану, не можна заповнювати клітини А2В1 та А4В1, оскільки це призведе до утворення циклів, які зображені в табл. 5.7. та 5.8.

Очевидно введення нульової поставки в будь-яку іншу пусту клітинку не дає змоги утворити цикл. Отже, можна заповнити нулем одну з клітин А1В3, А2В3, А3В1, А3В2, А4В3. Наприклад, виберемо клітину А3В2.

Таблиця 5.9

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