Опорний план ТЗ, цикл послідовності клітин

Матеріал з Вікі ЦДУ
Версія від 11:15, 14 травня 2012; Lionardo (обговореннявнесок)

(різн.) ← Попередня версія • Поточна версія (різн.) • Новіша версія → (різн.)
Перейти до: навігація, пошук

Опорний план ТЗ, цикл послідовності клітин

Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж 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. Лему доведено.


Джерело