3. Необхідна і достатня умови розв'язності транспортної завдання
Обмеження (1) і умови невід'ємності змінних, що виключають зворотні перевезення x ij > 0; i = 1, 2, ..., K ; j = 1, 2,., L . p> Ці умови утворюють систему обмежень. Будь-який план, компоненти якого задовольняють цій системі, буде допустимим. p> Як бачимо, система обмежень задана в основному ( k + l ) рівняннями. Встановимо умови, за яких ця система буде спільною, тобто буде мати рішення.
Складемо елементи x ij матриці перевезень по рядках, кожна рядок в сумі дає M i, і в результаті отримаємо. Складемо ті ж елементи за стовпцями, кожен стовпець дає N j, і в сумі отримаємо. Але від перестановки доданків сума не змінюється, тому для будь-якого допустимого плану обов'язково буде виконуватися умова
.
Рівність є необхідною умовою спільності обмежень завдання.
Доведемо і достатність цього умови: якщо запаси рівні потребам, то завжди мається допустимий план.
Дійсно, нехай. Розглянемо такі числа:
В
Переконаємося, що ці числа утворюють допустимий план. Для цього достатньо перевірити, що вони задовольняють всім обмеженням завдання.
Просуммируем ці числа за індексом i :
.
Але величини N j, від індексу i не залежить і їх можна винести за знак суми. В результаті
В
або
,
Отже, взяті числа задовольняють групі рівнянь (1).
Просуммируем ці числа за індексом j :
В
Виносячи постійні M i і за знак суми і маючи на увазі, що, отримуємо
В
або в розгорнутому вигляді
В
Як бачимо, наші числа задовольняють групі рівнянь (1). Ці числа ненегативні, тобто система обмежень повністю задовольняється. Таким чином, допустимий план існує, що й потрібно було довести. p> Рівність запасів потребам є необхідна і достатня умова спільності і, отже, можливості розв'язання транспортної завдання. [5]
4. Властивість системи обмежень транспортної задачі
Згідно з теоремою про структуру координат опорного плану задачі лінійного програмування, в невиродженому опорному плані повинно міститися r відмінних від нуля координат, де r - ранг системи обмежень br/>
.
У цій системі обмежень рівнянь закритої транспортної задачі є k + l -1 лінійно-незалежних рівнянь, тобто ранг системи обмежень дорівнює k + l -1. [6]
5. Опорне рішення транспортної задачі
Опорна рішення (опорний план, базисне рішення, basic solution) - одне з допустимих рішень, які знаходяться у вершинах області допусти...
