Формулювання класичної транспортної задачі лінійного програмування. Необхідність зведення відкритої транспортної задачі до закритої. Умови цілочисельності, оптимальності та методи побудови опорного плану транспортної задачі. Алгоритм методу потенціалів.
Аннотация к работе
ТРАНСПОРТНА ЗАДАЧА (ТЗ)При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного Аі-го постачальника до кожного Bj-го споживача, що подані як елементи матриці виду: Необхідно визначити план перевезень, за якого вся продукція була б вивезена від постачальників, повністю задоволені потреби споживачів і загальна вартість всіх перевезень була б мінімальною. У такій постановці задачі ефективність плану перевезень визначається його вартістю і така задача має назву транспортної задачі за критерієм вартості перевезень. Мають виконуватися такі умови: сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті: сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам: сумарна вартість всіх перевезень повинна бути мінімальною: Очевидно, що . У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд: (5.1) за обмежень: ; (5.2)Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m n - 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Отже, цикл утворюється клітинами, які містяться в l рядках та l стовпцях, тобто загальна їх кількість n = 2l. Нехай у таблиці 5.1 міститься опорний план транспортної задачі, тобто не більше ніж m n - 1 клітин будуть заповненими. Всякий план не може містити відємних компонент, а кількість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m n - 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не перевищує цієї величини. Очевидно, що приєднання до цього плану першого рядка з єдиним ненульовим елементом не утворить циклу, але відшуканий у такий спосіб план буде планом початкової задачі для , чим і доводиться теорема.