МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ОРГАНИЗАЦИИ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ МЕЖДИСЦИПЛИНАРНОГО КУРСА МДК.01.02 МАТЕМАТИЧЕСКИЙ АППАРАТ ДЛЯ ПОСТРОЕНИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ

Министерство образования, науки и молодежи Республики Крым Государственное бюджетное профессиональное  образовательное учреждение Республики Крым

«Феодосийский политехнический техникум»

                                                                                                      Утверждаю:

                                                                                                      Заместитель директора                                                                                                 по учебной работе

                                                                                                                        О.Г. Сердюкова                                                                                                  «07» апреля 2016 г.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ОРГАНИЗАЦИИ 

САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ

 МЕЖДИСЦИПЛИНАРНОГО КУРСА 

МДК.01.02 МАТЕМАТИЧЕСКИЙ АППАРАТ ДЛЯ ПОСТРОЕНИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ

для специальностей среднего профессионального образования

09.02.02 Компьютерные сети

2016 г.

Методические указания по организации самостоятельной работы студентов при изучении междисциплинарного курса МДК 01.02 Математический аппарат для построения компьютерных сетей разработаны на основе Рабочей программы профессионального модуля ПМ.01Участие в проектировании сетевой инфраструктуры и в соответствии с учебным планом специальности 09.02.02

Компьютерные сети.

Организация-разработчик: Государственное бюджетное профессиональное образовательное учреждение Республики Крым «Феодосийский политехнический техникум»

Разработчики: Кузьмич Г.А., преподаватель физики и математики.

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

Протокол № 1 от «28» июня 2016 года

Председатель цикловой комиссии                                                   Т.Н. Дворянова

Пояснительная записка

 Согласно учебного плана специальности 09.02.02 Компьютерные сети по междисциплинарному курсу МДК 01.02 Математический аппарат для построения компьютерных сетей объем самостоятельной работы студентов предусматривает 47 часов.

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

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

Выполнении самостоятельных работ обучающимися способствуют формированию следующих  

• общих компетенций:

 ОК.1 Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.

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

 ОК.3 Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

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

         ОК.5 Использовать информационно-коммуникационные технологии в деятельности.

 ОК.6 Работать в коллективе и команде, эффективно общаться с коллегами, потребителями.  ОК.7 Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.

 ОК.8 Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

            ОК.9 Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

• профессиональных компетенций:

ПК 1.3. Обеспечивать защиту информации в сети с использованием программно-аппаратных средств.

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

Целью методических указаний по организации самостоятельной работы студентов по междисциплинарному курсу МДК 01.02 Математический аппарат для построения компьютерных сетей является обеспечение эффективности самостоятельной работы обучающихся с литературой и интернет - ресурсами на основе организации их изучения.

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

-  активизация самостоятельной работы студентов; 

-  содействие развития творческого отношения к учебной дисциплине; 

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

Средства обучения, необходимые для организации самостоятельной работы: 

1.      Дидактические средства (первоисточники, документы, сборники задач, таблицы).

2.      Технические средства, при помощи которых предъявляется учебная информация (компьютеры, аудиовидеотехника, мультимедиа).

3.      Средства, которые используют для руководства самостоятельной деятельностью студентов (инструктивно-методические указания, карточки с дифференцированными заданиями для организации индивидуальной и групповой работы, карточки с алгоритмами выполнения заданий). 

Критерии оценки результатов самостоятельной работы

Критериями оценки результатов внеаудиторной самостоятельной работы студентов являются: уровень освоения учебного материала;

-     уровень умения использовать теоретические знания при выполнении практических задач;

-     уровень сформированности общеучебных умений;

-     уровень умения активно использовать электронные образовательные ресурсы, находить требующуюся информацию, изучать ее и применять на практике;

-     обоснованность и четкость изложения материала;

-     оформление материала в соответствии с требованиями стандарта предприятия;

-     уровень умения ориентироваться в потоке информации, выделять главное;

-     уровень умения четко сформулировать проблему, предложив ее решение, критически оценить решение и его последствия;

-     уровень умения определить, проанализировать альтернативные возможности, варианты действий;

-     уровень умения сформулировать собственную позицию, оценку и аргументировать ее.

Критерии оценки учебного конспекта:

