.RU

Языки описания выбора - Учебное пособие томск -2010 содержание


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

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

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. а. Область работоспособности, Критериальное пространство YП

заданная параметрическими ограничениями




Рис. 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)
^ Стремление оперирующей стороны к достижению цели описывается стремлением к увеличению (уменьшению) функций F1(X), F2(X), . . . , Fm(X), называемых критериями эффективности.

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

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

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

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

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

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

Пусть X1ÎD, тогда

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)

XÎD или

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

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

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

в квадрате D={-1£x1 £1, -1£x2 £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);

XÎD XÎD XÎD XÎD XÎD

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

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

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

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

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

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

Xopt=arg minF(X)

XÎD

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


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

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

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

XÎD XÎD

где 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 с последующим выбором одного решения лицом, принимающим решение (ЛПР).

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

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

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

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



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

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

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

Каждому решению XÎD соответствует векторная оценка 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 – критериальное пространство (область критериев, пространство оценок).

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

Предыдущая Главная Следующая


Следующая Начало

zhenya-i-serega-babini-magnit-dlya-priklyuchenij-ostrosyuzhetnaya-poznavatelno-razvlekatelnaya-povest-dlya-detej-srednego-i-starshego-shkolnogo-vozrasta-stranica-3.html
zhenya-i-serega-babini-magnit-dlya-priklyuchenij-ostrosyuzhetnaya-poznavatelno-razvlekatelnaya-povest-dlya-detej-srednego-i-starshego-shkolnogo-vozrasta.html
zher-kadastri.html
zher-ojnauin-pajdalanu-mseleler-zhnndeg-azastan-respublikasini-kejbr-zanamali-aktlerne-zgerster-men-tolitirular-engzu-turali-azastan-respublikasini-zai-zhobasini-tzhirimdamasi.html
zher-shn-tlenetn-tlemder-zheksenova-araj-adilbekizi.html
zher-uchaskesn-nisanali-masatin-zgertuge-sheshm-beru-memlekettk-izmet-standarti-zhalpi-erezheler-zher-uchaskesn-nisanali-masatin-zgertuge-sheshm-beru.html
  • exchangerate.bystrickaya.ru/bileti-po-mezhkulturnoj-kommunikacii-chast-13.html
  • report.bystrickaya.ru/internet-pod-kontrol-krasnaya-zvezda-grigorij-andriyanov-22032008-048-str-1.html
  • portfolio.bystrickaya.ru/politika-yunesko-v-sfere-razvitiya-sovremennih-mirovih-kultur.html
  • tests.bystrickaya.ru/lekciya-16--holodnaya-shtampovka-prodolzhenie-konspekt-lekcij-po-discipline-tehnologiya-konstrukcionnih-materialov.html
  • thesis.bystrickaya.ru/programma-dejstvij-administracii-vladimirskoj-oblasti-v-socialno-ekon.html
  • tests.bystrickaya.ru/koncepciya-razvitiya-rinka-cennih-bumag.html
  • tetrad.bystrickaya.ru/urok-muzikalnoe-iskusstvo-anglijskij-yazik-po-teme-obraz-materi.html
  • thesis.bystrickaya.ru/programma-disciplini-ods-06-specialnaya-psihologiya.html
  • teacher.bystrickaya.ru/glava-4-vidi-apraksii-t-g-vizel-osnovi-nejropsihologii.html
  • predmet.bystrickaya.ru/samosoznanie-lektorskij-vladislav-aleksandrovich-epistemologiya-klassicheskaya-i-neklassicheskaya-m.html
  • uchebnik.bystrickaya.ru/upotreblenie-strochnih-i-propisnih-bukv-v-naimenovaniyah-oficialnih-nazvaniyah.html
  • uchit.bystrickaya.ru/tema-4-uchebno-metodicheskoe-posobie-dlya-slushatelej-fzo-orel.html
  • institute.bystrickaya.ru/glava-5-ne-lishajte-menya-svobodi-f-g-uglovu-i-g-a-shichko-posvyashaetsya.html
  • kontrolnaya.bystrickaya.ru/razdel-6-inventarizaciya-resheniem-soveta-direktorov.html
  • exchangerate.bystrickaya.ru/istoriya-vozduhoplavaniya-i-aviacii.html
  • turn.bystrickaya.ru/pedagogicheskij-stazh-prikaz-04-sentyabrya-2006-g-219-v-red-prikaza-minobrnauki-rossii-ot-15-dekabrya-2006-g-325.html
  • occupation.bystrickaya.ru/na-konkurs-prinimayutsya-materiali-programmi-opublikovannie-vishedshie-v-efir-s-1-noyabrya-2006-goda-po-1-noyabrya-2007-goda.html
  • esse.bystrickaya.ru/referat-po-it-v-predmetnoj-oblasti-vvedenie-tema-moej-magisterskoj-dissertacii-zvuchit-kak-formirovanie-i-razvitie-massmedijnih-simvolov-na-primere-peredach-belorusskogo-televideniya.html
  • urok.bystrickaya.ru/primechanie-informaciya-o-vipolnenii-programmi-zakonoproektnih-rabot-tulskoj-oblastnoj-dumi-na-2007-god-59-v-programmu.html
  • desk.bystrickaya.ru/osobennosti-klassicheskoj-kartini-mira-voprosi-dlya-podgotovki-k-ekzamenu-kandidatskogo-minimuma.html
  • knigi.bystrickaya.ru/spisok-literaturi-vneshneekonomicheskih-svyazej-ekonomiki-i.html
  • spur.bystrickaya.ru/konkurs-razminka-vedushij-zadaet-vopros-zhyuri-zaschitivaet-otvet-dannij-igrokom-toj-komandi-uchastnik-kotoroj-pervim-podnyal-ruku-voprosi.html
  • literature.bystrickaya.ru/biologicheskaya-aktivnost-stranica-4.html
  • lecture.bystrickaya.ru/5-sroki-osvoeniya-osnovnoj-obrazovatelnoj-programmi-po-napravleniyu-podgotovki-diplomirovannogo-specialista.html
  • turn.bystrickaya.ru/perehod-k-rinochnoj-ekonomike-i-zadachi-milicii.html
  • shkola.bystrickaya.ru/sovremennoe-sostoyanie-v-nauchnoj-i-innovacionnoj-sfere-chast-2.html
  • bukva.bystrickaya.ru/totalitarnij-rezhim-chast-5.html
  • portfolio.bystrickaya.ru/otchet-o-rabote-gosudarstvennogo-obrazovatelnogo-uchrezhdeniya-srednego-professionalnogo-obrazovaniya-stranica-2.html
  • lektsiya.bystrickaya.ru/predislovie-kellerman-p-f-k-34-psihodrama-krupnim-planom-analiz-terapevticheskih-mehanizmov-per-s-angl-i-a-lavrentevoj.html
  • institut.bystrickaya.ru/tema-pervie-srednie-i-visshie-uchebnie-zavedeniya-kbr-ih-rol-v-pourochnoe-planirovanie-kursa-kultura-narodov-kbr.html
  • obrazovanie.bystrickaya.ru/praktikum-i-kontrolnie-zadaniya-po-nemeckomu-yaziku-dlya-studentov-specialnosti-dokumentovedenie-dnevnoj-i-zaochnoj-form-obucheniya.html
  • letter.bystrickaya.ru/modulnaya-programma-razrabotana-s-celyu-polucheniya-obuchayushimsya-ne-tolko-obshirnih-znanij-zalozhennih-v-tipovoj-programme-no-i-konkretnoj-informacii-po-voprosam-ne-vhodyashim-v-ustanovlennij-perechen.html
  • grade.bystrickaya.ru/mineralogo-geohimicheskie-i-gornie-nauki-otchetnij-doklad.html
  • lesson.bystrickaya.ru/segodnya-aktualnim-yavlyaetsya-vopros-rannego-okazanie-pomoshi-detyam-logopatam-reshenie-etoj-problemi-mi-vidim-v-tom-chisle-v-aktivnom-vzaimodejstvii-vseh-uchastn.html
  • testyi.bystrickaya.ru/82-materialno-tehnicheskoe-i-informacionnoe-obespechenie-disciplini-uchebno-metodicheskij-kompleks-po-discipline.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.