Плотное производное множество: TRAN.LNG

Следующая модель, названная TRAN.LNG и содержащаяся в наборе примеров LINGO, иллюстрирует использование производного множества. Она является оптимизационной моделью, которая решает транспортную задачу. Мы имеем некоторое количество поставщиков и потребителей, и мы хотим удовлетворить потребности потребителей при минимальных транспортных затратах. В результате мы должны получить количество товара, которое каждый поставщик должен отправить каждому из потребителей, чтобы обеспечить эти минимальные затраты.

Сначала взглянем на саму модель, а затем на то, что и как она делает.

TRAN.LNG

MODEL:

1]SETS:

2] WAREHOUSE /WH1, WH2, WH3/: CAPACITY;

3] CUSTOMER /C1, C2, C3, C4/: DEMAND;

4] ROUTES(WAREHOUSE, CUSTOMER): COST, VOLUME;

5]ENDSETS

6]

7] MIN = @SUM(ROUTES(I, J): COST(I, J)*VOLUME(I,J));

8]

9] @FOR(CUSTOMER(J):

10] @SUM(WAREHOUSE(I): VOLUME(I, J)) >= DEMAND(J));

11]

12] @FOR(WAREHOUSE(I):

13] @SUM(CUSTOMER(J): VOLUME(I, J)) <= CAPACITY(I));

14]

15]DATA:

16] CAPACITY = 30, 25, 21;

17] DEMAND = 15 17 22 12;

18] COST = 6, 2, 6, 7,

19] 4, 9, 5, 3,

20] 8, 8, 1, 5;

21]ENDDATA

END

Теперь исследуем механизм этой модели. Прежде всего, секцию SETS.

В строке 2 множество WAREHOUSE (склады) определяется как множество из трех элементов, представляя три склада, на которых хранятся наши продукты. Каждый склад имеет атрибут, характеризующий его запасы, который мы назвали CAPACITY. В строке 3 создается множество CUSTOMER (потребители) из четырех элементов, имеющих также атрибут, который мы назвали DEMAND (потребность).

В строке 4 строится производное множество из примитивных множеств WAREHOUSE и CUSTOMER. Определение множества ROUTES(WAREHOUSE, CUSTOMER) указывает, что каждый элемент множества ROOTES в действительности является упорядоченной парой из элементов примитивных множеств — одного из WAREHOUSE и одного из CUSTOMERS. Символьное представление этих пар может выглядеть, например, так:

WH1 Ю C1, WH2 Ю C2, WH1 Ю C3, WH2 Ю C1...WH3 Ю C4

Каждая упорядоченная пара — каждый путь от склада к потребителю — имеет атрибут VOLUME, соответствующий искомому количеству продукта, которое транспортируется вдоль каждого пути (ROUTE). Каждый путь (ROUTE) имеет также атрибут COST, определяющий известные затраты на перевозку единицы продукта.

Ну, достаточно о множествах. Теперь давайте взглянем на целевую функцию нашей модели. Синтаксис LINGO в целевой функции очень прост для запоминания: за словами «MIN=» или «MAX=» следует выражение, устанавливающее цель. В данном случае она состоит в том, чтобы минимизировать затраты на перевозки, являющиеся суммой удельных затрат (COST) умноженных на количество (VOLUME) товаров, перевозимых по каждому пути (ROUTE). Это записано в строке 7:

MIN = @SUM(ROUTES(I, J): COST(I, J)*VOLUME(I, J));

В переводе на обычный язык это означает: МИНИМИЗИРОВАТЬ СУММУ атрибутов COST, умноженных на атрибут VOLUME, для каждой упорядоченной пары (например, WH1,C1), содержащейся в множестве ROUTES. Мы к тому же использовали список индексов (I,J) для индексации атрибутов COST и VOLUME.

Такая целевая функция является типичной для транспортных задач. Обратите внимание, как используется функция @SUM поэлементной обработки множеств для перебора всех элементов производного множества ROUTES.

Перейдем к первому ограничению в строках 9 и 10, которое гарантирует, что потребности (DEMAND) каждого потребителя (CUSTOMER) будут удовлетворены:

@FOR(CUSTOMER(J):

@SUM(WAREHOUSE(I): VOLUME(I, J)) >= DEMAND(J));

Следовательно, для каждого потребителя CUSTOMER J сумма количеств товара, перевозимых из каждого склада WAREHOUSE I к потребителю CUSTOMER J — член VOLUME (I,J) — должна быть больше или равна потребности (DEMAND) потребителя CUSTOMER J.

