Основы теории оптимизации (стр. 87 )

В оптимизационных исследованиях обычно используются модели трёх основных типов: 1) аналитические модели; 2) модели поверхности отклика; 3) имитационные модели.

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

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

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

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

10.2. Реализация модели

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

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

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

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

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

1) модификация модели с целью преодоления вычислительных трудностей;

2) преобразование модели для повышения эффективности решения;

3) анализ модели с целью нахождения возможных признаков решения задачи.

10.3. Преодоление вычислительных трудностей.

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

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

Повышение эффективности решения

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

Наиболее часто недифференцируемость функций в модели возникает в двух случаях: 1) условные операторы приводят к различным выражениям; 2) работа некоторых блоков модели зависит от значений выбранных переменных или функций, а также минимаксных операторов (min, max). Минимаксные операторы можно заменить системой неравенств. Если в модели много условных выражений, целесообразно не применять оптимизационные алгоритмы, в которых используются значения градиентов функций.

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

10.4. Анализ модели с целью нахождения возможных признаков решения задачи

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

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

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

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

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