Способы решения многокритериальных задач оптимизации

Решение задач многокритериальной оптимизации

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

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

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

Ниже вы найдете подробные примеры решений по этой теме — изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий, перейдите в раздел: Контрольные работы по линейному программированию.

Многокритериальная оптимизация: примеры решений

Задача 1. Сформулировать экономическую задачу с двумя критериями эффективности и не менее 4 условий (ограничений).
Двумя способами:
1) методом идеальной точки
2) сведением к ЗЛП
Решая задачу вторым методом, добавьте дополнительное условие (ограничение) от ЛПР — обоснуйте. Сделать выводы по полученным данным.

Задача 2. Определить тип задачи и найти оптимальное решение, всеми способами. Фирма имеет возможность реализовывать свои товары на 4-х различных рынках (альтернативы A1 A2, А3 А4). При этом ставятся одновременно следующие цели: минимизация затрат на рекламу, завоевание максимальной доли рынка и максимальный объем продаж в течение планируемого периода. Исходные данные приведены в таблице.

Задача 3. Полуфабрикаты поступают на предприятие в виде листов фанеры. Всего имеется две партии материала, причем первая партия содержит 400 листов, а вторая 250 листов фанеры. Из поступающих листов фанеры необходимо изготовить комплекты двух видов. Комплект первого вида включает 4 детали 1-го типа, 3 детали 2-го типа и 2 детали 3-го типа. Комплект второго вида включает 2 детали 1-го типа, 4 детали 2-го типа и 3 детали 3-го типа. Лист фанеры каждой партии может раскраиваться различными способами. Количество деталей каждого типа, которое получается при раскрое одного листа соответствующей партии по тому или иному способу раскроя, представлено в следующей таблице. Стоимость одного листа первой партии составляет 1000 руб., а стоимость одного листа второй партии – 1200 руб. Цена комплекта первого вида составляет 150 руб., цена комплекта второго вида – 200 руб.
Необходимо решить многокритериальную задачу.
Критерий 1. Максимизация прибыли от продажи всех комплектов деталей.
Критерий 2. Максимизация количества комплектов первого вида.
Критерий 3. Максимизация количества комплектов второго вида.
Примечание: для построения Парето-оптимального множества рассмотреть только критерии 2,3..

Задача 4. Дана задача векторной оптимизации: $$ z_1=-5x_1+2x_2 \to \max,\\ z_2=-3x_1+x_2 \to \max,\\ z_3=3x_1 \to \max,\\ x_1+x_2 \le 18,\\ 1 \le x_1 \le 10,\\ 1 \le x_2 \le 9. $$ Требуется определить переговорное множество, а затем решить данную задачу методом последовательных уступок (допустимые уступки по первым двум критериям принять равными $\delta_1=3$ и $\delta_2=2$).

Задача 5. Возможные значения курса базовой валюты в течении ближайшего года представлены четырьмя интервалами. Банк рассматривает четыре инвестиционных проекта, каждый из которых связан с международным бизнесом. Последствия от принятия банком го инвестиционного проекта при условии, что курс валюты окажется в м интервале, приведены в таблице 1. В таблице 2 приведены прогнозируемые экспертами вероятности возможных интервалов курса базовой валюты.
Требуется построить матрицу сожалений, найти решения, рекомендуемые правила Вальда, Сэвиджа, максимального ожидаемого дохода и минимального ожидаемого риска, а также определить проекты, оптимальные по Паретто. .

Источник

5.2. Методы решения многокритериальной задачи оптимизации

Метод обобщенного критерия . Метод перехода от несколь-

ких критериев f 1 , f 2 ,… f m к одному, задаваемому новой функцией

называется сверткой или методом обобщенного крите-

α j называются весовыми коэффициентами. Чем больше

α j , тем больший «вклад» вносит j -й критерий в обобщенный крите-

рий z . Иногда требуют, чтобы ∑ α j = 1 .

Пример 5.3. Решить задачу методом обобщенного критерия

Решение. Пусть α 1

= 0,6 . Тогда задача двухкритери-

альной оптимизации сводится

к задаче одного критерия

z = α 1 f 1 + α 2 f 2 = 0,4(4x 1 + x 2 ) + 0,6(x 1 + 2 x 2 ) = 2,2x 1 + 1,6x 2 → max

x 1 + x 2 + x 3 = 7 x 1 + x 4 = 5 x 2 + x 5 = 4

Перепишем целевую функцию z в виде z − 2,2x 1 − 1,6 x 2 = 0 . Составим начальную симплекс-таблицу

Вводим в базис переменную x 1 и, так как

дим из базиса x 4 .

Вводим в базис переменную x 2

дим из базиса x 3 .

Последняя строка и столбец свободных членов содержит только положительные числа, следовательно, мы получили опти-

f 2 * = f 2 (5;2) = 9 .

5.2. Выбор весовых

Метод приоритетов. Метод приоритетов решения много-

критериальных задач применяется в том случае, когда критерии f i

упорядочены по их относительной важности.

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

Пример 5.4. Решить двухкритериальную задачу методом приоритетов.

Источник

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

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

Метод поиска Парето – эффективных решений. Рассмотрим его суть на примере использования двух критериев. Критерии при использовании данного метода являются равнозначными. Пусть имеется множество вариантов решения по каждому из вариантов определены значения всех критериев. Представим множество оценок вариантов решения в пространстве критериев на рисунке 4.

a b

P(Y)

c d

e

0

Рисунок 4. Иллюстрация поиска Парето-эффективных решений

На рисунке приняты следующие обозначения:

К1 и К2 – критерий оценки вариантов решения;

К11, К12,…,К1m – значения первого критерия для 1, 2,…, m-го варианта решения;

К 21, К22,…,К2m – значения второго критерия для 1, 2,…,m-го варианта решения;

P(Y) – множество Парето-эффективных оценок решений

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

Преимущества метода: 1) критерии равнозначны; 2) метод математически объективен. Недостаток метода: 1) одно окончательное решение получается только в частном случае, т. е. количество Парето-эффективных решений, как правило, больше одного.

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

— максиминный (минимаксный) критерий.

Аддитивный критерий. В них целевая функция получается путем сложения нормированных значений частных критериев. В общем виде целевая функция имеет следующий вид:

Где n – количество объединяемых частных критериев;

С2 – весовой коэффициент i-го частного критерия;

F2(X) – числовое значение i-го частного критерия;

F (X) – i-й нормирующий делитель;

Fi(X) – нормированное значение i-го частного критерия.

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

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

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

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

Преимущество данного метода: как правило, всегда удается определить единственный оптимальный вариант решения. Недостатки данного метода:

— трудности (субъективизм) в определении весовых коэффициентов;

— аддитивный критерий не вытекает из объектной роли частных критериев и поэтому выступает как формальный математический прием;

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

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

Основные этапы анализа логистической системы

Рассмотрим подробно этапы анализа логистической системы в таблице 22.

Таблица 22 Этапы анализа логистической системы

Научные инструменты системного анализа

1. Анализ логистической проблемы

Обнаружение логистической проблемы.

Точное формулирование логистической проблемы.

Анализ логической структуры проблемы.

Анализ развития проблемы (в прошлом и

Методы: сценариев, диагностический, деревьев целей, экономического анализа.

Продолжение таблицы 22

Научные инструменты системного анализа

— Определение внешних связей проблемы (с другими проблемами).

Выявление возможности принципиальной разрешимости проблемы.

2. Определение логистической системы

Спецификация задачи исследования.

Определение позиции наблюдателя (эксперта).

Выделение элементов (определение границ разбиения логистической системы).

Определение элементов системы.

Методы: матричные, кибернетические модели.

3. Анализ структуры логистической системы

Определение уровней иерархии.

Определение процессов функций.

Определение и спецификация процессов управления и каналов информации.

Спецификация процессов, функций текущей деятельности (рутинных) и развития (целевых).

Методы: диагностические, матричные, сетевые, морфологические, кибернетические модели.

4. Формулирование общей цели и критерия логистической системы

Определение целей и требований надсистемы.

Определение целей и ограничений

Методы: экспертных оценок («Дельфи»), деревьев целей, экономического анализа, морфологический, кибернетические

Формулирование общей цели.

Декомпозиция целей и критериев по подсистемам.

Композиция общего критерия из критериев подсистем.

модели, нормативные операционные модели (оптимизационные, имитационные, игровые).

5. Декомпозиция цели, выявление потребностей в ресурсах и процессах

Формулирование целей верхнего ранга.

Формулирование целей текущих процессов.

Формулирование целей эффективности.

Формулирование целей развития.

Формулирование внешних целей2 и ограничений.

Выявление потребностей в ресурсах и процессах.

Методы деревьев целей, сетевые и описательные модели.

Источник