Задача о перевозках (транспортная задача)

Имеется m складов, n пунктов потребления, связанных сетью дорог с определенными тарифами перевозок. При этом с_ij – стоимость перевозки единицы груза из i -го склада в j -й пункт потребления. На складах имеются запасы однородного товара в количествах a₁,…, a_i,…, a_m. Пункты потребления подают заявки, соответственно, на единицы товара b₁,…, b_j,…, b_n. Необходимо составить план перевозок, т. е. Указать, с какого склада, в какие пункты потребления и какое количество товаров нужно отправлять, чтобы заявки были выполнены, а общие расходы на перевозки были бы минимальными.

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

Заявки считаются выполнимыми, если , т. е. сумма заявок не превышает всех запасов. Это будет дополнительным условием задачи.

Количество взятого с каждого склада товара не должно превышать имеющегося запаса, поэтому

или в свернутом виде

. (3.11)

Заявки, поданные пунктами потребления, должны быть выполнены, следовательно:

или . (3.12)

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

. (3.13)

Это и будет целевая функция транспортной задачи.