В моделях AMPL наиболее распространены объявления отдельных наборов. Наборы также могут быть объявлены в коллекциях, индексированных по другим наборам. Индексирование наборов по наборам бывает достаточно полезным. В качестве примера того, как индексированные наборы наборов могут быть полезны, мы рассмотрим многопериодную модель производства: Начнем с объявления наборов:
set PROD;
set AREA{PROD};
Сделанная запись означает, что для каждого элемента p в PROD имеется по крайней мере один элемент в AREA[p]. Элементы AREA[p] обозначают места продажи товара.
set PROD:= bands coils;
set AREA[bands]:= east north;
set AREA[coils]:= east west export;
set FN{NUTR} within FOOD;
Таким образом, для каждого элемента набора NUTR имеется набор значений (переменной длинны) из подмножества FOOD. Спрос, ожидаемые доходы от продаж и объемы продаж проиндексируем по заданным местам продажи, а также по продуктам и неделям:
param market(revenue){p in PROD, AREA[p], 1..T} >= 0;
var Sell{p in PROD, a in AREA[p], t in 1..T} >= 0,<= market[p,a,t];
Объявлением параметра revenue (доход от продаж) мы определяем только фиктивный индекс p для указания набора AREA [p]. Для переменных Sell нам необходимо определить все фиктивные индексы, т.к. верхняя граница продаж market [p, a, t] имеет 3 индекса. Это еще один пример, в котором индекс, определенный одной фразой выражения индексации, используется следующей за ним фразой. Таким образом каждый p из набора PROD пробегает все элементы другого набора AREA[p].
Вместо этого, мы могли бы записать эту модель с набором пар PRODAREA. Так, что продукт p будет продаваться в области a, если и только если (p,a) является элементом PRODAREA. Однако наша формулировка с точки зрения PROD и AREA[p] представляется более предпочтительной, поскольку она подчеркивает иерархические отношения между продуктами и областями.
set orig{PROD} within ORIG;
set dest{PROD} within DEST;
set links{p in PROD} = orig[p] cross dest[p];
Объявление links демонстрирует, индексированную коллекцию составных наборов, и что индексированная коллекция может быть определена с помощью операций над множествами из других индексированных коллекций.
Следующий код демонстрирует итоги:
set PROD = {"A", "B", "C"}; # Типы продуктов
set ORIG = setof{i in 1..5}"O"&i; # Узлы отгрузки
set DEST = setof{i in 1..5}"D"&i; # Узлы потребителей
set orig{PROD} within ORIG; # Склады с которых возможна поставка каждого PROD
set dest{PROD} within DEST; # Потребители в которых имеется потребность в PROD
set links{p in PROD} = orig[p] cross dest[p]; # Объявление доступных связей между ORIG и DEST
data;
set orig[A] = O1,O2,O3;
set orig[B] = O4,O5;
set orig[C] = O1,O2,O5;
set dest[A] = D1,D2,D3;
set dest[B] = D4,D5,D3;
set dest[C] = D1,D2,D3,D4,D5;
display links; ->
set links[A] :=
(O1,D1) (O1,D3) (O2,D2) (O3,D1) (O3,D3)
(O1,D2) (O2,D1) (O2,D3) (O3,D2);
set links[B] := (O4,D4) (O4,D5) (O4,D3) (O5,D4) (O5,D5) (O5,D3);
set links[C] :=
(O1,D1) (O1,D3) (O1,D5) (O2,D2) (O2,D4) (O5,D1) (O5,D3) (O5,D5)
(O1,D2) (O1,D4) (O2,D1) (O2,D3) (O2,D5) (O5,D2) (O5,D4);
display {p in PROD}: orig[p] union dest[p]; ->
amp: set ( orig['A']) union ( dest['A']) := O1 O2 O3 D1 D2 D3;
amp: set ( orig['B']) union ( dest['B']) := O4 O5 D4 D5 D3;
amp: set ( orig['C']) union ( dest['C']) := O1 O2 O5 D1 D2 D3 D4 D5;
Итеративные union & inter
В дополнение к ранее упомянутым операциям, существуют итеративные операторы объединения (union) и пересечения (inter) индексированных наборов. Операторы, которые применяются к наборам так же, как итеративная сумма применяется к числам:
display union {p in PROD} orig[p]; ->
set union {p in PROD} orig[p] := O1 O2 O3 O4 O5; (все элементы индексированного набора orig)
display inter {p in PROD} orig[p]; ->
set inter {p in PROD} dest[p] := D3; (элементы индексированного набора dest, которые встречаются для всех PROD)
subject to Multi {i in ORIG, j in DEST}: sum{p in PROD: (i,j) in links[p]} Trans[p,i,j] <= limit[i,j];
Здесь необходимо, после sum, использовать несколько неуклюжее индексирующее выражение {p in PROD: (i,j) in links[p]} для описания набора, которое не соответствует иерархической организации.
В общем, почти любая модель, которая может быть написана с помощью индексированных наборов, также может быть написана с помощью наборов кортежей.
Индексированные коллекции наиболее подходят для таких объектов, как продукты и области, виды работ и этапы, которые имеют иерархические отношения. С другой стороны, наборам из кортежей предпочтительнее иметь дело с такими объектами, как происхождение и пункты назначения, которые связаны симметрично.
Общий вид синтаксиса выражений при использовании итеративных операторов union & inter имеет следующий вид:
| Форма | Описание компонентов |
| opname indexing sexpr Пример: inter {p in PROD} orig[p]; |
opname: union или inter
indexing: индексное выражение sexpr: набор |
Ниже приведен небольшой пример использования индексированных наборов в модели. Эта запись определяет различный набор A[e] для каждого e в E:
param n;
set E:= {1..n};
set A{E};
var C{e in E, A[e]} >= 0 integer;
s.t. constraint{e in E}: sum{j in A[e]}C[e,j] >= 0;
Еще один пример формирования индексированной коллекции на основании значений параметра.
set supplier{t in T} = {n in N: pl[n,t] > 0};
Сортировка литерального индексируемого набора
set P2 = union{i in F1} P1[i] ordered by ASCII;
Power set (POW)
В случаях, когда необходимо проиндексировать компоненты модели по множеству всех комбинаций элементов набора, это можно представить с помощью следующей записи:
param n integer > 0;
set S := 0..n - 1;
set SS := 0..2**n - 1;
set POW {k in SS} := {i in S: (k div 2**i) mod 2 = 1};
Для n := 3 получим набор (display POW;):
set POW[1] := 0;
set POW[2] := 1;
set POW[3] := 0 1;
set POW[4] := 2;
set POW[5] := 0 2;
set POW[6] := 1 2;
set POW[7] := 0 1 2;
или
param n := 4;
set S := 1..(n-1);
set SS := 1..(2**(n-1) - 1);
set POW {k in SS} := {i in S: (k div 2**(i-1)) mod 2 == 1};
display POW:
set POW[1] := 1;
set POW[2] := 2;
set POW[3] := 1 2;
set POW[4] := 3;
set POW[5] := 1 3;
set POW[6] := 2 3;
set POW[7] := 1 2 3;
Для n элементов набора S, существует 2**n вариантов подмножеств S. Следовательно, существует взаимно-однозначное соответствие между элементами набора SS:= 0..2**n-1 и подмножествами S. Используя простое кодирование, можно сделать это соответствие явным. Индексированная коллекция наборов POW, описанная выше, объявляется так, чтобы POW[k] являлось k-м уникальным вариантом подмножества S. Чтобы увидеть весь набор POW, нужно ввести display POW)
То же самое можно сделать для произвольного упорядоченного множества S:
set S ordered;
param n:= card(S);
set SS:= 0..(2**n - 1);
set POW{k in SS}:= {i in S:(k div 2**(ord(i)-1)) mod 2 = 1};
В любом случае, можно использовать индексирование по POW, чтобы получить эффект индексации по всем подмножествам набора.
В следующем примере, каждый элемент s из S имеет вес Wt[s], а средний «вес» всех элементов каждого уникального подмножествa S не должен превышать n/2:
var Wt{S} >= 0;
subj to MaxWt{k in SS}: sum{i in POW[k]} Wt[i] <= (n/2) * card(POW[k]);
Составление индексированного набора на основании закономерности
В случаях, когда существует некоторая закономерность составления индексированного набора, например:
set An[1,1] := (1,1) (1,2) (2,1) (2,2); set An[1,2] := (1,1) (1,2) (2,1) (2,2); set An[1,3] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[1,4] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[2,1] := (1,1) (2,1) (1,2) (2,2); set An[2,2] := (1,1) (1,2) (2,1) (2,2); set An[2,3] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[2,4] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[3,1] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[3,2] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[3,3] := (3,3) (3,4) (4,3) (4,4); set An[3,4] := (3,3) (3,4) (4,3) (4,4); set An[4,1] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[4,2] := (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4); set An[4,3] := (3,3) (3,4) (4,3) (4,4); set An[4,4] := (3,3) (3,4) (4,3) (4,4);
В этом случае можно воспользоваться следующими формулировками:
(с использованием цикла for):
set S:= 1 .. 4;
set W:= {i in S, j in S};
set An{W} within {i in S, j in S};
for {i in S, j in S}
let An[i,j]:=
if {i}union{j} within 1..2 then {1..2,1..2} else if {i}
union{j} within 3..4 then {3..4,3..4} else {1..4,1..4};
Представленный цикл можно реализовать с использованием индексирования выражения let:
let {i in S, j in S}An[i,j]:=
if {i}union{j} within 1..2 then {1..2,1..2}
else if {i}union{j} within 3..4 then {3..4,3..4}
else {1..4,1..4};
С точки зрения скорости выполнения, - преимущество в формулировках следует отдать индексированному оператору let (он работает быстрее чем цикл for при большом S). Однако, для выражения сложных правил, цикл for имеет большую гибкость.
Действия с проиндексированными коллекциями наборов
Следующий пример отражает правила описания различных действий с проиндексированными коллекциями наборов:
set K:= {3,7,5}; # Объявление набора K
set W{K}; # Объявление индексированного по К набора W
param M{k in K} = sum{i in W[k]} i; # Объявление параметра M индексированого по набору K, значение элементов которого определяется формулой sum элементов индексного набора W
set LINKS within {k in K, j in W[k]}; # Объявление 2-D набора LINKS чьи элементы являются подрабором W[k]
Другой пример:
set A ordered := {'a','b', 'c'};
set B{A} ordered;
set C{A} ordered;
set Cat{i in A, B[i] union C[i]} ordered;
param dSC{i in A, B[i], C[i]}:= 5;
param D{i in A, j in B[i], k in C[i], n in 1..4:
ord0(j,B[i]) = n and ord0(k,C[i]) = n}:= dSC[i,j,k];
data;
set B[a]:= Ba1, Ba2;
set B[b]:= Bb1;
set B[c]:= Bc1;
set C[a]:= Ca1, Ca2;
set C[b]:= Cb1, Cb2;
set C[c]:= Cc1;
set Cat[a,Ba1]= aBa1_1, aBa1_2, aBa1_3;
set Cat[a,Ba2]= aBa2;
set Cat[a,Ca1]= aCa1, aCa1_2;
set Cat[a,Ca2]= aCa2, aCa2_2;
set Cat[b,Bb1]= bBb1_1, bBb1_2;
set Cat[b,Cb1]= bCb1, bCb1_2;
set Cat[b,Cb2]= bCb2_1, bCb2_2;
set Cat[c,Bc1]= cBc1_1;
set Cat[c,Cc1]= cCc1, cCc1_2;
### Category ###
display sum{i in A, j in B[i] union C[i]}card(Cat[i,j]),
{i in A} sum{j in B[i] union C[i]}card(Cat[i,j]);
### B[i] & С[i] ###
display B,C, sum{i in A}(card(B[i]) + card(C[i]));
### B[i] || С[i] ###
display {i in A}first(B[i]), {i in A}member(1,B[i]),{i in A}card(B[i]),
/* !!! */ {i in A, j in B[i]} ord0(j,B[i]), {i in A} ord0(i,A);
display B['a'], B['b'];
### A ###
display {i in A: first(B[i])=='Ba1'}, {i in A: member(1,B[i])= 'Ba1'}, {i in A: ord(i) = 1};
display D;
Использование параметра вместо одноэлементного индексированного набора
Например, имеется индексированных набор Wx[1]=2, Wx[2]=2, ..., Wx[n]=2. В том случае, когда индексированный набор включает в себя 1 элемент, тогда вместо:
set W2 in W1;
subject to Constraint {x in W1: x in W2}: sum {r1 in Rc} Y[r1, x] <= sum{j in L1} A[x, j];
где: param Wx{X1} = set W2;
Лучше записать:
param Wx{X1} in W1;
s.t. Constraint {x in X1}: sum{r1 in Rc} Y[r1, Wx [x]] <= sum{j in L1} A[Wx[x], j];
В примере параметр Wx [x] используется как индекс в выражениях переменных Y [r1, Wx [x]] и A [Wx, j]. Одним из применений индексации переменной параметром является моделирование специального узла в сети, как при использовании параметра entr в netmax.mod из книги AMPL.
Многоуровневые индексированные коллекции
reset;
param nWorker; # Количество сотрудников
set W = 0..nWorker-1; # Набор сотрудников
param nClique{W} default 1; # Количество цехов в которых может работать сотрудник
set C{w in W} = 0..nClique[w]-1; # закрепление сотрудников за несколькими цехами
set CLIQUE{w in W, c in C[w]} within W; # Закрепление за сотрудником станков в цехах к которым они имеют доступ
param y {W};var X {W, W};data;param nWorker := 9;param nClique := 0 5 1 3 ;param y := 0 22 1 33 ;set CLIQUE[0,0] := 0 2 ;set CLIQUE[0,1] := 2 3 ;set CLIQUE[0,2] := 3 4 ;set CLIQUE[0,3] := 4 6 ;set CLIQUE[0,4] := 8 ;set CLIQUE[1,0] := 1 2 3 ;set CLIQUE[1,1] := 3 4 7 ;set CLIQUE[1,2] := 4 6 7 ;display W, nClique, C; |
Схема элементов рассматриваемой индексированной коллекции:
|