Далее мы должны быть уверены, что ни с одного из складов (WAREHOUSE) не вывозится товара больше, чем в нем запасено. Это устанавливается в строках 12 и 13:

@FOR(WAREHOUSE(I):

@SUM(CUSTOMER(J): VOLUME(I, J)) <= CAPACITY(I));

Снова, переводя на обычный язык, можно сказать, что для каждого склада WAREHOUSE I, сумма вывозимого товара ко всем потребителям CUSTOMER J — член VOLUME(I,J) — должна быть меньше или равна запаса (CAPACITY) на складе WAREHOUSE I.

Замечание: Эти два ограничения уже известны вам по первому знакомству с отношениями неравенств. Это «<=» и «>=» и означают «Меньше, чем… Или Равно» и «Больше, чем… Или Равно». Не путайте их с #LE#, #GE#, #LT# и #GT#, которые являются логическими операторами. Связи в виде неравенств и отношение равенства «=» являются инструкциями для LINGO, которым должны удовлетворять программные вычисления.

Теперь посмотрим на секцию DATA, начинающуюся со строки 15.

15] DATA:

16] CAPACITY = 30, 25, 21;

17] DEMAND = 15 17 22 12;

18] COST = 6, 2, 6, 7,

19] 4, 9, 5, 3,

20] 8, 8, 1, 5;

21] ENDDATA

Заметим, что каждый из трех складов (WAREHOUSE) имеет значение, соответствующее его запасам (CAPACITY), каждому из потребителей (CUSTOMER) соответствует значение потребности (DEMAND) и каждой из 12 возможных комбинаций складов и потребителей — то есть каждому пути ROUTE — соответствует величина затрат COST.

Секция DATA, как вы должны заметить, не содержит никаких значений для VOLUME, соответствующих искомым переменным модели — неизвестным, которые должны быть определены в LINGO.

Наконец, решим модель, выбрав команду Solve из меню LINGO. Полученное решение приведено ниже.

OPTIMUM FOUND AT STEP 6

OBJECTIVE VALUE = 161.000000

VARIABLE VALUE REDUCED COST

CAPACITY(WH1) 30.00000.0000000

CAPACITY(WH2) 25.00000.0000000

CAPACITY(WH3) 21.00000.0000000

DEMAND(C1) 15.00000.0000000

DEMAND(C2) 17.00000.0000000

DEMAND(C3) 22.0000.0000000

DEMAND(C4) 12.00000.0000000

COST(WH1, C1) 6.000000.0000000

COST(WH1, C2) 2.000000.0000000

COST(WH1, C3) 6.000000.0000000

COST(WH1, C4) 7.000000.0000000

COST(WH2, C1) 4.000000.0000000

COST(WH2, C2) 9.000000.0000000

COST(WH2, C3) 5.000000.0000000

COST(WH2, C4) 3.000000.0000000

COST(WH3, C1) 8.000000.0000000

COST(WH3, C2) 8.000000.0000000

COST(WH3, C3) 1.000000.0000000

COST(WH3, C4) 5.000000.0000000

VOLUME(WH1, C1) 2.000000.0000000

VOLUME(WH1, C2) 17.00000.0000000

VOLUME(WH1, C3) 1.000000.0000000

VOLUME(WH1, C4).0000000 2.000000

VOLUME(WH2, C1) 13.00000.0000000

VOLUME(WH2, C2).0000000 9.000000

VOLUME(WH2, C3).0000000 1.000000

VOLUME(WH2, C4) 12.00000.0000000

VOLUME(WH3, C1).0000000 7.000000

VOLUME(WH3, C2).0000000 11.00000

VOLUME(WH3, C3) 21.00000.0000000

VOLUME(WH3, C4).0000000 5.000000

ROW SLACK OR SURPLUS DUAL PRICE

OBJ 161.0000 1.000000

DEMAND(C1).0000000 -6.000000

DEMAND(C2).0000000 -2.000000

DEMAND(C3).0000000 -6.000000

DEMAND(C4).0000000 -5.000000

SUPPLY(WH1) 10.00000.0000000

SUPPLY(WH2).0000000 2.000000

SUPPLY(WH3).0000000 5.000000

Значение целевой функции (в верхней части отчета) говорит нам, что минимальные затраты при удовлетворении потребностей каждого из потребителей равны $161.00.

