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

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

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

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

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

10.5. Методы поиска и оценки решений

Методы поиска решений

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

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

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

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

1) наличие неявных ограничений для зависимых (внутренних) переменных;

2) наличие подразумеваемых ограничений, которые приняты при построении модели;

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

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

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

Оценка решения

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

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

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

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

1) упростить модель так, чтобы можно было использовать простые алгебраические методы;

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

3) с помощью вспомогательной модели построить ряд прогнозов и проверить их на полной модели;

4) если оптимизационные расчёты подтверждают тренды, полученные из вспомогательной модели, то успех в объяснении свойств модели достигнут.

Всё это способствует уменьшению разрыва между оптимумом системы и оптимумом модели.

Целями же второго этапа оценки результатов решения, анализа чувствительности, являются следующие:

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

2. Уточнение данных о дополнениях или модификации системы с целью улучшения показателей её работы.

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

4. Выяснение возможной реакции системы на неуправляемые внешние воздействия.

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