Тема 9.7 СИСТЕМА ПРИНЯТИЯ РЕШЕНИЙ
Удобным методом описания причинно-следственной связи служит, например, система уравнений. Однако существование причинно-следственной связи, или, иначе говоря, системы, не предполагает в общем случае существования определяющей процедуры или конструктивного описания, такого, какое дается системой уравнений. В действительности в весьма важном случае, когда изучается структурная взаимосвязь подсистем, их конструктивное описание несущественно. Кроме того, конструктивное описание системы может быть задано в неявном виде, т. е. отклик (выход) системы при данных начальных условиях задается как неявная функция входа.
Особенно удобно определять систему с помощью задачи “принятия решения”, а именно систему S Х* Y определяют так, что пара (х, у) принадлежит S тогда и только тогда, когда у является решением определенной задачи, конкретизация которой осуществляется посредством задания х. Мы будем часто предполагать, что определенная таким образом система S является функциональной. В этом случае можно считать, что система содержит алгоритм решения, и мы будем называть ее “решающей” системой, “решателем” или системой принятия решений.
Возможно, наиболее удачным примером системы принятия решений (“решающей” системы) служит система, которая действует таким образом, чтобы минимизировать значение некоторого заданного критерия качества функционирования G. Пусть Х — множество непрерывных вещественных функций на отрезке [0, 1]. Пусть для каждого x Х задана задача оптимизации Dx1: минимизировать
при ограничениях
где a, b и с > 0 - заданные константы, а т и у — функции, интегрируемые с квадратом на отрезке [0, 1]. Решение задачи Dxсводится к решению уравнений
(1)
Очевидно, для каждого х Х существует единственный элемент у L2[0, 1], определяемый уравнениями (1), который дает решение задачи Dx. Таким образом, имеется система S Х * L2[0, 1], такая, что для любых х Х и y L2[0, 1] пара (x, y) принадлежит системе S в том и только в том случае, если у представляет собой решение задачи Dxдля некоторого начального условия у (0) =.
Рассмотрим упругую систему, описанную ранее в примере . Для каждой функции х (t), задающей внешнюю силу на промежутке Т = [0, ), смещение у в соответствии с принципом Гамильтона определяется решением задачи Dx: найти у, удовлетворяющее условию
где обозначает первую вариацию. Решение этой задачи дается уравнением Эйлера
из которого следует уравнение движения. Следовательно, решением задачи Dxявляется смещение у (t). Иными словами, однозначное отображение S: Х -> У. описываемое уравнением смещения и начальным условием = (у (0), у*(0)), таково, что для любого х Х образ y=S(х) служит решением задачи Dx. Очевидно, что система S может быть описана двумя различными, но эквивалентными способами: один способ обеспечивает конструктивное описание с помощью уравнения движения, а второй основан на принципе Гамильтона и состоит в том, что задается семейство подлежащих решению задач Dx, х X.
Чтобы определить решающую систему, постараемся сначала дать читателю более конкретное представление относительно “решаемой” задачи. Ниже рассматриваются два вида таких задач: задача оптимизации и задача нахождения удовлетворительных решений.
Пусть g: Х —> V — функция, отображающая произвольное множество Х в множество V, частично или полностью упорядоченное отношением . Задача оптимизации состоит в следующем:
дано подмножество Xf X, требуется найти х* Xf, такое, что для всех х из Xf
(2)
Множество Х есть множество всех решений, а Xf— множество допустимых решений. Функция g называется целевой функцией, а множество V — множеством платежей. Задача оптимизации определяется парой (g, Xf). Элемент x* из Xf, удовлетворяющий соотношению (2) для всех х из Xf', называется решением задачи (g, Xf).
Часто функция g задается двумя функциями P: X—>Y и G: Х* У > V:
В этом случае Р называется выходной функцией, или моделью управляемого процесса, а G называется оценочной функцией, или функцией качества. Задача оптимизации может быть тогда определена тройкой (Р, G, Xf) или парой (Р, G), если Xf= X. Название “модель управляемого процесса” подразумевает тот факт, что задача оптимизации, определенная тройкой (Р, G, Xf), является задачей управления, где принимаемые решения влияют на процесс, выход которого в свою очередь влияет на целевую функцию или платеж. Вопрос о связи модели Р с реальным процессом выходит за рамки нашего рассмотрения. В общем случае само существование процесса может быть всего лишь допущением, необходимым для того, чтобы сформулировать задачу оптимизации и, таким образом, иметь возможность определить систему как некий “решатель” (задачи оптимизации) или как некоторую систему принятия решений.
Пусть Х и — произвольные множества, а g — функция, отображающая Х* в некоторое множество V, частично или полностью упорядоченное отношением , и пусть — функция, переводящая в V, т. е. g: Х* -> V и : -> V. Задача нахождения удовлетворительных решений заключается в следующем: дано подмножество Xf X, требуется найти такое х* из Xf, что для всех из
(3)
Множество называется множеством неопределенностей, — функцией допустимости, а неравенство (3) — критерием удовлетворительности. Остальные элементы задачи имеют тот же смысл, что и в задаче оптимизации. Четверка (g, , Xf, ) определяет задачу нахождения удовлетворительных решений, а любое х* из Xf, для которого (3) выполняется при всех из , является решением этой задачи.
Множество неопределенностей иногда называют множеством возмущений, так как оно представляет собой множество всех факторов, которые могут повлиять на результирующие характеристики системы. Если целевая функция g задана в виде выходной функции Р: Х * —>Y и оценочной функции G: Х * * Y -> V,
то множество является множеством всех возможных факторов, влияющих на получаемый результат решения х. Заметим, что благодаря высокому уровню абстракции множество охватывает и так называемые параметрические, и структурные неопределенности. Тогда функция определяет “максимально допустимое” значение оценочной функции. Решение х* считается удовлетворительным, если оно приводит к значению оценочной функции, не превосходящему определенного уровня (w) при любых w из множества неопределенностей .
Пусть функция Р: R * —> R задается уравнением
где — множество {-1,+ 1} состоящее только из двух элементов. Пусть функция допустимости : —> R — константа, (w) = 1, для всех w из , а качество функционирования оценивается абсолютным значением выхода
Решением задачи нахождения удовлетворительных решений тогда будет управление т из R, такое, что
для всех w из . Такое управление называется “удовлетворительным”.
Очевидно, удовлетворительным управлением является т*= 0. Однако следует отметить, что удовлетворительное управление m*= 0 не будет оптимальным для некоторых возмущений. А именно: если w= -1, управлением, минимизирующим | Р (т, w) |, будет т* (-1) = -1, в то время как для w =+ 1 оптимальное управление т* (1) = 1. Этот пример показывает, что решения задачи нахождения удовлетворительных решений могут быть не оптимальными для некоторых возмущений. Более того, ни одно из оптимальных решений не является удовлетворительным; для т = 1 получаем | Р (1, 1) | =2, что нарушает допустимый предел, и аналогично для m= -1 имеем | Р (—1,—1) | = 2, что также не удовлетворяет условию допустимости. На этом примере становится ясным различие между оптимальным и удовлетворительным решениями.
Рассмотрим задачу выбора разделяющей (решающей) функции для задачи распознавания при наличии канала с помехами. Предположим, что А = {a1, a2} — множество сообщений отправителя, а В = {b1, b2, b3} — множество сообщений, принимаемых получателем. Они не совпадают из-за наличия шумов в канале передачи. Тогда задача распознавания формулируется следующим образом:
пусть принято сообщение bi; как определить, используя статистическую информацию о канале, какое сообщение, a1или a2, было передано с другого конца канала? Другими словами, задача состоит в том, чтобы выбрать функцию т: В —> А, такую, что если получено сообщение bi, то за отправленное сообщение принимается aj= т (bi).
Рассмотрим множество М всех функций, отображающих В в А. Необходимо описать критерии, помогающие выбрать из множества М ту функцию m, которую следует использовать в качестве разделяющей функции. Один из критериев можно сформулировать, если использовать байесовский подход.
Обозначим через р[аi] априорную вероятность того, что было отправлено сообщение аi; предположим, что р[а1] = w, и, следовательно, р [а2] = 1 — w. Пусть р [bi| aj]— условная вероятность получения сообщения biпри условии, что было отправлено сообщение аj. Условные вероятности задаются следующей таблицей:
Для удобства обозначим через !т отрицание результата применения данной разделяющей функции т; если т (bi) = а1, то !т (bi) = а2, и наоборот.
Вероятность вынесения неправильного решения равна Р [!т (bi)]. Используя теорему Байеса, получим, что условная вероятность принятия неправильного решения, если принято сообщение bi, дается формулой
Теперь можно определить функцию потерь
где w: A —> R означает штраф за ошибку. Проблема выбора разделяющей функции может быть тогда сформулирована следующим образом: задана априорная вероятность w, требуется найти !т из М, минимизирующую функцию потерь.
В случае когда w=1/2 и функция штрафа w такова, что w (a1) = 1 и w (а2) = 2, оптимальная разделяющая функция !т есть !т (b1) = a1, !т (b2) = а2, !т (b3) =a2. Допустим, что априорные вероятности точно не известны, но w = р (a1) лежит в известном диапазоне, например принадлежит отрезку = (2/5, 3/5). Тогда, если задать уровень , где — постоянное число, можно представить выбор разделяющей функции в виде задачи нахождения удовлетворительных решений, а именно: найти такое т из М, что для всех w из
Удовлетворительным решением для = 5/3 тогда будет т* (b1) = a1, m* (b2) =a2, т* (b3) =a2. Заметим, что в данном случае удовлетворительное и оптимальное решения совпадают.
Когда мы рассматриваем задачу нахождения удовлетворительного решения в общем виде, отношение в (3) может быть заменено любым отношением вида R V * V. В общем случае задача нахождения удовлетворительных решений заключается в отыскании такого х* из Xf, что для всех w из
где R — некоторое заданное отношение на множестве платежей V; иначе говоря, решение х* из Xfудовлетворяет поставленной задаче, если для любого w из функция g (х, w) связана отношением R с функцией допустимости (w).
“РЕШАЮЩАЯ” СИСТЕМА
Теперь нам нетрудно определить, что подразумевается под системой принятия решений (или “решающей” системой), блок-схема которой представлена на рис. 9.9 .
Рисунок 9.9. Система принятия решений.
Система S = Х * Y называется решающей системой (системой принятия решений), если задано семейство задач Dx, х X, с множеством решений Z и отображение Т: Z --> Y. Для любого элемента x из Х и любого у из Y пара (х, у) принадлежит системе S в том и только в том случае, если существует элемент z Z, такой, что он является решением задачи Dxи Т (z) = у.
В большинстве случаев (хотя и отнюдь не всегда!), которые мы будем рассматривать, выход представляет собой решение поставленной задачи и Z= Y, т. е. Т — тождественное преобразование.
В заключение сделаем следующие замечания, касающиеся решающей системы:
1) Иногда можно дать конструктивное описание такой системы в виде ряда уравнений. Такое описание особенно удобно, если уравнения имеют аналитическое решение. Однако такой алгоритм существует далеко не всегда. В действительности мы требуем только того, чтобы для всякой решающей системы была достаточно точно определена решаемая задача, но не требуем существования какого-либо алгоритма для нахождения решения этой задачи.
2) Всякая система, формализованная посредством моделей “вход — выход”, может быть представлена в виде решающей системы, и наоборот. Аналогично обстоит дело, например, в классической физике, где явление может быть описано и на языке законов движения, и на языке вариационных принципов.
Следует подчеркнуть, что системы, обладающие иерархической структурой, отличаются от всех прочих тем, что функции их подсистем наиболее естественно интерпретируются как поиск и принятие решений. Именно такими системами мы и будем в дальнейшем интересоваться.
3) Задача оптимизации является, очевидно, частным случаем задачи нахождения удовлетворительных решений и получается из последней, если определить (w) как минимум g (х, w) на Xf* {w}. В то же время решение любой задачи отыскания удовлетворительных решений может быть получено как решение задачи оптимизации с соответствующим образом выбранной целевой функцией. Какой формулировкой пользоваться — в значительной степени вопрос вкуса, но мы все-таки будем различать эти два типа задач в связи с некоторыми методологическими соображениями, на которых мы не станем здесь подробно останавливаться. Также мы не будем останавливаться на понятии цели, т.к. оноочень сложно в определении. Приведем лишь один пример:
Для человека целью можно считать достижение “счастья”, хотя, что это значит, знает, пожалуй, только он сам, а пути, ведущие к счастью, ему заранее не известны. Преследуя эту цель, он пробует стратегии, которые дают надежду на ее достижение. Он может попытаться получить хорошее образование, постараться разбогатеть, жениться или испробовать любую другую комбинацию стратегий, но ни одна из этих стратегий не гарантирует ему достижения цели. После нескольких попыток он может убедиться в тщетности своего “целенаправленного” поведения.
Это не значит, что ситуации. связанные с целенаправленной деятельностью, в принципе не могут быть формализованы. Если такая формализация возможна, она неизбежно приведет к проблеме принятия решений. Более того, целенаправленное поведение и процесс целенаправленного поиска в сущности представляют собой последовательность принимаемых и осуществляемых решений. Переходя далее к “формализованным целям”, мы определяем их через “решаемые задачи”, которые в свою очередь могут быть сведены к задачам оптимизации или задачам поиска удовлетворительных решений. Поэтому, согласно нашей концепции, цель считается достигнутой, когда найдено решение соответствующей задачи.