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