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

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

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

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

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

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

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

Таблиця 5.6

bj ai	b1 = 7	b2 = 10	b3 = 6
а1 = 8	0 7	5 1	2
а2 = 7	2	3 7	4
а3 = 6	1	2	0 6
а4 = 2	0	0 2	0

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

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

Таблиця 5.9

bj ai	b1 = 7	b2 = 10	b3 = 6
а1 = 8	0 7	5 1	2
а2 = 7	2	3 7	4
а3 = 6	1	2 0	0 6
а4 = 2	0	0 2	0

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