517. Транспортна задача лінійного програмування. Економічна і математична постановка транспортної задачі.

Транспортна задача є типовою задачею лінійного програмування, отже, її розв’язок можна отримати звичайним симплексним методом. Транспортна задача належить до типу розподільчих задач лінійного програмування. Економічний зміст таких задач може стосуватися різ­номанітних проблем, що переважно зовсім не пов’язано із перевезенням вантажів, як, наприклад, задачі оптимального розміщення виробництва, складів, оптимального призначення тощо. Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників А_і в обсягах одиниць відповідно необхідно перевезти n споживачам в обсягах одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного А_і-го постачальника до кожного В_j-го споживача, що подані як елементи матриці виду:

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

У такій постановці задачі ефективність плану перевезень визначається його вартістю і така задача має назву транспортної задачі за критерієм вартості перевезень.

математична модель. Мають виконуватися такі умови:

сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті

сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам

сумарна вартість всіх перевезень повинна бути мінімальною

У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд:

за обмежень: ; ; .