Основная транспортная задача

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

Пусть существует множество источников, в которых производятся товары . Кроме этого имеется множество стоков, где потребляются товары . Между источниками и стоками имеются связи (Рисунок 17).

Рисунок 17 – К формулировке стандартной транспортной задачи

Для того, чтобы перевезти единицу товара из i в j, требуется заплатить денежных единиц.

Задача теперь состоит в том, чтобы перевезти товары из пунктов производства в пункты потребления с минимальными затратами. Таким образом, необходимо минимизировать целевую функцию следующего вида

при условиях

;

Первое условие означает, что сумма вывозимых товаров по ik направлениям из источника i не должна превышать количество товара, произведенного в i-ом источнике.

Второе условие показывает, что количество ввозимого товара по ij направлениям в j-й сток может быть больше или равно количеству потребляемых товаров. Если , то в стоках j будут образовываться накопления товаров.