Транспортная задача по критерию стоимости

Введем следующие обозначения :

- пропускная способность дуги ;

- стоимость прохождения единицы потока по дуге ;

_{ij =}  - поток, пропускаемый по дуге .

Сформулируем транспортную задачу следующим образом .

Дано :

• транспортная сеть с наибольшим потоком  ;

• матрица пропускных способностей

• матрица стоимостей прохождения единицы потока по дуге

• вектор распределения потоков на истоке сети

• вектор распределения потоков на стоке сети

Ограничения :

 , , (14)

 , , (15)

 , . (16)

Требуется найти такое распределение потока  по дугам транспортной сети Ф =  что величина W =  (17) будет минимальной.

Для решения этой задачи следует рассматривать величины d_ij как длины соответствующих дуг. В этом случае стоимость прохождения потока  по какому-либо пути  от х₀ до z будет равна произведению длины этого пути на значение потока  , и задача минимизации стоимости потока сведется к решению рассмотренной ранее задачи нахождения кратчайшего пути в графе от х₀ до z. Если нет ограничений на пропускную способность дуг, то кратчайшим путем является тот, который обеспечивает минимальную стоимость прохождения потока.

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