Лекция N 19

Общая схема решения многокритериальных задач

Для описания предпочтений используют бинарные отношения, вводимые на множестве А сравниваемых объектов. В многокритериальной задаче роль таких объектов играют X или Y на множествах Dи Gсоответственно.

Если из двух объектов a и b ЛПР выбирает a, то говорят, что a предпочтительнее b. Все пары вида (a,b), где a,bÎА, для которых a предпочтительнее b, образуют множество, называемое отношением строгого предпочтения на А. Такое отношение обозначают символом ý (aýb или aPb, где Р – первая буква английского слова preferance – предпочтение).

Объекты a и b неразличимы для ЛПР, если они одинаковы по предпочтительности. Это значит, что не выполняется ни отношение aýb, ни býa. Множество всех неразличимых пар (a,b) называют отношением неразличимости или безразличия и обозначают символом ~ (a~b или aIb, где I происходит от indifference – безразличие).

Очевидно, что для любой пары a,bA выполняется только одно из трех соотношений: aýb, býa, a~b. Объединение P и I дает отношение нестрогого предпочтения, обозначаемого символом (a b или aRb). Отношение a b означает, что a не менее предпочтительно, чем b.

В соответствии с этими определениями решение Х*D (вектор Y*G) называют оптимальным по отношению ý на множестве D (G), если не существует другого решения ХD (вектора YG), для которого справедливо соотношение ХýХ* (YýY*). Если для любых XD (YG) выполняется соотношение X* X (Y* Y), то X*D (Y*G) называется оптимальным решением (вектором) по отношению .

При сравнении по предпочтительности векторов Y=f(X) наиболее просто сопоставлять те вектора, которые отличаются лишь одной компонентой. Однако в общем случае частные критерии y_i=f_i(X) могут по-разному соотноситься по предпочтительности в зависимости от того , на каких уровнях зафиксированы остальные критерии. Так если вектор (,) предпочтительнее вектора (), а вектор () менее предпочтителен, чем (), то какое из значение первого критерия, или, предпочтительнее сказать нельзя без знания значений остальных критериев. Так, например, чем выше потолок комнаты, тем лучше, но справедливо это до определенных соотношений высоты, ширины и длины комнаты. Чаще, однако, все значения частного критерия можно упорядочить по предпочтению без учета значений других критериев. Такие критерии называют независимыми по предпочтению от остальных. Примерами могут служить прибыль, издержки и т.п.

Задачи, в которых все критерии независимы по предпочтению, а отношением строгого предпочтения R является отношение >= (не меньше) называются многокритериальными задачами максимизации (аналогично при отношении «не больше» – задачами минимизации).

Напомним, что R включает (объединяет) P и I. На множестве G (или D) отношение строгого порядка P задают неравенством YY’ ( т.е. Y Y’ и YY’ ) или Y>Y’ (т.е. для ). Наконец, равенство = порождает отношение безразличия.

Вектор (решение), оптимальный по отношению ≥ на множестве G (D), называется эффективным или парето-оптимальным. Значит, вектор Y^*ÎG является парето-оптимальным (оптимумом Парето), если не существует вектор Y Î G такой, что Y ³ Y^*. Множество таких векторов обозначают через Р(Y) и называют множеством Парето (эффективным множеством). Множество эффективных решений обозначают через Р(X).

Вектор, оптимальный по отношению >, называют слабо эффективным, слабо оптимальным по Парето (слабым оптимумом Парето). Значит, вектор Y^*ÎG слабо парето оптимальный, если не существует YÎG такой, что Y>Y^*. Множество таких векторов называют слабо эффективным и обозначают через S(Y). Соответствующее множество слабо эффективных решений имеет обозначение S(X). Если в G не найдётся Y³Y^*, то не существует и Y>Y^*. Следовательно, всякий эффективный вектор одновременно является и слабо эффективным, т.е. P(Y)ÍS(Y). Аналогично P(X) Í S(X).

Различие эффективного и слабо эффективного множеств хорошо видно на рис.10.3. Множество P(Y) состоит из частей границы множества G: кривых bc, de (исключая точки d и e ) и gh, а S(Y) – из кривой abcde (включая точку e) и кривой ghk. Точка d не входит в P(Y), т.к. она доминируется точкой c. Точно также точка e менее предпочтительна, чем g.

