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

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

Постановка транспортной задачи. Имеется n поставщиков однотипного, взаимозаменяемого груза, запасы которого равны a ₁, a ₂, …, a_n, и m потребителей этого груза с потребностями b ₁, b ₂, …, b_m. Стоимость поставки одной единицы груза от i –го поставщика к j –му потребителю равна c_ij. Требуется минимизировать суммарную стоимость поставок груза с тем, чтобы, с одной стороны удовлетворить спрос потребителей, и, с другой стороны, не превысить запасы поставщиков.

Математическая формализация задачи такова. Обозначим через x_ij количество груза, поставляемого от i –го поставщика к j –му потребителю. Тогда суммарная стоимость перевозок равна , а ограничения, связанные с запасами поставщиков и потребностями потребителей выглядят следующим образом:

Таким образом, требуется решить задачу

Запишем данные в виде таблицы:

			…	m
…
n

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

.

Для закрытых задач ограничения на спрос и предложение выполняются в виде равенства:

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