Сбалансированная транспортная задача

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

В качестве примера рассмотрим задачу с двумя пунктами отправления и тремя пунктами назначения, схема которой показана на рис.4.1. Здесь а ₁ и а ₂ – количество груза, которым располагают пункты отправления, b ₁, b ₂, b ₃ – потребности в грузе пунктов назначения.

Задача является сбалансированной, если суммарная потребность равна суммарной возможности. В нашем примере это значит, что

Рис. 4.1.

Если ввести обозначения:

x_ij - количество груза, перевозимого из i- го пункта отправления в j -й пункт назначения;

С_ij – затраты на перевозку единицы груза из i -го пункта отправления в j -й пункт назначения,

то исходные данные вместе с переменными можно представить в одной таблице (табл. 4.3):

Таблица 4.3

Пункты	B1	B2	B3	Количество груза
A1	С 11 Х 11	С 12 Х 12	С 13 Х 13	a 1
A2	С 21 Х 21	С 22 Х 22	С 23 Х 23	a 2
Потребность в грузе	b 1	b 2	b 3

Так как необходимо минимизировать суммарные затраты по перевозке, то целевая функция запишется в виде

L=C ₁₁ x ₁₁ + C ₁₂ x ₁₂ + C ₂₃ x ₂₃ → min.

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

B₁: x ₁₁ +x ₂₁ =b ₁;

B₂: x ₁₂ +x ₂₂ =b ₂;

B₃: x ₁₃ +x ₂₃ =b ₃.

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

А₁: х ₁₁ +х ₁₂ +х ₁₃ =а ₁;

А₂: х ₂₁ +х ₂₂ +х ₂₃ =а ₂.

Наконец, физический смысл переменных накладывает на них ограничение неотрицательности

" x_ij³ 0.

В результате мы получили модель транспортной задачи, содержащей только линейные функции. Очевидно, что характер модели не изменится при увеличении числа пунктов.