Сторона А организует три простейших потока заявок с интенсивностями λ1, λ2, λ3. Сторона В организует для обслуживания каждого потока отдельную СМО с отказами, располагая всего четырьмя каналами. Производительность каждого канала μ=0,3.
Чистые стратегии сторон:
Сторона А λ1 λ2 λ3 Сторона В n1 n2 n3
А1 0,3 0,4 0,3 В1 2 1 1
А2 0,4 0,4 0,2 В2 3 1 0
А3 0,5 0,3 0,2 В3 1 2 1
Выигрыш стороны А и проигрыш стороны В-суммарную интенсивность потоков необслуженных заявок.
Найти оптимальные стратегии сторон и чистую цену игры.
Ответ
Оптимальная смешанная стратегия игрока А: P = (0.529; 0; 0.471)Оптимальная смешанная стратегия игрока В: Q = (0.471; 0.529; 0)
Цена игры: γ =0.285
Решение
СМО описывается параметрами,которые характеризуют эффективность ра-боты системы:
n1, n2, n3-число отказов в СМО;
λ-интенсивность поступления в СМО заявок;
μ=0,3-интенсивность обслуживания заявок (Производительность каждого канала):
ρ= λ/ μ -коэффициент загрузхи СМО;
Вероятность отказа СМО есть предельная вероятность того, что все я каналов системы будут заняты, т.е.
Ротк.= ρn/n!* р0
р0=(1+ ρ+ ρn/n!)-1
ρ= λ/μ
1,00 1,33 1,00
1,33 1,33 0,67
1,67 1,00 0,67
ρ^n
1,00 1,33 1,00
2,37 1,33 1,00
1,67 1,00 0,67
р0=(1+ρ+ρn/n!)-1
0,40 0,27 0,33
0,37 0,27 0,38
0,23 0,40 0,43
Матрица игры сторон А и В .
Qотк.= ρn/n!*р0
0,20 0,36 0,33
0,14 0,36 0,38
0,38 0,20 0,29
Чистой стратегией игрока А является выбор одной из n строк матрицы вы- игрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.Считаем, что игрок I выбирает свою стратегию так, чтобы получить макси -мальный свой выигрыш, а игрок В выбирает свою стратегию так, чтобы ми-ними зировать выигрыш игрока А.
Игроки
B1 B2 B3 a = min(Ai)
A1 0.2 0.36 0.33 0.2
A2 0.14 0.36 0.38 0.14
A3 0.38 0.2 0.29 0.2
b = max(Bi) 0.38 0.36 0.38
Находим гарантированный выигрыш, определяемый нижней ценой игры
a = max(ai) = 0.2,
которая указывает на максимальную чистую стратегию A1.Верхняя цена игры
b = min(bj) = 0.36.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах
0.2 ≤ y ≤ 0.36.
Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой:
В матрице отсутствуют доминирующие строки.В матрице отсутствуют доминирующие столбцы.
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока А будет случайной величиной
. В этом случае игрок А должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.Аналогично, игрок В должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока А.Чтобы представить числа целыми, умножим элементы матрицы на 10 и вычтем 0.4. Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).
1.6 3.2 2.9
1 3.2 3.4
3.4 1.6 2.5
3. Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программиро -вания можно записать так:найти минимум функции F(x) при ограниче ниях (для игрока В):
1.6x1+x2+3.4x3 ≥ 13.2x1+3.2x2+1.6x3 ≥ 12.9x1+3.4x2+2.5x3 ≥ 1F(x) = x1+x2+x3 → min
Найти максимум функции Z(y) при ограничениях (для игрока I):
1.6y1+3.2y2+2.9y3 ≤ 1y1+3.2y2+3.4y3 ≤ 13.4y1+1.6y2+2.5y3 ≤ 1Z(y) = y1+y2+y3 → max
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.Определим максимальное значение целевой функции:
Z(Y) = y1+y2+y3 при следующих условиях-ограничений.
1.6y1+3.2y2+2.9y3≤1y1+3.2y2+3.4y3≤13.4y1+1.6y2+2.5y3≤1
Для построения первого опорного плана систему неравенств приведем к сис- теме уравнений путем введения дополнительных переменных:
1.6y1+3.2y2+2.9y3+y4 = 1y1+3.2y2+3.4y3+y5 = 13.4y1+1.6y2+2.5y3+y6 = 1Решим систему уравнений относительно базисных переменных: y4, y5, y6Полагая, что свободные переменные равны 0, получим первый опорный план:
Y0 = (0,0,0,1,1,1)
Базис
B y1 y2 y3 y4 y5 y6
y4 1 1.6 3.2 2.9 1 0 0
y5 1 1 3.2 3.4 0 1 0
y6 1 3.4 1.6 2.5 0 0 1
Z(Y0) 0 -1 -1 -1 0 0 0
Переходим к основному алгоритму симплекс-метода.Итерация №0.Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.В качестве ведущего выберем столбец, соответствующий переменной y3, так как это наибольший коэффициент по модулю.Вычислим значения Di по строкам как частное от деления: bi / ai3и из них выберем наименьшее:min (1 : 2.9 , 1 : 3.4 , 1 : 2.5 ) = 0.294Следовательно, 2-ая строка является ведущей.Разрешающий элемент равен (3.4) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B y1 y2 y3 y4 y5 y6 min
y4 1 1.6 3.2 2.9 1 0 0 0.34
y5 1 1 3.2 3.4 0 1 0 0.29
y6 1 3.4 1.6 2.5 0 0 1 0.4
Z(Y1) 0 -1 -1 -1 0 0 0
Формируем следующую часть симплексной таблицы. Вместо переменной y5 в план 1 войдет переменная y3.Получаем новую симплекс-таблицу:
Базис
B y1 y2 y3 y4 y5 y6
y4 0.15 0.75 0.47 0 1 -0.85 0
y3 0.29 0.29 0.94 1 0 0.29 0
y6 0.26 2.66 -0.75 0 0 -0.74 1
Z(Y1) 0.29 -0.71 -0.059 0 0 0.29 0
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.В качестве ведущего выберем столбец, соответствующий переменной y1, так как это наибольший коэффициент по модулю.Вычислим значения Di по строкам как частное от деления: bi / ai1и из них выберем наименьшее:
min (0.147 : 0.747 , 0.294 : 0.294 , 0.265 : 2.665 ) = 0.0993
Следовательно, 3-ая строка является ведущей.Разрешающий элемент равен (2.665) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B y1 y2 y3 y4 y5 y6 min
y4 0.15 0.75 0.47 0 1 -0.85 0 0.2
y3 0.29 0.29 0.94 1 0 0.29 0 1
y6 0.26 2.66 -0.75 0 0 -0.74 1 0.099
Z(Y2) 0.29 -0.71 -0.059 0 0 0.29 0
Формируем следующую часть симплексной таблицы
Задать вопрос
на новый заказ в Автор24.
