Казаринов Л.С., Попова О.В., Барбасова Т.А. Автоматизированные информационно-управляющие системы (часть 2)

Подождите немного. Документ загружается.

мулированные проблемы - те, в которых существенные зависимости

выяснены настолько хорошо, что могут быть выражены в числах или

символах, получающих в конце концов численные оценки.

Слабоструктуризованные, или смешанные проблемы — те, которые

содержат как качественные, так и количественные элементы, причем

качественные, малоизвестные и неопределенные стороны проблем имеют

тенденцию доминировать.

Важно подчеркнуть, что в типичных задачах исследования операций

объективно существует реальность, допускающая строгое количественное

описание и определяющая существование единственного очевидного

критерия качества. Изучение реальной ситуации может требовать большого

труда и времени. Необходимая информация может быть дорогостоящей

(например, требуются специальные исследования, чтобы определить

значения ряда параметров). Однако при наличии средств и хорошей

квалификации аналитиков имеются все возможности найти адекватное

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

переменными и критерий качества.

Можно сказать, что типичные проблемы исследования операций

являются хорошо структуризованными.

По-иному обстоит дело в многокритериальных задачах. Здесь часть

информации, необходимой для полного и однозначного определения

требований к решению, принципиально отсутствует. Исследователь часто

может определить основные переменные, установить связи между ними, т. е.

построить модель, адекватно отражающую ситуацию. Но зависимости между

критериями вообще не могут быть определены на основе объективной

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

являются слабоструктуризованными, так как здесь недостаток объективной

информации принципиально неустраним на момент принятия решения.

Более того, существуют проблемы, в которых известен только перечень

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

нельзя (нет необходимой информации). Иногда ясно лишь, что изменение

параметра в определенных пределах сказывается на решении. В таких

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

параметрами, не определена, и проблема называется неструктуризованной.

Типичными неструктуризованными проблемами являются многие проблемы

выбора. Слабоструктуризованные и неструктуризованные проблемы

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

решений при многих критериях.

Оценки по критериям

Cуществуют шкалы оценок по критериям. В принятии решений

принято различать шкалы непрерывных и дискретных оценок, шкалы

количественных и качественных оценок.

1. Шкала порядка - оценки упорядочены по возрастанию или

убыванию качества. Примером может служить шкала экологической

чистоты района около места жительства:

• очень чистый район;

• вполне удовлетворительный по чистоте;

• экологическое загрязнение велико.

2. Шкала равных интервалов – интервальная шкала. Для этой

шкалы имеются равные расстояния по изменению качест ва между

оценками. Например, шкала дополнительной прибыли для

предпринимателя может быть следующей: 1 млн, 2 млн, 3 млн и т.д. Для

интервальной шкалы характерно, что начало

отсчета выбирается произвольно, так же как и шаг (расстояние

между оценками ) шкалы.

3. Шкала пропорциональных оценок - идеальная шкала. Примером

является шкала оценок по критерию стоимости, отсчет в которой

начинается с установленного значения (например, с нулевой стоимости).

В принятии решений чаще всего используются порядковые шкалы и

шкалы пропорциональных оценок.

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

Можно сформулировать многокритериальную задачу линейного

программирования следующим образом.

Дано: область D допустимых значений переменных, определяемая

совокупностью линейных равенств и неравенств; критерии Q,

оценивающие качество решения.

Каждый из критериев линейно связан с переменными:





jiji

xcC

. (4.28)

где n — число переменных (j=l,...,n); с

— числовые коэффициенты.

Требуется: найти решение X в области D, при котором достигаются

наиболее приемлемые значения по всем критериям. Иначе говоря, нужно

найти такие критериальные оценки, при которых достигается

максимальное значение априори неизвестной функции полезности ЛПР.

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

Весовые коэффициенты важности критериев

При появлении многокритериальных задач возникли дополнительные

трудности их решения, связанные с получением информации от ЛПР.

Естественной реакцией на это было стремление получить такую информацию

сразу и быстро устранить многокритериальность. Этот подход был

