Алгебраическая нотация AMPL имеет большие возможности для выражения множества линейных сетевых программ, но результирующие выражения ограничений часто не так естественны, как хотелось бы.
В то время как идею ограничения «исходящий поток минус входящий» на каждом узле легко описать и понять, соответствующие алгебраические ограничения имеют тенденцию включать такие термины, как
sum {(i,k) in LINKS} Ship[i,k]
Алгебраические формулировки сетевых потоков имеют тенденцию быть проблематичными, поскольку они построены явно в терминах переменных и ограничений, в то время как узлы и дуги неявным способом включены в состав ограничений. Люди предпочитают подходить к проблемам сетевого потока с другой стороны. Они воображают, что дают явное определение узлов и дуг, из которых неявно возникают переменные потока и ограничения баланса. Чтобы справиться с этой ситуацией, AMPL предлагает альтернативу, которая позволяет объявлять концепцию сети непосредственно в модели.
Сетевые расширения AMPL включают два новых типа объявлений, node и arc, которые заменяют объявления subject to и var в формулировке алгебраических ограничений. Объявления node называют узлы сети и характеризуют ограничения баланса потоков в узлах. Объявления arc называют и определяют дуги, которые соединяют дуги, и предоставляют дополнительную информацию, такую как границы и стоимость, которые связаны с дугами.
Переписывая модель:
set CITIES;
set LINKS within (CITIES cross CITIES);
param supply {CITIES} >= 0; # amounts available at cities
param demand {CITIES} >= 0; # amounts required at cities
check: sum {i in CITIES} supply[i] = sum {j in CITIES} demand[j];
param cost {LINKS} >= 0; # shipment costs/1000 packages
param capacity {LINKS} >= 0; # max packages that can be shipped
var Ship {(i,j) in LINKS} >= 0, <= capacity[i,j];
# packages to be shipped
minimize Total_Cost:
sum {(i,j) in LINKS} cost[i,j] * Ship[i,j];
subject to Balance {k in CITIES}: supply[k] + sum {(i,k) in LINKS} Ship[i,k] = demand[k] + sum {(k,j) in LINKS} Ship[k,j];
используя node и arc, мы можем сохранить все объявления наборов и параметров и связанные данные. Изменения затрагивают только три объявления - minimize, var, and subject to - которые определяют линейную программу.
В сети есть узел для каждого элемента набора CITIES. Используя объявление узла, мы можем сказать это напрямую:
node Balance {k in CITIES}: net_in = demand[k] - supply[k];
Ключевое слово net_in означает «чистый вход», то есть спрос за вычетом предложения, поэтому в этом объявлении говорится, что чистый поток должен равняться чистому спросу в каждом узле Balance[k]. Таким образом, он говорит то же самое, что и ограничение с именем Balance[k] в алгебраической версии, за исключением того, что вместо длинного выражения используется краткий термин net_in.
sum {(i,k) in LINKS} Ship[i,k] - sum {(k,j) in LINKS} Ship[k,j]
На самом деле, синтаксис subject to и node практически одинаков, за исключением того, что указано ограничение сохранения потока. (Ключевое слово net_out также может использоваться для обозначения предложения за вычетом спроса, так что мы могли бы написать
net_out = supply[k] - demand[k]
В сети есть дуга для каждой пары в наборе LINKS. Это тоже можно сказать напрямую, используя объявление дуги:
arc Ship {(i,j) in LINKS} >= 0, <= capacity[i,j],
from Balance[i], to Balance[j], obj Total_Cost cost[i,j];
Дуга Ship[i,j] определена для каждой пары в LINKS с границами 0 и capacity[i,j] для ее потока. В этом смысле описания arc и var совпадают. Однако объявление arc содержит дополнительные фразы, чтобы сказать, что дуга проходит от узла с именем Balance[i] до узла с именем Balance[j] с линейным коэффициентом cost[i,j] и целевой функцией с именем Total_Cost. В этих фразах используются ключевые слова from, to и obj.
Поскольку информация о целевой функции включена в объявление arc, тогда ее объявление minimize, сводится к следующему виду:
set LINKS within (CITIES cross CITIES);
param supply {CITIES} >= 0; # amounts available at cities
param demand {CITIES} >= 0; # amounts required at cities
check: sum {i in CITIES} supply[i] = sum {j in CITIES} demand[j];
param cost {LINKS} >= 0; # shipment costs/1000 packages
param capacity {LINKS} >= 0; # max packages that can be shipped
minimize Total_Cost;
node Balance {k in CITIES}: net_in = demand[k] - supply[k];
arc Ship {(i,j) in LINKS} >= 0, <= capacity[i,j],
from Balance[i], to Balance[j], obj Total_Cost cost[i,j];
Как следует из этого описания, arc и node заменяют var и subject соответственно. Фактически AMPL рассматривает объявление дуги как определение переменных, так что нужно все равно указать display Ship, чтобы посмотреть на оптимальные потоки в сетевой модели. AMPL рассматривает объявление узла как определение ограничений. Разница в том, что использование нотации arc и node позволяет просто и точно задать условия сетевой задачи. Сначала всегда идет описание узлов, за которым следует описание того, как дуги соединяют узлы.
