На рисунке:
который мы использовали для иллюстрации проблемы максимального потока, есть три типа пересечений, представленных узлами:
- где входит трафик;
- где трафик уходит;
- где поток трафика сохраняется.
Таким образом, модель сети может иметь три соответствующих объявления узлов:
node Entr_Int: net_out >= 0;
node Exit_Int: net_in >= 0;
node Intersection {k in INTER diff {entr,exit}};
Условие net_out >= 0 подразумевает, что поток из узла Entr_Int может быть любым. Это правильное условие, поскольку на входном узле нет ограничения баланса. Аналогичный комментарий относится к условию для узла Exit_Int.
В этой сети есть одна дуга для каждой пары (i,j) в наборе ROADS. Таким образом, объявление должно выглядеть примерно так:
arc Traff {(i,j) in ROADS} >= 0, <= cap[i,j], # NOT RIGHT
from Intersection[i], to Intersection[j], obj Entering_Traff (if i = entr then 1);
Поскольку цель состоит в том, чтобы максимизировать общий трафик, покидающий входной узел, дуге дается коэффициент 1 в цели тогда и только тогда, когда i принимает значение entr. Однако, когда i принимает это значение, дуга определяется как Intersection[entr], которого не существует. Дуга должна быть из узла Entr_Int. Точно так же, когда j принимает значение exit, дуга должна быть не Intersection[exit], а в Exit_Int. AMPL перехватит эти ошибки и выдаст сообщение, в котором будет указан один из несуществующих узлов, на который была сделана ссылка. Может показаться разумным использовать if-then-else, чтобы обойти эту проблему следующим образом:
arc Traff {(i,j) in ROADS} >= 0, <= cap[i,j], # SYNTAX ERROR
from (if i = entr
then Entr_Int
else Intersection[i]),
to (if j = exit
then Exit_Int
else Intersection[j]),
obj Entering_Traff (if i = entr then 1);
Однако конструкция if-then-else в AMPL не применяется к таким компонентам модели, как Entr_Int и Intersection [i]. Эта версия будет отклонена как синтаксическая ошибка. Вместо этого нужно использовать фразы from и to, квалифицированные с помощью выражений индексации:
arc Traff {(i,j) in ROADS} >= 0, <= cap[i,j],
from {if i = entr} Entr_Int,
from {if i <> entr} Intersection[i],
to {if j = exit} Exit_Int,
to {if j <> exit} Intersection[j],
obj Entering_Traff (if i = entr then 1);
Специальное выражение индексации, начинающееся с if, работает здесь почти так же, как и для ограничений. Фраза from или to обрабатывается, если выполняется условие, следующее за if. Таким образом, Traff [i, j] объявлен как происходящий из Entr_Int, если i равно entr, и как происходящий из Intersection[i], если i не равно entr.
В качестве альтернативы можно объединить объявления трех разных типов узлов в одно. Заменив, положительный или нулевой net_out на Entr_Int, отрицательный или нулевой на Exit_Int и ноль для всех других узлов Intersection[i]. В результате можно объявить:
node Intersection {k in INTER}: (if k = exit then -Infinity)<= net_out <= (if k = entr then Infinity);
Узлы, которые ранее были объявлены как Entr_Int и Exit_Int, теперь являются просто Intersection[entr] и Intersection[exit]. Следовательно, объявленные дуги, которое ранее выдавали ошибку, теперь работают нормально. Выбор между этой версией и предыдущей находится полностью в плоскости удобства и вкуса пользователя. (Бесконечность Infinity - это предопределенный параметр AMPL, который может использоваться для указания любой «бесконечно большой» границы. Возможно, наиболее удобная и привлекательная формулировка AMPL не соответствует ни одному из вышеперечисленных, а скорее происходит из-за несколько иной интерпретации сетевой диаграммы, изображенной выше. Предположим, что мы видим стрелки во входной узел и из него. Выходной узел как представляющий дополнительные дуги, которые оказываются смежными только с одним узлом, а не с двумя. Затем поток равен потоку на каждом пересечении, и объявление узла упрощается до: node Intersection {k in INTER}; Две дуги, «висящие» на входе и выходе, определены очевидным образом, но включают только фразу to или from:
arc Traff_In >= 0, to Intersection[entr]; arc Traff_Out >= 0, from Intersection[exit];
Дуги, представляющие дороги в сети, объявляются, как и раньше:
arc Traff {(i,j) in ROADS} >= 0, <= cap[i,j],
from Intersection[i], to Intersection[j];
Когда модель представлена таким образом, цель состоит в том, чтобы максимизировать Traff_In (или эквивалентно Traff_Out). Мы могли бы сделать это, добавив фразу obj к объявлению дуги для Traff_In, но в этом случае, возможно, яснее определить цель алгебраически:
maximize Entering_Traff: Traff_In;
В итоге мы получим следующую версию модели:
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 cap {ROADS} >= 0; # capacities of roads
node Intersection {k in INTER};
arc Traff_In >= 0, to Intersection[entr];
arc Traff_Out >= 0, from Intersection[exit];
arc Traff {(i,j) in ROADS} >= 0, <= cap[i,j],
from Intersection[i], to Intersection[j];
maximize Entering_Traff: Traff_In;
data;
set INTER := a b c d e f g ;
param entr := a ;
param exit := g ;
param: ROADS: cap :=
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 ;