реализован путем объединения многих критериев в один с помощью так

называемых весовых коэффициентов важности критериев. Глобальный

критерий вычисляется по формуле





iiгл

CwC

, (4.29)

где С

– частные критерии (i=l,...,N); wi – веса (коэффициенты важности)

критериев:

1;10







. (4.30

Идея такого объединения состоит в том, что ЛПР назначает числа (часто

по численной шкале 1-100), представляющие для него ценность

рассматриваемого критерия. Считается, что ЛПР может назначить такие

числа. Далее, весовые коэффициенты нормируются на основе условия (4.30).

Существует лемма, утверждающая, что для линейной задачи любое

эффективное, находящееся на множестве Э-П решение может быть

представлено в виде (4.29), т. е. в виде весов, умноженных на частные

критерии. Следовательно, формально задача сводится к нахождению весов.

Возникла идея, что эти веса можно получить от ЛПР оперативно. Если

ЛПР затрудняется в начале процесса решения (до изучения области D) сразу

назвать эти веса, то можно построить ЧМП следующего содержания: ЛПР

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

получения удовлетворительного результата.

Различные группы задач принятия решений

Представим в самых общих чертах группы задач принятия решений.

Задачи первой группы

Дано: группа из n альтернатив-вариантов решения проблемы и N

критериев, предназначенных для оценки альтернатив; каждая из альтернатив

имеет оценку по каждому из критериев.

Требуется: построить решающие правила на основе предпочтений ЛПР,

позволяющие:

а) выделить лучшую альтернативу;

б) упорядочить альтернативы по качеству;

в) отнести альтернативы к упорядоченным по качеству

классам решений.

Задачи второй группы

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

возможных альтернатив; альтернативы либо заданы частично, либо

появляются после построения решающего правила.

Требуется: на основании предпочтений ЛПР построить решающие

правила, позволяющие:

а) упорядочить по качеству все возможные альтернативы;

б) отнести все возможные альтернативы к одному из не скольких

(указанных ЛПР) классов решений.

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

имеющихся в продаже товаров, например телевизоров или стиральных

машин. Здесь все возможные альтернативы заданы, критерии определены

ЛПР; оценки реальных альтернатив по критериям дают, как правило,

эксперты. От ЛПР требуется построить правило сравнения объектов,

имеющих оценки по многим критериям (например, сравнить стиральные

машины на основании таких оценок, как цена, долговечность, стоимость

эксплуатации, надежность, возможность ремонта и т. д.).

Примером задач второй группы является построение правила принятия

решений для государственного или частного фонда, распределяющего

ресурсы на научные исследования. Проекты проведения исследований еще не

поступили, но критерии оценки и решающее правило должны быть

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

что они будут достаточно разнообразны по оценкам. Критерии и решающее

правило определяют ЛПР. Затем уже поступают проекты, которые

оцениваются экспертами по заданным критериям. Решающее правило

позволяет сразу же получить целостную оценку проекта.

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

рассмотрении в рамках первой задачи большого числа достаточно

разнообразных (по своим оценкам) альтернатив. Но при малом числе

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

существенно различаются.

Критерии принятия решения

1. Классический минимаксный критерий введён в 1950 году Вальдом и

соответствует позиции крайней осторожности:

= max e

, e

= min e

, (4.31)

= {E



Е e

= max min e

}. (4.32)

Для этого критерия матрица решений дополняется ещё одним столбцом из

наименьших значений e

каждой строки. Выбирать надо те варианты E

, где

стоят наибольшие значения e

этого столбца. Такой выбор полностью исключает

риск, и он применим, когда:

- ничего не известно о возможности изменения внешних факторов,

решение реализуется однократно;

- необходимо полностью исключить результаты хуже Z

2. Критерий Байеса-Лапласа учитывает каждое из возможных состояний:

= max e

, e



1

, (4.33)

т.е. вводится строка математических ожиданий. Этот критерий расширяет гра-

ницы минимаксного критерия, так как:

- известны вероятности появления или изменения внешних факторов;

- выбор может осуществляться многократно;

- появляется риск.

