Формулировка и область применения транспортной задачи

Методы линейного программирования, одним из которых является транспортная задача, имеют широкое применение в экономике. С их помощью можно оптимизировать загрузку оборудования, распределение ресурсов или специалистов по заданиям, повышать эффективность использования финансовых ресурсов.

В распределительной логистике транспортная задача применяется для организации эффективного распределения потоков товаров от нескольких производителей к нескольким потребителям. В случае различной стоимости перевозки единицы груза между разными предприятиями возникает вопрос: какие потребители должны снабжаться первым производителем (первым складом, распределительным центром и т.д.), какие – вторым и так далее.

Даже при изучении простейшей транспортной системы, состоящей из трех производителей и трех потребителей, существует множество вариантов распределения потоков товаров. Перед логистом встает задача выбора из этих вариантов оптимального. В зависимости от поставленной перед ним задачи он может выбрать вариант распределения, характеризующийся наименьшими транспортными издержками, наименьшими затратами времени, наименьшим износом транспортных средств и т.д.

Для того чтобы сформулировать транспортную задачу, необходима следующая информация:
n – число поставщиков;
m – число потребителей;
ai – запасы товаров, имеющиеся у i-го поставщика (i = 1, 2, …, n); bj – потребности j-го потребителя (j = 1, 2, …, m);
cij – затраты на транспортировку единицы груза от i-го поставщика к j-му потребителю.

В качестве управляемых переменных xij выбирают количество товара, доставляемого от i-го поставщика к j-му потребителю.
Таким образом, целевая функция транспортной задачи может быть записана в виде

При этом нам подходит не любой набор управляемых переменных xij. На них должны быть наложены некоторые ограничения. Прежде всего значения xij должны быть неотрицательны (отрицательная перевозка с точки зрения экономики бессмысленна), т.е.

Следующее ограничение может быть задано различным образом. Например, мы формулируем простейшую, замкнутую транспортную задачу, в которой вся продукция должна быть распределена и все потребности должны быть удовлетворены этой продукцией

В этом случае объем перевозок от i-го производителя должен равняться мощности этого производителя, а количество товаров, доставленных j-му потребителю, должно соответствовать объему его потребностей. Это ограничение записывается следующими системами уравнений:

Возможны ситуации, когда сумма произведенных товаров не совпадает с суммой потребностей. В этом случае транспортная задача называется несбалансированной (или незамкнутой). Ограничения в этом случае превращаются в неравенства и записываются в виде