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

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

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

В теории многокритериальной оптимизации (МКО) решаются задачи принятия решений одновременно по нескольким критериям. Задача МКО ставится следующим образом: требуется найти числа , удовлетворяющие системе ограничений

, , (3.1)

для которых функции

, , (3.2)

достигают максимального значения.

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

,–целевыми функциями, или критериями, заданными на множестве D. В формулировке задаче (3.1)-(3.2) присутствует

целевых функций. Эти функции отображают множество

в множество

, которое называетсямножеством достижимости.

В векторной форме математическую модель МКО (3.1)-(3.2) можно записать следующим образом:

при . (3.3)

Здесь – вектор-функция аргумента.

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

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

Ввиду этого в теории МКО понятие оптимальности получает различные толкования, и поэтому сама теория содержит три основных направления:

1. Разработка концепции оптимальности.

2. Доказательство существования решения, оптимального в соответствующем смысле.

3. Разработка методов нахождения оптимального решения.

3.2. Оптимальность по Парето

Если функции достигают максимум в одной и той же точке, то говорят, что задача (3.3) имеетидеальное решение.

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

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

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

предпочтительнее решения

. Условие предпочтительности принято обозначать в виде

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

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

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

. В этой области ни один критерий не может быть улучшен без ухудшения хотя бы одного из других. Важным свойством множества Парето

является возможность «выбраковывать» из множества альтернатив

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

. При отсутствии дополнительной информации о системе предпочтений ЛПР должно принимать решение именно из множества Парето

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

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

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

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

studfiles.net

Лекция №7(Многокрит_оптимизация)

Лекция 5.

многокритериальная оптимизация.

Эффективность функционирования экономической системы оценивается, как правило, несколькими критериями. Математической формой критерия эффективности в оптимизационных экономико-математических задачах является целевая функция.

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

(1)

; (2)

. (3)

К задачам многокритериальной оптимизации приходят в следующих случаях:

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

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

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

Наиболее распространенными способами стандартизации показателей являются:

1) 2)3)4),

где

—среднеарифметическое значение i-го признака;

—некоторое эталонное значение i -го признака;

—максимальное значение i -го признака по всем j-м объектам;

—центрированное значение признака;

—минимальное значение i -го признака по всем j-м объектам.

Достаточно часто используется схема, где соответствующее преобразование производится в соответствии с формулой:

5) , где— среднеквадратическое отклонение по всем объектам,

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

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

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

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

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

Идею поиска оптимального компромиссного плана рассмотрим на простейшем примере оптимизации двумерного критерия

каждая составляющая которого, представляет функцию от одной переменной x, определенной на некотором закрытом интервале х [a,b]. Графики изменения составляющих и представлены на рис.1.

Рис.1. Иллюстрация определения компромиссного плана.

Очевидно, что поиск оптимального компромиссного плана в данном конкретном примере целесообразен лишь на множестве точек интервала [c,d], так как вне этого интервала решение может быть улучшено сразу по обеим целевым функциям. План X1, будем считать лучше (предпочтительнее) плана X2 и обозначать если хотя бы по одной компоненте целевой вектор – функции >, а по остальным компонентам .Этотак называемое улучшение по Парето, формулируемое очень просто: «Следует считать, что любое изменение, которое никому не причиняет убытков и которое приносит кому-то пользу (по их собственным оценкам), является улучшением».

Интервал [с,d] носит название множества Парето, или множества эффективных планов, и характеризуется теми важными свойствами, что на нем ни одно решение не может быть улучшено ни по одному из критериев без ущерба для других критериев.

План оптимален по Парето, если он допустим, и не существует другого планадля которого

и хотя бы для одного критерия выполняется строгое неравенство.

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

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

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

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

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

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

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

1. Метод свертывания критериев.

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

;

Критерии в свертке должны быть нормированы.

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

В [3] приведен сравнительный анализ методов определения коэффициентов важности критериев, в котором отмечено, что наиболее простой прием для определения весов в аддитивной свертке предложил Х. Юттлер, где в качестве весовых коэффициентов используются величины, обратные оптимальным значениям по частным критериям:

где - оптимальное максимальное значение критерия .

2. Метод последовательных уступок.

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

1. Критерии нумеруются в порядке убывания важности.

2. Решается задача

;

Определяется значение .

3. Устанавливается уступка , по этому критерию.

4. Решается задача

;

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

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

Метод последовательных уступок, являясь простым и понятным в реализации, обладает, тем не менее, целым рядом недостатков, основными из которых являются:

