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

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

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

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

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

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

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

Задача 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.1)

где x = (x1,x2, … , xn) – вектор искомых переменных, а D – множество допустимых решений, заданное с помощью тех или иных ограничений.

где F(x) — векторная функция векторного аргумента. Поскольку в записи модели (5.2) используется векторная функция, многокритериальную задачу часто называют задачей векторной оптимизации.

Сущность многокритериальной задачи (5.1) (или (5.2) состоит в нахождении такого решения, принадлежащего области допустимых решений (т. е. такого x Î D), которое в том или ином смысле максимизирует (или минимизирует) значения всех целевых функций f i(x), где i = 1, …, k.

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

Так как многокритериальная не имеет в общем случае строго математического решения, то есть, как правило, невозможно найти решение при котором достигается максимум (минимум) сразу по всем критериям, то приходится приходить к какому-то соглашению о том, какое решение будет наиболее предпочтительным в заданных условиях. Отсюда следует, что, во-первых, в теории многокритериальных задач понятие оптимальности получает различные и притом нетривиальные истолкования, а, во-вторых, то, что многокритериальная задача в общем случае решается с привлечением неформальной субъективной информации того, кто принимает окончательное решение или по терминологии теории принятия решений – лица, принимающего решения (ЛПР).

или, что то же самое:

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

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

Рис. 5.1. Субоптимальные решения задачи Примера 5.1.

5.2. Основные определения теории векторной оптимизации. Принцип Парето

Введем несколько определений.

Пусть решается задача (5.1) и есть x‘, x» — допустимые решения данной задачи. Говорят, что x‘ более предпочтительное решение по сравнению с x», если f i (x‘) ≥ f i (x») i=1,k), причем i0, такой, что f i (x’) > f i (x»). Другими словами, будем считать, что x‘ более предпочтительно по сравнению с x» , если оно не хуже x» по всем рассматриваемым критериям, причем среди всех критериев есть хотя бы один критерий с номером i0, для которого решение x‘ лучше, чем x»

Некоторое решение x* задачи (5.1) называется эффективным решением данной задачи, если для него не существует более предпочтительных решений. Иначе можно сказать, что эффективным решением называется такое решение x*, которое нельзя улучшить по какому-либо из критериев, не ухудшив при этом значения других критериев.

Множество эффективных решений называется множеством Парето и обозначается P(D). Очевидно, множество Парето является подмножеством множества допустимых решений, которое, в свою очередь принадлежит n-мерному векторному пространству, т. е. P(D) D En.

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

Смысл введенного понятия эффективного решения состоит в том, что оптимальное решение следует искать только среди элементов множества P(Д)

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

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

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

Рассмотрим введенные понятия на примере.

Решение xl называется слабоэффективным решением задачи (*), если для него не существует решения xll такого, что i=1,k f(xl) > f(xll), другими словами, слабоэффективное решение – решение, которое не может быть улучшено одновременно по всем критериям.

P(Д)En.

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

Читайте также:  Двухфазная сыворотка спрей для всех типов волос драгоценные масла эйвон способ применения

Схемы построения слабоэффективных и эффективных решений основываются, как правило, на ряде теорем.

F=,т. е.

D(2,0)- субоптимальное решение по f1,

f1()=f1max=6,

B(1,4), C(0,4) – субоптимальные решения по f2 (y=b+(1-)c)

f2(Д)= f2()=f2min=0

Зачастую целевые функции fi(x) имеют различную размерность и их необходимо свести к безразмерному виду с помощью какого-нибудь преобразования. Это преобразование должно удовлетворять по крайней мере следующим критериям:

1. иметь общее начало отсчета и один порядок изменения значений на всем множестве допустимых решений

2. быть монотонным преобразованием, т. к. должно сохранять отношение предпочтения на множестве Д, т. е. не менять множество Парето

3. учитывать необходимость минимизации отклонения от оптимальных значений по каждой целевой функции

Обыкновенно в качестве таких преобразований используют следующие:

причем , т. е. минимизируется разность между наилучшим решением и оптимальным.

Если , то

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

Недостаток принципа Парето в том, что он предлагает в качестве решения – множество решений, что не всегда приемлемо.

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

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

Но наименьшие значения величин или (x) , как правило, не достигаются одновременно ни для какого решения из Д (т. е. нельзя подобрать x, чтобы (x) max или min min .

Существует теорема: Если x0 – эффективное решение для данного вектора предпочтений , то ему соответствует наименьшее значение , при котором система равенств = выполняется для всех i=1,k.

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

Пример. 1-й критерий в 2 раза значимее по сравнению со 2-м

Т. о. — вектор предпочтений

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

Это подтверждается следующей теоремой:

Компромиссное решение может быть найдено как единственное решение системы неравенств вида для минимального значения параметра , при котором эта система совместна.

Метод, основанный на этом положении называется методом ограничений.

Этот метод можно рассматривать как метод решения минимаксной задачи:

Таким образом решается задача:

(**)

Если решение задачи (**) не единственное, то окончательное решение получится с помощью критерия

1(x)=0.6-0.3+0.1

2(x)=1-0.25

—

—

—

=

Источник