Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Учебное пособие

Теория принятия решений

В.М. Горбунов

ТОМСК -2010

Введение

История -- утомительная прогулка от Адама до атома"

Леонард Луис Левинсон, американский писатель

Говорят, самое сложное - это сделать правильный выбор.

(Из газет)

На протяжении всей истории люди при необходимости принимать решения прибегали к сложным ритуалам. Они устраивали торжественные церемонии, приносили в жертву животных, гадали по звёздам и следили за полётом птиц. Они полагались на народные приметы и старались следовать примитивным правилам, облегчающим им трудную задачу принятия решений. В настоящее время для принятия решения используют новый и, по-видимому, более научный "ритуал", основанный на применении ЭВМ [c. 8, Д. Химмельблау. Прикладное нелинейное программирование. - М.: Мир, 1974. 534 с.].

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

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

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

Методы поиска оптимальных решений рассматривают в разделах классической математики, связанных с изучением экстремумов функций, в математическом программировании. Решением этих задач является математический объект, основным свойством которого является то, что он доставляет экстремум заданной функции или функционалу. Как правило, оценка решения производится по одному аспекту или критерию. На практике решение нужно оценить с различных сторон, учитывая физические (габариты, вес), экономические (стоимость, ресурсоёмкость), технические (реализуемые функции) и другие критерии. Всё это требует построения модели оптимизации решений одновременно по нескольким критериям. Такие модели разрабатывают в теории выбора и принятия решений. Здесь при постановке задачи уже недостаточно построить оптимизируемые функционалы. Требуется ввести принцип оптимальности, который определяет понятие оптимального решения. Поскольку оптимальность решения даже в одной и той же ситуации может пониматься по-разному, вид принципа оптимальности в моделях принятия решений заранее не фиксируют. Именно в этом состоят основные особенности задач принятия решений.

Основные характеристики задач оптимизации, выбора и принятия решений.

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

На предприятии освободилась должность главного инженера. Задача директора - назначить главного инженера.

В 2008 году Ю.П. Похолков (ректор ТПУ) ушел в отставку. Задача - выбор нового ректора.

Строительному тресту поручено выполнить комплекс работ. Задача управляющего трестом - распределить работы по строительным управлениям.

Транспортному агентству необходимо перевести заданный объём грузов. Задача диспетчера - определить маршрут перевозок.

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

Множество вариантов и принцип оптимальности (функция выбора) позволяют ввести следующие понятия.

Опр. Задачей принятия решений назовём пару <X, ОП>, где X - множество вариантов, ОП - принцип оптимальности, дающий представление о качестве вариантов, в простейшем случае правило предпочтения вариантов;

Решением задачи <X, ОП> является множество Xоп X, полученное с помощью принципа оптимальности ОП.

Понятие "оптимальность" описывается функцией выбора (ФВ). ФВ - это правило, которое каждому допустимому набору вариантов (решений) ставит в соответствие его поднабор наилучших, или оптимальных вариантов, т.е. ФВ есть формальный (т.е. строго определённый) объект, отражающий весьма неформальную вещь: представление человека об оптимальности. Поэтому в ТПР говорят, например: "Принцип оптимальности выражается ФВ, определяемой близостью к "идеальной" точке"; "Принцип оптимальности выражается бинарным отношением специального вида"; "Принцип оптимальности задаётся условием: x лучше y, если x>y, и набору подлежат варианты с максимальным значением".

Задачи принятия решений различают в зависимости от имеющейся информации о множестве X и принципе оптимальности ОП.

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

Задачу, где X и ОП могут быть неизвестными, называют общей задачей принятия решений. Данные для получения Xоп определяют в этой задаче в процессе решения

Задачу с известным X называют задачей выбора.

Задачу с известными X и ОП - общей задачей оптимизации.

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

Задачу принятия решения решают следующим образом. Составляют множество X, если это возможно, т.е. определяют варианты, а затем решают задачу выбора. Отметим, что задача построения X в общем случае является задачей выбора. Следовательно, общую задачу принятия решений можно свести к решению последовательных задач выбора. В принятии решения в общем случае участвует ЭВМ; лицо, принимающее решение (ЛПР); эксперт и консультант (см. далее стр. 7).