Существует ещё много других критериев: - вводящих понятие вы-

игрыша (Сэвиджа), - уравновешивающих оптимизм и пессимизм (Гурвица), -

объединяющих ММ и BL критерии (Ходжа-Леймана) и т.д. Очевидно, что

все критерии используют минимаксный принцип, учитывая разные

компоненты вероятности, весовых функций, критерий p, взятый из теории

нечетких множеств Задэ. На практике применяют поочерёдно различные

критерии, а затем принимают окончательное решение. Влияние критерия на вид

оценочной функции проиллюстрируем на простейшем примере рассмотрения

двух состояний F

, F

, когда у



Е, а e

= f(e

, e

), то после подстановки имеем:

и = е(у, F); v = e(y, F). С помощью f(u, v) = К задаётся семейство линий уровня,

получаемых параллельным переносом на плоскости (u, v) вдоль прямой, носящей

название направляющей. Для минимаксного критерия ММ семейство конусов

предпочтения лежит на линии х = у. В нашем случае необходимо

перемещаться по биссектрисе до момента встречи последней точки (e

, e

На рисунке 6 приведен пример для критерия Z

Рис. 4.8. Семейство линий уровня

Для критерия Гермейера введение вероятностей меняет лишь угол наклона

направляющей. Для критерия Сэвиджа происходит смещение на расстояние

полезности и т.д.

Оценка принимаемого решения

Учитывая, что решения необходимо принимать в любых случаях,

независимо от вида воздействий и законов распределения, приходится

вводить не только доверительные интервалы для параметров, но и их

коэффициенты значимости, прибегая к понятию релевантности (упорядо-

чению параметров по степени их влияния). Мерой неопределённости появле-

ния значения параметра принимается Шенноновская мера энтропии. При

выборе одной из альтернатив в принципе возможны четыре исхода:

- принято верное в данной ситуации решение;

- отвергнуто неверное в данной ситуации решение;

- отвергнуто верное в данной ситуации решение (ошибка 1-го рода);

- принято неверное в данной ситуации решение (ошибка 2-го рода).

Первые две ситуации очевидны и не требуют пояснений. Две следую-

щих ситуации широко применяются в теории математической статистики,

поэтому дадим только краткий комментарий. При проверке статистических

гипотез возможны две ситуации: гипотеза верна или гипотеза ошибочна и

два возможных действия: отвергнуть или принять одну из гипотез. Сведём

результат в таблицу 4.6.

Таблица 4.6

Ситуация

верна H

неверна (H

)

Действие

Отвергнуть

1-

Принять

1- α



Вероятности ошибочных решений в разных случаях их применения

носят порой разные наименования не меняя при этом своего статистического

смысла. Так:

- ошибка 1-го рода, риск 1, риск поставщика (изготовителя), риск

излишней наладки технологического процесса – α – определяется

вероятностью неправильного отклонения нулевой гипотезы и берется

обычно в интервале от 0,01 до 0,1.

- ошибка 2-го рода, риск 2, риск заказчика (потребителя), риск

незамеченной разладки технологического процесса –  – определяется

вероятностью принятия альтернативной гипотезы и берётся обычно от 0,1 и

выше. Любое принимаемое решение характеризуется заранее задаваемой

вероятностью ошибки первого рода и в процессе принятия решения может

возникнуть три принципиально различных случая:

1. Эмпирический доверительный фактор - известна выборка значений

параметров и оценивается относительная величина отклонения теоретичес-

кого среднего от минимального значения критерия.

2. Прогностический доверительный фактор - известны теоретичес-

кие вероятности значений параметров. Оценивается относительная величина

отклонения среднего выборочного значения по серии W экспериментов от

минимального значения критерия.

3. Эмпирико-прогностический доверительный фактор - относитель-

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

оценивается для предстоящей серии W экспериментов по результатам вы-

борки V проведенных.

Понятие риска

Принятие решений в условиях неопределённости связано с понятием

риска. Риск отражает степень неуверенности ЛПР в правильности

принимаемого решения и в возможных последствиях его реализации.

Отметим, что чаще этому риску подвергаются люди, не имевшие никакого

отношения к процессу принятия решения. Риск можно оценить

количественно:

R = A



q, (4.34)

где А - событие, a q - вероятность его появления. При этом необходимо

учитывать:

- тип угрозы (материальный или жизненно важный);

- ущерб (количественный, качественный, здоровью и т.д.);

- параметр (значение, превышение предела, вероятность).

При оценке риска необходимо строить дерево ошибок аналогичное

дереву решений. Естественно, что оценки риска весьма расплывчаты. Риск

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

парашютный спорт), риск событий, на которые трудно повлиять завышается.

