- •Глава 10. Многокритериальные задачи принятия решений
- •10.1. Основы многокритериальной оптимизации
- •10.1.1. Многокритериальная задача математического программирования
- •10.1.2. Где искать оптимальное решение
- •10.1.3. Определения
- •10.1.4. Условия оптимальности
- •10.2. Методы многокритериальной оптимизации
- •10.2.1. Методы первой группы
- •10.2.1.1.Функция полезности
- •10.2.1.2. Решение на основе лексикографического упорядочения критериев
- •10.2.1.3. Метод главного критерия
- •10.2.1.4. Линейная свертка
- •10.2.1.5. Максиминная свертка
- •10.2.1.6. Метод идеальной точки
- •10.2.1.7. Целевое программирование (цп)
- •10.2.2. Интерактивные методы
- •10.2.2.1. Метод уступок
- •10.2.2.2. Интерактивное компромиссное программирование
- •Построить таблицу
- •10.2.2.3. Метод stem
- •10.2.2.4. Метод взвешенных метрик Чебышева
- •10.2.2.5. Прогрессивный алгоритм принятия многокритериальных решений
- •10.2.3. Построение эффективного множества
10.1.4. Условия оптимальности
Здесь рассмотрим наиболее важные с точки зрения приложений необходимые и достаточные условия оптимальности. Они позволяют строить методы отыскания эффективных решений и способы проверки эффективности найденных решений.
Наиболее общий случай необходимых условий содержит следующая теорема.
Теорема 1. Пусть Y*Gи все . Вектор Y* слабо эффективен тогда и только тогда, когда найдутся такие числа, что
(10.1)
Условие не ограничивает применимость теоремы, так как его всегда можно обеспечить добавлением кположительной константы.
При оговариваемых свойствах D и f(X) справедливы теоремы 2 и 3.
Теорема 2. Пусть D выпукло, а , вогнуты и положительны наD. Тогда решение X* слабо эффективно в том и только в том случае, если существуют такие числа , что
. (10.2)
Теорема 3. Пусть D выпукло, а f вогнуто. Для слабой эффективности точки X*D необходимо и достаточно, чтобы существовали числа , при которых
. (10.3)
Требование вогнутостиf существенно, так как его невыполнение может привести к тому, что не для всех слабо эффективных решений найдутся, удовлетворяющие (10.3). Например, для критериев и( выпукла) наD=[0,1] множество S(X)=D. Максимум функциидостигается только на одном из концов интервала[0,1] и поэтому ни при каких неотрицательныхимаксимизация этой функции не даст слабо оптимальную точку, лежащую внутриD.
Терема 4.ВекторY*G эффективен тогда и только тогда, когда для каждого
, (10.4)
где
¦>, }. (10.5)
Если Y*G эффективна, то она является единственной вG точкой, удовлетворяющей (10.4) при каждом.
Достаточные условия, приведенные ниже, основаны на свойствах возрастающей функции многих переменных. Поэтому сначала дадим определение такой функции. Числовая функция F(Y), определённая на множествеG, является возрастающей по отношению, если из выполнения неравенстваYY для векторовY,YG всегда следует справедливость неравенстваF(Y)>F(Y). Аналогично,F(Y) – функция, возрастающая по отношению >, если изY>Y всегда следуетF(Y)>F(Y).
Теорема 5.Пусть функцияF(Y) определена на множествеG. Для того чтобы точкаY*Gбыла эффективной (слабо эффективной), достаточно, чтобы она являлась точкой максимума на множествеG функцииF(Y), возрастающей по отношению(по отношению>).
Теорема легко доказывается от противного. Пусть Y*G и
F(Y*)F(Y) для всехYG. (10.6)
Предположим противное, т.е. что существует YG, для которого верно неравенствоY Y*. Так как функцияF возрастающая по отношению, то противоречит (10.6). Аналогично доказываются достаточные условия слабой эффективности.
Теорема 5 играет важную роль в решении многокритериальных задач. Её применение основано на максимизации возрастающих функций многих переменных. Поэтому целесообразно рассмотреть примеры таких функций.
1). Функция F(Y)=,где, является возрастающей по каждой переменнойна числовой оси и потому возрастает понаEm.Поэтому любая точка максимумаF(Y) наGэффективна. Эта же функция прии хотя бы одном из них положительном является возрастающей по отношению> и, значит, максимизация такой функции наG дает слабо эффективную точку.
2
m m m
3).Функция F(Y),гдеs>0, >0,а>= ,, возрастает по ≥ наG.Поэтому любая её точка максимума наG эффективна. Отсюда, в частности, следует, что минимизация широко применяемой функциидает эффективную точку.
4
m m
5). Возьмём функцию F(Y) при,. Еслидля всехi, то идля всехi. Поэтому справедливо неравенство
m
и, значит, приведённая функция возрастает по отношению > наE . Следовательно, любая её точка максимума наG слабо эффективна.