Методика решения задач оптимизации
При решении любой конкретной задачи оптимизации необходимо выполнить следующую последовательность работ: 1. Содержательно поставить задачу оптимизации. Для этого следует возможно более полно определить (классифицировать) объект оптимизации, т. е. процесс или систему; если систему, то динамическую или статическую; если объект динамический, то непрерывный или дискретный, детерминированный или стохастический. Необходимо также сформулировать критерий оптимизации, т. е. сформулировать цель оптимизации (что необходимо получить от процесса или системы). И, наконец, следует достаточно полно определить возможности оптимизации, т. е. сформулировать ограничения на переменные и параметры объекта оптимизации. 2. Полностью определить неизменяемую часть объекта оптимизации, т. е. выделить те характеристики и параметры, которые заданы в виде требований к процессу или системе или существуют объективно. Определить изменяемую часть объекта оптимизации, т. е. выделить характеристики и параметры, изменением которых можно влиять на критерий оптимизации. 3. Выбрать математический метод и построить математическую модель объекта оптимизации, т. е. описать объект оптимизации на языке выбранного математического метода. 4. В соответствии с п. 3 определить вид и характер ограничений, накладываемых в данной задаче на изменяемые характеристики и параметры процесса или системы. 5. В соответствии с пп. 3, 4 сформулировать и формализовать критерий, выбрать метод решения и полностью формально поставить задачу оптимизации. 6. Разработать алгоритм решения задачи оптимизации. 7. Разработать программу решения задачи оптимизации на ЭВМ. Отладить программу. Решить задачу оптимизации на ЭВМ.
Рассмотрим теперь более подробно каждый пункт приведенной Для нужд практики может быть использована классификация объектов оптимизации, показанная на рис. 15.1. Содержательная формулировка критерия оптимизации процесса или системы, а также содержательное определение возможностей оптимизации не нуждаются в дополнительном пояснении. Задача оптимизации отличается от задачи синтеза так же, как часть отличается от целого, т. е. оптимизация является частью синтеза и в этом смысле в известной мере опирается на него. Иными словами, оптимизировать можно то, что уже хотя бы в какой-то мере создано. Таким образом, если имеются хотя бы «контуры» проектируемого процесса или системы, то всегда можно назвать такие характеристики и параметры этого «контура», которые в данном варианте процесса или системы при оптимизации меняться не будут. Например, если проектируется внешнеэкономическая деятельность предприятия, то таможенные пошлины определяются государством и изменению не подлежат.
Рисунок 15.1 Классификация объектов оптимизации
Выделение изменяемой части объекта оптимизации, по существу, сводится к назначению переменных оптимизации, тех самых характеристик, варьируя значения которых, можно изменять качество процесса или системы, т.е. изменять показатель или критерий оптимизации. Именно эти переменные часто называют оптимизируемыми переменными или параметрами, так как они, принимая некоторые (оптимальные) значения, доставляют экстремум критерию оптимизации. При выборе и выделении переменных оптимизации следует следить за тем, чтобы их было сравнительно немного и чтобы изменение каждой из них действительно оказывало влияние на критерий оптимизируемого процесса или системы. Естественно, что такое пожелание предполагает хорошее знание особенностей функционирования объекта оптимизации.
Вопрос о построении математической модели объекта оптимизации тесно связан с его идентификацией. Действительно, если объект оптимизации статический, то для его описания применяются математические зависимости типа формул, алгебраических уравнений, логических уравнений или графов. Если объект оптимизации оказался динамическим, то применяют математические конструкции, зависящие в явном или неявном виде от времени, т. е. динамические зависимости. Аналогично можно проследить связь между идентификацией и построением математической модели объекта оптимизации по признакам детерминизма и дискретности. В математике существует довольно большое количество методов и способов описания статических и динамических объектов. Однако на практике применяется лишь несколько наиболее изученных и отработанных из них. Для построения математических моделей объектов оптимизации в технике связи наиболее часто используются следующие математические зависимости: — непрерывные функции; — дискретные (в том числе логические) функции; — линейные алгебраические уравнения; — нелинейные алгебраические уравнения; — трансцендентные уравнения; — обыкновенные линейные дифференциальные уравнения; — обыкновенные нелинейные дифференциальные уравнения — зависимости теории вероятности; — уравнения в частных производных; — зависимости теории графов и сетей. Выбор вида (или видов) математических зависимостей для построения математической модели объекта оптимизации, как уже упоминалось, выше, во многом определяется принадлежностью объекта к тому или иному классу. Обычно этот выбор зависит также и от ряда других факторов, к которым следует отнести следующие: способ задания критерия оптимизации, способ задания ограничении на оптимизируемые параметры объекта оптимизации, наличие или отсутствие адекватных машинных методов и алгоритмов реализации модели объекта оптимизации, сложность применения математических зависимостей того или иного вида для описания объекта оптимизации. Анализ перечисленных факторов показывает, что выбор математического метода для построения математической модели объекта оптимизации в достаточной степени субъективен. Это обстоятельство исключает возможность выработки единых рекомендаций по выбору математического метода.
Выбор математического аппарата для описания объекта оптимизации накладывает вполне определенные ограничения на все аспекты решения задачи оптимизации, в том числе и на форму, и метод построения и реализации критерия оптимизации. Иными словами, если объект оптимизации описан, например, в метрике (языке) координата, скорость, ускорение, то и критерий оптимизации должен быть сформулирован и описан также в этой метрике. Однако, кроме языковой стороны, при формализации критерия оптимизации встают еще некоторые вопросы, о которых и пойдет речь ниже. Дело в том, что оценка оптимальности объекта может производиться (и обычно производится) не по одному, а по нескольким частным показателям или критериям. Принцип формирования обобщенного показателя где xi – параметры оптимизируемого процесса или системы, т. е. суть аргументы функции частных и обобщенного показателей; Приведенный способ формирования обобщенного показателя позволяет учитывать ограничения, накладываемые на частные показатели. Эти ограничения могут быть следующего вида: где Пример плоских ограничений показан на рис. 15.2. Здесь область существования функции В соответствии с известными принципами формирования обобщенного показателя функция
1) 2) внутри области, ограниченной условиями существования суммы 3) вне области, ограниченной этими условиями, функция
Рисунок 15.2 Пример плоских ограничений.
4) для обеспечения возможности автоматической оптимизации непрерывными методами функция 5) функция Для удовлетворения некоторых из перечисленных выше требований к обобщенному показателю оптимальности может быть применен метод формирующих функций. Так, для удовлетворения требований 1, 2 и 3 можно использовать формирующую функцию вида или Обобщенный показатель с применением формирующей функции
При применении формирующей функции Вообще, для придания функции «Направление» оптимизации процесса или системы по показателю
где Выражение (15.2) отображает требование «равноценности» частных показателей оптимальности в дифференциально малой области экстремума функции Машинные методы оптимизации могут быть классифицированы следующим образом: – основанные на применении классических математических методов; – основанные на применении принципа максимума; – основанные на применении линейного и нелинейного дискретного программирования; – основанные на применении динамического программирования; – основанные на градиентных методах; – специальные методы оптимизации;
– методы оптимизации графов и граф-сетей; – методы оптимизации в условиях неопределенности. Выбор класса машинных методов оптимизации для решения конкретной задачи зависит в основном от следующих факторов, от принадлежности объекта оптимизации к тому или иному классу, от способа задания критерия оптимизации, от результатов композиции и декомпозиции объекта оптимизации, от личных склонностей и уровня подготовки лица, принимающего решение. Анализ перечисленных факторов показывает, что выбор машинного метода оптимизации хотя и в меньшей степени, чем выбор математической модели объекта оптимизации, все же остается весьма субъективным. Это обстоятельство в значительной степени затрудняет возможность выработки единых рекомендаций по выбору машинного метода оптимизации. Однако основанные на опыте частные рекомендации в значительной мере могут облегчить работу инженера при решении конкретных задач оптимизации Итак, если объектом оптимизации оказался некоторый объект и для его описания применена непрерывная на некотором участке функция критерия, то в качестве машинного метода оптимизации такого объекта может быть рекомендован один из методов, основанных на классической математике, один из градиентных методов или один из специальных методов. Если в качестве объекта оптимизации выступает некоторая система (или процесс) управления, описываемая дифференциальными уравнениями, а критериальная функция представлена в виде интеграла от функции фазовых координат системы, то в качестве машинных методов оптимизации здесь может быть рекомендована целая серия процедур от классического вариационного исчисления до принципа максимума и динамического программирования включительно. Задачи оптимизации, в которых в качестве объекта оптимизации выступают сети связи, а в качестве критериев оптимальности применяются функции или функционалы, связанные с пропускными способностями, могут успешно решаться с помощью машинных методов оптимизации сетей или машинных вероятностных методов (марковские методы, методы теории игр п др.). Проблему оптимизации в смысле разработки машинного алгоритма целесообразно рассматривать в двух направлениях: направлении, когда объект оптимизации представляется полностью своей критериальной функцией или функционалом, и направлении, когда объект оптимизации и его критериальная функция или функционал представляются самостоятельно и раздельно. Рассмотрим вначале первое направление. Случай, когда объект оптимизации представлен полностью своей критериальной функцией или функционалом, хотя и является простейшим, встречается весьма часто. На самом деле, предположим, что при проектировании того или иного объекта ЛПР удастся выразить некоторое качество Но тогда получается как раз тот случай, когда необходимо найти экстремум (максимум пли минимум в зависимости от физической сущности задачи) функции или функционала Проблема разработки алгоритма оптимизации и этом случае сводится к выбору или разработке программы нахождения экстремума функции по нескольким переменным. Если функция Гораздо более сложным оказывается путь построения алгоритма оптимизации, когда объект оптимизации и его критериальная функция (или функционал) представлены самостоятельно. В этом случае процедура оптимизации оказывается составной и сводится к следующему: 1) первоначальное задание некоторого состояния объекта и вычисление начального значения критериальной функции (или функционала); 2) изменение значений оптимизируемых параметров и вычисление соответствующих изменений состояния объекта и критериальной функции (функционала); 3) определение оптимальных (в смысле выбранного критерия) направлений изменения оптимизируемых параметров, вычисление их новых значений и установка этих значении на модели объекта; 4) контроль на окончание оптимизации; 5) повторение пп. 2–4 до тех пор, пока по п. 4 не произойдет останов. Более наглядно приведенный алгоритм оптимизации представлен на рис. 15.3.
Рис. 15.3 Алгоритм оптимизации объекта
Рассмотрение структурной схемы алгоритма оптимизации показывает, что для решения сложных задач оптимизации приходится разрабатывать не только алгоритм собственно оптимизации, но и алгоритмы модели оптимизируемого объекта и алгоритм вычисления критериальной функции или функционала.
Г Л А В А 16 Общая задача оптимизации Будем рассматривать общую задачу оптимизации, сформулированную в следующей стандартной форме. Рассмотрим задачу максимизации:
где
Ограничения (16.1) – функциональные ограничения; ограничения (16.2) – прямые. Функции Удобно иметь все неравенства одного знака. Если же встретятся неравенства вида Функциональное ограничение всегда можно представить в виде неравенств. Для этого ограничение вида Прямые ограничения (16.2), которых может и не быть (S может быть пустым множеством), всегда записывают, как условия на неотрицательность. Такой знак прямых ограничений естественно сохранить и в задаче на минимум, в которой знаки неравенств в функциональных ограничениях меняются на противоположные. Все прямые ограничения можно представить в таком виде, обозначая Чтобы обеспечить замкнутость допустимого множества, предполагается, что все неравенства записаны как нестрогие. Задача на оптимум, вообще говоря, не всегда имеет решение. Задача
Теорема Вейерштрасса: непрерывная функция, определенная на непустом замкнутом ограниченном множестве, достигает максимума (минимума), по крайней мере, в одной точке этого множества.
Поскольку обычно целевая функция берется непрерывной, а допустимое множество замкнутым, то ограниченность допустимого множества – единственное необеспеченное условие. Во многих случаях допустимое множество будет ограничено, однако это не будет очевидным без соответствующего исследования. Будет установлено, что теорема Вейрштрасса дает достаточныеусловия оптимума. Задачи, в которых не выполняются условия теоремы, могут иметь оптимум[4]. Задача на оптимум может, конечно, быть и тривиальной. Функция
16.2 Общий принцип решения Оптимальная точка должна лежать в допустимом множестве. Это либо внутренняя, либо граничная точка множества. Пусть оптимальная точка является внутренней. Тогда существует окрестность, содержащая эту точку и целиком лежащая в допустимом множестве, причем рассматриваемая точка оптимальна относительно точек этой окрестности. Такая точка должна удовлетворять обычным требованиям к безусловному оптимуму, то есть она должна быть критической точкой f ( Пусть теперь оптимальная точка лежит на границе. Тогда в любой ее окрестности имеются точки как принадлежащие, так и не принадлежащие допустимому множеству. Поэтому, вообще говоря, нельзя сказать, что эта точка является оптимальной относительно точек своей окрестности. Граничная оптимальная точка не обязательно должна быть критической точкой f. Таким образом, имеем общий принцип решения: решение общей задачи на оптимум (max или min Мы выделили два типа оптимальных точек – внутреннийи граничныйоптимумы. Это показано на рис. 16.1 а и б.На обоих рисунках эллиптические кривые представляют собой линии (или в общем случае поверхности) уровня целевой функции, а выделенная область – это допустимое множество. Оптимальная точка А является внутренним оптимумом на рис.16.1 аи граничным на рис. 16.1 б.
Рисунок 16.1 Внутренний (а) и граничный (б) оптимумы
В принципе, задача оптимизации может быть решена следующим образом. Находятся критические точки Если
16.3 Принцип Парето Принцип Парето позволяет сократить множество исходных вариантов, то есть исключить те варианты решений, которые заведомо будут неудовлетворительными. Предположим, что мы сделали некоторый выбор. Обозначим его через
причем хотя бы одно из неравенств – строгое. Очевидно, что выбор Предположим, что цели субъекта определяются двумя однозначными функциями:
Тогда каждому допустимому значению переменной определяют параметрическое задание некоторой кривой
Рисунок 16.2 Парето-предпочтение альтернатив
Из тех же соображений должен быть исключен участок Таким образом, принцип Парето заключается в том, что выбирать в качестве решений следует только тот вектор Принцип Парето играет очень важную роль в автоматизации проектирования. Предположим, например, что речь идет о проектировании водного комплекса. В результате создания этого комплекса появится возможность обеспечить водой несколько крупных промышленных и сельскохозяйственных объектов и тем самым повысить их эффективность. Но возникнет целый ряд отрицательных явлений. Большая площадь водохранилища, которая необходима для регулярной работы комплекса, приведет к большим потерям воды в результате испарения. Кроме этого, уменьшение количества воды в речной системе ухудшит условия рыболовства и судоходства, а строительство промышленных комплексов увеличит объем загрязнений и ухудшит качество воды, поступающей на поля. Одним словом, ситуация оказывается многокритериальной. Цели проектировщика могут быть записаны в виде:
Проектировщик сталкивается с необходимостью поиска компромисса, одним из путей которого является построение множества Парето, изучение которого дает большой объем информации. Лицо, принимающее решение, сможет увидеть, во сколько обойдется увеличение одного из показателей, как это скажется на остальных показателях, значения которых непременно ухудшатся. Как правило, это множество имеет очень сложную природу. Помимо критериев Приближенное построение множества Парето относится к числу очень важных и очень трудных задач численного анализа. Рассмотрим простейший случай двух критериев. Пусть речь идет о задаче Каждой точке ставят в соответствие некоторую точку
Рисунок 16.3 Приближенное построение множества Парето Множество Приближенное построение множества Парето сводится к последовательному решению ряда задач математического программирования. Опишем одну из возможных схем расчета. Зафиксируем некоторые значения критериев
Значения Теперь решаем две оптимизационные задачи. Решив эти задачи, мы определим точки Для уточнения аппроксимации, решив задачи 3 и 4, мы находим еще две точки Рисунок 16.4 Краевые задачи при построении множества Парето Значения Аппроксимацию множества Парето можно провести и другим способом. Пусть
Составим новый критерий и решим следующую задачу математического программирования:
Оказывается, что решение этой задачи определяет такой вектор принадлежит множеству Парето. Поэтому аппроксимацию множества Парето мы можем осуществить следующим образом (рис. 16.4). Решаем задачу:
где | ||||||||||||||
|
|