Зенкевич Н.А. Практикум по исследованию операций

Подождите немного. Документ загружается.

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 151

содержаться данные о значениях целевой функции (Objective value) и переменных модели

(Variable). Отчет может быть сохранен в виде файла или распечатан.

Рис.6.2.5. Диалоговое окно Solution Report

Из отчета мы получаем, что задача была решена за четыре итерации, значение целе-

вой функции z = 27.85714, значения переменных x

= 4.714286, x

= 6.857143.

В отчете LINGO содержатся дополнительные сведения о Reduced Cost и Dual Price.

Reduced Cost показывают в каких границах можно изменять коэффициенты модели

для улучшения оптимального решения. Если получено оптимальное решение, то Reduced

Cost равны 0, как в нашем случае.

Так же Reduced Cost можно интерпретировать как штраф, который мы должны за-

платить за одну единицу продукции, соответствующей каждой переменной входящей в

решение. Например, если у одной из переменных Reduced Cost равна 10, то необходимо

будет уменьшить оптимальное решение задачи на 10, в случае задачи на максимум и

увеличить в случае задачи на минимум.

Dual Price (двойственная цена, или оценка ресурса), показывает на сколько увели-

чится величина прибыли при изменении на единицу величины данного ресурса.

6.2.3 Второй способ решения задачи ЛП в LINGO

Данная модель может быть представлена иначе, с использованием языка моделирования

LINGO. В листинге модели все служебные слова написаны прописными буквами (это

сделано для удобства чтения модели, LINGO не чувствителен к регистру).

Строки, начинающиеся с восклицательного знака являются комментариями и не об-

рабатываются процессором LINGO. Все стандартные операторы, включая комментарии

должны заканчиваться точкой с запятой. Служебные слова MODEL, SETS, DATA долж-

ны заканчиваться двоеточием, служебные слова END, ENDSETS, RENDDATA (служеб-

152 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

ные слова закрывающие операторные скобки) не требуют после себя никаких знаков

препинания.

Оператор TITLE предваряет описание модели. В операторных скобках SETS: ENDSETS

вводятся имена основных компонентов модели ЛП – ограничения, переменных и мат-

рицы, содержащих коэффициенты ограничений. Эти данные определяются до начала

использования модели.Для того чтобы описать множество SETS необходимо:

• Задать имя множества.

• Задать объекты, содержащиеся в множестве.

• Задать атрибуты объектов (свойства объектов.)

В простейшем случае определения множества имеет следующий синтаксис:

Имя множества [/ список_объектов /] [: список_атрибутов];

Примечание: в качестве имени множества лучше всего использовать информатив-

ные и легко запоминающиеся названия. Имя может иметь до 31 символа (буквы и циф-

ры). LINGO не делает различий между строчными и прописными буквами.

В нашей модели используются следующие имена Constr-ограничения, Var- перемен-

ные, ConsVar- массив коэффициентов размерности Constr × V ar. Вектор правых частей

ограничений назовем Rhs. Отношения ограничений и правых частей могут быть заданы

оператором

Constr:Rhs;

Аналогично оператор

Var: C, X;

указывает, что каждой переменной X соответствует в целевой функции коэффициент

C (C и X - векторы). Матрицу, содержащую коэффициенты ограничений назовем Aij

ConsVar(Constr, Var): Aij;

Таким образом заданы все элементы, необходимые для описания алгебраической мо-

дели. Используя фиктивный индекс j для представления переменной j, целевая функция

строится следующим образом:

MAX=@SUM( Var(j): C(j)*X(j));

Этот оператор задает целевую функцию, как произведение C(j)*X(j), причем это

произведение берется по всем элементам множества Var(j)

MODEL:

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 153

TITLE задача об использовании сырья;

!——————–алгебраическое определение модели ЛП;

SETS:

Constr: Rhs;

Var: C, X;

ConsVar(Constr,Var): Aij;

ENDSETS

!————————- построение модели;

MAX=@SUM( Var(j): C(j)*X(j) ); !целевая функция;

@FOR( !ограничения;

Constr(i):@SUM( Var(j): Aij(i,j)*X(j) )<=Rhs(i)); !———————–данные модели;

DATA:

Constr = Resource1 Resource2 Resource3;

Rhs = 21 30 16;

Var = X1 X2;

C = 3 2;

Aij= 3 1

2 3

0 2

ENDDATA

END

Каждое i-е ограничение строится следующим образом:

Constr(i):@SUM( Var(j): Aij(i,j)*X(j) )<=Rhs(i));

Для вычислений всех ограничений из множества Constr(i) используется цикл

@FOR( !ограничения;

Constr(i):@SUM( Var(j): Aij(i,j)*X(j) )<=Rhs(i));

