36212

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

Доклад

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

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

Русский

2013-09-21

79.5 KB

58 чел.

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


 

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

43313. Розробка програмного забезпечення для визначення інформації про жорсткий диск за допомогою інтерфейсу IDE/ATAPI 710.5 KB
  Програми мовою асемблера дуже точні. Оскільки ця мова дозволяє програмістові безпосередньо працювати з усім апаратним забезпеченням, програми на асемблері можуть робити те, що недоступно ніякій іншій програмі. Безсумнівно, що в програмуванні пристроїв де потрібен контроль над окремими розрядами регістрів пристрою, програмування мовою асемблера - єдиний підходящий вибір. І остання причина для написання програми на мові асемблера. Тільки через написання програм на цьому рівні деталізації можна зрозуміти, як працює машина на самому нижньому рівні.
43314. Автоматизированная система управления воздушным движением 2.05 MB
  В системе автоматизированы процессы обработки и отображения информации от радиолокационных и радиотехнических средств, информации о планировании полетов, метеорологической обстановке и другие процедуры обеспечения процессов обслуживания воздушного движения. Все подсистемы АС УВД построены на базе локальных вычислительных сетей с применением технологий цифровой обработки и передачи данных.
43315. Правова система України 168.21 KB
  Перш ніж будувати власну державу і власну правову систему потрібно подивитись, що ми маємо на сучасному етапі і що хочемо побудувати у майбутньому. Будуючи нову правову систему потрібно звертатись за допомогою до більш досконалих іноземних систем, вибираючи з них найкраще. Нажаль, в Україні, сьогодні, склалась така ситуація, коли люди, що стоять при владі не розуміють цього або, що ще гірше розуміють, але спеціально нічого не роблять. Все на що вони спроможні – це бездумно вирвати з іноземного законодавства, можливо і найкращі, положення та ліпити їх в наше. Багато наших бід саме через це.
43316. Розробка програм на мові Turbo Pascal. Робота з додатками MS Office 97/200 (Word, Excel) і MathCAD 2000 2.5 MB
  Відмінність функції від процедури полягає в тому що результатом виконання операторів що утворюють тіло функції завжди є деяке єдине значення або покажчик тому звертання до функції можна використовувати у відповідних вираженнях поряд зі змінними й констант Підпрограми являють собою інструмент за допомогою якого будьяка програма може бути розбита на ряд певною мірою незалежних друг від друга частин. Поперше цей засіб економії пам'яті: кожна підпрограма існує в програмі в єдиному екземплярі у те час як звертатися до неї можна...
43317. Гарантированное удаление информации 298.5 KB
  Гарантированное удаление информации зачем это нужно Большинство пользователей персональных компьютеров уверены в том что стандартные функции уничтожения файлов предусмотренные в операционной системе позволяют раз и навсегда избавиться от файлов. Также немаловажным фактором является скорость удаления информации. Например если несмотря на все методы защиты каким-то образом был произведен несанкционированный доступ к секретной информации и выгоднее уничтожить эту самую информацию чем позволить злоумышленнику скачать ее нарушив таким...
43318. Обґрунтування зовнішньоекономічної угоди по експорту поліамідних волокон 241.5 KB
  Загальна характеристика товару Програма підготовки угоди. Аналіз можливостей країни з експорту товару. Характеристика умов експорту товару Визначення країниімпортера товару. Обґрунтування доцільної схеми транспортування та базисних умов поставки товару.
43319. Розкриття основних понять опіки (піклування) та патронату над дітьми 239.5 KB
  Поняття і значення опіки та піклування над дітьми. Історія становлення та розвитку інституту опіки та піклування в Україні. Загальна характеристика інститутів опіки та піклування над дітьм. Встановлення опіки та піклування над дітьми.
43320. Загальна характеристика аналітичних програм на телеканалі „Київ” 76 KB
  Загальна історія аналітичного телебачення Журналістика періоду перебудови Українське телебачення в 19912000 роках Жанрова стуктура телевізійної журналістики Аналітичні програми телеканалу Київ†та їх характеристика: Споживач Час мера з Олександром Колодієм У центрі уваги СТН Тижневик Телепресклуб Столиця Список використаної літератури Загальна історія аналітичного телебачення Перші аналітичні програми з'явилися в Радянському Союзі на початку 60х років. Саме 60ті роки для телебачення стали етапом...
43321. Адміністративно-правові засади управління інформаційною галуззю 176 KB
  Адміністративно правовий статус Інтернетвидань. Це укази Президента України серед яких підписані такі як “Про заходи щодо розвитку національної складової глобальної інформаційної мережі Інтернет та забезпечення широкого доступу до цієї мережі в Україніâ€ “Про додаткові заходи щодо безперешкодної діяльності засобів масової інформації дальшого утвердження свободи слова в Україніâ€ “Про Державний комітет інформаційної політики телебачення та радіомовлення Україн膓Про невідкладні додаткові заходи щодо зміцнення моральності...