Теория и методы принятия решений а также Хроника событий в Волшебных

6. Два пространства

Появление многокритериальное™ привело к принципиаль­ ному изменению характера решаемой задачи. Предпочтения ЛПР стали основой выработки решений. Они во многом опре­ деляют результат решения. Из наблюдателя и заказчика ЛПР превратился в решателя задачи. Решение теперь можно назвать субъективным, хотя в процессе решения используются объек­ тивные модели.

Характерной особенностью многокритериальных задач с объективными моделями является одновременное рассмотрение двух пространств — пространства переменных, используемых при построении модели, и пространства критериев.

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

0 ДО 1).

Введем два критерия: Ci — уменьшение безработицы (вы­ ражено в процентах); Сг —увеличение ВНП (выражено в про­ центах). Заметим, что при одном критерии оптимальное реше­ ние очевидно. При большом числе переменных и одном крите­ рии решение может быть найдено при помощи стандартных программ линейного программирования.

71

Пусть критерии связаны с переменными следующими зави­ симостями:

Ci = 0,1 xi -I- 0,9 Х2; Сг= 0,5 xi + 0,5 Х2.

Эти зависимости позволяют построить достижимую область изменения значений критериев S (рис. 3.4) при изменении пе­ ременных. Область S зависит от уравнений связи между пере­ менными и критериями. В реальных задачах число перемен­ ных велико (до десятков тысяч), а число критериев невелико (обычно не более 10). ЛПР работает с критериями, определяя свои требования к качеству решения и анализируя область S. Отметим еще раз, что область S появляется только в многокри­ териальных задачах.

Рис. 3.4. Допустимая область S измеиеиия значений критериев

7.Многокритериальный анализ экономической политики

От иллюстративной (и примитивной) модели перейдем к макроэкономической модели экономики Финляндии [6], по­ строенной в начале 70-х годов. Эта модель представляет собой совокупность линейных уравнений и ограничений. Некоторые переменные в модели были управляющими, т.е. могли быть изменены ЛПР. При определенных значениях управляющих переменных получаем одно из возможных решений. Качество решений оценивалось по четырем критериям:

Ci — увеличение валового национального продукта (выра­ жено в процентах);

Сг —уменьшение инфляции (выражено в процентах); Сз —уменьшение безработицы (выражено в процентах);

72

С4 —уменьшение дефицита внешней торговли (млрд фин­ ских марок).

Используя специальные человекомашинные процедуры (см. далее), несколько ЛПР получали при помощи макроэкономиче­ ской модели различные варианты экономической политики. В табл. 3.1 приведены три варианта, полученные одним из ЛПР.

Т а б л и ц а 3.1

Значения критериев оценки вариантов экономической политики

В нижней строке табл. 3.1 приведены наилучшие значения каждого из критериев, которые можно получить, если взять один из критериев как основной, а на другие не обращать вни­ мания. Наилучшие значения по всем критериям одновременно не достижимы. Модель, т.е. совокупность зависимостей между многочисленными переменными, описывающими экономику Финляндии, не позволяет получить такое решение. Это означа­ ет, что соответствующая точка лежит за пределами области до­ пустимых значений.

Варианты экономической политики, представленные в табл. 3.1, показаны также на рис. 3.5, где шкалы критериев по­ строены от лучших (нижних) к худшим (верхним) значениям.

Рис. 3.5. Три варианта экономической политики

73

Рисунок позволяет легко обнаружить, что три варианта эконо­ мической политики являются точками множества Э—П в четы­ рехмерном пространстве критериев. Действительно, первый ва­ риант дает минимальное значение инфляции, но отрицательный прирост ВНП и большую безработицу. Второй и третий вариан­ ты допускают большую инфляцию. Они приводят к росту ВНП, но вырастает и дефицит внешней торговли. Эти противоречия отражают типичный характер вариантов многокритериальных решений. Для окончательного выбора нужен компромисс: при­ ходится чем-то пожертвовать, чтобы что-то получить.