Языки описания выбора

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

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

Summary. The language of choice functions is very general and can potentially describe any type of choice. However, its theory is only beginning to be developed and is still occupied with describing old situations in new terms [Перегудов, Тарасенко].

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

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

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

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

Зам. В САПР встречаются все три вида перечисленных задач. Нужно построить трассу, соединяющую два элемента на плате. Возможные различные пути соединения будут вариантами. Пользователь в соответствии с алгоритмом учитывает длину, стоимость, число изгибов, число пересечений. Значение длины трассы можно выразить числом. Длину считать критерием оптимальности (критерий (греческий) - отличительный признак, мерило).

В процессе решения задачи принятия решений участвуют следующие лица: лицо, принимающее решение; эксперты; консультанты.

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

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

Помощь экспертов неоценима: каждый военачальник имеет штаб; ректор вуза или директор НИИ - учёный совет; министр - коллегию; в отдельных случаях образуют разовую группу экспертов для рассмотрения конкретной ситуации (см. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: Учеб. 2 - е изд., доп. - Томск: Изд-во НТЛ. 1997. - 396 с., стр. 263).

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

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

Замечание. В инженерной практике в задачу выбора включают большее количество параметров. Например, некоторые включают семь параметров

Классификация задач выбора

Классификацию проводят по следующим признакам:

1. Вид отображения F детерминированное, вероятностное или неопределённое, что позволяет выделить соответственно:

задачи ПР в условиях определенности (детерминированные) Уточним задачи ПР в пункте 1. В условиях определённости, существует детерминированное отображение множества альтернатив (решений) во множество их критериальных оценок. Имеет место тогда, когда для каждой альтернативы можно указать соответствующее ей точное значение любого критерия.;

задачи ПР в условиях риска (вероятностная неопределённость);

задачи ПР в условиях неопределённости.

2. Мощность множества критериев - одноэлементное или состоящее из нескольких критериев:

задачи ПР со скалярным критерием (однокритериальная задача);

задачи ПР с векторным критерием (многокритериальные задачи).

3. Тип системы - отображает предпочтения одного лица или коллектива, поэтому

задачи индивидуального ПР;

задачи группового ПР. (Ларичев. Диалоговые системы принятия решений).

Уточним задачи ПР в пункте 1. В условиях определённости, существует детерминированное отображение множества альтернатив (решений) во множество их критериальных оценок. Имеет место тогда, когда для каждой альтернативы можно указать соответствующее ей точное значение любого критерия.

Человеко-машинные системы и выбор

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

Как бы ни понималась сложность, простота понимается одинаково: простым является случай, когда посторонняя помощь не требуется. В сложных случаях, особенно если принимающий решение сталкивается со сложностью в отягчающих условиях дефицита времени или других экстремальных обстоятельств, ему требуется квалифицированная помощь в оценке возможных альтернатив. Как было сказано выше - помощь экспертов неоценима. Однако существуют естественные пределы человеческих способностей при восприятии и обработке информации. Работу экспертов лимитируют не только межличностные отношения, но и внутренние психологические и физиологические причины. Оказывается, человек одновременно может оперировать лишь с небольшим числом операндов (понятий, идей, моделей, альтернатив и т.д.) - психологи, говоря о пределе возможностей, иногда называют это законом "семь плюс - минус два". Кроме того, столкнувшись, например, с многокритериальной задачей, эксперт часто проявляет непостоянство, неуверенность нелогичность, стремление к резкому упрощению задачи. Наконец, в ряде случаев играет роль и низкое быстродействие нервной и мышечной системы человека.

Во всех этих отношениях возможности ЭВМ превосходят способности человека, и возникает простая, но очень плодотворная идея создания системы, которая объединила бы достоинства человека и машины и компенсировала их недостатки.

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

Пакеты прикладных программ для выбора.

К первому относятся программы и пакеты программ для решения конкретных хорошо определённых задач выбора. Примером может служить математическое обеспечение ЭВМ для статистической обработки данных (т.е. выбора в условиях стохастической неопределённости).

Базы знаний и экспертные системы

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