Геометрическое определение множеств P(Y) и S(Y) основано на том, что все точки YÎE^m, для которых выполняется неравенство Y³Y⁰, образуют ортант (для m=2 – прямой угол), стороны которого параллельны координатным осям, а вершиной является точка Y⁰.

Поэтому, если весь угол (ортант), построенный на некоторой точке Y*G, расположен вне множества G, то Y* парето-оптимальна. Если кроме вершины Y* пересечение ортанта и G содержит только точки, лежащие на одной из сторон ортанта, то Y* слабо парето-оптимальна, при этом Y*P(Y), т.е. не является эффективной.

Понятие слабой эффективности оказывается полезным и в случае, когда приходится сокращать первоначальный набор критериев. Нередко на первых этапах исследования трудно определить минимально необходимый набор критериев и поэтому начинают с возможно более полного набора. По мере изучения свойств задачи выявляются несущественные критерии, которые исключаются из дальнейшего рассмотрения. В [30] показано, что множество слабо эффективных решений, выделяемое на полном наборе критериев, содержит все исходные решения, эффективные по сокращенному набору критериев.

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

Наиболее общий случай необходимых условий содержит следующая теорема.

Теорема 1.Пусть Y*G и все . Вектор Y* слабо эффективен тогда и только тогда, когда найдутся такие числа, что

(1)

Условие не ограничивает применимость теоремы, так как его всегда можно обеспечить добавлением к положительной константы .

При оговариваемых свойствах D и f(X) справедливы теоремы 2 и 3.

Теорема 2.Пусть D выпукло, а , вогнуты и положительны на D. Тогда решение X* слабо эффективно в том и только в том случае, если существуют такие числа , что

. (2)

Теорема 3.ПустьD выпукло, а f вогнуто. Для слабой эффективности точки X^*ÎD необходимо и достаточно, чтобы существовали числа , при которых

. (3)

Требование вогнутости f существенно, так как его невыполнение может привести к тому, что не для всех слабо эффективных решений найдутся , удовлетворяющие (10.3). Например, для критериев и ( выпукла) на D=[0,1] множество S(X)=D. Максимум функции достигается только на одном из концов интервала [0,1] и поэтому ни при каких неотрицательных и максимизация этой функции не даст слабо оптимальную точку, лежащую внутри D.

Терема 4.Вектор Y^*ÎG эффективен тогда и только тогда, когда для каждого

, (4)

где

¦>, }. (5)

Если Y^*ÎG эффективна, то она является единственной в G точкой, удовлетворяющей (10.4) при каждом .

Достаточные условия, приведенные ниже, основаны на свойствах возрастающей функции многих переменных. Поэтому сначала дадим определение такой функции. Числовая функция F(Y), определённая на множестве G, является возрастающей по отношению ³, если из выполнения неравенства Y³Y^¢ для векторов Y,Y^¢ÎG всегда следует справедливость неравенства 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) для всех YÎG. (6)

Предположим противное, т.е. что существует Y^¢ÎG, для которого верно неравенство Y ^¢³Y^*. Так как функция F возрастающая по отношению ³, то противоречит (10.6). Аналогично доказываются достаточные условия слабой эффективности.

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

1). Функция F(Y)=, где , является возрастающей по каждой переменной на числовой оси и потому возрастает по ³ на E^m. Поэтому любая точка максимума F(Y) на G эффективна. Эта же функция при и хотя бы одном из них положительном является возрастающей по отношению > и, значит, максимизация такой функции на G дает слабо эффективную точку.

)=,

3).Функция F(Y), где s>0, >0, а >= , , возрастает по ≥ на G. Поэтому любая её точка максимума на G эффективна. Отсюда, в частности, следует, что минимизация широко применяемой функции дает эффективную точку

)

5). Возьмём функцию F(Y) при , . Если для всех i, то и для всех i. Поэтому справедливо неравенство

и, значит, приведённая функция возрастает по отношению > на E . Следовательно, любая её точка максимума на G слабо эффективна.

ЗАКЛЮЧЕНИЕ

Кратко подводятся итоги занятия, при этом обращается внимание студентов на цели и содержание дисциплины.

Дать задание на самостоятельную работу (отводимое время 4 часа):

ó с целью более глубокого освоения материала повторить и более подробно изучить линейную оптимизацию. Литература: [2] с. 262…264, конспект лекций,

При необходимости ответить на возникшие вопросы.

Старший преподаватель кафедры программного обеспечения И.Денисова