Название работы	Кол-во страниц	Размер
Методические указания к практическим занятиям по дисциплине «Математика»...	1	233.42kb.
Методические указания к практическим занятиям по дисциплине «Математика»...	3	294.49kb.
Методические указания Волгоград 2009 (07)	2	440.58kb.
Методические указания по ее выполнению, образцы решения основных...	2	498.51kb.
Методические указания к семинарским занятиям Красноярск сфу 2011 удк	1	218.77kb.
Методические указания по самостоятельной работе Красноярск сфу 2011	2	510.49kb.
Методические указания к семинарским занятиям Красноярск сфу 2011	2	399.28kb.
Методические указания по написанию эссе по дисциплине «Региональная...	1	172.46kb.
Методические указания к самостоятельной работе Красноярск сфу 2011...	1	278.45kb.
Методические указания к семинарским занятиям Красноярск сфу 2011	1	105.67kb.
Методические указания по самостоятельной работе Красноярск сфу 2011	1	173.31kb.
А. М. Липатов ² ² 1998 г	3	826.52kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

МИНистерство ОБРАЗОВАНИЯ И НАУКИ РФ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КАМЫШИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ГОУ ВПО «ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра «Высшая математика»

Дискретные цепи Маркова

и их применение в экономике
Методические указания

к практическому занятию по дисциплине «Математика»


Волгоград

2011

УДК 519.1(07)

Д 48
Дискретные цепи Маркова и их применение в экономике: методические указания к практическому занятию по дисциплине «Математика» / Сост. С. В. Мягкова, Е. В. Морозова; Волгоград. гос. техн. ун-т. – Волгоград, 2011. – 15 с.

Содержат теоретический материал, примеры решения задач по данной теме и задачи для самостоятельной работы.

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

Ил. 7. Библиогр.: 2 назв.
Рецензент: А. А. Кулеша
Печатается по решению редакционно-издательского совета

Волгоградского государственного технического университета

Составители: Светлана Васильевна Мягкова, Елена Васильевна Морозова

Дискретные цепи Маркова и их применение в экономике

Методические указания к практическому занятию по дисциплине «Математика»

Под редакцией авторов

Темплан 2011 г., поз. № 28К.

Подписано в печать 28. 12. 2011 г. Формат 60×84 ¹/₁₆.

Бумага листовая. Печать офсетная.

Усл. печ. л. 0,93. Уч.-изд. л. 0,73.

Тираж 50 экз. Заказ №

Волгоградский государственный технический университет

400131, г. Волгоград, пр. Ленина, 28, корп. 1.

Отпечатано в КТИ

403874, г. Камышин, ул. Ленина, 5, каб. 4.5

© Волгоградский

государственный

технический

университет, 2011

Введение
Методические указания предназначены для проведения практического занятия для студентов 2-го курса экономических специальностей.

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

В начале практического занятия студентам необходимо под руководством преподавателя изучить теоретическую часть и лишь потом, приступить к решению задач.

1. Дискретные цепи Маркова

и их применение в экономике
Марковские случайные процессы названы по имени выдающегося русского математика А. А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать «динамикой вероятностей». В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т. д.. В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.

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

Пусть у нас имеется некоторая система S, которая может находиться в одном из состояний ₁, _2,  _n и может менять свое состояние только в моменты времени t₁ , t₂ , ..., t_m … (t₁ t₂ t_m причем вероятность в момент t_m оказаться в состоянии _j зависит только от того, в каком состоянии система S находилась в момент времени t_m-1. В этом случае говорят, что задана цепь Маркова.

Если в момент t_m-1 система находилась в состоянии _i, то вероятность того, что в следующий момент t_m система окажется в состоянии _j, называется переходной и обозначается через:

.

В дальнейшем мы ограничимся так называемыми однородными цепями Маркова, когда переходные вероятности p_ij^(m) не зависят от момента времени t_m, а зависят только от индексов i и j. Так как система может находиться в одном из п состояний, то полная вероятностная картина изменений состояния системы S задается матрицей:

.

Эту матрицу называют матрицей перехода или переходной матрицей. Элементы этой матрицы, удовлетворяют следующим двум условиям:

1. 
   0 ≤ p_ij ≤ 1;
   
2. 
   для любого значения i (i = 1,2, …, n), (сумма вероятностей по строчкам).
   

Такие матрицы называются стохастическими.
Пример 1. Некоторая совокупность рабочих семей поделена на три группы: ₁ – семьи, не имеющие автомашины и не намеревающиеся ее приобрести; ₂ – семьи, не имеющие автомашины, но собирающиеся ее приобрести, и, наконец, ₃ – семьи, имеющие автомашину. Статистические обследования дали возможность оценить вероятность перехода семей из одной группы на протяжении года в другую. При этом матрица перехода оказалась такой:

.

И

Рис. 1.
з этой матрицы следует, что вероятность того, что семьи, которые в предшествующем году имели машину и в следующем за ним году, наверняка, будут иметь ее, равна p₃₃ = 1. В матрице элемент р₂₃ = 0,3 означает вероятность того, что семья, не имевшая в предыдущем году машины, но решившая приобрести ее, осуществит свое намерение в этом году. Далее, p₂₁ = 0 означает вероятность того, что семья, намеревавшаяся купить автомашину в прошлом году, в следующем за ним году от этого намерения вообще отказалась.

Матрицы перехода удобно представлять в виде сигнальных графов, изображая переходы системы их одного состояния в другое. Сигнальный граф для матрицы Р примера 1 изображен на рис. 1.
Пример 2. Какой граф задает марковский процесс (рис. 2):

а)	б)
в)	г)
д)
Рис. 2.

Решение:

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

Оценка переходных матриц, аналогичных рассмотренной в примере 1, имеет большое практическое значение: она дает возможность существенно уточнить экономические методы составления прогнозов опроса на некоторые потребительские товары длительного пользования. Наряду с переходной матрицей P на один шаг важна и матрица перехода за n шагов, она равна P(n) = рⁿ.
Пример 3. По данным примера 1 вычислить:

а)вероятность того, что семья, не имевшая машины и не собиравшаяся ее приобрести, будет находиться в той же ситуации через 2 года;

б) вероятность того, что семья, не имевшая автомашины и намеревающаяся ее приобрести, будет иметь автомашину через 2 года.
Решение
Для вычисления искомых вероятностей р₁₁(2) и р₂₃(2) следует найти матрицу Р(2). Применяя формулу P(2) = P² имеем:

.

Таким образом, первая из искомых вероятностей равна 0,64, а вторая – 0,51.

Пример 4. Предположим, что некая фирма осуществляет доставку оборудования по Москве: в северный округ (обозначим А), южный (В) и центральный (С). Фирма имеет группу курьеров, которая обслуживает эти районы. Понятно, что для осуществления следующей доставки курьер едет в тот район, который на данный момент ему ближе. Статистически было определено следующее:

1. 
   после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях – в В и в 40 случаях – в С;
   
2. 
   после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях – в В и в 20 случаях – в С;
   
3. 
   после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях – в В и в 20 случаях – в С.
   

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

Матрица вероятностей перехода будет выглядеть следующим образом:

Например, р₁₂ = 0,4 – это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А.

Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% – в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1, И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0 _ij . Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождние курьера в момент времени t + 1 зависит только от местонахождения в момент времени t.

Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей из С в В за 2 шага:

1) сначала из С в С и потом из С в В;

2) С В и В  В;

3) С  А и А  В.

Учитывая правило умножения независимых событий, получим, что искомая вероятность равна:

Р = Р(СА)  Р(АВ) + Р(СВ)  Р(ВВ) + Р(СС)  Р(СВ).

Подставляя числовые значения:

Р = 0,5  0,3 + 0,3  0,4 + 0,2  0,3 = 0,33.

Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки.

Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок – это может занять довольно много времени.

Покажем более простой способ вычисления подобных вероятностей. Для того, чтобы получить вероятности перехода из различных состояний за 2 шага, возведем матрицу Р в квадрат:

