8519

(1,4) коэффициент затрат после сложения будет равен 3+1=4, поэтому, чтобы он стал равен нулю, четвертому столбцу надо придать потенциал, равный –4.

Действуя далее аналогично, последовательно получим: потенциал 1 для первой строки, –1 для третьего столбца, –3 для третьей строки и 0 для второго столбца.

Прибавляя полученные потенциалы к коэффициентам затрат (и по строкам, и

по столбцам), получаем следующую матрицу оценок:

Так как среди оценок клеток есть отрицательные, полученное распределе-

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

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

Для клетки (4,4) цикл пересчета выглядит так:

Найдем максимальное значение поставки, которое можно передвинуть по циклу как наименьшее значение поставки в «отрицательных» клетках. В нашем случае такая поставка равна 30. Заметим, что передвинув по циклу 30 единиц,

получим нулевые поставки сразу в двух клетках – (2,4) и (4,1). Если считать их обе пустыми, число базисных клеток уменьшится, чего допустить нельзя. По-

81

В матрице нет отрицательных оценок, следовательно, полученное распре-

деление оптимально. Посчитаем суммарные затраты на перевозку этого рас-

пределения поставок.

Fmin 4 50 3 50 5 20 4 20 3 30 620 .

83

4.2. Элементы теории матричных игр

Задача 1. Определить нижнюю и верхнюю цену игры, заданной платежной

Решение. Найдем по каждой строчке платежной матрицы минимальное число αi min(ai1,ai2 ,ai3 ) – это гарантированный выигрыш игрока А при выбо-

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

им стратегии B j . Найдем минимальное из этих чисел β min(β1,β2 ,β3 ) – это верхняя цена игры. Занесем полученные данные в таблицу.

седловую точку. Для игрока А оптимальная стратегия – A3 , для игрока В опти-

мальная стратегия – B2 .

Ответ: α β 0 , игра имеет седловую точку, оптимальные стратегии ( A3 , B2 ) .

Прибавляя ко всем элементам матрицы (Pij ) число k= 5, приходим к мат-

Воспользовавшись симплекс-методом, находим решение:

В рассматриваемой игре Pij Т Pij и S*A S*В . Нетрудно найти оптималь-

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

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

Завершая рассмотрение игр двух участников с нулевой суммой без седло-

вых точек, заметим, что при использовании смешанных стратегий перед каж-

дой партией игры каждым игроком запускается некий механизм (бросание мо-

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

вающий выбор каждой чистой стратегии с заданной вероятностью. Как мы уже

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

85

гибкой тактики, при использовании которой противник не знает заранее, с ка-

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

При этом ожидаемые теоретические результаты игры, при неограниченном воз-

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

Задача 3. Теории игр (аналитическое решение и имитационная мо-

дель)

1)Решить игру аналитически.

2)Провести моделирование результатов игры с помощью таблицы рав-

номерно распределенных случайных чисел, разыграв 30 партий; определить от-

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

рыш игроку А, равный цене игры, при любом поведении игрока В:

для стратегии В1: 10 p1 8 p2 ;

для стратегии В2: 7 p1 11p2 .

86

С учетом того, что сумма вероятностей смешанной стратегии равна 1, по-

лучаем систему уравнений:

Итак:, = 9.

Аналогично получаем систему для нахождения смешанной стратегии игрока В.

10q1 7q2 ,8q1 11q2 ,

q1 q2 1.

впервое уравнение (Вместо подставим найденное значение для игрока А

= 9):

Итак:.

Ответ: , .

87

Проведем моделирование результатов решения с помощью таблицы рав-

номерно распределенных случайных чисел. Для 30 партий хватит 60 чисел, на основе которых будут выбираться стратегии игроками. Используемые случай-

ные числа сгенерированы в MS Excel функцией =СЛЧИС(). В приложении дос-

таточно много чисел, но использовать для моделирования можно любые 60,

выбранные произвольно с любого места таблицы. Выберем 60 чисел:

Будем выбирать стратегии игроков, используя геометрическое определе-

ние вероятности. Так как все случайные числа из отрезка [0; 1], то чтобы стра-

тегия А1 появлялась примерно в половине случаев, будем ее выбирать если случайное число меньше 0,5; в остальных случаях выбирается стратегия А2.

Аналогично для игрока В. Стратегию В1 будем выбирать, если соответствую-

щее случайное число меньше 2/3 0,67, в противном случае выбираем стратегию В2.

Заполним расчетную таблицу (Средний выигрыш игрока А считаем, как отношение накопленного выигрыша к количеству сыгранных партий):

88

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

Из 30 партий игрок А 18 раз применял стратегию А1, 12 раз – стратегию А2. Игрок В 21 раз применял стратегию В1, 9 раз – стратегию В2. Частоты ис-

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

p=(18/30;12/30)=(0,6;0,4), q=(21/30;9/30)=(0,7;0,3). Сравнивая с теоретически-

ми оптимальными стратегиями =(0,5; 0,5) и =(0,67; 0,33) можно сделать вывод, что результаты моделирования достаточно близко соответствуют теоре-

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

89

4.3. Системы массового обслуживания

Задача 1.

Пункт по ремонту радиотехники работает в режиме отказа с одним мастером. Интенсивность потока заявок 1, производительность мастера 1.3.

Определить предельные значения относительной пропускной способности Q,

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

Исчисляем показатели обслуживания для одноканальной СМО

1. Интенсивность нагрузки.

Интенсивность нагрузки ρ=0.769 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.

2.Время обслуживания.

3.Вероятность, что канал свободен (доля времени простоя канала).

Следовательно, 57% в течение часа канал будет не занят, время простоя

равно tпр = 33.9 мин.

4.Доля заявок, получивших отказ (вероятность отказа). pотк = 1 - p0 = 1 - 0.565 = 0.43

Значит, 43% из числа поступивших заявок не принимаются к обслуживанию.

5.Относительная пропускная способность.

Доля обслуживаемых заявок, поступающих в единицу времени:

90