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) выполняются на всем множестве допустимых альтернатив А.

Уменьшая параметр  и тем самым уменьшая взвешенные потери по всем целевых функциях, мы приближаемся к альтернативе, обеспечивающей минимальные потери по всем целевым функциям, то есть к компромиссной альтернативе. Итерационный процесс прекращается, когда наименьшее

W2

значение  ( где  – номер итерации), при котором система неравенств на множестве допустимых

G

k0(1)

 альтернатив еще совместна, отличается от своего ближайшего значения , при котором она становится уже не совместной, не более чем на , где  – довольно

W2

маленькая величина, которая задается из соображений допустимого времени решения задачи. При этом, если решение

k0(1)

G

системы неравенств

k0(j)

единственное, то это и будет

k0(l)

искомая компромиссная

k0(l+1)

альтернатива. Если же это решение

С*

 не единственное, то

R

A

для полученных альтернатив

W1

относительные потери будут

Рис. 1.7.

эквивалентны с точностью до . Единственную компромиссную альтернативу тогда можно получить, оптимизируя на этом множестве эквивалентных альтернатив некоторый дополнительный обобщенный критерий. В качестве такого критерия можно выбрать, например, критерий вида.

 ,                               (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 метод ограничений будет применен для решения многокритериальных задач линейного программирования.