Постановка транспортної задачі та її математична модель

Транспортна задача полягає у пошуку найбільш вигідного плану перевезення однорідного продукту з пунктів виробництва (чи зберігання) до пунктів споживання, тобто від постачальників до споживачів, ефективність якого будемо оцінювати за критерієм найменшої вартості перевезення. Транспортна задача - це специфічна задача лінійного програмування.

Сформулюємо визначення транспортної задачі. Деяку однорідну продукцію, яка знаходиться в т постачальників А_1, А₂,..., А_т кількістю a₁, а₂,..., а_т одиниць відповідно, потрібно перевезти п споживачам В₁, В₂,..., В_п в кількостях b₁, b₂,..., b_n одиниць. Відома матриця вартостей перевезення одиниці продукції від i -го постачальника до j -го споживача:

Необхідно скласти такий план перевезення, щоб вивезти всю продукцію від постачальників, задовольнити потреби всіх споживачів і сумарна вартість перевезення при цьому має бути мінімальною.

Окреслена постановка задачі вимагає виконання рівності загальної суми запасу вантажу загальній сумі потреб в ньому, тобто

(5.1)

Якщо в транспортній задачі умова (5.1) виконується, то таку транспортну задачу називають закритою (з правильним балансом). Якщо ж рівність (5.1) не виконується, то транспортну задачу називають відкритою (з неправильним балансом). Побудуємо математичну модель транспортної задачі. Оскільки наперед невідомо, скільки вантажу потрібно перевезти від певного постачальника до споживача, щоб план перевезень був оптимальним, то позначимо його через . Вартість перевезення всього вантажу від постачальників до споживачів позначимо Z. Умову транспортної задачі можна записати у вигляді таблиці: