Если бы мы до сих пор использовали оптимальное решение для любой из наших моделей, нам пришлось бы отправлять каждую из упаковок, автомобилей или чего-либо еще по некоторому пути от узла поставки (или входа) к узлу спроса (или выхода). Значения переменных решения напрямую не говорят о том, каковы оптимальные пути или какой поток должен пройти по каждому из них. Однако обычно не так сложно определить эти пути, особенно когда сеть имеет регулярную или особую структуру.
Если в сети есть только одна единица предложения и одна единица спроса, оптимальное решение принимает совершенно иную природу. Переменная, связанная с каждой дугой, равна 0 или 1, и дуги, чьи переменные имеют значение 1, представляют собой путь с минимальными затратами от узла предложения до узла спроса. Часто «затраты» на самом деле представляют собой время или расстояние, так что оптимум дает кратчайший путь.
Нужно внести всего несколько изменений в модель максимального потока, показанную выше, чтобы превратить ее в модель нахождения кратчайшего пути. Есть еще параметр и переменная, связанная с каждой дорогой от i до j, мы называем их time[i,j] и Use[i,j]. Сумма их произведений дает формулировку целевой функции:
param time {ROADS} >= 0; # times to travel roads
var Use {(i,j) in ROADS} >= 0; # 1 iff (i,j) in shortest path
minimize Total_Time: sum {(i,j) in ROADS} time[i,j] * Use[i,j];
Поскольку только переменные Use[i,j] на оптимальном пути, равны 1, а остальные равны 0, эта сумма правильно отображает общее время прохождения оптимального пути. Единственное изменение - это добавление ограничения, гарантирующего, что на входе в сеть доступна ровно одна единица потока:
subject to Start: sum {(entr,j) in ROADS} Use[entr,j] = 1;
Полная модель показана на ниже.
set INTER; # intersections
param entr symbolic in INTER; # entrance to road network
param exit symbolic in INTER, <> entr; # exit from road network
set ROADS within (INTER diff {exit}) cross (INTER diff {entr});
param time {ROADS} >= 0; # times to travel roads
var Use {(i,j) in ROADS} >= 0; # 1 iff (i,j) in shortest path
minimize Total_Time: sum {(i,j) in ROADS} time[i,j] * Use[i,j];
subject to Start: sum {(entr,j) in ROADS} Use[entr,j] = 1;
subject to Balance {k in INTER diff {entr,exit}}:
sum {(i,k) in ROADS} Use[i,k] = sum {(k,j) in ROADS} Use[k,j];
data;
set INTER := a b c d e f g ;
param entr := a ;
param exit := g ;
param: ROADS: time :=
a b 50, a c 100
b d 40, b e 20
c d 60, c f 20
d e 50, d f 60
e g 70, f g 70 ;
Если мы представим, что числа на дугах на рисунке 1 - это время в минутах, а не пропускная способность, данные будут одинаковыми. AMPL находит решение следующим образом:
ampl: model netshort.mod; ampl: solve; MINOS 5.5: optimal solution found. 1 iterations, objective 140 ampl: option omit_zero_rows 1; ampl: display Use; Use := a b 1 b e 1 e g 1 ;
Кратчайший путь - это путь: a → b → e → g, который занимает 140 минут.