1. Сложность и субъективизм в ранжировании критериев.

2. Субъективизм в задании величин уступок.

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

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

Пример. Решить задачу методом последовательных уступок, если уступка по первому критерию составляет 10% от его оптимального значения.

Решение.

Решим задачу по критерию . Получим. В соответствии с условием задачи величина уступки. Дополнительное ограничение будет иметь вид, то есть. Решая задачу

получим ,,

Задача 1.

Предприятие может выпускать пять видов продукции И1, И2, ИЗ, И4, И5. Для этого используется три вида ресурсов, расход которых на производство единицы продукции и их запасы приведены в таблице:

Ресурс	И1	И2	ИЗ	И4	И5	Запасы
В1	4	5	3	2	3	3000
В2	2	4	4	4	2	4500
В3	3	1	0	1	1	1500

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

Вид станков	И1	И2	И3	И4	И5	Фонд времени (ст./час)
Станок 1	2	3	5	4	5	5000
Станок 2	1	2	6	3	2	4000
Станок 3	3	4	4	1	4	4000
Станок 4	1	1	2	2	1	2000

Оптовая цена и себестоимость единицы продукции соответствующего типа приведены в таблице:

	И1	И2	И3	И4	И5
Оптовая цена (ден.ед.)	10	9	12	14	9
Себестоимость(ден.ед.)	7	8	9	12	6

Объем каждого вида продукции должен быть не менее 100 и не более 500 единиц. Мерой эффективности производственной программы являются следующие показатели:

1. Прибыль предприятия – f1;

2. Валовый объем выпуска продукции в стоимостном выражении – f2;

3. Себестоимость продукции – f3;

4. Уровень загрузки оборудования – f4.

Требуется.

1. Решить задачу методом последовательных уступок, если уступку по каждому критерию полагать равной 10% от его оптимального значения.

2. Решить задачу методом свертывания критериев, выбрав вектор весовых коэффициентов методом парных сравнений.

Решение.

1. Составим ЭММ задачи.

Обозначим через – количество продукции И1, – количество продукции И2, – количество продукции И3, – количество продукции И4, – количество продукции И5.

Целевые функции будут иметь вид:

Прибыль: .

Валовый объем ( в стоимостном выражении):

Себестоимость: .

Уровень загрузки оборудования:

Ограничениями задачи будут:

1). По расходу ресурсов:

–В1

–В2

–В3

2). По фонду времени работы оборудования:

3). По объему выпускаемой продукции: .

4). Условие целочисленности переменных: .

Пронормируйте критерии.

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

1. Ларичев О.И. Теория и методы принятия решений, а также хроника событий в Волшебных Странах: Учебник. – М.:Логос, 2000. – 296 с.

2. Подиновский В.В. Введение в теорию важности критериев в многокритериальных задачах принятия решений. — М.: ФИЗМАТЛИТ, 2007. - 64 с.

3. А. М. Анохин и др., Методы определения коэффициентов важности критериев, Автоматика и телемеханика, N° 8, 1997

studfiles.net

Методы решения многокритериальных задач — МегаЛекции

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

Метод аддитивной оптимизации.Пусть

. (18.12)

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

. (18.13)

Обобщенная функция цели (18.12) может быть использована для свертывания векторного критерия оптимальности , если о его компонентах известна следующая информация:

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

частные критерии являются однородными (имеют одинаковую размерность – доходы, расходы).

В этом случае для решения задачи векторной оптимизации (18.1) – (18.3) оказывается справедливым применение аддитивного критерия оптимальности (18.12). Подтверждением этого может служить лемма Карлина (1959 год), которая гласит, что, если для некоторых

, (18.14)

где вектор оптимален по Парето.

Действительно, если не оптимальное решение по Парето, то тогда существует такой , что

, (18.15)

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

, (18.16)

что противоречит (18.14) и доказывает справедливость утверждения леммы.

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

Требование нормализации критериев возникает в тех задачах, в которых локальные критерии имеют различные единицы измерения. К настоящему времени разработано большое количество схем нормализации. Рассмотрим некоторые из них.

Определим максимум и минимум каждого критерия , т.е.

;

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

Тогда в соответствии с принципом максимальной эффективности нормализованные критерии определяются из соотношений:

или

и обобщенная функция цели имеет вид .

В соответствии с принципом минимальной потери нормализованные критерии определяются из соотношений:

(18.17)

или

