Скачать 385.99 Kb.
|
Многоэтапное принятие решенийМ ![]() ы рассмотрели различные критерии принятия решений в условиях неопределённости. На практике, в таких задачах как, проектирование изделий, программ, мы можем столкнуться с принятием последовательных решений. Особое значение вот такие многоэтапные решения имеют при создании автоматизированных экспертных систем. Рассмотрим вопрос оптимизации многоэтапных решений. Многоэтапность приводит к тому, что схема принятия решения может быть представлена в виде дерева, в каждой вершине которого осуществляется либо:
Рассмотрим пример оптимизации многоэтапных решений на примере экономической задачи. Пример: фирма может принять решение о строительстве крупного или мелкого предприятия. Строительство крупного предприятия относительно дешевле, в случае если будет высокий спрос на производимые товары, мелкое предприятие можно расширить. Деятельность фирмы рассматривается в течение десяти лет, причём в случае строительства мелкого предприятия, вопрос о расширении будет рассматриваться через два года. Спрос заранее неизвестен. В ![]() ведём градацию спроса: высокий ![]() ![]() Применим для решения этой задачи метод динамического программирования. В качестве критерия применим средний выигрыш, т. .е МО выигрыша. Сама величина критерия равна доходу без затрат на строительство. Начнём с последнего четвёртого шага: подсчитаем средний выигрыш: Исходя из полученного результата, оптимальным будем сразу строить крупное предприятие. Критерий Лапласа Этот критерий опирается на известный принцип недостаточного обоснования. Поскольку вероятности состояний q 1, q 2, ... ,q n не известны, необходимая информация для вывода, что эти вероятности различны, отсутствует. В противном случае можно было бы определить эти вероятности и ситуацию уже не следовало рассматривать как принятие решения в условиях неопределенности. Так как принцип недостаточного обоснования утверждает противоположное, то состояния q 1, q 2, ...,q n имеют равные вероятности. Если согласиться с приведенными доводами, то исходную задачу можно рассматривать как задачу принятия решений в условиях риска, когда выбирается действие ai , дающее ожидаемый выигрыш. Другими словами, находится действие ai* , соответствующее ![]() ![]() Пример. Одно из предприятий должно определить уровень предложения услуг так, чтобы удовлетворить потребности клиентов в течение предстоящих праздников. Точное число клиентов не известно, но ожидается, что оно может принять одно из четырех значений: 200, 250, 300 или 350 клиентов. Для каждого из этих возможных значений существует наилучший уровень предложения (с точки зрения возможных затрат). Отклонения от этих уровней приводят к дополнительным затратам либо из-за превышения предложения над спросом, либо из-за неполного удовлетворения спроса. В таблице приведены потери в тысячах долларов. Клиенты Уровень предложения
Принцип Лапласа предполагает, что q 1, q 2, q 3, q 4 равновероятны. Следовательно, P{q =q j } =1/4, j= 1, 2, 3, 4, и ожидаемые потери при различных действиях a1, a2, a3, a4 составляют E{a1}= (1/4)(5+10+18+25)=14,5 E{a2}= (1/4)(8+7+8+23)=11,5 E{a3}= (1/4)(21+18+12+21)=18,0 E{a4}= (1/4)(30+22+19+15)=21,5 Таким образом, наилучшим уровнем предложения в соответствии с критерием Лапласа будет a2. Полезность ожидаемых результатов В процессе выбора варианта решения нам часто бывает необходимо учитывать индивидуальное отношение людей к рассматриваемым показателям, и мы оцениваем полезность ожидаемых результатов. Полезность, или показатель полезности – это число, приписываемое конкретному результату, например, рабочей характеристике или состоянию системы, и представляющее собой оценку значимости этого результата по восприятию определенного человека или группы людей. Например, важными факторами являются финансовые затраты, экономический выигрыш, вес конструкции. При наличии единственного критерия и определенной связи между вариантами решения и значением этого критерия (целевой функции, или функции полезности) мы имеем задачу линейного (или нелинейного) программирования. В реальных задачах однозначно определить вид функции полезности часто не представляется возможным. Рассмотрим это на простом примере. Более 200 лет назад Бернулли, рассматривая вопрос о полезности богатства, пришел к выводу, что заданное приращение богатства не обязательно принесет строго определенное приращение счастья (удовлетворения). Напротив, чем бóльшим богатством обладает человек, тем меньше будет добавка полезности на определенную величину приращения богатства. Т.е. миллионер получит от подарка в 100 долларов гораздо меньшее удовлетворение, чем бедняк. Бернулли предположил, что приращение полезности обратно пропорционально богатству человека и вывел формулу ![]() ![]() где u – полезность богатства, x – богатство, b - коэффициент пропорциональности. Интегрируя, получим u = bln x +C. Если положить b=C=1, то u =ln x, а если b = lg e, то u =lg x. Предположим, что приращение полезности пропорционально и приращению полезности, которого не хватает для «полного счастья», и приращению количества денег. Это значит, что если кто-то испытывает полное удовлетворение от имеющегося богатства, то приращение богатства уже не дает человеку приращение удовлетворения. Тогда мы можем записать следующую зависимость: du = b(1-u)dx, где u = 1 соответствует случаю полного удовлетворения. Приняв u = 0 для x = 0, в результате интегрирования получим u = e-bx . Эта функция также описывает более медленное изменение полезности, чем линейная. Такие функции полезности могут использоваться для оценки предпочтительности той или иной альтернативы (варианта решения). различный вид функций полезности может отражать разные психологические установки людей, условия окружающей среды, влияющие на решение и т.п. Постулаты теории полезности Для ряда вероятных событий А, В, С они сводятся к следующим. 1) условие транзитивности: если А > В (т.е. А предпочтительнее, чем В, и В > С, то А > С и если А = В (т.е. А эквивалентно В), и В = С, то А = С; 2) случайное событие предпочтительнее других только в том случае, когда вероятность связанного с ним более желательного результата выше, чем вероятность менее желательного результата; 3) при выборе решения может быть учтен дополнительный риск; это относится, например, к ситуации, когда событие А происходит с вероятностью р, а с вероятностью 1-р происходит либо событие В с вероятностью р’, либо событие С вероятностью 1-р’. ![]() Другими словами, ![]() эквивалентно 4) если событие В по предпочтительности занимает промежуточное место между событиями А и С, то можно установить соотношение эквивалентности между событиями А или С; это означает, что если А>B>C, то существует такая вероятность р при 0 р 1, что B [p, A; (1-p), C]. На основе этих четырех постулатов для некоторой переменной может быть определена единственная функция полезности, которая должна удовлетворять следующим условиям: если А > В, то и u(A) > u(B), т.е. полезность события А больше чем полезность события В, когда А предпочтительнее В. Энтропия системы В рассмотренном примере существовала возможность дать рекомендации для выбора решения, поскольку были известны вероятности случайных событий. Однако часто возникают ситуации, когда эти вероятности неизвестны. Ранее в курсе рассматривались 3 вида неопределенностей в системах: а) из-за недостаточного знания; б) расплывчатость; в) случайная неопределенность. Для неопределенности случайного объекта существует количественная мера (неопределенности), называется энтропией. Рассмотрим простейший вариант – случайное событие. Пусть некоторое событие может произойти с вероятностью Р1 = 0,99 и не произойти с вероятностью Р2 = 0,01, а другое событие имеет вероятности Р1 = Р2 = 0,5. Очевидно, что в 1-м случае результатом опыта «почти наверняка» является наступление события, во втором случае неопределенность исхода так велика, что от прогноза лучше воздержаться. Если мы имеем дело со случайной числовой величиной, то для характеристики различности распределений используется дисперсия или доверительный интервал. Дх = ![]() Дх = ![]() Однако эти величины имеют смысл лишь для случайных числовых величин и не могут применяться к случайным объектам, состояния которых различаются качественно (например, выбор тех или иных команд или спортсменов при жеребьевке и т.п.). Следовательно, мера неопределенности, связанной с распределением случайного события должна быть некоторой его числовой характеристикой, функционалом от распределения, но никак не связанным с тем, в какой шкале измеряются реализации случайного объекта. Такой мерой неопределенности случайного объекта А с конечным множеством возможных состояний А1 …Аn с соответствующими вероятностями р1…рn величину, Н = - ![]() которая называется энтропией случайного объекта А (или распределения рi). Действительно, любая большая система может рассматриваться как система, которая принимает некоторое множество состояний S1, S2, …Sn с вероятностями Р1, Р2, ….Pn соответственно. Энтропия системы, будучи, как видно из формулы, математическим ожиданием логарифма вероятности пребывания системы в некотором состоянии S, рассматривается в качестве меры разнообразия для множества возможных состояний S. Эта функция соответствует выделенной К.Шенноном в теории информации «мере неопределенности». Если выбор любого состояния равновероятен, то неопределенность выбора максимальна и определяется общим числом возможных вариантов: Н = - ![]() Величина Н(n) эквивалентна понятию энтропии в статистической физике H = klnW, где W (Е) – статистический вес системы, или количество возможных квантовых состояний физической системы, внутренняя энергия которой не превосходит Е. В связи со всем сказанным выше можно записать и еще одно утверждение в отношении энтропии: Энтропия Н рассматриваемой системы является мерой ее неупорядоченности. Пример с голосованием: если n кандидатов имеют одинаковую вероятность получения голоса любого заданного избирателя, то, очевидно, что Pi = ![]() Принцип максимизации энтропии Принцип максимизации энтропии заключается в том, что в ситуациях, когда распределение вероятностей или значения вероятностей нам неизвестны, мы задаем их, исходя из следующего утверждения: Система находится в равновесии, когда энтропия максимальна, что соответствует полному беспорядку. В рассмотренном примере это соответствует ситуации, когда нам ничего неизвестно о распределении пристрастий избирателей, и мы принимаем вероятность избрания любого кандидата равной Pi = ![]() Энтропия системы, таким образом, является весьма полезной величиной при моделировании систем в условиях случайной неопределенности. ПРИЛОЖЕНИЕ1 Примеры решения задач при парной игре с нулевой суммой Задача 1.1. Найти решение игры, заданной матрицей А А= ![]() Решение. Прежде всего проверим наличие седловой точки в данной матрице. Для этого найдем нижнюю и верхнюю цену игры. Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры = max (2; 3) = 3. Максимальные элементы по столбцам равны (3 и 6) тогда верхняя цена игры = min (3; 6) = 3. Отсюда видно, что = =3 и мы имеем седловую точку ![]() Оптимальные чистые стратегии для первого и второго игроков равны соответственно U* = (0; 1), Z* = (1; 0), а цена игры = 3. Задача 1.2. Найти решение игры, заданной матрицей А А= ![]() Решение. Прежде всего проверим наличие седловой точки в данной матрице. Для этого найдем нижнюю и верхнюю цену игры. Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры = max (2; 3) = 3. Максимальные элементы по столбцам равны (4 и 6) тогда верхняя цена игры = min (4; 6) = 4. Отсюда видно, что и мы имеем игру, которая имеет решение в смешанных стратегиях, а цена игры . Предположим, что для первого игрока смешанная стратегия задается вектором U = (u1; u2). Первый игрок, если придерживается своей оптимальной стратегии, независимо от стратегии второго игрока получает цену игры , т.е. 4u1* + 3u2* = (1) 2u1* + 6u2* = . Кроме этого относительные частоты связаны условием: u1* + u2* = 1. Решаем полученную систему трех линейных уравнений с тремя неизвестными. Получим оптимальную стратегию первого игрока и цену игры: U* = ( u1* ; u2*) = (3/5; 2/5), = 18/5. Составим уравнения для нахождения оптимальной стратегии второго игрока, если при любой чистой стратегии первого, второй проигрывает цену игры: 4z1* + 2z2* = = 18/5 (2) 3z1* + 6z2* = = 18/5. Решаем полученную систему двух линейных уравнений с двумя неизвестными. Получим оптимальную стратегию второго игрока: Z* = ( z1* ; z2*) = (4/5; 1/5). Рассмотрим геометрическую интерпретацию этой задачи в смешанных стратегиях. Для этого в плоскости введем систему координат и на горизонтальной оси Ou отложим вероятность применения первым игроком его двух стратегий, сумма этих вероятностей равна 1, поэтому весь график расположится на отрезке единичной длины. В точках 0 стратегия (1; 0), а в 1 стратегия (0; 1). ![]() Рисунок 1. По оси ординат в точке 0 отложим выигрыши первого игрока по первой его стратегии при обеих стратегиях второго, а в точке 1 при второй стратегии первого игрока. Соединим эти платежи по столбцам, тогда пересечение прямых дадут решение системы уравнений (1), а ордината этой точки цену игры . Анологично можно построить график для нахождения оптимальной стратегии второго игрока. Мы рассмотрели только самый простой вариант парной матричной игры с нулевой суммой, но она достаточно наглядно показывает, что иногда можно количественно оценить и выбрать оптимальный вариант поведения в конфликтной ситуации. ПРИЛОЖЕНИЕ 2 Рассчитать энтропию системы, состоящей из избирателей и 5 кандидатов на государственный пост для следующих вариантов:
2-го 500 3-го 50 4-го 40 5-го всего 10 опрошенных
в пользу 2-го 250 3-го 30 4-го 15 5-го 5 Пример: n = 5 неупорядоченная более упорядоченная система система Pi = ![]() P2 = 0,5 lnp2 = - 0,693 P3 = 0,05 lnp3 = - 2,996 P4 = 0,04 lnp4 = - 3,219 P5 = 0,01 lnp5 = - 4,605 Полностью упорядоченная система Р1 = 1 Р2…Р5 = 0. ПРИЛОЖЕНИЕ3 Задача о секретарше![]() Начнём искать оптимальное решение с последнего шага. Определим МО «выигрыша» секретарши, если мы испытываем трёх кандидаток: Во втором испытании, если попалась хорошая секретарша, надо остановиться, а в первом испытании, надо остановиться только если попалась отличная, а в третье испытании берём любую. Найдём средний оптимальный выигрыш после всех испытаний: ![]() Список используемой литературы:
|
![]() | Примерная программа учебной дисциплины Общая математическая модель операции. Понятие стратегии. Неконтролируемые факторы (фиксированные, случайные, неопределенные). Понятие... | ![]() | Ситуационный подход к организации поведения Известно, что применение нечетких представлений дает значительные преимущества при решении сложных задач в условиях неопределенности... |
![]() | Ситуационный подход к организации поведения Известно, что применение нечетких представлений дает значительные преимущества при решении сложных задач в условиях неопределенности... | ![]() | А. А. Кирильченко доказательства в богословии как архетипы логических рассуждений в условиях неопределенности Рассмотрены основные, наиболее древние типы рассуждений в условиях неопределенности, взятые в основном из богословских доказательств.... |
![]() | Программа к урса “ Теория сложных систем” Цель курса: дать представление о динамике сложных систем, механизмах самоорганизации открытых систем, описать явления перехода от... | ![]() | Отчет по нирсу на тему “Вероятностные методы расчета в транспортных установках” Цель работы: применение вероятностных методов при проэктировании транспортирующих машин, а так же при анализе работы сложных транспортных... |
![]() | Методические указания к выполнению лабораторной работы №4 по дисциплине «Автоматизация проектирования сложных систем» «Автоматизация проектирования сложных систем» Анализ сложных систем методами теории полумарковских процессов. Часть Анализ систем... | ![]() | Оценка учебных достижений в условиях компетентностного подхода К профессиональным компетенциям относят: умение принимать решения в ситуациях неопределенности, владение проектной культурой и умение... |
![]() | Учебники и учебные пособия, которым присвоен гриф Нечеткое моде-лирование и много-критериальная опти-мизация технических систем в условиях неопределенности | ![]() | Среднерусский университет Свойства сложных систем. Сложная система, как объект моделирования. Прикладной системный анализ методология исследования сложных... |