«Отлично» - полнота использования учебного материала. Объём конспекта – 1 тетрадная страница на один раздел или один лист формата А4. Логика изложения (наличие схем, количество смысловых связей между понятиями). Наглядность (наличие рисунков, символов и пр.; аккуратность выполнения, читаемость конспекта. Грамотность (терминологическая и орфографическая). Отсутствие связанных предложений, только опорные сигналы – слова, словосочетания, символы. Самостоятельность при составлении.

«Хорошо» - использование учебного материала неполное. Объём конспекта – 1 тетрадная страница на один раздел или один лист формата А4. Недостаточно логично изложено (наличие схем, количество смысловых связей между понятиями). Наглядность (наличие рисунков, символов и пр.; аккуратность выполнения, читаемость конспекта. Грамотность (терминологическая и орфографическая). Отсутствие связанных предложений, только опорные сигналы – слова, словосочетания, символы. Самостоятельность при составлении.

«Удовлетворительно» - использование учебного материала неполное. Объём конспекта – менее одной тетрадной страницы на один раздел или один лист формата А4. Недостаточно логично изложено (наличие схем, количество смысловых связей между понятиями). Наглядность (наличие рисунков, символов, и пр.; аккуратность выполнения, читаемость конспекта. Грамотность (терминологическая и орфографическая). Отсутствие связанных предложений, только опорные сигналы – слова, словосочетания, символы. Самостоятельность при составлении. Неразборчивый почерк.

«Неудовлетворительно» - использование учебного материала неполное. Объём конспекта – менее одной тетрадной страницы на один раздел или один лист формата А 4. Отсутствуют схемы, количество смысловых связей между понятиями. Отсутствует наглядность (наличие рисунков, символов, и пр.; аккуратность выполнения, читаемость конспекта. Допущены ошибки терминологические и орфографические. Отсутствие связанных предложений, только опорные сигналы – слова, словосочетания, символы. Несамостоятельность при составлении. Неразборчивый почерк.

Критерии оценки решения расчетных задач:

«Отлично» - в логическом рассуждении и решении нет ошибок, задача решена рациональным способом.

«Хорошо» - в логическом рассуждении и решении нет существенных ошибок, но задача решена нерациональным способом или допущено не более двух несущественных ошибок.

«Удовлетворительно» - в логическом рассуждении нет существенных ошибок, но допущена существенная ошибка в математических расчетах.                                                                    

«Неудовлетворительно» - имеются существенные ошибки в логическом рассуждении и в решении или решение отсутствует.

Тематический план и содержание самостоятельной работы

№ п/п	Название темы	Вид деятельности обучаемого	Формируемые ОК	Объем часов	Форма контроля
1	Равномерное распределение непрерывной случайной величины.	Составление конспекта и решение задач	ОК.1 – ОК.9, ПК 1.4	6	Оценка конспекта и правильности решения задач
2	Нормальный закон распределения непрерывной случайной величины.	Составление конспекта и решение задач	ОК.1 – ОК.9, ПК 1.4	6	Оценка конспекта и правильности решения задач
3	Показательное распределение непрерывной случайной величины.	Составление конспекта и решение задач	ОК.1 – ОК.9, ПК 1.4	6	Оценка конспекта и правильности решения задач
4	Распределение Релея.	Составление конспекта и решение задач	ОК.1 – ОК.9, ПК 1.4	6	Оценка конспекта и правильности решения задач
5	Составление матрицы инцидентности и смежности, списка ребер и дуг для графов.	Решение задач	ОК.1 – ОК.9, ПК 1.3	4	Оценка правильности решения задач
6	Классификация случайных процессов и их характеристика.	Составление конспекта и решение задач	ОК.1 – ОК.9, ПК 1.3	4	Оценка конспекта и правильности решения задач
7	Моделирование марковского процесса.	Составление конспекта	ОК.1 – ОК.9, ПК 1.3, ПК 1.4	4	Оценка конспекта
8	Элементы теории игр и матричные игры в чистых стратегиях.	Составление конспекта	ОК.1 – ОК.9, ПК 1.3, ПК 1.4	5	Оценка конспекта
9	Решение матричных игр в смешанных стратегиях.	Составление конспекта	ОК.1 – ОК.9, ПК 1.3, ПК 1.4	6	Оценка конспекта
Всего часов самостоятельной работы по дисциплине				47

Равномерное распределение непрерывной случайной величины.

 которые выносятся на самостоятельное изучение:

Понятие равномерного распределения.

Плотность вероятности и ее графическое изображение.

3.      Функция вероятности и ее графическое изображение.

4.      Математическое ожидание и дисперсия случайной величины.

Цель изучения: систематизация и углубление знаний обучающихся при изучении темы «Основные понятия теории вероятностей»; изучить основные характеристики равномерного распределения непрерывной случайной величины.

Литература:

1. Теория вероятностей и математическая статистика [Электронный ресурс]: учебное пособие/ Т.А. Гулай [и др.].— Электрон. текстовые данные.— Ставрополь: Ставропольский государственный аграрный университет, АГРУС, 2013.— 257 c.— Режим доступа: http://www.iprbookshop.ru/47360.— ЭБС «IPRbooks», с.120 – 124, по паролю.

План изучения:

1.      Изучите тему.

2.      Составьте краткий конспект.

3.      Решить задачи:

а) Случайна величина X равномерно распределена на отрезке [-2,6]. Записать плотность и

функцию распределения этой величины, найти ее математическое ожидание и дисперсию.

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

Вопросы для самоконтроля:

1.      Что такое равномерное распределение непрерывной случайной величины?

2.      Как выглядит формула и графическое изображение плотности вероятности?

3.      Как выглядит формула и графическое изображение функции вероятности? 4. Как вычисляется математическое ожидание и дисперсия величины?

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

 которые выносятся на самостоятельное изучение:

Понятие нормального закона распределения. Числовые характеристики распределения.

3.      Функция Лапласа.

4.      Приведенная функция Лапласа.

5.      Правило «трех сигм»

Цель изучения: систематизация и углубление знаний обучающихся при изучении темы «Основные понятия теории вероятностей»; изучить основные характеристики нормального закона распределения непрерывной случайной величины.

Литература:

1. Теория вероятностей и математическая статистика [Электронный ресурс]: учебное пособие/ Т.А. Гулай [и др.].— Электрон. текстовые данные.— Ставрополь: Ставропольский государственный аграрный университет, АГРУС, 2013.— 257 c.— Режим доступа: http://www.iprbookshop.ru/47360.— ЭБС «IPRbooks», с.132 – 139, по паролю.

План изучения:

1.      Изучите тему.

2.      Составьте краткий конспект.

3.      Решить задачи:

а) Результат радиолокации шельфа моря с научного самолета есть нормально распределенная случайная величина. Каким должно среднее квадратическое отклонение этой величины, чтобы с вероятностью 0,91 абсолютная погрешность результата измерения не превосходила 100 м? Предполагается, что систематическая ошибка измерения отсутствует, т.е. m = 0.

б) Производится обстрел зенитным комплексом по мишени, имеющей вид прямоугольника с размерами (10 х 5) м². Прицеливание производится по центу цели. Заход на цель вдоль оси Oх. Характеристики рассеивания комплекса: m_x = 3 м, m_y = 2 м, 𝜎_х= 3 м, 𝜎_𝑦= 2 м. Какова вероятность попадания комплекса.

Вопросы для самоконтроля:

1.      Что такое нормальный закон распределение непрерывной случайной величины?

2.      Запишите числовые характеристики величины.

3.      Как выглядит функция Лапласа?

4.      Что такое приведенная функция? 5. Что такое правило трехх сигм?

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

 которые выносятся на самостоятельное изучение:

Понятие показательного распределения.

Функция и плотность распределения величины.

3.      Числовые характеристики распределения.

4.      Функция надежности.

5.      Правило «трех сигм».

Цель изучения: систематизация и углубление знаний обучающихся при изучении темы «Основные понятия теории вероятностей»; изучить основные характеристики показательного распределения непрерывной случайной величины.

Литература:

1. Теория вероятностей и математическая статистика [Электронный ресурс]: учебное пособие/ Т.А. Гулай [и др.].— Электрон. текстовые данные.— Ставрополь: Ставропольский государственный аграрный университет, АГРУС, 2013.— 257 c.— Режим доступа: http://www.iprbookshop.ru/47360.— ЭБС «IPRbooks», с.132 – 139, по паролю.

План изучения:

1.      Изучите тему.

2.      Составьте краткий конспект.

3.      Решить задачи:

а) Результат радиолокации шельфа моря с научного самолета есть нормально распределенная случайная величина. Каким должно среднее квадратическое отклонение этой величины, чтобы с вероятностью 0,91 абсолютная погрешность результата измерения не превосходила 100 м? Предполагается, что систематическая ошибка измерения отсутствует, т.е. m = 0.

б) Производится обстрел зенитным комплексом по мишени, имеющей вид прямоугольника с размерами (10 х 5) м². Прицеливание производится по центу цели. Заход на цель вдоль оси Oх. Характеристики рассеивания комплекса: m_x = 3 м, m_y = 2 м, 𝜎_х= 3 м, 𝜎_𝑦= 2 м. Какова вероятность попадания комплекса.

Вопросы для самоконтроля:

1.      Что такое нормальный закон распределение непрерывной случайной величины?

2.      Запишите числовые характеристики величины.

3.      Как выглядит функция Лапласа?

4.      Что такое приведенная функция? 5. Что такое правило трех сигм?

Распределение Релея.

 которые выносятся на самостоятельное изучение: Понятие распределения Релея.

2.      Числовые характеристики распределения.

3.      Решение типовых задач.

Цель изучения: систематизация и углубление знаний обучающихся при изучении темы «Основные понятия теории вероятностей»; изучить распределения Релея непрерывной случайной величины.

Литература:

1. Теория вероятностей и математическая статистика [Электронный ресурс]: учебное пособие/ Т.А. Гулай [и др.]. — Электрон. текстовые данные. — Ставрополь: Ставропольский государственный аграрный университет, АГРУС, 2013. — 257 c.— Режим доступа: http://www.iprbookshop.ru/47360. — ЭБС «IPRbooks», с.139 – 141, по паролю.

План изучения:

1.      Изучите тему.

2.      Составьте краткий конспект.

3.      Решить задачу: Производится запуск ракеты «воздух - земля». Рассеивание ракет круговое с 𝜎 = 8 м, m_x = m_y = 0. Радиус срабатывания ракеты r = 15 м. При подрыве цель поражается с вероятностью p = 0,92. Какова вероятность поражения цели?

Вопросы для самоконтроля:

1.      Что такое распределение Релея?

2.      Чему равны числовые характеристика распределения? 3. Когда случайную величину можно считать распределенной по Релею?

Составление матрицы инцидентности и смежности, списка ребер и дуг для графов.

 которые выносятся на самостоятельное изучение: Составление матрицы инцидентности.

2.      Составление матрицы смежности.

3.      Составление матрицы списка ребер.

4.      Составление матрицы списка дуг.

Цель изучения: закрепление знаний обучающихся при изучении темы «Основные элементы теории графов».

План изучения:

1. Для данных графов составить матрицу инцидентности, смежности, списка ребер и списка дуг:

1)	a)       1 5					b 3					4		2 g	3
	2)		a)      1         a                        d                    c			2	i	б)		1 h				b 3 h
	3)							б) e 5	1
	4)						б)	1 5	4		2 i
	5)		a)          1       a            b                                         i            5          h				б) 5		c h		4 3 e 2
7)       б)
8)												2 3
		9)										c 3
												b c 5

Вопросы для самоконтроля:

1.      Как составить матрицу инцидентности?

2.      Как составить матрицу смежности?

3.      Как составить матрицу списка ребер?

4.      Как составить матрицу списка дуг?

Тема 6. Классификация случайных процессов и их характеристика.

Вопросы, которые выносятся на самостоятельное изучение:

1.      Классификация случайных процессов.

2.      Математическое ожидание случайного процесса.

3.      Дисперсия случайного процесса.

4.      Корреляционная функция случайного процесса.

Цель изучения: систематизация и углубление знаний обучающихся при изучении темы «Основы теории массового обслуживания»; изучить характеристики и классификацию случайных процессов.

Литература:

1. Кацман Ю.Я. Теория вероятностей, математическая статистика и случайные процессы [Электронный ресурс]: учебник/ Кацман Ю.Я.— Электрон. текстовые данные. — Томск: Томский политехнический университет, 2013. — 131 c.— Режим доступа: http://www.iprbookshop.ru/34722.

— ЭБС «IPRbooks», с. 115 -119, по паролю.

План изучения:

1.      Изучите тему.

2.      Составьте краткий конспект.

3.      Решить задачу: Случайная величина определяется формулой 𝑌(𝑡) = 2 ∙ 𝑋 ∙ 𝑒^−𝑡, 𝑡 > 0, 𝑋 => 𝑀 (2,4), где Х – случайная величина, распределенная по нормальному закону с 𝑚_𝑥 = 2, 𝜎_𝑥 = 4. Найти математическое ожидание случайного процесса.

Вопросы для самоконтроля:

1.      Перечислите основные классы случайных процессов?

2.      Какая разница между случайным процессом с дискретным и непрерывным временем?

3.      Как задается математическое ожидание и дисперсия случайного процесса?

4.      Что такое корреляционная функция случайного процесса?

Тема 7. Моделирование марковских случайных процессов.

Вопросы, которые выносятся на самостоятельное изучение:

1.      Марковский процесс.

2.      Марковский процесс с дискретным временем.

3.      Марковский процесс с непрерывным временем.

Цель изучения: систематизация и углубление знаний обучающихся при изучении темы «Основы теории массового обслуживания»; изучить основы моделирования марковских случайных процессов.

План изучения:

1.      Изучите тему.

2.      Составьте краткий конспект.

3.      Изучить алгоритм решения марковских процессов с дискретным и непрерывным временем.

Теория:

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

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

Итак, марковский процесс удобно задавать графом переходов из состояния в состояние. Мы рассмотрим два варианта описания марковских процессов — с дискретным и непрерывным временем.

В первом случае переход из одного состояния в другое происходит в заранее известные моменты времени — такты (1, 2, 3, 4, …). Переход осуществляется на каждом такте, то есть исследователя интересует только последовательность состояний, которую проходит случайный процесс в своем развитии, и не интересует, когда конкретно происходил каждый из переходов.

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

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

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

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

(переходами из i-го состояния в j-е состояние), см. рис. 1.

Каждый переход характеризуется вероятностью перехода Pij. Вероятность Pij показывает, как часто после попадания в i-е состояние осуществляется затем переход в j-е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.

Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие состояния должна быть всегда равна 1, см. рис.2 - Фрагмент графа переходов (переходы из i-го состояния являются полной группой случайных событий)

Например, полностью граф может выглядеть так, как показано на рис. 3.

Реализация марковского процесса (процесс его моделирования) представляет    собой вычисление             последовательности (цепи)

переходов из состояния в состояние (см. рис. 4). Цепь на рис. 4 является случайной из текущего i-го состояния, достаточно разбить интервал [0; 1] на подынтервалы величиной P_i1, P_i2, P_i3, … (P_i1 + P_i2 + P_i3 + … = 1),

см. рис. 5. Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале [0; 1] случайное число r_рр и определить, в какой из интервалов оно попадает. 

После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной

процедуры для нового состояния. Результатом работы модели является марковская цепь (см. рис. 4).

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

Определим следующие три состояния: S0 — цель не повреждена; S1 — цель повреждена; S2 — цель разрушена. Зададим вектор начальных вероятностей:

	S0	S1	S2
P0	0.8	0.2	0

Значение P0 для каждого из состояний показывает, какова вероятность каждого из состояний объекта до начала стрельбы. Зададим матрицу перехода состояний.

                                                           В S0       В S1        В S2       Сумма вероятностей переходов

                                          Из S₀      0.45        0.40        0.15                  0.45 + 0.40 + 0.15 = 1

                                          Из S₁        0          0.45        0.55                    0 + 0.45 + 0.55 = 1

                                          Из S₂        0             0             1                           0 + 0 + 1 = 1

Матрица задает вероятность перехода из каждого состояния в каждое. Заметим, что вероятности

заданыостальные так,  всегдачто сумма равна вероятностей единице  (переходакуда-то  изсистема некоторого должна состояния перейти в  ^{Рисунок 6} обязательно). 

Наглядно модель марковского процесса можно представить себе в виде следующего графа (см. рис.6).

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

Проимитируем, используя таблицу случайных чисел, процесс стрельбы. Пусть начальное       состояние       будет   S0.        Возьмем последовательность из таблицы случайных чисел: 0.31, 0.53, 0.23, 0.42, 0.63, 0.21, … (случайные числа можно взять, например, из этой таблицы). 

0.31: цель находится в состоянии S₀ и остается в состоянии S₀, так как 0 <0.31 <0.45; 

0.53: цель находится в состоянии S₀ и переходит в состояние S₁, так как 0.45 <0.53 <0.45 + 0.40;

0.23: цель находится в состоянии S₁ и остается в состоянии S₁, так как 0 <0.23 <0.45;

0.42: цель находится в состоянии S₁ и остается в состоянии S₁, так как 0 <0.42 <0.45; 

0.63: цель находится в состоянии S₁ и переходит в состояние S₂, так как 0.45 <0.63 <0.45 + 0.55.

Так как достигнуто состояние S2 (далее цель переходит из S2 в состояние S2 с вероятностью 1), то цель поражена. Для этого в данном эксперименте потребовалось 5 снарядов.

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

Процедура уничтожения цели совершена за 5 тактов, то есть марковская цепь этой реализации выглядит следующим образом: S0—S0—S1—S1—S1—S2. Конечно, ответом задачи это число быть не может, так как в разных реализациях получатся разные ответы. А ответ у задачи может быть только один.

Повторяя данную           имитацию,     можно получить, например, еще такие реализации (это зависит от того, какие конкретно случайные числа выпадут): 4 (S₀—S₀—S₁—S₁—S₂); 11 (S₀— S0—S0—S0—S0—S1—S1—S1—S1—S1—S1—S2);        5

(S₁—S₁—S₁—S₁—S₁—S₂);    6          (S₀—S₀—S₁—S₁— S₁—S₁—S₂); 4 (S₁—S₁—S₁—S₁—S₂); 6 (S₀—S₀— S₁—S₁—S₁—S₁—S₂); 5 (S₀—S₀—S₁—S₁—S₁—S₂). Всего уничтожено 8 целей. Среднее число циклов в процедуре стрельбы составило: (5 + 4 +

11 + 5 + 6 + 4 + 6 + 5)/8 = 5.75 или, округляя, 6. Именно столько снарядов, в среднем, рекомендуется иметь в боевом запасе пушки для уничтожения цели при таких вероятностях попаданий.

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

