 |
Принцип максимальной эффективности в принцип гарантированного результата в случае равнозначных критериев
|
|
|
|
Рассмотрим задачу векторной максимизации, допустимое множество Ω которой представляет собой выпуклое подмножество пространства 
, а частные критерии 
являются элементами пространства 
- непрерывных функций 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, определим минимум для оставшихся критериев 
:
Тогда 
(если бы 
, то появился бы новый уровень больше , отсюда не оптимально, что противоречит условиям задачи), т.е. полученное решение с минимальным уровнем не оптимально.
Следовательно, не существует другой точки 
, для которой бы выполнялось равенство 
, а остальные критерии удовлетворяли бы неравенствам 
Таким образом, точка не оптимальна по Парето, что и требовалось доказать.
|
|
|
