В моделях 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; |
Схема элементов рассматриваемой индексированной коллекции:
|