(18.18)

и обобщенная функция цели имеет вид . Однако в общем виде нормализованные критерии могут быть произвольными кривыми, изменяющимися от 0 до 1.

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

где - экспертная оценка относительной важности j - го частного критерия оптимальности, предложенная s - м экспертом.

Для назначения оптимально-компромиссных весовых коэффициентов , выражающих «коллективное мнение», необходимо задать схему компромисса и решить экстремальную задачу:

(18.19)

где .

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

Если мерой близости служит функция

(18.20)

то оптимальным решением задачи (18.19) является вектор средних значений по элементам столбцов матрицы :

(18.21)

Действительно, построим функцию Лагранжа:

Значения и должны удовлетворять системе уравнений:

(18.22)

(18.23)

Из выражения (18.22) находим

(18.24)

Подставляя полученные значения из (18.24) в выражение (18.23), получаем , откуда согласно выражению (18.24) следует справедливость формулы (18.21).

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

(18.25)

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

а) на основе информации, полученной от ЛПР о коэффициентах , формулируется задача оптимизации

, (18.26)

которая решается на ЭВМ. Из решения задачи (18.26) находится оптимальная по Парето точка , соответствующая данным весам , и скорость изменения функции в точке по различным направлениям, т.е. градиент ;

б) на основании полученной информации ЛПР оценивает решение , т.е. определяет, следует ли использовать это решение в качестве окончательного или, если решение неудовлетворительно, на основе значений градиентов и опыта работы с объектом корректирует веса , после этого задача (18.26) решается заново:

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

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

Метод многоцелевой оптимизации. Основная идея многоцелевого подхода, выдвинутая еще в начале шестидесятых годов, состоит в назначении в пространстве критериев некоторой цели . Это позволяет свести многокритериальную задачу к задаче оптимизации (18.27):

(18.27)

где есть некоторое расстояние между точками и

В частности,

(18.28)

или

Задача (18.27) представляет собой задачу целевого программирования и решается методами линейного программирования.

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

где - произвольно выбранный опорный критерий.

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

. (18.29)

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

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

Этап 2. Определяются подходящая начальная точка и вычисляется .

Этап 3. Определяется путем опроса ЛПР и использования формулы (18.29).

Этап 4. Решается задача математического программирования следующего вида:

(18.30)

(18.31)

(18.32)

Здесь yj определяет расхождение между критерием и целью . В результате решения задачи (18.30) – (18.32) определяется , и наилучшее направление решения многоцелевой задачи .

Этап 5. Путем опроса ЛПР определяется величина шага , которая минимизирует обобщенную функцию цели .

Этап 6. Если , то решение заканчивается, в противном случае определяется новое промежуточное решение и далее цикл решения повторяется с этапа 3.

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

Метод выделения главного критерия. Допустим, что среди критериев удается выделить один – главный, скажем , и установить разумные ограничения по другим целям, которым должно удовлетворять оптимальное решение. Обозначим эти минимальные значения по критериям через . Такая информация позволяет векторную задачу оптимизации свести к скалярной задаче:

(18.33)

(18.34)

(18.35)

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

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

Выбор компромиссного решения на основе решения п задач оптимизации может быть формализован. Пусть - вектор оптимальных значений целевых функций, - вектор отклонений от ; - максимально допустимые отклонения от . Можно сформулировать такие задачи скалярной оптимизации:

а) максимизация одной целевой функции при максимально допустимых отклонениях от оптимальных значений других целевых функций:

(18.36)

(18.37)

(18.38)

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

(18.39)

(18.40)

где - монотонно возрастающая функция.

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

Метод последовательных уступок. Пусть для определенности все критерии упорядочены по предпочтительности, т.е. . Сначала решается задача

(18.41)

(18.42)

Анализируется оптимальное решение и и далее устанавливается некоторая уступка по критерию , на которую ЛПР согласно для того, чтобы улучшить решение по другим критериям. Это приводит к следующей задаче:

(18.43)

(18.44)

(18.45)

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

(18.46)

(18.47)

(18.48)

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

Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:

megalektsii.ru

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

Пусть, как и прежде, необходимо выбрать одно из множества решений X из области xих допустимых значений. Но, в отличие от рассмотренного ранее, каждое выбранное решение оценивается совокупностью критериев f1,f2,…,fk, которые могут различаться своими коэффициентами относительной важности (1…k). Критерии fq, q=1..k, называют частными или локальными критериями, они образуют интегральный или векторный критерий оптимальности F={fq}. Коэффициенты образуют вектор важности . Каждый локальный критерий характеризует некоторую локальную цель принимаемого решения.

