Відмінності між версіями «Опорний план ТЗ, цикл послідовності клітин»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(Створена сторінка: == Опорний план ТЗ, цикл послідовності клітин == Назвемо опорним планом транспортної зада...)
 
 
(не показані 4 проміжні версії цього учасника)
Рядок 1: Рядок 1:
 
== Опорний план ТЗ, цикл послідовності клітин ==
 
== Опорний план ТЗ, цикл послідовності клітин ==
  
Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродже-ним. <br>
+
Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж 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), яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, причо-му перша клітина циклу є і його останньою клітиною. <br>
+
Назвемо циклом таку послідовність заповнених клітин таблиці (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_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. Лему доведено.
+
Оскільки перша та остання клітини циклу є однією кліти-ною, то виключимо з розгляду останній елемент <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/ Джерело]

Поточна версія на 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. Лему доведено.


Джерело