Презентация на тему "Многокритериальные задачи. Метод ограничений"

Содержание

• 
  Слайд 1

  Многокритериальные задачи. Метод ограничений

• 
  Слайд 2

  Общие сведения о многокритериальных задачах

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

• 
  Слайд 3
  

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

• 
  Слайд 4
  

  Проблемы и классификация методов решения задач многокритериальной оптимизации

  Основные проблемы, возникающие при разработке методов МКО: 1. Проблема нормализации критериев, то есть приведение критериев к единому (безразмерному) масштабу измерения. 2. Проблема выбора принципа оптимальности, то есть установление, в каком смысле оптимальное решение лучше всех остальных решений. 3. Проблема учета приоритетов критериев, возникающая в тех случаях, когда из физического смысла ясно, что некоторые критерии имеют приоритет над другими. 4. Проблема вычисления оптимума задачи МКО. Речь идет о том, как использовать методы линейной, нелинейной, дискретной оптимизации для вычисления оптимума задач с определенной спецификой. 4

• 
  Слайд 5
  

  Основные проблемы, возникающие при разработке методов МКО: 1. Проблема нормализации критериев, то есть приведение критериев к единому (безразмерному) масштабу измерения. 2. Проблема выбора принципа оптимальности, то есть установление, в каком смысле оптимальное решение лучше всех остальных решений. 3. Проблема учета приоритетов критериев, возникающая в тех случаях, когда из физического смысла ясно, что некоторые критерии имеют приоритет над другими. 4. Проблема вычисления оптимума задачи МКО. Речь идет о том, как использовать методы линейной, нелинейной, дискретной оптимизации для вычисления оптимума задач с определенной спецификой. 4

• 
  Слайд 6

  Метод ограничений

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

• 
  Слайд 7
  

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

• 
  Слайд 8
  

  Рассмотрим задачу многокритериальной оптимизации (1) где  — векторный критерий оптимальности,   — частные критерии оптимальности (скалярные),   — множество допустимых значений вектора варьируемых параметров.   8

• 
  Слайд 9
  

  В метод ε-ограничений в качестве скалярного критерия оптимальности  используется самый важный из частных критериев оптимальности , а остальные частные критерии учитываются с помощью ограничений типа неравенств вида   Таким образом, в методе  ε-ограничений вместо задачи (1) решается задача условной оптимизации со скалярным критерием оптимальности  : (2) где (3)   9

• 
  Слайд 10
  

    Метод ε-ограничений в значительной мере свободен от указанного выше недостатка метода весовых множителей в случае, когда множество  не выпукло (см. рис. 1). На рис. 1 точка A2 в данном методе является доступной.   10 Рис. 1.  Геометрическая интерпретация метода ε-ограничений: случай двух критериев; множество DФ не выпукло; самым важным является критерий ф1(X); на критерий ф2(X) наложено ограничение ф2(X) ≤ ε2.

• 
  Слайд 11

  Метод штрафных функций

  Совершенно иной подход используется в методах штрафных и барьерных функций. Ограничения задачи специальным образом отражаются в критерии, в результате чего критерий модифицируется, а исходная задача на условный экстремум сводится к задаче на безусловный экстремум. В методе штрафных функций в критерий вводится штраф при нарушении условий задачи. Пусть в общем случае имеем задачу f(x) → min; (4) ji(x) £ 0,  ; (5) yi(x) = 0 ,  . (6) Тогда можно построить вспомогательную функцию Q(x) = f(x) + aH(x), (7) где H(x)–функция штрафа, a – параметр штрафа.   11

