Розділи

загрузка...
5.2. Властивості опорних планів транспортної задачі; Математичне програмування - Наконечний С.І.

5.2. Властивості опорних планів транспортної задачі

Якщо умови транспортної задачі і її опорний план записані у вигляді табл. 5.1, то клітини, в яких (ненульові значення поставок), називаються заповненими, всі інші — пустими. Заповнені клітини відповідають базисним змінним і для невиродженого плану їх кількість дорівнює m + n – 1.

Назвемо циклом таку послідовність заповнених клітин таблиці 5.1, яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, причому перша клітина циклу є і його останньою клітиною. Якщо для певного набору заповнених клітин неможливо побудувати цикл, то така послідовність клітин є ациклічною.

Лема. Кількість клітин, які утворюють будь-який цикл транспортної задачі, завжди парна.

Доведення. Якщо позначити кожну клітину циклу двома індексами , то довільний цикл, що складається з n клітин, можна записати одним із двох способів:

, (5.9)

або

. (5.10)

Оскільки перша та остання клітини циклу є однією клітиною, то виключимо з розгляду останній елемент (i1, j1) наведених послідовностей. Кількість клітин, що залишилась, парна, бо кожній клітині виду в (5.9) та (5.10) відповідає наступна або . Саме такими клітинами закінчуються наведені послідовності. Передостанньою клітиною є клітина виду , де . Отже, цикл утворюється клітинами, які містяться в l рядках та l стовпцях, тобто загальна їх кількість n = 2l. Лему доведено.

Теорема 5.1. Щоб деякий план транспортної задачі був опорним, необхідно і достатньо його ациклічності.

Доведення. Необхідність. Нехай у таблиці 5.1 міститься опорний план транспортної задачі, тобто не більше ніж m + n – 1 клітин будуть заповненими. Якщо заповнених клітин менше, ніж m + n – 1, то решта базисних клітин знаходиться серед незаповнених.

Довести необхідність умови теореми означає довести ациклічність опорного плану.

Вектори, що відповідають базисним клітинам, тобто базисним змінним, є лінійно незалежними, і потрібно довести ациклічність набору клітин, що відповідає будь-якій системі лінійно незалежних векторів. Допустимо протилежне. Нехай деяка підсистема з даної системи базисних векторів утворює цикл, а саме:

. (5.11)

Складемо лінійну комбінацію таких векторів, що дорівнює нулю. Оскільки кожна змінна входить у систему обмежень лише двічі, то базисні вектори матимуть вид:

Лінійною комбінацією базисних векторів буде:

Або

. (5.12)

Проте рівність (5.12) суперечить умові лінійної незалежності базисних векторів, отже, послідовність (5.11) є ациклічною.

Достатність. Нехай деякий план транспортної задачі є ациклічним. Потрібно показати, що він є опорним планом, тобто довести лінійну незалежність векторів, що відповідають ненульовим компонентам плану.

Всякий план не може містити від’ємних компонент, а кількість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m + n – 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не перевищує цієї величини.

Позначимо множину всіх заповнених клітин через Н, а відповідні вектори — . Доведемо достатність, міркуючи від супротивного. Нехай вектори лінійно залежні. Розглянемо нульову лінійну комбінацію цих векторів:

. (5.13)

Деякі з коефіцієнтів можуть відрізнятися від нуля. Нехай один з таких коефіцієнтів відповідає індексам , тобто . Тоді відповідний доданок у рівності (5.13) можна перенести в ліву частину рівняння:

, (5.14)

де .

Оскільки і1-ша компонента в лівій частині (5.14) відмінна від нуля, то в правій частині також має бути хоча б один доданок з і-ою компонентою, що відмінна від нуля. Припустимо, що . Відповідний доданок також можна перенести в ліву частину (5.14):

, (5.15)

де .

Оскільки (інакше клітина входила б у суму (5.13) двічі) і компонента лівої частини (5.15) відмінна від нуля, то серед доданків правої частини знайдеться хоча б один, для якого . Перенесемо його також в ліву частину рівняння. Отримаємо:

, (5.16)

де .

Оскільки кількість заповнених клітин, що входять у множину Н, а отже, і кількість векторів скінченна і не перевищує числа , то через N кроків описаний процес перенесень обов’язково закінчиться.

Після деякої непарної кількості кроків дістанемо рівність:

, (5.17)

де .

Якщо кількість кроків була парною, матимемо:

, (5.18)

де .

Розглянемо співвідношення (5.17). При деякому значенні серед доданків другої суми лівої частини знайдеться такий, що має індекс . Тоді всі клітини, що були перенесені в ліву частину після -го кроку, утворюють цикл.

Аналогічні міркування стосуються також (5.18).

Покажемо, що до закінчення процесу, виходячи з рівності (5.17), обов’язково матимемо цикл. Для цього припустимо, що . Тоді, згідно з попередніми міркуваннями, в правій частині (5.17) обов’язково знайдеться доданок з індексами , для якого , бо інакше б рівність (5.17) не справджувалась. Отже, процес перенесення у разі, якщо , буде продовжуватись. Проте, внаслідок згаданої скінченності процесу перенесень (Nm n) умова виконання рівностей (5.17) та (5.18) рівносильна тому, що випадок обов’язково матиме місце, що означатиме побудову циклу.

Отже, припущення лінійної залежності векторів , що описується рівнянням (5.13), означає, що серед відповідних клітин існує цикл, але це суперечить умові теореми. Значить, достатність згаданої умови, а разом з тим і всю теорему доведено.

Отже, базисні клітини опорного плану завжди утворюють ациклічну послідовність клітин.

Теорема 5.2. (Наслідок теореми 5.1.) Будь-яка сукупність з клітин матриці транспортної задачі утворює цикл.

Доведення. Як зазначалось, сукупність лінійно незалежних векторів задачі не перевищує . Отже, всяка сукупність з векторів буде лінійно залежною. Як випливає з доведення попередньої теореми, відповідні клітини завжди утворюють цикл.

Отже, сукупність усіх базисних клітин та однієї вільної клітини таблиці транспортної задачі завжди утворює цикл.

Теорема 5.3. Якщо всі запаси і всі потреби є невід’ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами.

Доведення. Компоненти кожної системи із лінійно незалежних (базисних) векторів можуть бути подані у вигляді трикутної матриці. Нехай розглядається задача (5.1)—(5.4). Матриця з перших компонент базисних векторів системи (5.2), (5.3) матиме вигляд:

(5.19)

Розв’язування системи, що визначається (5.19), включатиме лише дії додавання та віднімання, і, оскільки та у постановці транспортної задачі є цілими числами, то значення змінних також будуть цілими числами.