Во многих приложениях нас интересует только подмножество всех упорядоченных пар из двух множеств. Например, в транспортной модели отгрузки могут быть невозможны из всех источников во все пункты назначения. Стоимость доставки за единицу может быть указана только для используемых дуг ORIG – DEST, поэтому желательно индексировать затраты и переменные только по этим парам. В терминах AMPL мы хотим, чтобы набор LINKS, содержал только подмножество пар, заданных в данных, а не все пары из ORIG и DEST.
Недостаточно объявить набор LINKS, потому что он объявляет только набор отдельных элементов. Как минимум, мы должны сказать:
set LINKS dimen 2;
чтобы указать «размерность» набора, т.е. данные должны состоять из двух элементов, то есть пар элементов. Более того, мы можем сказать, что LINKS является подмножеством набора всех пар из ORIG и DEST:
set LINKS within {ORIG,DEST};
Такое объявление имеет преимущество, что делает намерение модели более ясным. Это также помогает отлавливать ошибки в данных. Последующие объявления параметра cost, переменной Trans и целевой функции остаются такими же, как в предыдущем разделе. Но компоненты cost[i,j] и Trans[i,j] теперь будут определяться только для тех пар, которые указаны в данных как элементы LINKS, а выражение:
sum{(i,j) in LINKS}cost[i,j] * Trans[i,j]
будет представлять сумму только по заданным в LINKS парам.
При таком способе задания LINKS нужно переопределить ограничения. Когда LINKS задана и является подмножеством пар и мы пытаемся суммировать Trans[i,j] по каждому j в DEST, в то время как Trans[i,j] определен только для пар (i,j) in LINKS:
subject to Supply {i in ORIG}: sum{j in DEST} Trans[i,j] = supply[i];
Если мы сделаем так, мы получим сообщение об ошибке.
Для того что бы не было ошибки необходимо записать вместо:
sum{j in DEST} Trans[i,j] -> sum{j in DEST: (i,j) in LINKS}
Однако вместо того, чтобы требовать эту несколько неудобную форму, AMPL позволяет убрать j in DEST из выражения индексации, чтобы получить следующее более краткое ограничение:
subject to Supply {i in ORIG}: sum{(i,j) in LINKS} Trans[i,j] = supply[i];
Поскольку {(i,j) in LINKS} появляется в контексте, где i уже был определен, AMPL интерпретирует это индексное выражение как набор всех j, для которых существует пары (i,j) in LINKS. Ограничение спроса обрабатывается аналогичным образом, и вся пересмотренная версия модели примет следующий вид:
set ORIG; # origins
set DEST; # destinations
set LINKS within {ORIG,DEST};
param supply{ORIG} >= 0; # amounts available at origins
param demand{DEST} >= 0; # amounts required at destinations
check: sum{i in ORIG} supply[i] = sum{j in DEST}demand[j];
param cost{LINKS} >= 0; # shipment costs per unit
var Trans{LINKS} >= 0; # units to be shipped
minimize Total_Cost: sum {(i,j) in LINKS}cost[i,j] * Trans[i,j];
subject to Supply {i in ORIG}: sum{(i,j) in LINKS}Trans[i,j] = supply[i];
subject to Demand {j in DEST}: sum{(i,j) in LINKS}Trans[i,j] = demand[j];
data;
param: ORIG: supply :=
GARY 1400 CLEV 2600 PITT 2900 ;
param: DEST: demand :=
FRA 900 DET 1200 LAN 600 WIN 400
STL 1700 FRE 1100 LAF 1000 ;
param: LINKS: cost :=
GARY DET 14 GARY LAN 11 GARY STL 16 GARY LAF 8
CLEV FRA 27 CLEV DET 9 CLEV LAN 12 CLEV WIN 9
CLEV STL 26 CLEV LAF 17
PITT FRA 24 PITT WIN 13 PITT STL 28 PITT FRE 99 ;
Рисунок 1: Транспортная модель.
AMPL предлагает множество удобных способов указать членство составных наборов и данных, индексированных по ним, как объяснено в последующих главах. В примере выше видно, что индексное выражение {(i,j) in LINKS} означает что-то разное в каждом из трех мест, где оно появляется. Его членство может быть понято с точки зрения таблицы:
FRA DET LAN WIN STL FRE LAF GARY x x x x CLEV x x x x x x PITT x x x x
Рисунок 2: Заданное подмножество доступных направлений движения
Строки представляют источники а столбцы потребителей, в то время как каждая пара в наборе отмечена знаком x. Таблица для {ORIG, DEST} будет полностью заполнена x, в то время как показанная таблица отображает связи только для подмножества LINKS, определенного данными.
Там, где i и j в настоящее время не определены, например, для цели:
minimize Total_Cost: sum{(i,j) in LINKS}cost[i,j] * Trans[i,j];
индексное выражение {(i,j) in LINKS} представляет все пары таблицы LINKS. Но в тот момент, когда i был определен ранее, например, в ограничении предложения:
subject to Supply {i in ORIG}: sum{(i,j) in LINKS} Trans[i,j] = supply[i];
выражение {(i,j) in LINKS} ассоциируется только со строкой таблицы, соответствующей с ранее заданным индексом i. Можно подумать об этом как об использовании одномерного «среза» таблицы по строке, соответствующей ранее определенному i. Однако, в этом случае i является предварительно определенным фиктивным индексом. То же самое соглашение применяется, когда первый компонент элемента набора является любым выражением, которое может быть оценено как набор. Мы могли бы написать: {("GARY", j) in LINKS} для представления пар только первой строки таблицы.
Точно так же, для случаев когда j уже был определен: например, для ограничения спроса:
subject to Demand {j in DEST}: sum{(i,j) in LINKS}Trans[i,j] = demand[j];
выражение {(i,j) in LINKS} выбирает пары из столбца таблицы, соответствующего только j.
Пары для третьего столбца таблицы могут быть указаны с помощью записи: {(i,"LAN") in LINKS}.
