Принцип максимальной эффективности в принцип гарантированного результата в случае равнозначных критериев

Рассмотрим задачу векторной максимизации, допустимое множество Ω которой представляет собой выпуклое подмножество пространства , а частные критерии являются элементами пространства   непрерывных функций n переменных. Каждая функция цели  оценивает точки множества  с точки зрения различных качественных показателей, измеряемых в различных шкалах и имеющих различный содержательный смысл.

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

Нормализация критериев ЗВМ

Под способом нормализации критериев ЗВМ будем понимать однозначное отображение такое, что:

1. Решение задач:

,

                                                            (11)

должны совпадать для каждого .

2. Нормализованные критерии  должны быть измерены в одних и тех же единицах.

3. В оптимальных точках каждой частной задачи (11) величины всех критериев должны иметь одинаковую величину, т.е.

,

где  ­– оптимальное значение функции цели k -й  частной задачи.

Только при выполнении названных выше требований представляется возможным сравнить критерии по их численному значению. Для нормализиции критериев в ЗВМ в качестве отображения  используется линейное преобразование:

не влияющее на результат решения каждой частной задачи.

Рассмотрим один из способов нормализации задач векторной максимизации.

Пусть для любого k  конечны следующие величины:

Тогда:

a) критерии нормализованы, если каждый из них удовлетворяет соотношению:

;

b) критерии нормализованы, если каждый из них удовлетворяет соотношению:

Здесь  называется относительной оценкой по k -му критерию точки  и представляет собой степень достижения оптимума в точке  по k -й компоненте векторного критерия;  называется относительным отклонением достижения оптимума по k -му критерию.

Очевидно выполнение следующих свойств:

1)

2)

3)

Нормализацию, осуществленную таким способом, будем называть естественной.

Замечание 1. Кроме естественной нормализации известны следующие типы нормализации:

1) нормализация сравнения:

2) нормализация Сэвиджа:

3) нормализация осреднения:

Итак, рассмотрим ЗВМ с нормализованными критериями

Обозначим через , где  – заданная величина, .

Выбор некоторого уровня  означает для непустого множества , что степень достижения оптимума по каждой из компонент многоцелевого показателя не меньше .

 

Принцип гарантированного результата

 

Задача векторной максимизации при равнозначных критериях решена, если найдена точка  и максимальный уровень  среди всех относительных оценок такой, что:

                                                             (12)

 

Точка  обладает свойством:  (другими словами, ), т.е. оценка по k -му частному критерию в оптимальной точке не ниже величины .

Приведем алгоритмы решения ЗВО каждым из рассмотренных принципов.

Алгоритм 1. Алгоритм реализации принципа гарантированного результата

Шаг 0. Рассматривается задача векторной максимизации (2),  – частные критерии задачи, ,  – допустимое множество.

Шаг 1. Решение  частных задач вида:

 – максимальное значение функции цели;

 – минимальное значение функции цели.

Шаг 2. Нормализация частных критериев:

Шаг 3. Формирование функции

Шаг 4. Решение задачи:

(*)

 – решение задачи (*) является решением ЗВМ с принципом гарантированного результата. Останов.

Отметим, что, если число переменных и критериев в ЗВМ равно 2, то возможное графическое решение ЗВМ принципом гарантированного результата с использованием множества достижимости (см. пример 1).

Принцип максимальной эффективности

Принцип максимальной эффективности определяется как задача нахождения максимально возможного уровня , т.е. требуется найти решение задачи вида:

где , т.е.

                                    (13)

Элемент  называется оптимальным по принципу максимальной эффективности, если он является решением задачи (13). Величина  представляет собой наилучшее возможное приближение к оптимуму по всем компонентам многоцелевого показателя одновременно, в предположении, что их приоритет не задан.

Алгоритм 2. Алгоритм решения ЗВМ принципом максимальной эффективности

Шаг 0. Рассматривается задача векторной максимизации (2),  –частные критерии задачи, ,  – допустимое множество.

Шаг 1. Решение  частных задач вида:

 – максимальное значение функции цели;

 – минимальное значение функции цели.

Шаг 2. Нормализация частных критериев:

Шаг 3. Решение  -задачи

                                                      

 – решение  -задачи, которое является решением ЗВМ.

 

Замечание 2. В случае, если на шаге 2 алгоритма 2 выполнена нормализация сравнения, то в соответствующей задаче будет отсутствовать требование неотрицательности , т.к.  может быть любого знака.

Свойства принципов максимальной эффективности

и гарантированного результата

 