• 
  Слайд 12
  

  Вспомогательная функция играет роль модифицированного критерия, который при выполнении всех ограничений должен совпадать с исходным. Поэтому необходимо, чтобы в допустимой области Н(x) равнялась нулю. Для задачи (4) – (6) функция штрафа включает две составляющие , учитывающие ограничения-неравенства и ограничения-равенства соответственно и удовлетворяющие условиям (7) Возможны разные конструкции функций, обладающих указанными свойствами. Типичные представители составляющих штрафной функции имеют вид где р – натуральное число. Для дифференцируемости функций берут четные значения р, обычно р = 2. Чем больше a, тем сильнее влияет функция штрафа и, значит, тем точнее выполняются условия задачи.   12

• 
  Слайд 13
  

  Пример 1: f(x) = x → min; j(x)=3 – x £ 0. Теперь сведем эту задачу к определению безусловного экстремума вспомогательной функции. Построим штрафную функцию в соответствии с (7): H = [max (0, 3–x)]2. Тогда приходим к задаче Q=x+a[max (0, 3-x)]2min. 13 На рис. 2 и 3 показаны соответственно функции aH и Q для двух значений a. Видно, что точки минимума вспомогательной функции с увеличением a приближаются к точке условного минимума исходной задачи. Такой же вывод следует из аналитического решения. Действительно, при x

• 
  Слайд 14
  

  Пример 2: Рассмотрим влияние параметра шага в задаче Здесь   и    14 На рис. 4 построены линии уровня функции q для разных значений a и линия ограничения y. При a=0 имеем q=f, и минимум q достигается в точке безусловного минимума f: x1=x2=1. С увеличением a меняется форма линий уровня q и положение минимума. При a=1 минимум q смещается к линии ограничения, а при a=1000 он практически точно совпадает с условным минимумом задачи. В обоих примерах с увеличением a генерируемые точки приближаются к оптимальному решению извне допустимого множества. Поэтому ряд авторов называют рассматриваемый метод методом внешних штрафов.

• 
  Слайд 15
  

  15 Таким образом, чтобы безусловный минимум вспомогательной функции был близок к условному минимуму, необходимо брать очень большое значение a. Однако при больших a возникают серьезные трудности при поиске минимума вспомогательной функции. Поэтому предлагается решать последовательность задач минимизации Q с возрастающими значениями a. При этом в качестве начальной точки следующей задачи берется оптимальная точка предыдущей. Такой прием использован в следующем алгоритме штрафных функций. Алгоритм. Задать: начальную точку x0, точность e, начальное значение a0 и число b >1. 2. Минимизировать Q(x) одним из методов безусловной оптимизации, в результате чего определяется  3. Проверить: если  , то остановиться, приняв за оптимальное решение задачи. 4. Положить  , за начальную точку принять и вернуться на шаг 2.  

• 
  Слайд 16

  Метод барьерных функций

  16 В отличие от метода штрафных функций, данный метод применим к задачам с ограничениями только в виде неравенств. Суть метода заключается в том, что поиск начинается обязательно из внутренней точки и последующие точки не должны выходить из допустимой области. С этой целью задача модифицируется так, что при приближении к границе допустимой области растет барьер, препятствующий выходу на границу. Исходная задача на условный экстремум задается в виде f(x) → min; (8) ji(x) £ 0, (9) Она преобразуется в задачу безусловной минимизации вспомогательной функции Q(x) = f(x) + mB(x), где B(x) – барьерная функция, m – параметр барьера.  

• 
  Слайд 17
  

  17 Обязательное условие: внутренность области не должна быть пустой (имеются точки, в которых "ji (x)

• 
  Слайд 18
  

  18 Пример :f(x) = x → min; j(x)=3 – x £ 0. Барьерную функцию строим согласно (10). Тогда вспомогательная функция имеет вид   Находим точку минимума Q: .  Отсюда     Следовательно, с уменьшением m точки минимума вспомогательной функции приближаются к минимуму исходной задачи. В связи с возможными трудностями поиска при малых значениях m решается не одна, а последовательность вспомогательных задач с уменьшающимися значениями параметра барьера.

• 
  Слайд 19
  

  19 Алгоритм. Выбрать начальную точку x0 так, чтобы "ji(x0)