10 Вопрос

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

Введем следующие обозначения:

Х – область допустимых решений (ОДР) задачи (1.1), Х  Еⁿ; (будем полагать его замкнутым и ограниченным);

Q – образ множества Х в пространстве критериев: Q = q(X), Q  Е^m – область достижимых оценок; (критериальные функции q_i будем полагать непрерывными);

 = {E ^m _j > 0;  _j = 1} – незамкнутый симплекс в пространстве E ^m;

= {E ^m _j  0;  _j = 1} – замкнутый симплекс в пространстве E ^m;

( ) – положительный (неотрицательный) ортант в пространстве E^m; .

Par – бинарное отношение Парето, определенное на Q:

и ;

Sl – бинарное отношение Слейтера определенное на Q:

;

P(Q), S(Q) – множества элементов из Q, оптимальных по Парето и Слейтеру, соответственно (множества неулучшаемых оценок); P(Q) = { y  Q |  z  Q (z, y) Par };

P_q(Х), S_q(Х) – множества элементов из Х, оптимальных по Парето и Слейтеру, соответственно, при критериях q_i(x) (множества неулучшаемых решений);

P_q (Х) = { 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. (теорема Гермейера) Пусть (т.е. q_i(х) > 0 хХ). Тогда для того, чтобы решение х* Х было слабо-эффективным по векторному критерию q, необходимо и достаточно, чтобы существовал вектор параметров , при котором х* была точкой минимума функции ₂ (q(x), ⁰).

Геометрический смысл теоремы Гермейера. В пространстве критериев Е² линии равного уровня функций ₂(y, ), ₃(y, ) и ₄(y, ) при фиксированном  представляют собой вложенные “уголки”. Пусть, например, ₁= 2/3, ₂ =1/3. Построим линию равного уровня ₂(y, ) = 1/3. Эта линия будет содержать, например, точку А = (0.5, 1), т.к. max {0.52/3; 11/3} = 1/3 = ₂(A, ). Если теперь у₁ < 0.5, а у₂ = 1, то прежнему, ₂(, ) = 1/ 3. Если же у₂ < 1, а у₁ = 0.5, то также ₂(, ) = 1/3. Значит, линия уровня ₂(, ) = 1/3 – “уголок” с горизонтальной стороной у₂ = 1 и вертикальной у₁ = 0.5. Точка А – вершина уголка, ее координаты зависят от значений коэффициентов _i. Верно соотношение: ₁ А₁ = ₂ А₂ = ₂(A, ). (На рисунке точка А отмечена кружком).

Там, где уголок касается области Q, находится точка min. Вследствие такой уникальной формы линий уровня, независимо от выпуклости области Q любая слабо-эффективная точка у* будет точкой минимума ₂(у, ) при каком-нибудь , например при , и обратно – точка минимума ₂(у, ) при любом  будет слабо-эффективной.