Графический метод проверки эффективности точки задач векторной оптимизации

Баева Н. Б.

Теория и практика векторной оптимизации: учебное пособие / Н. Б. Баева, Ю. В. Бондаренко, Т. В. Азарнова, И. Л. Каширина; Воронежский государственный университет. – Воронеж: Издательский дом ВГУ, 2017. – с.

 ISBN 978-5-9273-2435        

 

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

Для студентов, обучающихся по направлениям «Прикладная математика и информатика», «Бизнес-информатика».

УДК 519.81 (075)

ББК 22.18

 

 

© Баева Н. Б., Бондаренко Ю. В.,
 Азарнова Т. В., Каширина  И. Л., 2017

© Воронежский государственный     университет, 2017

ISBN 978-5-9273-   2435-4                     © Оформление. Издательский дом ВГУ, 2017

СОДЕРЖАНИЕ

1. Постановка задачи векторной оптимизации. Принципы оптимальности	4
2.  Графический метод проверки эффективности точки задач векторной оптимизации	11
3. Классификация методов решения ЗВО	16
4.  Методы решения ЗВМ, основанные на свертывании (скаляризации) критериев	17
5. Принцип максимальной эффективности и принцип гарантированного результата	32
5.1. Принцип максимальной эффективности и принцип гарантированного результата в случае равнозначных критериев	33
5.2. Принцип максимальной эффективности и принцип гарантированного результата при заданном приоритете критериев	42
6. Методы решения ЗВМ, основанные на лексикографическом принципе оптимальности	48
7. Методы, использующие ограничения на критерии	52
7.1. Метод ограничений	52
7.2. Метод последовательных уступок	53
8. Целевое программирование	64
9. Методы решения ЗВМ произвольной структуры	74
9.1. Дискретизация множеств	75
9.2. Фильтрация множеств	76
Библиографический список	84

§ 1. ПОСТАНОВКА ЗАДАЧИ ВЕКТОРНОЙ ОПТИМИЗАЦИИ. ПРИНЦИПЫ ОПТИМАЛЬНОСТИ

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

                                                                                                (1)

и называется задачей векторной оптимизации (ЗВО), а каждая из функций  – частным критерием.

Если в исходной задаче критерии однонаправлены, т.е. все критерии, например, стремятся к максимуму (или к минимуму), то задача называется однородной. В противном случае исходная задача – неоднородная задача оптимизации.

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

Если  и  линейны, то задача (1) называется задачей линейной векторной оптимизации. Теория решения таких задач разработана наиболее полно.

С учетом того, что каждая оптимизированная задача может быть переписана в эквивалентной постановке как задача максимизации критериев, будем для удобства рассматривать задачу векторной максимизации (ЗВМ), записывая её в следующем виде:

                                          .                                                   (2)

Введем в рассмотрение ряд определений, связанных с понятием решения ЗВО.

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

Другими словами, идеальное решение задачи (2) является одновременно решением всех M частных задач:

                                                                                                  (3)

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

–

множество решений исходной задачи.

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

 

1. Принцип Слейтера

Определение 2. Точка  называется оптимальной по Слейтеру в задаче векторной максимизации, если не существует другой точки  для которой

Множество оптимальных по Слейтеру точек Sl  называют множеством слабо эффективных точек.

Другими словами, если ввести множество

то

.

Замечание 1. Любое решение каждой частной задачи (3) является точкой, оптимальной по Слейтеру.

 

2. Принцип Парето

Определение 3. Точка  называется оптимальной по Парето (Парето-оптимальной) в задаче векторной максимизации, если не существует другой точки  для которой  и существует такой индекс , что  

Множество Парето-оптимальных точек Pr называют множеством эффективных точек.

Другими словами, если ввести множество

 то

.

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

С понятием решения ЗВО связано понятие доминирования.

 

Доминирование.  Недоминируемые критериальные векторы

 

Рассмотрим задачу векторной максимизации (2).

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

 Множество  называется достижимым множеством.

Таким образом, каждой задаче векторной максимизации (2) может быть поставлена в соответствие задача:

                                                                                                   (4)

Для установления аналогий между решениями задач (2) и (4) введем в рассмотрение следующие определения.

Пусть   –  критериальные векторы.

Определение 4. Вектор   слабо доминирует вектор , если  (т. е.   и  по крайней мере, для одного k).

Определение 5. Вектор   сильно доминирует вектор , если , т. е.

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

Иначе  называется доминируемым.

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

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

Замечание 3. Соотношения  понимаются выполняемыми покоординатно.

Рассмотрим следующие примеры.

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

Решение. Допустимое множество задачи представлено на рисунке 1.

Вершинами многогранника   являются следующие точки:

 

Каждая точка X множества  является выпуклой линейной комбинацией вершин т.е.

 где

 

Рассмотрим отображение  определяемое правилом:

где  

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

Найдем координаты точки т.е.   

Аналогично:  

Достижимое множество в пространстве критериев Q изображено на рисунке 2.

Пример 2.  Вектор  сильно доминирует вектор  и слабо доминирует вектор

 

Пример 3. Рассмотрим задачу:

Найти множество оптимальных по Парето и по Слейтеру точек.

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