Результат, который мы разыскивали, отображается для всех перевозок в атрибуте VOLUME. Например, значение VOLUME (WH1,C1) равно 2. Это означает, что объем перевозок товара со склада WH1 к потребителю C1 должен быть равен 2. Чтобы просмотреть решение только для этого атрибута в LINGO для Windows, выберите Solution… в меню LINGO, введите «VOLUME» в поле Attribute:

… и нажмите OK. LINGO выведет на экран значения только для переменной
VOLUME, как показано ниже.

LI VARIABLE VALUE REDUCED COST

VOLUME(WH1, C1) 2.000000.0000000

VOLUME(WH1, C2) 17.00000.0000000

VOLUME(WH1, C3) 1.000000.0000000

VOLUME(WH1, C4).0000000 2.000000

VOLUME(WH2, C1) 13.00000.0000000

VOLUME(WH2, C2).0000000 9.000000

VOLUME(WH2, C3).0000000 1.000000

VOLUME(WH2, C4) 12.00000.0000000

VOLUME(WH3, C1).0000000 7.000000

VOLUME(WH3, C2).0000000 11.00000

VOLUME(WH3, C3) 21.00000.0000000

VOLUME(WH3. C4).0000000 5.000000

В отчете о решении колонка REDUCED COST сообщает вам, насколько следует улучшить коэффициенты при переменных в целевой функции, прежде чем оно станет пригодным для ввода в решение. Например, приведенные затраты величины 2 для VOLUME(WH1,C4) говорят вам, что коэффициент для пути от WH1 к C4 (который является величиной затрат на перевозку для этого пути) следует улучшить (в данном случае уменьшить) на 2, прежде чем этот путь будет использован в решении.

Двойственная цена во всех строках отчета является степенью того, насколько значение целевой функции улучшится при увеличении значения в правой части. Двойственная цена для ограничения на DEMAND(C1) равна –6. Это означает, что возрастание правой части ограничения для DEMAND(C1) на одну единицу приведет к ухудшению двойственной цены на 6 единиц. Поскольку мы имеем дело с минимизационной моделью, значение целевой функции возрастет на 6 единиц.

Поучительно познакомиться с развернутой записью модели. Чтобы сделать это, выберите команду Generate… из меню LINGO. Вот что вы увидите:

MIN 5 VOLUME(WH3, C4)+VOLUME(WH3, C3)+

8 VOLUME(WH3, C2)+8 VOLUME(WH3, C1)+3 VOLUME(WH2, C4)+

5 VOLUME(WH2, C3)+9 VOLUME(WH2, C2)+4 VOLUME(WH2, C1)+

7 VOLUME(WH1, C4)+6 VOLUME(WH1, C3)+2 VOLUME(WH1, C2)+

6 VOLUME(WH1, C1)

SUBJECT TO

2] VOLUME(WH3, C1)+VOLUME(WH2, C1)

+ VOLUME(WH1, C1) >= 15

3] VOLUME(WH3, C2)+VOLUME(WH2, C2)

+ VOLUME(WH1, C2) >= 17

4] VOLUME(WH3, C3)+VOLUME(WH2, C3)

+ VOLUME(WH1, C3) >= 22

5] VOLUME(WH3, C4)+VOLUME(WH2, C4)

+ VOLUME(WH1, C4) >= 12

6] VOLUME(WH1, C4)+VOLUME(WH1, C3)+VOLUME(WH1, C2)

+ VOLUME(WH1, C1) <= 30

7] VOLUME(WH2, C4)+VOLUME(WH2, C3)+VOLUME(WH2, C2)

+ VOLUME(WH2, C1) <= 25

8] VOLUME(WH3, C4)+VOLUME(WH3, C3)+VOLUME(WH3, C2)

+ VOLUME(WH3, C1) <= 21

END

Так должна была бы выглядеть модель, если бы вы не имели доступа к языку моделирования LINGO. Команда Generate переводит или развертывает функции поэлементной обработки множеств (@SUM, @FOR и т.п.) в явные операторы. Следует использовать команду Generate для отладки модели, если например, вы получите результаты не те, которые вы ожидали.

Замечание: Когда переменная появляется в нелинейной строке, ее коэффициент не может быть зафиксирован и определен заранее. В таких ситуациях команда Generate подставляет знак вопроса “?” вместо числовых значений коэффициента.

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