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

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

Исходная информация:

M_i - количество единиц груза в i -м пункте отправления (i = 1, 2, …, k);

N_j - потребность в j -м пункте назначения (j = 1, 2, …, l) (в единицах груза);

a_ij - стоимость перевозки единицы груза из i -гo пункта в j -й.

Обозначим через x_ij планируемое количество единиц груза для перевозки из i -ro пункта в j -й.

В принятых обозначениях:

- общая (суммарная) стоимость перевозок;

- количество груза, вывозимого из i -ro пункта;

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

В простейшем случае должны выполняться следующие очевидные условия:

Таким образом, математической формулировкой транспортной задачи будет:

найти

при условиях

; ;

Эта задача носит название замкнутой (закрытой, сбалансированной) транспортной модели.

Заметим, что условие является естественным условием разрешимости замкнутой транспортной задачи.

Более общей транспортной задачей является так называемая открытая (несбалансированная) транспортная модель:

найти

при условиях

; ;

Ясно, что в этой задаче не предполагается, что весь груз, накопленный в i -м пункте, должен быть вывезен.