![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Исследование операций
|
20.01.2005
|
![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1.4. ПРИНЯТИЕ РЕШЕНИЙ ПРИ ВЕКТОРНОМ КРИТЕРИИ ОПТИМАЛЬНОСТИПостановка многокритериальной задачи принятия решений и ее свойства. Рассмотрим ситуацию принятия решений на заданном множестве допустимых альтернатив при необходимости учета совокупности свойств, описываемых множеством целевых функций:
Будем считать, что первые m целевых функций максимизируются, а остальные M-m - минимизируются. Обозначим через Введем следующие отношения на множестве альтернатив при наличии множества целевых функций (критериев): а) слабого предпочтения б) строгого предпочтения (лучше): в) сильного предпочтения: г) эквивалентности: Следует подчеркнуть, что отношение Таблица 1.9
В этом заключается одна из принципиальных особенностей задач многокритериальной (векторной) оптимизации (МКО). Рассмотрим пример. Пусть в некоторой задаче принятия решений нужно выбрать одно управляющее воздействие (стратегию) из заданного множества Пусть первая целевая функция Какие же альтернативы считаются лучшими по совокупности целевых функций? Если Если во множестве допустимых альтернатив А существует хотя бы одна альтернатива Альтернатива и хотя бы одно из них было строгим. Это означает, что никакая другая альтернатива не может улучшить значение некоторой целевой функции по сравнению с эффективной альтернативой, не ухудшая при этом хотя бы одной из оставшихся целевых функций. Поэтому иногда эффективную альтернативу называют неулучшаемой по множеству целевых функций или оптимальной по Парето [39]. Из определения эффективной альтернативы вытекает следующая теорема [33]. ТЕОРЕМА 1.2. Две эффективные альтернативы либо эквивалентны, либо не сравнимы между собою по множеству целевых функций. Доказательство. Если Из теоремы следует, что если существует только одна эффективная альтернатива, то она обращает в оптимум каждый из критериев Как и в случае принятия решений с учетом одного критерия, в задачах принятия решений за одним критерием, в задачах принятия решения по множеству целевых функций могут существовать несколько множеств целевых функций, которым соответствуют одни и те же отношения строгого предпочтения и эквивалентности. В силу сказанного введем следующее определение. Множества целевых функций Очевидно,эквивалентные множества целевых функций определяют на множестве допустимых альтернатив одни и те же отношения эквивалентности и строгого предпочтения. ТЕОРЕМА 1.3. Если существует множество монотонных преобразований Доказать эту теорему можно, воспользовавшись теоремой 1.1. Используя теорему 1.2, а также определение эффективных альтернатив, нетрудно доказать и следующее утверждение. Если Поскольку целевые функции Обозначим через Пусть
![]() и хотя бы одно из неравенств (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 метод ограничений будет применен для решения многокритериальных задач линейного программирования.