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


 

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

20438. CASE-средства 1.81 MB
  В предыдущей лекции было рассказано о видах диаграмм UML и даны некоторые рекомендации относительно последовательности их построения. Мы уже знаем что нотация UML специально разрабатывалась в расчете на то чтобы диаграммы можно было легко рисовать от руки. В этой лекции мы познакомимся с некоторыми подобными пакетами а именно: IBM Rational Rose; Borland Together; Microsoft Visio; Sparx Systems Enterprise Architect; Gentleware Poseidon; SmartDraw; Dia; Telelogic TAU G2; StarUML; другие программы UML отличное средство моделирования но как...
20439. Rational Rose DataModeler 29.5 KB
  Унифицированный язык объектноориентированного моделирования Unified Modeling Language UML явился средством достижения компромисса между этими подходами. Существует достаточное количество инструментальных средств поддерживающих с помощью UML жизненный цикл информационных систем и одновременно UML является достаточно гибким для настройки и поддержки специфики деятельности различных команд разработчиков. Таким языком оказался UML. Создание UML началось в октябре 1994 г.
20440. CASE-средства 39.5 KB
  Microsoft Visio Visio решение для построения диаграмм от Microsoft. По словам разработчиков Visio помогает преобразовать технические и бизнесконцепции в визуальную форму. Visio имеет некоторые дополнительные возможности но все же повторим по большей мере это только средство для иллюстрирования документов MS Office не дотягивающее до уровня пакетов которые мы описывали ранее. Изобразительные же возможности Visio действительно весьма широки: Используя предопределенные фигуры Visio Professional draganddrop и мастера вы можете...
20441. Эволюция CASE-средств 99.5 KB
  Таким образом CASEтехнологии не могут считаться самостоятельными методологиями они только делают более эффективными пути их применения. CASE ≈ не революция в программо технике: современные CASEсредства являются естественным продолжением эволюции всей отрасли средств разработки ПО. Традиционно выделяют шесть периодов качественно отличающихся применяемой техникой и методами разработки ПО которые характеризуются использованием в качестве инструментальных следующих средств: ассемблеров дампов памяти анализаторов компиляторов...
20442. Варианты архитектуры клиент-сервер 122 KB
  Варианты архитектуры клиентсервер Разделение на три логических уровня обсуждавшееся в предыдущем пункте наводит на мысль о множестве вариантов физического распределения по отдельным компьютерам приложений в модели клиентсервер. Серверы реализующие все остальное то есть уровни обработки и данных. Проблема подобной организации состоит в том что на самом деле система не является распределенной: все происходит на сервере а клиент представляет собой не что иное как простой терминал. Многозвенные архитектуры Один из подходов к организации...
20443. Введение в UML 54.5 KB
  Модель физического уровня в языке UML отражает компонентный состав проектируемой системы с точки зрения ее реализации на аппаратурной и программной платформах конкретных производителей. Сущности в UML В UML определены четыре типа сущностей: структурные поведенческие группирующие и аннотационные. Структурные сущности это имена существительные в моделях на языке UML.
20444. Document Object Model 54 KB
  Модель DOM не накладывает ограничений на структуру документа. Любой документ известной структуры с помощью DOM может быть представлен в виде дерева узлов каждый узел которого представляет собой элемент атрибут текстовый графический или любой другой объект. Изначально различные браузеры имели собственные модели документов DOM не совместимые с остальными.
20445. Диаграмма развертывания (deployment diagram) 62 KB
  Для представления общей конфигурации и топологии распределенной программной системы в UML предназначены диаграммы развертывания. Диаграмма развертывания предназначена для визуализации элементов и компонентов программы существующих лишь на этапе ее исполнения runtime. Те компоненты которые не используются на этапе исполнения на диаграмме развертывания не показываются.