Постановка задачі

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

Зроблений у пунктах виробництва продукт повинен бути доставлений до пунктів споживання причому обсяг споживання в пункті складає одиниць продукту.

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

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

Формально задача ставиться наступним чином. Нехай — кількість продукту, що перевозиться з пункту в пункт Потрібно визначити сукупність з mn величин які відповідають умовам:

1.

2.

3.

і для яких лінійна форма набуває найменшого значення.

Група обмежень (1)-(2) пов'язана з тою обставиною, що обсяг вивезеного з кожного пункту виробництва продукту в точності дорівнює обсягу виробленого в цьому пункті продукту, а обсяг ввезеного в пункт споживання продукту відповідає його потребі. За цих обмежень необхідною і достатньою умовою для розв'язності транспортної задачі є виконання умови балансу:

Приклад

Умови транспортної задачі зручно записувати за допомогою таблиці, що називається транспортною таблицею. Подана нижче таблиця відображає задачу з трьома пунктами виробництва що виробляють 15, 25 і 10 одиниць товару і чотирма пунктами споживання попит в яких рівний, відповідно 5, 15, 15 і 15. На перетині рядка і подається значення — вартість транспортування товару з пункту i в пункт j. Для даної задачі, наприклад рівне 9, тобто транспортування одиниці товару з пункту в пункт коштує 9 грошових одиниць.

Дата добавления: 2015-11-16