2014-02-02
621
Основная транспортная задача
Сформулируем основную транспортную задачу, которая носит еще название стандартной транспортной задачи.
Пусть существует множество источников, в которых производятся товары 
. Кроме этого имеется множество стоков, где потребляются товары 
. Между источниками и стоками имеются связи 
(Рисунок 20).
Для того, чтобы перевезти единицу товара из i в j, требуется заплатить 
денежных единиц.
Задача теперь состоит в том, чтобы перевезти товары из пунктов производства в пункты потребления с минимальными затратами. Таким образом, необходимо минимизировать целевую функцию следующего вида
при условиях
;
.
Рисунок 20. К формулировке стандартной транспортной задачи
Первое условие означает, что сумма вывозимых товаров по ik направлениям из источника i не должна превышать количество товара, произведенного в i -ом источнике.
Второе условие показывает, что количество ввозимого товара по ij направлениям в j -й сток может быть больше или равно количеству потребляемых товаров. Если 
, то в стоках j будут образовываться накопления товаров.
Таким образом, для того чтобы в транспортной задаче получилось допустимое решение, необходимо
.
В предыдущем разделе мы познакомились с постановками сетевых задач, в которых было много пунктов производства и много пунктов потребления. Причем поток мог быть послан из любого произвольного пункта отправления в любой произвольный пункт назначения.
Если требуется, чтобы поток из определенных пунктов отправления должен быть послан в определенные пункты назначения, то мы получаем новый класс задач – задачи о многопродуктовых потоках.
Особый случай многопродуктовых потоков – когда каждый поток идет только из одного определенного пункта отправления только в один определенный пункт назначения.
Для общего потока из узла А в узел В используем обозначение 
и введем следующее определение.
