1.4. ПРИНЯТИЕ РЕШЕНИЙ ПРИ ВЕКТОРНОМ КРИТЕРИИ ОПТИМАЛЬНОСТИ
Постановка многокритериальной задачи принятия решений и ее свойства. Рассмотрим ситуацию принятия решений на заданном множестве допустимых альтернатив при необходимости учета совокупности свойств, описываемых множеством целевых функций:
, где 
- отвечает i-му свойству, по которому оцениваются альтернативы 
.
Будем считать, что первые m целевых функций максимизируются, а остальные M-m - минимизируются. Обозначим через 
и 
множества индексов соответственно для максимизируемых и минимизируемых функций. Чтобы сформулировать задачу принятия сложных решений в терминах многокритериальной оптимизации, остановимся на вопросе сравнения альтернатив по множестве целевых функций.
Введем следующие отношения на множестве альтернатив при наличии множества целевых функций (критериев):
а) слабого предпочтения 
(не хуже): будем говорить, что 
, если
(1.4.1)
б) строгого предпочтения (лучше): 
, тогда и только тогда, если система неравенств (1.4.1) выполняется и хотя бы одно из них - строго;
в) сильного предпочтения: 
, если все неравенства (1.4.1) - строгие;
г) эквивалентности: 
тогда и только тогда, когда 
.
Следует подчеркнуть, что отношение , описываемое соотношениями (1.4.1) не является линейным или сильно упорядоченным. Это означает, что не всякая пара альтернатив сравнима по множеству целевых функций 
, то есть не для всех пар альтернатив 
имеет место либо 
, либо 
, либо то и другое вместе.
Таблица 1.9
|
|
|
|
|
|
5 |
3 |
|
|
4 |
1 |
|
|
3 |
2 |
|
|
6 |
6 |
|
|
5 |
4 |
В этом заключается одна из принципиальных особенностей задач многокритериальной (векторной) оптимизации (МКО).
Рассмотрим пример. Пусть в некоторой задаче принятия решений нужно выбрать одно управляющее воздействие (стратегию) из заданного множества 
с учетом двух целевых функций 
и 
, значения которых приведены в таблице 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.4) будет строгим.
Вектор 
, соответствующий эффективной альтернативе, будем называть эффективным.
Свойства эффективных альтернатив
и способы их нахождения.
Будем считать, что все значения 
минимизируются и приведены к безразмерному виду. Свойства эффективных альтернатив устанавливаются в следующих трех теоремах.
ТЕОРЕМА 1.4. Если множество допустимых альтернатив А выпуклое, а целевые функции - вогнуты, то для любой эффективной альтернативы существует такой вектор 
, где 
и 
. что линейный критерий
(1.4.5)
достигает минимума на множестве А при 
.
Доказательство этой теоремы приведено в [22].
ТЕОРЕМА 1.5. Пусть - эффективная альтернатива множества целевых функций 
. Тогда существует вектор 
с компонентами 
и ,такой, что критерий
(1.4.6)
достигает минимума на множестве допустимых альтернатив А, описываемых соотношением вида (1.3.3)-(1.3.6) при .
В качестве компонент 
можно взять числа 
,
где 
; 
.
Эту теорему доказал Ю. Б. Гермейер [9] ,и она оказывается более сильной, чем теорема 1.3, поскольку никакие условия на вид функций 
и ограничения в ней не накладывается.
ТЕОРЕМА 1.6. Если - эффективная альтернатива множества целевых функций, то для любого 
,
(1.4.7)
или для любого 
(1.4.8)
.
Доказательство этой теоремы приведено в [39].
Эти теоремы позволяют строить различные способы нахождения эффективных альтернатив.
Принятие решения в задачи
многокритериальной оптимизации
Рассмотрим, как найти наиболее рациональное решение в задаче многокритериальной оптимизации. Такое решение может оказаться не оптимальным ни для одной целевой функции, но вместе с тем, оно оказывается наилучшим компромиссным решением с учетом всех целевых функций (критериев) одновременно. Очевидно, наилучшим решением следует считать такую альтернативу 
, при которой отклонение от оптимальных значений по каждой целевой функции :
достигает своего минимального значения. Здесь через 
обозначено оптимальное значение і-й целевой функции на множестве допустимых альтернатив. Но поскольку наименьшие значения величин 
не достигаются одновременно ни на одной альтернативе, то возникает необходимость сравнивать эти величины между собой, что связано с необходимостью привлечения дополнительной неформализованной информации от экспертов.
Поскольку целевые функции имеют различную размерность, то необходимо ввести некоторое преобразование , приводящее к безразмерному виду. Это преобразование должно удовлетворять, по крайней мере, следующим требованиям:
а) учитывать необходимость минимизации отклонений от оптимальных значений по каждой целевой функции;
б) иметь общее начало отсчета и один порядок изменения значений на всем множестве допустимых альтернатив;
в) сохранять отношение предпочтения на множестве альтернатив, сравниваемых по совокупности целевых функций , и тем самым не изменять множества эффективных альтернатив.
Последнее требование, как было показано ранее (в теореме 1.3), означает, что преобразование должно быть монотонным. В качестве такого преобразования можно выбрать одну из монотонных функций следующего вида
|
(1.4.9)
|
(1.4.10)
в) 
, (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 метод ограничений будет применен для решения многокритериальных задач линейного программирования.
