Марковские случайные процессы с непрерывным временем

Итак, снова модель Марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i-го состояния в j-е состояние), см. рис. 3.1..

Рис. 3.1. Пример графа Марковского процесса с непрерывным временем

Теперь каждый переход характеризуется плотностью вероятности перехода?_ij. По определению:

При этом плотность понимают как распределение вероятности во времени.

Переход из i-го состояния в j-е происходит в случайные моменты времени, которые определяются интенсивностью перехода?_ij.

К интенсивности переходов (здесь это понятие совпадает по смыслу с распределением плотности вероятности по времени t) переходят, когда процесс непрерывный, то есть, распределен во времени.

Зная интенсивность?_ij появления событий, порождаемых потоком, можно сымитировать случайный интервал между двумя событиями в этом потоке.

где?_ij -- интервал времени между нахождением системы в i-ом и j-ом состоянии.

Далее, очевидно, система из любого i-го состояния может перейти в одно из нескольких состояний j, j + 1, j + 2, …, связанных с ним переходами?_ij,?_{ij + 1},?_{ij +2}, ….

В j-е состояние она перейдет через?_ij; в (j + 1)-е состояние она перейдет через?_{ij + 1}; в (j + 2)-е состояние она перейдет через?_{ij + 2} и т. д.

Ясно, что система может перейти из i-го состояния только в одно из этих состояний, причем в то, переход в которое наступит раньше.

Поэтому из последовательности времен:?_ij,?_{ij + 1},?_{ij + 2} и т. д. надо выбрать минимальное и определить индекс j, указывающий, в какое именно состояние произойдет переход.

Рассмотрим пример. Моделирование работы станка. Промоделируем работу станка (см. рис. 3.2.), который может находиться в следующих состояниях: S₀ -- станок исправен, свободен (простой); S₁ -- станок исправен, занят (обработка); S₂ -- станок исправен, замена инструмента (переналадка)?₀₂ <?₂₁; S₃ -- станок неисправен, идет ремонт?₁₃ <?₃₀.

Зададим значения параметров?, используя экспериментальные данные, получаемые в производственных условиях:?₀₁ -- поток на обработку (без переналадки);?₁₀ -- поток обслуживания;?₁₃ -- поток отказов оборудования;?₃₀ -- поток восстановлений.

Реализация будет иметь следующий вид (рис. 3.2.).

Рис. 3.2. Пример моделирования непрерывного марковского процесса с визуализацией на временной диаграмме (желтым цветом указаны запрещенные, синим -- реализовавшиеся состояния)

В частности, из рис. 3.2. видно, что реализовавшаяся цепь выглядит так: S₀--S₁--S₀--… Переходы произошли в следующие моменты времени: T₀--T₁--T₂--T₃--…, где T₀ = 0, T₁ =?₀₁, T₂ =?₀₁ +?₁₀.

Очень часто аппарат Марковских процессов используется при моделировании компьютерных игр

1.4. Цепь Маркова

случайный процесс марковский вероятность

Представим, что производится последовательность испытаний.

Определение. Цепью Маркова называют последовательность испытаний, в каждом из которых появляется одно и только одно из несовместных событий полной группы, причем условная вероятность того, что в -м испытании наступит событие, при условии, что в -м испытании наступило событие, не зависит от результатов предшествующих испытаний.

Например, если последовательность испытаний образует цепь Маркова и полная группа состоит из четырех несовместных событий, причем известно, что в шестом испытании появилось событие, то условная вероятность того, что в седьмом испытании наступит событие, не зависит от того, какие события появились в первом, втором, …, пятом испытаниях.

Заметим, что независимые испытания являются частным случаем цепи Маркова. Действительно, если испытания независимы, то появление некоторого определенного события в любом испытании не зависит от результатов ранее произведенных испытаний. Отсюда следует, что понятие цепи Маркова является обобщением понятия независимых испытаний.

Часто при изложении теории цепей Маркова придерживаются иной терминология и говорят о некоторой физической системе, которая в каждый момент времени находится в одном из состояний:, и меняет свое состояние только в отдельные моменты времени то есть система переходит из одного состояния в другое (например из в). Для цепей Маркова вероятность перейти в какое-либо состояние в момент зависит только от того, в каком состоянии система находилась в момент, и не изменяется от того, что становятся известными ее состояния в более ранние моменты. Так же в частности, после испытания система может остаться в том же состоянии («перейти» из состояния в состояние).

Для иллюстрации рассмотрим пример.

Пример 1. Представим, что частица, находящаяся на прямой, движется по этой прямой под влиянием случайных толчков, происходящих в моменты. Частица может находиться в точках с целочисленными координатами:; в точках и находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью и влево с вероятностью, если только частица не находится у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка между стенками. Здесь мы видим, что этот пример блуждания частицы представляет собой типичную цепь Маркова.

Таким образом, события называют состояниями системы, а испытания - изменениями ее состояний.

Дадим теперь определение цепи Маркова, используя новую терминологию.

Цепью Маркова с дискретным временем называют цепь, изменение состояний которой происходит в определенные фиксированные моменты времени.

