36212

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

Доклад

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

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

Русский

2013-09-21

79.5 KB

59 чел.

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(у, ) при любом будет слабо-эффективной.


 

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

76016. Що за диво ці казки! The Magic World of Fairy Tales 966.5 KB
  Мета: узагальнити та систематизувати знання учнів за темою «Казка»; розвивати уміння застосовувати набуті знання сприяти морально-етичному вихованню школярів, виховувати інтерес до вивчення літератури.
76019. Как планете остаться голубой. Вода – источник жизни на Земле 148 KB
  Цели урока: познакомить учащихся с проблемой загрязнения воды научить детей быть бережливыми хозяевами природных ресурсов воспитывать любовь и бережное отношение к водным источникам. Приветствие в кругу друзей: Экологов в круг приглашаем сейчас Проблемы воды мы обсудим как раз.
76021. Казкові герої виліплення з пластиліну. Виготовлення плоских форм на площині казкового героя 50 KB
  Як ви уже зрозуміли сьогодні до нас на урок завітала казка Чи полюбляєте ви казки Які казки вам подобаються Про що ми дізнаємося у казках Як казочки завжди розпочинаються Як казочки закінчуються А чи знаєте ви що таке казка і звідки вона до нас прийшла...
76022. НИКТО НЕ ЗАБЫТ, НИЧТО НЕ ЗАБЫТО... ВЕЧЕР ПАМЯТИ, ПОСВЯЩЁННЫЙ 66-Й ГОДОВЩИНЕ ВЕЛИКОЙ ПОБЕДЫ 49 KB
  22 июня 1941 года, нарушив мирную жизнь людей, внезапно, без объявления войны, фашистская Германия напала на нашу страну. В тихое, мирное воскресное утро, когда еще люди спали, началась война. (В записи звучит песня «Священная война».)
76023. МЫ БУДЕМ ПОМНИТЬ ВАШИ ИМЕНА... ЛИТЕРАТУРНО – МУЗЫКАЛЬНАЯ КОМПОЗИЦИЯ, ПОСВЯЩЕННАЯ ДНЮ ОСВОБОЖДЕНИЯ ОДЕССЫ И ДНЮ ПОБЕДЫ 79 KB
  Вставай страна огромная Пусть ярость благородная Вставай на смертный бой Вскипает как волна С фашистской силой темною Идет война народная С проклятою ордой Священная война Одесса была одним из первых городов преградившим на длительное время путь врагу.
76024. Побратимські стосунки між угорським містечком та прикарпатським селом 626.5 KB
  Курс України на плідну й довготривалу співпрацю з багатьма країнами, її інтеграція в європейський освітній простір, міжнародний обмін інформацією в різних галузях знань, реальна можливість навчання, проходження практики, стажування та робота в зарубіжних...