На первом этапе вычислений средний ответ составил 5 снарядов, на втором этапе средний ответ составил (5 + 4)/2 = 4.5 снаряда, на третьем — (5 + 4 + 11)/3 = 6.7. Далее     ряд      средних          величин,         по        мере накопления статистики, выглядит следующим образом: 6.3, 6.2, 5.8, 5.9, 5.8. Если изобразить этот ряд в виде графика средней величины выпущенных снарядов, необходимых для поражения цели, в зависимости от номера эксперимента, то обнаружится, что данный ряд сходится к некоторой величине, которая и

является ответом (см. рис.8).                                                                                ^{Рисунок 8}

Визуально мы можем наблюдать, что график «успокаивается», разброс между вычисляемой текущей величиной и ее теоретическим значением со временем уменьшается, стремясь к статистически точному результату. То есть в некоторый момент график входит в некоторую «трубку», размер которой и определяет точность ответа.

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

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

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

Теперь каждый переход характеризуется плотностью вероятности перехода λ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, указывающий, в какое именно состояние произойдет переход.

Пример. Моделирование работы станка. Промоделируем работу станка (см. рис. 9), который может находиться в следующих состояниях: S0 — станок исправен, свободен (простой); S1 — станок исправен, занят (обработка); S2 — станок исправен, замена инструмента (переналадка)λ02 <λ21; S3 — станок неисправен, идет ремонт λ13 <λ30. 

Зададим значения параметров λ, используя экспериментальные данные, получаемые в производственных условиях: λ01 — поток на обработку (без переналадки);            λ10        —        поток обслуживания;           λ13        — оборудования; λ30 — поток восстановлений. 

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

В частности, из рис. 33.10 видно, что реализовавшаяся цепь выглядит так: S0—S1—S0—…Переходы произошли в следующие моменты времени: T0—T1—T2—T3—…, где T0 =

0, T₁ = τ₀₁, T₂ = τ₀₁ + τ₁₀.

Задача. Поскольку модель строят для того, чтобы на ней можно было решить задачу, ответ которой до этого был для нас совсем не очевиден, то сформулируем такую задачу к данному примеру. Определить долю времени в течение суток, которую занимает простой станка (посчитать по рисунку) T_ср = (T + T + T + T)/N.

Алгоритм имитации будет иметь следующий вид (см. рис .11).

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

Рис. 11. Блок-схема алгоритма моделирования непрерывного марковского процесса на примере имитации работы станка

Вопросы для самоконтроля:

1.      Что такое марковский процесс?

2.      Что такое марковский процесс с дискретным временем.

3.      Что такое марковский процесс с непрерывным временем?

Тема 8. Элементы теории игр и матричные игры в чистых стратегиях.

Вопросы, которые выносятся на самостоятельное изучение:

1.      Основные элементы теории игр.

2.      Некооперативные игры в сравнении с кооперативными.

3.      Матричные игры в чистых стратегиях.

Цель изучения: систематизация и углубление знаний обучающихся при изучении темы «Основы теории массового обслуживания»; изучить основные элементы теории игр и матричные игры в чистых стратегиях.

План изучения:

1.      Изучите тему.

2.      Составьте краткий конспект.

3.      Записать алгоритм нахождения: а) максиминной и минимаксной стратегии в игре с матрицей; б) седловой точки в игре с матрицой.

Теория:

К задачам теории игр и теории массового обслуживания сводятся многие прикладные задачи.

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

Анализ математической стороны и основных принципов ТИ был дан Дж. фон Нейманом в 1928 году. В 1944 фон Нейман и Моргенштерн опубликовали работу «Теория игр и экономического поведения», положившую начало бурному развитию математического исследования игр. Эта работа явилась основным толчком для развития линейного программирования и теории статистических решений Вальда. Она открыла новый подход к задачам выбора решений в конкурентных ситуациях.

В природе и обществе часто возникают конфликтные ситуации, в которых участвуют стороны с различными или даже противоположными интересами. Конфликтные ситуации возникают при операциях типа купли-продажи (при наличии конкуренции), в судопроизводстве, в спорте и т.д.

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

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

 Игра – это упрощенная формализованная модель реальной конфликтной ситуации.

Для математического описания игры необходимо четко сформулировать:

•     правила игры, в которых должны быть описаны возможные варианты действий игроков;

•     объем информации каждой стороны о поведении другой;

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

Игрок – это одна из сторон в игровой ситуации. 

Стратегия игрока – это его правила действия в каждой из возможных ситуаций игр.

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

Основная задача ТИ состоит в выявлении оптимальных стратегий игроков.

Конфликтные ситуации, встречающиеся в практике, порождают различные виды игр. Классификацию игр можно проводить по разным признакам. Различают игры:

•     по количеству игроков. В игре может участвовать любое конечное число игроков. Если игроки объединяются в две группы, преследующие противоположные цели, то имеет место игра двух «лиц» (парная игра). Например: шахматы – игра двух партнеров с конечным числом возможных ходов; покер – игра многих партнеров с конечным числом возможных ходов.

•     В зависимости от взаимоотношений участников различают игры некооперативные и кооперативные.

Некооперативные игры в сравнении с кооперативными.

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

Пример кооперативной игры: торг между покупателем и продавцом относительно цены ковра. Если издержки производства ковра составляют 100$, и покупатель оценивает его в 200$, возможна кооперативная игра, потому что соглашение о продаже ковра по цене между 101$ и 199$ максимизирует сумму излишка покупателя и прибыли продавца, улучшая положение обоих сторон.

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

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

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

Будем заниматься некооперативными играми.

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

У каждого игрока А и В конечное число возможных действий – чистых стратегий.

Игрок А располагает m чистыми стратегиями А1, А2, …, Аm.   Игрок В –    n чистыми стратегиями

B1, B2, …, Bn. Игра определена, если указано правило, сопоставляющее каждой паре чистых стратегий

Ai и Bj число aij – выигрыш игрока А за счет игрока B. При aij<0 игрок А платит игроку В сумму |aij|. Если известны значения aij выигрыша для каждой пары (Ai, Bj) стратегий, то можно составить матрицу игры – платежную матрицу.

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

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

Стратегию игрока А называют оптимальной, если при ее применении выигрыш игрока А не уменьшается, какими бы стратегиями не пользовался игрок В.

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

С учетом этого игрок А анализирует матрицу выигрышей: для каждой чистой стратегии Аi он

определяет минимальное значение _i  min a_ij          (i 1,m). Затем по минимальным выигрышам α_i он

j

отыскивает такую чистую стратегию Аi0, при которой этот минимальный выигрыш будет максимальным, т.е. находит  max_i  max mina_ij .

i                             i                       j

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

Игрок В старается максимально уменьшить проигрыш. Для каждой чистой стратегии Вj он

отыскивает _j  maxa_ij               ( j 1,n). Затем по βj находит свою стратегию Bj0, при которой его проигрыш

i

будет минимальным, т.е.  min_j  min maxa_ij .

j                             j                       i

Число β называется верхней чистой ценой игры (минимаксом). Оно показывает, какой максимальный проигрыш при использовании своих чистых стратегий может быть у игрока В. Соответствующая чистая стратегия Bj0 игрока B минимаксной.

Таким образом, используя чистые стратегии игрок А обеспечивает выигрыш не меньше α, а игрок B в результате применения своих чистых стратегий не позволит игроку выиграть больше, чем β. Принцип осторожности, диктующий игрокам выбор максиминной и минимаксной стратегий, называют принципом минимакса.

0  Пример. Найти максиминную и минимаксную стратегии в игре с матрицей 1 3  Решение.								4 0 1	1 2 2	3   2  1
		B1	B2	B3	В4	αi
	A1	0	4	-1	3	-1
	A2	1	0	2	2	0
	A3	3	1	-2	-1	-2
	βj	3	4	2	3

 max mina_ij  max{1;0;2} 0.Максиминной чистой стратегией является А₂. i      j

 min maxa_ij  min{3,4,2,3} 2.Минимаксной для игрока B является стратегия В₃. j      i

Теорема 1. В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т.е. α ≤ β.

i  min aij  aij

          Доказательство: По определению:                                 ^j_i  min a_ij  a_ij  max a_ij _j , значит αi ≤ aij

                                                                                                       j  max aij  aijj                                                              i

i

≤ βj или αi ≤ βj.

Это неравенство справедливо при любых комбинациях i и j. Будет оно справедливо для тех i и j, для которых max_i  и min_j , и при этих i и j получим α ≤ β. i  j

Если в матричной игре нижняя и верхняя чистые цены игры совпадают, т.е. α = β, то это игра имеет седловую точку в чистых стратегиях и чистую цену игры .

Обозначим через i* и j* номера чистых стратегий, при которых имеет место равенство α = β. Пару чистых стратегий ^A_i* ,^B_j*  игроков А и В, при которых достигается равенство α = β, называют седловой точкой матричной игры, а элемент ai*j* матрицы, стоящий на пересечении i* строки и j* столбца, – седловым элементом платежной матрицы.

Седловой элемент ^a_i* j* является наименьшим в i* строке и наибольшим в j* столбце, т.е.

^a_ij* ^a_i* j* ^a_i* j  . Поэтому, если игрок В отклонится от своей минимальной стратегии, то его проигрыш может увеличиться. Аналогично, отклонение игрока А от своей максимальной стратегии ведет к уменьшению его выигрыша. Таким образом, минимальные стратегии в игре с седловой точкой обладают свойством устойчивости, создают ситуацию равновесия. Следовательно, если в матрице игры существует седловой элемент, то наилучшими для игроков являются их минимальные стратегии. Назовем чистые стратегии ^A_i* и ^B_j* , образующие седловой элемент, оптимальными чистыми стратегиями соответственно игроков А и В. Набор ^A_i*,^B_j*,^v назовем решением игры.

Пример. Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определен. Предполагают, что его величина характеризуется тремя возможными состояниями (I, II, III). С учетом этих состояний анализируется три возможных варианта выпуска данной модели (А1, А2, А3). Каждый из этих вариантов требует своих затрат и обеспечивает различный эффект. Прибыль (тыс. руб.), которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей

	I	II	III
A1	22	22	22
A2	21	23	23
A3	20	21	24

Найти объем выпуска модели одежды обеспечивающий среднюю величину прибыли при любом состоянии спроса.

Решение. Проверим, имеет ли исходная матрица седловую точку.  max a_i  max{22,21,20} 22

i

 22.

 min_j  min{22,23,24} 22

j

Число 22 – цена игры. Игра имеет седловую точку, соответствующую варианту А1 выпуска модели одежды. Объем выпуска модели, соответствующий данному варианту, обеспечивает прибыль в 22 тыс. руб. при любом состоянии спроса.

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

Если в матрице (aij)m_×n игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующие строкам (столбцам) стратегии называются дублирующими.

Если в матрице (aij)m_×n игры все элементы некоторой строки, определяющей i-ю стратегию Аi игрока А, не больше (меньше или равны) соответствующих элементов другой строки, то i-я стратегия Аi называется заведомо невыгодной.

Если в матрице (aij)m_×n игры все элементы некоторого столбца, определяющего j-ю стратегию Вj игрока В, не меньше (больше или равны) соответствующих элементов другого столбца, то j-я стратегия Вj называется заведомо невыгодной.

Рассмотрим платежную матрицу игры:

	В1	B2	B3	В4	В5	αi
A1	8	6	4	5	1	1
A2	5	4	3	2	3	2
A3	6	7	6	3	5	3
A4	3	3	2	1	2	1
βj	8	7	6	5	5

        max{1;2;3;1} 3;         min{8,7,6,5,5} 5.

α = 3 ≠ β = 5. Платежная матрица игры не имеет седловой точки.

Сравнивая почленно элементы второй и третьей строк, видим, что все элементы второй строки меньше соответствующих элементов третьей строки. Следовательно, вторая стратегия для игрока А заведомо невыгодна и ее можно исключить. Аналогично, сравнивая А3 и А4, исключаем А4. Получаем матрицу игры:

	B1	B2	B3	В4	В5
A1	8	6	4	5	1
A3	6	7	6	3	5

Замечаем, что 1, 2, 3 стратегии игрока В заведомо невыгодны по сравнению с 5-й стратегией, поскольку игрок В стремится уменьшить выигрыш игрока А. Исключая эти стратегии, получаем матрицу 2×2, в которой нет дублирующих и заведомо невыгодных стратегий.

	В4	В5
A1	5	1
A3	3	5

Перенумеруем стратегии, запишем платежную матрицу:

	В1	В2	αi
A1	5	1	1
A2	3	5	3
βj	5	5

                     α = 3, β = 5.

Если для упрощенной матрицы α = β, то число α = β = v есть цена игры не только с упрощенной, но и со сходной матрицей. Если α <β, то анализируется упрощенная матрица, а затем осуществляется возвращение к исходной матрице.

Вопросы для самоконтроля:

1.      Перечислите основные элементы теории игр?

2.      Какая разница между некооперативными играми в сравнении с кооперативными?

3.      В чем суть принципа минимакса?

4.      Что такое седловая точка?

5.      Что такое чистая стратегия?

Тема 9. Решение матричных игр в смешанных стратегиях.

Вопросы, которые выносятся на самостоятельное изучение:

1.      Смешанные стратегии.

2.      Алгоритм решения смешанных стратегий.

3.      Игры 2 x 2.

4.      Алгоритм решения игр 2 x 2.

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

План изучения:

1.     Изучите тему.

2.     Составьте краткий конспект.

3.     Записать алгоритм решения: а) смешанных игр; б) игр 2 x 2. Теория:

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

	В1	В2	αi
A1	2	9	2
A2	6	3	3
βj	6	9

Пример: α = 3, β = 6. Игрок А может выиграть не менее 3 единиц, а игрок В может ограничить свой проигрыш (выигрыш игрока А) 6 единицами. Область между числами 3 и 6 является как бы нейтральной, и каждый игрок может

 попытаться улучшить свой результат за счет этой области. А2 и В1 – минимаксные стратегии игроков. Если игрок В заметит, что игрок А

предпочитает стратегию А2, то он может использовать стратегию В2 и уменьшить выигрыш игрока А до 3. Но если игрок А раскроет замысел игрока В и применит стратегию А1, то он увеличит свой выигрыш до 9. В свою очередь, узнав об этом, игрок В выберет стратегию В1 и понизит выигрыш игрока А до 2. Таким образом, в очередной партии игрокам надо так выбирать стратегии, чтобы противник о них не догадался, т.е. использовать механизм случайного выбора.  Bj Ai  B1 B2 ……… Bn pi Обозначим через Пусть имеется игра p1m, ×pn2, …, . pm  вероятности, с которыми

A1             a11       a12 ………        a1n      p1           игрок А использует чистые стратегии A1, A2, …, Am. Ясно, что

A2         a21      a22 ………        a2n      p2                             m

           …                   ………           …              p_i  0,i 1,m,  p_i 1.                                                (*)

Am           am1 am2 ………        amn      pm                              i1                                                                r

q_j q₁ q₂ ……… q_n Упорядоченное множество p p₁; p₂;...; p_m  (m-мерный вектор), элементы которого удовлетворяют условиям (*), называют смешанной стратегией игрока А. Т.е. смешанной стратегией игрока А является полный набор вероятностей применения его чистых стратегий. Механизм случайного выбора чистых стратегий, которым пользуется игрок А, обеспечивает ему множество смешанных стратегий. Любая чистая стратегия Аi есть частный случай смешанной

r

стратегии p 0;0;...;1;0;...;0, i-ая компонента которой равна 1, а остальные равны 0.

Аналогично упорядоченное множество qrq₁;q₂;...;q_n , элементы которого удовлетворяют

                                                                 n

соотношениям q _j  0, j 1,n^, q _j 1, является смешанной стратегией игрока В.

j1

                                                                                                                                                     r      r

Пусть игроки А и В применяют смешанные стратегии p и q . Это означает, что игрок А использует стратегию Аi с вероятностью pi, а игрок В – стратегию Вj с вероятностью qj. Вероятность выбора комбинации стратегий (Аi,Вj) равна P(Аi;Вj) = piqj, при этом будет получен выигрыш aij. При использовании смешанных стратегий игра носит случайный характер, случайной становится и величина выигрыша игрока А (проигрыша игрока В). Средняя величина выигрыша (математическое

                                                                                                                                   r     r

ожидание) является функцией от смешанных стратегий  p и q и определяется:

                                                                        r r                                                 m      n

f p;q a11p1q1 a12p1q2 ...amn pmqn aij piq j .

i1 j1

r r

Функция f p;q называется платежной функцией игры с матрицей (aij)m_×n.

                                                                                                                                                                                                                             r      r

Для решения игры с точки зрения игрока А необходимо найти такие смешанные стратегии p и q ,

r r

при которых ему обеспечивался бы средний выигрыш, равный min_r max_r          f p;q. Эту величину назовем q       p

