36212

Эффективные и слабо-эффективные решения. Поточечные методы поиска слабо-эффективных решений и оценок. Линейная свёртка, теорема Карлина. Логическая свёртка, теорема Гермейера. Геометрический смысл теорем Карлина и Гермейера

Доклад

Математика и математический анализ

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

Русский

2013-09-21

79.5 KB

57 чел.

10  Вопрос

Эффективные и слабо-эффективные решения. Поточечные методы поиска слабо-эффективных решений и оценок. Линейная свёртка, теорема Карлина. Логическая свёртка, теорема Гермейера. Геометрический смысл теорем Карлина и Гермейера.

Введем следующие обозначения:

Х – область допустимых решений (ОДР) задачи (1.1), Х Еn; (будем полагать его замкнутым и ограниченным);

Q – образ множества Х в пространстве критериев: Q = q(X), Q  Еm  – область достижимых оценок; (критериальные функции qi будем полагать непрерывными);

= {E m  j > 0;   j = 1} – незамкнутый симплекс в пространстве  E m;

= {E m  j  0;   j = 1} – замкнутый симплекс в пространстве  E m;

() – положительный (неотрицательный) ортант в пространстве Em; .

Par  – бинарное отношение Парето, определенное на Q:

и;

Sl  – бинарное отношение Слейтера определенное на Q:

;

P(Q),  S(Q) – множества элементов из Q, оптимальных по Парето и Слейтеру, соответственно (множества неулучшаемых оценок); P(Q) = { y  Q |  z  Q   (z, y) Par };

Pq(Х), Sq(Х) – множества элементов из Х, оптимальных по Парето и Слейтеру, соответственно, при критериях qi(x) (множества неулучшаемых решений);

Pq (Х) = { x X | t X   ( q(t), q(x) ) Par }.

Определение 2.2. Решения или оценки называются эффективными (слабо-эффективными), если они неулучшаемы по отношению Парето (Слейтера).

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

Теорема 2.5. (теорема Карлина). Пусть множество Q выпукло. Тогда для того, чтобы оценка у*  Q была слабо-эффективна необходимо и достаточно, чтобы существовал такой вектор параметров , что в точке у* достигался минимум свертки

;  у  Q.                                  (2.3)                   

Смысл теоремы – на рисунке. На рисунке: пространство критериев; прямые – линии равного уровня функции . Там, где касаются – там min на Q. Пунктир – P(Q). Если Q выпукло, то к любой точке P(Q) можно провести касательную, у которой все коэффициенты . Если Q не выпукло, то на P(Q) найдутся точки, в которых  ни при каком не достигает min.

Логические свертки. Выпуклость множеств Q или Х – очень сильное допущение, которое редко выполняется. Значительно менее жесткие требования предъявляет метод, основанный на логической (минимаксной) свертке Ю. Б. Гермейера:

.                               (2.5)

Теорема 2.7. (теорема Гермейера)  Пусть  (т.е. qi(х) > 0 хХ). Тогда для того, чтобы решение х* Х было слабо-эффективным по векторному критерию q, необходимо и достаточно, чтобы существовал вектор параметров , при котором х* была точкой минимума функции 2 (q(x), 0). 

Геометрический смысл теоремы Гермейера. В пространстве критериев Е2 линии равного уровня функций 2(y, ), 3(y, ) и 4(y, ) при фиксированном представляют собой вложенные “уголки”. Пусть, например, 1= 2/3, 2 =1/3. Построим линию равного уровня 2(y, ) = 1/3. Эта линия будет содержать, например, точку А = (0.5, 1), т.к. max {0.52/3; 11/3} = 1/3 = 2(A, ). Если теперь у1 < 0.5, а у2 = 1, то прежнему, 2(, ) = 1/ 3. Если же у2 < 1, а у1 = 0.5, то также 2(, ) = 1/3. Значит, линия уровня 2(, ) = 1/3 – “уголок” с горизонтальной стороной у2 = 1 и вертикальной у1 = 0.5. Точка А – вершина уголка, ее координаты зависят от значений коэффициентов i. Верно соотношение:     1 А1 = 2 А2 = 2(A, ). (На рисунке точка А отмечена кружком).