Последний раздел модели содержит данные подставляемые в алегебраическую мо-

дель. Множество Constr определяется как множество из четырех ограничений: Resource

1, Resource 2, Resource 3 (Ресурс 1, Ресурс 2, Ресурс 3). Между именами необходимо

ставить пробелы, которые определяют количество элементов в множестве. В следующей

строке вектору Rhs присваиваются значения правых частей ограничений. Элементам

множества Var присваиваются имена X1, X2 (в модели имеются две переменные). Соот-

ветственно C присваиваются значения 3 и 2, значения коэффициентов целевой функции.

154 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Массиву Aij присваиваются значения левых частей ограничений.

По умолчанию в LINGO подразумевается, что все переменные не отрицательны. Сво-

бодные переменные, (т.е. такие которые могут принимать любые значения, как положи-

тельные так и отрицательные) задаются с помощью оператора @FREE. Например если

в модели X2 свободная переменная то это может быть записано

@FREE(X(2));

Этот оператор можно использовать в любом месте программы после оператора ENDSETS.

Отчет по результатам решения задачи.

Рис.6.2.6. Диалоговое окно Solution Report

6.2.4 Транспортная задача

Рассмотрим транспортную задачу. Имеется шесть складов W h

(WAREHOUSES) и во-

семь рынков V

(VENDORS). Заданы объемы каждого из складов и спрос каждого из

рынков, а также матрица стоимостей перевозки продукции с i-го склада на j-й рынок

