Транспортна задача

Мінімізація сумарних витрат на транспортування вантажу від постачальників до споживачів.

Максимізація кількості прибутку від продажу товарів

Рівномірний розподіл продукції між усіма наявними складами

Мінімізація кількості задіяних транспортних засобів.

Кількість постачальників дорівнює кількості споживачів (матриця є квадратною).

Усі тарифи на перевезення є додатними числами.

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

Жоден із маршрутів не має заборони на перевезення.

Кількість постачальників не дорівнює кількості споживачів

Сума запасів дорівнює сумі потреб (A = B)

Сума запасів менше суми потреб (A < B)

Сума товарів у постачальників більше суми потреб (A > B)

Фіктивного постачальника з нульовими тарифами.

Фіктивного споживача з потребою, що дорівнює різниці між запасами та попитом, та нульовими тарифами.

Додаткові обмеження на максимальну вартість перевезень.

Штрафні тарифи для споживачів з найбільшим попитом.

m + n - 1

m * n

m + n

m * n - 1

Усі тарифи в матриці однакові.

Кількість заповнених клітин більша ніж m + n - 1.

Сумарні витрати дорівнюють нулю.

Кількість заповнених клітин менша ніж m + n - 1.

Угорський метод.

Симплекс-метод.

Метод потенціалів.

Метод мінімальної вартості.

Він працює лише з квадратними матрицями вартості перевезень.

Він завжди гарантує отримання оптимального плану.

Він заповнює клітини послідовно від верхнього лівого кута до нижнього правого, ігноруючи вартість тарифів.

Він обирає маршрути з найвищими тарифами для їхнього подальшого виключення послідовно від верхнього правого кута до нижнього лівого.

u + v = c

u - v = c

u * v = c

u + v <= c

Усі потенціали рядків та стовпців мають однакові знаки.

У матриці не залишилося жодної вільної клітини.

Хоча б для однієї вільної клітини сума потенціалів є більшою 0.

Для всіх вільних клітин виконується умова: сума потенціалів мінус тариф менше або дорівнює 0.