Этапы решения прикладных задач оптимизации

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

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

1. Ранжирование критериев оптимальности (метод уступок).

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

Далее решается задача оптимизации по главному критерию Ki, в результате чего определяется его оптимальное значение КГ. Затем назначается величина уступки ui>0, то есть максимальное значение отклонения от Ki, которое можно допустить при оптимизации по следующему по важности критерию Кг. Оптимизация по Кг выполняется при дополнительном условии: нельзя отклоняться от Ki более, чем на щ. Если по первому критерию задача решалась на минимум, то это дополнительное ограничение имеет вид Ki< Ki*+m, а если на максимум

- то Ki>Ki* - ui. Определяется оптимальное значение второго критерия Кг* при уступке по первому, назначается уступка по второму критерию U2>0, вводится ещё одно дополнительное ограничение, теперь на отклонение Кг от Кг*, и решается задача оптимизации по Кз и т.д.

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

2. Свёртка критериев.

Вместо нескольких критериев вводится один в виде их взвешенной суммы.

Весовые множители vi,V2,..., vn характеризуют относительную важность критериев. Это положительные числа, сумма которых равна единице. Фактически речь снова идёт о ранжировании критериев, но с заданием количественных характеристик важности каждого из них. Это можно сделать следующим образом. Важность главного критерия принимаем за единицу (wi=l), а для каждого из остальных устанавливаем его относительную важность по сравнению с главным Wi (i=2,...,n). Все полученные положительные числа должны быть меньше единицы. Затем каждое из них, в том числе и важность главного критерия (она равна 1), делим на их сумму и получаем весовые коэффициенты Vi (i=l,2,...,n). Можно в качестве весовых коэффициентов принять и величины Wj (i=2,...,n), не добиваясь равенства единице суммы весов, так как умножение критерия на положительное число не меняет оптимального решения.

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

Если в конкретной многокритериальной задаче не удаётся использовать ни один из способов её сведения к однокритериальной, то приходится изменить подход к оптимизации, само понятие оптимальности. Один из таких приёмов состоит в оптимизации по Парето [7,9,18 ].

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

Если численные значения каждого критерия для всех допустимых решений, отложить по соответствующей координатной оси, то получим множество точек так называемого критериального пространства. Если в задаче минимизации по критериям Ki, К2,..., Кп для двух точек этого множества A(Kia,K2a,..., Кпа) и B(Kib,K2b,..., Knb) выполнены неравенства Kia b (i=l,2,...,n) и хотя бы для одного значения i соответствующее неравенство выполнено строго (иначе это совпадающие точки), то точка А (и соответствующее ей решение задачи) называется доминирующей над точкой В, а точка В называется доминируемой. Заметим, что было бы ошибочным определить множество Парето как множество доминирующих точек, как это иногда делается [13 ]. Дело в том, что в множество Парето очевидно не входят доминируемые точки, но из двух точек не обязательно одна доминирующая. Вообще в исходном множестве допустимых решений (соответственно множестве точек критериального пространства) может и не быть доминирующих точек. Поэтому множество Парето- это подмножество недоминируемых (т.е. эффективных) точек исходного множества критериального пространства, то есть недоминируемых допустимых решений. Если два решения по некоторым критериям могут быть равноценны, то нельзя утверждать, что множество Парето - это множество решений, каждое из которых нельзя улучшить сразу по всем критериям. Например, для задачи минимизации по двум критериям для двух решений А и В выполнено Kia< Kib и Кга= Кгь и других допустимых решений нет. Переходя к решению А от решения В, его нельзя улучшить по всем (двум) критериям, но можно улучшить по одному (первому), не ухудшая по остальным (второму), поэтому оно не входит в множество Парето.

Для графической иллюстрации рассмотрим задачу минимизации по двум критериям Кл и Кг. Предположим, что нам известны все допустимые решения, из которых нам предстоит сделать выбор по этим двум критериям и для каждого решения вычислены величины каждого критерия. Геометрически на координатной плоскости с осями Ki и Кг все допустимые решения будут представлены точками (рис. 1.1). Как определить какие точки входят в множество Парето? Другими словами, по какому правилу мы можем исключить заведомо не эффективные решения? Очевидно, в это множество из всех допустимых точек попадут только точки A,B,C,D, причём только точки А и D соответствуют мини- мимизации по отдельным критериям. Заметим, что в задаче на минимум точка входит в множество Парето, в том и только в том случае, если в третьем квадранте системы координат, построенной с центром в этой точке, нет других точек.

Пример построения множества Парето

Рис. 1.1 Пример построения множества Парето

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

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

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

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

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

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

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

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

Если вычисление критерия оптимальности и проверка выполнения ограничений могут быть разбиты на этапы так, что на каждом этапе изменяется только одна или небольшое число переменных, то необходимо рассмотреть возможность использования динамического программирования. К примеру, целевая функция представляет собой сумму слагаемых, каждое из которых зависит только от одной переменной K(xi,X2,...,xn)=fi(xi)+f2(x2)+...+fn(xn) и есть система ограничений в виде неравенств, каждое из которых содержит не более двух последовательных переменных gj(xj,Xj+i)

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >