Cтраница 1
Марковские процессы принятия решений или управляемые марковские процессы уже давно привлекают внимание математиков, как интересная, содержательная и вместе с тем трудная область творчества. В то же время эти процессы используются для решения многих задач, встречающихся при исследовании операций, в системном анализе, теории надежности, диагностике, управлении запасами, прогнозировании, причем применение оптимальных стратегий управления, получаемых с помощью алгоритмов, разработанных в рамках теории управляемых марковских процессов, может дать весьма значительный экономический эффект при решении задач практики. Поэтому аппарат теории управляемых процессов становится рабочим инструментом все возрастающего числа специалистов, работающих в указанных областях. [1]
Марковские процессы принятия решения широко используются в теории систем, исследовании операций, теории надежности, теории управления и многих других прикладных областях знаний. [2]
Марковские процессы принятия решений с переоценкой впервые были рассмотрены Ховардом [63], им же был предложен итерационный алгоритм нахождения стратегий. [3]
Рассмотрим марковский процесс принятия решений специального вида. Именно, мы предположим, что система имеет одно поглощающее состояние при любом решении. Предположим затем, что состояние 1 достижимо из любого другого состояния. Строго это предположение выглядит так. [4]
При изучении марковских процессов принятия решений без переоценки используются два подхода: 1) случай р1 считается предельным случаем неравенства Р1; 2) непосредственно рассматривается стационарный средний доход за единицу времени. Мы детально изложим первый подход и лишь кратко опишем второй. [5]
Общие построения и свойства марковских процессов принятия решений представляют большой интерес не только для математиков-прикладников и лиц, занимающихся исследованием операций, но и для статистиков, экономистов и инженеров. Помимо рассмотрения общетеоретических вопросов, в книге приводятся алгоритмы нахождения оптимальных решений и даются некоторые наиболее важные обобщения исходных постановок. Например, изучаются полумарковские и общие процессы принятия решений, а также стохастические игры. Все эти модели тесно примыкают к марковским процессам принятия решений. [6]
Основной целью при изучении марковских процессов принятия решений является нахождение стратегии, максимизирующей заданную целевую функцию, и определение соответствующего максимального значения, а математическим аппаратом исследования служит теория дискретных цепей Маркова. [7]
Формулировка задачи линейного программирования применительно к марковским процессам принятия решений с конечным временем планирования была дана Дерманом и Клейном [43], но мы ее здесь не рассматриваем. [8]
В этой и следующей главах будут рассмотрены марковские процессы принятия решений без переоценки в случае бесконечного времени планирования. [9]
Таким образом, алгоритм линейного программирования для общих марковских процессов принятия решений строится с помощью лемм 2.3 и 3.6 - 3.8. Заметим, что двойственные переменные u ( f) и v ( f) являются также симплекс-множителями. Используя их, получаем симплексный критерий, соответствующий процедуре улучшения решения в итерационном алгоритме. Возрастание среднего дохода по симплексному критерию непосредственно доказывается без использования свойств линейных программ. [10]
Покажем, что задача нахождения оптимальной стратегии для марковского процесса принятия решений с одним эргодическим классом может быть сформулирована в виде задачи линейного программирования. [11]
Ниже мы приведем итерационный алгоритм нахождения стратегий для марковских процессов принятия решений с переоценкой, который был впервые предложен Ховардом [63] и поэтому иногда называется итерационным алгоритмом Ховарда. [12]
Ниже будет сформулирована задача линейного программирования применительно к марковским процессам принятия решений ( соотношение между итерационным алгоритмом нахождения стратегий и алгоритмом линейного программирования рассматривается в следующем разделе) и приведен алгоритм ее решения. [13]
В разделе 1 4 было показано, что для марковских процессов принятия решений с переоценкой итерационный алгоритм и алгоритм линейного программирования эквивалентны с математической точки зрения. [14]
Определение 2.1. Пусть при любой стратегии цепь Маркова, описывающая марковский процесс принятия решений, эргодична. Такой процесс называется процессом с одним эргодическим классом. [15]