Экспертные системы имеют широкие перспективы: известны их многочисленные практические реализации в разнообразных предметных областях. Некоторые важные принципы организации экспертных систем, учитывающие расплывчатость терминов естественного языка, были заложены Д.А. Поспеловым ещё в системах ситуационного управления.

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

Системы поддержки решений

Это третье направление представлено системами "интерактивной оценки решений" и особенно "системами поддержки решений" (DSS - Decision Support Systems).

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

Некоторые определения и понятия.

Принятие решения представляет собой выбор одного из некоторого множества рассматриваемых вариантов [Э. Мишук. Методы принятия технических решений].

Оптимальные варианты в некотором наборе называются выбором [Многокритериальная оптимизация. Б. Березовский].

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

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

Тема Многокритериальные задачи оптимизации

векторный коэффициент экспертный аналитический

Общие сведения о многокритериальных задачах оптимизации.

До сих пор мы рассматривали задачи оптимизации, где ясен критерий (показатель эффективности) по которому проводится оценка эффективности проектируемого объекта, т.е. требуется обратить в min (max) один единственный показатель. К сожалению, такие задачи на практике встречаются редко. Когда идёт речь о проектировании таких объектов как самолёт, технологический процесс, то их эффективность, как правило, не может быть полностью оценена с помощью единственного показателя. Приходится рассматривать дополнительные критерии (показатели эффективности). Чем больше критериев качества вводится в рассмотрение, тем более полную характеристику достоинств и недостатков проектируемого объекта можно получить. Таким образом, задачи проектирования сложных систем всегда многокритериальны, так как при выборе наилучшего варианта приходится учитывать много различных требований, предъявленных к системе (объекту). Например, при проектировании самолёта учитывают следующие показатели: скорость, радиус действия, боевой потолок, полезная нагрузка.

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

Прежде чем сформулировать задачу векторной оптимизации (ЗВО) введём и рассмотрим некоторые понятия.

Математическая модель объекта проектирования

При решении задач следует основное внимание обратить на предварительный этап - составление математической модели (ММ) и на заключительном этапе - всесторонний анализ полученного оптимального решения.

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

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

Опр. 1. Приближённое описание объекта, выраженное с помощью математической символики, называют математической моделью.

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

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

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

Опр. 3. Параметры элементов объекта называют внутренними параметрами, величины. Следовательно, внутренние параметры характеризуют свойства элементов проектируемого объекта (проектные параметры).

Опр.4. Те внутренние параметры, которые являются независимыми друг от друга и могут изменяться в некоторых пределах, называются управляемыми параметрами (независимыми).

Опр.5. Параметры, характеризующие свойства объекта, называют выходными параметрами.

Опр.6. Параметры, характеризующие свойства внешней по отношению к рассматриваемому объекту среды, называют внешними параметрами.

Например, для блока электронно-вычислительной аппаратуры (ЭВА) выходными параметрами будут быстродействие, объём внутренней памяти; внутренними параметрами могут быть параметры транзисторов, ёмкости конденсаторов, тепловые характеристики элементов; внешними параметрами будут радиационное излучение, температура окружающей среды, давление, влажность, напряжение источников питания и т.п.

Функционирование любой проектируемой технической системы подчиняется определённым физическим законам. Закон функционирования технической системы описывается аналитическим выражением между входными, внутренними и выходными переменными системы. Эти переменные связаны определёнными соотношениями с переменными проектирования X, под которыми понимаются внутренние переменные, допускающие варьирование (изменение). В процессе определения наилучших значений параметров (параметрического синтеза) изменение переменных X ведёт к изменению выходных параметров Y системы.

Введём обозначения

X=(x1, x2, . . . , xn) - вектор управляемых параметров;

Y=(y1, y2, . . . , ym) - вектор выходных параметров;

Q=(q1, q2, …,ql) - вектор внешних параметров;

т.к. Y есть функция от X и Q, то в явном виде она имеет следующий вид

Y=F(X, Q) - аналитическая модель объекта (1)

Следовательно, y1=F1(X,Q), y2=F2(X, Q), . . . , ym=Fm(X,Q).

