книги / Моделирование и оптимизация в LINGO

Теперь вернемся к интерпретации стандартного отчета LINGO. Чтобы пояснить смысл столбцов отчета Reduced Cost и Dual Price, предположим, что в задаче Production рассматривается непрерывное производство. Тогда и переменные Xij будут непрерывными. Удалив из линейной LINGO-модели строку

@FOR(PR_EQ(I,J)|order(I) #NE# 0: @GIN(X));

и снова решив задачу, получим

Global optimal solution found.		743.1343
Objective value:
Objective bound:		743.1343
Infeasibilities:		0.000000
Extended solver steps:		0
Total solver iterations:		16
Model Class:		MILP
Total variables:		16
Nonlinear variables:		0
Integer variables:		9
Total constraints:		10
Nonlinear constraints:		0
Total nonzeros:		28
Nonlinear nonzeros:		0
Variable	Value	Reduced Cost
TIME	743.1343	0.000000
ORDER( PR1)	75.00000	0.000000
ORDER( PR2)	123.0000	0.000000
ORDER( PR3)	0.000000	0.000000
ORDER( PR4)	62.00000	0.000000
TWORK( 1)	743.1343	0.000000
TWORK( 2)	743.1343	0.000000
TWORK( 3)	743.1343	0.000000
K( 1)	2.000000	0.000000
K( 2)	1.000000	0.000000
K( 3)	3.000000	0.000000
T( PR1, 1)	7.000000	0.000000
T( PR1, 2)	11.00000	0.000000
T( PR1, 3)	9.000000	0.000000
T( PR2, 1)	14.00000	0.000000

41

T( PR2, 2)	8.000000	0.000000
T( PR2, 3)	10.00000	0.000000
T( PR3, 1)	12.00000	0.000000
T( PR3, 2)	7.000000	0.000000
T( PR3, 3)	13.00000	0.000000
T( PR4, 1)	10.00000	0.000000
T( PR4, 2)	9.000000	0.000000
T( PR4, 3)	11.00000	0.000000
X( PR1, 1)	75.00000	0.000000
X( PR1, 2)	0.000000	1.805970
X( PR1, 3)	0.000000	0.3880597
X( PR2, 1)	0.000000	1.611940
X( PR2, 2)	92.89179	0.000000
X( PR2, 3)	30.10821	0.000000
X( PR3, 1)	0.000000	0.000000
X( PR3, 2)	0.000000	0.000000
X( PR3, 3)	0.000000	0.000000
X( PR4, 1)	21.81343	0.000000
X( PR4, 2)	0.000000	0.7462687E-01
X( PR4, 3)	40.18657	0.000000
Row	Slack or Surplus	Dual Price
1	743.1343	-1.000000
2	0.000000	-2.298507
3	0.000000	-2.985075
4	0.000000	-3.283582
5	0.000000	0.3283582
6	0.000000	0.3731343
7	0.000000	0.2985075
8	0.000000	-0.3283582
9	0.000000	-0.3731343
10	0.000000	-0.2985075

Значения оценок Reduced Cost имеют смысл только для переменных, при этом ненулевые оценки могут быть лишь для нулевых переменных. Оценка переменной показывает, насколько ухудшится значение критерия при увеличении переменной на единицу. В данном примере наибольшее влияние на критерий может оказать изменение значения переменной X(PR1,2).

Двойственная переменная в столбце Dual Price характеризует влияние на оптимальное значение критерия изменения правой части соответствующего ей ограничения. Так, увеличение правой части в 3-м ограничении (4-я строка) с 62 до 63 приведет к возрастанию критерия до 746,418, т.е. к увеличению времени выполнения заказа

42

на 3,28. Если же уменьшить этот заказ до 61, то критерий станет равным 739,85 (уменьшится на 3,28). Таким образом, не повторяя решение задачи, можно видеть, что отрицательная двойственная цена показывает, насколько ухудшится оптимальное значение критерия при увеличении правой части на единицу и соответственно улучшится при положительном значении Dual Price.

Следует иметь в виду, что значения оценок переменных и двойственных переменных справедливы в ограниченных диапазонах изменений, которые можно найти в отчетax Range.

Первый отчет Range содержит диапазоны изменения коэффициентов целевой функции, второй – правых частей условий (RHS), в которых базис не изменяется, а значит, не изменяются оценки переменных и двойственные переменные. В качестве иллюстрации приведем полный отчет Range по строкам:

Righthand Side Ranges:
Row	Current	Allowable	Allowable
	RHS	Increase	Decrease
2	75.00000	46.39683	75.00000
3	123.0000	134.6250	48.02976
4	62.00000	73.35455	59.83333
5	0.000000	598.3333	324.7778
6	0.000000	384.2381	1077.000
7	0.000000	730.7500	806.9000
8	0.000000	324.7778	598.3333
9	0.000000	1077.000	384.2381
10	0.000000	806.9000	730.7500

Отчеты Range возможны только для линейных моделей. LINGO предоставляет дополнительные возможности языка

моделирования, облегчающие интерпретацию стандартных отчетов и отладку моделей. В частности, рекомендуется присваивать имена ограничениям, а также целевой функции. Имена записываются перед началом ограничения (или ограничений в цикле @FOR) в квадратных скобках. При этом имя должно соответствовать требованиям LINGO: не превышать 64 символов, начинаться с буквы, последующие символы могут быть буквами, цифрами и знаком подчеркивания. Например:

43

[CRITERION] MIN = TIME;

@FOR(PRODUCT(I)|order #NE# 0: [DEMAND]@SUM(EQUIPMENT(J): X(I,J))=order);

Тогда начальные строки второй части отчета непрерывной задачи

Production будут такими:

Row	Slack or Surplus	Dual Price
CRITERION	743.1343	-1.000000
DEMAND( PR1)	0.000000	-2.298507
DEMAND( PR2)	0.000000	-2.985075
DEMAND( PR4)	0.000000	-3.283582

Также можно давать имя всей модели, которое записывается после ключевого слова TITLE:

MODEL:

TITLE Production; SETS:....

Допустимы имена на русском языке.

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

6.4. Функции манипулирования множествами

Функциями манипулирования множествами являются @IN, @INDEX, @INSERT, @SIZE и @WRAP.

Функция @IN определяет, содержится данный элемент в множестве или нет. Функция вводится следующим образом:

@IN(set_name,primitive_1_index[,primitive_2_index...]),

где primitive_1_index – индекс элемента примитивного множества 1 (2 и т.д.).

Пример:

SETS:

DAYS / MON.. SUN/; CLOSED(DAYS) /SAT SUN/;

OPEN(DAYS)|#NOT# @IN(CLOSED,&1); ENDSETS

Здесь определены одно первичное множество DAYS и два производных от него. При этом элементы множества OPEN образо-

44

ваны из DAYS исключением элементов, содержащихся в множестве CLOSED, с помощью функции @IN. Индекс &1 указывает на первое (и единственное) первичное множество. В этом примере опущены атрибуты множеств.

Функция @INDEX используется для определения индекса элемента в указанном множестве в соответствии с синтаксисом:

@INDEX( set_name, set_member).

Пример:

SETS:

Set1 /A B C/:;

Set2 /X Y Z/:;

Set3(Set1, Set2) /A,X A,Z B,Y C,X/:; ENDSETS

X = @IN(Set3,@INDEX(Set1,A),@INDEX(Set2,Z));

В отличие от предыдущего примера в функции @IN заданы 2 индекса из примитивных множеств Set1 и Set2. Если элемент A содержится в Set1, а Z принадлежит Set2, то функция @INDEX вернет их индексы в производном множестве Set3, и X примет значение 1. Получить индекс элемента (A,Z) в множестве Set3 можно просто:

IND = @INDEX(Set3, A,Z);

В данном примере индекс будет равен 2.

Для динамического добавления элементов в производное множество используется функция @INSERT. При этом вставляемый элемент должен быть образован только элементами, содержащимися в соответствующих примитивных множествах. Синтаксис функции @INSERT такой же, как для функции @IN. Например, вставим эле-

мент (B, Z) в Set3:

@INSERT(Set3, 2, 3);

Здесь 2 и 3 – индексы B и Z в примитивных множествах, содержащих эти элементы. Если значения индексов неизвестны, тот же результат получим, применив функцию @INDEX:

@INSERT(Set3, @INDEX(Set1, B), @INDEX(Set2,Z));

Функция @SIZE возвращает число элементов в множестве set_name:

@SIZE(set_name);

45

Так, для нашего примера можем записать:

N1=@SIZE(set1); N3=@SIZE(set3);

Значение N3 для рассматриваемого примера станет равным 5. Использование @SIZE позволяет повысить независимость математической модели от данных, так как в ней не требуется указывать фактическое число элементов, и выражения останутся справедливыми для любого размера множества.

При моделировании некоторых ситуаций возникает необходимость преобразовывать текущий индекс так, чтобы его значение принадлежало заданному диапазону. Такое преобразование выполняет функция @WRAP, имеющая 2 аргумента:

@WRAP(INDEX,LIMIT);

где INDEX и LIMIT – фактический текущий индекс и верхняя граница диапазона (целое число). Функция возвращает значение из интервала [1, LIMIT]. Так, при планировании на 3 года текущий индекс может представлять порядковый номер месяца в плановом периоде (от 1 до 36). Если он равен, например 27, функция @WRAP(27, 12) вернет значение 3, т.е. месяц март.

6.5. Функции представления отчетов

Функции отчетов позволяют формировать отчеты с требуемой информацией и в требуемом виде, а также совместно с функциями интерфейса экспортировать их из LINGO. Эти функции могут размещаться только в секциях DATA и CALC. Их список весьма значителен, поэтому ниже рассматриваются только наиболее часто используемые функции отчета.

Функция @WRITE выводит объекты, представляемые как ее аргументы:

@WRITE(obj1[, …, objn]).

В качестве объекта может быть записано и арифметическое выражение:

DATA:

X=6800; !Обмениваемая сумма, руб; Y=61.5; !Курс доллара;

46

@TEXT() = @WRITE( X,' руб. ',Y,' руб/$',' Получено ', X/Y,' $'); ENDDATA

Здесь функция @TEXT() посылает вывод на стандартное устройство (как правило, на экран):

6800 руб. 61.5 руб/$ Получено 110.5691056910569 $

Функция вывода @WRITEFOR применима к множествам аналогично цикловым функциям:

@WRITEFOR ( setname[ ( set_index_list) [ | cond_qualifier]]: obj1[, …, objn])

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

@TEXT() = @WRITE('Поставщик отправит: ',@NEWLINE(1));

! или так: @TEXT() ='Поставщик отправит:';; @TEXT() = @WRITEFOR( NET ( I, J) | X(I,J)#GT# 0:

X(I,J), ' единиц со склада ', SUPPLIERS(I),

' потребителю ', CONSUMERS( J), @NEWLINE(1));

то в отчете получим

Поставщик отправит:

5 единиц со склада H1 потребителю A

8 единиц со склада H1 потребителю B

10 единиц со склада H2 потребителю A

22 единиц со склада H3 потребителю C

6 единиц со склада H3 потребителю D

В этом примере использована функция @NEWLINE(n), выполняющая перевод строки n раз.

Обе рассмотренные функции допускают вложение функции @FORMAT и оператора репликации текста * по правилу: n*’строка символов‘, где n – числовое значение (целое число или значение целочисленной переменной), определяющее число повторений текста. Например, если в приведенном выше фрагменте в функции @WRITEFOR вставить перед X(I,J) оператор репликации 4*' ', тогда строки 2–6 сдвинутся вправо на 4 пробела:

47

Поставщик отправит:

5 единиц со склада H1 потребителю A

8 единиц со склада H1 потребителю B

10 единиц со склада H2 потребителю A

22 единиц со склада H3 потребителю C

6 единиц со склада H3 потребителю D

Функция @FORMAT применяется для форматирования числовых или строковых значений в виде

@FORMAT ( value, format_descriptor),

где первый аргумент – форматируемое значение, а второй – дескриптор формата, определяющий вид отформатированного значения. Например, дескриптор '10.2f' для числового значения приведет к выводу значения в поле, длиной в 10 символов с двумя цифрами после десятичной точки. Дескриптор '10s' определит вывод строкового значения в 10-символьное поле с выравниванием по правому краю, а '-10s' – с выравниванием по левому краю. Если в примере с обменом денег использовать форматирование результата, т.е. фрагмент модели представить в виде

DATA:

X=6800; !Объме0,ниваемая сумма, руб; Y=61.5; !Курс доллара;

@TEXT() = @WRITE( X,' руб. ',Y,' руб/$',' Получено ', @FORMAT( X/Y, '8.1f'),' $');

ENDDATA

то в отчете получим

6800 руб. 61.5 руб/$ Получено 110.6 $.

Функция @STRLEN(string) возвращает длину строки. Она применяется при форматировании отчетов.

Функция @TABLE используется для вывода данных в виде таблицы, которая может содержать либо значения атрибутов, либо элементы множества:

@TABLE(attr|set).

Пример:

sets:

PRODUCT: order;

EQUIPMENT /EQ1..EQ3/: TWORK, K;

PR_EQ (PRODUCT, EQUIPMENT): T, X;

48

endsets
data:
PRODUCT=pr1.. pr4;
order= 75 123 0 62;
T = 7	11	9
14	8	10
12	7	13
10	9	11;
@TEXT()= @TABLE(T);
enddata
В этом примере данные будут выведены в виде
PR1		EQ1	EQ2	EQ3
		7.000000	11.00000	9.000000
PR2		14.00000	8.000000	10.00000
PR3		12.00000	7.000000	13.00000
PR4		10.00000	9.000000	11.00000

Для получения таблицы множества заменим аргумент T именем множества:

@TEXT()=@TABLE(PR_EQ);

В результате имеем

PR1	EQ1	EQ2	EQ3
	X	X	X
PR2	X	X	X
PR3	X	X	X
PR4	X	X	X,

где символ Х показывает, что в производном множестве PR_EQ имеется соответствующий элемент, иначе был бы пробел. Как видно из таблицы, данное множество является плотным.

LINGO поддерживает не только плоские, но и многомерные таблицы с помощью дополнительных аргументов функции @TABLE. Эти аргументы позволяют распределять измерения по осям таблицы: какие показывать по горизонтальной оси, а какие – по вертикальной. Заметим, что при одном измерении таблица будет представлена одним столбцом.

Если ширина таблицы превышает ширину страницы, остальная часть таблицы переносится и размещается под предыдущей.

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

49

6.6. Функции даты и времени

Функция @TIME() возвращает общее время генерации и решения модели в секундах. Она допустима только в секциях DATA и CALC. Например:

CALC:

@write('Время решения задачи: ', @TIME(), ' сек. '); ENDCALC

Функция @STMNOW() возвращает текущее время в секундах от точки отсчета 1 января 2000 г. Так, при выполнении скрипта

CALC:

T = @STMNOW(); @WRITE(T);

ENDCALC

получим

Variable	Value
T	0.5410119E+09

Из синтаксиса функции @YMD2STM( year, month, day, hour, minute, second) следует, что ее аргументами являются год, месяц, день, час, минуты и секунды. Возвращает эта функция соответствующее им скалярное время в секундах, положительное для дат после 1 января 2000 г. и отрицательное для дат до 1 января 2000 г. Пример:

CALC:

T1 = @YMD2STM( 2016, 2, 21, 17, 37, 7.5);

T2 = @YMD2STM( 1812, 11, 17, 12, 0, 0); ENDCALC

Результат выполнения скрипта:

Variable	Value
T1	0.5093914E+09
T2	-0.5904965E+10

Аргументом функции, обратной предыдущей, является стандартное скалярное время (STM), преобразуемое в год, месяц и т.д., указанные в левой части выражения

YEAR, MON, DAY, DAYOFWEEK, HOUR, MIN, SEC = @STM2YMD( stm).

Часть возвращаемых значений может быть опущена. Функция применяется только в секции CALC. Пример:

50