8. Две трудности для ЛПР

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

Чтобы принять решение, необходимо, во-первых, устано­ вить, насколько хорошие значения по критериям достижимы одновременно. Сделать это совсем не просто. В отличие от ил­ люстративного примера на рис. 3.3, число переменных, описы­ вающих область D допустимых значений, равно сотням и ты­ сячам. Получая каким-то из способов (см. далее) решение зада­ чи, ЛПР видит соотношения между критериями. Для поведе­ ния ЛПР типичны попытки достичь «всего сразу* (т.е. полу­ чить нанлучшне значения по всем критериям одновременно). Результаты таких попыток позволяют понять, чего можно дос­ тичь и чего нельзя. Наряду с этим ЛПР вырабатывает компро­ мисс между оценками по критериям, определяя желательное для него отношение между ними в точке решения.

Выработка такого компромисса достигается тоже путем проб, ошибок и затрат времени. На первых этапах решения ЛПР обычно стремится к идеальному результату, но потом, с опытом, его притязания становятся более реалистичными.

9. Исследование решений на множестве Э-П

При появлении многокритериальных задач возникла идея построения множества Э—П и организации работы ЛПР на этом множестве.

Из современных направлений исследований, идущих по этому пути, необходимо выделить два подхода. Первый из них

74

связан с визуализацией множества Э—П и предоставлением ЛПР возможности проводить анализ на плоскостях пар крите­ риев при фиксированных значениях других критериев. Этот подход получил название метода достижимых целей [13].

Другой подход применяется в тех случаях, когда ЛПР мо­ жет восстановить по совокупности критериальных оценок, а также по другим параметрам целостный облик альтернативы. Эта ситуация характерна обычно для деятельности конструкто­ ра. Предъявление решений, находящихся на множестве Э—П, помогает конструктору в поиске новых эффективных конст­ рукций механизмов и машин [14].

10. Постановка многокритериальной задачи линейного программирования

Теперь, когда основные трудности для ЛПР стали ясны, можно сформулировать многокритериальную задачу линейного программирования.

Дано: область D допустимых значений переменных, опре­ деляемая совокупностью линейных равенств и неравенств; кри­ терии Q, оценивающие качество решения.

Каждый из критериев линейно связан с переменными:

П

j=i

где п —число переменных (j = 1, ..., п); сц —числовые коэффи­ циенты.

Требуется: найти решение (xi, Х2,...,хп) в области D, при котором достигаются наиболее приемлемые значения по всем критериям. Иначе говоря, нужно найти такие критериальные оценки, при которых достигается максимальное значение ап­ риори неизвестной функции полезности ЛПР.

Эта задача решается с помощью человекомашинных процедур.

11. Человекомашинные процедуры

Средством исследования области допустимых решений, приводящим к желаемому выбору наилучшего решения, явля­ ются человекомашинные процедуры (ЧМП), представляющие

75

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

Фаза расчетов (компьютер):

•используя полученную от ЛПР на предыдущем шаге инфор­ мацию, проводит дополнительные расчеты;

•вычисляет решение, соответствующее последней информации ЛПР;

•вырабатывает вспомогательную информацию для ЛПР.

Фаза анализа (ЛПР):

•оценивая предъявленное решение (или совокупность реше­ ний), определяет, является ли решение (одно из решений) приемлемым; если да, то ЧМП окончена; в противном случае ЛПР анализирует вспомогательную информацию;

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

Существует большое количество ЧМП [3], [7]. Различные ЧМП отличаются друг от друга содержанием и способом вы­ полнения каждой из фаз. Первые из разработанных ЧМП осно­ ваны на использовании информации об относительной важно­ сти критериев.

12. Весовые коэффициенты важности критериев

При появлении многокритериальных задач возникли до­ полнительные трудности их решения, связанные с получением информации от ЛПР. Естественной реакцией на это было стремление получить такую информацию сразу и быстро устра­ нить многокритериальность. Этот подход был реализован путем объединения многих критериев в один с помощью так назы­ ваемых весовых коэффициентов важности критериев. Гло­ бальный критерий вычисляется по формуле

N

( 1)

где Q - частные критерии (i = 1, ..., N); wi —веса (коэффици­ енты важности) критериев:

i=l

76

Идея такого объединения состоит в том, что ЛПР назначает числа (часто по численной шкале 1—100), представляющие для него ценность рассматриваемого критерия. Считается, что ЛПР может назначить такие числа. Далее, весовые коэффициенты нормируются на основе условия (2).

Обратимся к рис. 3.2. Легко увидеть, что решения, соот­ ветствующие точкам А и В на множестве Эджворта—Парето, могут быть представлены в виде

Сд = 5> ,С *; св = 'f w ic®

Существует лемма [8], утверждающая, что для линейной задачи любое эффективное, находящееся на множестве Э—П, решение может быть представлено как решение задачи линей­ ного программирования с критерием (1). Следовательно, фор­ мально задача сводится к нахождению весов.

Возникла идея, что эти веса можно получить от ЛПР опе­ ративно. Если ЛПР затрудняется в начале процесса решения (до изучения области D) сразу назвать эти веса, то можно по­ строить ЧМП следующего содержания: ЛПР назначает перво­ начальные веса, смотрит на решение и корректирует веса до получения удовлетворительного результата.

13.Классификация ЧМП

В[3] предложена классификация ЧМП, основанная на ха­ рактере информации, получаемой от ЛПР на фазе анализа.

Первая группа ЧМП - прямые ЧМП, в которых ЛПР непо­ средственно назначает веса критериев и корректирует их на основе полученных решений.

Для второй группы ЧМП задача ЛПР состоит в сравнении многокритериальных решений. Эта группа называется ЧМП оценки векторов.

Третья группа требует от ЛПР наложения ограничений на значения критериев и, следовательно, на область достижимых значений. ЧМП этой группы называются ЧМП поиска удовле­

творительных решений.

Перед тем как перейти к рассмотрению ЧМП каждой груп­ пы, следует указать на общие предварительные этапы, встре­

77

чающиеся во многих ЧМП. Прежде всего рекомендуется произ­ вести нормирование критериев, определив диапазон их измене­ ния от 0 до 1:

с ^ о - £ ^ х ) Ck(x)-C k(x)

где Ск , Ск —минимально и максимально возможные значе­

ния k-го критерия; Ск(х) —промежуточное значение.

Кроме того, как это было показано выше (табл. 3.1), для каждого из критериев вычисляется наилучшее значение при предположении, что он является единственным. Вектор таких (недостижимых одновременно) значений помогает ЛПР оценить пределы возможного.

14.Прямые человекомашинные процедуры

Воснове прямых ЧМП лежит предположение, что человек может искать наилучшее решение путем непосредственного на­ значения ряда параметров (например, весов критериев) и срав­ нения получающихся решений.

Вкачестве примера прямых ЧМП рассмотрим процедуру SIGMOP (последовательный генератор информации для много­ целевых задач [9]). В ней ЛПР пытается найти хорошее реше­ ние путем назначения весов критериев (wi) и уровней допусти­ мых значений по всем критериям одновременно (Q >h).

Лицо, принимающее решение, задает начальные значения wi и li (i = 1, ...» N). Далее на фазе расчетов компьютер опреде­ ляет новую область D достижимых значений переменных и на­ ходит в ней значение глобального критерия (1), а также всех отдельных критериев. Значения всех критериев, не удовлетво­ ряющих начальным уровням, предъявляются ЛПР. После этого ЛПР меняет веса и ограничения в любой последовательности до тех пор, пока процедура не даст ему приемлемого решения.

