Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




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

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

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

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

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...