При принятии решений необходимо выбрать рациональные варианты и

соотнести их с ущербом или угрозой. По разным отраслям и событиям

накоплена статистика, которая кладётся в основу расчётов c

использованием правил Булевой алгебры. Обозначив через К

– сочетание

неблагоприятных событий, а через N

, – отсутствие неблагоприятных

событий для рискованного варианта решения, получим полную группу

событий:

1)()(







iiiji

NqKq

, (4.35)

а риск при этом равен

)(

ijjij

KqAR





, (4.36)

т.е. риск равен ожидаемой величине ущерба при принятии E

. Сами оценки

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

экспертных методов.

Неформальные механизмы принятия решения

При учёте риска часто используются интуитивные, а порой и эмоцио-

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

индукционных или редукционных методах или использующие методы ас-

социаций, аналогий, правдоподобных рассуждений и т.п. Применение ИТ в

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

направление, которое занимает промежуточное положение между строгими

математическими методами и неформальными методами. Этим направлени-

ем являются экспертные оценки, развитие вычислительной техники позво-

лило создавать автоматизированные экспертные системы. Процедура

экспертного оценивания достаточно хорошо разработана. Поэтому вопросы

формирования деревьев целей и критериев, проведение квалиметрических

оценок, отбор экспертов, порядок проведения экспертиз и обработка их

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

остановиться на некоторых особенностях, которые надо учитывать при

возникновении необходимости обращения к экспертизе.

1. Далеко не все проблемы могут быть решены в настоящее время с

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

неполноты и противоречивости исходных данных.

2. Некомпетентность или предвзятость экспертов может загубить

любую экспертизу.

3. Нечёткая постановка задачи даже для сверхпрофессиональных

экспертов может привести к неверным выводам.

4. Для получения достоверных результатов надо обеспечивать

проведение независимых экспертиз и использовать комбинированные

экспертные технологии.

5. Стремиться использовать не только количественные оценки, но при-

бегая к квалиметрическим (качественным) оценкам стараться использовать

более мощные статистические шкалы, чем шкалы классификации.

6. Налаживать взаимодействие экспертов с целью исключения

конъюнктурности и конформизма.

7. Не исключать проведение экспертизы из процесса принятия

решений, так как в большинстве случаев выходные данные экспертизы

являются достаточными для использования их в качестве априорных в

корректных аналитических моделях или позволяют получить рациональное

решение уже входе экспертизы.

Многокритериальная теория полезности (MAUT)

Научное направление MAUT (Multi-Attribute Utility Theory) отличают

следующие особенности:

1) строится функция полезности, имеющая аксиоматическое (чисто

математическое) обоснование;

2) некоторые условия, определяющие форму этой функции,

подвергаются проверке в диалоге с ЛПР;

3) решается обычно задача из второй группы, а полученные

результаты используются для оценки заданных альтернатив.

Основные этапы подхода MAUT

Представим этапы решения задачи при подходе MAUT.

1. Разработать перечень критериев.

2. Построить функции полезности по каждому из критериев.

3. Проверить некоторые условия, определяющие вид общей

функции полезности.

4. Построить зависимость между оценками альтернатив по

критериям и общим качеством альтернативы (многокритериальная функция

полезности).

5.Оценить все имеющиеся альтернативы и выбрать наилучшую.

Аксиоматическое обоснование

Точно так же, как и классическая теория полезности, MAUT имеет

