Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

Глава 13

Практическая оптимизация с помощью пакетов прикладных программ

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

Например, в 1975 г. было объявлено о начале работ над системой GAMS — General Algebraic Modeling System [29] для решения широкого круга задач линейного, нелинейного и дискретного программирования. Эти работы были поддержаны Международным банком реконструкции и развития, для консолидации усилий математиков и программистов была создана GAMS Development Corporation. С тех пор, непрерывно совершенствуясь, GAMS превратилась в высокоуровневую программную систему, реализованную на различных аппаратных платформах — от ноутбуков до суперкомпьютеров. Для формального описания задач линейного и нелинейного программирования в системе имеется специальный входной язык, который мы рассмотрим далее.

Другим примером является очень популярная и стремительно

развивающаяся система компьютерной математики MATLAB [1] (сокращение от MATrix LABoratory). Она начала свою жизнь в конце 1970-х годов в Университете Нью-Мексико. Вначале система задумывалась как программа для доступа студентов, не владеющих Фортраном, к библиотеке программ линейной алгебры и линейного программирования LINPACK. Впоследствии функции системы постоянно расширялись, к началу XXI века она превратилась в уникальную по богатству возможностей программную среду, широко используемую академическим и научным сообществом, число ее легальных пользователей превышает миллион1.

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

13.1. Оптимизация в пакете Excel

Для многих миллионов пользователей персональных компьютеров электронная таблица Excel, входящая в пакет прикладных программ Microsoft O ce, является единственным и незаменимым средством автоматизации вычислений. С помощью этой программы делают все — от простых расчетов «на скорую руку» до комплексных систем бухгалтерского учета и планирования. Благодаря встроенному в O ce языку программирования VBA (Visual

1Система поставляется американской компанией The MathWorks, Inc., расположенной в пригороде г. Бостона, США (http://www.mathworks.com). Подробная пользовательская документация в pdf-формате с описанием использованных алгоритмов и подробными примерами доступна для скачивания на сайте компании.

Basic for Applications) имеются неограниченные возможности разработки специализированных надстроек — Add-ons для решения многих, в том числе достаточно сложных задач.

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

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

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

Описание надстройки Solver приведено в документации Excel

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

Пр и м е р 1. Возьмем совсем несложную задачу выпуклого программирования (см. пример на с. 56), которую мы решали самыми различными методами:

f (x1, x2) = (x1 − 2)2 + (x2 − 2)2 → min,

x21 + x22 4,

−x1 + x2 0, x2 1,

x1, x2 0.

На рис. 13.1 представлен соответствующий рабочий лист Excel, в котором для наглядности включен режим отображения формул, а не значений, и имеются поясняющие надписи. Под переменные x1, x2 выделены ячейки B3 и C3 с нулевыми начальными значе-

ниями, формула вычисления целевой функции записана в ячейку A3, а формулы левых частей ограничений занимают диапазон ячеек B4:B6.

Для инициализации процесса оптимизации запускаем надстройку Поиск решения (Solver) из меню Сервис (Tools) и настраиваем ее на рабочий лист. Для этого указываем: 1) целевую ячейку, 2) диапазон ячеек с переменными, 3) диапазон ячеек с формулами левых частей ограничений (если они есть) и 4) диапазон ячеек с правыми частями ограничений.

Установка параметров поиска решения производится нажатием кнопки Параметры. В открывшемся окне видим опцию Линейная модель, которую оставляем выключенной, так как наша модель нелинейная, и включаем опцию Неотрицательные значения. Выбираем квазиньютоновский метод оптимизации с прямыми (правыми) разностями для численного дифференцирования. Оставляем значения параметров точности по умолчанию, возвращаемся в главное окно поиска решения и нажимаем кнопку Выполнить. В нашем примере для нахождения решения с заданной точностью потребовалось 5 итераций.

Отчеты Solver формируются на отдельных рабочих листах (рис. 13.2). В «Отчете о результатах» распечатываются начальные и достигнутые при оптимизации значения переменных и целевой функции, а также анализируются ограничения. Как видно из отчета, для найденного оптимального решения связанными (активными) являются первое и третье ограничения, что соответствует действительности.

В «Отчете по устойчивости» приводятся полученные в ходе оптимизации оценки множителей Лагранжа. Напомним, что их

истинные значения, полученные при аналитическом решении в примере на с. 56, равны соответственно (0.1547, 0, 1.6906). Об-

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

Рис. 13.2. Отчет Solver для задачи нелинейного программирования

П р и м е р 2. В качестве другого примера решим простейшую транспортную задачу линейного программирования с двумя складами и тремя магазинами, подробно рассмотренную в [9, с. 133]:

Рабочий лист Excel и настройки главного окна Solver для нее приведены на рис. 13.3. Ячейки для оптимизируемых переменных выделены цветом и оставлены пустыми. В параметрах поиска решения следует включить опции Линейная модель и Неотрицательные значения. При этом автоматически вызовется программа симплексного метода. Хотя с точки зрения трудоемкости стандартный симплексный метод неоптимален для транспортной задачи, так как метод потенциалов гораздо экономнее, для небольших размерностей он вполне работоспособен. Отчет по результатам мы для экономии места не приводим, найденное оптимальное решение полностью соответствует тому, которое в данной задаче было получено вручную.

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

ново анализируются интерпретатором системы при каждом перевычислении.

13.2. Оптимизация в пакете MATLAB

Система компьютерной математики MATLAB состоит из ядра и многочисленных расширений (toolboxes), их насчитывается более 80. Существуют специализированные расширения для самых различных приложений — от символьных вычислений до обработки изображений и имитационного моделирования.

Для решения оптимизационных задач во всех версиях системы имеется Optimization Toolbox, в дополнение к нему, начиная с версии 7.0.1 (2004 г.), поставляется пакет расширений Genetic Algorithm and Direct Search Toolbox.

Поскольку круг оптимизационных задач весьма разнообразен и наилучшего универсального алгоритма не существует, в Optimization Toolbox име-

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

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

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

С другой стороны, даже давно известные классические методы за те десятилетия, пока шел прогресс в области оптимизации и создавались промышленные алгоритмы, претерпели значительные изменения и продолжают совершенствоваться. Примером может служить поиск по образцу (метод конфигураций Хука — Дживса). В решателе patternsearch, включенном в пакет расшире-