Опр. 7. Если математическое описание проектируемого объекта не содержит элементов случайности, то математическая модель называется детерминированной.

Опр. 8. Математические модели, в которых учитываются случайные факторы, называются вероятностными (стохастическими).

Таким образом, выражение "задана математическая модель" означает, что имеются формулы (или готовые программы (алгоритмы)), позволяющие по заданному набору (x1, x2, . . . , xn) вычислить любые интересующие нас характеристики системы (y1, y2, . . . , ym).

Опр. 9. Пространством параметров называется n - мерное пространство, состоящее из точек с декартовыми координатами (x1, x2, . . . , xn). Обычно X входит в дифференциальные или другие уравнения, описывающие функционирование системы.

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

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

(2)

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

hk(X)=0, k=1,2, . . . , K; ограничения равенства (3)

gj(X)0, j= 1,2, . . . , J. ограничения неравенства (4)

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

Очевидно, ограничения (2) выделяют в n - мерном пространстве параметров параллелепипед П. Ограничения (3) и (4) выделяют в параллелепипеде П некоторое подмножество D. Динамика определение допустимого множества решений и критериального пространства показана на рис. 1. Рассмотрен двумерный случай.

Рис 1. а. Область работоспособности



Рис. 1. б. Область работоспособности D Критериальное пространство YD

Опр. 10. Множество D - допустимая область (область работоспособности) - это множество векторов X, для которых одновременно выполняются условия (2), (3) и (4).

Отметим, что условия работоспособности важны при проектировании, т.к. задача проектирования формулируется следующим образом:

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

Опр. 11. Множество D называют множеством решений (альтернатив, вариантов, планов, стратегий).

Определение множества D - одна из первостепенных проблем оптимального проектирования. Кто поручится, что даже талантливый и опытный конструктор при малом числе вариантов, не имея этого множества, сможет найти оптимальное решение? А ведь речь идёт о современных машинах, приборах и конструкциях, которые тиражируются миллионами штук. Следовательно, чтобы создать конкурентоспособные машины, необходимо уметь строить допустимое множество вариантов проекта. В этом множестве имеется подмножество неулучшаемых или так называемых парето-оптимальных решений, т.е. таких, которые нельзя одновременно улучшить по всем оптимизируемым критериям качества не ухудшив при этом значения хотя бы одного из этих критериев. Очевидно, вариант проекта, по которому будет изготавливаться серийная машина, обязательно должен быть парето-оптимальным.

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

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

Пример ограничений в других областях. Утилизация автомобилей. "Ограничений только три: нужно, чтобы автомобиль был в собственности не менее года, кроме того, не удастся спихнуть битые или аварийные авто. И последнее - субсидию можно потратить только на новую машину, выпущенную в России". [Статья "Кто снимет сливки", АН, №192, четверг 21 января 2010 года]

В многокритериальных задачах оптимизации (МЗО) сравнение решений осуществляется при помощи задания на множестве управляемых параметров функций y1=F1(X), y2=F2(X), . . . , ym=Fm(X), называемых критериями. Показатель качества принято называть критерием оптимальности.

Опр. 12. Критерием называется характеристика системы (объекта) заданная функцией f(X), которая связана с её качеством монотонной зависимостью и обладает тем свойством, что если альтернатива X1 предпочтительнее альтернативы X2, то f(X1)<f(X2) и обратно.

Стремление оперирующей стороны к достижению цели описывается стремлением к увеличению (уменьшению) функций F1(X), F2(X), . . . , Fm(X), называемых критериями эффективности.

Встречаются также названия: показатели качества, эффективности, критериальные функции, функции предпочтения, функция полезности, целевые функции, частные критерии или локальные критерии.

Если оптимизация ведётся без учёта статистического разброса характеристик, то соответствующий критерий оптимальности называют детерминированным критерием, если разброс параметров учитывается, то имеем критерий статистический. Статистические критерии оптимальности более полно отражают представление о качестве объектов проектирования, однако их использование, как правило, при автоматизированном проектировании ведёт к значительному увеличению затрат машинного времени [Корячко В.П. и др. Теоретические основы САПР: Учебник для вузов/В.П. Корячко, В.М. Курейчик, И.П. Норенков. - М.: Энергоатомиздат, 1987. - 400 с.: ил.].

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