Там, где уголок касается области Q, находится точка min. Вследствие такой уникальной формы линий уровня, независимо от выпуклости области Q любая слабо-эффективная точка у* будет точкой минимума 2(у, ) при каком-нибудь , например при , и обратно – точка минимума 2(у, ) при любом будет слабо-эффективной.


 

А также другие работы, которые могут Вас заинтересовать

53073. Проектна робота «Ходить гарбуз по городу» 72.5 KB
  Мета проекту: вчити учнів працювати з науковопізнавальною літературою; розкрити користь гарбуза для людини його фармакологічні властивості та використання; розвивати творчі та інтелектуальні здібності; виховувати працьовитість взаємодопомогу почуття дружби необхідність ділитися досвідом новими ідеями знахідками. Посередині столу – великий гарбуз з намальованим обличчям. Гарбуз Що ти знаєш про нього Наше завдання – збагатити знання учнів про гарбуз його історію назву види лікувальні властивості страви з нього.
53075. Каждый несет ответственность перед всей планетой (по рассказу Ю. Нагибина «Мой первый друг, мой друг бесценный» 24 KB
  Нагибина Мой первый друг мой друг бесценный. Оборудование и материалы: текст рассказа; портрет писателя; тетради учеников; на отвороте доски закрыт от учеников написан отрывок из стихотворения:: Мой первый друг мой друг бесценный И я судьбу благословил Когда мой двор уединенный Печальным снегом занесенный Твой колокольчик огласил. Сегодня мы говорим о рассказе писателя Юрия Нагибина Мой первый друг мой друг бесценный.
53076. Основи здоров'я. Газобезпека 137 KB
  Перша вправа для покращення мозкового обігу, працюємо з нашими головами, але не забуваємо, що вага голови 5кг., тому оберігаємо шию, як зв.язуючий ланцюг.
53077. Рівняння стану ідеального газу 138.5 KB
  Повторення основних понять створення презентації за допомогою програми PowerPoint. Створення презентації за темою Рівняння стану ідеального газу. Два учні розв’язують домашні задачі біля дошки інші повторюють основні поняття створення презентації за допомогою програми PowerPoint вчитель читає початок речення а учні закінчують його. Закінчіть речення: Комп'ютерні презентації використовують для.
53078. Перлини народної мудрості Жива газета для учнів 5 - 9 класів 72 KB
  Допоможемо вам поринути у світ фольклору ми – працівники редакції: я – головний редактор координатори – ведучі сторінок голоси та ілюстрації. Голос 1: Природа. Голос 2: Наука. Голос 3: Вади вдачі та поведінки.
53079. Газообмін у легенях і тканинах 76 KB
  Основні поняття й терміни: зовнішнє диханнявнутрішнє диханнягазообміндифузіяпарціальний тискоксигемоглобінартеріальна кроввенозна кров. Знати як явище дифузії впливає на перетворення венозної крові в артеріальну і навпаки. Яким повітря повинне потрапляти до легень Яка система нашого організму тісно пов’язана з дихальною системою Яка кров називається артеріальною Яка кров називається венозною Де починається й закінчується М. оксигемаглобін Альвеоли...
53080. ТВОРЧІ ТА ПРОБЛЕМНІ ЗАВДАННЯ З ФІЗИЧНОЇ ГЕОГРАФІЇ 108 KB
  Учні вивчають матеріал а потім їм пропонується відповісти на запитання: Якими морями та океанами омивається Південна Америка Які форми рельєфу переважають в Південній Америці Чому Південну Америку вважають найвологішим материком. У чому полягає особливість клімату Південної Америки Як вплинула надмірна вологість клімату на особливості розташування природних зон на материку Для розв’язання проблеми учням пропонують відповіді які не завжди були правильними тому такі завдання допомагає виконувати вчитель. З яким океаном...
53081. Мы такие разные. Мы такие равные 194.25 KB
  Цель: более детально ознакомить учащихся с принципами гендерного равенства развивать навыки исследовательской работы воспитывать уважение к представителям обоих полов стремление к взаимопониманию и равенству соблюдению прав человека неприятия насилия формировать коммуникативные и социокультурные компетентности Оборудование: мультимедийная презентация музыка плакаты Ход занятия 1 слайд Как силы нет без слабости юга без севера дня без ночи так и женщины не могут быть без мужчин а мужчины без женщин. Мы все...