аксиоматическое обоснование. Это означает, что выдвигаются некоторые

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

ЛПР. В случае, если условия удовлетворяются, дается математическое

доказательство существования функции полезности в том или ином виде. В

MAUT эти условия можно разделить на две группы. Первая группа -

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

теории полезности.

1. Аксиома, утверждающая, что может быть установлено отношение

между полезностями любых альтернатив: либо одна из них превосходит

другую, либо они равны.

2. Аксиома транзитивности: из превосходства полезности альтернативы

А над полезностью альтернативы В и превосходства полезности В над

полезностью С следует превосходство полезности альтернативы А над

полезностью альтернативы С.

3. Для соотношений между полезностями альтернатив А, В, С,

имеющими вид

U(A)>U(B)>U(C), (4.37)

можно найти такие числа α, , которые меньше 1 и больше 0, так что:

αU(A)+(l-α)U(C)=U(B),

U(A)(1-)+U(B)>U(B). (4.38)

Аксиома 3 основана на предположении, что функция полезности

непрерывна и что можно использовать любые малые части полезности

альтернатив.

Вторая группа условий специфична для MAUT. Они называются

аксиомами (условиями) независимости, позволяющими утверждать, что

некоторые взаимоотношения между оценками альтернатив по критериям не

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

Приведем несколько условий независимости.

1. Независимость по разности. Предпочтения между двумя

альтернативами, отличающимися лишь оценками по порядковой шкале

одного критерия С

, не зависят от одинаковых (фиксированных) оценок по

другим критериям С

,..., C

. На первый взгляд это условие кажется

естественным и очевидным. Но возможны случаи, когда оно не

выполняется. Например, при выборе автомобиля при примерно одинаковой

цене ЛПР предпочитает большую по размеру машину. Однако его

предпочтение меняется на обратное, когда он узнает, что у машины не

гидравлическая, а механическая коробка передач, что усложняет управление.

2. Независимость по полезности. Критерий С

называется независимым

по полезности от критериев С

,..., С

, если порядок предпочтений лотерей, в

которых меняются лишь уровни критерия C

, не зависит от фиксированных

значений по другим критериям.

3. Независимости по предпочтению являются одним из наиболее важных

и часто используемых условий. Два критерия C

и С

независимы по

предпочтению от других критериев С

,...,С

, если предпочтения между

альтернативами, различающимися лишь оценками по С

, С

, не зависят от

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

Приведем пример нарушения условия независимости по предпочтению -

выбор дачи для летнего отдыха (табл. 4.7). Вполне возможно, что

альтернатива А предпочтительнее альтернативы В, если по критерию

«Расстояние от города» оба варианта имеют оценку «Дача расположена

недалеко от города». В то же время, если оба варианта имеют по последнему

критерию оценку «Дача расположена далеко от города», вариант В может

оказаться предпочтительнее варианта А. Первые два условия независимости

относились к независимости одного критерия от остальных, третье условие -

к независимости пары критериев от прочих.

Таблица 4.7

Задача выбора дачи для летнего отдыха

Альтернатива

Критерии

Качество

(комфортность)

наличие магазина

недалеко от дачи

расстояние от

города

А Хорошее Нет магазина

В Среднее Есть магазин

Судя по литературе, отсутствуют примеры зависимости трех и большего

числа критериев от остальных, которые не проявлялась бы в нарушении

условия независимости по предпочтению. По мнению известных ученых Г.

Фишера и Д. Винтерфельда, появление такой зависимости «неопределенно

по своей природе и трудно обнаружимо». В связи с этим понятно особое

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

Следствия из аксиом

Если аксиомы первой группы и некоторые из условий независимости

выполнены, то из этого следует строгий вывод о существовании

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

В качестве примера приведем широко известную теорему Р. Кини. Если

условия независимости по полезности и независимости по предпочтению

выполнены, то функция полезности является аддитивной

U(x) =

 

 



iii

wприxUw

1 1

1)(

(4.39)

либо мультипликативной

1)](1[)(1









wприxUkwxkU

, (4.40)