Предполагается, что m2, при m=1 задача оптимизации является однокритериальной (скалярной).

Опр. 13. Задачи оптимизации, в которых имеется не одна, а несколько целевых функций (критериев), получили название многокритериальных задач оптимизации.

Критерии Fi(X), i=1,2, . . . , m, образуют векторный критерий F(X)=(F1, F2, . . . , Fm). Поэтому в литературе также используют термин "векторная оптимизация".

Пусть X1D, тогда

F1(X1) - локальная оценка решения X1 по 1 - му критерию или критерию F1;

F2(X1) - локальная оценка решения X1 по 2 - му критерию или критерию F2;

Fm(X1) - локальная оценка решения X1 по m - му критерию или критерию Fm;

F(X1)=(F1(X1), F2(X1), Fm(X1)) - векторная оценка для решения X1.

Для пояснения сущности задач используют геометрическую интерпретацию, связанную с введением n - мерного пространства En пространства параметров проектирования (управляемых параметров) и m - мерного пространства Em выходных параметров. Каждой точке пространства En и Em соответствуют векторы X и Y значений переменных проектирования и выходных параметров соответствующего проектируемого объекта.

Следовательно, допустимой области D (образ) можно поставить в соответствие некоторое множество оценок. Это множество будем обозначать YD и его будем называть критериальным пространством или областью критериев (областью оценок), т.е. YD=F(D) - прообраз множества D.

Сформулируем задачу многокритериальной оптимизации. Она имеет вид:

min F(X) min F(X)

XD или

hk(X)=0, k=1,2, . . . , K; (5)

gj(X) 0, j= 1,2, . . . , J.

Задача многокритериальной оптимизации может быть сформулирована следующим образом, например:

в квадрате D={-1x1 1, -1x2 1} заданы два критерия которые желательно минимизировать.

Замечание. Символ minF(X) понимается как набор символов minFi(X), i=1,2, . . . , m. Будем предполагать, что все критерии нужно минимизировать, т.к. всегда можно перейти от maxFi(X) к min[-Fi(X)], i=1,2, . . . , m, т.е. сменой знака перед частным критерием.

Спрашивается, можно ли найти решение, одновременно удовлетворяющее всем этим требованиям? Со всей откровенностью ответим: нет. Решение, обращающее в минимум один какой-то показатель, как правило, не обращает ни в минимум, ни в максимум другие. Поэтому часто применяемая формулировка: "достичь максимального эффекта при минимальных затратах" представляет собой не более чем фразу и при научном анализе должна быть отброшена [стр. 44; Е.С. Вентцель. Исследование операций: задачи, принципы, методология. - 2-е изд., стер. - М.: Гл. ред. физ. мат. лит., 1988. - 208 с.].

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

Пример. При проектировании транзисторного элемента ЭВМ необходимо рассматривать одновременно несколько частных критериев оптимальности. Задача векторной оптимизации для данного примера имеет следующий вид:

maxF1(X); maxF2(X); maxF3(X); minF4(X); minF5(X);

XD XD XD XD XD

где D - область работоспособности; F1(X) - нагрузочная способность; F2(X), F3(X) - помехоустойчивость; F4(X) - рассеиваемая мощность, F5(X) - среднее время задержки сигнала.

Замечание. Векторная задача (выражение (4)) представляет собой ММ проектируемого объекта (технической системы), т.е. критерий эффективности, независимые переменные, ограничения образуют ММ рассматриваемой системы (объекта).

Процесс решения задачи (5), как правило, состоит из двух этапов:

1. Находят множество решений оптимальных по Парето PD;

2. Из множества P выбирают вектор , являющийся наиболее предпочтительным из всех векторов множества P и которому соответствует набор технических характеристик объекта Fi(Xopt), i=1,2, . . . , m.

Замечание. Дадим другую форму записи постановки задачи векторной оптимизации:

Xopt=arg minF(X)

XD

Таким образом, в результате решения задачи (4) мы получим вектор оптимальных параметров объекта и набор технических характеристик объекта Fi(Xopt), i=1,2, . . . , m.