Оптимальное решение X должно удовлетворять соотношению:

где: F – оптимальное решение интегрального критерия;

opt – оператор оптимизации, он определяет выбранный принцип оптимизации.

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

–область согласия, в которой качество решения может быть улучшено одновременно по всем локальным критериям или без снижения уровня любого из критериев;

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

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

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

Рассмотрим основные схемы компромисса, предполагая вначале, что все локальные критерии нормализованы (то есть имеют одинаковую размерность или являются безразмерными величинами) и одинаково важны. Рассмотрение удобно вести, перейдя от пространства xвыбираемых решений X к пространству kвозможных (допустимых) локальных критериев F={f1,f2,…,fk}, деля его на область согласия и область компромиссов.

Тогда сформулированную ранее модель оптимизации можно переписать в виде:

Основными схемами компромисса являются:

- принцип равномерности;

- принцип справедливой уступки;

- принцип выделения одного оптимизируемого критерия;

- принцип последовательной уступки.

Принцип равномерности провозглашает целесообразность выбора такого варианта решения, при котором достигалась бы некоторая “равномерность” показателей по всем локальным критериям. Используют следующие реализации принципа равномерности:

- принцип равенства;

- принцип максимина;

- принцип квазиравенства.

Принцип равенства формально выражается следующим образом:

то есть оптимальным считается вариант, принадлежащий области компромиссов, при котором все значения локальных критериев равны между собой. Однако случай f1=f2=…=fkможет не попасть в область компромиссов или вообще не принадлежать к области допустимых вариантов.

Принцип максимина формально выражается следующим образом:

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

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

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

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

Принцип абсолютной уступки может быть формально выражен с помощью следующей записи:

, где

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

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

,-абсолютное значение приращения критериев;

-символ “такой, для которого”.

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

Можно показать, что принципу абсолютной уступки соответствует модель максимизации суммы критериев:

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

Принцип относительной уступки может быть записан в виде:

, где

-относительные изменения критериев;

- максимальные значения критериев.

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

Можно сказать, что принципу относительной уступки соответствует модель максимизации произведения критериев

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

Принцип выделения одного оптимизируемого критерия формально может быть записан следующим образом:

,где

fi-оптимизируемый критерий при условиях:

;

fqdop. - допустимое значение критерия.

Один из критериев является оптимизируемым и выбирают тот вариант, при котором достигается максимум этого критерия. На другие критерии накладываются ограничения.

Принцип последовательной уступки. Предположим, что локальные критерии расположены в порядке убывающей важности: сначала основной критерий f1, затем другие, вспомогательные критерии f2,f3,… Как и ранее, считаем, что каждый их них нужно обратить в максимум. Процедура построения компромиссного решения сводится к следующему. Сначала находят решение, обращающее в максимум главный критерий f1. Затем, исходя из практических соображений, например, из точности, с которой известны исходные данные, назначают некоторую “уступку” f1, допустимую для того,чтобы обратить в максимум второй критерий f2. Налагаем на критерий f2 требование, чтобы он был меньше, чемf1max-f1, где f1max– максимально возможное значение f1, и при этом ограничении ищем вариант, обращающий в максимум f2. Далее снова назначают “уступку” в критерии f2, ценой которой можно максимизировать f3 и т. д.

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

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

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

либо

,где

fq,-локальные критерии, которые необходимо максимизировать;

fq,-локальные критерии, которые необходимо минимизировать.

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

studfiles.net

Многокритериальная оптимизация - Задача

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

Агафья Тихоновна: “Если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколько-нибудь развязности, какая у Балтазара Балтазарыча, да, пожалуй, прибавить к этому еще дородности Ивана Павловича — я бы тогда тотчас же решилась.”

Н.В. Гоголь. «Женитьба». 1833

Пример

Покупка автомобиля

	VW Golf	Opel Astra	Ford Focus	Toyota Corolla
Цена (1000 Euro)	16.2	14.9	14.0	15.2
Расход топлива (на 100 км)	7.2	7.0	7.5	8.2
Мощность (kW)	66.0	62.0	55	71

Какой автомобиль выбрать, чтобы он был мощным, недорогим, с малым расходом топлива?

Пример

минимизация пары функций

минимум в точке

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

при условии .

