Eng | Rus | Ukr | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Исследование операций
|
20.01.2005
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1.4. ПРИНЯТИЕ РЕШЕНИЙ ПРИ ВЕКТОРНОМ КРИТЕРИИ ОПТИМАЛЬНОСТИПостановка многокритериальной задачи принятия решений и ее свойства. Рассмотрим ситуацию принятия решений на заданном множестве допустимых альтернатив при необходимости учета совокупности свойств, описываемых множеством целевых функций: , где - отвечает i-му свойству, по которому оцениваются альтернативы . Будем считать, что первые m целевых функций максимизируются, а остальные M-m - минимизируются. Обозначим через и множества индексов соответственно для максимизируемых и минимизируемых функций. Чтобы сформулировать задачу принятия сложных решений в терминах многокритериальной оптимизации, остановимся на вопросе сравнения альтернатив по множестве целевых функций. Введем следующие отношения на множестве альтернатив при наличии множества целевых функций (критериев): а) слабого предпочтения (не хуже): будем говорить, что , если (1.4.1) б) строгого предпочтения (лучше): , тогда и только тогда, если система неравенств (1.4.1) выполняется и хотя бы одно из них - строго; в) сильного предпочтения: , если все неравенства (1.4.1) - строгие; г) эквивалентности: тогда и только тогда, когда . Следует подчеркнуть, что отношение , описываемое соотношениями (1.4.1) не является линейным или сильно упорядоченным. Это означает, что не всякая пара альтернатив сравнима по множеству целевых функций , то есть не для всех пар альтернатив имеет место либо , либо , либо то и другое вместе. Таблица 1.9
В этом заключается одна из принципиальных особенностей задач многокритериальной (векторной) оптимизации (МКО). Рассмотрим пример. Пусть в некоторой задаче принятия решений нужно выбрать одно управляющее воздействие (стратегию) из заданного множества с учетом двух целевых функций и , значения которых приведены в таблице 1.9. Пусть первая целевая функция определяет производительность устройства и измеряется в операциях за секунду, а вторая целевая функция - стоимость устройства и измеряется в рублях. Нужно выбрать такое решение - проект прибора, которое будет обладать наибольшей производительностью и минимальной стоимостью. Очевидно, что при сравнении альтернатив по этим критериям (целевым функциям) , а в каком отношении находятся между собой остальные решения, сказать невозможно. Какие же альтернативы считаются лучшими по совокупности целевых функций? Если , то альтернатива предпочтительнее альтернативы , так как при переходе от к , мы ничего не проигрываем ни по одному из критериев, а по одному и выигрываем. В этом случае говорят, что доминирует над . Если во множестве допустимых альтернатив А существует хотя бы одна альтернатива такая, что , то альтернатива x называется доминированой Если же такой альтернативы не существует, то альтернатива называется недоминируемой или эффективной. Дадим более строгое определение эффективной альтернативы в терминах целевых функций. Альтернатива носит название эффективной, если на множестве допустимых альтернатив А не существует такой альтернативы , для которой бы выполнялись неравенства: (1.4.2) (1.4.3) и хотя бы одно из них было строгим. Это означает, что никакая другая альтернатива не может улучшить значение некоторой целевой функции по сравнению с эффективной альтернативой, не ухудшая при этом хотя бы одной из оставшихся целевых функций. Поэтому иногда эффективную альтернативу называют неулучшаемой по множеству целевых функций или оптимальной по Парето [39]. Из определения эффективной альтернативы вытекает следующая теорема [33]. ТЕОРЕМА 1.2. Две эффективные альтернативы либо эквивалентны, либо не сравнимы между собою по множеству целевых функций. Доказательство. Если - эффективная альтернатива, то для любой альтернативы , которая не совпадает с по множеству целевых функций, либо справедливо M равенств вида и тогда эквивалентна , либо найдется по крайней мере один индекс такой, что , если , или , если , и тогда не может быть эффективной. Из теоремы следует, что если существует только одна эффективная альтернатива, то она обращает в оптимум каждый из критериев . Действительно, поскольку, то очевидно и Как и в случае принятия решений с учетом одного критерия, в задачах принятия решений за одним критерием, в задачах принятия решения по множеству целевых функций могут существовать несколько множеств целевых функций, которым соответствуют одни и те же отношения строгого предпочтения и эквивалентности. В силу сказанного введем следующее определение. Множества целевых функций и определенные на одном и том же множестве допустимых альтернатив А, будем называть эквивалентными, если они определяют на нем одно и то же отношение слабого предпочтения, то есть для любых двух альтернатив из следует, что , и наоборот, из следует, что . Очевидно,эквивалентные множества целевых функций определяют на множестве допустимых альтернатив одни и те же отношения эквивалентности и строгого предпочтения. ТЕОРЕМА 1.3. Если существует множество монотонных преобразований таких, что -е преобразование переводит область значений функции в область значений функции и для всего множества допустимых альтернатив А, то множества целевых функций и эквивалентны. Доказать эту теорему можно, воспользовавшись теоремой 1.1. Используя теорему 1.2, а также определение эффективных альтернатив, нетрудно доказать и следующее утверждение. Если - эффективная альтернатива на множестве целевых функций , то - эффективная альтернатива и на множестве функций , где - монотонная функция от . Поскольку целевые функции имеют различную физическую размерность, так как характеризуют разные свойства выбираемого решения, то зачастую целесообразно рассматривать не само множество целевых функций, а эквивалентное ему множество функций , где - монотонные преобразования, приводящие целевую функцию к безразмерному виду и позволяющие сравнивать их между собой. Обозначим через множество значений функций , на котором каждой альтернативе соответствует определенный вектор , где , и наоборот. Тогда отношения слабого предпочтения, эквивалентности и строгого предпочтения, введенные для альтернатив, оказываются пригодными и для множества W. Пусть , тогда
и хотя бы одно из неравенств (1.4.4) будет строгим. Вектор , соответствующий эффективной альтернативе, будем называть эффективным. Свойства эффективных альтернатив
|
|
|
в) , (1.4.11)
где - соответственно наименьшие значения максимизируемых и наибольшие значения минимизируемых целевых функций, достигаемые ими на множестве допустимых альтернатив.
В выражении (1.4.11) могут определяться соотношениями (1.4.9) или (1.4.10), а показатель степени - целое число, причем . Заметим, что в преобразованиях (1.4.9) величины всегда лежат в границах интервала , а в преобразованиях (1.4.10) могут и не лежать. Выбранные преобразования однозначно определяют расположение множества допустимых альтернатив, описываемого одним из соотношений (1.4.9) - (1.4.11) в пространстве значений функций .
Теперь определим, какую альтернативу будем считать решением задачи многокритериальной оптимизации, если выбрано множество функций , каждая из которых минимизируется, и заданы отношения предпочтения на множестве целевых функций.
Справедливое следующее утверждение.
ТЕОРЕМА 1.7. Для каждой допустимой альтернативы такой, что в пространстве , существуют вектор , удовлетворяющий соотношению
, (1.4.12)
и число , такие, что альтернатива удовлетворяет одновременно М равенствам вида
. (1.4.13)
Доказательство.Так как , то разделив обе части выражения (1.4.13) на , получим
. (1.4.14)
Но поскольку величины должны удовлетворять условиям (1.4.12), то подставив в соотношение выражение для получим
. (1.4.15)
С учетом (1.4.15) выражение (1.4.14) принимает вид
, (1.4.16)
что и доказывает теорему 1.7.
Выражение (1.4.15), определяющее параметр , является монотонно-возрастающей функцией по каждой из переменных на интервале , и при этом , где .
Справедлива такая лемма [33].
ЛЕММА. Если для двух неэквивалентных альтернатив и векторы и равны , то и , где - коэффициент пропорциональности.
Доказательство. Альтернатива удовлетворяет системе (1.4.13): , а альтернатива - системе вида . Откуда и . С учетом того, что , получим
. (1.4.17)
Это равенство и доказывает лемму. Заметим, что при , то есть .
Произвольный вектор весовых коэффициентов , удовлетворяющий соотношениям (1.4.12), будем интерпретировать как предпочтение целевых функций множества друг перед другом, выраженное в количественной шкале оценок.
Определим направление, порожденное вектором в пространстве . Зададим его углами между осями координат и радиусом - вектором . Тогда
, (1.4.18)
где - точка, находящаяся в пространстве на луче . Учитывая это соотношение и условие нормировки, запишем систему линейно независимых уравнений, из которых можно найти неизвестные направляющие косинусы:
и . (1.4.19)
Вместе с тем вследствие теоремы 1.7
, (1.4.20)
Учитывая последнее соотношение, систему уравнений (1.4.19) можно записать так:
. (1.4.21)
Решая эту систему, получим следующее выражение для направляющих косинусов вектора:
. (1.4.22)
Будем считать целевые функции равноценными, если , тогда направляющие косинусы для такого вектора в пространстве будут определять так:
.
Таким образом, задание отношения предпочтения между целевыми функциями в количественной шкале с помощью (1.4.13) дает направление поиска решений в пространстве значений выбранных преобразований целевых функций .
Поэтому под решением задачи векторной оптимизации будем понимать такую компромиссную альтернативу, которая принадлежит множеству эффективных альтернатив и лежит на заданном направлении, определяемом вектором в пространстве W. Если для некоторой альтернативы и заданного вектора выполняется соотношение , то будем говорить, что альтернатива лежит на направлении, определяемом вектором . Найдем, какое значение параметра соответствует эффективной альтернативе, лежащей на направлении, определяемом вектором . Ответ на этот вопрос дает следующая теорема.
ТЕОРЕМА 1.8. Если - эффективная альтернатива для данного вектора , то ей соответствует наименьшее значение параметра , при котором система нестрогих равенств (1.4.13) выполняется одновременно для всех .
Доказательство этой теоремы вытекает непосредственно из леммы и определения эффективности альтернативы . Пусть в качестве преобразований целевой функции выбраны преобразования вида (1.4.9). Тогда с учетом теоремы 1.7 решение задачи векторной оптимизации определим следующим образом [33].
Под решением задачи векторной оптимизации для заданного вектора предпочтений понимается такая компромиссная альтернатива , которая обеспечивает одинаковые минимальные взвешенные относительные потери по всем критериям одновременно.
Рассмотрим подход к поиску компромиссного решения (альтернативы) в задаче векторной оптимизации. Он основан на следующей теореме.
ТЕОРЕМА 1.9. Для того, чтобы альтернатива такая, что , была эффективной при заданном векторе предпочтений , достаточно, чтобы была единственным решением системы неравенств
(1.4.23)
для минимального значения параметра , при котором эта система совместная
Доказательство. Предположим противное, что единственное решение системы (1.4.23) при значении параметра неэффективно. Тогда существует альтернатива такая, что , причем хотя бы одно неравенство будет строгим. Умножив эти неравенства на получим, что и хотя бы одно неравенство строгое. Итак, получаем противоречие: альтернатива удовлетворяет системе (1.4.23) со значением параметра , не превосходящим . Таким образом, теорема 1.9 доказана.
Из этой теоремы следует, что определенное высшее компромиссное решение может быть найдено как единственное решение системы неравенств вида (1.4.23) для минимального значения параметра , при котором эта система еще совместна. В пространстве компромиссной альтернативе соответствует точка пересечения луча, направляющие косинусы которого определяются заданным вектором предпочтений по формулам (1.4.22), с областью эффективных альтернатив. Если существует эта точка пересечения, то отсюда следует существование компромиссного решения, для которого минимальные взвешенные потери по всем критериям одинаковы: . Если же такой точки не существует (то есть луч, определяемый вектором предпочтений , не пересекает область эффективных альтернатив), то для компромиссной альтернативы выполняется система неравенств (1.4.23) и этой альтернативе будет соответствовать точка, ближайшая к заданному лучу.
Для нахождения компромиссной альтернативы строится итерационный процесс с параметром , на каждом шаге которого проверяется совместимость системы неравенств (1.4.23) для и заданного вектора . Параметр ограничивает относительные потери . При относительные потери стремятся к нулю, то есть целевые функции стремятся к своим оптимальным значениям , а при неравенства (1.4.23) выполняются на всем множестве допустимых альтернатив А.
Уменьшая параметр и тем самым уменьшая взвешенные потери по всем целевых функциях, мы приближаемся к альтернативе, обеспечивающей минимальные потери по всем целевым функциям, то есть к компромиссной альтернативе. Итерационный процесс прекращается, когда наименьшее
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, (1.4.24)
и минимизировать его на множестве альтернатив
. (1.4.25)
Как показано выше, такой обобщенный критерий всегда дает эффективные решения.
Проиллюстрируем идею метода на примере двух равноценных критериев на множестве допустимых альтернатив, описываемых линейными ограничениями (рис. 1.7), где - область значений преобразованных критериев и в пространстве ограничений; - граница этого множества, определяемая соотношениями - часть области значений и , в которой эти критерии принимают значения, не превосходящие . Поскольку эти критерии считаются равноценными, то есть и , то направление совпадает с направлением биссектрисы координатного угла . Решения, дающие минимальные относительные отклонения от оптимальных значений, находятся в области на луче, исходящем из начала координат в направления . Компромисс, принадлежащий множеству эффективных альтернатив, будет в точке , определяемой пересечением упомянутого луча с областью эффективных точек. Чтобы отыскать эту точку, определяем такое наименьшее значение , при котором еще не пусто пересечение областей и .
Если же вектор , определенный в соответствии с формулой (1.4.22), не пересекается с областью значений критериев , то в область , соответствующую минимальному при котором система еще совместна, попадает некоторое подмножество точек, среди которых обязательно есть эффективная, наилучшим образом отвечающая предпочтениям, задаваемым весовым вектором (то есть ближайшая к лучу ).
Рассмотрим некоторые известные методы отыскания компромиссных решений в задачах векторной оптимизации.
Одним из таких методов является метод, предложенный Ю. Б. Гермейером [10]. Он основан на минимизации обобщенного критерия вида
, (1.4.26)
где - описывается преобразованиями (1.4.9).
Этот метод минимакса позволяет найти такую альтернативу , для которой либо выполняется система равенств для всех и минимального значения параметра , либо для некоторых равенства не выполняются и . Если при этом такая альтернатива единственная, то это и есть искомое компромиссное решение. Поэтому рассмотренный дальше метод ограничений, основанный на поиске допустимых альтернатив системы неравенств (1.4.23) при минимальном значении параметра , можно рассматривать как метод решения минимаксной задачи виду
минимизировать . (1.4.27)
Если решение (1.4.27) не единственное, то для выбора компромиссной альтернативы нужно применить дополнительный критерий вида (1.4.24).
Таким образом, если в качестве монотонных преобразований целевых функций выбрать соотношения (1.4.9), то задачу (1.4.24) - (1.4.25) нахождения единственной компромиссной альтернативы можно сформулировать следующим образом.
Найти решение следующей задачи параметрического программирования относительно параметра при заданном векторе предпочтений :
минимизировать (1.4.28)
при условиях
, (1.4.29)
. (1.4.30)
Решение задачи (1.4.28) - (1.4.30) при минимально возможном значении параметра определит искомую компромиссную альтернативу.
Рассмотрим метод нахождения компромиссной альтернативы при решении задачи (1.4.28) - (1.4.30), который называется методом ограничений [33].
Вначале отыскивается минимально возможное значение параметра , при котором система ограничений (1.4.29) - (1.4.30) будет совместна.
Если найденное решение не единственное, то есть существует некоторое подмножество (эффективных) альтернатив, эквивалентных с точностью до по значению параметра , то выбор компромиссной альтернативы осуществляется с помощью критерия (1.4.28).
Такой метод не зависит от вида функциональных зависимостей и множества допустимых альтернатив А. Вместе с тем для каждого конкретного вида зависимостей необходимо иметь эффективные способы проверки совместности системы неравенств (1.4.29) - (1.4.30) на заданной области ограничений.
В гл.2 метод ограничений будет применен для решения многокритериальных задач линейного программирования.