Проблемы решения задач многокритериальной оптимизации

На предыдущей лекции мы сформулировали задачу многокритериальной оптимизации (ЗМО):

min F(X) или min (F1(X), F2(X), . . . , Fm(X))

XD XD

где Fi(X), i=1,2, . . . , m, частные критерии, D - область работоспособности. Заметим, что к выходным параметрам относят не только физические параметры (масса, скорость, задержка сигнала), но и стоимость, надёжность. Говорят, что мы построили математическую модель многокритериальной задачи оптимизации. Но эту задачу нужно ещё и решить, т.е. найти оптимальное решение. Главная особенность многокритериальных задач оптимизации заключается в том, что частные критерии противоречивы, т.е. улучшение одного приводит к ухудшению другого (других) критериев. Такие критерии (выходные параметры) ещё называют конфликтными.

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

Несравнимость решений. Основная сложность логического анализа многокритериальных задач состоит в том, что в них, в отличие от "обычных" (однокритериальных) задач появляется эффект несравнимости вариантов (решений). Рассмотрим пример. Множество D состоит из 4 возможных решений X1, X2, X3, X4. Каждому решению соответствуют определённые значения показателей (критериев) F1 и F2 (критерии минимизируются). Пусть имеются следующие векторные оценки: F(X1)=(2;4), F(X2)=(3;5), F(X3)=(5;2), F(X4)=(2;1). Вариант X1 лучше варианта X2. Вариант X1 лучше по первому критерию, но хуже по второму (варианты X1 и X3 несравнимы между собой). Вариант X1 хуже варианта X4. Вариант X4 лучше по первому критерию вариант X3, но хуже по второму (варианты X3 и X4 несравнимы между собой). В результате решения мы получили два недоминируемых (неулучшаемых) решения X3 и X4. Несравнимость решений является формой неопределённости, которая, в отличие от неопределённости, вызванной воздействием среды, связана со стремлением лица принимающего решение "достичь противоречивых целей" и может быть названа ценностной неопределённостью. Выбор между несравнимыми решениями является сложной концептуальной проблемой и составляет основное содержание многокритериальной оптимизации [В.В. Розен. Математические модели принятия решений в экономике].

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

После нормализации частных критериев векторные критерии приобретают некоторые полезные свойства. Главное из них - любая перестановка частных критериев приводит к векторной оценке, которая входит во множество векторных оценок (значений исходной векторной оценки). С помощью нормализации частных критериев стоятся пошаговые математические алгоритмы сужения исходного множества D до единственного решения. Нормализация частных критериев используется, например, при построении аддитивного критерия оптимальности.

Выбор принципа оптимальности, т.е. требуется определить правило, которое позволило бы сказать какое решение лучше. Выбор принципа оптимальности - основная проблема векторной оптимизации. Формально описать принцип оптимальности (критерии "правильности решения") - оказывается затруднительным.

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

2. Во-вторых, цели участников процессов принятия решений - различны и часто противоположны.

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

4. В-четвёртых, трудности выбора решения могут скрываться и в самой постановке задачи, если требуется достижение нереальных результатов. Например, получение максимальной прибыли при минимальном риске; строительство в минимальные сроки при максимальном качестве; минимальный ущерб противнику в военных действиях при минимальных собственных потерях.

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

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

Вычисление оптимума ЗВО. Сейчас достигнуты определённые успехи в области решения задач математического программирования (МП). Так по одним данным, методов однокритериальной оптимизации и их модификаций более 500 (пятисот), по другим - их количество перевалило за несколько тысяч! Но их, как правило, нельзя один к одному применять к решению. ЗМО, т.к. известны примеры, когда вычислительные алгоритмы становятся непригодными для решения задач математического программирования в результате небольших изменений и добавлений к первоначальной задаче, поэтому встаёт проблема - вычисление оптимума построенной задачи векторной оптимизации.

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

Развитие методов решения задач векторной оптимизации идёт по трём направлениям (хотя некоторые авторы называют больше):

Замена векторного критерия скалярным критерием, т.е. переход к однокритериальной задаче оптимизации;

