птимізації, або завдання з обмеженнями, це такі, при формулюванні яких задаються деякі умови (обмеження) на безлічі. Ці обмеження задаються сукупністю деяких функцій, задовольняють рівнянням або нерівностям [1].
. 4.1 Постановка транспортної задачі
Транспортна задача використовується для моделювання та оптимізації економічних проблем, пов'язаних з формуванням оптимального плану перевезень і оптимального розподілу індивідуальних контрактів на транспортування. Критерієм ефективності в даному випадку є лінійна функція, обмеження також лінійні, тому для вирішення такого завдання, можуть застосовуватися методи лінійної оптимізації і зокрема симплекс - метод, спеціальна структура задачі дозволяє розробляти більш зручні та прості методи рішення. Але перш ніж приступати до вирішення транспортної задачі необхідно її збалансувати, а потім скласти транспортну таблицю.
Рішення транспортної задачі складається з двох етапів:
- знаходження початкового плану перевезень, що задовольняє обмеженням в задачі;
поліпшення початкового плану та отримання оптимального плану перевезень, що доставляє мінімум цільової функції.
Найбільш відомими і часто вживаними вважаються наступні методи знаходження початкового плану перевезень:
- метод «північно-західного» кута;
метод мінімального елемента;
метод Фогеля.
Після здобуття початкової плану перевезень, ймовірно, існує ще більш досконалий план, тому бажано повести знаходження оптимального плану перевезень. Для цього існують спеціальні алгоритми, ми розглянемо метод потенціалів. Спочатку визначається, чи є отриманий план виродженим. Вироджений план перевезень виходить в тому випадку, якщо на якому-небудь кроці одночасно задовольняється попит споживача і вичерпуються пропозиції відповідного постачальника, тобто одночасно викреслюються рядок і стовпець. А потім проводиться перевірка плану на оптимальність і якщо необхідно здійснюється його поліпшення [2].
Також вводиться поняття «непрямі витрат» - витрат, одержуваних для маршрутів, за якими не здійснюються перевезення при даному плані. Розрахункові непрямі витрати порівнюються з реальними витратами, які мали б місце, якби перевезення по даному маршруту здійснювалися. Якщо для всіх не вибраних маршрутів непрямих витрат не більш реальних, то даний план перевезень є оптимальним. Якщо хоча б для одного маршруту непрямі витрати більше реальних, то план перевезень може бути поліпшений шляхом введення в нього даного маршруту.
Транспортна задача ставиться таким чином: є m пунктів відправлення, в яких зосереджені запаси якихось однорідних вантажів. Мається n пунктів призначення подали заявки відповідно на вантажу. Відомі вартості р ij перевезення одиниці вантажу від кожного пункту відправлення до кожного пункту призначення. Всі числа р ij, що утворюють прямокутну таблицю задані. Потрібно скласти такий план перевезень (звідки, куди і скільки одиниць поставити), щоб всі заявки були виконані, а загальна вартість всіх перевезень була мінімальна.
Далі, передбачається, що
(1)
де bi є кількість продукції, що знаходиться на складі i, і aj - потреба споживача j.
Зауваження. Якщо те кількість продукції, рівне залишається на складах. У цьому випадку ми введемо" фіктивного" споживача n +1 з потребою і покладемо транспортні витрати pi, n + 1 рівними 0 для всіх i.
Якщо то потреба не може бути покрита. У цьому випадку початкові умови повинні бути змінені таким чином, щоб потреба у продукції могла бути забезпечена.
Позначимо через x ij кількість продукції, що поставляється зі складу i споживачеві j. У реченні (1) нам потрібно вирішити наступну задачу (математична модель транспортної задачі):
(2)
(3)
(4)
(5)
(6)
Транспортну задачу ми можемо характеризувати транспортної таблицею і таблицею витрат.
Таблиця 1. Транспортна таблиця
а1 ... аnb1 Вm ......
Таблиця 2. Таблиця витрат
p11 ... p1n ...... pm1 ... pmn
Допустимий план перевезень будемо представляти у вигляді транспортної таблиці
Таблиця 3. Транспортна таблиця
а1 ... аnb Вm ... ...... ...
Cумма елементів рядка i повинна бути дорівнює bi, а сума елементів стовпця j повинна дорівнювати aj, і всі повинні бути невід'ємними. <...
