Некоторые главы линейного программирования: теория игр, теория массового обслуживания (стр. 1 )

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

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

Кафедра высшей математики

,

НЕКОТОРЫЕ ГЛАВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ: ТЕОРИЯ ИГР, ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ

Учебно-методическое пособие

Кострома

2007

УДК 51

, Филатова главы линейного программирования: теория игр, теория массового обслуживания : учебно-методическое пособие / , . – Кострома : КГТУ, 2007. – 30 с.

Пособие соответствует требованиям Государственного образовательного стандарта и учебному плану по дисциплине «математика» и рекомендуется для студентов специальностей 080109.

Рецензенты: кафедра экономики и управления КГТУ;

к. э.н., доцент

Рекомендовано к изданию редакционно-издательским советом КГТУ

© Костромской государственный технологический университет, 2007

оГЛАВЛЕНИЕ

Предисловие……………………………………………………………..

1. Элементы теории игр………………………………………………….

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

1.2. Матричные игры. Решение матричных игр в чистых стратегиях………………………………………………………..

1.3. Упрощение игр…………………………………………………...

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

1.5. Решение задач в смешанных стратегиях. Игра 2×2……………

1.6. Критерии принятия решения в играх с «природой».

1.7. Упражнения………………………………………………………

2. Элементы теории массового обслуживания…………………………

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

2.2. Марковский случайный процесс в системах массового обслуживания……………………………………………………

2.3. Уравнения Колмогорова…………………………………………

2.4. Одноканальная система массового обслуживания с отказами..

2.5. Одноканальная система массового обслуживания с очередью.

2.6. Упражнения………………………………………………………

3. Ответы к упражнениям……………………………………………….

4. Библиографический список…………………………………………..

ПРЕДИСЛОВИЕ

Настоящее учебно-методическое пособие предназначено для изучения элементов теории игр и основ теории массового обслуживания.

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

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

1. Элементы теории игр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Игрок А располагает m чистыми стратегиями А1, А2, … , Аm. Игрок В – n чистыми стратегиями B1, B2, … , Bn. Игра определена, если указано правило, сопоставляющее каждой паре чистых стратегий Ai и Bj число aij – выигрыш игрока А за счет игрока B. При aij<0 игрок А платит игроку В сумму |aij|. Если известны значения aij выигрыша для каждой пары (Ai,Bj) стратегий, то можно составить матрицу игры – платежную матрицу.

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

Ai Bj	B1	B2	B3	………………	Bn
A1	a11	a12	a13	………………	a1n
A2	a21	a22	a23	………………	a2n
…	…	…	…	………………
Am	am1	am2	am3	………………	amn

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

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

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

С учетом этого игрок А анализирует матрицу выигрышей: для каждой чистой стратегии Аi он определяет минимальное значение . Затем по минимальным выигрышам αi он отыскивает такую чистую стратегию Аi0, при которой этот минимальный выигрыш будет максимальным, т. е. находит

.

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

Игрок В старается максимально уменьшить проигрыш. Для каждой чистой стратегии Вj он отыскивает . Затем по βj находит свою стратегию Bj0, при которой его проигрыш будет минимальным, т. е.

.

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

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

Пример. Найти максиминную и минимаксную стратегии в игре с матрицей

Решение.

	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

Максиминной чистой стратегией является А2.

Минимаксной для игрока B является стратегия В3.

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

Доказательство:

По определению

,

значит αi ≤ aij ≤ βj или αi ≤ βj.

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

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

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

Седловой элемент является наименьшим в i* строке и наибольшим в j* столбце, т. е. . Поэтому, если игрок В отклонится от своей минимальной стратегии, то его проигрыш может увеличиться. Аналогично, отклонение игрока А от своей максимальной стратегии ведет к уменьшению его выигрыша. Таким образом, минимальные стратегии в игре с седловой точкой обладают свойством устойчивости, создают ситуацию равновесия. Следовательно, если в матрице игры существует седловой элемент, то наилучшими для игроков являются их минимальные стратегии. Назовем чистые стратегии и , образующие седловой элемент, оптимальными чистыми стратегиями соответственно игроков А и В. Набор назовем решением игры.

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

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

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

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

.

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

1.3. Упрощение игр

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

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

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

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

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

B1 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

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