Особенности современной теории принятия решений. В курсе системный анализ рассматривались типовые математические модели систем операций, в которых в качестве искомых вариантов проведения операций выступали управляемые переменные. Например, в линейном программировании переменные принадлежат множеству действительных чисел. Значение целевой функции, так же действительное число.
Поэтому очень легко определить, что лучше, что хуже. В дискретном программировании множество вариантов дискретное. Существует большое число практических задач, в которых все значительно сложнее. 1 В некоторых задачах сами варианты проведения операций представляют собой небольшое число отдельных альтернатив. Например строить большой завод или строить меньше, а потом расширять.
Поэтому в ТПР говорят о задании множества альтернатив, на которых ищется оптимальное решение. 2 Во многих задачах множество альтернатив не ясно с самого начала, например, альтернативы при игре в шахматы. Поэтому в ТПР говорят о генерации альтернатив. При игре в шахматы приходится генерировать альтернативы и оценивать их. 3 Оценка ценности каждой альтернативы во многих случаях не сводится к простому сравнению чисел.
Целевая функция не является числовой и ТПР применяет специальные методы измерения полезности альтернатив. 4 В большом числе практических задач сама критериальная величина не может быть единственной, т. е. критерий не скаляр, а ветка. Оказывается, что когда по одному показателю один вариант лучше, по другому он может оказаться хуже, и поэтому их сравнить нельзя. 5 Во многих задачах автоматизации управления присутствуют нечткие переменные, и нечеткие критерии.
6 Иногда встречаются задачи, в которых присутствуют несколько сторон моделей, государств, фирм, которые принимают решения в одной и той же системе, причм критерии этих сторон противоположны. Такие ситуации называются конфликтными, при этом принцип оптимальности является совершенно иным, чем в линейном программировании. Этим занимается теория игр. 7 Во многих задачах принимаются групповые решения, при этом на основе экспертизы выявляется желание
этой группы, т. е. исследователь отделяется от эксперта. В результате обработки экспертов, исследователь получает критерий. Кроме этого, принятие решения является многократным. Если в какой-то задаче все семь проблем она неразрешима. Задача принятия решения. В задаче принятия решения назовем пару
Щ, С, где Щ множество вариантов альтернатив, Р принцип оптимальности. Решением задачи является множество , получающееся в соответствии с принципом оптимальности Р. Отсутствие хотя бы одного из элементов Щ, С лишает задачу смысла. Математическим выражением принципа оптимальности Р служит функция выбора Ср, которая со всеми подмножествами его часть Срх.
Таким образом, решением исходной задачи является СрЩ. Задача принятия решения различается в зависимости от информации о множестве Щ и принципе оптимальности Р 1 Общая задача принятия решения Щ, Р неизвестны, необходимо получить в процессе самого решения. 2 Задача с известными Щ называется задачей выбора.
3 Задача, в которой Щ, С известны называется общей задачей оптимальности. Оценка операций по многим критериям. Во многих задачах при моделировании критерия приходится назначать много критериев. Оказывается, что изменение одного критерия, нест за собой изменение другого критерия. Существует принципиальная трудность в оценке двух или более вариантов. Особенно если их оценивать безусловно. Векторная оптимизация 1
Безусловная оптимизация, когда пытаются определить безусловно лучшее решение, но после этапа безусловной оптимизации можно отсеять заведомо невыгодные решения, т. е. безусловно сравннные и худшие, поэтому несравнимые, но и не плохие остаются, и мы получаем эффективное множество множество Парето. 2 Для нахождения наилучшего решения приходится вводить некоторые условия, например, предпочтения или приходится выбирать из всех важных критериев, какой из них самый ценный.
Определение множества Парето Непрерывный случай. Если множество точек, в котором небольшое улучшение влечт за собой небольшое изменение . Пусть есть два показателя . Сравним безусловную пару вариантов третий безусловно лучше второго и первого. На дуге находятся лучшие точки при , а на дуге лучшие точки при . Поэтому точками множества Парето будут являться точки находящиеся на дуге .
Дискретный случай. Существует несколько алгоритмов нахождения множества Парето для дискретного множества точек. Они зависят от того, в каком виде задано множество вариантов критериев. В практических заданиях приходится сначала получать само множество критериев. Существует два основных метода нахождения множества Парето 1 Метод отбора конусом. Конус часть телесного угла, ограниченной области, соответствующая направлениям
оптимизации конкретного критерия. Пусть для двух критериев k1 и k2 v Если конус установить на границу критериального множества и обойти все точки границы, то если ни один луч не пересек область, то вершина конуса стоит на точке Парето. Пример k1 min k2 min 2 Метод прямоугольников. Запишем алгоритм для случая, когда k1 min и k2 min 1
Фиксируем самые левые точки, если их несколько, выбираем среди них нижнюю. 2 Через эту точку проводим вертикаль и горизонталь. 3 Фиксируем самые нижние точки, если их несколько выбираем самую левую. Проводим вертикаль и горизонталь. 4 Выбрасываемые точки являются точками множества Парето. 5 Отбрасываем все точки, лежащие на границе прямоугольника.
6 К внутренним точкам прямоугольника применим алгоритм с пункта 1. Методы условной оптимизации. После нахождения множества Парето, если количество точек в нм , встат вопрос о выборе единственной точки, которую необходимо выбрать для проведения операций. Так как точки на множестве Парето отбираются так, что каждая из них лучше по одному критерию, но хуже по другому, то совместное
улучшение по двум критериям невозможно. Условная оптимизация предполагает введение условия согласованности в компонентах критерия. Их существует четыре вида 1 Метод скаляризации. Здесь формируется некоторая скалярная функция многих переменных это скалярная величина. Наиболее распространнный метод метод скользящей суммы вес каждой компоненты критерия. 2 Метод главного критерия. Критерии располагаются в порядке убывания важности объявляется собственным
критерием, а остальные становятся управляемыми переменными Такой метод чаще всего используется при оптимизации технических систем в системах оптимизации и проектирования. 3 Метод уступок. Располагаем критерии в порядке убывания важности . Считаем критерий , а остальные отбрасываем и вычисляем . Назначается уступка на критерий , которую мы готовы отдать в пользу других критериев.
Далее проделываем то же самое для всех остальных критериев. далее и т. д. Очевидно, успех такого метода зависит от того, насколько тупой максимум. Процедура может быть повторена для других . 4 Метод последовательной оптимизации. В некоторых случаях критерии системы не слишком связаны друг с другом. Поэтому, сначала оптимизируют систему по важнейшему показателю, отбросив все остальные, затем по второму,
и т. д. Затем прогоняют оптимизацию в другом порядке. Динамическое программирование. Это особый метод, он специально приспособлен для оптимизации динамических задач, в которых операция состоит из элементов, сильно влияющих друг на друга. ДП связано с именем Ричарда Беллмана, который сформулировал принцип Беллмана. Он позволяет существенно сократить перебор решений в многоэтапных нелинейных задачах.
Рассмотрим экономическую задачу распределения ресурсов пусть есть начальный капитал . Его можно потратить на несколько предприятий . количество средств вкладываемых в ом году, в ое предприятие. В результате получается эффект В общем случае это не линейная функция. Так как функция нелинейная, то получаем задачу нелинейного программирования. Решать е сложно, кроме того, часто дискретные значения.
Вопрос нельзя ли решить задачу последовательно, т. е. найти оптимальное вложение для первого года, второго и т. д. т. е. провести последовательную оптимизацию. В большинстве задач так нельзя, т. к. то, что мы решили оказывает влияние на последующие шаги, например Бег на 800 метров. Каждый бегун имеет запас энергии, который он тратит на каждые 100 метров. ti время на i й 100 метров. Уtiхi min Ухi х0. Оказывается, на первых 100 метров бегун будет обеспечивать минимальное
время. Принцип оптимальности Беллмана Принцип оптимальности Беллмана ставит вопрос о том, что такое оптимальность отдельного элемента системы с точки зрения оптимальности всей системы. Принимая решение на отдельном этапе, мы должны выбирать управление на этом этапе с прицелом на будущее, т. к. нас интересует результат в целом за все шаги. Беллман предложил рассматривать величину выигрыша от го шага и до конца, если ый шаг начинается с некоторого
состояния . Такую величину называют условным оптимальным выигрышем . Тогда, принимая решение на шаге, мы должны выбрать так, чтобы условный оптимальный выигрыш был максимальным от шага и до конца. Определение оптимальность в малом понимается через оптимальность в большом. Любой процесс имеет где-то окончание, т. е. имеет горизонт планирования. Тогда последний этап не имеет будущего. Вот именно его можно оптимизировать только из условий данного
этапа. После этого приступают к оптимизации го этапа. Выбирают такое , чтобы при применении этого его внести в управление последнего шага. При этом мы задам состояние, с которого начинается ый шаг. Поэтому функцию называют условным оптимальным выигрышем. Таким образом, процесс оптимизации разворачивается от конца к началу, и начальное состояние становится
известно. Принцип Беллмана нашл применение в методе программно-целевого планирования любое действие планируется некоторым проектом. Задача о наборе высоты и скорости летательного аппарата. Летательный аппарат находится на высоте и летит со скоростью . Необходимо перевести его на высоту со скоростью . Причм Разобьм участок от до на частей Известен расход горючего при переводе системы на при и на при
. Таким образом, из каждого состояния есть лишь два управления. За каждое такое управление получим расход горючего выигрыш и потери. Суммарные потери равны сумме всех выигрышей на всех шагах. Дойдя до конца и получив 22, мы получим минимальную величину потерь горючего. Любая задача, сводится к поиску минимального пути в графе и решается методом динамического программирования.
Функциональное уравнение Беллмана. Назовм состоянием системы вектор координат . В некоторых задачах состояние одна величина. Тогда работу системы можно представить как движение в фазовом пространстве пространстве состояний. Назовм шаговым управлением управление на ом шаге. Рассмотрим процесс управления системой за шагов. Функция называется выигрышем на i-ом шаге. Здесь состояние перед ым шагом, а управление на ом шаге.
Величина должна быть известна до начала динамического программирования. Если состояние перед ым шагом было и мы приняли какое-то управление , то система перейдт в новое состояние . Эта функция должна быть так же известна. Если эти функции не заданы, то их надо сформулировать. Введм условный оптимальный выигрыш. Это выигрыш на всех этапах от до конца, если ый шаг начинается с состояния . Рассмотрим шагов. Начнм с го шага. Мы системой управляем оптимально, величина оптимального
выигрыша . На ом шаге – любое управление. неоптимальный выигрыш, т. к. на ом шаге мы применяем управление . Это функциональное уравнение Беллмана. Для использования уравнения Беллмана начинают с конца 1 . 2 Итак, идя от конца к началу, мы получаем последовательно Придя в начальное состояние W1S, мы можем подставить S S0 и W1S0 Wmax это безусловный выигрыш. Теперь необходимо получить, идя от начала к концу по цепочке,
безусловно оптимальное уравнение Итак, в конце мы получаем Задача распределения ресурсов. Это едва ли не самая распространнная операция. Под ресурсом в общем случае понимают физическую или абстрактную величину, которую система использует для производства полезного продукта. Например горючее, деньги, время, объм склада. Как правило ресурс ограничен, поэтому встат задача так распределить ресурс между отдельными элементами
системы, чтобы суммарный эффект был максимальным. Рассмотрим классическую задачу распределения ресурсов. Имеется начальное количество ресурсов , которые необходимо распределить между двумя отраслями. Каждая отрасль работает в течении лет. Если в первую отрасль в ый год вкладываются средства , то доход , если же во вторую вкладываются , тогда доход . Средства тратятся, принося доход, а новых средств не поступает и полученный доход не вкладывается. Нас интересует суммарный доход .
Суммарный выигрыш равен сумме выигрышей на каждом шаге. Состоянием системы является количество средств перед ым шагом. Так как новых средств не поступает, то ресурсы тают. Управление может быть записано как . После го шага в первой отрасли остаются средства , а во второй . Эти функции называются функциями траты. Мы можем составить уравнение
Беллмана. В этой задаче на i-ом шаге одно управление и одно состояние Исследуя функции траты, получим количество средств после го шага Задача о распределении ресурсов допускает геометрическую интерпретацию. Распределение на первом шаге указание точки на гипотенузе. После этого средства тратятся. Распределение средств движение внутрь треугольника.
Рассмотрим частные случаи задач о распределении ресурсов. Распределение по неоднородным этапам. Выше мы считали, что все функции одинаковы на всех этапах. Во многих задачах функции меняются от этапа к этапу . Покажем, что процедура динамического программирования принципиально не меняется. Запишем уравнение Беллмана Распределение ресурсов между тремя и более отраслями.
В этом случае на каждом шаге будет уже управлений, но одно из них может быть выражено как . В этом случае, в правой части уравнения Беллмана будет две и более переменных, по которым ищется максимум, и задача усложняется. Распределение ресурсов с резервированием. В такой модели если средства распределяются между двумя отраслями, то какое-то количество средств можно оставить до последующего распределения. В этом случае задача имеет смысл даже для одной отрасли.
Начальное количество средств разделяется на первом этапе на и на резерв, на втором этапе подлежат разделению средства из резерва. Такую задачу можно представить как с одной отраслью реальной, а другой фиктивной не приносящей доход и не расходующей средства. Решение такой задачи сводится к классической, задав функции дохода и трат. Подставив их в уравнение Беллмана, можно решить задачу как классическую. Задача может быть упрощена до следующей Задача линейного программирования с одной переменной.
Пусть вид функции не убывающий в этом случае недоиспользовать средства не выгодно. В этом случае решение допускают теоремы, обосновывающие, если 1 неубывающая и выпуклая вверх, оптимальное распределение ресурсов равномерное. 2 возрастающая и выпуклая вниз, оптимальное решение вложить все средства в один этап, и ничего не зарезервировать. Таким образом приходим к классической задаче. Трата оси
Х. Задача с резервированием в одной отрасли при параллельных функциях траты. Все функции траты . В этом случае задача сводится к более простой. Рассмотрим более частный случай все функции одинаковые на всех шагах . Эти функции неубывающие. 1 2 2 равенство, т.к. функция неубывающая и недоиспользование средств невыгодно. Это имеет теоретическое обоснование -1- если функция неубывающая и выпуклая вверх, то оптимальным распределением
является равномерное распределение. -2- Если функция неубывающая и выпуклая вниз, то оптимальным распределением является такое все распределение в один этап элемент и ничего в другие. Распределение ресурсов с вложением доходов в производство. В классической задаче считается, что полученный доход на ом шаге в производство не вкладывается, т. е. он отчисляется и подсчитывается как эффект. Во многих задачах полученный эффект можно использовать
как ресурс для следующего шага объединяя его с оставшимся ресурсом. Если ресурс не деньги, то средства можно привести к единому эквиваленту с оставшимися средствами. Такая модель является развитием классической модели. Так как оставшиеся средства и доход объединяются, то можно ввести единую интегральную функцию функцию изменения средств. количество оставшихся средств плюс доход после го шага, если вложили .
I. II. количество средств перед м шагом. Выигрыш на ом шаге зависит от того, как мы подсчитываем доход эффект от управления всеми ресурсами. Поставим задачу максимальный доход в конце го шага. Тогда на всех шагах , доход 0 На ом шаге выигрыш . Подставив эти выражения в уравнение Беллмана, мы программируем задачу от начала к концу, если имеется начальное количество средств . Здесь функция траты .
Частный случай когда и неубывающие. В этом случае чем больше значение доход средства получается в конце го шага, тем лучшим условием это будет для проведения го шага. Поэтому можно не заботиться о следующих шагах, достаточно обеспечить максимум на каждом шаге. Таким образом процедура оптимизации возможна в одном направлении от начала к концу, т. е. задача динамического программирования вырождается в задачу последовательной оптимизации.
Рассмотрим задачу распределения ресурсов с вложением доходов в производство и отчислением. Это наиболее общий случай. Разделим функции дохода и функции траты и максимальный суммарный отчисленный доход оставшиеся средства после го шага. Введм функцию отчисления доход. Тогда выигрыш на каждом шаге Уравнение Беллмана для го шага будет выглядеть так для надо учесть . Если , то мы получаем классическую задачу. Учт предыстории процесса.
Мы считаем, что функции как выигрыша, так и траты зависят от состояния перед ым шагом, т. е. не зависят от более ранних состояний. Такие процессы называются процессами без памяти. Но иногда при рассмотрении процессов, связанных с живыми организациями требуется помнить всю историю происходящего. Такая задача более сложна. Введм расширенное состояние состояние за шагов до го. Тогда . Но задача сложна вычислительном аспекте. Пусть имеет координат и предыстория распространяется
на шагов, тогда результат . Вот почему подобные задачи можно решать если . Задача с мультипликативным критерием. До сих пор мы считали, что суммарный выигрыш равен сумме выигрыш на ом шаге. Но есть задачи, где общий критерий равен произведению критериальных величин на каждом шаге. В этом случае так же можно применить уравнение Беллмана но вместо этого можно взять функцию . Оптимальные решения будут одинаковы ввиду многоэтапности функций.
Но можно при вводе уравнения Беллмана учесть, что Пример устройство состоит из узлов. Имеется некоторое устройство , которое может использоваться для повышения наджности каждого узла. Необходимо так распределить ресурс, чтобы суммарная наджность была максимальной. наджность каждого узла Операции не связанные со временем. Во многих задачах распределение ресурсов не связано с временными шагами.
Ресурс обычно распределяется по объектам. Например, если расписать распределение ресурсов между n объектами и на каждый объект задана функция выигрыша, то такая задача эквивалентна рассмотренной нами задаче о распределении ресурсов с резервированием в одной отрасли по n шагам. Игровые модели принятия решений теория игр. Игровая модель представляет собой особый вид модели ТПР. До сих пор мы считали, что решение принимается на основе критерия, отражающего эффективность по
отношению к нам. Оказывается, встречается довольно много ситуаций в экономике, особенно в военных операциях, где действует несколько сторон, преследующих различные интересы. И поэтому, невозможно оценить результат принимаемого решения единообразно. Такого рода ситуации называются конфликтными. Теория, описывающая конфликтные ситуации с количественной стороны, называется теорией игр. Интересы между сторонами могут быть полностью противоположными.
Такие модели называются антагонистическими играми. Но во многих ситуациях в игре могут принимать участие три и более сторон. Такие игры называются множественными. Некоторые стороны могут объединяться по интересам. Такие игры называются коалиционными. Игра модель ситуации, некоторая упрощнная схема, где зафиксированы сами игроки, правила игры, определнные выигрыши после каждого хода, правила окончания игры.
В более сложных играх совокупность ходов определяют некоторую стратегию. Мы будем рассматривать только парные игры, в которых есть два игрока, и интересы которых полностью противоположны антагонистические парные игры. Если игрок выиграл , то игрок выиграл потерял . Поэтому такие игры называются так же играми с нулевой суммой. Главным в игровой модели является то, что другая сторона противник, активно противодействует вам в
выборе оптимального решения. Поэтому мы должны объективно оценивать противника, т. е. становиться на его сторону, и считать, что противник не менее разумен чем мы. При этом меняется само понятие оптимального решения. В дальнейшем мы покажем, что принцип согласованного оптимума является основой игры. Ходы в игре могут быть личные и случайные. Личный ход зависит от сознательного решения стороны, а случайный
ход результат случайного механизма, который иногда применяется специально, а иногда случайно вовлекается в игру. Например, часто азартные игры состоят из одних случайных ходов. Стратегией игрока называется совокупность правил, определяющих выбор вариантов действий при каждом личном ходе игрока в зависимости от сложившейся ситуации. Если количество стратегий конечно игра конечная, в противном случае бесконечная игра.
Задачей теории игр является обоснование оптимальных стратегий обоих игроков. В теории игр считается, что игра повторяется многократно и игроков интересует средний выигрыш. К сожалению, при подходе к выработке оптимального решения приходится применять тот или иной принцип оптимальности. Платжная матрица. Рассмотрим конечную игру в которой у игрока стратегий, а у . Пусть при применении этих стратегий известен выигрыш , тогда говорят, что задана платжная матрица.
Т. е. применение в каждой игре стратегии однозначно определяет исход игры. Если есть случайные ходы, то выигрыш так же случае, и можно взять математическое ожидание выигрыша. Построить матрицу можно не всегда из-за е большого размера игра в шахматы. Для игр с полной информацией, т. е. когда один игрок знает, как поступил второй, всегда можно построить платжную матрицу. Рассмотрим простейшие примеры игр 1
Игра поиск. Игрок прячется в первом или втором месте. Игрок ищет его. Если игрок находит , то платит ему один рубль, если же не находит , то платит один рубль . Построим платжную матрицу. Решение этой игры . 2 Игра три пальца. игроки и одновременно показывают один, два или три пальца. Выигрыш равен сумме, причм если получилось чтное число очков, выигрывает , а если нечтное, то .
Строим платжную матрицу. Решение у этой игры . 3 Игра вооружение самолты. У стороны есть три вида вооружения зенитка, ракета и автомат. У три типа средств нападения. Известны вероятности, с которыми каждый ый тип вооружения сбивает каждое ое средство противника . Построим платжную матрицу. Решение для этой игры . Такое решение называется седловой точкой.
Рассмотрим принципы , на основе которых можно обосновать оптимальные решение. Принцип минимакса. Рассмотрим игру . При анализе игр применяют принцип осторожности пессимиста. Он требует, чтобы мы больше всего реагировали на плохие ходы со стороны противника плохие для нас. Будем рассуждать со стороны игрока если игрок идет по , то мы просматриваем всю строку и фиксируем самую меньшую . И так по всем строкам После этого мы можем выбрать так, чтобы было лучшее из худших
нижняя цена игры применяя принцип минимакса, меньше величины ты не получишь. Теперь рассмотрим игру со стороны игрока если игрок рассмотрит столбец , то самый худший для него максимальный в этом столбце Затем выбираем такую стратегию , которая обеспечивает минимум по максимальным верхняя цена игры. Итак, мы можем сразу найти и анализируя матрицы. Принцип чистых стратегий. Если игра имеет седловую точку, то говорят, что игра решается в чистых стратегиях.
Такое решение обладает свойством устойчивости, т. е. если один игрок придерживается своей оптимальной стратегии, то другому игроку невыгодно отклоняться от своей оптимальной стратегии. Это свойство устойчивости полагается в основу понятия оптимальной игры. В игре может быть несколько седловых точек. Но как правило таких точек нет, и нельзя найти решение в чистых стратегиях. Смешанные стратегии. Решение игр в смешанных стратегиях.
Если , то можно улучшить нашу нижнюю границу путм смешивания чистых стратегий, т. е. изменением стратегии от одной к другой от одного этапа игры к другому. Для каждой конкретной игры можно установить . Здесь цена игры , вероятность применения стратегии , вероятность применения стратегии . свойство полноты. С применением смешанных стратегий всегда можно найти решение, обладающее устойчивостью. Решением игры называется пара оптимальных смешанных стратегий обладающих следующим свойством если один
из игроков придерживается своей оптимальной смешанной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш соответствующего оптимального решения называется ценой игры. Основная теорема теории игр. Каждая конечная игра имеет по крайней мере одно решение, возможно в области смешанных стратегий. Цена игры заключена в пределах . Введм понятие активной стратегии стратегии, которая входит в решение с вероятностью большей нуля.
Теорема об активных стратегиях если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равен цене игры независимо от того, что делает другой игрок, если только тот не выходит за пределы своих активных стратегий. Доказательство пусть получена оптимальная стратегия игрока Применение решения 1 дает выигрыш . Пусть пользуется чистыми стратегиями, в результате получим выигрыш
. По определению решения игры следует, что отклонение от своей стратегии невыгодно для игрока . Посмотрим, может ли быть , т. е. существует ли такое . Выразим цены игры, полученные при применении смешанной стратегии как величину математического ожидания Получается, что чистая цена игры это математическое ожидание, если какая-то случайная величина , а все остальные равны , то среднее значение должно быть больше , а не равно ему, так как ни одна случайная
величина не может быть больше МО. Упрощение игр. Если в игре построена платжная матрица, то игру возможно упростить, т. е. заранее отбросить такие стратегии игроков, которые не могут быть выгодными ни при каких обстоятельствах. Итак вычркиваем заведомо невыгодные и дублирующие стратегии дублирующая стратегия это строка . Стратегия заведомо невыгодна, а при просмотре столбцов невыгодны большие векторы, поэтому так же вычркиваем. Таким образом, если записана платжная матрица, нужно е упростить, вычислить и , и если
они не равны друг другу, принимаются за решение смешанной стратегии. Решение игр . Если в такой игре нет седловой точки, то все стратегии являются активными. Если же седловая точка есть, то игра может быть решена путм отбрасывания заведомо невыгодных решений. Все стратегии активные, значит можно применить теорему об активных стратегиях Решая эту систему получим Для игрока Пример игра в прятки
Геометрическое решение игр . Игры с двумя стратегиями можно решить геометрически. Для этого начинаем решать игру со стороны игрока, у которого две стратегии. Пусть этот игрок А. Решается по принципу минимакса для игрока А. Решение необязательно находится на пересечении линий. Рассмотрим задачу со стороны игрока В. Если у одного игрока 2 стороны, а у другого много, то игру также
можно решить геометрически. В результате упрощения, игра имеет вид B1B2B3B4A1-12-36A21-14-5 Решим игру относительно игрока А Для решения необходимо решить совместное уравнение В4, В1. Тангенс угла наклона A1 A2 Решение игр m n. Пусть у игрока , стратегий, а у . В общем случае игра имеет решение в области смешанных стратегий.
Таким образом, чтобы решить игру надо найти и . Пусть игрок применяет свою оптимальную смешанную стратегию, а игрок чистую. При этом поучится выигрыш По определению решения игры, отклонение игрока от своей оптимальной стратегии невыгодно для него. Если бы все стратегии были активными, то можно было бы поставить в выражение . В дальнейшем будем считать, что величина цены игры . Этого можно добиться, если первоначальную платжную матрицу сместить вверх, т. е. прибавить величину
к каждому элементу матрицы. При этом решение игры не меняется. Разделим левую и правую часть неравенств на величину , и обозначим величины . Тогда получим систему ограничений в следующем виде Так как то Так как необходимо выбрать такие вероятности , что бы цена игры была максимальной, то можно считать, что . Получили следующую задачу линейного программирования найти такие неотрицательные величины
которые бы удовлетворяли системе уравнений и при этом минимизировали линейную систему . Аналогично рассмотрим игру со стороны игрока . Аналогично делим на и обозначим . Получим задачу Так как игрок стремится уменьшить выигрыш, то решение игры может быть сведено к решению пары задач линейного программирования. Рассмотрим вопрос существования решения задач . Доказательство существования этого решения будет доказательством основной теоремы теории игр.
Доказательство из теории линейного программирования известно, что задача линейного программирования не имеет решения в двух случаях 1 Нет допустимого решения, т. е. система ограничений несовместна. 2 Целевая функция не ограничена. Покажем, что любая пара задач линейного программирования имеет решение возьмм и . Рассмотрим самый маленький выигрыш матрицы . Тогда в качестве решения можно взять следующее . Подставим это решение во все строки линейных неравенств
. Так как , то, например, всегда, а остальные равны нулю, то у нас есть решение всегда. Так как вероятности и цена игры больше нуля, поэтому . Так как , то минимальная величина ограничена по крайней мере нулм, таким образом мы доказали, что решение и всегда существуют. А если существует , то существует , и значит существует во второй задаче. Мы доказали основную теорему теории игр любая матричная игра имеет решение в области смешанных стратегий.
Теория принятия статистических решений. Это чрезвычайно развитая область в экономике, в военном деле, в области обработки информации на фоне шумов и т. д. Рассмотрим элементы этой теории как продолжение теории игр. Существуют задачи, в которых бессознательный игрок, который мешает принимать нам принимать правильные решения, но он не противодействует активно, а действует в соответствии с природными случайными явлениями,
поэтому такую ситуацию называют игрой с природой. Например, помехи в канале связи для передачи информации, шумы при записи или воспроизведении звука и т. д. С другой стороны эта бессознательность приводит к непредсказуемому поведению противника. Так в теории игр мы постулируем факт, сознательного поведения противника. Вот почему в теории статистических решений, главным является обоснование критериев оценки различных
ситуаций со стороны . Мы будем рассматривать дискретные альтернативы стратегии природы. Тогда, если у нас имеется стратегий, а у природы имеется альтернатив, то может быть получена матрица выигрышей, при применении каждой пары . Условия иногда называются гипотезами, т. е. возникают как продукты действия со стороны . Если матрица построена, то задача состоит в анализе матрицы с целью получить стратегию , которая более выгодна по отношению к другим. В простейшем случае, если какие-то строки матрицы заведомо
невыгодны, то их можно отбросить и оставить только одну, безусловно лучшую, но обычно это не так. Столбцы платжной матрицы нельзя отбрасывать, т. к. природа может поступать и в нашу пользу. При анализе платжной матрицы можно сделать неверный вывод о качестве нашего решения. Пусть сравниваются два выигрыша, находящихся в разных столбцах и , причм . Если , то вроде бы решение в ой строке лучше, чем решение в ой строке, но так просто можно сравнивать,
если выигрыш соответствует одинаковым условиям. Пример в Томской области в этом году урожайность пшеницы 20 центнеров с гектара, а в Краснодарской 25. но эти значения сравнивать нельзя, т. к. для Томской области это оптимальный результат, а для Краснодарской плохой. Решение нужно сравнивать с потенциальными возможностями.
Вот почему необходимо преобразовывать платжную матрицу таким образом, чтобы каждый наш выигрыш соотносился с тем максимумом, который можно достигнуть в данных условиях . Для каждого можно найти максимальную величину и вычислить величину называемую риском. Здесь . Чем риск меньше, тем лучше. Методы принятия решений в условиях риска. Принятие решений при известных априорных вероятностях.
Будем обозначать вероятности гипотез . Таким образом, мы считаем, что вероятности известны до того, как мы решили принять решение. Решение выбор оптимальной стратегии . говорят, что это ситуация идеального наблюдателя. Естественно, в качестве критерия выбирается средний выигрыш, который мы получим, если выберем стратегию Это аналог математического ожидания. Решение принимается по критерию критерий максимального среднего выигрыша. Если задана матрица рисков, то можно для каждой строки вычислить средний риск и оптимальным
будет являться решение, которое . Возникает вопрос не одно это и то же Покажем, что оптимальное решение можно искать как по , так и по . тогда . величина независящая от , это постоянная величина для данной строки. В результате решения выбирается чистая стратегия . Есть ли смысл смешивать стратегии пусть мы смешиваем наши стратегии с вероятностями , тогда в результате применения смешанной стратегии мы получим средний выигрыш в таком виде математическое ожидание
Мы знаем, что МО меньше максимального значения в игре с природой нет смысла смешивать стратегии чистая стратегия обеспечивает наилучший результат. Слабым местом в этом подходе является то, что надо знать априорные вероятности. Если они неизвестны, то необходимо их изучить. Это можно делать путм экспериментов, которые учитывают условия природы. Говорят, что мы эту систему обучаем. Такой подход называется принципом адаптации к условиям.
Если априорные вероятности изучить не удатся, то применяется принцип недостаточности основания если не знаем о вероятности, то считаем, что гипотезы природы равновероятны. После этого применяем критерий идеального наблюдателя. Так как при равных вероятностях энтропия неопределнность максимальна, то мы применяем принцип пессимизма. Если сами значения вероятности неизвестны, но есть информация о предпочтениях гипотез, то существуют
методы обработки предпочтений и получения вероятностей. Если вероятности гипотез относятся как , то можно подсчитать саму величину вероятности в следующем виде В некоторых случаях учитывается не только средний выигрыш, но также и дисперсия, т. е. величина разброса выигрыша в каждой строке Принятие решений при неизвестной априорной информации. Если априорная информация неизвестно или ненаджна, то применяются другие критерии 1
Критерий Вальда это максимально-минимальный критерий, т. е. выбирается максимальная стратегия , для которой . Мы подходим к .той задаче, рассчитывая на самый худший случай, как и в игре с разумным противником. 2 Критерий Сэвиджа это критерий минимаксного риска . Этот критерий не эквивалентен критерию Вальда, т. е. оптимальный по Сэвиджу не обязательно так же будет эквивалентен по
Вальду. 3 Критерий Гурвица это комбинированный критерий, его так же называют критерием пессимизма-оптимизма коэффициент, который выполняет требования критерия быть более или менее оптимистичным. При , а при , крайний оптимизм. Существуют другие критерии и однозначный выбор одного критерия невозможен. Но если одну и ту же ситуацию рассматривать по разным критериям, то получается одинаковое решение по разным критериям. Планирование эксперимента в условиях неопределнности.
Если априорной информации нет или она ненаджна, то можно путм проведения эксперимента получить более наджные данные о вероятности . Под экспериментом понимают систему мероприятий позволяющих уточнить информацию о состоянии природы. Насколько может помочь в принятии решения эксперимент и как сопоставить стоимость эксперимента с тем оптимальным выигрышем, который мы получим Соответствующую теорию можно построить исходя из знания вероятности , а так же из знания на основе критериев
при неизвестной априорной информации. Мы рассмотрим когда есть априорная информация, т. е. ситуацию идеального наблюдателя. Появляется вопрос есть ли смысл проводить эксперимент Возможны два случая 1 Идеальный эксперимент. Результат этого эксперимента однозначно определяет каковы условия природы. Пусть заданы выигрыши и априорные вероятности . Стоимость эксперимента сопоставима с , т. е. имеют одинаковую размерность.
Сравним средний выигрыш без проведения эксперимента со средним выигрышем при проведении эксперимента Нет эксперимента Если мы проведм эксперимент, то мы точно узнаем , и тогда найдя в ом столбце максимальный выигрыш, мы найдм наш выигрыш . Но нам нужно оценить эффективность эксперимента до его проведения, поэтому мы должны ориентироваться на средний ожидаемый выигрыш, который мы получим, если будем проводить эксперимент. Таким образом, после эксперимента мы можем ожидать выигрыш .
Поэтому чтобы решить, проводить эксперимент или нет, надо определить, что больше или . Получается, что мы будем проводить эксперимент, если B преобразовав это неравенство, получим 2 Неидеальный эксперимент. В результате проведения эксперимента мы не находим однозначно , а лишь изменяем вероятность . Пусть проводится неидеальный эксперимент. В результате появляются некоторые несовместные события .
Вероятности этих событий зависят от условий, в которых они проводятся. Пусть известны . Эти вероятности называются прямыми. После эксперимента, давшего исход необходимо пересмотреть вероятности , т. е. вместо вероятности мы перейдм к вероятности . Это так называемые апостериорные вероятности формула Байеса. Но результаты эксперимента могут быть и и и , поэтому мы можем только ожидать всякие исходы
, которые получатся в результате эксперимента. Причм, каждый исход привл бы к некоторым оптимальным стратегиям . А величина выигрыша, которая бы при этом получилась Эти выигрыши , могут произойти с вероятностью события , т. е. это вероятность . У нас их нет, но их можно получить по формуле полной вероятности Тогда ожидаемый выигрыш будет Можно рассмотреть случай, когда проводят эксперимента.
Их при этом считают независимыми. Многоэтапное принятие решений. Мы рассмотрели различные критерии принятия решений в условиях неопределнности. На практике, в таких задачах как, проектирование изделий, программ, мы можем столкнуться с принятием последовательных решений. Особое значение вот такие многоэтапные решения имеют при создании автоматизированных экспертных систем. Рассмотрим вопрос оптимизации многоэтапных решений.
Многоэтапность приводит к тому, что схема принятия решения может быть представлена в виде дерева, в каждой вершине которого осуществляется либо 1 Сознательный выбор между двумя и более альтернативами 2 Случайный переход из одной ветви в другую под воздействием внешних факторов Рассмотрим пример оптимизации многоэтапных решений на примере экономической задачи. Пример фирма может принять решение о строительстве крупного или мелкого предприятия.
Строительство крупного предприятия относительно дешевле, в случае если будет высокий спрос на производимые товары, мелкое предприятие можно расширить. Деятельность фирмы рассматривается в течение десяти лет, причм в случае строительства мелкого предприятия, вопрос о расширении будет рассматриваться через два года. Спрос заранее неизвестен. Введм градацию спроса высокий и низкий . Затраты и доходы строительство крупного предприятия 5 млн. строительство мелкого 1 млн. затраты на
расширение 4,2 млн. крупное предприятие при высоком спросе дат доход 1 млн. ежегодно, а при низком 300 тыс. мелкое предприятие при высоком спросе 250 тыс. ежегодно, при низком 200 тыс. расширенное предприятие в случае высокого спроса приносит доход 900 тыс. в год, и при низком спросе 200 тыс. мелкое предприятие без расширения при высоком спросе на производимый продукт приносит в течение двух лет по 250 тыс. ежегодно, а в течение следующих восьми по 200 тыс Нарисуем наше дерево.
Применим для решения этой задачи метод динамического программирования. В качестве критерия применим средний выигрыш, т. .е МО выигрыша. Сама величина критерия равна доходу без затрат на строительство. Начнм с последнего четвртого шага подсчитаем средний выигрыш Исходя из полученного результата, оптимальным будем сразу строить крупное предприятие.
Задача о секретарше. Директор собирается принять на работу секретаршу. Прежний опыт делит секретарш на три категории отличных 3 балла, хороших 2 балла и посредственных 1 балл. Анализ учебных заведений по подготовке секретарш дат статистику выпускниц заведений вероятность взять на работу отличную секретаршу 0,2, хорошую 0,5, посредственную 0,3. директор может испытать только трх претенденток, причм в случае отказа директора кандидат убывает на другую работу.
Построим дерево решений. Начнм искать оптимальное решение с последнего шага. Определим МО выигрыша секретарши, если мы испытываем трх кандидаток Во втором испытании, если попалась хорошая секретарша, надо остановиться, а в первом испытании, надо остановиться только если попалась отличная, а в третье испытании берм любую. Найдм средний оптимальный выигрыш после всех испытаний
Нелинейное программирование НЛП. НЛП это такая задача математического программирования, когда-либо целевая функция, либо ограничения, либо они вместе представляют собой нелинейные функции. Несмотря на то, что ограничения могут быть наложены на сами переменные, термин НЛП применяется только тогда, когда действительные числа. Решение задач НЛП намного сложнее решения задач ЛП, при прочих равных условиях.
Рассмотрим особенности задач НЛП, а именно то, где может находиться оптимальное решение. Для этого будем рассматривать целевую функцию двух переменных. В НЛП используют геометрический образ целевой функции, как некоторой поверхности, определнный на множестве управляемых переменных. Методы НЛП разработаны только для выпуклых функций, причм так как используются производные, считается, что функции должны быть дифференцируемы.
Методы оптимизации нелинейных функций без ограничений. Если ограничения в задаче НЛП отсутствуют, то применяют все методы оптимизации нелинейных функций. Причм, если в задаче с ограничениями, они находятся внутри области, то решение можно найти этими методами. Говорят, что ограничения не являются активными и их можно отбросить. Рассмотрим наиболее широко применяемые методы. 1 Классический градиентный метод.
Все эти методы принадлежат к поисковым методам, т. е. оптимальное решение находится не сразу, а последовательным движением от точки к точке и заканчивается в оптимальной точке. Начинаем с начальной точки, е выбор чтобы была ближе к оптимальной точке. Для е выбора и направления движения используют понятие градиента. Градиент вектор, показывающий направление наибыстрейшего изменения функции.
Градиент направлен по нормали к поверхности целевой функции, а в плоскости по нормали к линиям уровня. Алгоритм . Каждая последующая точка определяется как предыдущая длина градиента в предыдуще точке шага задача на максимум задача на минимум. Если максимуму или минимум гладкий большой коэффициент тупизны, градиент у нас уменьшается в вершине градиент равен нулю по модулю по мере приближения к максимуму и шаг уменьшается. Но при выборе надо иметь в виду следующее если мало, то идти будем долго, а если
большое, то можем перепрыгнуть. В некоторых алгоритмах , в более сложных зависит от . Правила остановки могут быть различными, например следующее 2 Покоординатный градиентный метод метод координат спуска или подъма. Из некоторой начальной точки движемся вдоль некоторой координаты в сторону, где проекция градиента положительна. Движемся до тех пор, пока производная по этой координате не будет равна нулю.
Затем движение идт по второй координате аналогичным способом, и т. д. если для двух координат, то опять по первой и по второй. 3 Метод наискорейшего спуска подъма. В этом алгоритме из некоторой начальной точки движение осуществляется вдоль направления градиента до тех пор, пока производная по этому направлению не будет равна нулю. Далее из этой точки определяем градиент и т. д. Отличие здесь в том , что длина шага определяется из
условия, чтобы обеспечить Второй и третий методы называются алгоритмами с длинным шагом. Кроме этого существуют методы, использующие вторую производную, например, метод Ньютона Метод поиска минимальной, не использующий понятие производной. Метод Нелдера-Мида. Современные методы поиска минимальной максимальной нелинейной функции чрезвычайно разнообразны. Одним из наиболее эффективных является метод
Нелдера-Мида. Идея метода состоит в том, что, вычисляется значение целевой функции в вершинах сначала правильного, а затем деформируемого многогранника. Многогранник некоторое правильное тело в мерном пространстве. Эта правильная фигура называется симплексом. В задачах для двух переменных, это правильный треугольник. Затем сравниваются значения целевых функций в вершине, а затем выполняются операции 1
Отражение поворот симплекса через одну из сторон 2 Растяжение если идм в правильном направлении 3 Редукция возврат назад, если перескочили максимум 4 Сжатие уменьшение сторон, чтобы движение было с более мелким шагом. Алгоритм 1 Обозначим самая худшая точка самая лучшая точка. центр тяжести всех вершин, исключая . Координаты центра тяжести определяются 2 Затем отражаем, и получаем точку .
Здесь коэффициент отражения в обычном случае он равен единице. Если , то вектор растягивается в раз и получаем Если для полученной точки , то заменяется на , и переходим к пункту 2 Если , то вектор сжимается в раз и получаем точку Затем точка заменяется на точку , и так же переходим к пункту 2 Если , то все векторы уменьшаются в раз . номер вершины.
Затем возвращаемся к пункту 1. Правило остановки Задачи НЛП с ограничениями-равенствами. В НЛП особо рассматриваются задачи с ограничениями-равенствами. Это так называемые задачи на условный экстремум. Решение такой задачи производится с использованием функции Лагранжа. Это функция позволяет построить новую целевую функцию, которая бы в виде штрафа учитывала ограничения целевая функция. Таким образом, задача сводится к минимизации функции
Лагранжа без ограничений. Для е решения используется классический прим записывается условие существования экстремума множитель Лагранжа. Выражения 2 и 3 дают точки подозрительные на экстремум и их ещ надо проверить с помощью достаточных признаков экстремума. Рассмотрим некоторые из этих признаков. 1 Пусть критическая точка подозрительная на экстремум полученная с помощью выражений 2 или 3. Рассмотрим матрицу Гесса матрицу вторых производных
Если эта матрица определена положительно, то точка минимум, а если определена отрицательно, то максимум. Если же матрица Гесса знаконеопределена, то в этой точке экстремума нет, а если полуопределена, то это признак не дат ответа на вопрос. 2 Пусть главный определитель матрицы Гесса го порядка. Если это достаточный признак минимума Если достаточный признак минимума Если же в определителях знаки и , то это необходимый, а не достаточный
признак и вопрос об экстремуме не решается. 3 Наиболее сильным достаточным признаком является следующий. Составим расширенную матрицу Гесса транспонированная матрица. Признак точка соответствует максимуму если начиная с главного определителя порядка , последние определителей матрицы образуют знакопеременный ряд, а знак определителя стоящего на ом месте от конца должен быть Геометрически задача на условный экстремум сводится к тому, что решение находится в той точке, где линия
поверхность определяющая функцию систему ограничений, касается какой-нибудь линии уровня. Квадратичное программирование. Задачей КП называется такая задача НЛП, когда целевая функция представляет собой сумму линейной и квадратичной формы переменные не старше второй степени, а все ограничения линейные, т. е. эта задача на одну ступень выше ЛП и для решения таких задач используется симплекс-метод.
В нелинейном программировании до конца изучен вопрос существования решения только для задачи выпуклого программирования. Фундаментом является теорема Куна-Такера если функции и выпуклые, то решение задачи НЛП находится в седловой точке для функции Лагранжа, т. е. Поэтому, составляя соответствующую функцию Лагранжа необходимо найти е седловую точку. Геометрически это можно нарисовать если одна координата
и один коэффициент Эта точка должна удовлетворять системе следующих неравенств Итак, точка Куна-Такера позволяет записать условие Куна-Такера и найти седловую точку. Решение задач квадратичного программирования методом Баранкина-Дорфмана. Задачей КП называется следующая задача В матричном виде пусть векторы-столбцы матрица квадратичной формы, которая должна быть симметрична и
положительно-полуопределена. Метод Баранкина-Дорфмана непосредственно основан на применении теоремы Куна-Такера, поэтому условие Куна-Такера в матричной форме для КП выглядит следующим образом Тогда условие Куна-Такера можно записать в следующем виде Неизвестными являются . система линейных уравнений относительно неизвестных решить е, значит найти решение задачи ЛП. нелинейное условие, и поэтому задача сводится к нахождению точки в допустимой области, чтобы
выполнилось . Введм новый вектор и . Окончательно условие Куна-Такера будет выглядеть так Метод Баранкина-Дорфа заключается в следующем находится допустимый вектор , удовлетворяющая выражению 1 и проверяется условие 2. Далее выбирается новое базисное решение, причм оно выбирается так, чтобы величина вс время уменьшалась. Для этого используется модифицированная симплекс-таблица, в которой генеральный элемент находится минимизацией
выпуклой функции т. е. мы решаем задачи 1 и 3, а не 1 и 2. В симплекс-таблице записывается в качестве базисных переменных, все переменные. Запишем строку базисных переменных где и свободные переменные. Если строка соответствует свободным переменным, то в строке одна единица и остальные нули. Для выбора генерального элемента используются следующие элементы, которые записываются в дополнительные
строки Можно показать, что новое значение По определению , поэтому должно быть меньше нуля, так как хотим, что бы оно было меньше . Рассмотрим величину величина вторая производная функции , которая выпукла вниз, и поэтому , значит, надо выбрать тот столбец для которого , а строку надо выбрать ту, для которой вычисляется величина . Пример Запишем все матрицы, которые нам нужны Запишем условие Куна-Такера, определяемое выражением 1
Чтобы записать симплекс-таблицу надо выделить базис. Для получения первого базисного решения используется любой метод, например, метод Гаусса. Можно использовать метод, который использует симплекс-процедуры. Для любых задач можно и подобрать первое базисное решение. Мы подберм такое, чтобы сразу получить опорное решение
Запишем симплекс-таблицу по методу Баранкина-Дорфмана таблица 1. Симплекс преобразования строку умножаем на , а столбец на . Порядок строк нарушать нельзя. Недостаток метода иногда встречаются задачи, когда все . Значит мы будем переходить в новую вершину и значение будет увеличиваться, т .е. в соседних вершинах значение больше мы идм по соседним вершинам в симплекс-методе.
В этом случае идм на временное ухудшение , т .е. идм через мртвую зону. В алгоритме Франца-Вольфа это учтено. Метод проекции градиента для решения задач НЛП. Этот метод предусматривает движение от точки к точке внутри области допустимых решений одним из градиентных методов. Но при выходе точки за пределы ограничений производится процедура возврата очередного приближения на допустимое множество . Т. е. если была задача то проекция ближайшая точка множества ,
лежит на границе области . Точка называется проекцией точки на область , если расстояние . Очевидно, что если точка , то проекция совпадает с . Таким образом, в методе проекции градиента любая последующая точка вычисляется как коэффициент определяющий длину шага, который определяется так же, как и в методе наискорейшего спуска. Такую задачу можно решить методом Золотого сечения
Ньютона. Если на множестве удовлетворяет условию Липтица, означающего ограничения но крутизну изменения функции, т. е тогда полагают , что , которая выбирается как любое число из интервала если известна минимальная константа Липтица, то берут . Определение проекции точки является самостоятельной задачей НЛП. Eсли область определнная линейными ограничениями, то это будет задачей квадратичного программирования. Во многих случаях определение проекции возможно из практических соображений, например, если шар.
Иногда, как в примере с шаром, нахождение кратчайшего расстояния приводит к задаче на условный экстремум В случае с шаром Методы возможных направлений Гаус-Зойтендейка. В методах возможных направлений переход от точки к точке осуществляется по направлению , необязательно вдоль градиента. При этом движение вдоль должно быть таким, что бы новая точка принадлежала области . Направление, удовлетворяющее этому условию, называется возможным или допустимым
Таких направлений множество среди возможных направлений выбирают такое, для которого скалярное произведение градиентов в точке и этого направления меньше нуля. Такое направление называется подходящим. Таких направлений в общем случае так же множество. Зойтендейк предложил выбирать то, которое максимально уменьшает значение целевой функции ограничение нашей задачи В общем случае, на каждом шаге анализируется не только значение градиентов целевой функции,
но и значение градиентов активных ограничений. Активными называются те ограничения, которые находятся вблизи ой точки. В какой-то начальной точке определяем множество индексов , таких что . Пусть градиент целевой функции, градиент функции ограничений, номер ограничения. Тогда ищут , такое, что . Тогда надо найти , такое, что . Для этого сначала определяют , где корень уравнения . выбирается из условия прохода до противоположной
границы. Это разумно, когда точка вне области. Затем вычисляется , где , здесь корень уравнения . Т. е. определяет длину шага до точки, где градиент равен нулю. Если нет решения выражения , то , и выбирается из условия не выхода из области, а выбирается из условия попадания в экстремум. Кроме этого, при решении вспомогательной задачи , используются различные условия нормировки самое распространнное. Метод Зойтендейка для выпуклой задачи не гарантирует сходимость за
конечное число шагов для квадратичной задачи гарантируется сходимость за конечное число шагов с применением условия сопряжнности градиентов. Методы экспертных оценок. Во многих практических задачах при принятии решения возникает принципиальная сложность оценить альтернативы. Например, надо дать оценку качества конкретной физической системы компьютера, станка. Количество параметров, которые влияют на оценку системы так велико и они настолько разнообразны, что
невозможно раз и навсегда задать какой-то способ установки соответствия между качеством системы и числом. В этом случае прибегают к методу экспертных оценок. В этом методе решаются следующие задачи Необходимо построить множество возможных и допустимых альтернатив решения Сформировать набор аспектов, существующих для оценки альтернатив Определяется критериальное пространство Необходимо упорядочить альтернативы по аспектам
Получит оценку альтернатив по критериям отобразить множество допустимых решений в критериальном пространстве. Все эти задачи часть общей задачи оценивания сопоставления числа некоторой альтернативе. Метод основан на использовании экспертных процедур. Общая схема экспертизы такова саму оценку выполняют люди, специалисты в предметной области, которые называются экспертами. Для проведения самой экспертизы привлекается консультант.
Он определяет множество альтернатив, а иногда и вспомогательное множество для экспертизы. Каждый эксперт выбирает свою оценку и передат е консультанту. Эта оценка обрабатывается по очень сложной схеме и получается единая для всех экспертов оценка для каждой альтернативы. Затем по определнному правилу выбирается оптимальная оценка консультантом. В схеме экспертизы заложен блок, который отвечает за оценку согласованности мнения экспертов или оценку
компетентности экспертов. Эксперты могут взаимодействовать друг с другом в одних видах экспертизы, либо наоборот, отделяются друг от друга в других методах. В известном методе экспертизы Делфи, экспертам вновь предлагаются результаты экспертизы и просят посмотреть на них и призадуматься. В методе Делфи устанавливается обратная связь при экспертизе. Типы задач оценивания. Оценивание составление альтернатив какого-то вектора евклидова пространства.
1 Пусть некоторая альтернатива в множестве альтернатив Имеется критериев, тогда требуется каждой альтернативе сопоставить некоторый вектор . Это общая задача оценивания. 2 Пусть критерии, учитываемые при выборе. Эти критерии надо установить по возможности, т. е. здесь оценивается система критериев. Система этих критериев сопоставляется перестановке натуральных чисел.
Это задачи раипсирования. 3 Пусть некоторое множество разбито на подмножеств и для какой-то альтернативы необходимо указать, какому подмножеству она принадлежит, т. е. сопоставляется конкретное подмножество. Это задача классификации. 4 Пусть отрезок, длину которого надо измерить т. е. отрезку надо сопоставить действительное число. Это самая простая и самая распространнная задача оценивания. Обозначим исходное множество допустимых оценок множество допустимых оценок для экспертов тип взаимодействия
между экспертами наличие обратной связи алгоритм обработки. Все методы обработки экспертной информации можно разбить на три вида 1 Статистический метод 2 Алгебраический метод 3 Методы шкалирования. 1 Оценка каждого эксперта рассматривается, как случайная величина. Обработка производится на основе методов математической статистики, которая позволяет определить согласованность
методов экспертов и значимость, т. е. качество экспертизы. Экспертиза 1 численная оценка. Каждой альтернативе ставится в соответствие одно число. эксперты изолированы обратная связь отсутствует количество экспертов веса экспертов при отсутствии информации компетентности числовые оценки экспертов. Степень согласованности определяется выражением дисперсия Применяется экспертиза. Экспертиза 2 каждый эксперт дат три оценки для числа соответственно, оптимистическая,
наиболее вероятная и пессимистическая оценка эксперта веса, которые можно доверять данной оценкой. Обычно и степень согласованности определяется дисперсией коэффициент неуверенности эксперта в свом ответе. Метод Делфи для численной оценки. эксперты изолированы экспертам предоставляется величина медианы задатся следующим образом весь интервал допустимых значений оцениваемой величины разбивается на интервалов . Эксперт оценивает вероятность попадания величины в каждый из интервалов.
Затем оценивается мнение экспертов о попадании оцениваемой величины в каждый из интервалов Результирующая оценка является медианой распределения. Эту величину снова дают экспертам, которые вновь записывают оценку до тех пор, пока не уменьшается в 1,6 раза по сравнению с первоначальным заданием.