|
Реферат: Методические указания по курсу "Математика" для студентов I курса исторического факультета (Математика)
Сыктывкарский государственный университет
Кафедра математического анализа
Методические указания по курсу “Математика”
для студентов I курса исторического факультета
(заочное отделение)
Преподаватель Попова Н.А.
Сыктывкар 2001
Учебный план по курсу “Математика”
для I курса исторического факультета (заочное отделение)
на 2001-02 уч.год преподавателя Поповой Н.А.
I семестр. Лекции (4 часа)
1. Краткий исторический очерк развития математики. Обзор
литературы.
2. Множества, элементы комбинаторики, введение в теорию
вероятностей и математическую логику, знакомство с графами.
Консультация (1 час). Методические указания к выполнению контрольной
работы.
Задания для самостоятельной работы:
1. Контрольная работа (5 задач. См. приложение 1).
2. Подготовка (написание) реферата по выбранной теме (список тем
– приложение 2).
II семестр. Практические занятия (12 часов). Решение задач.
1. Множества. Элементы комбинаторики.
2. Элементы теории графов и математической логики.
3. Элементы теории вероятностей. Математическое ожидание и
дисперсия, их применение в математической статистике.
4. Функции и их графики.
Семинары.
5–6. Некоторые вопросы истории развития математики (основные
вехи развития общества и развития математики).
Консультации (к зачету) – 13 часов.
Зачет ставится с учетом оценок за:
1) контрольную работу,
2) реферат (по индивидуальной теме),
3) участие в работе практических занятий (общая оценка за 6 занятий),
4) ответы на вопросы зачета по двум частям (2 вопроса, приложение 3).
Список основной литературы:
1. Ловягин Ю.Н., Матвеева О.П. Математика. Учебное пособие для студентов
нематематических специальностей. Ч.1. Дифференциальное и интегральное
исчисления. Сыкт-р. СГУ, 1998. 73 с. Ч.2. Теория вероятностей. Графы.
СГУ, 1999. 64 с.
2. Матвеев И.В. Функции и их графики. М. МГУ, 1970. 104 с.
3. Столл Р.Р. Множества. Логика. Аксиоматические теории. М. Просв., 1968.
230 с.
4. Крамор В.С. Повторяем и систематизируем школьный курс алгебры и начал
анализа. М. Просвещение, 1990. 416 с.
5. Шиханович Ю.А. Введение в современную математику (Начальные понятия). М.
Наука, 1965. 376 с.
6. Головач П.А. Введение в теорию графов. Сыктывкар. СГУ, 1993.
7. Гнеденко Б.В., Хинчин А.Я. Введение в теорию вероятностей. М. Физматгиз,
1982. 160 с.
8. Колмогоров А.Н., Журбенко И.Т., Прохоров А.В. Введение в теорию
вероятностей. М. Физматгиз, 1982.
9. Мендельсон Э. Введение в математическую логику. М. Наука, 1984. 320 с.
10. Валуцэ И.И., Дилигул Г.Д. Математика для техникумов. Учебное пособие.
М. Наука, 1989. 576 с.
11. Стройк Д.Я. Краткий очерк истории математики. М. Наука, 1978. 336 с.
12. Рыбников К.А. Возникновение и развитие математической науки. Пособие
для учителя. М. Просвещение, 1987. 159 с.
Приложение 1.
Контрольная работа по математике
для I курса исторического факультета СГУ (заочное отделение)
Задание 1. (Множества. Комбинаторика.)
1) Составить множества различных букв. А – своего полного имени, В – своего
отчества, С – своей фамилии.
2) Найти объединение и пересечение множеств А и В.
3) Найти дополнения к С до А и к А до С.
4) Проверить на диаграммах, верно ли равенство: [pic].
5) Вычислить, сколько элементов имеет декартово произведение множеств А и
В, изобразить их точками плоскости.
6) Сколько различных аббревиатур можно составить из всех букв множества С?
В каждой из аббревиатур использовать каждую букву из множества С только
по одному разу (т.е. без повторений).
7) Сколько различных трехбуквенных слов можно составить из букв множества
В, если слова составляются из разных букв (без повторений)? Что собой
представляют наборы букв этих слов – сочетания или размещения?
8) Сколько различных подмножеств (всех) имеет множество А?
Пример решения такой задачи. Пусть автор – Пафнутий Львович Чебышёв
(будем считать е и ё за одну и ту же букву). Тогда
1) А={П, А, Ф, Н, У, Т, И, Й}, В={Л, Ь, В, О, И, Ч}, С={Ч, Е, Б, Ы,
Ш, В}.
2) [pic]= {П, А, Ф, Н, У, Т, И, Й, Л, Ь, В, О, Ч}. [pic]={И}.
3) Т.к. [pic](, то [pic] и [pic].
4) [pic]{П, А, Ф, Н, У, Т, И, Й, В, Ч}.
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]{П, А, Ф, Н, У, Т, И, Й, В, Ч}.
Ответ: Т.к. получилось одно и то же множество, то равенство верно.
5) [pic]. Ч
И
О
В
Ь
Л
П А Ф Н У Т И Й
6) Так как аббревиатуры составляются из всех букв множества С и без
повторений, то их количество равно множеству порядков на множестве С:
[pic].
7) Т.к. при перестановке букв в слове получаются другие (новые) слова
(например, ЛОВ и ВОЛ), то наборы букв для слов – это размещения, т.к. важен
порядок выбора букв. Всех размещений из букв множества В по 3 - [pic]. Но
нет слов, начинающихся с буквы “ь”, поэтому такие наборы надо исключить, их
количество равно [pic]. Тогда различных трехбуквенных слов [pic].
Ответ: 100.
8) Т.к. [pic], то количество подмножеств - [pic].
Задание 2 (Графы)
Пусть множество А из предыдущего задания есть множество обозначений
вершин для построения графов, т.е. множества точек V.
1) Изобразить вершины графа точками, обозначить их и соединить ребрами так,
чтобы получился а) полный граф - [pic], б) двудольный граф - [pic],
в) полный двудольный граф - [pic], г) регулярный граф - [pic] (указать
его степень), д) односвязный граф с одним “мостом” - [pic], е)
непростой граф - [pic] (т.е выполнить не менее шести рисунков).
2) Найти среди изображенных графов а) эйлеров граф, б) полуэйлеров граф,
в) граф, имеющий циклы (если они есть на рисунках, подписать их; если
нет, то изобразить такие графы).
3) Из множеств А, В и С предыдущей задачи выбрать множество с наименьшим
числом букв (элементов) и, считая их вершинами графа, изобразить все
возможные деревья с вершинами во всех этих точках.
Например.
b
[pic]
a c полный граф с пятью
вершинами; он же регулярный
(однородный), степень вершин
r = 4; а также он эйлеров;
l d односвязный.
[pic] n двудольный и
двусвязный граф; (двудольный -
m неполный).
l
k o
p q
s
[pic] t u непростой,
односвязный с одним “мостом”,
полуэйлеров граф.
x v
z w
y
Задание 3 (Теория вероятностей)
Возьмем множества А и В из задания 1. Пусть каждая из букв написана на
отдельной карточке и множества А и В – это две колоды карточек (все
карточки положены буквами вниз, их не видно).
Вычислить вероятность того, что при выборе наугад по одной карточке из
каждой колоды будут вынуты а) 2 одинаковые буквы; б) 2 разные буквы; в)
хотя бы одна из букв такая, какую Вы задумали заранее (укажите, какую
именно; если есть разные варианты решения, то покажите все решения).
Например, ) А={П, А, Ф, Н, У, Т, И, Й}, В={Л, Ь, В, О, В, И, Ч}.
Тогда: а) общая буква только одна – И; вероятность ее выбора из А равна
[pic], вероятность ее выбора из В равна [pic]; вероятность ее выбора из А
и из В – [pic] (правило произведения); б) т.к. во всех остальных случаях
буквы будут различны, то вероятность выбора двух разных букв равна [pic]
(можно ее найти и другим способом); в) если задумана буква “И”, то
вероятность ее выбора хотя бы из одной колоды – это 3 случая: “И” из А и
любая другая буква из В, “И” из В и любая другая буква из А, а также “И” –
из А и В; сложив вероятности, получим: [pic]. Аналогично для других букв
(2 случ.).
Внимание! В заданиях 4 и 5 каждый студент должен выполнить свой
вариант. Номер варианта соответствует Вашему номеру зачетной книжки
следующим образом: а) если две последние цифры номера зачетной книжки
составляют число не больше тридцати, то это и есть номер Вашего варианта;
б) если две последние цифры составляют число большее тридцати, то из него
следует вычесть 30 столько раз, сколько возможно; остаток и есть номер
Вашего варианта; если две последние цифры номера зачетной книжки 60 ли 90,
то Вы выполняете вариант 30. Например, номер зачетной книжки …41 – вариант
11, т.к. 41=30+11, …62 – вариант 2, …97 – вариант 7; …208 – т.е. …08 –
вариант 8.
Задание 4 (Математическая логика).
А. В вариантах 1 – 15 составить таблицу истинности формулы:
1. ( x ( y ( (( y ( x( ( y); 2. ( (x (( y )(
(( x ( y) ( ( y);
3. y ( ( x ( ( y ( x ( ( x); 4. x ( y ( (( x (
( y ( y );
5. x ( ( x ( ( y ( ( y ( ( x); 6. (y ( ( x ( ( x
( y)) ( x( y;
7. ( (x ( ( y) ( (x( ( y); 8. x ( ( y ( y
( ( (x( y));
9. x ( y ( ( y ( ( x ( y); 10. x ( ( ( y ( x(
y);
11. x ( ( y ( ( x( ( x ( ( y)); 12. (x( y) ( ( y (
( x);
13. ( x( y) ( (( x ( ( (y ( x)); 14. x ( ( ( y ( x) ( (
x( ( y));
15. (x ( ( y) ( ( ( x( y) ( ( y;
Б. В вариантах 16-30 проверить, является ли формула тавтологией:
16. (y ( (x( ( y)) ( ( x ( ( y ( ( x)); 17. ( x ( y) ( ( y ( (
x);
18. x ( ( x ( ( y ) ( ( y); 19. x ( ( x (
(( y ( x ));
20. x ( (( y ( ( x) ( x); 21. (x ( y) ( x( y
( ( (( x ( ( y);
22. x( y ( ( (( x ( ( y); 23. ( ( x( y (
y ) ( x( y;
24. ( ( x( y ( x ) ( x ( y; 25. ( (x ( y) ( (
( y ( ( x);
26. ( (x ( y) ( ( ( y ( ( x); 27. x ( ( y ( (x(
y ( ( x);
28. x ( ( y ( (( y ( ( x) ( ( x; 29. x ( ( y ( x (
( y );
30. ( x ( ( y ( ( x ( ( y)).
Примеры. А. Составить таблицу истинности формулы
(x ( ( y) ( (x( y)) ( x ( ( y.
Решение. Порядок выполнения действий:
x ( t
(
( z
(
y ( (
v
| | | | |z |t |v |Ответ: |
|x |y |( y |x ( y |( y ( (x ( |(x( z) |( x ( ( y |t ( v |
| | | | |y) | |) | |
|И |И |Л |И |Л |Л |И |Л |
|И |Л |И |И |И |И |И |И |
|Л |И |Л |И |Л |И |Л |Л |
|Л |Л |И |Л |Л |И |И |И |
Б. Проверить, является ли формула (x ( ( y) ( (x( y)) ( (x ( ( y)
тавтологией.
Решение (аналогично решению предыдущей задачи, отличается лишь v: x (
( y.
| | | | |z |t |v |Ответ: |
|x |y |( y |x ( y |( y ( (x ( |x( z |x( ( y |t ( v |
| | | | |y) | | | |
|И |И |Л |И |Л |Л |Л |И |
|И |Л |И |И |И |И |И |И |
|Л |И |Л |И |Л |И |И |И |
|Л |Л |И |Л |Л |И |И |И |
Ответ: да, тавтология.
Задание 5.
Построить график дробно-рациональной функции [pic] (варианты 1-30),
предварительно исследовав ее по следующему плану:
1) найти область определения функции [pic] (для этого можно преобразовать
формулу, разложив числитель и знаменатель на множители);
2) если есть точки разрыва, то выяснить, есть ли в них вертикальные
асимптоты (для этого найти в этих точках пределы функции слева и
справа);
3) найти наклонные или горизонтальные асимптоты (для этого преобразовать
формулу функции, выделив целую часть из дроби);
4) проверить, не обладает ли функция частными свойствами: а) четностью или
нечетностью, б) периодичностью (если нет, то доказать, пояснить это);
5) найти точки пересечения графика с осями координат и интервалы
знакопостоянства, если точки пересечения с осью [pic] легко находятся;
6) найти производную и критические точки;
7) по знаку производной выяснить интервалы возрастания и убывания функции и
что она имеет в критических точках;
8) изобразить систему координат (в соответствии с исследованными
свойствами) и отметить в ней все найденные точки, изобразить асимптоты;
для уточнения вида графика найти координаты нескольких дополнительных
точек; отметить их и нарисовать график;
9) если в п.5 не были найдены точки пересечения графика с осью [pic] (нули
функции), то найти их теперь по графику;
10) найти область изменения функции (по графику и исследованным свойствам).
Варианты: [pic]
1) [pic]; 11) [pic]; 21) [pic];
2) [pic]; 12) [pic]; 22) [pic];
3) [pic]; 13) [pic]; 23) [pic];
4) [pic]; 14) [pic]; 24) [pic];
5) [pic]; 15) [pic]; 25) [pic];
6) [pic]; 16) [pic]; 26) [pic];
7) [pic]; 17) [pic]; 27) [pic];
8) [pic]; 18) [pic]; 28) [pic];
9) [pic]; 19) [pic]; 29) [pic];
10) [pic]; 20) [pic]; 30) [pic].
Пример. Исследовать функцию [pic][pic].
Решение. 1) [pic][pic]= [pic]=[pic] при [pic] (корни квадратного
трехчлена найдены по обратной теореме Виета (в уме)),
значит, [pic].
2) а) при [pic] слева [pic];
(1)
|[pic] |-8 |-7,5 |-7,1 |… |
|[pic] |-90 |-159,5 |-719,1 |… |
при [pic] справа [pic];
(2)
|[pic] |-6 |-6,5 |-6,9 |… |
|[pic] |52 |121,5 |681,1 |… |
Значит, [pic] - вертикальная асимптота;
б) при [pic] (и слева и справа) [pic];
|[pic] |1,9 |2,1 |
|[pic] |[pic] |[pic] |
асимптоты нет; [pic] - исключенная точка (т. разрыва).
(3)
3) В [pic] [pic] [pic][pic]
[pic]; т.к. при [pic] [pic], то
[pic]; таким образом, прямая [pic] - наклонная асимптота.
4) Исследуем на четность: [pic][pic][pic]
[pic]; видим, что: [pic][pic] и [pic][pic], т.е. [pic] и [pic], значит,
[pic] общего вида (не обладает ни четностью, ни нечетностью); [pic] не
является периодической как дробно-рациональная функция (многочлены –
непериодические функции).
5) а) при [pic] [pic]; значит,
[pic] - точка пересечения графика с осью ординат;
(4)
б) [pic] при [pic], но [pic], т.е. при [pic] или [pic], т.о.
[pic] и [pic] - точки пересечения графика [pic] с осью
абсцисс. (5)
С учетом точек разрыва и найденных значений функции (по (1), (2), (3) и
(4), (5)) получаем: при [pic] [pic]; при [pic] [pic];
при [pic] [pic]; при [pic] [pic].
6) [pic]
(использована формула: [pic] );
а) нет критических точек, где [pic] не существует, т.к. [pic] не
имеет значе-
ния только при [pic], но [pic];
б) [pic] при [pic] и [pic], т.е. при [pic]; [pic];
значит, [pic] и [pic] - критические точки, а
[pic][pic]; [pic].
7)
|[pic] |[pic] |[pic]|[pic] |[pic] |[pic] |[pic]|[pic] |[pic] |
|[pic] |+ |0 |- |нет |- |0 |+ |+ |
| | | | |зн. | | | | |
|[pic] |[pic] |[pic]| |нет | |[pic]| | |
| | | | |зн. | | | | |
| |от | |от[pic]|вертик|от | |от[pic]|от[pic|
|выводы|[pic] |max | |. |[pic] |min | |] |
| |до[pic]| |до |асимпт|до[pic]| |до[pic]|до |
| | | |[pic] | | | | |[pic] |
Т.к. при[pic]и[pic] [pic], то преобразуем формулу[pic] [pic]; тогда
[pic]; [pic];
[pic]; поэтому [pic], [pic]; [pic], [pic].
8)[pic];
|[pi|-17 |-14 |-12 |-3 |3 |8 |13 |
|c] | | | | | | | |
|[pi|-36 |-36 |-38 |2,5 |-2 |2/3 |4,5 |
|c] | | | | | | | |
9) см. 5).
10) [pic].
5 y
-21 -17 -14 -12 -7
-2 0 7 12 x
[pic]
[pic]
-2
[pic]
-12
-36
-38
-40
Приложение 2.
Темы рефератов
1. Возникновение понятия числа; первые системы счисления.
2. Математика в Древнем Египте.
3. Математика в Древней Месопотамии (Шумер, Вавилон, Ассирия).
4. Математика в Древнем Китае.
5. Математика в Древней Греции (1 тысячелетие до н.э.).
6. Пифагор. *)
7. Аристотель.
8. Евклид.
9. Архимед.
10. Математика Древней Греции и Древнего Рима (начало новой эры – I-V века;
Александрийская школа).
11. Средневековье. Математика в Индии.
12. Математика в Средней Азии (VIII-XIII века, Улугбек, Омар Хайам и др.).
13. Математика в древней Руси (VIII-XIII века).
14. Математика в эпоху Возрождения (Западная Европа; XII-XV века).
15. Леонардо Пизанский (Фибоначчи). XV век.
16. Леонардо да Винчи. XV век.
17. Франсуа Виет. XVI век.
18. Джон Нэпер (Непер). XVI век.
19. Кардано и Тарталья. XVI век.
20. Коперник, Тихо Браге, Кеплер, Галилей. XVI век.
21. Рене Декарт. XVII век.
22. Блез Паскаль. XVII век.
23. Исаак Ньютон. XVII век.
24. Г.В.Лейбниц. XVII век.
25. Пьер Ферма. XVII век.
26. Даламбер. XVIII век.
27. Леонард Эйлер. XVIII век.
28. Ж.Л.Лагранж. XVIII век.
29. А.М.Лежандр. XVIII век.
30. Г.Монж. XVIII век.
31. П.С.Лаплас. XVIII век.
32. Математика в России XVII-XVIII веков (Роль реформ Петра I; Екатерина
II).
33. М.В.Ломоносов.
34. Знаменитые задачи древности (об удвоении куба, о трисекции угла, о
спрямлении окружности) и их разрешение (вплоть до XVIII века).
35. К.Ф.Гаусс.
36. Различные доказательства V постулата Евклида (до XIX в. н.э.).
37. Н.И.Лобачевский
38. Основные первоначальные факты геометрии Лобачевского, модели плоскости
Лобачевского.
39. Нильс Абель. XIX век.
40. Эварист Галуа. XIX век.
41. Огюстен Коши. XIX век.
42. Карл Вейерштрасс. XIX век.
43. М.В.Остроградский. XIX век.
44. П.Л.Чебышёв. XIX век.
45. С.В.Ковалевская. XIX век.
46. Ф.Клейн. XIX век.
47. А.Пуанкаре. XIX век.
48. Г.Кантор. XIX век.
49. Б.Риман. Конец XIX века.
50. Д. Гильберт. Конец XIX века.
51. Французская математическая школа (XVII-XX в.в.).
52. Немецкая математическая школа (XVII-XX в.в.).
53. Английская математическая школа (XVII-XX в.в.).
54. Российская математическая школа (XVIII-началоXX в.в.).
55. Советская математическая школа.
56. Американская математическая школа (XIX-X X в.в.).
57. Н.Винер.
58. А.Н.Колмогоров.
59. Математика XX века; основные направления развития.
60. Основные стадии развития науки; основные черты современной математики и
ее роль в развитии общества.
Примечание. Дополнительная литература к работе над рефератом не
указана, т.к. подбор литературы входит как часть в самостоятельную работу
студента (этому надо научиться). В пособии Д.Я.Стройка [11] в конце каждой
главы есть список рекомендуемой литературы. Можно использовать то, что
найдется в личной библиотеке или в ближайшей общественной, в т.ч. и статьи
из журналов “Квант”, “Математика в школе” и других периодических изданий, а
также энциклопедические словари.
Приложение 3.
Вопросы к зачету по курсу “Математика”
для студентов I курса исторического факультета СГУ
Часть 1. Математика.
1. Понятие множества; элементы множества; мощность множества; отношения
принадлежности и включения. Виды множеств.
2. Числовые множества.
3. Операции над множествами, их свойства.
4. Соответствия между элементами множеств, их виды (в т.ч. отображения и
биекция).
5. Функции, их исследование.
6. Понятие графа. Виды графов, их применение.
7. Понятие о комбинаторной задаче. Правила суммы и произведения.
8. Порядок на множестве. Количество всех порядков множества мощности [pic].
Перестановки из [pic] элементов.
9. Подмножества из [pic] элементов по [pic]. Сочетания. Количество всех
подмножеств множества, содержащего [pic] элементов.
10. Упорядоченные подмножества из [pic] элементов по [pic]. Размещения.
Связь размещений и сочетаний. Количество размещений и количество
сочетаний из [pic] по [pic]. Размещения с повторениями.
11. Свойства сочетаний, их применение.
12. Случайные события. Достоверные и невозможные события. Испытание,
элементарный исход, полная система исходов. Относительная частота и
вероятность наблюдаемого события.
13. Совместные и несовместные, зависимые и независимые события. Правила
суммы и произведения.
14. Случайные величины. Функция распределения случайных величин.
Математическое ожидание.
15. Дисперсия. Закон больших чисел.
16. Высказывания; высказывательные формы; кванторы общности и
существования. Область отправления и множество истинности высказывания.
17. Логические операции над высказываниями (логические связки), порядок их
выполнения в сложной формуле.
18. Отрицания логических связок.
19. Свойства дизъюнкции и конъюнкции.
20. Свойства импликации и эквивалентности.
Часть 2. История математики.
1. Этапы развития науки; роль математики в развитии наук и особенности ее
развития.
2. Возникновение основных математических понятий (число, фигура,…).
3. Обозначения чисел и системы счисления у разных народов.
4. Математика в древних Месопотамии и Египте. Математика в древних Китае и
Индии.
5. Математика в Древней Греции и Древнем Риме.
6. Математика в Средние Века (Средняя Азия).
7. Математика в древней Руси.
8. Математика средних веков в Западной Европе.
9. Математика Эпохи Возрождения.
10. Математика Западной Европы в XVII веке.
11. Математика в России в XIV-XVII в. (влияние татаро-монгольского ига и
отношений с Западной Европой).
12. Развитие математики в XVIII веке в Западной Европе.
13. То же – в России.
14. Возникновение дифференциального и интегрального исчислений; их
развитие.
15. Геометрия – XIX век.
16. 23 проблемы, поставленные Гильбертом, их решение.
17. Основные ветви математики, их зарождение и роль в настоящее время
(алгебра, теория чисел, теория вероятностей, тригонометрия,…).
18. Кибернетика и информатика.
19. Основания математики и математическая логика.
20. Основные черты современной математики и пути ее развития.
Сентябрь 2001 года
Н.А.Попова
*) Здесь и далее имя ученого означает, что требуется изложить сведения о
его жизни и его вкладе в историю развития математики.
-----------------------
Л Ь В
О
И
Б Е
Ч Ш Ы
П А Ф Н У Т Й Й
П А Ф
Н У Т
Й
И
Л Ь
О
В ЧЧ
Ч
Б Е Ш Ы
Е Ш ВЫ
Реферат на тему: Методы и алгоритмы построения элементов систем статистического моделирования
Факультет повешения квалификации преподавателей
при КГТУ им. А.Н. Туполева
Направление : Электроника и вычислительная техника
Секция : Моделирование
Выпускная работа
« Методы и алгоритмы построения элементов систем
статистического моделирования»
Выполнил : аспирант Аджели М. А.
Руководитель : профессор Захаров В. М.
Оценка : _______________
Подпись : _______________
Казань, 1999г.
Содержание
Введение
1. Метод статистического моделирования систем
2. Моделирование случайных величин и процессов
3. Основные понятия марковских процессов
4. Математический аппарат дискретных марковских цепей
Введение
В настоящее время нельзя назвать область человеческой деятельности, в
которой в той или иной степени не использовались бы методы моделирования.
Особенно это относится к сфере управления различными системами, где
основными являются процессы принятия решений на основе получаемой
информации.
Метод моделирования широко применяют в таких областях, как
автоматизация проектирования и организации в автоматизированных системах
научных исследований, в системах исследования и проектирования, в системах
массового обслуживания, анализ различных сторон деятельности человека,
автоматизированное управление производственными и другими процессами. Важно
подчеркнуть, что моделирование используется при проектировании, создании,
внедрении, эксплуатации систем, а также на различных уровнях их изучения,
начиная от анализа работы элементов и кончая исследованием системы в целом
при их взаимодействии с окружающей средой.
1. Метод статистического моделирования систем
На этапе исследования и проектирования систем при построении и
реализации машинных моделей (аналитических и имитационных) широко
используется метод статистического моделирования (Монте-Карло), который
базируется на использовании случайных чисел, т.е. возможных значений
некоторой случайной величины с заданным распределением вероятностей.
Статистическое моделирование представляет собой метод получения с помощью
ЭВМ статистических данных о процессах, происходящих в моделируемой системе.
Для получения представляющих интерес оценки характеристик моделируемой
системы S с учетом воздействий внешней среды Е статистические данные
обрабатываются и классифицируются с использованием методов математической
статистики,
Сущность метода статистического моделирования сводится к построению
для процесса функционирования исследуемой системы S некоторого
моделирующего алгоритма, имитирующего поведение и взаимодействие элементов
системы с учетом случайных входных воздействий и воздействий внешней среды
Е, и реализации этого алгоритма с использованием программно-технических
средств ЭВМ.
Различают две области применения метода статистического моделирования:
- для изучения стохастических систем;
- для решения детерминированных задач.
Основной идеей, которая используется для решения детерминированных
задач методом статистического моделирования, является замена
детерминированной задачи эквивалентной схемой некоторой стохастической
системы, выходные характеристики последней совпадают с результатом решения
детерминированной задачи. При такой замене погрешность уменьшается с
увеличением числа испытаний (реализации моделирующего алгоритма) N.
В результате статистического моделирования системы S получается серия
частных значений искомых величин или функций, статистическая обработка
которых позволяет получить сведения о поведении реального объекта или
процесса в произвольные моменты времени. Если количество реализации N
достаточно велико, то полученные результаты моделирования системы
приобретают статистическую устойчивость и с достаточной точностью могут
быть приняты в качестве оценок искомых характеристик процесса
функционирования системы S.
При статистическом моделировании систем одним из основных вопросов
является учет стохастических воздействий. Количество случайных чисел,
используемых для получения статистически устойчивой оценки характеристики
процесса функционирования системы S при реализации моделирующего алгоритма
на ЭВМ, колеблется в достаточно широких пределах в зависимости от класса
объекта моделирования, вида оцениваемых характеристик, необходимой точности
и достоверности результатов моделирования. Для метода статистического
моделирования на ЭВМ характерно, что большое число операций, а
соответственно большая доля машинного времени расходуются на действия со
случайными числами. Кроме того, результаты статистического моделирования
существенно зависят от качества исходных (базовых) последовательностей
случайных чисел. Поэтому наличие простых и экономичных способов
формирования последовательностей случайных чисел требуемого качества во
многом определяет возможность практического использования машинного
моделирования системы.
Понятие «статистическое моделирование» тесно связано с понятием «метод
Монте-Карло» и почти ему тождественно.
Для решения задач методом Монте-Карло необходимо получать на ЭВМ
последовательность выборочных значений случайной величины с заданным
распределением. Такой процесс принято называть моделированием случайной
величины. Случайные величины обычно моделируют с помощью преобразований
одного или нескольких независимых значений случайной величины а, равномерно
распределенной в интервале (0,1). Независимые случайные величины,
равномерно распределенные в интервале (0,1).
Можно выделить следующие этапы моделирования случайных величин:
. генерирование N реализации случайной величины с требуемой функцией
распределения;
. преобразование полученной величины, определяемой математической моделью;
. статистическая обработка реализации.
Особенностью первого этапа является то, что все методы для получения
заданного распределения используют преобразование равномерно распределенной
величины.
Конструктивно задаются случайная величина, равномерно распределенная в
интервале (0,1), [pic](0,l), далее производится отображение [pic] [pic] и
получается новая случайная величина [pic] с распределением, определяемым
решаемой задачей, в общем случае [pic] может быть довольно сложным.
Далее следует получение некоторых характеристик. При параметрических
оценках вычисляется некоторая функция [pic]. При непараметрическом задании
функций распределения обычно вычисляются плотности или функции
распределения. Чаще всего находят оценки математической ожидания.
Погрешность оценки определяется дисперсией (если она известна) по числу
экспериментов N.
В результате можно выделить следующие этапы (рис. 4.1):
- подготовка исходных данных (блок 1),
- генерирование равномерно распределенных случайных чисел (блок 2),
- преобразования для получения заданного закона распределения (блок 3);
- выполнение дополнительных преобразований в соответствии с проблем ной
областью (блок 4);
- статистическая обработка (блок 5).
Рис. 4.1. Технологический процесс в Монте-Карло системах
где:
- ПИД - подготовка исходных данных,
- ГРРСЧ - генерирование равномерно распределенных случайных чисел;
- ГПЗ - генерирование произвольного (заданного) закона распределения;
- ДПр - дополнительные преобразования;
- СО - статистическая обработка.
Имитационные системы имеют следующие функциональные блоки:
- имитации входных процессов;
- имитации правил переработки входной информации исследуемой системы;
- накопления информации в результате моделирования;
- анализа накопленной информации;
- управления имитирующей системы.
Традиционный подход использует все классы задач, что и в методе Монте-
Карло. Рассмотрим подробнее аналитический подход задания экзогенных
переменных (первый случай). Они являются выходными другой подсистемы
макросистемы и сами представляют собой макромодель. В рассматриваемом
случае характеристики заданы аналитически.
Информационно технологическая блок-схема представлена на рис. 4.2.
Рис. 4.2. Технологический процесс имитационной системы
ГСП - генерирование случайных (входных) процессов;
ИС - имитационная система.
На первом этапе находят наиболее подходящие методы и алгоритмы для
описания аналитических функций распределения и проводят вычисления (блок 1)
для определения исходных данных, например, при аппроксимационных методах -
координаты узлов, коэффициентов и т.п.
Во втором и третьем блоках производится генерирование случайных чисел
с равномерным распределением (, и экзогенных случайных процессов (.
Блок 4 имитирует работу исследуемой системы, результаты его работы
накапливаются для последующей статистической обработки. В последнем, пятом,
блоке осуществляется статистическая обработка.
При моделировании систем на ЭВМ программная имитация случайных
воздействий любой сложности сводится к генерированию некоторых стандартных
(базовых) процессов и к их последующему функциональному преобразованию. В
качестве базового может быть принят любой удобный в случае моделирования
конкретной системы S процесс (например, пуассоновский поток при
моделировании Q-схемы). Однако при дискретном моделировании базовым
процессом является последовательность чисел [pic], представляющих собой
реализации независимых, равномерно распределенных на интервале (0,1)
случайных величин [pic] или – в статистических терминах- повторную выборку
из равномерно распределенной на (0,1) генеральной совокупности значений
величины (.
Непрерывная случайная величина ( имеет равномерное распределение в
интервале (а,b), если ее функция плотности (рис. 4.3,а) и распределение
(рис. 4.3,6) соответственно примут вид:
Рис. 4.3. Равномерное распределение случайной величины
[pic]
2. Моделирование случайных величин и процессов
Под статистическим моделированием понимается воспроизведение с помощью
ЭВМ функционирования вероятностной модели некоторого объекта.
Задачи статистического моделирования состоят в том, чтобы научиться
воспроизводить с помощью ЭВМ поведение таких моделей, например:
- с помощью специальных методов и средств вырабатывать программы
реализации случайных чисел;
- с помощью этих чисел получать реализацию случайных величин или случайных
процессов с более сложными законами распределения;
- с помощью полученных реализации вычислять значения величин,
характеризующих модель, и производить обработку результатов
экспериментов;
Устанавливать связь алгоритмов моделирования с алгоритмами решения
задач вычислительной математики с помощью метода Монте-Карло и строить так
называемые «фиктивные» модели, т.е. модели, не имеющие связи с объектом
моделирования, но удобные в вычислительном отношении и позволяющие
вычислять нужные нам характеристики объекта.
Моделирование случайных процессов строится на основе базовых
распределений случайных величин.
Одним из таких процессов является марковские процессы.
3. Основные понятия марковских процессов
Марковские случайные процессы названы по имени выдающегося русского
математика А.А. Маркова (1856-1922), впервые начавшего изучение
вероятностной связи случайных величин и создавшего теорию, которую можно
назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились
исходной базой общей теории случайных процессов, а также таких важных
прикладных наук, как теория диффузионных процессов, теория надежности,
теория массового обслуживания и т.д. В настоящее время теория марковских
процессов и ее приложения широко применяются в самых различных областях
таких наук, как механика, физика, химия и др.
Благодаря сравнительной простоте и наглядности математического
аппарата, высокой достоверности и точности получаемых решений особое
внимание марковские процессы приобрели у специалистов, занимающихся
исследованием операций и теорией принятия оптимальных решений.
Несмотря на указанную выше простоту и наглядность, практическое
применение теории марковских цепей требует знания некоторых терминов и
основных положений, на которых следует остановиться перед изложением
примеров.
Как указывалось, марковские случайные процессы относятся к частным
случаям случайных процессов (СП). В свою очередь, случайные процессы
основаны на понятии случайной функции (СФ).
Случайной функцией называется функция, значение которой при любом
значении аргумента является случайной величиной (СВ). По- иному, СФ можно
назвать функцию, которая при каждом испытании принимает какой-либо заранее
неизвестный вид.
Такими примерами СФ являются: колебания напряжения в электрической
цепи, скорость движения автомобиля на участке дороги с ограничением
скорости, шероховатость поверхности детали на определенном участке и т.д.
Как правило, считают, что если аргументом СФ является время, то такой
процесс называют случайным. Существует и другое, более близкое к теории
принятия решений, определение СП. При этом под случайным процессом понимают
процесс случайного изменения состояний какой-либо физической или
технической системы по времени или какому-либо другому аргументу.
Нетрудно заметить, что если обозначить состояние [pic] и изобразить
зависимость [pic], то такая зависимость и будет случайной функцией.
СП классифицируются по видам состояний [pic] и аргументу t. При этом
СП могут быть с дискретными или непрерывными состояниями или временем.
Например, любой выборочный контроль продукции будет относиться к СП с
дискретными состояниями ([pic]- годная, [pic]- негодная продукция) и
дискретным временем ([pic], [pic]- времена проверки). С другой стороны,
случай отказа любой машины можно отнести к СП с дискретными состояниями, но
непрерывным временем. Проверки термометра через определенное время будут
относиться к СП с непрерывным состоянием и дискретным временем. В свою
очередь, например, любая осциллограмма будет записью СП с непрерывными
состояниями и временем.
Кроме указанных выше примеров классификации СП существует еще одно
важное свойство. Это свойство описывает вероятностную связь между
состояниями СП. Так, например, если в СП вероятность перехода системы в
каждое последующее состояние зависит только от предыдущего состояния, то
такой процесс называется процессом без последействия (рис.1).
Зависимость [pic] называют переходной вероятностью, часто говорят, что
именно процесс[pic] без последействия обладает марковским свойством,
однако, строго говоря, здесь есть одна неточность. Дело в том, что можно
представить себе СП, в котором вероятностная связь существует не только с
предшествующими, но и более ранними ([pic]) состояниями, т.е.
[pic] (1)
Рис. 1. Схема процесса без последействия
Такие процессы также рассматривались А.А. Марковым, который предложил
называть их в отличие от первого случая (простой цепи) - сложной цепью. В
настоящее время теория таких цепей разработана слабо и обычно применяют так
называемый процесс укрупнения состояний путем математических
преобразований, объединяя предшествующие состояния в одно.
Это обстоятельство должно обязательно учитываться при составлении
математических моделей принятия решений.
Выше мы совершили незаметный терминологический переход от понятия СП к
“марковской цепи”. Теперь эту неясность следует устранить. Отметим, во-
первых, что случайный процесс с дискретными состояниями и временем
называется случайной последовательностью.
Если случайная последовательность обладает марковским свойством, то
она называется цепью Маркова.
С другой стороны, если в случайном процессе состояния дискретны, время
непрерывно и свойство последействия сохраняется, то такой случайный процесс
называется марковским процессом с непрерывным временем.
Марковский СП называется однородным, если переходные вероятности
[pic] остаются постоянными в ходе процесса.
Цепь Маркова считается заданной, если заданы два условия.
1. Имеется совокупность переходных вероятностей в виде матрицы:
[pic]. (2)
2. Имеется вектор начальных вероятностей
[pic], ….. (3)
описывающий начальное состояние системы.
Матрица (2) называется переходной матрицей (матрицей перехода).
Элементами матрицы являются вероятности перехода из i-го в j-е состояние
за один шаг процесса. Переходная матрица (2) обладает следующими
свойствами:
a) [pic],
(3a)
б) [pic].
Матрица, обладающая свойством (3a), называется стохастической. Кроме
матричной формы модель марковской цепи может быть представлена в виде
ориентированного взвешенного графа (рис. 2).
Рис. 2. Ориентированный взвешенный граф
Вершины графа обозначают состояние [pic], а дуги- переходные
вероятности.
Множество состояний системы марковской цепи, определенным образом
классифицируется с учетом дальнейшего поведения системы.
1. Невозвратное множество (рис. 3).
Рис. 3. Невозвратное множество
В случае невозвратного множества возможны любые переходы внутри этого
множества. Система может покинуть это множество, но не может вернуться в
него.
2. Возвратное множество (рис. 4).
Рис. 4. Возвратное множество
В этом случае также возможны любые переходы внутри множества. Система
может войти в это множество, но не может покинуть его.
3. Эргодическое множество (рис. 5).
Рис. 5. Эргодическое множество
В случае эргодического множества возможны любые переходы внутри
множества, но исключены переходы из множества и в него.
4. Поглощающее множество (рис. 6)
Рис. 6. Поглощающее множество
При попадании системы в это множество процесс заканчивается.
Кроме описанной выше классификации множеств различают состояния
системы:
а) существенное состояние (рис.7): возможны переходы из [pic] в [pic]
и обратно.
Рис. 7. Существенное состояние
б) несущественное состояние (рис. 8): возможен переход из [pic] в
[pic], но невозможен обратный.
Рис. 8. Несущественное состояние
В некоторых случаях, несмотря на случайность процесса, имеется
возможность до определенной степени управлять законами распределения или
параметрами переходных вероятностей. Такие марковские цепи называются
управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ)
особенно эффективным становится процесс принятия решений, о чем будет
сказано впоследствии.
Основным признаком дискретной марковской цепи (ДМЦ) является
детерминированность временных интервалов между отдельными шагами (этапами)
процесса. Однако часто в реальных процессах это свойство не соблюдается и
интервалы оказываются случайными с каким-либо законом распределения, хотя
марковость процесса сохраняется. Такие случайные последовательности
называются полумарковскими.
Кроме того, с учетом наличия и отсутствия тех или иных, упомянутых
выше, множеств состояний марковские цепи могут быть поглощающими, если
имеется хотя бы одно поглощающее состояние, или эргодическими, если
переходные вероятности образуют эргодическое множество.
В свою очередь, эргодические цепи могут быть регулярными или
циклическими. Циклические цепи отличаются от регулярных тем, что в процессе
переходов через определенное количество шагов (циклов) происходит возврат в
какое-либо состояние. Регулярные цепи этим свойством не обладают. Если
просуммировать все вышесказанные определения, то можно дать следующую
классификацию марковских процессов (рис. 9):
Рис. 9. Классификация марковских процессов
4. Математический аппарат дискретных марковских цепей
В дальнейшем рассматриваются простые однородные марковские цепи с
дискретным временем. Основным математическим соотношением для ДМЦ является
уравнение, с помощью которого определяется состояние системы на любом ее k-
м шаге. Это уравнение имеет вид:
[pic] (4)
и называется уравнением Колмогорова-Чепмена.
Уравнение Колмогорова-Чепмена относится к классу рекуррентных
соотношений, позволяющих вычислить вероятность состояний марковского
случайного процесса на любом шаге (этапе) при наличии информации о
предшествующих состояниях.
Дальнейшие математические соотношения зависят от конкретного вида
марковской цепи.
2.1. Поглощающие марковские цепи
Как указывалось выше, у поглощающих ДМЦ имеется множество, состоящее
из одного или нескольких поглощающих состояний.
Для примера рассмотрим переходную матрицу, описывающую переходы в
системе, имеющей 4 возможных состояния, два из которых являются
поглощающими. Матрица перехода такой цепи будет иметь вид:
[pic] (5)
Практически важным является вопрос о том, сколько шагов сможет пройти
система до остановки процесса, то есть поглощения в том или ином состоянии.
Для получения дальнейших соотношений путем переименования состояний матрицу
(8.5) переводят к блочной форме:
[pic] (6)
[pic]
Такая форма позволяет представить матрицу (6) в каноническом виде:
[pic] (6а)
где [pic] - единичная матрица;
[pic] - нулевая матрица;
[pic] - матрица, описывающая переходы в системе из невозвратного
множества состояний в поглощающее множество;
[pic] - матрица, описывающая внутренние переходы в системе в
невозвратном множестве состояний.
На основании канонической формы (6а) получена матрица, называемая
фундаментальной:
[pic] (7)
В матрице (7) символ (-1) означает операцию обращения, то есть
[pic] (8)
После соответствующих преобразований матрица (7) примет вид:
[pic] (7а)
Каждый элемент матрицы (7а) соответствует среднему числу раз попадания
системы в то или иное состояние до остановки процесса (поглощения).
Если необходимо получить общее среднее количество раз попадания
системы в то или иное состояние до поглощения, то фундаментальную матрицу
М необходимо умножить справа на вектор-столбец, элементами которого будут
единицы, то есть
[pic] (8а)
где [pic].
Для иллюстрации приведем конкретный числовой пример: пусть известны
значения переходных вероятностей матрицы [pic] с одним поглощающим
состоянием: [pic]; [pic]; [pic]; [pic]; [pic]; [pic]; [pic]; [pic].
Переходная матрица в блочной системе будет выглядеть так:
[pic]
В данном случае
[pic]; [pic]; [pic] ; [pic]
Проделаем необходимые вычисления:
[pic];
[pic];
[pic] .
В данном случае компоненты вектора [pic] означают, что если процесс
начинается с состояния [pic], то общее среднее число шагов процесса до
поглощения будет равно 3,34 и, соответственно, если процесс начинается с
состояния [pic], то - 2,26.
В конкретных задачах, конечно, более информативным результатом будет
не количество шагов, а какие-либо временные или экономические показатели.
Этот результат легко получить, если связать пребывание в каждом состоянии с
соответствующими характеристиками. Очевидно, набор этих характеристик
составит вектор, на который нужно умножить [pic] слева.
Так, если задать в нашем примере время пребывания в состоянии
[pic] [pic], а в состоянии [pic]- [pic], то общее время до поглощения будет
равно:
[pic]
В случаях, когда марковская цепь включает несколько поглощающих
состояний, возникают такие вопросы: в какое из поглощающих состояний цепь
попадет раньше (или позже); в каких из них процесс будет останавливаться
чаще, а в каких - реже? Оказывается, ответ на эти вопросы легко
получить, если снова воспользоваться фундаментальной матрицей.
Обозначим через [pic] вероятность того, что процесс завершится в
некотором поглощающем состоянии [pic] при условии, что начальным было
состояние [pic]. Множество состояний [pic] снова образует матрицу, строки
которой соответствуют невозвратным состояниям, а столбцы - всем поглощающим
состояниям. В теории ДМЦ доказывается, что матрица В определяется следующим
образом:
[pic] (8.9)
где
М - фундаментальная матрица с размерностью S;
R - блок фундаментальной матрицы с размерностью r.
Рассмотрим конкретный пример системы с четырьмя состояниями [pic],
два из которых- [pic]- поглощающие, а два - [pic]- невозвратные (рис.10):
Рис. 8.10. Система с четырьмя состояниями
Для наглядности и простоты вычислений обозначим переходные вероятности
следующим образом:
[pic]; [pic]; [pic]
Остальные значения вероятностей будут нулевыми. Каноническая форма
матрицы перехода в этом случае будет выглядеть так:
[pic]
Фундаментальная матрица после вычислений примет вид:
[pic]
Тогда, согласно формуле (9), матрица вероятностей поглощения
вычисляется так:
[pic].
Поясним вероятностный смысл полученной матрицы с помощью конкретных
чисел. Пусть[pic], а[pic]. Тогда после подстановки полученных значений в
матрицу [pic]получим:
[pic]
Таким образом, если процесс начался в [pic], то вероятность попадания
его в [pic] равна [pic], а в [pic] - [pic]. Отметим одно интересное
обстоятельство: несмотря на то, что, казалось бы, левое поглощающее
состояние (“левая яма”) находится рядом с [pic], но вероятность попадания
в нее почти в два раза меньше, чем в “удаленную яму” - [pic]. Этот
интересный факт подмечен в теории ДМЦ, и объясняется он тем, что [pic], то
есть процесс имеет как бы “правый уклон”. Рассмотренная выше модель
называется в теории ДМЦ моделью случайного блуждания. Такими моделями часто
объясняются многие физические и технические явления и даже поведение
игроков во время различных игр.
В частности, в рассмотренном примере объясняется тот факт, что более
сильный игрок может дать заранее значительное преимущество (“фору”) слабому
противнику и все равно его шансы на выигрыш будут более предпочтительными.
Кроме указанных выше средних характеристик вероятностного процесса с
помощью фундаментальной матрицы можно вычислить моменты и более высоких
порядков. В частности, дисперсия числа пребывания в том или ином состоянии
- D определяется с помощью следующей матрицы:
[pic] (10)
где
[pic] - диагональная матрица, т.е. матрица, полученная из М путем
оставления в ней лишь диагональных элементов и замены остальных элементов
нулями. Например, приведенная выше матрица (7а) будет иметь вид:
[pic]
В свою очередь, матрица М представляет собой матрицу, полученную из М
путем возведения в квадрат каждого ее элемента, то есть для (7а) будем
иметь:
[pic]
Аналогичным образом определяема и дисперсия для общего количества раз
пребывания в том или ином состоянии [pic]. Обозначим ее [pic]:
[pic] (11)
2.2. Эргодические цепи
Как указывалось выше под эргодической ДМЦ понимается цепь, не имеющая
невозвратных состояний. Таким образом, в такой цепи возможны любые переходы
между состояниями. Напомним, что эргодические цепи могут быть регулярными и
циклическими. Ранее определение таких цепей было дано.
Поскольку согласно данному выше определению в эргодической ДМЦ на
любом шаге должны быть возможными любые переходы, то очевидно при этом, что
переходные вероятности не должны равняться нулю. Оказывается, из этого
условия вытекают некоторые замечательные свойства регулярных ДМЦ:
1. Степени [pic] при [pic] стремятся к стохастической матрице [pic].
2. Каждая строка матрицы [pic] представляет один и тот же вероятностный
вектор
[pic] (12)
все компоненты которого положительны.
Вектор (12) в теории ДМЦ занимает особое место из-за наличия многих
приложений и называется вектором предельных или финальных вероятностей
(иногда - стационарным вектором). Финальные вероятности определяют с
помощью векторно-матричного уравнения
[pic] (13)
которое в развернутом виде будет выглядеть так:
[pic] (13а)
К уравнениям (8.13а) можно дополнительно добавить условие нормировки:
[pic] (14)
Тогда любое из уравнений в (8.14) можно исключить.
Так же, как и в случае поглощения ДМЦ многие характеристики
эргодических цепей определяются с помощью фундаментальной матрицы, которая
в этом случае будет иметь вид:
[pic] (15)
Для эргодических цепей характеристикой, имеющей важное практическое
значение, является продолжительность времени, за которое процесс из
состояния [pic] впервые попадает в [pic], так называемое время первого
достижения. Матрица средних времен достижения определяется по формуле:
[pic] (16)
где
[pic] - фундаментальная матрица (15);
[pic] - диагональная матрица, образованная из фундаментальной заменой
всех элементов, кроме диагональных, нулями;
D - диагональная матрица с диагональными элементами, [pic];
Е - матрица, все элементы которой равны единице.
Матрица дисперсий времени первого достижения имеет несколько более
сложный вид:
[pic] (17)
где кроме уже упомянутых обозначений встречается новое - ([pic],
обозначающее диагональную матрицу, полученную из матричного произведения
матриц [pic].
2.3. Управляемые марковские цепи
Как указывалось выше, под управляемыми марковскими процессами понимают
такие, у которых имеется возможность до определенной степени управлять
значениями переходных вероятностей. В качестве примеров таких процессов
можно привести любые торговые операции, у которых вероятность сбыта и
получения эффекта может зависеть от рекламы, мероприятий по улучшению
качества, выбора покупателя или рынка сбыта и т.д.
Очевидно, что при создании математических моделей в данном случае
должны фигурировать следующие компоненты:
- конечное множество решений (альтернатив) [pic], где [pic] - номер
состояния системы;
- матрицы переходов [pic]соответствующие тому или иному принятому k-му
решению;
- матрицы доходов (расходов) [pic], также отражающие эффективность
данного решения.
Управляемой цепью Маркова (УЦМ) называется случайный процесс,
обладающий марковским свойством и включающий в качестве элемента
математической модели конструкцию (кортеж) [pic]. Решение, принимаемое в
каждый конкретный момент (шаг процесса), назовем частным управлением.
Таким образом, процесс функционирования системы, описываемой УЦМ,
выглядит следующим образом:
- если система находится в состоянии [pic] и принимается решение [pic],
то она получает доход [pic];
- состояние системы в последующий момент времени (шаг) определяется
вероятностью [pic], то есть существует вероятность того, что система
из состояния [pic] перейдет в состояние [pic], если выбрано решение
[pic].
Очевидно, общий доход за n шагов является случайной величиной,
зависящей от начального состояния и качества принимаемых в течение хода
процесса решений, причем это качество оценивается величиной среднего
суммарного дохода (при конечном времени) или среднего дохода за единицу
времени (при бесконечном времени).
Стратегией ( называется последовательность решений:
[pic] (18)
где
[pic]- вектор управления.
Задание стратегии означает полное описание конкретных решений,
принимаемых на всех шагах процесса в зависимости от состояния, в котором
находится в этот момент процесс.
Если в последовательности (векторе) ( все [pic] одинаковы, то такая
стратегия называется стационарной, т.е. не зависящей от номера шага.
Стратегия [pic] называется марковской, если решение [pic], принимаемое в
каждом конкретном состоянии, зависит только от момента времени n, но не
зависит от предшествующих состояний.
Оптимальной будет такая стратегия, которая максимизирует полный
ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода
определения оптимальных стратегий: рекуррентный и итерационный.
Первый, рекуррентный, метод применяется чаще всего при сравнительно
небольшом числе шагов n. Его идея основана на применении принципа
Беллмана и заключается в последовательной оптимизации дохода на каждом шаге
с использованием рекуррентного уравнения следующего вида:
[pic] (19)
где
[pic] - полный ожидаемый доход;
[pic] шагов, если система находится в состоянии i;
[pic] - непосредственно ожидаемый доход, т.е. доход на одном
шаге, если процесс начался с i-го состояния;
[pic] - величина полного ожидаемого дохода за n прошедших шагов,
если процесс начинался с j-го состояния (i(j).
Таким образом, данный метод, по существу, аналогичен методу
динамического программирования, отличием является лишь то, что на каждом
шаге учитывается вероятность попадания системы в то или иное состояние.
Поэтому этот метод называют стохастическим динамическим программированием.
Конкретное применение метода будет рассмотрено далее на примере.
Второй - итерационный метод оптимизации применяется при неограниченном
числе этапов (шагов) процесса. Этот метод использует свойство эргодичности
марковской цепи и заключается в последовательном уточнении решения путе | |
