Условие принадлежности элементов множеству — Пример 1

Следующий пример иллюстрирует использование метода условия принадлежности элементов при определении разреженного множества. В задачах поиска соответствий имеется N объектов, которые мы хотим составить пары с минимальными затратами. Предположим, что мы хотим разместить жильцов в общежитии, по два в комнате. Пара (I,J) не различима с парой (J,I), так что для определенности положим, что в каждой паре I<=J (формально мы требуем, что I и J образуют множество упорядоченных пар). Другими словами, мы не хотим образовывать излишне упорядоченные пары из I и J, а только те, для которых I<=J).

Это иллюстрируется в следующем примере (файл MATCH.LNG в поддиректории “Samples”):

MATCH.LNG

MODEL:

1] Образование пар из объектов;

2] SETS:

3]!Объекты;

4] OBJ / 1..8 /;

5]! Каждая конкретная пара характеризуется затратами C на ее подбор и индикатором 0/1 (да/нет);

6] PAIR(OBJ, OBJ) | &1 #LT# &2: C, X;

7] ENDSETS

8]

9]!Минимизировать общие затраты по подбору пар;

10] MIN = @SUM(PAIR(I, J): C(I, J) *X(I, J));

11]!; Каждый объект должен быть сопоставлен только с одним другим объектом

12] @FOR(OBJ(I):

13] @SUM(PAIR(J, K) | J #EQ# I #OR# K #EQ# I:

14] X(J, K)) = 1;);

15] @FOR(PAIR(J, K): @BIN(X));

16] DATA:

17] C = 9, 3, 4, 2, 1, 5, 6,

18] 1, 7, 3, 5, 2, 1,

19] 4, 4, 2, 9, 2,

20] 1, 5, 5, 2,

21] 8, 7, 6,

22] 2, 3,

23] 4;

24] ENDDATA

END

Строка 4 определяет восемь объектов, из которых мы хотим образовать пары.

Строка 6 образует эти пары:

PAIR(OBJ, OBJ) | &1 #LT# &2: C, X;

Заметим, что оба элемента в этих парах производятся из единственного примитивного множества OBJ. Здесь мы вводим условие принадлежности, которому должны удовлетворять элементы множества пар (PAIR). &1 должно быть меньше чем (#LT#) &2. Здесь &1 и &2 индексные заполнители LINGO (placeholders) для первого и второго элементов пары. Это условие требует, чтобы номер индекса первого элемента пары меньше номера индекса второго элемента. В результате LINGO будет считать, например, пару (3,5) допустимой, исключая пару (5,3).

Индексо-заменители (&1 и &2) разрешаются только в условных выражениях в определении множества.

Цель в строке 10 состоит в минимизации суммы затрат, то есть суммы произведений атрибутов C на X для каждого элемента множества PAIR.

В строках с 12 по 14 мы установили ограничение, согласно которому каждый объект может быть спарен только с каким-то одним другим объектом. Другими словами, для каждого OBJ(I) мы суммируем все возможные спаренные объекты, так что одним из членов в паре является элемент OBJ(I). Мы затем принудительно приравниваем всю сумму единице, тем самым требуя, чтобы каждый объект был спарен только с каким-то одним другим объектом.

В строке 15 записано, что атрибут X для каждой пары должен быть равен 0 или 1.

Отчет о решении для переменной приведен ниже. Отметим, что X(I,J) существует только для I<=J.

LI NGVARIABLE VALUE REDUCED COST

X(1,2).00000000 8.0000000

X(1,3).00000000 1.0000000

X(1,4).00000000 2.0000000

X(1,5).00000000 1.0000000

X(1,6) 1.0000000.00000000

X(1,7).00000000 2.0000000

X(1,8).00000000 4.0000000

X(2,3).00000000.00000000

X(2,4).00000000 6.0000000

X(2,5).00000000 3.0000000

X(2,6).00000000 5.0000000

X(2,7) 1.0000000.00000000

X(2,8).00000000.00000000

X(3,4).00000000 2.0000000

X(3,5).00000000 3.0000000

X(3,6).00000000 1.0000000

X(3,7).00000000 6.0000000

X(3,8) 1.0000000.00000000

X(4,5) 1.0000000.00000000

X(4,6).00000000 4.0000000

X(4,7).00000000 2.0000000

X(4,8).00000000.00000000

X(5,6).00000000 8.0000000

X(5,7).00000000 5.0000000

X(5,8).00000000 5.0000000

X(6,7).00000000.00000000

X(6,8).00000000 2.0000000

X(7,8).00000000 1.0000000

ROW SLACK OR SURPLUS DUAL PRICE

1 6.0000000 1.0000000

2.00000000 -1.0000000

3.00000000.00000000

4.00000000 -1.0000000

5.00000000 -1.0000000

6.00000000.00000000

7.00000000.00000000

8.00000000 -2.0000000

9.00000000 -1.0000000

Итоговые затраты в решении равны 6. Распределение по парам таково (1,6), (2,7), (3,8), и (4,5).

Чтобы увидеть только ненулевые значения для X в LINGO для Windows, выберите команду Solution … в меню LINGO ипоставьте отметку в позиции Nonzeros only (только ненулевые), введите X в поле Attribute и нажмите кнопку OK.

Дата добавления: 2015-11-16