Информационные технологии решения задач векторной оптимизации (стр. 1 из 4)
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ РЕШЕНИЯ ЗАДАЧ ВЕКТОРНОЙ ОПТИМИЗАЦИИ
План:
Введение
Принцип оптимальности Парето. Неулучшаемые (оптимальные по Парето) решения
Принцип равновесия по Нэшу
Конфликты, переговоры и компромиссы
Краткий обзор методов решения задачи векторной оптимизации
В отличие от задач обоснования решений по скалярному критерию, результатом которых является оптимальная (с точностью до предпосылок и допущений модели) стратегия, в задачах с векторным критерием оказывается невозможно с абсолютной уверенностью утверждать, что то или иное решение, действительно (объективно) оптимально. Одно из решений может превосходить другое по одним критериям и уступать ему по другим. Сказать, какое из двух решений в указанных условиях объективно лучше другого, не представляется возможным. Только со временем будет ясно, сколь верным было принятое решение; пока же, до реализации решения, личные предпочтения ЛПР, его опыт и интуиция являются той основой, которая определяет способность ЛПР предвидеть последствия принятого им компромисса.
Таким образом, сложность проблемы принятия решений по векторному критерию даже в условиях определенности связана не столько с вычислительными трудностями, сколько с концептуальной обоснованностью выбора оптимального решения. Невозможно строго математически доказать, что выбранное решение наилучшее, - любое решение из числа недоминируемых, то есть неулучшаемых одновременно по всем частным критериям, может оказаться наилучшим для конкретного ЛПР в конкретных условиях. С той же точки зрения не имеет смысла говорить о наилучшем решении вообще. Это может считаться аксиомой обоснования решений по нескольким критериям.
Сравнение альтернатив по векторному критерию осуществляются по следующему правилу: всякая альтернатива не хуже любой другой, если для нее значение векторного критерия не менее предпочтительно, чем значение критерия другой альтернативы, то есть:
где
- альтернативы; 
- векторный критерий; 
- символ отношения нестрогого предпочтения.Предположим, что множественность критериев связана с наличием нескольких сторон, заинтересованных в разрешении проблемной ситуации. Каждая сторона стремится найти и принять решение, при котором ее показатель эффективности (целевая функция) был бы наибольшим. Очевидно, величина показателя эффективности каждой стороны зависит от решений всех остальных сторон. Поэтому наиболее эффективные для одной стороны решения не являются таковыми для других. В связи с этим, стремление каждой стороны добиваться наибольшей эффективности принимаемых ею решений носит конфликтный характер и сама формулировка того, какое решение является приемлемым, хорошим или наилучшим (оптимальным), проблематична.
Рассмотрение сложных экономических объектов, характеризующихся целым спектром характеристик, приводит к необходимости введения понятий локального и глобального критериев оптимальности. При этом математически глобальный критерий формулируется в виде скалярной целевой функции, которая обобщенно выражает многообразие целей, или в виде векторной функции, представляющей собой набор несводимых друг к другу частных целевых функций (локальных критериев).
Следует отметить, что множественность целей развития экономических систем существенно усложняет планирование, особенно если цели разнонаправленные, и приближение к одним целям удаляет систему от достижения других. В результате возникает задача их согласования. Целью многокритериальной или векторной оптимизации и является отыскание наилучших решений по нескольким критериям.
Среди множества многокритериальных задач можно выделить задачи четырех типов:
Задачи оптимизации на множестве целей, каждая из которых должна быть учтена при выборе оптимального решения. Примером может служить задача составления плана работы предприятия, в которой критериями служит ряд экономических показателей;
Задачи оптимизации на множестве объектов, качество функционирования каждого из которых оценивается самостоятельным критерием. Если качество функционирования каждого объекта оценивается несколькими критериями (векторным критерием), то такая задача называется многовекторной. Примером может служить задача распределения дефицитного ресурса между несколькими предприятиями. Для каждого предприятия критерием оптимальности является степень удовлетворения его потребности в ресурсе или другой показатель, например, величина прибыли. Для планирующего органа критерием выступает вектор локальных приоритетов предприятий;
Задача оптимизации на множестве условий функционирования. В задачах такого типа задан спектр условий, в которых предстоит работать объекту, и применительно к каждому условию качество функционирования оценивается некоторым частным критерием;
Задачи оптимизации на множестве этапов функционирования. Рассматривается функционирование объектов на некотором интервале времени, разбитом на несколько этапов. Качество управления на каждом этапе оценивается частным критерием, а на множестве этапов – общим векторным критерием. Примером может служить распределение квартального плана цеха по декадам. В каждой декаде необходимо обеспечить максимальную загрузку. В результате получится критерий максимизации загрузки в каждой декаде квартала.
Многокритериальные задачи можно также классифицировать по другим признакам, например, по вариантам оптимизации, по числу или типам критериев, по соотношениям между критериями, по уровню структуризации, наличию фактора неопределенности и т.п.
При разработке методов решения векторных задач приходится решать ряд специфических проблем.
Проблема нормализации возникает в связи с тем, что локальные критерии имеют, как правило, различные единицы и масштабы измерения, и это делает невозможным их непосредственное сравнение. Операция приведения критериев к единому масштабу и безразмерному виду называется нормированием. Наиболее распространенным способом нормирования является замена абсолютных значений критериев их относительными величинами.
Проблема выбора принципа оптимальности связана с определением свойств оптимального решения и решением вопроса – в каком смысле оптимальное решение превосходит все остальные.
Проблема учета приоритета критериев возникает, если локальные критерии имеют различную значимость. Необходимо найти математическое определение приоритета и степень его влияния на решение задачи.
Проблема вычисления оптимума возникает, если традиционные вычислительные схемы и алгоритмы непригодны для решения задачи векторной оптимизации.
Качественная информация об относительной важности критериев чаще всего представляет собой сообщения о том, что какие-то критерии “равноценны” или же “один критерий важнее других”. Такая информация может быть получена в ходе контрольного предъявления ЛПР специально формируемых векторных оценок и выяснения, какие из них он предпочитает при сравнении с другими. При этом предъявляемые ЛПР оценки должны удовлетворять двум специальным требованиям. Во-первых, все частные компоненты таких специальных оценок должны иметь общую шкалу, то есть быть однородными. Во-вторых, в предъявляемых оценках все компоненты, кроме тех, чья относительная важность выясняется, должны быть одинаковыми.
Для того чтобы обеспечить однородность частных критериев, которые, вообще говоря, имеют различные шкалы, в практике часто используют простые приемы эквивалентного преобразования неоднородных частных критериев к единому, безразмерному виду. Используются следующие формулы преобразований (в качестве стандарта выбрано преобразование в шкалу со значениями из отрезка [0;1]:
Если известны эталонные значения показателей
(например, международный стандарт), то используется преобразование следующего вида: 
;Если известны максимально возможные значения показателей, то
;Если известны диапазоны изменения показателей, то
или
.Прежде чем приступить к рассмотрению алгоритмов решения задач векторной оптимизации, имеет смысл кратко остановиться на некоторых фундаментальных понятиях теории принятия решений в контексте многокритериальных задач.
Принцип оптимальности Парето. Неулучшаемые (оптимальные по Парето) решения
Рассмотрим проблемную ситуацию, решения которой оцениваются по некоторой совокупности показателей
(под 
может пониматься, например, целевая функция, описывающая какую-либо характеристику производственного процесса, показатель функционирования предприятия и т.п.). Для наглядности можно представлять, что в выборе решения участвуют 
сторон, каждая из которых заинтересована в максимизации соответствующего (“своего”) показателя. При этом 
-я сторона может выбрать любое допустимое для нее решение 
. Чрезвычайно важно, что решение, выбранное этой стороной, влияет на эффективность всех остальных. Это означает, что показатель эффективности любой стороны зависит от совокупности допустимых решений 
всех сторон, т.е. 
.