Последовательное решение конечного множества однокритериальных задач;

Сужение множества D с последующим непосредственным выбором оптимального решения (см. рис 3.).

Рис. 3. Методы решения задач векторной оптимизации

Подведём итоги. Все задачи проектирования, управления многокритериальны по своему существу.

Построение допустимого множества - основной этап в постановке и решения задач оптимального проектирования и управления. Многокритериальная задача оптимизации вместе с множеством возможных (допустимых) решений D включает набор частных критериев оптимальности F1(X), F2(X), . . . , Fm(X). Набор частных критериев оптимальности образует вектор-функцию (векторный критерий), которую будем обозначать через F(X)=(F1(X), F2(X), . . . , Fm(X)).

Каждому решению XD соответствует векторная оценка F(X)=(F1(X), F2(X), . . . , Fm(X)). С другой стороны, каждой оценке F(X)=(F1(X), F2(X), . . . , Fm(X)) YD=F(D) могут соответствовать несколько решений из D. Таким образом, между множествами D и YD имеется связь, и поэтому выбор решения из D равносилен выбору соответствующей оценки из YD. В дальнейшем наряду с множеством допустимых решений D будем рассматривать множество YD - критериальное пространство (область критериев, пространство оценок).

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

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

В науке и технике достаточно актуальны задачи многокритериальной оптимизации [1,2,3], требующие одновременной оптимизации сразу по нескольким функциям (критериям). Краеугольным понятием в многокритериальной оптимизации является - Парето-оптимальная (недоминируемая) альтернатива, т.к. поиск приемлемой ("оптимальной") альтернативы, являющейся решением многокритериальной задачи, следует выполнять на множестве недоминируемых альтернатив. Именно поэтому так актуальны методы, позволяющие выделять подмножества Парето-оптимальных альтернатив из множества возможных альтернатив.

Для облегчения результатов полезно всё время проводить аналогию с однокритериальным (классическим) случаем. Пусть имеется область D и задана функция f(X) - целевая функция (критерий). Задача оптимизации имеет вид

min f(X)

XD

Точка X1D называется оптимальной (недоминируемой, неулучшаемой), если не существует точки X2D, для которой f(X1)>f(X2) (целевая функция минимизируется). Аналогично в МЗО можно исключить из области D точки, которые заведомо не могут оказаться наилучшими.

Очевидно, что в обобщённом смысле определение оптимальности можно трактовать как описание (выделение) в подмножестве D некоторого нового подмножества D0, т.е. некоторое сужение D до D0 D. В зависимости от характера описания, подмножество D0 может оказаться пустым, состоять из одного элемента, содержать более одного элемента. Описание D0 можно проводить либо только с помощью критериев Fi, либо использовать дополнительные условия. Здесь мы рассмотрим направление, которое связано с определением оптимальности по Парето Наименование указанного понятия связано с именем итальянского экономиста Вильфредо Парето [1848 - 1923(24)]..

Отношение доминирования по Парето. Парето-оптимальность.

Как было сказано раньше для всякого решения XD набор его оценок по всем критериям, т.е. набор (F1(X), F2(X), . . .,Fm(X)), есть векторная оценка решения X. Векторная оценка X содержит полную информацию о ценности (полезности) этого решения для ЛПР и сравнение любых двух решений заменяется сравнение их векторных оценок. Пусть в МЗО требуется получить меньшие значения каждого частного критерия (минимизировать частные критерии) Fi(X).

Опр. Пусть имеются два решения X1 и X2. Говорят, что решение X1 лучше (предпочтительнее, эффективнее, доминирует) решения X2, если Fi(X1)<=Fi(X2) для всех i=1,m, и хотя бы для одного j - го критерия выполняется строгое неравенство Fi(X1)<Fi(X2) или

Опр. Решение X2 называется доминируемым, если существует решение X1, не хуже чем X2, т.е. для любой оптимизируемой функции Fi, I=1, 2, …, m,

Fi(X2)Fi(X1) при максимизации функции Fi,

Fi(X2)Fi(X1) при минимизации Fi.