r r

верхней ценой игры  min_r max_r f p;q.

                                                             q            p

r r

         Аналогичной должна быть ситуация для игрока В: нижняя цена игры  max_r min_r f p;q.

p            q

                                                                                                                             r         r

Оптимальным назовем смешанные стратегии p* и q* игроков А и В, удовлетворяющие

r r      r r      r r      r r      ^{m                     n} равенству: minr maxr                f p;q maxr minr    f p;q f p*;q*;v  f p*;q*a_ij p_i *q _j * – цена игры.

q            p                p                      q

i1 j1

Отметим свойства оптимальных смешанных стратегий.

1)    Основная теорема теории игр: любая конечная матричная игра с нулевой суммой имеет, по крайней мере, одно решение, возможно, в смешанных стратегиях.

Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры v. α ≤ v ≤ β.

                                                                                                                       r                                 r

2)    Для того, чтобы смешанные стратегии p*p₁*; p₂*;...; p_m * и q*q₁*;q₂*;...;q_n * были оптимальными для игроков А и B в игре с матрицей (aij)m_×n и ценой v необходимо и достаточно

                                                          m                                                                  n                                                     

выполнение неравенств:a_ij p_i* ^v j 1,ⁿ^;a_ijq_i* ^v i 1,^m.

                                                         i1                                                                        j1

r        r r      r

3) Пусть p* и q* – оптимальные смешанные стратегии игроков А и B в игре I с матрицей (aij)m_×n

и ценой v. Тогда p* и q* будут оптимальными в игре I' с матрицей (baij + c)m_×n, где b>0, и ценой v'=bv+c.

Благодаря этому утверждению любую платежную матрицу можно преобразовать в платежную матрицу, все элементы которой положительны, поэтому цена игры v' также положительна.

Игра 2×2. В приведенных формулах для α и β функции min и max вычисляются на бесконечных множествах смешанных стратегий, поэтому значения α и β нельзя найти путем перебора вариантов. Воспользуемся теоремой об активных стратегиях.

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

r

оптимальной смешанной стратегии p*0;0,2;0,8;0 активными являются стратегии А₂ и А₃.

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

Найдем решение в случае игры 2×2. У игроков А и В по две стратегии, игра не содержит седловую

r

точку. Найдем оптимальную смешанную стратегию p*p₁*; p₂ *.

Решение. Матрица игры имеет вид. Поскольку игра не имеет решения в чистых стратегиях, в

r

оптимальной стратегии q*q₁*;q₂ * игрока В числа q₁* 0 и q₂* 0 , т.е. обе стратегии В1 и В2 активные. Тогда по теореме об активных стратегиях, если игрок А

r

придерживается своей оптимальной стратегии p*p₁*; p₂ *, то игрок В может, не влияя на значение выигрыша, применять какую-либо из своих чистых активных

стратегий В1 или В2. Игрок А получит средний выигрыш равный цене игры. Имеем два уравнения: a₁₁p₁*a₂₁p₂*v  (при стратегии В1); a₁₂ p₁ *a₂₂ p₂*v  (при стратегии В2).

Учитывая, что p₁*p₂*1 , будем иметь систему трех линейных уравнений с тремя

r неизвестными. Решив ее, найдем оптимальную смешанную стратегию p*p₁*; p₂ * игрока А и цену игры v. Рассуждая аналогично, для определения оптимальной стратегии игрока В получим систему a11q1 *a12q2* v;  уравнений: a₂₁q₁ *a₂₂q₂* v; ^q₁ *q₂* 1.

 Пример. Имеются две конкурирующие фирмы А и В, выпускающие однотипные изделия, соответственно видов I и II, которые могут быть окрашены в один из двух цветов: красный (кр.) или синий (син.). Изучение спроса покупателей показало, что если выпущены изделия I кр. и II кр., то 40% покупателей получают I кр. и 60% – II кр. Если выпущены I кр. и II син., то 90% покупателей приобретают I кр. Если изготовлены I син. и II кр. будет продано 70% I син. Если сделаны I син. и II син., то 20% покупателей получат I син. Найти оптимальные стратегии и цену матричной игры. A  II II Решение. Составим платежную матрицу игры (выигрыш аij фирмы А).

      B                                                          αi

                        кр.         син.                               max{20,60}20

I кр.               -20      80                               -20  – игра не имеет седловой точки.

I син.   40        -60       -60  min{40,80} 40 βj      40        80         Найдем оптимальное решение матричной игры в смешанных стратегиях.

r

Пусть фирма А придерживается своей оптимальной стратегии p*p₁*; p₂ * . По теореме об активных стратегиях, при применении фирмой В чистой стратегии В1 или В2 фирма А получит средний выигрыш, равный цене игры, т.е.

 20p₁ *40p₂* v;

                                     p₁* 1 p₂*;                                                    p₂* 1 2;       p₁* 12;

80p₁ *60p₂* v;      ,         _ _p1 _*p2_{* 1.}        201 p₂ * 40p₂*  801 p₂ * 60p₂*, p₁* 11 2, p₂* 12,

_

v 80 1 60 1 10 – цена игры. pr*^¹;^1 , v = 10.

                 2          2                                        2 2

r

Составим систему уравнений для определения q*q₁*;q₂ * оптимальной стратегии игрока В.

 20q₁ *80q₂* 10;

^40q₁ *60q₂* 10;         Решая систему, найдем qr*^ 7 ; 3 ^ . При таких оптимальных стратегиях

q1 *q2* 1.                                                                     10 10

 изделия фирмы А будут покупать 55%, фирмы В – 45% покупателей (55%+45%=100%).

Вопросы для самоконтроля:

1.      Что такое смешанная стратегия?

2.      В чем свойства оптимальных смешанных стратегий?

3.      В чем принцип смешанной стратегии 2 х 2?