Цепью Маркова с непрерывным временем называют цепь, изменение состояний которой происходит в любые случайные возможные моменты времени.

1.5 Однородная цепь Маркова. Переходные вероятности. Матрица перехода

Определение. Однородной называют цепь Маркова, если условная вероятность (переход из состояния в состоянии) не зависит от номера испытания. Поэтому вместо пишут просто.

Пример 1. Случайное блуждание. Пусть на прямой в точке с целочисленной координатой находится материальная частица. В определенные моменты времени частица испытывает толчки. Под действием толчка частица с вероятностью смещается на единицу вправо и с вероятностью - на единицу влево. Ясно, что положение (координата) частицы после толчка зависит от того, где находилась частица после непосредственно предшествующего толчка, и не зависит от того, как она двигалась под действием остальных предшествующих толчков.

Таким образом, случайное блуждание? пример однородной цепи Маркова с дискретным временем.

Далее ограничимся элементами теории конечных однородных цепей Маркова.

Переходной вероятностью называют условную вероятность того, что из состояния (в котором система оказалась в результате некоторого испытания, безразлично какого номера) в итоге следующего испытания система перейдет в состояние.

Таким образом, в обозначении первый индекс указывает номер предшествующего, а второй? номер последующего состояния. Например, - вероятность перехода из второго состояния в третье.

Пусть число состояний конечно и равно.

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

Так как в каждой строке матрицы помещены вероятности событий (перехода из одного и того же состояния в любое возможное состояние), которые образуют полную группу, то сумма вероятностей этих событий равна единице. Другими словами, сумма переходных вероятностей каждой строки матрицы перехода равна единице:

Приведем пример матрицы перехода системы, которая может находиться в трех состояниях; переход из состояния в состояние происходит по схеме однородной цепи Маркова; вероятности перехода задаются матрицей:

Здесь видим, что если система находилось в состоянии, то после изменения состояния за один шаг она с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,2 перейдет в состояние, то после перехода она может оказаться в состояниях; перейти же из состояния в она не может. Последняя строка матрицы показывает нам, что из состояния перейти в любое из возможных состояний с одной и той же вероятностью 0,1.

На основе матрицы перехода системы можно построить так называемый граф состояний системы, его еще называют размеченный граф состояний. Это удобно для наглядного представления цепи. Порядок построения граф рассмотрим на примере.

Пример 2. По заданной матрице перехода построить граф состояний.

Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.

S1

0,2 0,7

S2 0,4 S4

0,6 0,5

0,1 0,5

S3

На графе не отмечаются вероятности перехода системы из одного состояния в то же самое. При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы.

1.6 Равенство Маркова

Определение. Обозначим через вероятность того, что в результате шагов (испытаний) система перейдет из состояния в состояние. Например, - вероятность перехода за 10 шагов из второго состояния в пятое.

Подчеркнем, что при получим переходные вероятности

Поставим перед собой задачу: зная переходные вероятности найти вероятности перехода системы из состояния в состояние за шагов.

С этой целью введем в рассмотрение промежуточное (между и) состояние. Другими словами, будeм считать, что из первоначального состояния за шагов система перейдет в промежуточное состояние с вероятностью, после чего за оставшиеся шагов из промежуточного состояния она перейдет в конечное состояние с вероятностью.

По формуле полной вероятности, получим

. (1)

Эту формулу называют равенством Маркова.

Пояснение. Введем обозначения:

- интересующее нас событие (за шагов система перейдет из начального состояния в конечное), следовательно,;? гипотезы(за шагов система перейдет из первоначального состояния в промежуточное состояние), следовательно,? условная вероятность наступления при условии, что имела место гипотеза (за шагов система перейдет из промежуточного состояния в конечное), следовательно,

По формуле полной вероятности,

()

Или в принятых нами обозначениях

что совпадает с формулой Маркова (1).

Зная все переходные вероятности т.е зная матрицу перехода из состояния в состояние за один шаг, можно найти вероятности перехода из состояния в состояние за два шага, следовательно, и саму матрицу перехода; по известной матрице можно найти матрицу перехода из состояния в состояние за три шага, и т.д.

Действительно, положив в равенстве Маркова

,

Получим

,

Или

(2)

Таким образом, по формуле (2) можно найти все вероятности следовательно, и саму матрицу. Поскольку непосредственное использование формулы (2) оказывается утомительным, а матричное исчисление ведет к цели быстрее, напишу вытекающие из (2) соотношение в матричной форме:

Положив в (1), аналогично получим

В общем случае

Теорема 1. При любых s, t

(3)

Доказательство. Вычислим вероятность по формуле полной вероятности (), положив

(4)

Из равенств

и

следует

Отсюда из равенств (4) и

получим утверждение теоремы.

Определим матрицу В матричной записи (3) имеет вид

(5)

Так как то где? матрица вероятности перехода. Из (5) следует

(6)

Результаты, полученной в теории матриц, позволяют по формуле (6) вычислить и исследовать их поведение при

Пример 1. Задана матрица перехода Найти матрицу перехода

Решение. Воспользуемся формулой

Перемножив матрицы, окончательно получим:.

1.7 Стационарное распределение. Теорема о предельных вероятностях

Распределение вероятностей в произвольной момент времени можно найти, воспользовавшись формулой полной вероятности

(7)

Может оказаться, что не зависит от времени. Назовем стационарным распределением вектор, удовлетворяющий условиям

,

(8)

где вероятности перехода.

Если в цепи Маркова то при любом

Это утверждение следует по индукции из (7) и (8).

Приведем формулировку теоремы о предельных вероятностях для одного важного класса цепей Маркова.

Теорема 1. Если при некотором >0 все элементы матрица положительны, то для любых, при

, (9)

где стационарное распределение с а некоторая постоянная, удовлетворяющая неравенством 0<h<1.

Так как, то по условию теоремы из любого состояния можно попасть в любое за время с положительной вероятностью. Условия теоремы исключает цепи, являющиеся в некотором смысле периодическими.

Если выполнить условие теоремы 1, то вероятность того, что система находится в некотором состоянии, в пределе не зависит от начального распределение. Действительно, из (9) и (7) следует, что при любом начальном распределении,

Рассмотрим несколько примеров цепи Маркова, которых условия теоремы 1, не выполнены. Нетрудно проверить, что такими примерами является примеры. В примере вероятности перехода имеют приделы, но эти приделы зависят от начального состояния. В частности, при 0<<,

В других примеров приделы вероятностей при очевидно, не существуют.

Найдем стационарное распределение в примере 1. Нужно найти вектор удовлетворяющий условиям (8):

,

,

;

Отсюда, Таким образом, стационарное распределение существует, но не все координаты векторы положительны.

Для полиномиальной схемы были введены случайные величины, равные чесу исходов данного типа. Введем аналогичные величины для цепей Маркова. Пусть? число попадания системы в состояние за время. Тогда частота попаданий системы в состояние. Используя формулы (9), можно доказать, что при сближается с. Для этого нужно получить асимптотические формулы для и и воспользоваться неравенством Чебышева. Приведем вывод формулы для. Представим в виде

(10)

где, если, и в противном случае.

Так как,то, воспользовавшись свойством математического ожидания и формулой (9), получим

.

Втрое слагаемое в правой части этого равенства в силу теоремы 1 является частной суммой сходящегося ряда. Положив, получим

(11)

Поскольку

Из формулы (11), в частности, следует, что

при

Так же можно получить формулу для которая используется для вычисления дисперсии.

II глава. Марковские процессы

Рассмотрим систему, которую в любой момент времени можно описать одним из состояний,, для примера.

Через определенный промежуток времени система может изменить свое состояние или остаться в прежнем состоянии согласно вероятностям, указанным для данных состояний. Моменты времени, когда мы регистрируем состояние системы, обозначим как а состояние в момент времени мы обозначим. Полное описание рассмотренной выше системы должно содержать текущее состояние (в момент времени) и последовательность всех предыдущих состояний, через которые прошла система. В отдельных случаях описание системы сводится к указанию текущего и предыдущего состояния, т.е.

(1.1)

Кроме того, мы также полагаем что процессы, протекающие в системе, не зависят от времени, о чем нам говорит правая часть формулы (1.1). Таким образом, систему можно описать матрицей вероятностей в виде

(1.2)

где - это вероятность перехода из состояния в состояние в данный момент времени. Поскольку эти вероятности характеризуют случайный процесс, они имеют обычные свойства, т.е.

(1.3)

Описанный выше случайный процесс можно назвать открытой Марковской моделью, поскольку выходной сигнал модели - это последовательность состояний регистрируемых во времени. Каждое состояние соответствует определенному (наблюдаемому) событию.

Теперь рассмотрим простую Марковскую модель погоды, у которой будет всего три состояния. Предполагается, что мы один раз в день (например, в полдень), смотрим в окно и регистрируем в журнале текущее состояние погоды. Мы условились, что лишь одно из трех ниженазванных состояний в день мы записываем в журнал:

· Состояние №1: дождь (или снег)

· Состояние №2: пасмурно

· Состояние №3: ясно

Матрица вероятностей изменения погоды имеет вид

(1.4)

Так как погода в первый день () ясная (состояние 3), мы можем задать себе вопрос: какова вероятность (согласно нашей модели), что следующие 7 дней будет именно "ясно - ясно - ясно - дождь - дождь - ясно - пасмурно - ясно"? Точнее сказать, для данной последовательности состояний, где соответствует, мы хотим на основе данной модели определить вероятность наблюдения последовательности. Эта вероятность может быть выражена (и вычислена) следующим образом

(1.5)

где - это вероятность того, что начальное состояние системы будет.

Есть и другой интересный вопрос, ответ на который нам даст эта модель: какова вероятность того, что модель сохранит свое состояние в течение ровно дней? Эта вероятность может быть вычислена как вероятность наблюдения следующей последовательности

дает модель, в которой

(1.6)

