Відмінності між версіями «Критерії опорного плану.»
Максим (обговорення • внесок) (→Теорема) |
Максим (обговорення • внесок) (→Теорема) |
||
| Рядок 6: | Рядок 6: | ||
Довести необхідність умови теореми означає довести ацикліч¬ність опорного плану. | Довести необхідність умови теореми означає довести ацикліч¬ність опорного плану. | ||
Вектори, що відповідають базисним клітинам, тобто базис-ним змінним, є лінійно незалежними, і потрібно довести ацик-лічність набору клітин, що відповідає будь-якій системі ліній-но незалежних векторів. Допустимо протилежне. Нехай деяка підсистема з даної системи базисних векторів утворює цикл, а саме: | Вектори, що відповідають базисним клітинам, тобто базис-ним змінним, є лінійно незалежними, і потрібно довести ацик-лічність набору клітин, що відповідає будь-якій системі ліній-но незалежних векторів. Допустимо протилежне. Нехай деяка підсистема з даної системи базисних векторів утворює цикл, а саме: | ||
| + | |||
(i_1,j_1); (i_1,j_2); (i_2,j_2) ;...; (i_k,j_k); (i_k,j_l) (5.11) | (i_1,j_1); (i_1,j_2); (i_2,j_2) ;...; (i_k,j_k); (i_k,j_l) (5.11) | ||
| + | |||
Складемо лінійну комбінацію таких векторів, що дорівнює нулю. Оскільки кожна змінна входить у систему обмежень лише двічі, то базисні вектори матимуть вид: | Складемо лінійну комбінацію таких векторів, що дорівнює нулю. Оскільки кожна змінна входить у систему обмежень лише двічі, то базисні вектори матимуть вид: | ||
| Рядок 16: | Рядок 18: | ||
Або | Або | ||
| + | |||
1*a_{i_1}{j_1}-1*a_{i_1}{j_2}+1*a_{i_2}{j_2}- ... - 1*a_{i_k}{j_l}=0(5.12) | 1*a_{i_1}{j_1}-1*a_{i_1}{j_2}+1*a_{i_2}{j_2}- ... - 1*a_{i_k}{j_l}=0(5.12) | ||
| + | |||
Проте рівність (5.12) суперечить умові лінійної незалежності базисних векторів, отже, послідовність (5.11) є ациклічною. | Проте рівність (5.12) суперечить умові лінійної незалежності базисних векторів, отже, послідовність (5.11) є ациклічною. | ||
Достатність. Нехай деякий план транспортної задачі є ацик¬лічним. Потрібно показати, що він є опорним планом, тобто до-вести лінійну незалежність векторів, що відповідають ненульо-вим компонентам плану. | Достатність. Нехай деякий план транспортної задачі є ацик¬лічним. Потрібно показати, що він є опорним планом, тобто до-вести лінійну незалежність векторів, що відповідають ненульо-вим компонентам плану. | ||
Всякий план не може містити від’ємних компонент, а кіль-кість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m + n – 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не пере-вищує цієї величини. | Всякий план не може містити від’ємних компонент, а кіль-кість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m + n – 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не пере-вищує цієї величини. | ||
Позначимо множину всіх заповнених клітин через Н, а відпо-відні вектори — . Доведемо достатність, міркуючи від супро-тивного. Нехай вектори лінійно залежні. Розглянемо нульову лінійну комбінацію цих векторів: | Позначимо множину всіх заповнених клітин через Н, а відпо-відні вектори — . Доведемо достатність, міркуючи від супро-тивного. Нехай вектори лінійно залежні. Розглянемо нульову лінійну комбінацію цих векторів: | ||
| + | |||
<math>\sum_{(i,j)\in H} \lambda_ij*a_ij^*</math>(5.13) | <math>\sum_{(i,j)\in H} \lambda_ij*a_ij^*</math>(5.13) | ||
| − | Деякі з коефіцієнтів можуть відрізнятися від нуля. Нехай один з таких коефіцієнтів відповідає індексам | + | |
| − | + | Деякі з коефіцієнтів можуть відрізнятися від нуля. Нехай один з таких коефіцієнтів відповідає індексам <math> \ (i_1,j_1)</math> , тобто <math>\lambda_{i_1}{j_1}</math>. Тоді відповідний доданок у рівності (5.13) можна перенести в лі-ву частину рівняння: | |
| − | де | + | |
| + | <math>- \lambda_{i_1}{j_1}*a_{i_1}{j_1}^* = \sum_{(i,j)\in H_1} \lambda_ij*a_ij^* </math>(5.14) | ||
| + | |||
| + | де <math>H_1=H-(i_1,j_1)</math>. | ||
| + | |||
Оскільки і1-ша компонента в лівій частині (5.14) відмінна від нуля, то в правій частині також має бути хоча б один доданок з | Оскільки і1-ша компонента в лівій частині (5.14) відмінна від нуля, то в правій частині також має бути хоча б один доданок з | ||
і-ою компонентою, що відмінна від нуля. Припустимо, що . Відповідний доданок також можна перенести в ліву частину (5.14): | і-ою компонентою, що відмінна від нуля. Припустимо, що . Відповідний доданок також можна перенести в ліву частину (5.14): | ||
| − | + | ||
| − | де | + | <math>- \lambda_{i_1}{j_1}*a_{i_1}{j_1}^* -\lambda_{i_1}{j_2}*a_{i_1}{j_2}^* = \sum_{(i,j)\in H_2} \lambda_ij*a_ij^*</math>(5.15) |
| + | |||
| + | де <math>H_2=H_1-(i_1,j_1)</math> . | ||
| + | |||
Оскільки (інакше клітина входила б у суму (5.13) двічі) і компонента лівої частини (5.15) відмінна від нуля, то серед доданків правої частини знайдеться хоча б один, для якого . Перенесемо його також в ліву частину рівняння. Отримаємо: | Оскільки (інакше клітина входила б у суму (5.13) двічі) і компонента лівої частини (5.15) відмінна від нуля, то серед доданків правої частини знайдеться хоча б один, для якого . Перенесемо його також в ліву частину рівняння. Отримаємо: | ||
, (5.16) | , (5.16) | ||
Версія за 11:36, 2 травня 2012
Теорема
Теорема 5.1. Щоб деякий план транспортної задачі був опор¬ним, необхідно і достатньо його ациклічності.
Доведення. Необхідність. Нехай у таблиці 5.1 міститься опор¬ний план транспортної задачі, тобто не більше ніж m + n – 1 клі-тин будуть заповненими. Якщо заповнених клітин менше, ніж m + n – 1, то решта базисних клітин знаходиться серед незапов-нених. Довести необхідність умови теореми означає довести ацикліч¬ність опорного плану. Вектори, що відповідають базисним клітинам, тобто базис-ним змінним, є лінійно незалежними, і потрібно довести ацик-лічність набору клітин, що відповідає будь-якій системі ліній-но незалежних векторів. Допустимо протилежне. Нехай деяка підсистема з даної системи базисних векторів утворює цикл, а саме:
(i_1,j_1); (i_1,j_2); (i_2,j_2) ;...; (i_k,j_k); (i_k,j_l) (5.11)
Складемо лінійну комбінацію таких векторів, що дорівнює нулю. Оскільки кожна змінна входить у систему обмежень лише двічі, то базисні вектори матимуть вид:
Лінійною комбінацією базисних векторів буде:
Або
1*a_{i_1}{j_1}-1*a_{i_1}{j_2}+1*a_{i_2}{j_2}- ... - 1*a_{i_k}{j_l}=0(5.12)
Проте рівність (5.12) суперечить умові лінійної незалежності базисних векторів, отже, послідовність (5.11) є ациклічною. Достатність. Нехай деякий план транспортної задачі є ацик¬лічним. Потрібно показати, що він є опорним планом, тобто до-вести лінійну незалежність векторів, що відповідають ненульо-вим компонентам плану. Всякий план не може містити від’ємних компонент, а кіль-кість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m + n – 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не пере-вищує цієї величини. Позначимо множину всіх заповнених клітин через Н, а відпо-відні вектори — . Доведемо достатність, міркуючи від супро-тивного. Нехай вектори лінійно залежні. Розглянемо нульову лінійну комбінацію цих векторів:
Неможливо розібрати вираз (невідома помилка): \sum_{(i,j)\in H} \lambda_ij*a_ij^* (5.13)
Деякі з коефіцієнтів можуть відрізнятися від нуля. Нехай один з таких коефіцієнтів відповідає індексам Неможливо розібрати вираз (невідома помилка): \ (i_1,j_1)
, тобто Неможливо розібрати вираз (невідома помилка): \lambda_{i_1}{j_1}
. Тоді відповідний доданок у рівності (5.13) можна перенести в лі-ву частину рівняння:
Неможливо розібрати вираз (невідома помилка): - \lambda_{i_1}{j_1}*a_{i_1}{j_1}^* = \sum_{(i,j)\in H_1} \lambda_ij*a_ij^* (5.14)
де Неможливо розібрати вираз (невідома помилка): H_1=H-(i_1,j_1) .
Оскільки і1-ша компонента в лівій частині (5.14) відмінна від нуля, то в правій частині також має бути хоча б один доданок з і-ою компонентою, що відмінна від нуля. Припустимо, що . Відповідний доданок також можна перенести в ліву частину (5.14):
Неможливо розібрати вираз (невідома помилка): - \lambda_{i_1}{j_1}*a_{i_1}{j_1}^* -\lambda_{i_1}{j_2}*a_{i_1}{j_2}^* = \sum_{(i,j)\in H_2} \lambda_ij*a_ij^* (5.15)
де Неможливо розібрати вираз (невідома помилка): H_2=H_1-(i_1,j_1)
.
Оскільки (інакше клітина входила б у суму (5.13) двічі) і компонента лівої частини (5.15) відмінна від нуля, то серед доданків правої частини знайдеться хоча б один, для якого . Перенесемо його також в ліву частину рівняння. Отримаємо: , (5.16) де . Оскільки кількість заповнених клітин, що входять у множину Н, а отже, і кількість векторів скінченна і не перевищує числа , то через N кроків описаний процес перенесень обов’язково закінчиться. Після деякої непарної кількості кроків дістанемо рів-ність: , (5.17) де . Якщо кількість кроків була парною, матимемо: , (5.18) де . Розглянемо співвідношення (5.17). При деякому значенні серед доданків другої суми лівої частини знайдеться такий, що має індекс . Тоді всі клітини, що були перенесені в ліву частину після -го кроку, утворюють цикл. Аналогічні міркування стосуються також (5.18). Покажемо, що до закінчення процесу, виходячи з рівності (5.17), обов’язково матимемо цикл. Для цього припустимо, що . Тоді, згідно з попередніми міркуваннями, в правій частині (5.17) обов’язково знайдеться доданок з індексами , для якого , бо інакше б рівність (5.17) не справджувалась. Отже, процес перенесення у разі, якщо , буде продовжува-тись. Проте, внаслідок згаданої скінченності процесу перенесень (N ≤ m • n) умова виконання рівностей (5.17) та (5.18) рівносиль-на тому, що випадок обов’язково матиме місце, що означа-тиме побудову циклу. Отже, припущення лінійної залежності векторів , що описується рівнянням (5.13), означає, що серед відповідних клітин існує цикл, але це суперечить умові теореми. Значить, до-статність згаданої умови, а разом з тим і всю теорему доведено. Отже, базисні клітини опорного плану завжди утворюють ациклічну послідовність клітин.