Тогда элемент (2, 3) – это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице Р² также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ.

р(СА)  Р(АВ) + р(СВ)  Р(ВВ) + р(СС)  Р(СВ) =

= 0,37  0,3 + 0,33  0,4 + 0,3  0,3 = 0,333,

где р(СА) – вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы Р²).

2 способ. Вычислить матрицу Р³:

Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:

Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Таким образом, в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).

Пример 5. Две машины А и В сдаются в аренду по одной и той же цене. Эти машины имеют следующие матрицы переходных вероятностей:

где ₁ – состояние, когда машина работает хорошо;

₂ – состояние, когда машина требует регулировки.

Определить вероятности для обеих машин. Какую машину стоит арендовать?

Рeшeние
Сделаем чертеж графа матрицы А переходных вероятностей.

Д

Рис. 3.
ля первой машины находим вероятности из системы трех линейный алгебраических уравнений с двумя неизвестными р_А1 и р_А2:

p_A1  0,8 + p_A2  0,7 = p_A1;

p_A1  0,2 + p_A2  0,3 = p_A1;

p_A1 + p_A2 = p_A1.

Отсюда р_А1 = 7/9, р_А2 = 2/9.

Для второй машины аналогично находим p_В1 = 2/3, p_В2 = 1/3.

Сравнивая между собой р_А1 и р_В1 заключаем, что 1-ая машина будет более часто в исправном состоянии, чем 2-ая, поэтому лучше всего арендовать именно эту машину.

Пример 6. Машина может находиться в одном из двух состояний: ₁ – машина работает хорошо и ₂ – машина нуждается в регулировке. На следующий день работы машина меняет свое состояние в соответствии со следующей матрицей переходных вероятностей:

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

Решение
Матрица вознаграждений имеет вид:

Графическое изображение марковского процесса будет:

Рис. 4.

Обозначим ожидаемую прибыль в каждом состоянии как q₁ и q₂. Тогда, согласно рис. 4, имеем:

q₁ = 0,7  40 + 0,3  20 = 34,

q₂ = -20  0,4 + 20  0,6 = 4, а q₁ + q₂ = 38.

Значит ожидаемая прибыль равна 38 р.

Пример 7. Состав исправных (состояние S₁) и требующих ремонта (состояние S₂) машин в автопарке в начале года определятся состоянием k = N(S₁) : N( S₂) = 4 : 1, а вероятность переходов между этими состояниями по истечении года характеризуются матрицей:

.

Тогда в конце года (или в начале следующего года) состояние k будет равно …

1) 7 : 2.

2) 3 : 2.

3) 36 : 11.

4) 31 : 16.
Решение
Графическое изображение марковского процесса:

8

Рис. 5.

Тогда:

N(S₁ )= 4  0,7 + 1  0,2 = 3, N(S₁) = 1  0,8 + 4  0,3 = 0,8 + 1,2 = 2.

Значит k = 3 : 2.

2. Задачи ДЛЯ самостоятельной работЫ
Задача 1. Пусть (Е₁, Е₂, Е₃) – возможные состояния системы, Р – матрица вероятностей перехода из состояния в состояние за один шаг:

Построить граф, соответствующий матрице Р.

Задача 2. Рассмотрим марковскую цепь с двумя состояниями Е₁ и Е₂ с матрицей вероятностей перехода:

С помощью особого устройства случайного выбора мы выбираем состояние, с которого начинается процесс. Это устройство выбирает Е₁ с вероятностью 1/2 и Е₂ с вероятностью 1/2. Требуется:

а) найти вероятность того, что после первого, шага этот процесс перейдет в состояние Е₁;

б) то же самое для случая, когда это устройство выбивает Е₁ с вероятностью 1/3 и Е2 с вероятностью 2/3.

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

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

б) Если в среду ожидается дождливая погода с вероятностью 0,3, то какова вероятность, что она будет дождливой в ближайшую пятницу?
Задача 4. В некоторой местности климат весьма изменчив. Здесь никогда не бывает двух ясных дней подряд. Если сегодня ясно, то завтра с одинаковой вероятностью пойдет дождь или снег. Если сегодня снег (или дождь), то с вероятностью 1/2 погода не изменится. Если все же она изменится, то в половине случаев снег заменяется дождем или наоборот и лишь в половине случаев на сле­дующий день будет ясная погода.

Требуется:

а) принимая в качестве состояний цепи различные виды погоды Д, Я, С, выписать матрицу Р вероятностей перехода;

б) построить граф, соответствующий матрице Р.
Задача 5. Дан граф (рис. 6):

Рис. 6.

Составить переходную матрицу.
Задача 6. Какие из следующих матриц являются стохастическими и пригодны для описания Марковского процесса?

а) ; б) ; с) ;

д) ; е) .
Задача 7. Имеется водохранилище с тремя уровнями наполнения: полный (состояние е₁), средний (состояние е₂) и критический (состояние е₃). Данная система описана как Марковская цепь с переходной матрицей:

Построить граф данной матрицы.

Задача 8. В любой данный день человек здоров или болен. Если человек здоров сегодня, то вероятность того, что он будет здоров и завтра оценивается в 98%. Если человек сегодня болен, то завтра он будет здоров лишь в 30% случаев. Описать последовательность состояний здоровья как Марковскую цепь. Определить:

а) вероятность того, что человек выздоровеет завтра, послезавтра и на третий день, если сегодня он болен;

б) ожидаемое число дней, в течение которых больной на сегодняшний день человек остается больным.
Задача 9. Погода на некотором острове через длительные периоды времени становится то дождливой (состояние е₁), то сухой (состояние е₂). Вероятности ежедневных изменений заданы матрицей:



Вычислить:

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

б) вероятность солнечной погоды в ближайшую субботу, если в среду погода была дождливой.
Задача 10. В учениях участвуют два корабля, которые одновременно производят выстрелы друг в друга и через равные промежутки времени. При каждом обмене выстрелами корабль А поражает корабль В с вероятностью 1/2, корабль В поражает корабль А с вероятностью равной 3/8. Предполагается, что при любом попадании корабль выходит из строя. Рассматриваются результаты серии выстрелов.
Требуется:

a) построить матрицу вероятностей перехода, вычислив переходные вероятности p_ij, если состояниями цепи являются комбинации кораблей, оставшихся в строю: е₁ – оба корабля в строю; е₂ – в строю корабль А; е₃ – в строю корабль В; е₄ – оба корабля поражены.

б) построить граф этой системы.
Задача 11. Посетитель банка с намерением получить кредит проходит ряд проверок (состояний): е₁ – оформление документов; е₂ – кредитная история; е₃ – возвратность; е₄ – платежеспособность. По результатам проверки возможны два исхода: отказ в выдаче кредита (е₆) и получение кредита (е₅). Граф этой системы изображен на рис. 7.

Рис. 7.

Требуется:

a) описать данный процесс как Марковскую цепь и построить переходную матрицу;

б) найти среднее время получения положительного и отрицательного результата.

Ответы
№ 2 а) 5/12; б) 4/9.

№ 3 а) 0,61 б) 0,547

№ 4 а)		Д	Я	С
	Д	½	¼	¼
Р =	Я	½	0	½
	С	¼	¼	½

№ 5

Литература
1. Мацкевич И.П., Свирид Г.П. Высшая математика. Теория вероятностей и математическая статистика: учебник для студентов экономических специальностей вузов. – Минск: «Высшая школа», 2001.

2. Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Т. II: Марковские цепи как отправная точка теории случайных процессов и их приложения. М.: МЦНМО, 2009. – 295 с.: ил.

Содержание
Введение…………………………………………………………………3

1. 
   Дискретные цепи Маркова и их применение в экономике………3
   
2. 
   Задачи для самостоятельной работы……………………………..11
   
3. 
   Ответы……………………………………………………………...14
   
4. 
   Литература…………………………………………………………15