Відмінності між версіями «Опорний план ТЗ, цикл послідовності клітин»
| (не показані 3 проміжні версії цього учасника) | |||
| Рядок 1: | Рядок 1: | ||
== Опорний план ТЗ, цикл послідовності клітин == | == Опорний план ТЗ, цикл послідовності клітин == | ||
| − | Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є | + | Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродженим. <br> |
Якщо ж кількість базисних змінних менша ніж m + n – 1, то має-мо вироджений опорний план.<br> | Якщо ж кількість базисних змінних менша ніж m + n – 1, то має-мо вироджений опорний план.<br> | ||
Якщо умови транспортної задачі і її опорний план записані у вигляді табл. <br><math> min F = \sum\limits_{i=1}^m \sum\limits_{j=1}^n c_{ij} x_{ij} (1)</math><br>, то клітини, в яких <math> x_{ij} > 0 </math> (ненульові значення поставок), називаються заповненими, всі інші — пустими. <br> | Якщо умови транспортної задачі і її опорний план записані у вигляді табл. <br><math> min F = \sum\limits_{i=1}^m \sum\limits_{j=1}^n c_{ij} x_{ij} (1)</math><br>, то клітини, в яких <math> x_{ij} > 0 </math> (ненульові значення поставок), називаються заповненими, всі інші — пустими. <br> | ||
Заповнені клітини відповідають базисним змінним і для неви-родженого плану їх кількість дорівнює m + n – 1. <br> | Заповнені клітини відповідають базисним змінним і для неви-родженого плану їх кількість дорівнює m + n – 1. <br> | ||
| − | Назвемо циклом таку послідовність заповнених клітин таблиці (1), яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, | + | Назвемо циклом таку послідовність заповнених клітин таблиці (1), яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, причому перша клітина циклу є і його останньою клітиною. <br> |
| − | Якщо для певного набору заповнених клітин неможливо | + | Якщо для певного набору заповнених клітин неможливо побудувати цикл, то така послідовність клітин є ациклічною. |
'''Лема.''' Кількість клітин, які утворюють будь-який цикл транспортної задачі, завжди парна.<br> | '''Лема.''' Кількість клітин, які утворюють будь-який цикл транспортної задачі, завжди парна.<br> | ||
'''Доведення.''' Якщо позначити кожну клітину циклу двома індексами , то довільний цикл, що складається з n клітин, можна записати одним із двох способів: <br> | '''Доведення.''' Якщо позначити кожну клітину циклу двома індексами , то довільний цикл, що складається з n клітин, можна записати одним із двох способів: <br> | ||
| Рядок 12: | Рядок 12: | ||
або <br> | або <br> | ||
<math> (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) </math> <br> | <math> (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) </math> <br> | ||
| − | Оскільки перша та остання клітини циклу є однією кліти-ною, то виключимо з розгляду останній елемент <math>(i_1, j_1)</math> | + | Оскільки перша та остання клітини циклу є однією кліти-ною, то виключимо з розгляду останній елемент <math>(i_1, j_1)</math> наведених послідовностей. Кількість клітин, що залишилась, парна, бо кожній клітині виду <math>(i_k, j_k)</math> в (1) та (2) відповідає наступна <math>(i_p, j_k)</math> або <math>(i_k, j_p) (p \ne k) </math> . Саме такими клітинами закінчуються наведені послідовності. Передостанньою клітиною є клітина виду <math>(i_k, j_k)</math> , де k=l . Отже, цикл утворюється клітинами, які містяться в l рядках та l стовпцях, тобто загальна їх кількість n = 2l. Лему доведено. |
[http://www.twirpx.com/file/388285/ Джерело] | [http://www.twirpx.com/file/388285/ Джерело] | ||
Поточна версія на 11:15, 14 травня 2012
Опорний план ТЗ, цикл послідовності клітин
Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж 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. Лему доведено.
