Опорний план ТЗ, цикл послідовності клітин
Опорний план ТЗ, цикл послідовності клітин
Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродженим.
Якщо ж кількість базисних змінних менша ніж m + n – 1, то має-мо вироджений опорний план.
Якщо умови транспортної задачі і її опорний план записані у вигляді табл.
Неможливо розібрати вираз (невідома помилка): min F = \sum\limits_{i=1}^m \sum\limits_{j=1}^n c_{ij} x_{ij} (1)
, то клітини, в яких Неможливо розібрати вираз (невідома помилка): x_{ij} > 0
(ненульові значення поставок), називаються заповненими, всі інші — пустими.
Заповнені клітини відповідають базисним змінним і для неви-родженого плану їх кількість дорівнює m + n – 1.
Назвемо циклом таку послідовність заповнених клітин таблиці (1), яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, причо-му перша клітина циклу є і його останньою клітиною.
Якщо для певного набору заповнених клітин неможливо по-будувати цикл, то така послідовність клітин є ациклічною.
Лема. Кількість клітин, які утворюють будь-який цикл транспортної задачі, завжди парна.
Доведення. Якщо позначити кожну клітину циклу двома індексами , то довільний цикл, що складається з n клітин, можна записати одним із двох способів:
Неможливо розібрати вираз (невідома помилка): (i_1,j_1);(i_2,j_1);(i_2,j_2);...;(i_l,j_l);(i_1,j_l);(i_1,j_1); (2)
або
Неможливо розібрати вираз (невідома помилка): (i_1,j_1);(i_1,j_2);(i_2,j_2);...;(i_l,j_l);(i_l,j_1);(i_1,j_1); (3)
Оскільки перша та остання клітини циклу є однією кліти-ною, то виключимо з розгляду останній елемент Неможливо розібрати вираз (невідома помилка): (i_1, j_1)
наведе-них послідовностей. Кількість клітин, що залишилась, парна, бо кожній клітині виду Неможливо розібрати вираз (невідома помилка): (i_k, j_k) в (1) та (2) відповідає наступна Неможливо розібрати вираз (невідома помилка): (i_p, j_k) або Неможливо розібрати вираз (невідома помилка): (i_k, j_p) (p \ne k) . Саме такими клітинами закінчуються наведені послідовності. Передостанньою клітиною є клітина виду Неможливо розібрати вираз (невідома помилка): (i_k, j_k) , де k=l . Отже, цикл утворюється клітинами, які містяться в l рядках та l стовпцях, тобто загальна їх кількість n = 2l. Лему доведено.
