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


 

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

7906. Володимиро-Суздальське князівство. Великий Новгород. Монгольське завоювання Русі 25.48 KB
  Всесвітня історія: Володимиро-Суздальське князівство. Великий Новгород. Монгольське завоювання Русі. Невська битва та Льодове побоїще. Початок збирання руських земель навколо Москви. Мета: створити умови для всебічного розуміння учнями всіх політичн...
7907. Віра, надія, любов як духовно-практичні виміри людини 41 KB
  Віра, надія, любов як духовно-практичні виміри людини Загальноприйнятим і простим є твердження, що людина не може жити без віри. Насамперед віру тлумачать якупевненість людини в існуванні якого-небудь явища, визнання його реальності. Віра...
7908. Загальні засади організації системи органів влади України 40 KB
  Загальні засади організації системи органів влади України У розділі І Конституції Загальні засади є низка важливих положень, які стосуються характеру і статусу організації державної влади. В ч. 1 ст. 5 Конституції встановлено: «Народ здійснює влад...
7909. Причини, характер, періодизація Другої світової війни 29.2 KB
  Причини, характер, періодизація Другої світової війни Більше, ніж півстоліття минуло з дня закінчення Другої світової війни, яка принесла людству чисельні жертви і руйнування. У цій війні брали участь понад 60 держав, на території яких проживало...
7910. Стереотипи та їх роль у житті людини і суспільства. Толерантність. Ксенофобія. Расизм 26.28 KB
  Стереотипи та їх роль у житті людини і суспільства. Толерантність. Ксенофобія. Расизм. Мета: розвивати готовність і потребу учнів до самопізнання і самореалізації своєї особистості визначити сутність понять стереотипи, толерантність формувати ...
7911. Засоби масової інформації та їх роль у суспільному житті 28.66 KB
  Засоби масової інформації та їх роль у суспільному житті Мета: дати знання про сутність понять інформація, ЗМІ, Інформаційна революція визначити основні види і функції ЗМІ розкрити роль ЗМІ у сучасному суспільному житті продовжити формування вмін...
7912. Особливості розвитку української культури. Освіта. Недільні школи в наддніпрянській Україні. Вищі навчальні заклади. Новоросійський університет 25.19 KB
  Особливості розвитку української культури. Освіта. Недільні школи в наддніпрянській Україні. Вищі навчальні заклади. Новоросійський університет Освіта в другій половині XIX ст.Чому освіту називають світлом життя? МЕТА:формувати вміння аналізув...
7913. Османська імперія та її зовнішня політика. Ослаблення Османської імперії. Перське царство. Правління Надир-шаха 24.12 KB
  Османська імперія та її зовнішня політика. Ослаблення Османської імперії. Перське царство. Правління Надир-шаха. Османська імперія і відсіч Європи. На початку XVI ст. Османська імперія перетворилася на могутню державу з великою територією. Піс...
7914. Утворення та зміцнення Московської держави 22.5 KB
  Утворення та зміцнення Московської держави МЕТА: створити умови для всебічного розуміння учнями всіх політичних та економічних процесів розвитку земель Північно - Східної Русі. розвивати вміння зіставляти та порівнювати інформацію з різни...