Важнейшим свойством приведенных принципов оптимальности является их эквивалентность, т.е. принцип максимальной эффективности совпадает с принципом гарантированного результата.

Теорема 1. Принцип максимальной эффективности совпадает с принципом гарантированного результата, т.е. .

Доказательство

1. Покажем, что .

2. Покажем, что .

В силу определения множества  и выполнения условия ;  имеем:

Из доказанных п. 1 и 2 следует справедливость теоремы. Что и требовалось доказать.

Таким образом, задача (12) сводится к эквивалентной ей задаче (13), которая представляет собой задачу скалярной оптимизации.

В силу этого,  с одной стороны,  принцип максимальной эффективности можно рассматривать как некоторую интерпретацию принципа гарантированного результата, а с другой стороны, как самостоятельный принцип выбора, который представляет собой экстремальную задачу оптимизации нахождения   из условия:

.                   (14)

В дальнейшем для определенности будем рассматривать принцип гарантированного результата, подразумевая его эквивалентное представление в виде задачи (14).

Взаимосвязь множества решений задач (12), (13) и множества эффективных точек ЗВМ нашла свое отражение в следующих теоремах.

Теорема 2. Решение  -задачи есть слабоэффективный вектор.

Доказательство. Предположим противное: пусть – решение задачи (13), и существует вектор , для которого , что эквивалентно предположению о том, что вектор  не является слабоэффективным.

Тогда , а следовательно,

что противоречит предположению о том, что  есть решение задачи (13). Теорема доказана.

 

На основе ЗВМ  (2) построим ЗВМ следующего вида:

где  – константы.

 

Теорема 3. Решение -задачи не зависит от положительного линейного преобразования частных критериев.

Доказательство. Докажем, что решения -задачи ЗВМ (2) и задачи (15) совпадают.

Пусть  - нормированные критерии задачи (2),

где

      

Аналогично: . Тогда

Из приведенного равенства немедленно следует доказательство теоремы.

Для доказательства следующей теоремы рассмотрим предварительно следующую лемму.

 

Лемма 1. В выпуклой ЗВМ, решенной на основе нормализации критериев и принципа гарантированного результата, в оптимальной точке всегда найдется 2 критерия с индексами q и p, для которых выполняется равенство: , а остальные критерии определяются неравенствами .

Доказательство. Первоначально докажем, что существует хотя бы один критерий q, для которого , а затем докажем, что таких критериев два.

1. Предположим противное: не существует ни одного критерия q, для которого , т.е. .

Рассмотрим

тогда , т.е.  не является решением задачи максимизации (12), получили противоречие.

2. Предположим, что существует только один критерий, для которого . Рассмотрим величину .

Тогда .

Частные критерии ЗВМ  являются непрерывными и вогнутыми функциями, тогда  также непрерывны и вогнуты . Следовательно, можно найти такое приращение , и соответственно , которое увеличило бы значение  где  и уменьшило один из критериев  (иначе все M критериев стремились бы к единице), который равен

,

и для которого остается строгое неравенство:

                                                      (**)

Такое увеличение критерия может идти до тех пор, пока относительная оценка одного из критериев   p   не будет равна относительной оценке критерия k, т.е. строгое неравенство (**) не станет равенством. В результате получили, что существует два критерия p, q, большие , что противоречит решению ВЗМ с принципом гарантированного результата, в котором  – максимальная величина. Остается принять, что существуют критерии p,q, относительные оценки которых равны . А остальные критерии определяются как  что и требовалось доказать.

 

Теорема 4. В выпуклой ЗВМ, решенной на основе нормализации критериев и принципа гарантированного результата, точка оптимума  оптимальна по Парето, причем такая точка только одна.

Доказательство. Пусть  –  решение задачи (12).

Тогда в точке оптимума , или

                                                                            (16)

Согласно лемме 1, система неравенств (16) выполняется как равенство хотя бы для двух критериев, т.е. существуют индексы p и q такие, что:

а для остальных индексов  где

Рассмотрим новую точку X ’, которая получается из  добавлением приращения  такого, что критерий q увеличился:

Тогда

Используя  рассуждения леммы 1, определим  минимум для оставшихся критериев :

Тогда  (если бы , то появился бы новый уровень больше , отсюда  не оптимально, что противоречит условиям задачи), т.е. полученное решение с минимальным уровнем  не оптимально.

Следовательно, не существует другой точки , для которой бы выполнялось равенство , а остальные критерии удовлетворяли бы неравенствам

Таким образом, точка  не оптимальна по Парето, что и требовалось доказать.