В случае доминирования при переходе от X2 к X1 ничего не будет проиграно ни по одному из частных критериев, но в отношении j - го частного критерия точно будет получен выигрыш. Говорят, что решение X1 лучше (предпочтительнее) решения X2.

Опр. Стратегия X1D называется эффективной (оптимальной по Парето), если не существует стратегии X2D такой, что Fi(X2)Fi(X1), i=1, . . ., m, F(X2)F(X1), или

Опр. Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.

Очевидно, тогда в составе множества D нет смысла сохранять решение X2, оно вытесняется (или, как говорят, “доминируется”) решением X1. Ладно, выбросим, решение X2 как неконкурентоспособное и перейдём к сравнению других решений по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество D обычно сильно уменьшается: в нём сохраняются только так называемые эффективные (иначе “паретовские”) решения, характерные тем, что ни для одного из них не существует доминирующего решения. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи математического программирования для каждого частного критерия. В литературе множество точек оптимальных по Парето, как правило, обозначают буквой P (PD).

Опр. Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. Будем обозначать YP (YP YD).

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

В области Yc нет противоречия между частными критериями оптимальности, т.к. каждая точка XD может быть изменена таким образом, что будет одновременно улучшены все частные критерии.

Если область критериев YD состоит только из области согласия Yc, то существует единственная точка XoptD, в которой все частные критерии согласованны между собой в том смысле, что при движении к точке Xopt все Fi(X) i=1, 2, . . ., m, одновременно улучшаются. Все частные критерии достигают минимума в т. Xopt (см. рис. 1). Такую точку называют оптимальным решение и при этом значения всех частных критериев достигают в ней минимума.

Рис. 1. Критерии F1 и F2 непротиворечивы

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



Рис. 2. Критерии F1 и F2 противоречивы на отрезке

Проиллюстрируем приём выделения паретовских решений на примере задачи с двумя критериями F1 и F2 (оба требуется максимизировать). Множество D состоит из 11 возможных решений. Каждому решению соответствуют определённые значения показателей F1 и F2. Пусть имеются следующие векторные оценки: F(X1)=(2;4), F(X2)=(3;5), F(X3)=(3;3), F(X4)=(5;2), F(X5)=(4;3), F(X6)=(1;3), F(X7)=(2;3), F(X8)=(3;2), F(X9)=(2;2), F(X10)=(3;1), F(X11)=(2;1). Векторные оценки исходов представим точками координатной плоскости (по оси абсцисс откладываем значения критерия F1, а по оси ординат - значения критерия F2). Используем принцип оптимальности по Парето для выделения эффективных решений. Решение X1 вытесняется решением X2, решение X2 лучше решений X3, X7, X8, X9, X10 и X11. Решение X4 по первому критерию лучше решения X5, а по второму наоборот, т.е. имеем неулучшаемые решения, и т.д. После проведённого анализа у нас остались три решения X2,X4, X5 оптимальных по Парето.

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



Рис. 3. Множество Yk

Когда из множества возможных решений выделены эффективные, “переговоры” могут вестись уже в пределах этого "эффективного" множества. На рис 3. образуют три решения X2, X4, X5; из них X4 лучше по критерию F1, а решение X2 по критерию F2. Дело ЛПР, выбрать тот вариант, который для него предпочтителен и “приемлем” по обоим критериям.

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

Замечание. Для определения эффективных точек используют правило “уголка”. Уголок вида L используется для определения компромиссных точек в критериальном пространстве, когда критерии максимизируются, а уголок ¬когда критерии минимизируются.

В случае, когда множество допустимых исходов является непрерывным, их векторные оценки "заполняют" некоторую область YD на плоскости и получается "картинка" вроде изображённой на рис.4. В этом случае множество Парето-оптимальных оценок (красная линия) представляет собой часть границы YD, образно говоря, её "юго-западную" границу". Если критерии максимизируются то - "северо-восточную" границу области YD.



Рис. 4. Пространство оценок YD и компромиссная кривая (красный цвет)

Замечание. В случае невыпуклой области её Парето-оптимальная граница может иметь более "экзотический" вид, например, состоять из отдельных линий и/или точек. Для данного примера (критерии максимизируются) -- это правый пик.

...