36212

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

Доклад

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

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

Русский

2013-09-21

79.5 KB

61 чел.

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


 

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

52709. Героев имена помнит Донбасс 53 KB
  Цель: Воспитывать уважительное отношения к исторической памяти народа. Способствовать формированию стремлению учащихся знать историю своего народа и отстаивать историческую правду. Воспитывать ответственность, эмпатию, потребность личного участия в мероприятиях, посвященных празднованию памятных дат.
52711. Моєму рідному краю, його величності Донбасу – 80 1.58 MB
  Мета: Формувати в учнів інтерес до навчання; формувати також в учнів навички здорового способу життя, навички толерантного спілкування; засвоїти матеріал за темою; вчити розповідати про символи Української держави та їх значення; розвивати прагнення бути свідомим громадянином України, її патріотом.
52713. Організація надання першої медичної допомоги в бою. Реанімація потерпілих 223 KB
  Ознайомити учнів з особливостями розшуку поранених на полі бою; навчити проводити первинний огляд поранених надавати першу медичну допомогу; формувати практичні навички проведення підручних заходів реанімації потерпілих.Розшук поранених на полі бою.Збір виніс вивіз і евакуація поранених з поля бою.
52714. Розв’язування завдань з параметрами – напрямок розвитку творчого математичного мислення учнів 220 KB
  Декілька прикладів розвязування задач з параметрами. В якості змістовної основи для побудови системи вправ розвивального характеру можна запропонувати завдання з параметрами. Це дозволяє розглядати задачі з параметрами як змістовний матеріал для повноцінної математичної діяльності.
52716. СНІД – СТРАШНИЙ СУПУТНИК ЛЮДСТВА 76.5 KB
  Мета: формувати в учнів інтерес до існування глобальних проблем людства; формувати навички здорового способу життя; розвивати зацікавленість до творчо-пошукової роботи; виховувати почуття небайдужості, добра та співчуття.
52717. ФОРМУВАННЯ КОМПЕТЕНТНОСТЕЙ УЧНІВ ЗАСОБАМИ ІННОВАЦІЙНИХ ТЕХНОЛОГІЙ 48.5 KB
  Цілі та завдання технології: Формування пізнавального інтересу в учнів та розуміння мети вивчення даної теми; Розвиток внутрішньої мотивації до цілеспрямованого навчання; Підтримування пізнавальної активності учнів; Спонукання учнів до порівняння отриманої інформації з особистим досвідом і на її грунті формування аналітичного судження; Розвиток критичного способу мислення. ТЕХНОЛОГІЯ ІНТЕРАКТИВНОГО НАВЧАННЯ Наприкінці ХХ століття інтерактивні технології набули поширення в теорії та практиці американської...