C = {c

Необходимо определить такой план перевозок x = {x

}, при котором котором спрос

каждого из рынков был удовлетворен, весь продукт был вывезен с каждого склада и

при этом суммарные затраты по перевозке продукции были бы минимальными.

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 155

Зададим значения векторов a, b и матрицы C.

a = (60 55 51 43 41 52), b = (35 37 22 32 41 32 43 38).

V1 V2 V3 V4 V5 V6 V7 V8

Wh1 6 2 6 7 4 2 5 9

Wh2 4 9 5 3 8 5 8 2

Wh3 5 2 1 9 7 4 3 3

Wh4 7 6 7 3 9 2 7 1

Wh5 2 3 9 5 7 2 6 5

Wh6 5 5 2 2 8 1 4 3

Формализация данной модели представлена в главе 2.1.

6.2.5 Решение транспортной задачи при помощи пакета LINGO

Обозначим через VOLUME_I_J количество продукции перевозимой с i-го склада на j

рынок.

Целевая функция может быть записана следующим образом:

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

В таблице представлено сравнение между математической формулировкой и записью

на языке моделирования LINGO

Математическая запись Язык моделирования LINGO

Minimize MIN

COST ij · VOLUME ij @SUM( LINKS(I,J): COST(I,J)* VOLUME(I,J));

Следующим шагом сформулируем ограничения модели. Нам необходимо удовлетво-

рить спрос всех рынков и при этом с каждого склада мы можем вывезти не больше

продукции, чем у него имеется. Получим два множества ограничений.

Рассмотрим первую группу ограничений Обозначим через DEMAND_j – спрос каж-

дого из рынков. Сформулируем требование о том, что суммарный объем перевозимой со

склада продукции должен равняться спросу рынка.

V OLUME_i_j = DEMAND_j, для всех j.

В пакете LINGO это выражение запишется в виде:

@FOR( VENDORS( J): @SUM( WAREHOUSES( I): VOLUME( I, J)) = DEMAND( J));

156 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Вторая группа ограничений относится к емкости складов, обозначим емкость склада

через CAP_i. Запишем требование, что суммарный объем вывозимой со склада продук-

ции не должен превышать его емкость.

V OLUME_i_j <= CAP _i , для всех i.

В LINGO это выглядит следующим образом:

@FOR( WAREHOUSES( I): @SUM( VENDORS( J): VOLUME( I, J))<= CAPACITY(

I));

Таким образом ограничения на спрос рынков и емкость складов описываются опера-

торами:

MODEL:

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

@FOR( VENDORS( J): @SUM( WAREHOUSES( I): VOLUME( I, J)) = DEMAND( J));

@FOR( WAREHOUSES( I): @SUM( VE NDORS( J): VOLUME( I, J)) <= CAPACITY(

I));

END

Как правило, в реальной жизни мы имеем дела не с одним, а с множеством объек-

тов. Применительно к нашей модели этими объектами являются множества складов и

множество рынков и множество связей между ними (см рис.2.1.1 гл. 2). Используем для

описания множеств оператор SETS.

Как говорилось ранее, у нас имеется три множества: склады, рынки и множество

связей между ними.В нашем случае их можно описать в виде:

SETS:

WAREHOUSES / WH1 WH2 WH3 WH4 WH5 WH6/: CAPACITY;

VENDORS / V1 V2 V3 V4 V5 V6 V7 V8/ : DEMAND;

LINKS( WAREHOUSES, VENDORS): COST, VOLUME;

ENDSETS

Множество складов WAREHOUSES состоит из шести объектов, каждый из которых

обладает атрибутом CAPACITY.

Множество рынков VENDORS состоит из восьми объектов, каждый из которых об-

ладает атрибутом DEMAND.

Множество связей между складами и рынками LINKS состоит из 48 объектов с

атрибутами COST и VOLUME. LINGO создает упорядоченные пары WAREHOUSES-

VENDORS. Для наглядности эти пары представлены в таблице:

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 157

Порядковый номер Связь

1 W H1 → V 1

2 W H1 → V 2

3 W H1 → V 3

... ...

47 W H6 → V 7

48 W H6 → V 8

Осталось добавить в модель исходные данные и решить ее.

Примечание. LINGO позволяет решать не только сбалансированные транспортные

модели.

В пакете LINGO исходные значения модели могут быть выделены в отдельный ра з-

дел. Этот раздел отделяется ключевыми словами: DATA и ENDDATA. Таким образом

исходный данные нашей модели можно записать следующим образом:

DATA:

CAPACITY = 60 55 51 43 41 52;

DEMAND = 35 37 22 32 41 32 43 38;

COST = 6 2 6 7 4 2 5 9

4 9 5 3 8 5 8 2

5 2 1 9 7 4 3 3

7 6 7 3 9 2 7 1

2 3 9 5 7 2 6 5

5 5 2 2 8 1 4 3;

ENDDATA

CAPACITY и DEMAND являются атрибутами объектов множеств складов и рын-

ков. COST – матрица стоимостей перевозок со складов на рынки. В том случае, когда

LINGO находит многомерный массив данных, он вначале выстраивает по возрастанию

последовательности индексов этого массива. В нашем случае значение COST( WH1, V1)

определяется первым, затем COST( WH1, V2) и так далее до COST (WH1, V8). Потом

инициализируется COST(WH2, V1). Далее процесс происходит по заданной схеме.

Пакет LINGO позволяет импортировать данные из внешних источников баз данных,

электронных таблиц и т.п. используя интерфейс ODBC.

В итоге мы имеем транспортную модель записанную на языке моделирования LINGO:

158 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Рис.6.2.7. Транспортная задача.

Решая эту модель получаем, что значение целевой функции равно 664.0000.

Для того чтобы получить отчет содержащий только неотрицательные значения коли-

чества продукции VOLUME_i_j перевозимой со складов на рынки необходимо выбрать

команду Solution из пункта меню L INGO.

Рис.6.2.8. Диалоговое окно Solution Report or Graph

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 159

В появившемся диалоговом окне необходимо выбрать VOLUME в поле Attribute or

Row Name. Для того чтобы посмотреть только неотрицательные значения надо поставить

флажок в поле Nonzeros Only.

Рис.6.2.9. Диалоговое окно Solution Report od Graph

В результате решения модели получаем отчет:

Рис.6.2.10. Диалоговое окно Solution Report

6.2.6 Задача коммивояжера

В пакете LINGO задача коммивояжера, рассмотренная в главе 4.2, решается эвристиче-

ским методом.

160 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Коммивояжер должен объехать шесть городов Atlanta, Chicago, Cincinnati, Houston,

Los Angeles, Montreal, в каждом побывать по одному разу и вернуться в исходный пункт.

Задана матрица расстояний между городами.







∞ 702 454 842 2396 1196

702 ∞ 324 1093 2136 764

454 324 ∞ 1137 2180 798

842 1093 1137 ∞ 1616 1857

2396 2136 2180 1616 ∞ 2900

1196 764 798 1857 2900 ∞







При записи на языке моделирования LINGO символ ∞ заменяется на 0.

MODEL:

!Задача коммивояжера;

SETS:

CITY / 1.. 6/: U; ! U( I) = последовательность номеров городов;

LINK( CITY, CITY):

DIST, ! Матрица расстояний;

X; ! X( I, J) = 1 если возможен переезд между городами I, J;

ENDSETS

DATA: !Матрица расстояний;

DIST = 0 702 454 842 2396 1196

702 0 324 1093 2136 764

454 324 0 1137 2180 798

842 1093 1137 0 1616 1857

2396 2136 2180 1616 0 2900

1196 764 798 1857 2900 0;

ENDDATA

!The model:Ref. Desrochers & Laporte, OR Letter s,

Feb. 91;

N = @SIZE( CITY);

MIN = @SUM( LINK: DIST * X);

@FOR( CITY( K):