ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ РЕШЕНИЯ ЗАДАЧ ВЕКТОРНОЙ ОПТИМИЗАЦИИ
План:
Введение
Принцип оптимальности Парето. Неулучшаемые (оптимальные по Парето) решения
Принцип равновесия по Нэшу
Конфликты, переговоры и компромиссы
Краткий обзор методов решения задачи векторной оптимизации
Введение
В отличие от задач обоснования решений по скалярному критерию, результатом которых является оптимальная (с точностью до предпосылок и допущений модели) стратегия, в задачах с векторным критерием оказывается невозможно с абсолютной уверенностью утверждать, что то или иное решение, действительно (объективно) оптимально. Одно из решений может превосходить другое по одним критериям и уступать ему по другим. Сказать, какое из двух решений в указанных условиях объективно лучше другого, не представляется возможным. Только со временем будет ясно, сколь верным было принятое решение; пока же, до реализации решения, личные предпочтения ЛПР, его опыт и интуиция являются той основой, которая определяет способность ЛПР предвидеть последствия принятого им компромисса.
Таким образом, сложность проблемы принятия решений по векторному критерию даже в условиях определенности связана не столько с вычислительными трудностями, сколько с концептуальной обоснованностью выбора оптимального решения. Невозможно строго математически доказать, что выбранное решение наилучшее, - любое решение из числа недоминируемых, то есть неулучшаемых одновременно по всем частным критериям, может оказаться наилучшим для конкретного ЛПР в конкретных условиях. С той же точки зрения не имеет смысла говорить о наилучшем решении вообще. Это может считаться аксиомой обоснования решений по нескольким критериям.
Сравнение альтернатив по векторному критерию осуществляются по следующему правилу: всякая альтернатива не хуже любой другой, если для нее значение векторного критерия не менее предпочтительно, чем значение критерия другой альтернативы, то есть:
где - альтернативы; - векторный критерий; - символ отношения нестрогого предпочтения.
Предположим, что множественность критериев связана с наличием нескольких сторон, заинтересованных в разрешении проблемной ситуации. Каждая сторона стремится найти и принять решение, при котором ее показатель эффективности (целевая функция) был бы наибольшим. Очевидно, величина показателя эффективности каждой стороны зависит от решений всех остальных сторон. Поэтому наиболее эффективные для одной стороны решения не являются таковыми для других. В связи с этим, стремление каждой стороны добиваться наибольшей эффективности принимаемых ею решений носит конфликтный характер и сама формулировка того, какое решение является приемлемым, хорошим или наилучшим (оптимальным), проблематична.
Рассмотрение сложных экономических объектов, характеризующихся целым спектром характеристик, приводит к необходимости введения понятий локального и глобального критериев оптимальности. При этом математически глобальный критерий формулируется в виде скалярной целевой функции, которая обобщенно выражает многообразие целей, или в виде векторной функции, представляющей собой набор несводимых друг к другу частных целевых функций (локальных критериев).
Следует отметить, что множественность целей развития экономических систем существенно усложняет планирование, особенно если цели разнонаправленные, и приближение к одним целям удаляет систему от достижения других. В результате возникает задача их согласования. Целью многокритериальной или векторной оптимизации и является отыскание наилучших решений по нескольким критериям.
Среди множества многокритериальных задач можно выделить задачи четырех типов:
Задачи оптимизации на множестве целей, каждая из которых должна быть учтена при выборе оптимального решения. Примером может служить задача составления плана работы предприятия, в которой критериями служит ряд экономических показателей;
Задачи оптимизации на множестве объектов, качество функционирования каждого из которых оценивается самостоятельным критерием. Если качество функционирования каждого объекта оценивается несколькими критериями (векторным критерием), то такая задача называется многовекторной. Примером может служить задача распределения дефицитного ресурса между несколькими предприятиями. Для каждого предприятия критерием оптимальности является степень удовлетворения его потребности в ресурсе или другой показатель, например, величина прибыли. Для планирующего органа критерием выступает вектор локальных приоритетов предприятий;
Задача оптимизации на множестве условий функционирования. В задачах такого типа задан спектр условий, в которых предстоит работать объекту, и применительно к каждому условию качество функционирования оценивается некоторым частным критерием;
Задачи оптимизации на множестве этапов функционирования. Рассматривается функционирование объектов на некотором интервале времени, разбитом на несколько этапов. Качество управления на каждом этапе оценивается частным критерием, а на множестве этапов – общим векторным критерием. Примером может служить распределение квартального плана цеха по декадам. В каждой декаде необходимо обеспечить максимальную загрузку. В результате получится критерий максимизации загрузки в каждой декаде квартала.
Многокритериальные задачи можно также классифицировать по другим признакам, например, по вариантам оптимизации, по числу или типам критериев, по соотношениям между критериями, по уровню структуризации, наличию фактора неопределенности и т.п.
При разработке методов решения векторных задач приходится решать ряд специфических проблем.
Проблема нормализации возникает в связи с тем, что локальные критерии имеют, как правило, различные единицы и масштабы измерения, и это делает невозможным их непосредственное сравнение. Операция приведения критериев к единому масштабу и безразмерному виду называется нормированием. Наиболее распространенным способом нормирования является замена абсолютных значений критериев их относительными величинами.
Проблема выбора принципа оптимальности связана с определением свойств оптимального решения и решением вопроса – в каком смысле оптимальное решение превосходит все остальные.
Проблема учета приоритета критериев возникает, если локальные критерии имеют различную значимость. Необходимо найти математическое определение приоритета и степень его влияния на решение задачи.
Проблема вычисления оптимума возникает, если традиционные вычислительные схемы и алгоритмы непригодны для решения задачи векторной оптимизации.
Качественная информация об относительной важности критериев чаще всего представляет собой сообщения о том, что какие-то критерии “равноценны” или же “один критерий важнее других”. Такая информация может быть получена в ходе контрольного предъявления ЛПР специально формируемых векторных оценок и выяснения, какие из них он предпочитает при сравнении с другими. При этом предъявляемые ЛПР оценки должны удовлетворять двум специальным требованиям. Во-первых, все частные компоненты таких специальных оценок должны иметь общую шкалу, то есть быть однородными. Во-вторых, в предъявляемых оценках все компоненты, кроме тех, чья относительная важность выясняется, должны быть одинаковыми.
Для того чтобы обеспечить однородность частных критериев, которые, вообще говоря, имеют различные шкалы, в практике часто используют простые приемы эквивалентного преобразования неоднородных частных критериев к единому, безразмерному виду. Используются следующие формулы преобразований (в качестве стандарта выбрано преобразование в шкалу со значениями из отрезка [0;1]:
Если известны эталонные значения показателей (например, международный стандарт), то используется преобразование следующего вида:
;
Если известны максимально возможные значения показателей, то
;
Если известны диапазоны изменения показателей, то
или .
Прежде чем приступить к рассмотрению алгоритмов решения задач векторной оптимизации, имеет смысл кратко остановиться на некоторых фундаментальных понятиях теории принятия решений в контексте многокритериальных задач.
Принцип оптимальности Парето. Неулучшаемые (оптимальные по Парето) решения
Рассмотрим проблемную ситуацию, решения которой оцениваются по некоторой совокупности показателей (под может пониматься, например, целевая функция, описывающая какую-либо характеристику производственного процесса, показатель функционирования предприятия и т.п.). Для наглядности можно представлять, что в выборе решения участвуют сторон, каждая из которых заинтересована в максимизации соответствующего (“своего”) показателя. При этом -я сторона может выбрать любое допустимое для нее решение . Чрезвычайно важно, что решение, выбранное этой стороной, влияет на эффективность всех остальных. Это означает, что показатель эффективности любой стороны зависит от совокупности допустимых решений всех сторон, т.е. .
Решение стороны предпочтительнее ее решения , если:
.
На основании вышесказанного (учитывая наличие сторон, самостоятельно выбирающих свои решения), можно сформулировать принцип единогласия, известный как принцип оптимальности Парето):
Если для всех сторон допустимые решения предпочтительнее решений , то последние не будут приняты (единогласно отвергнуты).
Как правило, на практике совокупность решений оказывается неединственной и образует некоторое множество решений, оптимальных по Парето. Любой набор решений из этого множества не может быть улучшен сразу по всем показателям . В силу этого решения, оптимальные по Парето, называются также неулучшаемыми. Следует отметить, что задачи, в которых имеется единственная совокупность неулучшаемых решений, встречаются исключительно редко. Любое решение из множества является неулучшаемым. Изменением этого решения невозможно добиться увеличения какого-либо показателя эффективности, не уменьшая при этом хотя бы одного из остальных. Выбор конкретного решения из множества оптимальных по Парето может быть осуществлен лишь на основе компромисса на основе переговоров ЛПР всех заинтересованных сторон.
Хотя до сих пор мы считали, что в выборе решения участвуют различных сторон, рассмотренные понятия и вся формулировка в целом совершенно аналогичны и в том случае, когда выбор решения осуществляет одна сторона, руководствующаяся не единственным, а некоторой совокупностью показателей эффективности. Принятие какого-либо конкретного решения из множества Парето является при этом прерогативой исключительно ЛПР и осуществляется, как правило, на основе его субъективных предпочтений.
Принцип равновесия по Нэшу
Пусть все стороны выбрали решения, оптимальные по Парето (назовем эту ситуацию оптимальной по Парето). Согласно принципу оптимальности Парето, все стороны, действуя совместно, не могут увеличить эффективность своих решений. Однако любая сторона, уклонившись от ситуации, оптимальной по Парето, при определенных условиях может добиться большего значения “своего” показателя эффективности. Иными словами, ситуации, оптимальные по Парето, не обладают устойчивостью по отношению к отклонениям от них какой-либо стороны. В то же время желательно, чтобы ни одна из сторон, действуя в одиночку, не могла увеличить эффективность выбираемых ею решений. Другими словами, необходим поиск таких ситуаций, отклонение от которых было бы невыгодным ни для одной из сторон по отдельности.
Существование ситуаций, являющихся устойчивыми в смысле невыгодности отклонения от них ни одной из сторон, приводит к принципу равновесия по Нэшу.
Ситуацию, характеризующуюся набором решений , называют равновесной по Нэшу, если для всех имеет место неравенство:
.
Если прочитать эти неравенства справа налево, то можно видеть, что замена какого-либо одного решения, входящего в равновесную ситуацию, любым другим из множества допустимых, уменьшает соответствующий показатель эффективности. Если под понимать показатели эффективности сторон, то из определения ситуации равновесия по Нэшу следует, что ни одна из них не заинтересована в изменении решения входящего в ситуацию равновесия, если все остальные стороны сохраняют решения, соответствующие этой ситуации.
Таким образом, если стороны предварительно договариваются о выборе решений, образующих равновесную ситуацию, то индивидуальное нарушение этого договора невыгодно нарушителю. Отметим некоторые особенности равновесных ситуаций:
Ситуация равновесия может оказаться не единственной.
Ситуации равновесия часто оказываются в разной степени предпочтительными для различных сторон. Иначе говоря, показатели эффективности решений сторон имеют неодинаковые значения в различных равновесных ситуациях. В связи с этим какая-то равновесная ситуация, выгодная для одной стороны, может оказываться невыгодной для других. Поэтому решение -й стороны, соответствующее какой-либо равновесной ситуации, не следует трактовать как оптимальное для этой стороны. Равновесность как принцип оптимальности имеет смысл только для набора равновесных решений всех сторон.
Ситуации равновесия могут совпадать или не совпадать с ситуациями оптимальными по Парето.
Конфликты, переговоры и компромиссы
Решения сторон (участников конфликтной ситуации) могут быть выгодными для всех (решения, оптимальные по Парето), но неустойчивыми, или устойчивыми (равновесными по Нэшу), но не обязательно наилучшими, характеризующимися наибольшими значениями показателей эффективности. При этом неустойчивость ситуаций, оптимальных по Парето, означает, что выход из этой ситуации любого из участников может оказаться выгодным для него. Устойчивость равновесной по Нэшу ситуации означает, что индивидуальный (в одиночку) выход и
Ситуации, оптимальные по Парето, эквивалентны для всей совокупности участников конфликта. Поэтому выбор какой-то одной ситуации из множества оптимальных по Парето должен осуществляться путем проведения соответствующих переговоров между сторонами и представляет собой компромиссное решение этих сторон. Но и о выборе решений, соответствующих тем или иным равновесным ситуациям, стороны должны предварительно договориться, так как эффективность этих решений неодинакова для различных сторон.
Таким образом, переговорный процесс, направленный на выработку компромиссных соглашений, является существенным фактором разрешения конфликтных ситуаций. В ходе переговоров могут определяться не только решения, но и процедуры, правила поведения, позволяющие отыскать решения, приемлемые для всех сторон.
Для обеспечения устойчивости ситуаций может применяться, например, образование коалиций, что обусловлено следующим. При выработке соглашения между сторонами о выборе решений, соответствующих равновесию по Нэшу, учитывается позиция каждой стороны. В отличие от этого Парето-оптимальные решения определяются общим интересом всех сторон. Естественно, возможны промежуточные случаи, когда несколько сторон объединяются в одну коалицию. При этом коалиционные результаты оказываются лучшими, чем индивидуальные (иначе образование коалиций не имело бы смысла). Число образуемых в некоторых случаях коалиций может оказываться достаточно большим.
Эффективным способом обеспечения устойчивых Парето-оптимальных соглашений является выработка специальных процедур ведения переговоров по выбору решений, базирующихся на расширении взаимной информированности сторон об их решениях и намерениях.
Помимо расширения информированности сторон имеются и другие пути стабилизации возможных исходов, определяемые конкретными особенностями конфликтных ситуаций. Однако наличие множества неравнозначных для различных сторон вариантов затрудняет поиск компромисса, так как каждая сторона стремится отстаивать наиболее выгодный для себя вариант. В связи с этим возникают новые проблемы, требующие решения. В качестве примера можно привести борьбу “за первый ход”. Не исключена также возможность дезинформирующих действий участников переговоров, а также опасность срыва переговорного процесса и т.д.
Краткий обзор методов решения задачи векторной оптимизации
Решение задачи векторной оптимизации представляет собой сложный процесс, в ходе которого могут применяться различные расчетные схемы и алгоритмы. Перечислим некоторые из наиболее употребительных:
Методы, основанные на свертывании системы показателей эффективности;
Методы, использующие ограничения на критерии;
Методы целевого программирования;
Методы, основанные на отыскании компромиссного решения;
Методы, в основе которых лежат человеко-машинные процедуры принятия решений (интерактивное программирование).
Для ряда из вышеперечисленных методов вводится понятие функции предпочтения (полезности). С помощью функции предпочтения проблема сравнения совокупности чисел-значений, принимаемых показателями эффективности, сводится к сравнению чисел-значений, принимаемых функцией предпочтения. При этом ЛПР считает, что один набор значений локальных критериев предпочтительнее другого, если ему соответствует большее значение функции предпочтения. Кратко охарактеризуем упомянутые методы векторной оптимизации.
А. В методах, основанных на свертывании системы показателей эффективности, из локальных критериев формируется один. Наиболее распространенным является метод линейной комбинации локальных (частных) критериев.
Пусть рассматриваемая экономическая система характеризуется набором локальных критериев (целевых функций) и известен вектор весовых коэффициентов (вектор приоритетов) критериев , характеризующий важности соответствующих критериев, причем:
.
В этом случае функция предпочтения выбирается в виде:
(5.1)
и задача векторной оптимизации сводится к задаче скалярной оптимизации, рассмотренной ранее. При решении данной задачи учитывается система функций-ограничений для каждой из целевых функций . К недостаткам данного метода можно отнести то, что решение, оптимизирующее функцию предпочтения, может оказаться неудовлетворительным по одному или сразу нескольким частным показателям. Это объясняется тем, что при достижении максимума функции предпочтения недопустимо малые значения некоторых показателей компенсируются большими значениями остальных.
К этой же группе методов относятся методы, в которых используется среднестепенная функция предпочтения вида:
,
где параметр .
оптимальность парето векторный многокритериальный
Б. Методы, использующие ограничения на критерии, включают два подхода: метод ведущего критерия и метод последовательных уступок.
В методе ведущего критерия все целевые функции, кроме одной, переводятся в разряд ограничений. Пусть - вектор, компоненты которого представляют собой нижние границы соответствующих критериев. Тогда задача записывается в виде:
где - исходная система функций-ограничений. Метод ведущего критерия применяется в таких задачах, как минимизация полных затрат при условии выполнения плана по производству различных видов продукции, максимизация выпуска комплектных наборов при ограничении на потребляемые ресурсы и ряда других.
Алгоритм метода последовательных уступок состоит в следующем:
Критерии нумеруются в порядке убывания важности;
Определяется оптимальное значение наиболее важного критерия . Лицом, принимающим решение, устанавливается величина уступки по этому критерию;
Решается задача по критерию с дополнительным ограничением ;
Пункты 2 и 3 повторяются последовательно для критериев .
В. При решении задач методами целевого программирования предполагается приближение значения каждого критерия к определенной величине , т.е. достижение определенной цели. В самом общем виде задача целевого программирования может быть сформулирована как минимизация сумм отклонений целевых функций (критериев) от целевых значений с нормированными весами :
, (5.2)
где - вектор целевых значений,- расстояние (мера отклонения) между и , . Часто (например, в случае линейного целевого программирования) полагают . Следует отметить, что точка , как правило, не принадлежит области допустимых значений, в связи с чем, ее иногда называют идеальной или утопической точкой.
Г. В методах, основанных на отыскании компромиссного решения, используется принцип гарантированного результата. Задача может быть сформулирована следующим образом:
.(5.3)
Данным методом могут решаться задачи с заданными приоритетами критериев и многовекторные задачи.
Д. В методах основанных на человеко-машинных процедурах (методы интерактивного программирования) решение задачи происходит в интерактивном режиме. ЛПР оценивает полученное решение и вносит или изменяет заранее заданные коэффициенты или уступки по критериям, а также определяет направление оптимизации. Эта информация служит для постановки новой задачи оптимизации и получения промежуточного решения. Диалог продолжается до тех пор, пока решение не будет удовлетворять требованиям ЛПР. Основным достоинством данного метода является использование знаний и интуиции ЛПР, глубоко понимающего смысл задачи и способного правильно корректировать промежуточные результаты в нужном направлении.
Отметим еще один важный метод агрегирования целевой функции. В некоторых случаях, когда одни частные критерии желательно увеличивать, а другие – уменьшать, может быть использована функция агрегирования в виде отношения одних критериев к другим. При этом первая группа критериев отождествляется с целевым эффектом, а другая – с затратами на его достижение. Результатом агрегирования в этом случае выступает удельная эффективность:
,
где - прибыль (полезный эффект), - затраты. Этот метод часто называют методом “затраты – эффект”.
Перейдем к рассмотрению информационных технологий решения ряда задач векторной оптимизации. В процессе рассмотрения мы ограничимся наиболее широко используемыми методами. Для решения задач будем использовать процессор электронных таблиц Excel, способный достаточно просто и эффективно решать задачи подобного рода.
Пример 1.
Свертывание системы показателей эффективности.
Рассмотрим следующую задачу векторной оптимизации:
,
где целевые функции и соответствующие им ограничения имеют вид:
Решим задачу в Excel и проанализируем зависимость получаемого решения от значения коэффициентов .
Внесем данные на рабочий лист в соответствии с Рис. 5.1. Под значения переменных отведем ячейки A16:C16. В ячейки A6:A8 и A10:A12 введем формулы, определяющие ограничения на значения переменных, в ячейки E16 и G16 – формулы для расчета соответствующих целевых функций, в ячейку F20 – формулу для расчета функции .
Чрезвычайно важным является использование в данном методе общей для всех функций системы ограничений.
Рис. 1. Данные для решения примера 1
Вызовем Поиск решения и зададим область изменения переменных, целевую ячейку и систему ограничений стандартным образом. В результате получим ответ: (для данных значений параметров (см. Рис. 1)) Полагая значения параметров равными, например, получим другое оптимальное значение исследуемой функции Таким образом, можно сделать вывод о весьма существенной чувствительности значений данной оптимизируемой функции к вариациям весовых коэффициентов.
Пример 2.
Ограничения на критерии. Метод последовательных уступок.
Ограничимся для простоты задачей линейной оптимизации (линейного программирования).
Пусть необходимо решить задачу векторной оптимизации следующего вида:
при ограничениях:
методом последовательных уступок, если уступка по первому критерию составляет 10% от его оптимального значения.
Решение
. Решим задачу по критерию , в результате чего получим . В соответствии с условием задачи величина уступки . Дополнительное ограничение будет иметь вид: , т.е. . Решая задачу
получим
.
Проведем решение задачи с помощью Excel. Введем данные на рабочий лист в соответствии с Рис.2.
Отведем под значения переменных ячейки A19 и B19, введем формулы, определяющие ограничения исходной задачи, в ячейки A13:A15; формулу для целевой функции в ячейку E19, а формулу для расчета в ячейку H19. Поиск решения дает значение . Далее, копируем значение из ячейки E19 в ячейку С26 (используется специальная вставка – только значение). Затем отводим под целевую ячейку E26, вводим в нее формулу для расчета , а в ячейку A26 вводим формулу =A19+3*B19, представляющую собой дополнительное ограничение задачи.
При вторичном запуске Поиска решения наряду с уже введенными на первом этапе ограничениями вводим еще одно дополнительное ограничение A26>=144.
В результате расчета получим ответ:
.
Рис. 2. Данные для решения задачи оптимизации по методу последовательных уступок
Пример 3.
Целевое программирование.
Провести оптимизацию вектор – функции
при ограничениях:
Рис. 3. Данные для решения примера 3
Решение. Введем данные на рабочий лист в соответствии с Рис.3.
Отведем под значения переменных ячейки A20 и B20; введем формулы, определяющие ограничения задачи, в ячейки A16:A17; формулы для расчета функций в ячейки E20, G20 и I20, а формулу для расчета - в ячейку C28. Поскольку наши функции нелинейны, в окне диалога Параметры поиска решения необходимо снять флажок (указатель) линейная модель.
Далее последовательно проводим поиск оптимальных (максимальных) значений функций (целевыми ячейками выбираем E20, G20 и I20); после нахождения оптимальных значений каждой из функций ее максимальное значение заносим (используя специальную вставку) в ячейки E24, G24 и I24 соответственно. Таким образом, в ячейках окажутся значения: 1.0748 (E24), 0.7357 (G24), 2 (I24).
После этого переходим к заключительному этапу. Оптимизируем (минимизируем) значение целевой функции (целевая ячейка С28). Поиск решения дает для оптимального значения целевой функции значение 0,32534. При этом в ячейках E20, G20 и I20 окажутся значения функций , соответствующие значениям , при которых отклонение от будет минимальным.
Таким образом, при данных значениях весовых коэффициентов мы получаем следующие оптимальные (с точки зрения достижения оптимального значения “совокупной” функции ) значения компонент вектор функции:
| 1,0748 | 0,7815 | 0,7358 | 0,3609 | 2 | 1,6784 |
Из вышеприведенной таблицы видно, что в результате оптимизации значения всех трех функций-составляющих уменьшились. Естественно, при использовании других весовых коэффициентов мы получили бы другие значения (но при любых значениях весовых коэффициентов тенденция уменьшения всех компонент вектор-функции сохраняется).
Следует отметить, что задача целевого программирования может формулироваться несколько иным образом. ЛПР может просто указать, исходя из своих соображений, желательные с его точки зрения, значения , или диапазоны, в которых эти значения должны быть локализованы. При этой постановке задача решается практически аналогично, с тем отличием, что поиск оптимальных значений компонент (первая часть решения) не проводится, а их значения (или диапазоны изменения) вводятся в качестве ограничений дополнительно к исходным ограничениям задачи.