Допустимое решение называется эффективным по Парето или Парето-оптимальным, если не существует другого решения такого, что для всех k = 1,…, p, и хотя бы для одного i = 1,…, p.

Если — эффективное решение, то называется недоминируемой точкой. Множество всех недоминируемых точек называется недоминируемым множеством и обозначается YN. Множество всех эффективных решений называется эффективным множеством и обозначается XE.

Пространство решений и пространство критериев

Пример Opel и Ford эффективный выбор или Парето*-оптимальные решения

*Вильфредо Парето, 1848-1923 итальянский экономист

Пространство решений и пространство критериев

Пример минимизации двух функций

допустимое множество

допустимое множество в пространстве критериев состоит из части графика, расположенной справа от вертикальной линии

недоминируемые точки: , , соответствующие решениям

Линейная свертка критериев

Вместо исходной многокритериальной задачи

будем решать задачу с одним взвешенным критерием

при разных значениях и .

Графическая интерпретация

При заданных  ищем элементы множества



< ,y > = c

Всегда ли такой процесс дает недоминируемые точки?
Если да, то все ли точки можно получить, меняя  ?

Эффективность по Джеоффриону

Допустимое решение называется эффективным по Джеоффриону, если является эффективным и существует такое положительное число M, что для любого xX, удовлетворяющего условию

для некоторого i,

найдется такой индекс j, что и выполнено неравенство

Точка называется недоминируемой поДжеоффриону.

Пример.

Y = X

— недоминируемая точка

x = (0, 1) не является эффективным по Джеоффриону.

Теорема. Пусть положительные величины k, k = 1,…, p удовлетворяют равенству Если — оптимальное решение линейной свертки, то — эффективное решение по Джеоффриону.

Доказательство. Покажем, что — эффективное решение. Пусть xX, и существует индекс iтакой, что . Т.к. k > 0, то

что противоречит оптимальности в линейной свертке.

Покажем эффективность по Джеоффриону. Положим .

Предположим, существует xX и такой индекс i p, что и для всех индексов j, где .

Тогда по выбору M получаем

Заметим, что неравенство верно для всех j  i, т.к. при оно тривиально. Умножим это неравенство на и сложим по всемj  i:

Тогда ,

группируем .

Получаем , что противоречит оптимальности . ■

Верно ли обратное утверждение?

— недоминируемая точка

Лемма (о свойствах выпуклых функций). Пусть X  Rn— выпуклое множество и все функцииhk:RnR выпуклые k = 1,…, p. Если система hk (x) < 0, k = 1,…, p, не имеет решений xиз множества X, то существуют такие неорицательные величины k, в сумме равные 1, , что

для всех xX.

Без доказательства.

Теорема. Пусть X  Rn— выпуклая область и все функции fk :Rn Rвыпуклые, k = 1,…, p. Тогда является эффективным решением по Джеоффриону, если и только если — оптимальное решение линейной свертки с положительными весами k,k = 1,…, p.

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

Пусть — эффективное решение по Джеоффриону. Из определения следует, что существует M> 0, для которого при любом i = 1,…, pсистема

не имеет решений.

Тогда по лемме о выпуклых функциях для i-й системы найдутся величины , k = 1,…, p в сумме равные 1, т.е. при которых для любого xX верно неравенство:

Открываем скобки:

Заносим в сумму первое слагаемое в обеих частях неравенства:

Пользуясь равенством получаем:

Итак, для каждого i = 1,…, p получили неравенство. Складывая их по i,получаем:

Отсюда следует, что верно для всех xX. Поделив обе части на, получаем нормированный вектор > 0, указанный в теореме, при котором — оптимальное решение в линейной свертке. ■

Пример. f1(x) = x1, f2(x) = x2

— решения, эффективные по Парето.

При любых  0 линейная свертка дает только !

Метод уступок

Для   Rp рассмотрим задачу с одним критерием

при условии

()

Теорема. Допустимое решение является эффективным по Парето     Rp, при котором — оптимальное решение () для всех j = 1,…, p.

Доказательство.  Положим и предположим, что не является оптимальным решением для некоторого j. Тогда найдется , для которого и , kj, т.е. не является эффективным по Парето.

 Предположим, что Тогда  jи решение , для которых и , kj. Поэтому не может быть оптимальным решением ни при каком , если — допустимое решение для этого .

Пример

Устные вопросы до экзамена

4 курс, ММФ НГУ, зимняя сессия, 2011 г.