Величина - это вероятность того, что система будет находиться в состоянии ровно раз подряд. Соответственно, есть функция распределения вероятности для продолжительности пребывания системы в одном состоянии, которая является характеристикой сохранения состояния для Марковской цепи. Зная величины мы можем вычислить среднее время, в течение которого система сохранит свое состояние (используем формулу математического ожидания):

(1.7)

(1.8)

Ожидается, что солнечная погода вероятнее всего простоит дней, пасмурная - 2.5 дня, а вот дождливая погода, согласно нашей модели, вероятнее всего продержится 1.67 дня.

 

24 §1 Цепи Маркова

Основные понятия.

В этой главе мы будем рассматривать некоторую систему ξ(t), которая в любой момент времени может находиться в одном из состояний S₁, S₂, …, S_k, и ξ (t) – это номер состояния, в котором система находится в момент t. Причём состояние системы отслеживается только в отдельные моменты времени {0, Dt, 2×Dt, 3×Dt,…}. В эти моменты времени система может переходить из одного состояния в другое. Т.е. время в этой модели дискретно.

Пример 1. Рассмотрим состояния, в которых может находиться студент:

S₁ – студент учится и не получает стипендию;

S₂ – студент учится и получает стипендию;

S₃ – студент отчислен.

Состояние студента может меняться после сессии раз в семестр, т.е. шаг Dt в примере – семестр, и здесь t – номер семестра.

Рассмотрим вероятность: P{ξ(t₁) = i₁, ξ(t₂) = i₂,…, ξ(t_r) = i_r }.

Определение 1. Случайный процесс называется однородным (стационарным) или стандартным, если для любых t₁, t₂ … и T>=0 выполняется равенство:

(1.1) P{ξ(t₁) = i₁,…, ξ(t_r) = i_r } = P{ ξ(t₁ + T) = i₁,…, ξ(t_r + T) = i_r}, т.е. вероятность перехода из состояния i₁ с состояние i_r за время T зависит только от величины T и не зависит от положения интервала на временной оси. В дальнейшем мы будем изучать только однородные (стационарные) процессы.

К примеру, стандартным процессом можно считать колебания курсов валют на небольшом отрезке времени.

Обозначим

(1.2) p_ij(t) = P{ξ(t) = j / ξ(0) = i} – вероятность перейти из состояния i в состояние j за t шагов.

Определим также

(1.3) P_ij = P_ij ( 1 ) – вероятность перейти из состояния i в состояние j за один шаг.

Определим также распределение вероятностей в начальный момент времени:

(1.4) p_i⁰ = P{ξ(0) = i}

Определение 2. Однородный процесс с дискретным временем называется Марковским или Марковской цепью с дискретным временем, если выполняется равенство:

(1.5)

Утверждение 1. (Марковское свойство). Пусть дана Марковская цепь с дискретным временем, тогда справедливо равенство:

(1.6) P{ξ(t) = i_t / ξ(t–1) = i_t-1,ξ(t–2) = i_t-2,…, ξ(0) = i₀} = P{ξ(t) = i_t / ξ(t–1) = i_t-1}

Смысл: P(будущее/настоящее и прошлое) = P{будущее/настоящее}, т.е. в Марковских цепях будущее не зависит от прошлого, оно зависит только от настоящего. Такие системы ещё называются системами без памяти.

Часто Марковскую цепь удобно задавать при помощи графа переходов. При построении такого графа каждому состоянию ставится в соответствие вершина. Если из состояния s _i система переходит в состояние s _j с ненулевой вероятностью , то из вершины, соответствующей s _i, проводится стрелка в вершину s _j, помечаемая величиной ; если , то стрелку не проводят.

 

Матрицы переходов.

Определим матрицу переходов за n шагов (1.7) иматрицу переходов за один шаг (1.8) следующим образом:

(1.7) (1.8)

Пример 2. Воспользуемся состояниями студента из Примера 1. Из многолетнего опыта известно, что матрица переходов за один шаг:

Пусть начальное распределение: P⁰= (0,6; 0,4; 0). Найти вероятность того, что студент получает стипендию в течении двух первых семестров.

Решение: Надо найти: P{ξ(1) = 1, ξ(2) = 1} = {1.7} = P₁⁰ × P₁₁ × P₁₁ = 0,4 ×0,4× 0,79.

Утверждение 2. Пусть дана Марковская цепь с дискретным временем с состояниями S₁ … S_k, тогда справедливо равенство:

(1.9)

Доказательство: Формула полной вероятности: . Обозначим через A = {система перешла из состояния i в состояние j за (s + t) шагов}, H_r = {система перешла из состояния i в состояние r за S шагов}.

P(A) = P_{i j}(s + t) (*)

P(H_r) = P_{i r}(s) (* *)

P(A / H_r) = P_{r j}(t) (* * *)

Подставим (*), (**), (***) в формулу полной вероятности и получим (1.9)

 

Теорема 1. (Основное свойство Марковских цепей с дискретным временем):

(1.10) P(n) = Pⁿ, где слева матрица перехода за n шагов, справа – матрица перехода за 1 шаг.

Утверждение 3. Пусть дана Марковская цепь с состояниями S₁ … S_k, заданная матрицей переходов P, и задано начальное распределение вероятностей p⁰=(p₁⁰,p₂⁰,…, p_k⁰). Распределение вероятностей через n шагов можно вычислить по формуле:

(1.11) , где p_i(n) = P{ξ(n) = i} – вероятность находиться в момент времени n в состоянии i.

Пример 3. На некотором острове в Северном море 30% женщин рыжих. Известно, что у рыжей матери с вероятностью 0,6, а у не рыжей матери с вероятностью 0,2 рождается рыжая дочь. Найти вероятность того, что у не рыжей бабушки будет рыжая внучка.

Решение: Опишем процесс наследования цвета при помощи Марковской цепи. Составим матрицу переходов за 1 шаг, введя состояния: S₁ – рыжая, S₂ – не рыжая, тогда матрица переходов за один шаг, где шаг – одно поколение:

Начальное распределение имеет вид: P₁⁰ = 0,3; P₂⁰ = 0,7. Надо найти P_{2 1}(2). По теореме 1

=> P₂₁ = 0,28

В условиях этой же задачи найдем вероятность того, что у случайно выбранной женщины будет рыжая внучка. Обозначим события: H₁ – бабушка рыжая, H₂ – бабушка не рыжая. Тогда

P{рыжая внучка}= P(H₁) * P₁₁(2) + P(H₂) * P₂₁(2) =

= 0,3 * 0,44 + 0,7 * 0,28 = 0,132 + 0,196 = 0,328

Решить эту задачу можно другим способом, если воспользоваться Утверждением 3, тогда надо найти:

Нам надо p₁(2)=0,328.

 

1.3 Предельные вероятности в Марковских цепях

Рассмотрим Марковскую цепь с состояниями S₁, S₂, … S_k.

Определение 2. Если для всех i, j=1,…,k существует предел , причем величина p_j не зависит от i, тогда у этой системы существуют предельные вероятности, задаваемые равенством:

(1.12) , j=1,2,…k.

Физический смысл предельных вероятностей:

1) p_j – это доля времени, которое система проводит в j-том состоянии.

2) p_j – это вероятность застать систему в j-том состоянии, если мы посмотрим на нее в случайный момент времени.

Теорема 2. (О существовании предельных вероятностей) Пусть дана Марковская цепь с матрицей переходов P. Если при некотором t₀ все элементы матрицы строго положительны, то предельные вероятности существуют. (Без доказательства)

 

Рассмотрим пример, поясняющий, в каких случаях предельные вероятности не существуют.

Пример 4. Пусть цепь задана следующей матрицей переходов:

Представим эту систему в виде графа:

Видим, что в матрице Р есть нулевые элементы. Найдем P(2), P(3) и т. д. в надежде, что найдем матрицу без нулей и применим Теорему 2. Перемножив, получим:

Очевидно, все P(t) содержат нули. Возникает подозрение, что предельные вероятности не существуют. Для этого, чтобы убедиться в этом, рассмотрим траектории такой цепи:

состояние							...
t=							...

Состояния такой цепи меняются циклически (периодически):

p₁₁(2t+1)=0, p₁₁(2t)=1, поэтому не существует.

 

Рассмотрим вопрос о вычислении предельных вероятностей.

Теорема 3. Пусть дана Марковская цепь с конечным числом состояний S₁, S₂, … S_k, у которой существуют предельные вероятности p₁, p₂,..., p_k, тогда они могут быть найдены как решение системы уравнений:

(1.13) , или, в матричном виде,

(1.14)

Пример 5. Используя данные из примера 3, найдем долю рыжих женщин на этом острове через 1000 лет.

Решение: Найдем предельные вероятности для цепи с матрицей

Очевидно, предельные вероятности существуют, т.к. все элементы ненулевые. Для их вычисления используем Теорему 3. Запишем систему уравнений (1.14):

Решением этой системы будет p₁ =1/3, p₂ =2/3. Следовательно, через 1000 лет на этом острове будет 1/3 рыжих и 2/3 не рыжих женщин.

 

Задачи для самопроверки

1. В мастерскую для ремонта поступают моторы двух типов. Ремонт мотора типа М₁ требует одного дня, типа М₂ – двух дней. Каждое утро вероятность поступления на ремонт мотора типа М₁ равна 1/2, и типа М₂ – 1/3. Если день занят ремонтом мотора М₂, то отказывают любому заказу. Составить матрицу переходов.

2. В учениях участвуют два корабля, которые одновременно производят выстрелы друг в друга через равные промежутки времени. При каждом обмене выстрелами корабль А поражает корабль В с вероятностью 1/2, а корабль В поражает корабль А с вероятностью 3/8. Предполагается, что при любом попадании корабль выходит из строя. Найти матрицу переходов, если состояниями цепи являются комбинации кораблей, оставшихся в строю: Е1 – оба корабля в строю, Е2 – в стою корабль А, Е3 – в строю корабль В, Е4 – оба корабля поражены.

3. Погода на некотором острове бывает дождливой (Д) или сухой (С). Вероятности ежедневных изменений погоды заданы матрицей

а) если сегодня дождь, то какова вероятность того, что после завтра будет сухо?

б) если в среду ожидается дождливая погода с вероятностью 0,3, то какова вероятность того, что она будет дождливой в ближайшую пятницу?

 

 

25) Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения, через – запасы груза в i -м пункте отправления, через – потребности в грузе в j– м пункте назначения, а через – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(63)

при условиях

(64)

(65)

(66)

Поскольку переменные удовлетворяют системам уравнений (64) и (65) и условию неотрицательности (66), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 15.

Всякое неотрицательное решение систем линейных уравнений (64) и (65), определяемое матрицей , называется планом транспортной задачи.

Определение 16.

План , при котором функция (63) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы 21.

Таблица 21

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

(67)

то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

Теорема 13.

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство (67).

В случае превышения запаса над потребностью, т. е. вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (67).

Аналогично, при вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (67).

Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (64) и (65) равно п+т. Так как мы предполагаем, что выполняется условие (67), то число линейно независимых уравнений равно п+т– 1. Следовательно, опорный план транспортной задачи может иметь не более п + т– 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п+т– 1, то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы.

Пример 19.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i –го пункта его получения на j –е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(68)

При данном плане перевозок общая стоимость перевозок составит

(69)

Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (68), при котором целевая функция (69) принимает минимальное значение.

 

26)

итуации, описываемые рассмотренными в гл. 2 моделями в виде стратегических игр, в экономической практике могут не в полной мере оказаться адекватными действительности, посколь­ку реализация модели предполагает многократность повторения действий (решений), предпринимаемых в похожих условиях. В реальности количество принимаемых экономических решений в неизменных условиях жестко ограничено. Нередко экономичес­кая ситуация является уникальной, и решение в условиях нео­пределенности должно приниматься однократно. Это порождает необходимость развития методов моделирования принятия реше­ний в условиях неопределенности и риска.

Традиционно следующим этапом такого развития являются игры с природой. Формально изучение игр с природой, так же как и стратегических, должно начинаться с построения платежной мат­рицы, что является, по существу, наиболее трудоемким этапом под­готовки принятия решения. Ошибки в платежной матрице не могут быть компенсированы никакими вычислительными методами и приведут к неверному итоговому результату.

Отличительная особенность игры с природой состоит в том, что в ней сознательно действует только один из участников, в большинстве случаев называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные «ходы» партнер по игре. Поэтому термин «природа» характеризует некую объективную действительность, которую не следует понимать буквально, хотя вполне могут встретиться ситуации, в которых «игроком» 2 действительно может быть природа (например, обстоятельства, связанные с погодными ус­ловиями или с природными стихийными силами).

На примере игры с природой рассмотрим проблему заготов­ки угля на зиму.

Задача 3.1. Необходимо закупить уголь для обогрева дома. Количество хранимого угля ограничено и в течение холодного периода должно быть полностью израсходовано. Предполагает­ся, что неизрасходованный зимой уголь в лето пропадает. Поку­пать уголь можно в любое время, однако летом он дешевле, чем зимой. Неопределенность состоит в том, что не известно, какой будет зима: суровой, тогда придется докупать уголь, или мягкой, тогда часть угля может остаться неиспользованной. Очевидно, что у природы нет злого умысла и она ничего против человека «не имеет». С другой стороны, долгосрочные прогнозы, состав­ляемые метеорологическими службами, неточны и поэтому мо­гут использоваться в практической деятельности только как ори­ентировочные при принятии решений.

Решение. Матрица игры с природой аналогична матрице стратегической игры: А = || а_ij ||, где а_ij - выигрыш игрока 1 при реализации его чистой стратегии i и чистой стратегии j игрока 2 (i = 1,..., m; j = 1,..., п).

Мажорирование стратегий (см. разд. 2.4) в игре с природой имеет определенную специфику: исключать из рассмотрения можно лишь доминируемые стратегии игрока 1: если для всех j =1,..., п , k, l = 1,..., т, то k-ю стратегию принимающего решения игрока 1 можно не рассматривать и вычеркнуть из мат­рицы игры. Столбцы, отвечающие стратегиям природы, вычер­кивать из матрицы игры (исключать из рассмотрения) недопус­тимо, поскольку природа не стремится к выигрышу в «игре» с человеком, для нее нет целенаправленно выигрышных или про­игрышных стратегий, она действует неосознанно*.

* Впрочем, в матричных представлениях игр с природой значения выигры­шей принимающего решения игрока не всегда располагаются по строкам. Это допустимо делать и по столбцам, принимая ЛПР как игрока 2, понимая, одна­ко, что мажорировать можно только стратегии принимающего решения игрока. Такой подход осуществлен в некоторых задачах, представленных в гл. 6 - 8 настоящего учебного пособия.

 

На первый взгляд отсутствие обдуманного противодействия упрощает игроку задачу выбора решения. Однако, хотя ЛПР никто не мешает, ему труднее обосновать свой выбор, поскольку в этом случае гарантированный результат не известен.

