Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

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) не справджувалась. Отже, процес перенесення у разі, якщо , буде продовжуватись. Проте, внаслідок згаданої скінченності процесу перенесень (N ≤ m • 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), включатиме лише дії додавання та віднімання, і, оскільки та у постановці транспортної задачі є цілими числами, то значення змінних також будуть цілими числами.