МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧЕРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра Прикладной Информатики
Индивидуальное задание
по курсу «ЭММ»
Выполнила студентка гр. М-53
Полупанова Ю.
Проверила Вовк С. П.
Таганрог 2006 г.
1. Спорт-клуб А располагает 3 вариантами состава команды Аi, i=1..3, спорт-клуб В - 4 вариантами состава команды Вj, j=1..4. Вероятность выигрыша состава Аj у состава Вj равна аij. Определить оптимальное (обеспечивающее максимальную вероятность выигрыша) сочетание вариантов состава спортклуба А.
|
В1 |
В2 |
В3 |
В4 |
А1 |
0,4 |
0,7 |
0,9 |
0,2 |
А2 |
0,6 |
0,3 |
0,1 |
0,8 |
А3 |
0,3 |
0,1 |
0,8 |
0,5 |
Решение:
Посмотрим имеет ли задача решение в чистых стратегиях.
|
В1 |
В2 |
В3 |
В4 |
min aij j |
А1 |
0,4 |
0,7 |
0,9 |
0,2 |
0,2 |
А2 |
0,6 |
0,3 |
0,1 |
0,8 |
0,1 |
А3 |
0,3 |
0,1 |
0,8 |
0,5 |
0,1 |
max aij |
0,6 |
0,7 |
0,9 |
0,8 |
|
i
u = max min aij = max {0,2; 0,1; 0,1} = 0,3 => α0 = α1
i j
v = min max aij = min {0,6; 0,7; 0,9; 0,8} = 0,6 => β0 = β1
i j
Т.к. u ≠ v, то игра решения в чистых стратегиях не имеет, следовательно, решение игры необходимо искать в смешанных стратегиях.
Решим задачу симплекс-методом. Составим двойственные задачи для 1-го и для 2-го игроков.
t1 + t2 + t3 → min,
0,4t1 + 0, 6t2 + 0,3t3 ≥ 1,
0,7t1 + 0,3t2 + 0,1t3 ≥ 1, – двойственная задача для 1-го игрока
0,9t1 + 0,1t2 + 0,8t3 ≥ 1,
0,2t1 + 0,8t2 + 0,5t3 ≥ 1,
ti ≥ 0, i = 1..3.
w1 + w2 + w3 + w4 → max,
0,4w1 + 0,7w2 + 0,9w3 + 0,2w4 ≤ 1,
0,6w1 + 0,3w2 + 0,1w3 + 0,8w4 ≤ 1, – прямая задача для 2-го игрока
0,3w1 + 0,1w2 + 0,8w3 + 0,5w4 ≤ 1,
wj ≥ 0, j = 1..4.
Легче решать задачу максимизации, т.к. сразу получаем начальный базис.
Приводим задачу к канонической форме
w1 + w2 + w3 + w4 → max,
0,4w1 + 0,7w2 + 0,9w3 + 0,2w4 + w5 = 1,
0,6w1 + 0,3w2 + 0,1w3 + 0,8w4 + w6 = 1,
0,3w1 + 0,1w2 + 0,8w3 + 0,5w4 + w7 = 1,
wj ≥ 0, j = 1..7.
Строим симплекс-таблицу
Базис |
Св. член |
w1 |
w2 |
w3 |
w4 |
w5 |
w6 |
w7 |
|
w5 |
1 |
0,4 |
0,7 |
0,9 |
0,2 |
1 |
0 |
0 |
2,5 |
w6 |
1 |
0,6 |
0,3 |
0,1 |
0,8 |
0 |
1 |
0 |
1,666667 |
w7 |
1 |
0,3 |
0,1 |
0,8 |
0,5 |
0 |
0 |
1 |
3,333333 |
L |
0 |
-1 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Базис |
Св. член |
w1 |
w2 |
w3 |
w4 |
w5 |
w6 |
w7 |
|
w5 |
0,333333 |
0 |
0,5 |
0,833333 |
-0,33333 |
1 |
-0,66667 |
0 |
0,4 |
w1 |
1,666667 |
1 |
0,5 |
0,166667 |
1,333333 |
0 |
1,666667 |
0 |
10 |
w7 |
0,5 |
0 |
-0,05 |
0,75 |
0,1 |
0 |
-0,5 |
1 |
0,666667 |
L |
1,666667 |
0 |
-0,5 |
-0,83333 |
0,333333 |
0 |
1,666667 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Базис |
Св. член |
w1 |
w2 |
w3 |
w4 |
w5 |
w6 |
w7 |
|
w3 |
0,4 |
0 |
0,6 |
1 |
-0,4 |
1,2 |
-0,8 |
0 |
0,666667 |
w1 |
1,6 |
1 |
0,4 |
0 |
1,4 |
-0,2 |
1,8 |
0 |
4 |
w7 |
0,2 |
0 |
-0,5 |
0 |
0,4 |
-0,9 |
0,1 |
1 |
|
L |
2 |
0 |
-1,7E-16 |
0 |
1,11E-16 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Базис |
Св. член |
w1 |
w2 |
w3 |
w4 |
w5 |
w6 |
w7 |
|
w2 |
0,666667 |
0 |
1 |
1,666667 |
-0,66667 |
2 |
-1,33333 |
0 |
|
w1 |
1,333333 |
1 |
0 |
-0,66667 |
1,666667 |
-1 |
2,333333 |
0 |
|
w7 |
0,533333 |
0 |
0 |
0,833333 |
0,066667 |
0,1 |
-0,56667 |
1 |
|
L |
2 |
0 |
0 |
2,78E-16 |
0 |
1 |
1 |
0 |
|
Т.к. среди коэффициентов целевой строки нет отрицательных, то найденное ДБР является оптимальным.
Решением задачи линейного программирования для 1-го игрока будет являться T0 = (1; 1; 0), а для 2-го игрока – W0 = (1,33; 0,67; 0; 0).
Цена игры u = v = 1/L0 = 0,5. Отсюда находим пару уравновешенных стратегий А0 = uT0 = (0,5; 0,5; 0), В0 = vW0 = (0,67; 0,33; 0;0).
Ответ: u = v = 0,5; А* = (0,5; 0,5; 0).
Вывод: спорт-клуб А, чтобы обеспечить себе максимальное количество побед над спорт-клубом В должен использовать в 50% игр состав А1 и в 50% игр состав А2, состав А3 не входит в уравновешенную стратегию. В этом случае спорт-клуб А обеспечит себе вероятность выигрыша не меньше 50%.
2. Найти приближенное решение задачи п.1 методом итераций (выполнить 20 шагов итерационного процесса).
Решение:
n |
i |
В1 |
В2 |
В3 |
В4 |
j |
А1 |
А2 |
А3 |
v |
v |
v* |
1 |
А1 |
0,4 |
0,7 |
0,9 |
0,2 |
В4 |
0,2 |
0,8 |
0,5 |
0,2 |
0,8 |
0,5 |
2 |
A2 |
1 |
1 |
1 |
1 |
B1 |
0,6 |
1,4 |
0,8 |
0,5 |
0,7 |
0,6 |
3 |
A2 |
1,6 |
1,3 |
1,1 |
1,8 |
B3 |
1,5 |
1,5 |
1,6 |
0,366667 |
0,533333 |
0,45 |
4 |
A3 |
1,9 |
1,4 |
1,9 |
2,3 |
B2 |
2,2 |
1,8 |
1,7 |
0,35 |
0,55 |
0,45 |
5 |
A1 |
2,3 |
2,1 |
2,8 |
2,5 |
B2 |
2,9 |
2,1 |
1,8 |
0,42 |
0,58 |
0,5 |
6 |
A1 |
2,7 |
2,8 |
3,7 |
2,7 |
B1 |
3,3 |
2,7 |
2,1 |
0,45 |
0,55 |
0,5 |
7 |
A1 |
3,1 |
3,5 |
4,6 |
2,9 |
B4 |
3,5 |
3,5 |
2,6 |
0,414286 |
0,5 |
0,457143 |
8 |
A1 |
3,5 |
4,2 |
5,5 |
3,1 |
B4 |
3,7 |
4,3 |
3,1 |
0,3875 |
0,5375 |
0,4625 |
9 |
A2 |
4,1 |
4,5 |
5,6 |
3,9 |
B4 |
3,9 |
5,1 |
3,6 |
0,433333 |
0,566667 |
0,5 |
10 |
A2 |
4,7 |
4,8 |
5,7 |
4,7 |
B1 |
4,3 |
5,7 |
3,9 |
0,47 |
0,57 |
0,52 |
11 |
A2 |
5,3 |
5,1 |
5,8 |
5,5 |
B2 |
5 |
6 |
4 |
0,463636 |
0,545455 |
0,504545 |
12 |
A2 |
5,9 |
5,4 |
5,9 |
6,3 |
B2 |
5,7 |
6,3 |
4,1 |
0,45 |
0,525 |
0,4875 |
13 |
A2 |
6,5 |
5,7 |
6 |
7,1 |
B2 |
6,4 |
6,6 |
4,2 |
0,438462 |
0,507692 |
0,473077 |
14 |
A2 |
7,1 |
6 |
6,1 |
7,9 |
B2 |
7,1 |
6,9 |
4,3 |
0,428571 |
0,507143 |
0,467857 |
15 |
A1 |
7,5 |
6,7 |
7 |
8,1 |
B2 |
7,8 |
7,2 |
4,4 |
0,446667 |
0,52 |
0,483333 |
16 |
A1 |
7,9 |
7,4 |
7,9 |
8,3 |
B2 |
8,5 |
7,5 |
4,5 |
0,4625 |
0,53125 |
0,496875 |
17 |
A1 |
8,3 |
8,1 |
8,8 |
8,5 |
B2 |
9,2 |
7,8 |
4,6 |
0,476471 |
0,541176 |
0,508824 |
18 |
A1 |
8,7 |
8,8 |
9,7 |
8,7 |
B1 |
9,6 |
8,4 |
4,9 |
0,483333 |
0,533333 |
0,508333 |
19 |
A1 |
9,1 |
9,5 |
10,6 |
8,9 |
B4 |
9,8 |
9,2 |
5,4 |
0,468421 |
0,515789 |
0,492105 |
20 |
A1 |
9,5 |
10,2 |
11,5 |
9,1 |
B4 |
10 |
10 |
5,9 |
0,455 |
0,5 |
0,4775 |
Из таблицы следует, что при n = 20 цена игры v ≈ 0,48 при следующей частости использования стратегий:
PА1=0,55; PА2=0,4; PА3=0,05; PВ1=0,2; PВ2=0,45; PВ3=0,05; PВ4=0,3.
Ответ: u = v ≈ 0,48; А* = (0,55; 0,4; 0,05).
Вывод: Полученная уравновешенная стратегия отличается от уравновешенной стратегии, полученной в первой задаче (на 5% увеличены стратегии А1 и А3 и на 10% уменьшена стратегия А2), отсюда и следует, что максимальная вероятность выигрыша уменьшилась на 2%. Недостатком итерационного метода является его медленная сходимость, а также то, что он дает приближенный ответ.