Методы принятия решений в играх с природой зависят от характера неопределенности, точнее от того, известны или нет вероятности состояний (стратегий) природы, т.е. имеет ли место ситуация риска или неопределенности. Ниже будут описаны методы, применяемые в обоих случаях.

Рассмотрим организацию и аналитическое представление игры с природой. Пусть игрок 1 имеет т возможных стратегий: А₁, A₂,..., А_m, а у природы имеется п возможных состояний (стра­тегий): П₁, П₂,..., П_n, тогда условия игры с природой задаются матрицей А выигрышей игрока 1:

Платит, естественно, не природа, а некая третья сторона (или совокупность сторон, влияющих на принятие решений игроком 1 и объединенных в понятие «природа»).

Возможен и другой способ задания матрицы игры с приро­дой: не в виде матрицы выигрышей, а в виде так называемой матрицы рисков R = || r_ij || _m,n или матрицы упущенных возможно­стей. Величина риска - это размер платы за отсутствие инфор­мации о состоянии среды. Матрица R может быть построена не­посредственно из условий задачи или на основе матрицы выиг­рышей А.

Риском r_ij игрока при использовании им стратегии А_i и при состоянии среды П_j будем называть разность между выигрышем, который игрок получил бы, если бы он знал, что состоянием среды будет П_j, и выигрышем, который игрок получит, не имея этой информации.

Зная состояние природы (стратегию) П_j, игрок выбирает ту стратегию, при которой его выигрыш максимальный, т.е. r_ij = b_j – a_ij при заданном j. Например, для мат­рицы выигрышей

Согласно введенным определениям r_ij и b_j получаем матрицу рисков

Независимо от вида матрицы игры требуется выбрать такую стратегию игрока (чистую или смешанную, если последняя име­ет смысл), которая была бы наиболее выгодной по сравнению с другими. Необходимо отметить, что в игре с природой понятие смешанной стратегии игрока не всегда правомерно, поскольку его действия могут быть альтернативными, т.е. выбор одной из стратегий отвергает все другие стратегии (например, выбор аль­тернативных проектов). Прежде всего следует проверить, нет ли среди стратегий игрока мажорируемых, и, если таковые имеют­ся, исключить их.

Критерий Лапласа

Критерий Лапласа опирается на принцип недостаточного основания, который гласит, что, поскольку распределение вероятностей состояний P(s_i) неизвестно, нет причин считать их различными. Следовательно, используется оптимистическое предположение, что вероятности всех состояний природы равны между собой, т.е. P{s₁} = P{s₂} =... = P{s_n} = 1/n. Если при этом v(а_i, s_j) представляет получаемую прибыль, то наилучшим решением является то, которое обеспечивает

Если величина v(а_i, s_j) представляет расходы лица, принимающего решение, то оператор "max" заменяется на "min".

 

Решить игру с природой по критерию Сэвиджа

Решение

Строится матрица R – матрица риска

Элементы находятся по формуле

а) если А – матрица выигрышей

Оптимальной является 2 и 3 стратегии

б) если А – матрица потерь

Оптимальной является 1 стратегия

 

27)

При решении ряда задач оптимизации приходится сталкиваться с проблемой принятия решений в условиях неопределённости. Очень часто неопределённость, сопровождающая ту или иную операцию, связана с недостаточной осведомлённостью об условиях, в которых она будет проводиться. Так, например, могут быть заранее неизвестны: погода в некотором районе, покупательский спрос на продукцию определённого вида и т.п. Во всех подобных случаях условия выполнения операции зависят от объективной действительности, которую в теории игр принято называть «природой». Соответствующие ситуации называют «играми с природой» (статистическими играми).

«Природа» в теории игр рассматривается как некая незаинтересованная инстанция, поведение которой хотя и неизвестно, но, во всяком случае, не содержит элемента сознательного противодействия нашим планам. Рассмотрим подобную ситуацию.

Пусть сторона А имеет возможных стратегий

 

 

О состоянии «природы» можно сделать предположений

 

 

Для каждой пары стратегий ( ) существует функция которая является случайной величиной и называется функцией потерь.

Пусть удаётся определить величину − эффективность решения в условиях для всех комбинаций пар стратегий . В этом случае платёжная матрица игры имеет вид:

 

 

В теории статистических игр, помимо платёжной матрицы, используется и, так называемая, матрица рисков или матрица сожалений.

Риском стороны А при использовании стратегии в условиях называется величина

 

где − максимальный выигрыш стороны А в состоянии «природы»

Рассмотрим критерии выбора оптимальной стратегии в статистической игре.

1. Наиболее просто решается задача о принятии решения в условиях неопределённости, когда, хотя и неизвестны условия выполненияоперации но известны их вероятности соответственно. В этом случае в качестве показателя эффективности естественно взять математическое ожидание выигрыша

1.1. По критерию Байеса, за оптимальную чистую стратегию принимается чистая стратегия при которой величина достигает наибольшего значения. С помощью этого критерия задача принятия решения в условиях неопределённости сводится к задаче принятия решения в условиях определённости, только принятое решение является оптимальным не в каждом отдельном случае, а в среднем.

