Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Постановка транспортної задачі та її математична модель
|
|
Транспортна задача полягає у пошуку найбільш вигідного плану перевезення однорідного продукту з пунктів виробництва (чи зберігання) до пунктів споживання, тобто від постачальників до споживачів, ефективність якого будемо оцінювати за критерієм найменшої вартості перевезення. Транспортна задача - це специфічна задача лінійного програмування.
Сформулюємо визначення транспортної задачі. Деяку однорідну продукцію, яка знаходиться в т постачальників А1, А2,..., Ат кількістю a1, а2,..., ат одиниць відповідно, потрібно перевезти п споживачам В1, В2,..., Вп в кількостях b1, b2,..., bn одиниць. Відома матриця вартостей перевезення одиниці продукції від i -го постачальника до j -го споживача:
Необхідно скласти такий план перевезення, щоб вивезти всю продукцію від постачальників, задовольнити потреби всіх споживачів і сумарна вартість перевезення при цьому має бути мінімальною.
Окреслена постановка задачі вимагає виконання рівності загальної суми запасу вантажу загальній сумі потреб в ньому, тобто
(5.1)
Якщо в транспортній задачі умова (5.1) виконується, то таку транспортну задачу називають закритою (з правильним балансом). Якщо ж рівність (5.1) не виконується, то транспортну задачу називають відкритою (з неправильним балансом). Побудуємо математичну модель транспортної задачі. Оскільки наперед невідомо, скільки вантажу потрібно перевезти від певного постачальника до споживача, щоб план перевезень був оптимальним, то позначимо його через 
. Вартість перевезення всього вантажу від постачальників до споживачів позначимо Z. Умову транспортної задачі можна записати у вигляді таблиці:
| постачальники | Споживачі | В1 | В2 | … | Вп |
 Потреби Запаси
| b1 | b2 | … | bn | |
| A 1 | a 1 | 
| 
| … | 
|
| A 2 | a 2 | 
| 
| … | 
|
| … | … | … | … | … | … |
| Am | am | 
| 
| … | 
|
Тоді цільова функція матиме вигляд:
або 
(5.2)
Для складання обмежень транспортної задачі скористаємося такими міркуваннями:
1) кількість вантажу, який потрібно перевезти до пункту Вj з усіх пунктів постачання, рівна 
aспоживачеві Вj потрібно bj -одиниць вантажу, тому, враховуючи те, що всі потреби повинні бути задоволеними, можемо записати обмеження стосовно потреб:
, 
;
2) кількість вантажу, який треба вивезти з пункту постачання Аi до всіх споживачів, дорівнює 
а постачальник має 
одиниць вантажу і всі вантажі мають бути вивезені, тому обмеження стосовно запасів матимуть вигляд:
. 
.
В загальному випадку систему обмежень запишемо таким чином:
або
(5.3)
Ми отримали математичну модель транспортної задачі (5.2)-(5.3), де - кількість продукції, що перевозиться від і- гопостачальника до j -го споживача; 
- вартість перевезення одиниці продукції від i -го постачальника до j-го споживача; - запаси продукції i -го постачальника; bj - попит на продукцію j -го споживача.
Тепер, виходячи з економічної постановки транспортної задачі, можемо сформулювати її математичну задачу: серед всіх невід’ємних розв’язків системи рівнянь (5.3) знайти такий, при якому оптимізуюча форма (5.2) набуде найменшого значення.
Транспортна задача є задачею лінійного програмування, яку можна розв’язати симплекс-методом, але при розв’язуванні транспортної задачі симплексним методом ми б отримали симплекс-таблиці великих розмірів, оскільки число невідомих дорівнює 
. Специфічна структура цієї задачі дозволяє використати для її розв’язання ефективніший метод - метод потенціалів, який розглянуто в п. 5.3.
Методи побудови початкового опорного плану
Як і в симплексному методі розв’язування задач лінійного програмування, при розв’язуванні транспортної задачі потрібно мати початковий опорний план.
Розглянемо методи знаходження цього плану:
|
|