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

УДК 004.42:519.85-37(075.8) Г63

Рецензенты:

д-р техн. наук, профессор Ю.Н. Хижняков (Пермский национальный исследовательский политехнический университет);

канд. техн. наук, заведующий лабораторией Г.Ф. Масич (Институт механики сплошных сред УрО РАН)

Гольдштейн, А.Л.

Г63 Моделирование и оптимизация в LINGO : учеб. пособие / А.Л. Гольдштейн. – Пермь : Изд-во Перм. нац. исслед. поли-

техн. ун-та, 2018. – 146 с.

ISBN 978-5-398-01964-3

Рассмотрены возможности пакета программ LINGO, предназначенного для решения оптимизационных задач, от линейных до нелинейно-целочислен- ных общего вида. Основными составляющими LINGO являются развитый современный язык моделирования задач оптимизации, набор мощных решателей и интерфейс с внешними системами. Представлена концепция языка, базирующаяся на описании задачи множествами подобных объектов, обладающих общими атрибутами, и функциях, оперирующих с этими множествами. Набор функций позволяет моделировать практически любые задачи математического программирования. Приведено большое число примеров, демонстрирующих применение основных функций описания модели и процесса решения, решения задач оптимизации от модели до результата, а также взаимодействия LINGO с текстовыми файлами, Excel и известными БД. Показана возможность встраивания функционала LINGO в приложения.

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

УДК 004.42:519.85-37(075.8)

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

Рассматриваются особенности и преимущества языка LINGO при моделировании и решении задач математического программирования средней и большой размерности, в частности, компактность представления математической модели и легкость масштабирования моделируемых задач. Структурированное представление модели задачи позволяет отделить модель оптимизации от данных, выделить разделы предварительных вычислений (например, средних и дисперсии) и задания начальных условий. Как сможет убедиться читатель, язык моделирования дает возможность в одном описании задать вариантность решения задачи, выделить подмодели и из них формировать необходимые комбинации, каждая из которых решается как единая задача. Язык включает средства программирования, которые позволяют вводить данные как непосредственно в модель, так и из внешних источников (текстовых файлов, электронных таблиц, баз данных и пользовательских приложений), а также передавать результаты решения на экран или во внешние файлы, базы данных и т.д.

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

6

Основными компонентами LINGO являются решатели (Solvers), применяемые для разных классов задач оптимизации, и встроенный современный язык моделирования с очень широкими возможностями.

Для решения задач оптимизации LINGO использует 4 встроенных решателя:

1)прямой решатель,

2)линейный решатель,

3)нелинейный решатель,

4)менеджер ветвей и границ.

Как правило, LINGO автоматически выбирает решатель (метод), соответствующий модели задачи. В то же время пользователь может в настройках решателей Solver|Options указать желаемый.

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

Прямой решатель в основном выполняет функции препроцессора. Он ищет в модели равенства с одной переменной и, если находит, то из каждого такого равенства вычисляет допустимое значение неизвестной. С учетом полученных значений таких переменных, возможно, найдется другое равенство, в котором останется также одна неизвестная, что позволяет определить ее значение. Этот процесс продолжается, пока есть возможность сокращать число неизвестных, а следовательно, размерность модели.

Если в генераторе модели опция линеаризации (Linearization) не отключена (degree None), LINGO автоматически линеаризует многие негладкие функции (например, max, abs), что нередко позволяет преобразовать нелинейную модель в линейную, и затем использовать линейный решатель.

Для решения линейных задач LINGO располагает тремя вариантами решателя:

8

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

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

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

В расширенном варианте в LINGO могут входить специализированные решатели:

Branch-and-Price Solver (BNP),

Branch-and-Bound Solver,

Global Solver,

Multistart Solver,

SP Solver.

Решатель BNP (ветвей и цены) предназначен для поиска решения на линейных моделях смешанного целочисленного программирования, имеющих блочную структуру. Он представляет собой гибрид процедур ветвей и границ, генерации столбца и методов релаксации лагранжиана. Используя декомпозицию, BNP выделяет из исходной задачи несколько подзадач (по числу блоков) и при многоядерном процессоре решает их независимо в режиме параллельных вычислений. В случаях, когда число связующих условий мало, число блоков велико и они примерно одинакового размера и когда число доступных процессоров или ядер не меньше 4, BNP может искать решение лучше установленного по умолчанию решателя MIP. Иногда быстро найденное BNP хорошее решение может потребовать много времени для доказательства его оптимальности.

Опция Blocks позволяет определять блоки либо через имена входящих в блок строк (Row Names), либо пользователем с помощью функции @BLOCKROW при выборе значения Specified, либо указанием возможного числа блоков, а также отказаться от применения

10