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

Рис. 32

Рис. 33

121

В меню Build командой Build gol строим проект. Результатом является готовая библиотека gol.dll, которая находится в папке gol/Debug. Чтобы включить функцию @USER в LINGO, копируем gol.dll в головной каталог LINGO с именем myuser.dll.

Теперь при каждом запуске LINGO будет появляться окно с сообщением об инсталляции DLL (см. код). При построении DLL в некоторых версиях Visual C++ возможно также предупреждение «Ошибка», которое следует игнорировать.

Примеры, подтверждающие реализацию функции @USER, приведены в скриншоте на рис. 34.

Рис. 34

122

ЗАКЛЮЧЕНИЕ

LINGO – полнофункциональная среда для построения, анализа

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

Вучебном пособии невозможно полно и всесторонне раскрыть всю функциональность LINGO, и материал пособия следует рассматривать только как введение в LINGO. Пособие содержит основы работы с LINGO, знание которых позволит читателю строить модели оптимизации и находить на них наилучшие решения. Приведенные в нем многочисленные примеры наглядно показывают, какие широкие возможности предоставляет LINGO для решения реальных задач и создания программных систем автоматизации биз- нес-процессов в различных сферах деятельности человека.

Пособие может быть использовано в практических занятиях, для постановки лабораторных работ, при выполнении курсовых работ и проектов по дисциплинам «Моделирование», «Методы оптимизации» и смежным с ними, в ВКР и, конечно, в научных исследованиях и разработках.

Дополнения. Как отмечалось во введении, система LINGO продолжает развиваться и совершенствоваться. Когда рукопись пособия была уже подготовлена, компания LINDO Systems Inc. представила новую, 17-ю версию LINGO. Отметим основные отличия от предшествующей, 16-й версии.

Вновой версии повышена скорость на 15–20 % симплексного

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

Внесена поддержка передачи аргументов пользовательским процедурам, стиля представления данных в разделах DATA и CALC. Добавлены новые функции:

123

@NEXTKBEST() для получения следующего наилучшего решения в бинарных моделях (используется в разделе Calc);

@QRFACTOR(A) для выполнения QR-факторизации матриц; @MTXMUL(A, B) для умножения двух матриц;

@ALLDIFF для ограничений на целочисленные переменные в виде требования несовпадающих значений.

Пример применения функции @NEXTKBEST для нахождения до 4 лучших решений:

CALC:

! Начальное и максимальное значение счетчика решений;

N = 0;

NMAX= 4;

!Первичное решение модели;

@SOLVE( NAME_MODEL);

!Получение других решений при разрешимости модели;

WHILE( @STATUS() #EQ# 0 #AND# N #LT# NMAX:

N = N + 1;

! Печать очередного лучшего решения;

REPORT;

!Решение для получения следующего лучшего решения;

@NEXTKBEST();

); ENDCALC

Синтаксис второй функции

Q, R = @QRFACTOR( A);

где A=QR, R – верхняя треугольная матрица; Q – ортогональная матрица. Все матрицы должны быть определены на плотных множествах.

Оригинальная функция @ALLDIFF накладывает на группу целочисленных переменных требование, чтобы в группе они принимали только различные значения. Она применяется аналогично функции @CARD:

@ALLDIFF ('set_name', variable_name);

где 'set_name' – это имя, назначенное группе общих целочисленных переменных, а variable_name – имя переменной, принадлежащей этой группе. Для размещения нескольких переменных в одной груп-

124

пе можно использовать вложение @ALLDIFF в функцию цикла @FOR. Простые примеры:

@ALLDIFF ('SET1', X); @ALLDIFF ('SET1', Y); @FOR (FLATS (I): @ALLDIFF ('NUM_FLAT', Z (I)));

Интересным примером применения этой функции является задача составления головоломки судоку. В матрице 9×9 надо поместить цифры от 1 до 9 так, чтобы в каждой строке и в каждом столбце, а также в каждой подматрице 3×3 и на главных диагоналях каждая цифра встречалась только один раз. Ограничимся матрицей 3×3 и запишем фрагмент модели, содержащий ограничения по строкам:

