Основные понятия и определения. Векторный критерий. Альтернатива

ТЕМА 21. МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ

Векторный критерий. Альтернатива. Локальный критерий оптимальности. Глобальный критерий оптимальности. Оптимизация на множестве целей.

Оптимизация на множестве объектов. Оптимизация на множестве условий функционирования. Оптимизация на множестве этапов функционирования. Нормализация критериев. Приоритет критериев. Принцип оптимальности Парето. Принцип равновесия по Нэшу.

Методы свертывания системы показателей эффективности. Методы, использующие ограничения на критерии. Методы целевого программирования. Методы интерактивного программирования.

21.1 Классификация многокритериальных задач

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

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

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

³ ³,

где - альтернативы; - векторный критерий; ³- символ отношения нестрогого предпочтения.

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

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

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

Можно выделить четыре типа многокритериальных задач.

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

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

· Оптимизация на множестве условий функционирования. Задан спектр условий работы объекта, и применительно к каждому условию качество функционирования оценивается частным критерием (например, “жесткий” или “нормальный” режим работы).

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

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

При решении векторных задач приходится решать ряд специфических проблем.

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

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

Для обеспечения однородности частных критериев обычно используют приемы эквивалентного преобразования неоднородных частных критериев к единому, безразмерному виду, например:

· Если известны эталонные значения показателей (например, международный стандарт), то используется преобразование:

· Если известны максимально возможные значения показателей, то

· Если известны диапазоны изменения показателей, то

или

Кратко рассмотрим некоторые фундаментальные понятия теории принятия решений в контексте многокритериальных задач.

21.2 Принцип оптимальности Парето.

Пусть решения ПС оцениваются по некоторой совокупности показателей (под может пониматься, например, целевая функция, описывающая какую-либо характеристику производственного процесса, показатель функционирования предприятия и т.п.). Для наглядности можно представлять, что в выборе решения участвуют сторон, каждая из которых заинтересована в максимизации соответствующего (“своего”) показателя. При этом -я сторона может выбрать любое допустимое для нее решение . Чрезвычайно важно, что решение, выбранное этой стороной, влияет на эффективность решений всех остальных. Это означает, что показатель эффективности любой стороны зависит от совокупности допустимых решений всех сторон, т.е.

.

Решение стороны предпочтительнее ее решения , если

.

Учитывая наличие сторон, самостоятельно выбирающих свои решения, можно сформулировать принцип оптимальности Парето):

Если для всех сторон допустимые решения предпочтительнее решений , то последние не будут приняты (т.е. будут единогласно отвергнуты).

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

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

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

W2

Рис. 14.1. Формирование оптимальных по Парето решений

Видно, что из всех решений эффективными (недоминируемыми) являются лишь решения . Для всякого другого решения существует хотя бы одно доминирующее, для которого либо W₁, либо W₂, либо оба больше, чем для данного. После того, как выделены эффективные по Парето решения, выбор “наилучшего” производится в пределах этого множества. Например, решение u ₁₁ является наилучшим по критерию W₁, u ₂ – наилучшим по критерию W₂, а остальные два решения характеризуются “хорошим” сочетанием обоих критериев. Выбор - за ЛПР.

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

21.3 Принцип равновесия по Нэшу

Пусть все стороны выбрали решения, оптимальные по Парето (ситуация, оптимальная по Парето). Согласно принципу оптимальности Парето, все стороны, действуя совместно, не могут увеличить эффективность своих решений. Однако любая сторона, уклонившись от ситуации, оптимальной по Парето, при определенных условиях может добиться большего значения “своего” показателя эффективности. Иными словами, ситуации, оптимальные по Парето, не обладают устойчивостью по отношению к отклонениям от них какой-либо стороны. В то же время желательно, чтобы ни одна из сторон, действуя в одиночку, не могла увеличить эффективность выбираемых ею решений. Другими словами, необходим поиск таких ситуаций, отклонение от которых было бы невыгодным ни для одной из сторон по-отдельности.

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

Ситуацию, характеризующуюся набором решений , называют равновесной по Нэшу, если для всех справедливо неравенство

.

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

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

21.4 Обзор методов решения задач векторной оптимизации

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

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

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

· методы, основанные на свертывании системы показателей эффективности;

· методы, использующие ограничения на критерии;

· методы целевого программирования;

· методы, в основе которых лежат человеко-машинные процедуры принятия решений (интерактивное программирование).

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

Приведем краткий обзор методов векторной оптимизации.