Этапы процесса принятия решений; классификация задач принятия решений

1 1. Этапы процесса принятия решений 1) Предварительный анализ проблемы. 1. Главные цели 2. Элементы и структуры системы, уровни рассмотрения 3. Подсистемы, используемые ими ресурсы и критерии качества функционирования систем. 4. Основные противоречия, узкие места и ограничения 2) Постановка задачи 1. Формулирование задачи 2. Определение типа 3. Определение множества вариантов и основных критериев для выбора 4. Выбор метода решения задач 3) Получение исходных данных. Устанавливаются способы измерения альтернатив и комплексной оценки. При этом возможно 3 способа проведения комплексной характеристики: 1. Статистическая оценка 2. Метод математического (или имитационного) моделирования 3. Метод экспертной оценки 4) Решение задачи принятия решений с привлечением необходимых методических (?) методов, вычислительной техники, экспертов и ЛПР. Обработка исходных данных и решения может проводиться с одной стороны итеративно, а с другой – с привлечением нескольких методов. 5) Анализ и интерпретация полученных результатов Статические ЗПР Динамические Статические ЗПР не требуют многократного решения через короткий промежуток, а динамические ЗПР требуют частого регулярного решения. 2 2. Классификация задач принятия решений Любая ЗПР представляется в виде: , где T – постановка задачи, A – множество допустимых альтернатив, K – множество критериев выбора (способов оценки эффективности вариантов решения), X – множество методов измерения отношения между вариантами F – отображение множества допустимых вариантов на множество критериальных оценок, G – система предпочтений экспертов, D – решающее правило, отражающее эту систему предпочтения. Каждый из элементов этого набора может служить классификационным признаком. Традиционно рассматривается следующая классификация: 1) По виду отображения F F: A * K Может иметь детерминированный, вероятностный и неопределенный вид. В связи с этим выделяются следующие задачи: - в условиях определенности (если имеется достаточное и достоверное количество информации, пример – задачи оптимизации) - в условиях риска. Возникает, когда возможные исходы можно описать с помощью некоторого вероятностного распределения. Такое описание может быт получено либо статистическими, либо экспертными методами. - в условиях неопределенности. Все остальные задачи. Информация о задаче неполная, неточная. Форм. методы либо отсутствуют, либо слишком сложны. 2) По мощности множества К. Задачи могут быть однокритериальные и многокритериальные. 3) По типу системы предпочтения экспертов (G) - системы предпочтения одного ЛПР (задачи индивидуального принятия решений) - коллективная ЗПР - 3. Основные принципы принятия решений. К настоящему времени сложилось несколько общих принципов, которые позволяют обоснованно и ясно формулировать критерии отбора альтернатив, а также сузить множество поиска. 1) Принцип Парето (принцип единогласия). Оптимальным по Парето решением является такое решение X, что для решения Z, если кто-либо (хотя бы один участник коллектива) считает, что Z лучше X, то обязательно найдется кто-то другой, считающий, что X лучше Z. Принцип Парето означает, что поиск решения надо вести до тех пор, пока все единогласно не скажут, что X – оптимально. Для любого другого решения Z будет хотя бы один голос против. 2) Принцип равновесия Нэша. Определение принципа: существует ситуация, при которой принятие решения индивидуально отдельным ЛПР неэффективно для любого участника коллектива или сложившейся ситуации. 3) Принцип гарантированного результата (принцип минимакса). Принцип, используемый участниками, которые не хотят рисковать, а желают получить гарантированный результат. Т.е. при любом ходе, при любом варианте надо получить гарантированный результат независимо от действий другого игрока. Оптимальное решение(ния): e* =maxi minj eij Сначала для гарантии соглашаемся с наименьшим результатом, но затем от части компенсируем это, выбирая решение, для которого гарантированный результат максимален. 4) Принцип Байеса предполагает, что игроку известно распределение вероятностей появления реакций системы. Знание распределения должно приводить к более объективному критерию выбора для данных условий. Наиболее объективной оценкой значения выигрыша для каждого варианта действий будет мат. ожидание. Применив это действие ко всем строкам, получим набор значений мат ожиданий, выбираем наибольшее из них: е = maxi ∑j eijqj . 5) Принцип ограниченной рациональности. Опр. Существуют пределы способности человека описывать и правильно передавать информацию о сложных ситуациях, осмысливать эту информацию, одновременно продумывать несколько вариантов поведения и выбирать из каких-то разумных соображений только один. Следствием данного принципа является то, что на практике ЛПР склонен находить и использовать не оптимальное решение, а временно удовлетворительные, т.к. не в состоянии оптимизировать их. Реализация этого принципа привела к тому, что появились такие системы, как системы поддержки решений. При этом они реализованы как в виде специального коллектива, так и в автоматизированной среде (программа на ЭВМ). В соответствии с этим принципом основным видом решения является компромисс. 3 4. Постановка задачи динамического программирования Динамическое программирование – это поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируется только один шаг. Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. В общем виде постановка задачи ДП сводится к следующему. Имеется некоторая управляемая операция или целенаправленное действие, распадающаяся естественно или искусственно на n шагов. На каждом шаге осуществляется распределение и перераспределение ресурсов, участвующих в операции, с целью улучшения ее результата в целом. Это распределение ДП называется управлением операции и обозначается Y. Эффективность операции в целом оценивается тем же показателем, что и эффективность ее управления. При этом эффективность управления зависит от совокупности управлений на каждом шаге операции: w(u) = w(u1,u2,…,un). Управление, при котором показатель достигает максимума, называется оптимальным управлением. w(u*) = max w(u) u Оптимальное управление многошаговым процессом состоит из совокупности оптимальных пошаговых управлений. u* = (u1*, u2*,…,un*) Задача ДП – определит оптимальное управление на каждом шаге и тем самым оптимальное управление всей операцией в целом. В большинстве практических задач принимается, что показатель эффективности операции в целом – сумма эффективности действий на всех этапах операции. n W   wi i 1 n W *  max  wi n i 1 Выделим особенности модели динамического программирования: - задача оптимизации интерпретируется как n-шаговый процесс управления; - целевая функция равна сумме целевых функций каждого шага; - выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи); - состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Хk (отсутствие последействия); - на каждом шаге управление Хk зависит от конечного числа управляющих переменных, а состояние sk - от конечного числа параметров. 4 5.Обобщенная модель управления запасами Любая модель управления запасами, в конечном счете, должна дать ответ на два вопроса: 1. Какое количество продукции заказывать? 2. Когда заказывать? Ответ на первый вопрос выражается через размер заказа, определяющего оптимальное количество ресурсов, которое необходимо поставлять каждый раз, когда происходит размещение заказа. В зависимости от рассматриваемой ситуации размер заказа может меняться во времени. Ответ на второй вопрос зависит от типа системы управления запасами. Если система предусматривает периодический контроль состояния запаса через равные промежутки времени (например, еженедельно или ежемесячно), момент поступления нового заказа обычно совпадает с началом каждого интервала времени. Если же в системе предусмотрен непрерывный контроль состояние запаса, точка заказа обычно определяется уровнем запаса, при котором необходимо размещать новый заказ. Таким образом, решение обобщённой задачи управления запасами определяется следующим образом; 1. В случае периодического контроля состояния запаса следует обеспечивать поставку нового количества ресурсов в объеме размера заказа через равные интервалы времени. 2. В случае непрерывного контроля состояния запаса необходимо размещать новый заказ в размере объема запаса, когда его уровень достигает точки заказа. Размер и точка заказа обычно определяются из условий минимизации суммарных затрат системы управления запасами, которые можно выразить в виде функции этих двух переменных. Суммарные затраты системы управления запасами выражаются в виде функции их основных компонент следующим образом: (суммарные затраты системы управления запасами) = (затраты на приобретение) + (затраты на оформление) + (затраты на хранение) + (потери от дефицита запасов) Оптимальный уровень запаса соответствует минимуму суммарных затрат. Все эти затраты д.б. выражены как функции искомого объема заказа и интервалы времени между заказами. Затраты на приобретение: опр-ся стоимостью единицы приобретенной продукции. Стоимость м.б. постоянной или со скидкой (наценкой) в зависимости от объема. Затраты на оформление: постоянные расходы, не зависят от объема заказов. Затраты на хранение: сюда обычно включается стоимость хранения, содержания и ухода. Потери от дефицита: 1) потенциальные потери прибыли 2) субъективные потери (потери доверия у покупателей) 5 6. Классическая статическая модель Модель управления запасами простейшего типа характеризуются постоянным во времени спросом, мгновенным пополнением запаса и отсутствием дефицита. На рисунке показано изменение уровня запаса во времени. Предполагается, что интенсивность спроса (в единицу времени) равна . Наивысшего уровня запас достигается в момент поставки заказа размером у Уровень запаса достигает нуля спустя у/ единиц времени после получения заказа размером у. Уровень запаса Моменты поставки t0=y/ Средний уровень запаса = у/2 Время Рисунок.Изменение уровня запаса во времени Чем меньше размер заказа у, тем чаще нужно размещать новые заказы. С другой стороны, с увеличением размера заказа уровень запаса повышается, но заказы размещаются реже. Так как затраты зависят от частоты размещения заказов и объема хранимого запаса, то величина у выбирается из условия обеспечения сбалансированности между двумя видами затрат. Это лежит в основе построения соответствующей модели управления запасами. Пусть К – затраты на оформление заказа, имеющие место всякий раз при его размещении и затраты на хранение единицы заказа в единицу времени равны h. Следовательно, суммарные затраты в единицу времени TCU(y) как функцию от у можно представить в виде: K  y TCU(y) =  h  . Продолжительность цикла движения заказа составляет t0=y/ и средний y 2  уровень запаса равен y/2. Оптимальное значение у получается в результате минимизации TCU(y) по у. Таким образов, в TCU ( y ) K h предположении, что у – непрерывная переменная, имеем:   2   0 ,откуда оптимальное y 2 y 2 K .Оптимальная стратегия модели h предусматривает заказ у* единиц продукции через каждые t0*=y*/ единиц времени. Оптимальные 2 K затраты TCU(y*) составляют . h Для большинства реальных ситуаций существует (положительный) срок выполнения заказа (временное запаздывание) L от момента размещения заказа до его действительной поставки. Стратегия размещения заказов в приведенной модели должна определять точку возобновления заказа. С точки зрения анализа в условиях стабилизации системы срок выполнения заказа L можно всегда принять меньше продолжительности цикла t0* . Если это условие не выполняется, вычисляют эффективный срок L выполнения заказов: Le  L  n * t 0* , n  [ ] t0 значение размера заказа определяется выражением: y *  6 7. Задача экономичного размера заказа с разрывами цен Не редко цена единицы продукции зависит от размера закупаемой партии. В таких случаях цены меняются скачкообразно или предоставляются оптовые скидки. При этом в модели управления запасами необходимо учитывать затраты на приобретение. Рассмотрим модель управления запасами с мгновенным пополнением запаса при отсутствии дефицита. Предположим, что цена единицы продукции равна с1 при y=q, где с1>c2 и q – размер заказа, при превышении которого предоставляется скидка. Тогда суммарные затраты за цикл помимо издержек оформления заказа и хранения запаса должны включать издержки приобретения. Суммарные затраты на единицу времени при y=q эти затраты составляют K h TCU 2  y   c 2   y. y 2 Графики этих двух функций приведены на рисунке. Затраты TCU1 TCU2 I II y Рисунок: Графики функций TCU(y) III у Пренебрегая влиянием снижения цен, обозначим через ym размер заказа, при котором достигается минимум величин TCU1 и TCU2. Тогда y m  2 K . Из вида функции затрат TCU1 и h TCU2, приведенных рисунке 7 следует, что оптимальный размер заказа y* зависит от того, где по отношению к трем показанным на рисунке зонам I, II и III находится точка разрыва цены q. Эти зоны находятся в результате определения q1(>ym) из уравнения TCU1(ym)=TCU2(q1). В результате оптимальный размер заказа y* определяется следующим образом:  y m , если 0  q  y m ( зона I ),  * y  q, если y m  q  q1 ( зона II ),  y , если q  q ( зона III ). 1  m 7 8.Многопродуктовая статическая модель управления запасами с ограничениями вместимости. Эта модель предназначена для систем управления запасами, включающие n(>1) видов продукции, которая хранится на одном складе ограниченной площади. Пусть А – максимально допустимая площадь складского помещения для n видов продукции; ai - необходимое пространство для хранения единицы iго товара; y i - объем заказа iго вида. Ограничение на потребность в складском n помещении принимают вид a y i i  A. i 1 Допустим, что запас продукции каждого вида пополняется мгновенно и скидки цен отсутствуют, дефицит не допускается. Пусть i, Ki и hi – интенсивность спроса, затраты на оформление заказа и затраты на хранение единицы продукции в единицу времени для i-го вида продукции соответственно. Рассматриваемая задача имеет вид: минимизировать n n K  hy  TCU ( y,....., y n )    i i  i i  при  a i y i  A, y i  0 для всех i. yi 2  i 1 i 1  Общее решение этой задачи находится методом множителей Лагранжа. Однако, прежде чем применять этот метод, необходимо установить, действуют ли указанное ограничение, проверив 2K i  i выполнимость ограничений на площадь склада для решения y i*  неограниченной задачи. hi Если ограничение выполняется, то оно избыточно, и им можно пренебречь. Ограничение действует, если оно не выполняется для значений y i* . В таком случае нужно найти новое оптимальное значение yi, удовлетворяющее ограничению на площадь склада в виде равенства. Этот результат достигается построением функции Лагранжа вида hy  n  n K  L , y1 , y 2 ,  , y n   TCU  y1 ,  , y n      a i y i  A     i i  i i 2  i 1  i 1  y i   n       a i y i  A  , где (<0) – множитель  i 1   Лагранжа. Оптимальные значения yi и  можно найти, приравняв нулю соответствующие частные n K  h L L производные, что дает   i 2 i  i  a i  0 ,   a i y i  A  0 .  y i 2 yi i 1 Из второго уравнения следует, что значение y i* должно удовлетворять ограничению на площадь склада в виде равенства. Из первого уравнения следует, что y i*  2K i  i hi  2 * a i . Заметим, что y i* зависит от оптимального значения * множителя . Кроме того, при *=0 значение y i* является решением задачи без ограничения. Значение * можно найти методом систематических проб и ошибок. Так как по определению в поставленной выше задаче минимизации <0, то при последовательной проверке отрицательных значений  найденное значение * будет одновременно определять значения y*, которые удовлетворяют заданному ограничению в виде равенства. Таким образом, в результате определения * автоматически получаются значения y* . 8 9. Динамическая модель управления запасами при отсутствии затрат на оформление. Рассматривается задача календарного планирования производства, рассчитанная на n равных периодов. Возможные объемы производства на каждый из периодов ограничены, но могут включать несколько уровней. На протяжении текущего периода могут производится изделия для последующих, но в этом случае необходимо учитывать затраты на хранение. Основные предположения модели: 1) Отсутствие затрат на оформление заказа 2) Недопустимость дефицита 3) Стоимость производства единицы продукции в любой период либо является постоянной, либо имеет возрастающие предельные затраты, т.е. функция затрат является выпуклой 4) Стоимость хранения единицы продукции в каждый период является постоянной величиной Предположение об отсутствии дефицита означает, что спрос на продукцию в текущем периоде не может быть удовлетворен за счет ее производства в последнем. Т.е. суммарное производство в текущем периоде должно быть удовлетворено спросу за то же время. Рассмотрим задачу n-этапного планирования. Можно сформулировать в виде транспортной задачи с kn-пунктами n-пунктами потребления. К – количество возможных уровней производства. Производственные возможности каждого из kn пунктов производства определяют объемы поставок . Объемы потребления определяются объемом спроса для каждого периода. Себестоимость перевозки от пункта от пункта производства до пунукта назначения определяется суммой затрат используемого производственного процесса и стоимостью хранения единицы продукции. Оптимальное решение такой транспортной задачи определит объемы производственной продукции для каждого производственного уровня, который минимизирует суммарные затраты на производство и хранение. 10. Модель управления запасами с затратами на оформление заказа. Основные предположения модели: 1) Дефицит не допускается 2) Затраты на оформление заказа учитываются всякий раз, когда начинается производство новой партии продукции Существует два метода решения: 1) Точный метод динамического программирования 2)Эвристический прием Постановка задачи этой модели: Z1 Zi X1 X2 D1 Zn Xi Xn+1=0 Xn Di Dn Zi – количество заказанной продукции, объем заказа Di – спрос на продукцию Xi – объем запаса на начало этапа i. Стоимостные компоненты: Ki – затраты на оформление заказа Hi – затраты на хранение единицы продукции, переходящей из этапа i в i+1. Ci(Zi) – функция производственных затрат Ci (Zi) = 0 если Zi=0 и Ci (Zi)= Ki+ Ci (Zi) если Zi>0 Ci (Zi) – функция предельних производственных затрат при заданном значении Zi 9 11.Понятие игры. Характеристика игры. Цена игры. Теория игр – математическое моделирование условий конфликта и поиск на этой основе оптимальных решений. Игра – модель ситуации, некоторая упрощённая схема, где зафиксированы сами игроки, правила игры, определённые выигрыши после каждого хода, правила окончания игры. В более сложных играх совокупность ходов определяют некоторую стратегию. Участники игры – это участники конфликта. Каждая сторона, участвующая в конфликте, преследует свои цели, имеет активные средства для их достижения, разрабатывает и реализует стратегии, осуществляет рациональный выбор поведения. Участники конфликта обладают набором допустимых стратегий. Считается, что в результате применения каждой стороны порождает устойчиво повторяющийся результат, который частично можно считать исходом применения этого набора стратегии. Исходы образуют множество конечное или бесконечное. На множестве исходов у каждой стороны есть своя система предпочтений. Система предпочтений может быть выражена как бинарное отношение, что является наиболее простым способом задания системы предпочтения. Но непосредственно использовать систему предпочтений для моделирования сложно, поэтому чаще используют числовую функцию выигрыша, или по-другому платежную функцию. В целом получается, что игра задается следующими компонентами: /. Где U - множество участников игры S – множество стратегий участников J – множество возможных исходов П(u) – функция выигрыша, заданная на исходах Как правило игры разделяют на игры двух лиц и игры n лиц. Первые удобно представить в матричной форме следующего вида: B A S1b S2b … Snb Как правило, сами Исход исходы не записываются. S1a Название Кроме того, на значения Па(u), функций Пa(u) и Пb(u) Пb(u) накладываются ограничения: Если Пa(Uij) = - Пb(Uij) = Aij, S2a то получаем игру с нулевой суммой (бескомпромиссное решение). Игра с нулевой … суммой является наиболее простой для аналитического Sna решения. Если в условиях игры нулевой суммой участников > 2, то возможно появление коалиций или кооперативных игр. Игра с нулевой суммой двух лиц однозначно задается платежной матрицей. В каждой игре существует несколько оптимальных линий поведения, которые можно применить в чистом виде, т.е. сами по себе. Цена игры – среднее значение выигрыша одной стороны и проигрыша другой. 10 12. Классификация игр. Определение седловой точки. Классификацию игр можно проводить: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д. В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков - тем больше проблем. По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называется бесконечной. По характеру взаимодействия игры делятся на: 1) бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции; 2) коалиционные (кооперативные) – могут вступать в коалиции. В кооперативных играх коалиции наперёд определены. По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой. По виду функций выигрыша игры делятся на: матричные, биматричные, непрерывные, выпуклые, сепарабельные, типа дуэлей и др. Определение. Если в игре с матрицей А  =  (нижняя чистая цена равна верхней чистой цене), то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры  =  =  . Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство  =  .Если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе: aijo  aio jo  a io j , где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку. Таким образом, седловой элемент a i o jo является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент aio jo , называется решением игры. При этом iо и jо называются оптимальными чистыми стратегиями соответственно игроков 1 и 2. Свойства седловых точек: 1. Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы. 2. Взаимозаменяемость оптимальных стратегий. Игроки могут заменить свои оптимальные стратегии другими оптимальными стратегиями, при этом равновесие не нарушится, а выигрыш (проигрыш) останется неизменным. 11 13.Определение смешанной стратегии. Решение игры 2*2 в смешанных стратегиях. Смешанная стратегия это когда вместо того, чтобы применить какую-то одну конкретную стратегию, участники игры могут чередовать (смешивать) в случайном порядке свои стратегии в соответствии со специально разработанной схемой, обеспечивающей нужную частоту, или вероятность реализации каждой из стратегий. Для каждого игрока можно задать следующие компоненты: m Pia – вероятность применения i-ой стратегии со стороны А. P ia 1 i 1 Если подобрать такой набор Pia , который обеспечивает наибольший выигрыш независимо от действий второй стороны, то этот набор вероятностей {p1a , p2a , …, pma } = SA и будет называться смешанной стратегией. S*A = {p*1a , p*2a , …, p*ma } – оптимальная смешанная стратегия. { SA } – множество смешанных стратегий со стороны А, из которых нужно выбрать оптимальную. Игра 2*2 в смешанных стратегиях. Если хотя бы у одной стороны только 2 действия, применим графо-аналитический метод решения. Зададим игру в виде следующей матрицы: B A S1b S2b S1a S2a 11 12 21 22 Для этой игры можно считать следующее: игрок каждый раз играет против какой-либо чистой стратегии другой стороны. При этом он может выбрать такое соотношение вероятностей, которое даст ему гарантированный выигрыш, размером с цену игры. a11 p*1a + a21 p*2a = γ - при игре против первой чистой стратегии стороны В. a12 p*1a + a22 p*2a = γ – против второй чистой стратегии стороны В. p*1a + p*2a = 1 Аналогично для В: a11 p*1b + a12 p*2b = γ - при игре против первой чистой стратегии стороны В. a21 p*1b + a22 p*2b = γ – против второй чистой стратегии стороны В. p*1b + p*2b = 1 Решение системы уравнений: a 22  a 21 P1*a  a11  a 22  a12  a 21 a 22  a12 a11  a 22  a12  a 21 a a a a   11 21 12 21 a11  a 22  a12  a 21 Для того, чтобы полученные решения имели смысл необходимо требовать следующие соотношения: a 22  a 21  0 a 22  a 21  0 P1*b  a11  a 21  0 или a 22  a12  0 a11  a 21  0 a 22  a12  0 a11  a12  0 a11  a12  0 Если выполняется либо одно, либо другое, то вероятности от 0 до 1. Для стороны А: Для стороны В: γ γ a11 a11 P*1 max a22 a22 γ a21 γ mi n a12 P1a a21 a12 * P1b 12 14.Типы критериальных функций в играх с природой. В задачах теории статистических решений рассматриваются платежные матрицы (для дискретного случая), либо платежная функция (в непрерывном случае). Значения в платеж. матрице, либо в платеж. функции зависят от 2х факторов: 1. состояние природы, 2. варианты решений ЛПР. В отличие от теории игр, здесь только одна из сторон рассматривается как сторона с рациональным поведением. Др. сторона рассматривается как природный фактор с элементом неопределенности. В этом случае, условно считается, что мы играем с природой, поэтому относительно второй стороны делаются различные предположения о том, как будут выбираться варианты ее состояния. Платежная матрица может образовываться в результате решения оптимизационной задачи когда, например, можно получить несколько эквивалентных решений. Для осуществления выбора наилучшего варианта необходимо ввести критериальную функции, отражающую систему ei2 предпочтений ЛПР. 1 3 Геометрическая интерпретация. max e i2 F1 F2 I IV E1 РТ 2 E2 11 12 ● III II 21 22 min ei2 En n1 n2 min ei1 max ei1 ei1 Fi – состояние природы. Еi – варианты решений. Если отложить точки (ei1, ei2 ), то они заполнят определенное пространство, ограниченное прямоугольником. РТ – рабочая точка. Внутри этого прямоугольника образовалось 4 квадранта или 4 конуса. Рассмторим свойства точек из этих конусов. I : все точки хотя бы по одной координате лучше, чем рассматриваемая РТ. Поэтому конус I – конус предпочтения. III : все точки хотя бы по одной координате заведомо хуже чем РТ. II и IV : все точки по одной координате могут быть лучше, а по другой хуже. Поэтому эти конусы – конусы неопределенности. Для определения более менее предпочтительных точек, чем РТ, необходимо рассмотреть различные линии, представляющие линии уравнений или линии эквивалентных решений. Линия биссектрисы (линия 1) соответствует нейтральной критериальной функции. Линия 2 – пессимистическая критериальная функция. Линия 3 – оптимистическая критериальная функция. Любая из линий 1, 2, 3 соединяет эквивалентные по предпочтению точки. Точки, расположенные правее и выше любой из этих линий предпочтительнее точек, лежащих левее и ниже. Предельный случай для пессимистической функции – линии, ограничивающие I-ый квадрант. Для оптимистической – III-ий квадрант. 13 15.Классические критерии принятия решений в играх с природой. Классические критерии: 1. Минимаксный критерий Z MM  max ( min eij ) - оценочная функция i j Надо дополнить платежную матрицу столбцом из наименьших результатов по строке и выбрать те варианты решений, которые содержат max-ное значение в этом результирующем столбце. 2. Критерий Байеса – Лапласа В отличие от предыдущего, учитывается не единичный результат для любого варианта, а все возможные следствия. При этом требуется дополнительная информация, связанная с распределением вероятностей реализации внешних состояний. m Z BL  max (  eij q j ) i j 1 т.е. в результирующий дополнительный столбец записывается не min по строке, а мат.ожидание. 3. Критерий Сэвиджа. Z S  min (max (max eij  eij )) i j i aij  max eij  eij i Величину аij можно понимать как max-ный дополнительный выигрыш, который достигается если в состоянии Fj вместо варианта eij выбрать другой, оптимальный для этого состояния. Или как потери (штраф), возникающий в состоянии Fj при замене оптимального для него варианта на вариант хуже. В исходной матрице критерий Сэвиджа связан с риском. А сточки зрения элементов матрицы aij он от риска свободен. 4. Расширенный минимаксный критерий m n Z MM *  max min  eij p i q j , q p i 1 j 1 где p – вероятностный вектор для Ei , а q – вероятностный вектор для Fj. Расширенный ММ-критерий задается целью найти наивыгоднейшее распределение вероятностей на множестве вариантов Ei , когда в многократно воспроизводящейся ситуации ничего не известно о вероятностях состояний Fj. Поэтому предполагается, что Fj распределены наименее выгодным образом. 16.Производные критерии принятия решений в играх с природой 1. Критерий Гурвица. Оценочная функция этого критерия находится между точками зрения предельного оптимизма и крайнего пессимизма. Z HW  max(c min eij  (1  c ) max eij ), j i j где с – весовой множитель. 2. Критерий Ходжа-Лемана m Z HL  max(  eij q j  (1   ) min eij ) , i j j 1 где p – вероятностный вектор для Ei , q – вероятностный вектор для Fj,  - параметр, с помощью которого выражается степень доверия к используемому распределению вероятностей. 3. Составной BL(MM) критерий. I1: {i : ei0 j0  min eij   доп } j 14 I2: {i : max eij  max ei0 j  ei0 j0  min eij   i } j j j n Z BL ( MM )  max  eij q j , i ≤ I1∩I2. i j 1 I1 – множество проигрышей – номера тех вариантов, у которых min-ое значение в строке отличается от опорного решения, в качестве которого выступает величина, полученная по минимаксному критерию, не больше чем  допустимое. Величина проигрыша задается заранее и если ее значение не задано, то берем половину от опорного значения. I2 – множество выигрышей – номера вариантов решений, у которых разность между max-ным вариантом в строке решений и max-ным элементом в строке опорного варианта больше чем величина проигрыша. 4. Критерий Гермейера Z G  max min eij q j j i Данный критерий с самого начала ориентирован на величины потерь, т.е. на отрицательные значения eij. 5. Критерий произведений Z P  max  eij i j С самого начала этот критерий ориентирован на величины выигрышей, т.е. на положительные значения eij. 17.Шкала. Определение. Виды. Рассмотрим эмпирическое множество АЭ = {а1, а2, …, аn}, в качестве объектов которого могут выступать варианты решения или альтернативы. На этом множестве альтернатив задано некоторое бинарное отношение РЭ. Такая пара образует эмпирическую систему с отношением UЭ=<АЭ, РЭ>. Каждому объекту множества АЭ можно сопоставить некоторое число. Множество всех числовых оценок: АЧ = {f(a1), f(a2), …, f(an)}. На множестве чисел задано бинарное отношение РЧ. АЧ с РЧ образуют числовую систему UЧ = <АЧ, РЧ>. Соответствие между UЭ и UЧ устанавливается с помощью гомоморфного (односторонне однозначного) отношения f, такого, что (f(ai), f(aj))  PЧ, (аi, aj)  PЭ. Шкала - < UЭ, f, UЧ >. Виды шкал: 1. Номинальная. Числа в ней являются обозначениями или именами классов объектов. Пр.: ответ на закрытый вопрос анкеты, ответы на которые перечислены заранее. 2. Ранговая, или порядковая. Применяется для разбиения объектов на классы эквивалентности и для упорядочения этих классов по интенсивности рассматриваемого признака. Пр.: шкала твердости минералов Мооса. В номинальной шкале измеряется квалификации спортсменов, а в ранговой места, которые они занимают. 18.Экспертные методы получения количественных оценок альтернатив. 1. Непосредственное численное оценивание альтернатив. Метод заключается в присваивании объектам числовых значений в шкале интервалов. Эксперту необходимо поставить в соответствие каждому объекту точку на определенном отрезке числовой оси. При этом необходимо, чтобы эквивалентным объектам приписывались одинаковые числа. 2. Метод Черчмена-Акоффа (последовательное сравнение). В нем предполагается последовательная корректировка оценок, указанных экспертами. Основные предположения, на которых основан метод, состоят в следующем: 15 1. каждой альтернативе аi ставится в соответствие действительное неотрицательное число флаг; 2. если альтернатива a1 предпочтительнее альтернативы а2, то флаг(а1)>флаг(а2), если же альтернативы равноценны, то ф(а1) = ф(а2); 3. если ф(а1) и ф(а2)- оценки альтернатив а1 и а2, то ф(а1)+ф(а2)соответствует совместному осуществлению альтернатив а1 и а2. Этот метод можно успешно использовать при измерениях в шкале отношений. В этом случае определяется наиболее предпочтительная альтернатива а1. Ей присваивается максимальная оценка. Для всех остальных альтернатив эксперт указывает, во сколько раз они менее предпочтительны, чем а1. Для корректировки численных оценок альтернатив можно использовать как стандартную процедуру метода Черчмена-Акоффа, так и попарное сравнение предпочтительности альтернатив. Если численные оценки альтернатив не совпадают с представлением эксперта об их предпочтительности, производится корректировка. 3. Метод Терстоуна. При построении установочной шкалы Терстоуна респондент, соглашаясь или не соглашаясь с определенным образом подобранными суждениями, как бы сравнивает свой собственный "вес" с "весами" этих суждений, и мы считаем, что фактический "вес" респондента равен среднему значению "весов" тех предметов (суждений), с которыми этот респондент себя ассоциирует. Суждения должны составляться на базе собственного опыта исследователя. 4. Метод Фоннеймана – Моргенштейна. Он заключается в получении численных оценок альтернатив с помощью так называемых вероятностных смесей. В основе метода лежит предположение, согласно которому эксперт для любой альтернативы а1, менее предпочтительной, чем а2, но более предпочтительной, чем a3, может указать число А такое, что альтернатива а1, эквивалентна смешанной альтернативе (вероятностной смеси). Смешанная альтернатива состоит в том, что альтернатива a1 выбирается с вероятностью Р, а альтернатива а2 с вероятностью 1-Р. 19.Экспертные методы получения качественных оценок альтернатив. 1. Парное сравнение. Этот метод представляет собой процедуру установления предпочтения объектов при сравнении всех возможных пар. В отличие от ранжирования, в котором осуществляется упорядочение всех объектов, парное сравнение объектов является более простой задачей. При сравнении пары объектов возможно либо отношение строгого порядка, либо отношение эквивалентности. Отсюда следует, что парное сравнение так же, как и ранжирование, есть измерение в порядковой шкале. 2. Множественные сравнения. Они отличаются от парных тем, что экспертам последовательно предъявляются не пары, а тройки, четверки,..., n-ки объектов. Эксперт их упорядочивает по важности или разбивает на классы в зависимости от целей экспертизы. Множественные сравнения занимают промежуточное положение между парными сравнениями и ранжированием. 3. Ранжирование. Метод представляет собой процедуру упорядочения объектов, выполняемую экспертом. На основе знаний и опыта эксперт располагает объекты в порядке предпочтения, руководствуясь одним или несколькими выбранными показателями сравнения. В зависимости от вида отношений между объектами возможны различные варианты упорядочения объектов. 4. Гиперупорядочение. Основан на определении относительной значимости или относительного веса объектов. 5. Вектора предпочтений. 6. Классификация. Представляет собой разделение объектов по заранее известным или неизвестным классам. 16 20.Метод анализа иерархий. Этапы. Метод анализа иерархий (МАИ) является систематической процедурой для иерархического представления элементов, опеределяющих суть любой проблемы. Метод состоит в декомпозиции проблемы на все более простые составляющие части и дальнейшей обработке последовательности суждений ЛПР на основе парных сравнений. В результате может быть выражена относительная степень (интенсивность) взаимодействия элементов в иерархии. Эти суждения затем выражаются численно. МАИ включает процедуры синтеза множественных суждений, получения приоритетности характеристик и нахождения вариантов решений. Полезно отметить, что полученные таким образом значения являются оценками в шкале отношений и соответствуют так называемым жестким оценкам. Решение проблемы, согласно МАИ, – процесс поэтапного установления приоритетов. На первом этапе выявляются наиболее важные элементы проблемы, на втором – наилучший способ проверки наблюдений, испытания и оценки элементов; следующим этапом может быть выработка способа применения решения и оценка его качества. Весь процесс подвергается проверке и переосмыслению до тех пор, пока не будет уверенности, что процесс охватил все важные характеристики, необходимые для представления и решения проблемы. Процесс может быть проведен над последовательностью уровней иерархии, в этом случае результаты, полученные на одном из них, используются в качестве входных данных при изучении следующего. В соответствии с работой Т.Саати /1/, предложившего МАИ, для релизации метода необходимо осуществить следующие этапы: Этап 1.Очертить проблему и определить, что необходимо узнать. Этап 2.Построить иерархию, начиная с вершины (цели – с точки зрения управления), через промежуточные уровни (характеристики, от которых зависят последующие уровни) к самому нижнему уровню (который обычно является перечнем альтернатив). Этап 3.Построить множество матриц парных сравнений для каждого из нижних уровней – по одной матрице для каждого элемента примыкающего сверху уровня. Этот элемент называют зависимым (направляемым) по отношению к элементу, находящемуся на нижнем уровне, так как элемент нижнего уровня влияет на расположенный выше элемент (однако подчинен ему по цели). В полной простой иерархии любой элемент воздействует на каждый элемент примыкающего сверху уровня. Элементы любого уровня сравниваются друг с другом относительно их воздействия на направляемый элемент. Таким образом, получаем квадратную матрицу суждений. Попарные сравнения проводятся в терминах доминирования одного из элементов над другим на заданном уровне. Эти суждения затем выражаются в целых числах (смотрите таблицу шкалы 1–9). Если элемент А доминирует над элементом Б, то клетка, соответствующая строке А и столбцу Б, заполняется целым числом, а клетка, соответствующая строке Б и столбцу А, заполняется обратным к нему числом 17 (дробью). Если элемент Б доминирует над элементом А, то проис ходит обратное: целое число ставится в позицию Б, А, а обратная величина автоматически в позицию А,Б. Если считается, что А и Б одинаковы, в обе позиции ставится единица. На данном этапе для получения каждой матрицы требуется n(n–1)/2 суждений (при каждом парном сравнении автоматически приписываются обратные величины). Этап 4.Вычисляются компоненты собственного вектора как средние геометрические по строке. После нахождения, компоненты собственного вектора нормируются, что дает вектор приоритетов или весов объектов. Этап 5.После проведения всех парых сравнений и получения данных по собственному значению и собственному вектору можно определить согласованность. Для этого, используя отклонение lmax от n, проверяем индекс согласованности, сравнивая с соответствующими средними значениями, полученных для матрицы, построенной случайным образом, получаем отношение согласованности. Эти значения приведены ниже в виде таблицы 7. Этап 6.Этапы 3,4 и 5 проводятся для всех уровней и групп в иерархии. Этап 7.Проводится вычисление общего веса варианта решения путем последовательного взвешивания векторов весов нижележащего уровня (вариантов решений) компонентами вектора весов вышележащего уровня (характеристик). При этом вычисляется сумма взвешенных компонент вида SXнi*Yнij. Где Xнi – вес характеристики (элемента) вышележащего уровня иерархии , а Yнij – вес j-го варианта с точки зрения i-ой характеристики вышележащего уровня. Этап 8.Согласованность всей иерархии можно найти, перемножая каждый индекс согласованности на приоритет соответствующей характеристики и суммируя полученные числа. Результат затем делится на выражение такого же типа, но со случайным индексом согласованности, соответствующим размерам каждой взвешенной приоритетами матрицы. Отметим, что приемлемым является ОС не более 10%. Иначе необходимо произвести переоценку соответствующей матрицы. Если это не позволяет улучшить согласованность, то задачу следует более точно структурировать, то есть сгруппировать аналогичные элементы под более значащими (весомыми) характеристиками. После этого необходимо вернуться к этапу 2. 21.Метод анализа иерархий. Шкала. Для оценок важности объектов необходимо использовать одну из шкал. В МАИ используется шкала порядка следующего вида: Таблица 1 – Шкала относительной важности Интенсивнос Определение Объяснение ти относительной важности 1 Равная важность Равный вклад двух объектов в достижении цели 3 Умеренное превосходство Опыт и суждения дают одного над другим легкое превосходство одному объекту над другим 5 Существенное или сильное Опыт и суждения дают превосходство сильное превосходство одному объекту над другим 7 Значительное превосходство Одному объекту дается настолько сильное превосходство над другим, что оно становится значимым 9 Очень сильное превосходство Очевидность превосходства одного объекта над другим подтверждается наиболее сильно 2,4,6,8 Промежуточные значения Принимаются в 18 между двумя соседними суждениями Обратные Если при сравнении одного величины объекта с другим получено одно из приведенных чисел вышеуказанных чисел (например 3 ), то при сравнении второго объекта с первым получим обратную величину (т.е.1/3) компромиссных случаях Все вопросы, которые можно задавать при проведении сравнений элементов А и Б, попадают в одну из следующих категорий: – какой из них важнее или имеет большее воздействие на целевой результат? – какой из них более вероятен? – какой из них предпочтительнее? Первый вопрос обычно задают при сравнении характеристик, второй – при сравнении сценариев, получаемых из характеристик, третий – при сравнении вариантов решений. 22.Метод анализа иерархий. Калибровки. В исследованиях методов построения оценок было показано, что практически все методы построения предпочтений экспертов можно свести к последовательным оценкам парных сравнений. При этом такие оценки удобно представить в виде матрицы парных сравнений следующего вида – рисунке 1, где элементы aij соответствуют степени предпочтения i–го элемента по отношению к j–му. xj xi X 1 x1 x2 x3 a1 a1 a13 a1n a2 a23 a2n a3 a33 a3n an an3 ann 1 X 2 1 3 xn 2 a2 X ... 2 a3 1 2 ... xn an 1 2 Рисунок 1 – Матрица парных сравнений При этом считается заданным либо множество вариантов, либо множество характеристик вариантов (элементов) X={x1,...,xn}, которые сравниваются попарно с точки зрения их предпочтительности, важности, желательности и т.п. Матрица парных сравнений отражает бинарное отношение предпочтения/безразличия на множестве X. Такой матрице соответствует орграф G у которого дуга из вершины i в вершину j проводится в том случае, если элемент xi превосходит xj. Кроме того, дуга нагружается, иначе взвешивается соответствующим элементом aij. Такой граф не содержит кратных дуг. Симметричные элементы матрицы парных сравнений aij и aij должны выбираться равными, если соответствующие объекты равноценны или несравнимы (далее мы не будем различать эти случаи), если же xi>xj, то aij должно быть больше aji. Кроме этих условий, на элементы матрицы A обычно накладываются дополнительные калибровочные органичения, однозначно связывающие попарно симметричные элементы aij и aji. Рассмотрим основные типы таких калибровок. 1) Калибровка простой структуры. (ПС): ж 1, если xi>xj; Ai,j, i<>j aij=н 0, если xi=0; aij+aji=c. (2) Интерпретация: aij – число очков, набранных объектом (“игроком”) xi во всех сравнениях (“встречах”) с xj; число c=const при этом может интерпретироваться как количество таких сравнений (встреч). Нередко дополнительно постулируется целочисленность матрицы A. 3)Степенная калибровка. (С): Ai,j aij>0; aij*aji=1. (3) Интерпретация: объект xi превосходит в парном сравнении объект xj в aij раз. 4) Кососимметрическая калибровка. (К): Ai,j aij+aji=0. (4) Интепретация: объект xi превосходит в парном сравнении объект xj на aij. 5)Вероятностная калибровка. (В): Ai,j 0<=aij<=1; aij+aji=1. (5) Интерпретация: aij – вероятность превосходства xi над xj. При использовании ограничений – калибровок, количество парных сравнений уменьшается с n2 до n(n–1)/2, что очень важно с точки зрения стоимости и времени проведения экспертизы. Отметим, что в МАИ используется степенная калибровка матрицы парных сравнений. 23.Метод анализа иерархий. Вектора приоритетов. Для группы матриц парных сравнений мы формируем набор локальных приоритетов (заданного уровня иерархии), которые выражают относительное влияние множества элементов на элемент примыкающего сверху уровня. Для этого нужно вычислить множество собственных векторов для каждой матрицы, а затем нормализовать эти вектора (так, чтобы в сумма элементов каждого вектора давала единицу), получая тем самым вектор приоритетов данного уровня. Существует множество способов вычисления собственных векторов, отличающихся по сложности и эффективности. В МАИ предлагается алгоритм, использующий особенности парных оценок в симметричной шкале отношений, а именно строить элементы собственного вектора как средние геометрические по строкам (это возможно, поскольку матрица является вырожденной и её собственный вектор пропорционален значению строк). Например, для матрицы 4*4 это даст следующее. Компонент собственного вектора первой строки будет иметь вид: 4 Ц(w1/ w1)*( w1/ w2)*( w1/ w3)*( w1/ w4), компонент собственного вектора третьей строки будет иметь вид: 4 Ц(w3/ w1)*( w3/ w2)*( w3/ w3)*( w3/ w4). После вычисления компонент собственного вектора требуется провести их нормировку. Процедура вычисления собственного вектора и его нормировка для матрицы общего вида n*n представлена схемой на рисунке 3: A 1 A ---- A 2 2 --- ----- w w --- w .. . 2 w 1 1 A A n w 1 ---2 --- --- w w --- w w 1 --2 --- --- w w --- w 20 .. . A n w n ---- ----- w w n ---- ----- w w n ---- ----- w Рисунок 3 – Вычисление собственного вектора и его нормировка После того как компоненты собственного вектора получены для всех n строк, становится возможным их использование для дальнейших вычислений. Для удобства и однозначности прочтения далее в данной работе обозначим собственный вектор матрицы парных сравнений характеристик через X, его компоненты – Xi, а нормированный вектор соответственно – Xнi. Собственный вектор матрицы парных сравнений вариантов с точки зрения i–ой характеристики обозначим через Yi, его компоненты – Yij, а нормированный вектор соответственно – Yнij. 24.Метод анализа иерархий. Оценка согласованности. Весьма полезным побочным продуктом теории является так называемый индекс согласованности (ИС), который дает информацию о степени нарушения численной (кардинальной, aijajk=aik) и транзитивной (порядковой) согласованности. Для улучшения согласованности можно рекомендовать поиск дополнительной информации и пересмотр данных, использованных при построении шкалы. В других процедурах построения шкал отношения нет структурно порожденного индекса. Для выполнения условий согласованности в матрицах попарных сравнений используются обратные величины aji=1/aij вместо традиционно используемых при построении интервальных шкал величин aji=– aij. Все измерения, включая те, в которых используются приборы, подвержены погрешностям измерений, а также погрешностям из–за неточностей в самом измерительном приборе. Эти погрешности могут привести к несогласованным выводам. Вместе с матрицей парных сравнений мы имеем меру оценки степени отклонения от согласованности. Когда такие отклонения превышают установленные пределы, тому, кто проводит суждения, следует перепроверить их в матрице. Индекс согласованности в каждой матрице и для всей иерархии может быть приближенно получен вычислениями вручную по следующему алгоритму. Шаг 1. Вычисления оценочного значения максимального собственного числа lmax. 1) Сначала суммируется столбец суждений. 2) Затем сумма первого столбца умножается на величину первой компоненты нормализованного вектора приоритетов, сумма второго столбца – на вторую и т.д. 3) Полученные числа суммируются. Вновь образованная величина образует приближенное значение максимального собственного числа lmax. Шаг 2. Индекс согласованности вычисляется по следующей формуле (lmax–n) ИС=–––––––––––, (n–1) где n – число сравниваемых элементов. Для обратно-симметричной матрицы всегда lmax/n. Шаг 3. Определение оценки согласованности. Теперь сравним эту величину с той, которая получилась бы при случайном выборе количественных суждений из шкалы 1/9, 1/8, 1/7, ..., 1, 2, ..., 9, но образовании обратно-симметричной матрицы. 21 Величина, называемая оценка согласованности (ОС), получается путем деления ИС на случайную согласованность, выраженная в процентах ИС ОС = –––– *100% СС и показывает относительную согласованность матрицы парных сравнений. Величина ОС должна быть порядка не более 10%, в крайнем случае, в пределах 20%.