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

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

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

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

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

Решается задача оптимизации по главному критерию К), в результате чего определяется его оптимальное значение К]*. Затем назначается величина уступки — uj, то есть максимальное значение отклонения от Kj, которое можно допустить при оптимизации по следующему по важности критерию К.2. Оптимизация по К.2 выполняется при дополнительном условии: нельзя отклоняться от К более чем на и. Если по первому критерию задача решалась на минимум, то это дополнительное ограничение имеет вид К < Kj* + + u 1, а если на максимум — то Ki > Kj* — щ. Определяется оптимальное значение второго критерия К^* при уступке по первому, назначается уступка по второму критерию U2, вводится еще одно дополнительное ограничение, теперь на отклонение К2 от К2*, и решается задача оптимизации по К3 и т. д.

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

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

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

Весовые множители характеризуют относительную важность критериев. Это положительные числа, сумма которых равна единице. Фактически речь снова идет о ранжировании критериев, но с заданием количественных характеристик важности каждого критерия. Это можно сделать следующим образом. Важность главного критерия принимаем за единицу (wi = I), а для каждого из остальных устанавливаем его относительную важность по сравнению с главным wj (i = 2, ..., п). Все полученные положительные числа должны быть меньше единицы. Затем каждое из них, в том числе и важность главного критерия (она равна I), делим на их сумму и получаем весовые коэффициенты v, (i = 1, 2, ..., п). Можно в качестве весовых коэффициентов принять и величины w; (i = 2, ..., п), не добиваясь равенства единице суммы весов, так как умножение критерия на положительное число не меняет оптимального решения.

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

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

Вместо оптимальных предлагается искать так называемые эффективные решения, то есть такие решения, каждое из которых нельзя улучшить сразу по всем критериям. Множество таких решений называется множеством Парето. Естественно, что в него входят решения, оптимальные по отдельным критериям, но, как правило, не только такие решения. Для иллюстрации этого положения рассмотрим задачу минимизации по двум критериям К] и К-2- Предположим, что нам известны все допустимые решения, из которых нам предстоит сделать выбор по этим двум критериям, и для каждого решения вычислены величины каждого критерия. Геометрически на координатной плоскости с осями К и К.2 все допустимые решения будут представлены точками (рис. 1.1). Как определить, какие точки входят в множество Парето? Другими словами, по какому правилу мы можем исключить заведомо неэффективные решения?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 1.1. Контрольные вопросы к разделу 1
  • 1. Может ли множество Парето быть пустым?
  • 2. В множество Парето из всех точек критериального пространства входит одна и только одна точка. Что это означает? Какая связь между критериями имеется в этом случае.
  • 3. Могут ли все точки критериального пространства быть эффективными, то есть входить в множество Парето?
  • 4. В чем смысл построения множества Парето?
  • 5. Нужно ли строить множество Парето для того, чтобы применить метод уступок или метод весов?
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >