36212

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

Доклад

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

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

Русский

2013-09-21

79.5 KB

76 чел.

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


 

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

66694. А.С. Макаренко 142 KB
  Одну з кращих своїх статей, написану для ювілейного збірника з приводу п'ятиліття комуни імені Ф.Э.Дзержинського, Антон Семенович так і назвав «Педагоги знизують плечима». Ці люди не розуміли, що вже давно наступив момент, коли без теорії не можна стати гарним практиком...
66695. МАТРИЧНЫЕ (ИГОЛЬЧАТЫЕ) ПРИНТЕРЫ 105.5 KB
  В зависимости от технологии печати различают матричные струйные лазерные светодиодные сублимационные принтеры. От их количества зависит качество печати в основном на рынке представлены матричные принтеры печатающая головка которых имеет 24 иголки плотность печати до 180 dpi.
66696. Технология и организация междугордных перевозок 92.5 KB
  За последние 10 лет парк автомобилей в России вырос почти в 25 раза. В 1999 году произошло существенное на 61 увеличение количества грузовых автомобилей в экономическом комплексе и впервые за последние годы зафиксирован рост объема грузовых автомобильных перевозок....
66697. Жизнь и научная деятельность Бориса Борисовича Полынова 376.55 KB
  Крупную роль в советском почвоведении играл Борис Борисович Полынов 1877 1952 гг. вышла в свет его книга Кора выветривания в которой были глубоко и всесторонне охарактеризованы основные фазы и главные типы кор выветривания Полынов 1934. Полынов одна из самых ярких личностей в советском почвоведении.
66699. Научный вклад Сергея Николаевича Виноградского в почвоведение 159.5 KB
  Кроме того Сергей Николаевич Виноградский объяснил процесс почвообразования показав что в почве существуют азотофиксирующие бактерии способные давать растениям необходимый для роста азот являющийся одним из главных лимитирующих факторов развития растений.
66700. Добровольский Глеб Всеволодович 111.53 KB
  Это вызвало повышенный интерес к проблемам экологии к проблемам биосферы Добровольский Г. Биография Глеб Всеволодович Добровольский академик Российской академии наук Президент Общества почвоведов при РАН известный почвоведэколог научная организационная...
66702. Диаграммы: основные понятия и термины 2.45 MB
  Одно из основных свойств, которое сделало Microsoft Excel мощным деловым пакетом – это возможность отображать числовые данные в виде полноцветных, легких для понимания диаграмм. Excel предоставляет широкий диапазон стандартных типов диаграмм научного и делового назначения...