sets:

number;

matrix( number, number): X; endsets

data:

number = 1..3; enddata

@for( number( i): @for( number(j):

@alldiff( 'row'+number(i), X(i,j)); );

);

Сгенерировав развернутую модель, получаем

MODEL:	X_1_1);	@GIN(	X_1_2);	@GIN(	X_1_3);	@GIN(
@GIN(
X_2_1); @GIN( X_2_2);			X_3_1);	@GIN(	X_3_2);	@GIN(
@GIN(	X_2_3);	@GIN(
X_3_3);

@ALLDIFF( 'ROW1', X_1_1); @ALLDIFF( 'ROW1', X_1_2); @ALLDIFF( 'ROW1', X_1_3); @ALLDIFF( 'ROW2', X_2_1); @ALLDIFF( 'ROW2', X_2_2); @ALLDIFF( 'ROW2', X_2_3); @ALLDIFF( 'ROW3', X_3_1); @ALLDIFF( 'ROW3', X_3_2); @ALLDIFF( 'ROW3', X_3_3);

END

Заметим, что все переменные, указанные в функции @ALLDIFF, воспринимаются как целочисленные без использования

вмодели функции @GIN, и поэтому линейная модель при таких ограничениях относится к классу MILP.

Аналогично записываются ограничения на несовпадение цифр

вкаждом столбце.

125

СПИСОК ЛИТЕРАТУРЫ

1.Мину М. Математическое программирование. Теория и алгоритмы: пер. с фр. – М.: Наука, 1990. – 486 с.

2.Карманов В.Г. Математическое программирование: учеб. пособие для вузов. – 6-е изд., испр. – М.: Физматлит, 2008. – 263 с.

3.Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы: пер. с англ. / под ред. Д.Б. Юдина. – М.: Мир, 1982. – 583 с.

4.Грешилов А.А. Прикладные задачи математического программирования: учеб. пособие. – 2-е изд., доп. – М.: Логос, 2006. – 286 с.

5.Пыткин А. Н. Моделирование механизма территориального планирования промышленного сектора экономики региона / Ин-т экономики УрО РАН. – Екатеринбург, 2009. – 167 с.

6.Уайлд Д. Оптимальное проектирование: пер. с англ. – М.:

Мир, 1981. – 272 с.

7.Практическая оптимизация: пер. с англ. / Ф. Гилл, У. Мюр-

рей, М. Райт. – М.: Мир, 1985. – 509 с.

8.Теория иерархических многоуровневых систем: пер. с англ. / М. Месарович, Д. Мако, И. Такахара. – М.: Мир, 1973. – 344 с.

9.Оптимизация в технике: пер. с англ.: в 2 кн. / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел.– М.: Мир, 1986. – Кн. 2. – 320 с.

10.Лэсдон Л.С. Оптимизация больших систем. – М.: Наука, 1975. – 432 с.

11.Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования (теория, методы и приложения). – М.: Радио и связь, 1982. – 282 с.

12.Вагнер Г. Основы исследования операций: пер. с англ.:

в3 т. – Т. 2. – М.: Мир, 1973. – 488 с.

13.Гольдштейн А.Л. Оптимизация в LINDO: учеб. пособие / Перм. гос. техн. ун-т. – Пермь, 2000. – 87 с.

126

14.Гольдштейн А.Л. Моделирование в LINGO // Вестник Перм. нац. ислед. политехн. ун-та. Электротехника, информационные технологии, системы управления. – 2016. – № 18. – С. 25–38.

15.Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы / В.С. Михалевич, В.А. Трубин, Н.З. Шор. – М.: Наука, 1986. – 264 с.

16.Gilmore P.C., Gomory R.T. A Linear Programming Approach to the Cutting Stock Problem // Operations Research. – 1961. – Vol. 9, no. 6. – P. 849–859.

17.Lingo User’s Manual // Сайт LINDO SYSTEMS Inc. – URL: http:// www.lindo.com (дата обращения: 21.11.2017).

127

		ПРИЛОЖЕНИЕ 1
	Приоритет операций
Уровень приоритета		Операторы
Самый высокий		#NOT# – (отрицание)
		^
		*/
		+ -
		#EQ# #NE# #GT# #GE# #LT# #LE#
		#AND# #OR#
Самый низкий		<= = >=

128

		ПРИЛОЖЕНИЕ 2
	Математические функции
Функция		Описание (результат)
@ABS(X)		|X|
@ACOS( X)		Обратный косинус
@ACOSH( X)		Обратный гиперболический косинус
@ASIN( X)		Обратный синус
@ASINH( X)		Обратный гиперболический синус
@ATAN( X)		Обратный тангенс
@ATAN2( X, Y)		Обратный тангенс от Y/X
@ATANH( X)		Гиперболический арктангенс
@COS(X)		Косинус, X в радианах
@COSH( X)		Гиперболический косинус
@EXP(X)		Экспонента (e^X)
@FLOOR(X)		Целое I такое, что при X>0 I<=X, при X<0 I>=X
@INT( X)		Целая часть X такая, что I<=X
@INTEGRAL( PRO-		Значение интеграла от XL до XU, вычисленного по
CEDURE, X, XL, XU, Y)		формуле Симпсона. Значение подынтегральной
		функции Y вычисляется процедурой. Функция
		применима только в CALC-секции
@LGM(X)		Натуральный логарифм гамма-функции от X
@LOG(X)		Натуральный логарифм X
@LOG10(X)		Десятичный логарифм X
@LOGB( X, B)		Логарифм X по основанию B
@MOD( X, Y)		Оставшаяся часть от целого деления X на Y
@PI()		Значение
@POW( X, Y)		X^Y
@ROUND( X, N)		Округление X до ближайшего числа с N цифрами
		в дробной части
@ROUNDDOWN( X, N)		Округление X до ближайшего числа в направле-
		нии к 0 с N цифрами в дробной части

129

Функция	Описание (результат)
@ROUNDUP( X, N)	Округление X до ближайшего числа в направле-
	нии от 0 с N цифрами в дробной части
@SIGN(X).	–1 для X < 0, 0 для X = 0, +1 для X > 0
@SIN(X)	Синус
@SINH( X)	Гиперболический синус
@SMAX (X1, X2,..., XN)	Максимальное значение из N чисел
@SMIN(X1, X2,..., XN)	Минимальное значение из N чисел
@SQR( X)	X ^2
@SQRT( X)	Корень квадратный
@TAN(X)	Тангенс
@TANH( X)	Гиперболический тангенс
Функции полностью плотных матриц (для CALC-секции)
L[, err] =	Факторизация по Чолеску: преобразует симмет-
@CHOLESKY( A)	ричную положительно-определенную матрицу в
	нижне-треугольную L, так что L L’= A. Флаг err:
	успешно 0, иначе 1
@DETERMINANT( A)	Определитель матрицы A
LAMDAR, VR,	Вычисление действительных и мнимых частей
LAMBDAI, VI, ERR =	собственных значений (векторы LAMDAR и
@EIGEN( A)	LAMBDAI), аналогично для собственных векто-
	ров (матрицы VR и VI)
AINV[, err] =	Вычисляет обратную матрицу A–1
@INVERSE( A)
B, b0, RES, rsq, f, p, var	Строит множественную линейную регрессию
= @REGRESS( Y, X)	Y = b0 + B*X. RES – остатки (вектор разностей),
	rsq – статистика R-квадрат, f и p – меры значимо-
	сти регрессионной модели, var, – оценка диспер-
	сии остатков
T = @TRANSPOSE( A)	Транспонирует матрицу A
	Функции вероятности
@PEB(A, X)	Вероятность, что заняты все X сервисов системы
	массового обслуживания с неограниченной очере-
	дью при нагрузке A, равной ожидаемому числу
	клиентов в единицу времени, умноженному на
	ожидаемое время обслуживания одного клиента, и
	потоке обслуживания Эрланга
130