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

↑

▷ Содержание

Стр 1 из 7Следующая ⇒

Баева Н. Б.

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

 ISBN 978-5-9273-2435        

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

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

УДК 519.81 (075)

ББК 22.18

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

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

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

СОДЕРЖАНИЕ

§ 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) являются нежесткими в том смысле, что они не ограничивают допустимую область Ω в пространстве решений. В действительности они пополняют область допустимых решен

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США