Приближенные алгоритмы с гарантированной относительной точностью. Модифицированный жадный алгоритм для задачи о рюкзаке и алгоритм с точностью ¾.
Аппроксимационные схемы, полиномиальные и полностью полиномиальные схемы для задачи о рюкзаке.
Задача упаковки в контейнеры. Алгоритмы NF, FF, BF, FFD, отрицательный результат об аппроксимируемости.
Нижние оценки Martello и Toth.
Метод генерации столбцов для задачи упаковки в контейнеры.
Задача календарного планирования. Критические работы, пути и критическое время проекта.
Задачи календарного планирования с ограниченными ресурсами.
Алгоритм Гимади для задачи со складируемыми ресурсами.
Задача коммивояжера. Теорема о погрешности приближенных полиномиальных алгоритмов и алгоритмов локального спуска.
Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2.
Нижние оценки в задаче коммивояжера
Алгоритм Лаулера для задачи 1| prec| fmax
Алгоритм решения задачи P | pmtn |Cmax
Алгоритм решения задачи P | pmtn, ri |Lmax
Алгоритм решения задачи F2 || Cmax
Задачи о покрытии, алгоритм Чватала
Задача размещения в условиях конкуренциии «безнадежный» пример.
Матричные игры. Определение седловой точки.
Теорема Фон-Неймана.
Бескоалиционные игры, равновесие по Нэшу.
Многокритериальная оптимизация. Эффективные решения по Парето и Джеоффриону. Метод уступок.

Вопросы к экзамену

4 курс, ММФ НГУ, зимняя сессия, 2011 г.

Метод динамического программирования на примере распределительной задачи.
Модель размещения капитала, верхняя оценка оптимума, свойство оптимального решения линейной релаксации, алгоритм округления дробного решения.
Классическая задача о рюкзаке, теорема об алгоритмах с гарантированной абсолютной точностью.
Жадные алгоритмы для классической задачи о рюкзаке, свойства LP-релаксации
Приближенные алгоритмы с гарантированной относительной точностью. Модифицированный жадный алгоритм для задачи о рюкзаке и алгоритм с точностью ¾.
Аппроксимационные схемы, полиномиальные и полностью полиномиальные схемы для задачи о рюкзаке.
Замена оборудования. Алгоритм динамического программирования для конечного планового периода.
Задача упаковки в контейнеры. Алгоритмы NF, FF, BF, FFD и их свойства, отрицательный результат об аппроксимируемости.
Нижние оценки Martello и Toth.
Метод генерации столбцов для задачи упаковки в контейнеры.
Задача двумерной упаковки, кодировки решений, алгоритм имитации отжига.
Задача календарного планирования. Критические работы, пути и критическое время проекта.
Постановка задачи календарного планирования с ограниченными ресурсами.
Т–поздние расписания. Алгоритм вычисления Т–поздних расписаний.
Доказательство оптимальности Т*–позднего расписания. Алгоритм Гимади.
Задачи календарного планирования с переменными длительностями работ. Сведение к линейному программированию.
Задача коммивояжера. Теорема о погрешности приближенных полиномиальных алгоритмов и алгоритмов локального спуска.
Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2. Доказательство оценки и ее неулучшаемости.
Нижние оценки в задаче коммивояжера: примитивная оценка, оценка линейного программирования, оценка задачи о назначениях и минимальные 1-деревья.
Алгоритм решения задачи о назначениях.
Метод ветвей и границ для задачи коммивояжера.
Классификация задач теории расписаний.
Алгоритм Лаулера для задачи 1| prec| fmax
Алгоритм решения задачи 1| prec, pmtn, ri | fmax
Алгоритм решения задачи P | pmtn |Cmax
Алгоритм решения задачи P | pmtn, ri |Lmax
Алгоритм решения задачи Q | pmtn |Cmax
Алгоритм решения задачи F2 || Cmax
Задачи о покрытии, алгоритм Чватала, оценка его погрешности и экстремальный пример.
Задачи размещения. Генетический алгоритм для задачи размещения производства.
Задача размещения в условиях конкуренции, математическая модель, «безнадежный» пример, точный метод.
Матричные игры. Определение седловой точки.
Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема Фон-Неймана. Дилемма заключенных.
Бескоалиционные игры, равновесие по Нэшу, пример игры без равновесий.
Многокритериальная оптимизация. Эффективные решения по Парето и Джеоффриону. Линейные свертки и их свойства. Метод уступок.

-26-

Лекция 15. Многокритериальная оптимизация

textarchive.ru