Точка  является оптимальной по Парето, так как в допустимом множестве не существует точек X таких, что

 причем одно из неравенств – строгое. (ABC) – множество оптимальных по Слейтору точек.

Упражнения

№ 1. Представьте графически достижимую область в пространстве критериев  для задач:

1)

 

2)

 

3)

№ 2. Для каждого из перечисленных векторов определите слабо и сильно доминирующие векторы:

 

№ 3. Определите, какие точки из таблицы эффективны.

Точки
	4	-2	3	7	-5
	9	3	-5	0	4
	0	0	0	2	-1
	-6	3	4	5	1
	4	1	3	9	0
	-2	-4	-1	-3	-2

 

Упражнения

 

№ 1. Графическим методом определите, какие из точек:

эффективны в задаче

 

№ 2. Графическим методом определите, какие из точек:

эффективны в задаче

 

№ 3. Найти эффективное множество каждой из задач:

1)

 

2)

 

3)

 

4)

 

5)

 

6)

 

7)

 

8)

 

Упражнения

 

№ 1. Для задач векторной максимизации с заданной функцией полезности ЛПР найти решение в пространстве решений и критериальном пространстве:

1)

.

 

2)

.

 

3)

.

 

№ 2. Решить методом взвешенных сумм

1)

, ,

 

2)

, ,

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

1)

а) отрезок [A,B]; b) точка B; c) точка C; d) отрезок [B,C], где A=(0,0), В=(0,3), С=(3,3).

 

2)

а) отрезок [A,B]; b) точка B; c) точка C; d) отрезок [B,C], где A=(3,0), В=(), С=().

 

№ 4. Определить графически все подмножества , соответствующие каждой эффективной грани в следующих задачах:

1)

 

2)

 

№ 5. Пусть модель автомобиля оценивается по 2 характеристикам: надежность (), максимальная скорость передвижения (). Причем автомобиль может быть сконструирован с любой комбинацией данных характеристик, удовлетворяющих системе ограничений:

Критерии выбора , .

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

 

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

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

a)  математике; b) английскому; c) ни по математике, ни по английскому; d) по обоим предметам.

 

5. ПРИНЦИП МАКСИМАЛЬНОЙ ЭФФЕКТИВНОСТИ
В ПРИНЦИП ГАРАНТИРОВАННОГО РЕЗУЛЬТАТА

Упражнения

№1. Построить и решить -задачу для следующих ЗВМ:

1)

 

2)

 

3)

4)

По найденным значениям  произвести сравнительный анализ степени противоречивости целевых функций задач 1) – 4).

 

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

 

№3. Для задачи

1) Выписать задачи с нормализованными критериями, в которых в качестве нормализованных критериев выбраны относительные оценки  и относительные отклонения ;

2) Построить - и -задачи, сформулировав принцип гарантированного результата для каждого из случаев.

 

№4. Построить  для следующих ЗВМ:

1)

 

2)

 

3)

 

№4. Решить ЗВМ принципом гарантированного результата:

1)

 

2)

 

3)

 

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

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

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

 

Алгоритм 1. Алгоритм решения ЗВМ методом ограничений:

Шаг 0. Рассматривается задача векторной максимизации (2);  частные критерии задачи .

Шаг 1. ЛПР предлагается назначить нижние допустимые границы  для всех критериальных функций:

                                  .                               (21)

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

Шаг 2. Строится подмножество множества Парето, состоящее из точек, удовлетворяющих неравенствам (21):

Шаг 3. Если  - пустое множество, то ЛПР предлагается ослабить требование с помощью уменьшения какого-то из чисел , переход к шагу 2. Иначе – останов,  - множество решений ЗВМ.

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

1)

где  – обобщенный критерий;

2)

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

 

Упражнения

№ 1. Решить задачу векторной оптимизации методом последовательных уступок:

1)

если  и

 

2)

если  и

 

№ 2. Пользуясь результатами теоремы 3, для эффективной точки  найти такие величины уступок , что  является решением ЗВМ методом последовательных уступок:

1)

если  = (1/2; 1/2);

 

2)

если  = (1/3; 2/3);

 

3)

если  = (2; 1);

 

4)

если  = (3, 5; 0, 5);

 

5)

если  = (2; 3);

 

6)

если  = (2; 2).

 8. ЦЕЛЕВОЕ ПРОГРАММИРОВАНИЕ

Рассмотрим допустимое множество  – критерии оценки векторов множества . Будем предполагать, что в критериальном пространстве  задано непустое, выпуклое множество  такое, что любые векторы  из множества

,

где , являются “хорошими” для лица, принимающего решения.

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

1)

2)

3)

4)

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

Метод идеальной точки

Рассмотрим ЗВМ (2) и точку  где  – оптимальное значение функции цели в k -й частной задаче:

                                           

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

                                                                                      (28)

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

1) ;

2)  где

В силу свойств функции расстояния, получаемые в ходе решения задачи (28) точки являются Парето-оптимальными.

Метод сведения к архимедовой задаче

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

1) (X) ≥ ,  ;

2) (X) = ,

3)  ≤ (X) ≤ , .

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

 

Ω_A                                  (29)

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

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