5. Графически решить игру:
|
|
|
B1 |
B2 | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
|
|
A1 |
0 |
8 | |||||||
|
|
A2 |
10 |
7 | |||||||
|
|
A3 |
4 |
8 | |||||||
|
|
A4 |
8 |
4 | |||||||
|
|
|
|
|
| ||||||
|
|
|
|
| |||||||
|
|
|
|
| |||||||
|
|
|
|
| |||||||
|
|
|
|
| |||||||
|
|
|
|
| |||||||
|
|
B1 |
B2 |
α |
|
A1 |
0 |
8 |
0 |
|
A2 |
10 |
7 |
7 |
|
A3 |
4 |
8 |
4 |
|
A4 |
8 |
4 |
4 |
|
β |
10 |
8 |
7 8 |
игра решается в
смешанных стратегиях
|
|
B1 |
B2 |
|
A2 |
10 |
7 |
|
A3 |
4 |
8 |
Ответ: 
,
,
6. Решить матричную игру, сведя ее к задаче линейного программирования:
1. Проверяем, содержит ли данная матрица седловую точку.
|
|
B1 |
B2 |
B3 |
B4 |
B5 |
α |
|
A1 |
8 |
6 |
0 |
2 |
4 |
0 |
|
A2 |
7 |
5 |
3 |
10 |
1 |
1 |
|
A3 |
0 |
4 |
7 |
4 |
1 |
0 |
|
β |
8 |
6 |
7 |
10 |
4 |
1 4 |
=1,
а
=4.
,
т. е. матрица не содержит седловой точки,
поэтому решение игры представлено в
смешанных стратегиях
и
.
Составляем двойственную задачу:
Для определения
оптимальной стратегии игрока
Прямая задача:
.
Для определения
оптимальной стратегии игрока
Двойственная
задача:
Найдем оптимальный план двойственной задачи, а затем исходя из него оптимальный план прямой задачи.
Приведем двойственную задачу к каноническому виду и решим симплекс-методом, используя табличный способ:
|
Шаг 0 |
|
|
|
|
|
|
|
|
|
|
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
|
y6 |
1 |
8 |
6 |
0 |
2 |
4 |
1 |
0 |
0 |
|
y7 |
1 |
7 |
5 |
3 |
10 |
1 |
0 |
1 |
0 |
|
y8 |
1 |
0 |
4 |
7 |
4 |
1 |
0 |
0 |
1 |
|
z |
0 |
-1 |
-1 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 1 |
|
|
|
|
|
|
|
|
|
|
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
|
y1 |
1/8 |
1 |
3/4 |
0 |
1/4 |
1/2 |
1/8 |
0 |
0 |
|
y7 |
1/8 |
0 |
-1/4 |
3 |
33/4 |
-5/2 |
-7/8 |
1 |
0 |
|
y8 |
1 |
0 |
4 |
7 |
4 |
1 |
0 |
0 |
1 |
|
z |
1/8 |
0 |
-1/4 |
-1 |
-3/4 |
-1/2 |
1/8 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 2 |
|
|
|
|
|
|
|
|
|
|
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
|
y1 |
1/8 |
1 |
3/4 |
0 |
1/4 |
1/2 |
1/8 |
0 |
0 |
|
y3 |
1/24 |
0 |
-1/12 |
1 |
11/4 |
-5/6 |
-7/24 |
1/3 |
0 |
|
y8 |
17/24 |
0 |
55/12 |
0 |
-61/4 |
41/6 |
49/24 |
-7/3 |
1 |
|
z |
1/6 |
0 |
-1/3 |
0 |
2 |
-4/3 |
-1/6 |
1/3 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3 |
|
|
|
|
|
|
|
|
|
|
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
|
y1 |
3/41 |
1 |
17/41 |
0 |
56/41 |
0 |
-1/41 |
7/41 |
-3/41 |
|
y3 |
21/164 |
0 |
39/82 |
1 |
73/82 |
0 |
-7/164 |
2/41 |
5/41 |
|
y5 |
17/164 |
0 |
55/82 |
0 |
-183/82 |
1 |
49/164 |
-14/41 |
6/41 |
|
z |
25/82 |
0 |
23/41 |
0 |
-40/41 |
0 |
19/82 |
-5/41 |
8/41 |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 4 |
|
|
|
|
|
|
|
|
|
|
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
|
y4 |
3/56 |
41/56 |
17/56 |
0 |
1 |
0 |
-1/56 |
1/8 |
-3/56 |
|
y3 |
9/112 |
-73/112 |
23/112 |
1 |
0 |
0 |
-3/112 |
-1/16 |
19/112 |
|
y5 |
25/112 |
183/112 |
151/112 |
0 |
0 |
1 |
29/112 |
-1/16 |
3/112 |
|
z |
5/14 |
5/7 |
6/7 |
0 |
0 |
0 |
3/14 |
0 |
1/7 |
|
|
z* |
0 |
0 |
9/112 |
3/56 |
25/112 |
0 |
0 |
0 |
Двойственная
задача имеет оптимальный план
.
Исходя из решения двойственной задачи решаем прямую, составляем следующую систему
Решаем систему уравнений:
Используя решение пары двойственных задач, найдем цену игры и оптимальные стратегии игроков.
- цена игры.
.
-
.оптимальная стратегия для игрока
.
-
.оптимальная стратегия для игрока
.
Ответ:
Задача 7. На сети дорог указаны стоимости перевозки единиц груза между отдельными пунктами сети. Найти наиболее экономный маршрут доставки груза. Чему равны суммарные затраты по доставке единицы груза оптимальным маршрутом?
N=1
В пункт 12 груз может быть доставлен из пункта 9, 10 или из пункта 11, поэтому вычисляем:
min [17;16;19] = 16
Маршрут 10, 12.
N=2
В пункты 9, 10 и 11 груз может быть доставлен из пункта 5, 6, 7 или 8, поэтому вычисляем отдельно затраты на перевозку ед. груза для пункта 5, 6, 7 и 8.
Для пункта 5:
Маршрут из пункта 5: 5, 10, 12 – 30 единиц.
Для пункта 6:
Маршрут из пункта 6: 6, 9, 12 – 32 единицы.
Для пункта 7:
Маршрут из пункта 7: 7, 10, 12 – 30 единиц.
Для пункта 8:
Маршрут из пункта 8: 8, 10, 12 – 30 единиц.
N=3
В пункты 5, 6, 7 и 8 груз может быть доставлен из пункта 2, 3 или 4, поэтому вычисляем отдельно затраты на перевозку ед. груза для пункта 2, 3 и 4.
Для пункта 2:
Маршрут
из пункта 2: 2, 6, 9, 12 – 42 единиц.
Для пункта 3:
Маршрут
из пункта 3: 3, 7, 10, 12 – 40 единиц
Для пункта 4:
Маршрут из пункта4: 4, 8, 10, 12 – 44 единицы.
N=4
В пункты 2, 3 и 4 груз может быть доставлен из пункта 1.
Оптимальный маршрут 1, 3, 7, 10, 12 с наименьшими затратами 51единица.
Проверяем решение через программу «Графоанализатор»
Задача 8. Распределить имеющиеся ресурсы в размере 120 тыс. руб. между 4-мя предприятиями, если увеличение продукции в зависимости от представленных средств характеризуется таблицей:
|
Средства |
Предприятия | |||
|
1 |
2 |
3 |
4 | |
|
Прирост выпуска продукции на предприятиях | ||||
|
20 |
7 |
18 |
9 |
9 |
|
40 |
15 |
15 |
14 |
15 |
|
60 |
5 |
14 |
5 |
13 |
|
80 |
16 |
19 |
5 |
2 |
|
100 |
20 |
21 |
18 |
19 |
|
120 |
21 |
15 |
6 |
19 |
|
|
|
|
|
|
| ||||||
|
|
|
|
|
|
|
|
|
| |||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
20 |
0 20 |
20 0 |
0+9=9 9+0=9 |
9 |
0 |
0+9=9 18+0=18 |
18 |
20 |
0+18=18 7+0=7 |
18 |
0 |
|
40 |
0 20 40 |
40 20 0 |
0+15=15 9+9=18 14+0=14 |
18 |
20 |
0+18=18 18+9=27 15+0=15 |
27 |
20 |
0+27=27 7+18=25 15+0=15 |
27 |
0 |
|
60 |
0 20 40 60 |
60 40 20 0 |
0+13=13 9+15=24 14+9=23 5+0=5 |
24 |
20 |
0+24=24 18+18=36 15+9=24 14+0=14 |
36 |
20 |
0+36=36 7+27=34 15+18=33 5+0=5 |
36 |
0 |
|
80 |
0 20 40 60 80 |
80 60 40 20 0 |
0+2=2 9+13=22 14+15=29 5+9=13 5+0=5 |
29 |
40 |
0+29=29 18+24=42 15+18=33 14+9=23 19+0=19 |
42 |
20 |
0+42=42 7+36=43 15+27=42 5+18=23 16+0=16 |
43 |
20 |
|
100 |
0 20 40 60 80 100 |
100 80 60 40 20 0 |
0+19=19 9+2=11 14+13=27 5+15=20 5+9=14 18+0=18 |
27 |
40 |
0+27=27 18+29=47 15+24=39 14+18=32 19+9=28 21+0=21 |
47 |
20 |
0+47=47 7+42=49 15+36=51 5+27=32 16+18=43 20+0=20 |
51 |
40 |
|
120 |
0 20 40 60 80 100 120 |
120 100 80 60 40 20 0 |
0+19=19 9+19=28 14+2=16 5+13=18 5+15=20 18+9=27 6+0=6 |
28 |
20 |
0+28=28 18+27=45 15+29=44 14+24=38 19+18=37 21+9=30 15+0=15 |
45 |
20 |
0+45=45 7+47=54 15+42=57 5+36=41 16+27=43 20+18=38 21+0=21 |
57 |
40 |
=3
=2
=1
Ответ:
Максимум суммарной прибыли равен 57 усл.
ед., т. е.
1 предприятию должно быть выделено 40 усл. ед., 2-му – 20 усл. ед., 3-ему – 20 усл. ед. и 4-ому – 40 усл. ед., так как 120-40-20-20=40.