Следует отметить, что, по критерию Байеса, оптимальной будет та стратегия при которой минимизируется величина среднего риска

Это связано с тем, что стратегия, максимизирующая средний выигрыш, совпадает со стратегией, минимизирующей средний риск.

1.2. Вероятности состояний «природы» могут быть определены из статистических данных, связанных с многократным выполнением подобных операций или просто с проведением наблюдений над состояниями «природы». Однако часто об этих состояниях нет никаких представлений. В подобных случаях состояния могут быть оценены субъективно: некоторые из них представляются нам более, а другие – менее правдоподобными. Для того чтобы наши субъективные представления формализовать численно, могут применяться различные технические приёмы. Так, если мы не можем предпочесть ни одной гипотезы, то естественно положить состояния «природы» равновероятными:

Этот подход получил название принципа недостаточного основания Лапласа. В этом случае, как и по критерию Байеса, оптимальной считается та стратегия, при которой максимизируется средняя величина выигрыша.

2. Пусть теперь вероятности состояний «природы» неизвестны. Рассмотрим критерии, которые можно использовать для определения оптимальной стратегии в этом случае.

2.1. Максиминный критерий Вальда.

Согласно этому критерию, в качестве оптимальной выбирается та стратегия при которой минимальный выигрыш максимален, т.е. стратегия, гарантирующая при любых условиях выигрыш, не меньший, чем максимин

.

Если руководствоваться этим критерием, нужно всегда ориентироваться на худшие условия и выбирать ту стратегию, для которой в худших условиях выигрыш максимален.

2.2. Критерий минимаксного риска Сэвиджа.

Этот критерий рекомендует в условиях неопределённости выбирать ту стратегию, при которой величина риска принимает наименьшее значение в самой неблагоприятной ситуации (т.е. тогда, когда риск максимален):

Сущность этого критерия состоит в том, чтобы любыми путями избежать большого риска при принятии решения.

Критерии Вальда и Сэвиджа относятся к группе критериев крайнего пессимизма.

2.3. Критерий пессимизма–оптимизма Гурвица.

По критерию Гурвица, оптимальной является та стратегия для которой принимает наибольшее значение величина

где

При критерий Гурвица превращается в пессимистический критерий Вальда, а при в критерий крайнего оптимизма, рекомендующий ту стратегию, для которой в наилучших условиях выигрыш максимален.

Пример. Планируется проведение операции в заранее неясных условиях, относительно которых можно сделать различные предположения

Задана платёжная матрица

 

Найдём оптимальную стратегию, пользуясь критериями Вальда, Сэвиджа и критерием Гурвица при

 

Решение.

1. Критерий Вальда. В каждой строке платёжной матрицы выбираем наименьший выигрыш и из полученных значений берём наибольшее:

 

Следовательно, согласно критерию Вальда, оптимальной является стратегия

2. Критерий Сэвиджа. Построим сначала матрицу сожалений Для этого вычислим максимальные выигрыши стороны при трёх различных состояниях «природы»:

 

 

Теперь можем вычислить элементы матрицы сожалений:

 

 

Матрица сожалений имеет вид:

 

В каждой строке матрицы сожалений выберем наибольший риск и из полученных значений отметим наименьшее:

 

 

Следовательно, согласно критерию Сэвиджа, оптимальными являются стратегии и

3. Критерий Гурвица. В каждой строке платёжной матрицы определяем наименьший и наибольший выигрыши и соответственно, а затем для каждой строки вычисляем величину и отмечаем из последней совокупности чисел наибольшее значение:

 

Следовательно, согласно критерию Гурвица при оптимальной является стратегия

 

 

15. Планирование эксперимента в условиях неопределённости

Пусть некоторую операцию предстоит осуществить в недостаточно ясных условиях. Необходимо выяснить, имеет ли смысл для уточнения условий в этой ситуации предпринимать некоторый эксперимент. Рассмотрим случай идеального эксперимента, приводящего к точному знанию того состояния «природы» которое имеет место в данной ситуации.

Пусть задана платёжная матрица а также известны вероятности всех состояний «природы» Обозначим через С затраты на проведение эксперимента.

Сравним средний выигрыш с проведением эксперимента и средний выигрыш без проведения эксперимента.

Если дополнительно не проводить эксперимента, то в качестве оптимальной необходимо выбрать ту стратегию для которой достигается

(15.1)

 

Это и будет выигрыш без проведения эксперимента.

Теперь предположим, что произведён эксперимент и установлено, какое из состояний является действительным состоянием «природы». Пусть этим состоянием является тогда выигрыш будет определяться величиной

.

 

«Осредним» этот выигрыш с весами, равными вероятностям :

С учётом стоимости эксперимента средний выигрыш с применением эксперимента равен величине

. (15.2)

 

Итак, если величина, выражаемая формулой (15.2), больше величины, выражаемой формулой (15.1), то эксперимент следует проводить, а если наоборот, то эксперимент проводить не следует:

,

откуда получим неравенство