Сетевое планирование
1,7 5
1,3 4
1,2 6
Рис.2 Графики загрузки (а) и привязки (b) до оптимизации.
Проанализируем возможность уменьшения загрузки (38 человек) с 7-го по 12 день, т.е. в течение интервала времени в 6 дней. Так работа (2,4) является единственной, которую можно сдвинуть таким образом, чтобы она не выполнялась в указанные 6 дней с 7-го по 12 день. Для этого, используя Rп (2,4) = 8, сдвинем работу Tу (i,j) на 4 дня, после чего она будет начинаться уже не в 6-й, а в 10 день, к чему мы и стремились. Но поскольку Rс (2,4) = 0 и для сдвига работы Tн (i,j) был использован полный резерв, то это влечет за собой обязательный сдвиг на 7 дней работы (6,7), следующей за работой (2,4).
В результате произведенных сдвигов максимальная загрузка сетевой модели уменьшилась с 41 до 15 человек, что и являлось целью проводимой оптимизации. Окончательные изменения в графиках привязки и загрузки показаны на рис.3 пунктирной линией.
Проведенная оптимизация продемонстрировала следующее различие использования свободных и полных резервов работ. Так, сдвиг работы на время в пределах ее свободного резерва не меняет моменты начала последующих за ней работ. В тоже время сдвиг работы на время, которое находится в пределах ее полного резерва, но при этом превышает ее свободный резерв, влечет сдвиг последующих за ней работ.
15 16
14 12
11 10
9
3 6
7,8 3
6,7 1
5,7 7
5,6 5
4,6 2
3,5 3
2,4 8
1,7 5
1,3 4
1,2 6
Рис.3 Графики загрузки (а) и привязки (b) после оптимизации.
Оптимальное решение игры двух лиц с нулевой суммой
Определите оптимальные стратегии и цену игры. Для 1) - в чистых стратегиях, для 2) - в смешанных.
1)
2)

Таблица 5
| B1 | B2 | B3 | B4 |
|
|
| A1 | 1 | 3 | 4 | 1 | 1 |
| A2 | 5 | 6 | 9 | 1 | 1 |
| A3 | 2 | 8 | 4 | 3 |
2 |
|
|
5 | 8 | 9 |
3 |
|
Решение
Все расчеты
удобно проводить
в таблице, к
которой, кроме
матрицы Р, введены
столбец
и строка
(табл.1). Анализируя
строки матрицы
(стратегии
игрока А), заполняем
столбец
:
а1 = 1; а2 = 1; а3
= 2 - минимальные
числа в строках
1, 2,3. Аналогично
= 5;
=
8;
= 9;
= 3 - максимальные
числа в столбцах
1, 2, 3 соответственно.
Нижняя цена
игры
,
(1; 1;
2) = 2 (наибольшее
число в столбце
)
и верхняя цена
игры
,
(5; 8; 9;
3) = 3 (наименьшее
число в строке
).
Эти значения
не равны, т.е.
,
и, так как они
достигаются
ни на одной и
той же паре
стратегий, то
игра седловой
точки не имеет.
И, так как игра
седловой точки
не имеет, то
применение
чистых стратегий
не дает оптимального
решения игры.
В таком случае
можно получить
оптимальное
решение случайным
образом чередуя
чистые стратегии.
Пусть игра
задана платежной
матрицей

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию
,
а игрок В чистую стратегию В1 (это соответствует первому столбцу платежной матрицы Р), равен цене игры v:
![]()
Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию В2, т.е.
.
Учитывая,
что
получаем систему
уравнений для
определения
оптимальной
стратегии S*A
и цены игры v:

Решая эту систему, получим оптимальную стратегию


и цену игры

Применяя
теорему об
активных стратегиях
при отыскании
- оптимальной
стратегии
игрока В, получаем,
что при любой
чистой стратегии
игрока А (А1
или А2) средний
проигрыш игрока
В равен цене
игры v, т.е.

Тогда оптимальная
стратегия
(
)
определяется
формулами:


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

Поэтому ищем решение в смешанных стратегиях: для игрока А средний выигрыш равен цене игры v (при В1 и В2) для игрока В средний проигрыш равен цене игры v (при А1 и А2). Системы уравнений приведенные выше в данном случае имеют вид: