Тема 6.  Многокритериальные решениея при обънетивныъ моделях .          

Рассмотрим следующую модель задачи ПР:

X- множество альтернатив;
Y- множество исходов;

- множество показателей качества (критериев);

 - детерминистская функция, отображающая множество альтернатив во множество исходов. (R – множество вещественных чисел.).

Таким образом, мы здесь предполагаем, что каждому решению

Соответствует единственный элемент , где

«Качество» или «полезность» исхода y , а тем самым и соответствующего решения x оценивается несколькими ( m) числами в соответствии с зависимостями f_i. Для  определенности будем полагать, что функции f_i-максимизируются. 

С помощью суперпозиции

Мы имеем возможность непосредственно оценивать качество самого решения    x   т. е. считаем, что задано отображение

   В результате мы приходим к очень распространенной в приложениях многокритериальной модели принятия решений, или задаче многокритериальной оптимизации вида

5.  Методы многокритериальной оптимизации.
Пусть рассматривается задача многокритериальной оптимизации

                                      (1)

Вначале рассмотрим традиционные «инженерные» методы многокритериальной оптимизации, сводящие задачу (1) к некоторой ее однокритериальной версии.

Рассматривая  задачу  (1), отметим, что в идеальном случае можно вести поиск такого решения, которое принадлежит пересечению множеств оптимальных решений всех однокритериальных задач. Однако такое пересечение обычно оказывается пустым множеством, поэтому приходится рассматривать так называемое «переговорное» множество эффективных решений (оптимальных по Парето).

Некоторые частные критерии могут противоречить друг другу, другие действуют в одном направлении, третьи – индеферентны, безразличны друг другу.

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

Известен ряд методов решения задач многокритериальной оптимизации. Рассмотрим некоторые из них:

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

учитываются с помошью введения необходимых дополнительных ограничений. Таким образом, вместо задачи (1) решается другая, уже однокритериальная задача вида

Формально получили более простую задачу поиска максимума функционала f_i на новом допустимом множестве D⁰. Добавились ограничения вида  показывающие что мы согласны не добываться максимальных значений для функционалов   сохраняя требование их ограниченности снизу на приемлемых уровнях.

Метод линейной свертки. Он  основан на линейном объединении всех частных целевых функционалов в один:

Весовые коэффициенты a_i могут при этом рассматриваться как показатели относительной значимости отдельных критериальных функционалов f_i.

Метод  максиминной  свертки. Обычно применяется в форме

Здесь, в отличие от метода линейной свертки, на целевой функционал
j(x)  оказывает влияние только тот частный критерий оптимальности, которому в данной точке х соответствует наименьшее значение соответствующей функции f_i. Данный критерий определяет гарантированную нижнюю оценку для всех функционалов f_i(x).

При необходимости нормировки отдельных частных целевых функционалов может быть использована «взвешенная» форма максиминного критерия:

где  весовые коэффициенты a_i удовлетворяют требованиям (2).

Метод последовательных уступок. Он применяется в случае, когда частные критерии могут быть упорядочены в порядке убывания их важности.

Предположим, что все частные критерии максимизируются и пронумерованы в порядке убывания их важности. Находим максимальное значение f₁* первого по важности критерия в области допустимых решений путем решения однокритериальной задачи.

Затем, исходя из практических соображений и принятой точности, назначается величина допустимого отклонения   

(экономически оправданные уступки) критерия f₁ и находится максимальное значение второго критерия f₂* при условии, что значение первого критерия не должно отклоняться от своего максимального значения более чем на величину допустимой уступки, т. е. решается задача:

Снова назначается величина уступки  по второму критерию, которая вместе с первой уступкой используется для нахождения условного максимума третьего частного критерия:

Аналогичные процедуры повторяются до тех пор, пока не будет выявлено максимальное значение последнего по важности критерия f_m.

Рассмотрим следующий пример: для выпуска 2-х видов продукции используются 3 вида ресурсов. Известна матрица норм расхода А, цены Q на ресурсы, цены реализации P продукции и запасы В ресурсов.

На основе исходной информации могут быть определены 2 критерия: прибыли и выручка с двумя переменными  Х₁ – выпуск продукции 1-го вида и Х₂ – выпуск продукции 2-го вида. Тогда задача может быть записана следующим образом:

Графически множество допустимых решений может быть изображено следующим образом:

Значения критериев в угловых точках заданы в таблице:

	А(0;10)	В(10;5)	С(12;3)	D(13;0)
F1	120	230	240	221
F2	50	55	51	39

Окончательный выбор останется за ЛПР.

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

Определение:  Решение задачи (1)  Х*  Q называется эффективным (оптимальным по Парето) решением, если не существует такого другого решения     Х  Q, что  

 f_i (X) >= f_i (X*), i = 1, m, (3)

Причем хотя бы для одного значения i имеет место строгое неравенство.

Определение: Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности (т. е. улучшить хотя бы один из них, не ухудшая остальных), принято называть областью Парето, или областью компромиссов, а принадлежащие ей решения эффективными, или оптимальными по Парето.

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

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

 6.  Методы многокритериального выбора на основе дополнительной информации

Решением многокритериальной задачи, сформулированной выше, является соответствующее множество  Парето- множество недоминируемых по Парето альтернатив. Это множество может оказаться достаточно обширным, а пользователя обычно интересует выбор какого-то «наилучшего» варианта или небольшого их числа. Если какая-либо дополнительная информация  о задаче отсутствует, то множество Парето – это лучшее, что можно предложить. Однако при наличии дополнительной информации о системе предпочтений пользователя могут  быть применены различные методы сужения исходного множества альтернатив – более сильные, чем методы, основанные на доминировании по Парето. Весьма часто исходной информацией для таких методов выступает само множество Парето и ставится задача его сужения с целью выбора одной или нескольких альтернатив в качестве окончательного результата.

Метод t – упорядочения. Пусть решается многокритериальная задача (1). Будем предполагать, что все критериальные функции  f_i отражают «полезность» объекта с позиций различных критериев и являются соизмеримыми в том смысле, что значения каждой критериальной функции изменяются в одних и тех же пределах [a, b]:

                                 (4)

Таким образом, мы предполагаем, что оценочные шкалы критериев являются числовыми и одинаковыми.

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

         (5)

Здесь max f_i , min f_i- максимальные и минимальные значения f_i соответственно. Новые оценочные функции  будут изменяться уже в пределах заданного промежутка [a, b]. Обычно полагают a = 0, b = 1.

Итак, пусть критериальные функции соизмеримы и удовлетворяют условиям (4).

Определение. Нормированные критерии f_i и f_j называются равноценными    ( f_i = f_j), если всякие две векторные оценки Z, W, где

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

Таким образом, если, например, два школьника оцениваются по четырем предметам и имеют оценки (которые необходимо максимизировать)

                      Z = (5,4,4,3), W = (5,5,3,3)

то при условии равноценности  критериев f₂, f₃ приведенные векторные оценки будут одинаковыми по предпочтительности, т.к. 4+4=5+3, а остальные оценки совпадают.

Следовательно, если критерии f_i и f_j равноценны, то можно «забрать»   

единиц у частной оценки z_j и  «передать» их частной оценке z_i. При этом получим векторную оценку, одинаковую с исходной по предпочтительности.

Если в приведенном  выше  примере считать, что оценка Z предпочтительнее, чем W, то естественно предположить, что критерий f₃ важнее критерия f₂. 

Определение.  Критерий f_i более важен, чем критерий f_j (что записывается в виде f_i > f_j), если векторная оценка

менее предпочтительна, чем оценка 

  .

где  и Таким образом, перенос единицы  

с частной оценки z_j на частную оценку z_i приводит к улучшению ситуации, если  f_i >f_j.

На основе выше приведенной операции переноса единиц с одной частной оценки на другую частную оценку происходит сокращение множества Парето решаемой многокритериальной задачи.

Рассмотрим пример.

Путь Z = (1; 0,5; 0,1; 0,2), W = (0,4; 0,9; 0,1; 0,2) 

и пусть утверждается, что критерий f₁важнее, чем f₂: f₁ > f₂. Эти векторные оценки, очевидно, несравнимы по Парето. Рассмотрим оценку

W' = (0,8; 0,5; 0,1; 0,2)

полученную из W с помощью переноса 0,4 единиц со второй позиции в первую. Согласно определению имеем

 И, поскольку имеем

То естественно считать  а, значит
 

Методы упорядочения альтернатив, основанные на рассмотренной процедуре переноса (transfer) c учетом ординальной (порядковой) информации пользователя, называются методами t- упорядочения.

Частным случаем изложенного метода t- упорядочения является метод, предложенный В.В. Подиновским (метод П - упорядочения). Он основан на том, что мы имеем возможность переставлять численные значения оценок между равноценными и неравноценными критериями. Например, пусть дана векторная оценка   Z=(5,10,6) и известно, что  f₁ > f₂. Тогда по Подиковскому оценка
Z'=(10,5,6), полученная из Z перестановкой чисел 5 и 10, будет признана лучшей, чем  Z, т. к. на место более «важного» критерия f₁ пришло большее значение (10 вместо 5). Если бы критерии f₁ и f₂ были равноценными, то оценки Z и Z' считались бы эквивалентными.

Недостатком метода П – упорядочения является его недостаточная «мощность». Например, пусть даны векторные оценки

                     Z=(7,9,6), W=(5,10,6)

 при наличии ординальной информации f₁> f₂. Эти оценки, очевидно, несравнимы по Парето. Несравнимы они и по методу П – упорядочения (никакие перестановки численных значений оценок между f₁ и f₂ не приводят к их сравнимости по Парето). В то же время легко видеть, что согласно методу t- упорядочения для  W'=(6,9,6) полученной из W с помощью переноса одной единицы со второй позиции в первую, мы имеем

и, следовательно,