Если критериев мало (два —три), то данная процедура мо­ жет быть достаточно удобной. Однако при возрастании числа критериев для ЛПР становится все сложнее оценить влияние на получаемые решения каждого из весов и каждого из огра­ ничений. Поэтому, вероятно, количество прямых ЧМП сравни­ тельно невелико [3].

78

15.Процедуры оценки векторов

Воснове этих процедур лежит предположение, что ЛПР может непосредственно сравнивать решения, предъявляемые ему в виде векторов в критериальном пространстве, и система­ тически искать в этом пространстве наилучший вектор.

Одной из наиболее известных ЧМП оценки векторов явля­ ется процедура Дайера-Джиофриона (Д—Д) [10]. Она начинает­ ся с выбора какой-либо точки в критериальном пространстве (рис. 3.6).

Рис. 3.6. Поиск решения в критериальном пространстве

В этой точке ЛПР определяет градиент глобальной целевой функции следующим образом. Один из критериев считается опорным. Берется небольшое изменение значения этого крите­ рия (в сторону улучшения) от начального. Перед ЛПР ставятся вопросы типа: какое изменение по иному критерию эквива­ лентно заданному изменению опорного критерия? Ответы ЛПР определяют вектор (направление), вдоль, которого изменение глобального критерия будет наиболее эффективным. Вдоль это­ го направления делается шаг определенной длины и получают­ ся новые значения по всем критериям. Совокупность этих зна­ чений (вектор) предъявляется ЛПР вместе с первоначальным решением (соответствующим начальной точке). Далее перед ЛПР ставится вопрос: какое из решений лучше? Если лучше новое решение (назовем его Yi), то делается еще шаг вдоль это­ го же направления и вычисляется решение Y2. Далее Yi и Y2 предъявляются ЛПР. Если Y2 лучше, то делается еще шаг в прежнем направлении, и т.д. Если Yi лучше, чем Y2 , то в точ­ ке Y2 определяется новый градиент (направление) изменения

79

глобальной целевой функции (см. рис. 3.6), и т.д. Процедура заканчивается, если ЛПР признает очередное решение вполне для него удовлетворительным.

Другим наиболее известным методом, принадлежащим к данной группе, является метод Зайонца—Валлениуса [7]. Он представляет собой процедуру сужения множества значений весовых векторов wi. В начале задается вектор весов, имеющий равные компоненты. Далее выясняется значение глобального критерия. Обычно этому значению соответствует в области до­ пустимых значений одна из вершин многоугольника. В смеж­ ных к ней вершинах подсчитываются значения весов критери­ ев, при которых данная вершина могла бы быть оптимальным решением однокритериальной задачи. Также в этих вершинах подсчитываются значения вектора оценок по критериям.

ЛПР попарно предъявляются векторы значений критериев в начальной точке и каждый из векторов значений критериев в смежных вершинах. При этом ЛПР ставит вопрос, какой кри­ териальный вектор предпочтительнее. Возможны три варианта ответа:

1)предпочтительнее смежный критериальный вектор;

2)предпочтительнее начальный критериальный вектор;

3)нет четкого предпочтения.

На основе ответов ЛПР формируются ограничения на зна­ чения весовых коэффициентов критериев. Далее определяется центральная точка в допустимой области весовых коэффициен­ тов, опять вычисляется значение глобального критерия и т.д.

Доказано, что метод сходится к точке, соответствующей наибольшей полезности ЛПР, если априори неизвестная функ­ ция полезности ЛПР является вогнутой.

В отличие от прямых методов мы видим в ЧМП оценки векторов систематический поиск, помогающий ЛПР найти наилучшее решение.

16. Процедуры поиска удовлетворительных значений критериев

Эти процедуры также предназначены для систематического поиска наилучшего решения. Однако такой поиск осуществля­ ется по-иному: в порядке очереди определяется приемлемое значение по каждому из критериев.

80