Сетевое планирование
СОДЕРЖАНИЕ: Построение сетевой модели, расчет временных параметров событий. Критический путь модели. Оптимизация сетевой модели по критерию минимум исполнителей. Исходные данные для оптимизации загрузки. Оптимальное решение игры двух лиц с нулевой суммой.Содержание
Сетевое планирование и управление
Исходные данные для оптимизации загрузки
Оптимальное решение игры двух лиц с нулевой суммой
Сетевое планирование и управление
Построить сетевую модель, рассчитать временные параметры событий (на рисунке) и работ (в таблице);
Определить критические пути модели;
Оптимизировать сетевую модель по критерию “минимум исполнителей” (указать какие работы надо сдвигать и на сколько дней, внесенные изменения показать на графиках привязки и загрузки пунктирной линией).
| Название работы | Нормальная длительность | Количество исполнителей | Вариант 8 (N=11 человек) C, D, E- исходные работы проекта, которые могут начинаться одновременно; Работа А следует за С, работа Fначинается сразу после окончания работы А; Работа G следует за F; Работа В следует за D, а работы I и J следуют за В; Работа H следует J и Е, но не может начаться, пока не завершена работа G. |
| A | 9 | 8 | |
| B | 10 | 3 | |
| C | 6 | 6 | |
| D | 5 | 4 | |
| E | 16 | 5 | |
| F | 12 | 2 | |
| G | 14 | 1 | |
| H | 15 | 3 | |
| I | 11 | 5 | |
| J | 3 | 7 |
На рисунке 1 представлена сетевая модель, соответствующая данному упорядочению работ. Каждому событию присвоен номер, что позволяет в дальнейшем использовать не названия работ, а их коды (см. табл.1). Численные значения временных параметров работ сети представлены в табл.2.
Таблица 1
Описание сетевой модели с помощью кодирования работ
| Номера событий | Код работы | Продолжительность работы | |
| начального | конечного | ||
| 1 | 2 | (1,2) | 6 |
| 1 | 3 | (1,3) | 5 |
| 1 | 7 | (1,7) | 16 |
| 2 | 4 | (2,4) | 9 |
| 3 | 5 | (3,5) | 10 |
| 4 | 6 | (4,6) | 12 |
| 5 | 6 | (5,6) | 11 |
| 5 | 7 | (5,7) | 3 |
| 6 | 7 | (6,7) | 14 |
| 7 | 8 | (7,8) | 15 |
A F
9 12
C
6 I
D B 11
5 10 J 14 G
E 3 H
16 15
Рис.1 Сетевая модель
Таблица 2
Временные параметры работ
| (i,j) | t (i,j) | TPH (i,j) | TPO (i,j) | TПН (i,j) | TПО (i,j) | RП (i,j) | RC (i,j) |
| (1,2) | 6 | 0 | 6 | 0 | 6 | 0 | 0 |
| (1,3) | 5 | 0 | 5 | 1 | 6 | 1 | 0 |
| (1,7) | 16 | 0 | 16 | 25 | 41 | 25 | 0 |
| (2,4) | 9 | 6 | 15 | 6 | 15 | 0 | 0 |
| (3,5) | 10 | 5 | 15 | 6 | 16 | 1 | 1 |
| (4,6) | 12 | 15 | 27 | 15 | 27 | 0 | 0 |
| (5,6) | 11 | 15 | 26 | 16 | 27 | 1 | 1 |
| (5,7) | 3 | 15 | 18 | 38 | 41 | 23 | 23 |
| (6,7) | 14 | 27 | 41 | 27 | 41 | 0 | 0 |
| (7,8) | 15 | 41 | 56 | 41 | 56 | 0 | 0 |
Исходные данные для оптимизации загрузки
Таблица 3
| Код работ | Продолжительность работ | Количество исполнителей |
| (1,2) | 6 | 6 |
| (1,3) | 5 | 4 |
| (1,7) | 16 | 5 |
| (2,4) | 9 | 8 |
| (3,5) | 10 | 3 |
| (4,6) | 12 | 2 |
| (5,6) | 11 | 5 |
| (5,7) | 3 | 7 |
| (6,7) | 14 | 1 |
| (7,8) | 15 | 3 |
Допустим, что организация, выполняющая проект, имеет в распоряжении только N = 11 исполнителей. Но в соответствии с графиком загрузки (рис.2), в течение интервала времени с 3 по 16 день для выполнения проекта требуется работа одновременно 41, 39 и затем 40 человек. Таким образом, возникает необходимость снижения максимального количества одновременно занятых исполнителей с 41 до 15 человек.
Проанализируем возможность уменьшения загрузки (41 человек) в течение 5 дня. Используя Rc (5,6) = 5, сдвинем работу (5,7) на 1 день, что снизит загрузку 5-го дня до 2 человек, но при этом в 11 день появится пик - 42 исполнителя. Для его устранения достаточно сдвинуть работу (6,7) на 1 день, используя Rc (6,7) = 1.
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
Рис.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 ). Системы уравнений приведенные выше в данном случае имеют вид:
Решая эти системы, получаем 
v = 0.
Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью -3 и 4 при этом средний выигрыш равен 0.
Оптимальное решение игры двух лиц с нулевой суммой.
Определите оптимальные стратегии и цену игры. Для 1) - в чистых стратегиях, для 2) - в смешанных.
1) 
2) 
Таблица 5
| B1 | B2 | B3 | B4 | |
|
| A1 | 2 | 3 | 4 | 2 | 2 |
| A2 | 3 | 5 | 2 | 4 | 2 |
| A3 | 2 | 5 | 4 | 6 | 2 |
|
3 | 5 | 4 | 6 | |
Решение.
Все расчеты удобно проводить в таблице, к которой, кроме матрицы Р, введены столбец и строка (табл.1). Анализируя строки матрицы (стратегии игрока А), заполняем столбец : а1
= 2; а2
= 2; а3
= 2 - минимальные числа в строках 1, 2,3. Аналогично = 3; = 5; = 4; = 6 - максимальные числа в столбцах 1, 2, 3 соответственно. Нижняя цена игры , (2; 2;
2) = 2 (наибольшее число в столбце ) и верхняя цена игры , (3; 5; 4;
6) = 3 (наименьшее число в строке ). Эти значения не равны, т.е. , и, так как они достигаются ни на одной и той же паре стратегий, то игра седловой точки не имеет.
И, так как игра седловой точки не имеет, то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение случайным образом чередуя чистые стратегии.
Пусть игра задана платежной матрицей
Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию
,
а игрок В чистую стратегию В1 (это соответствует первому столбцу платежной матрицы Р), равен цене игры v:
Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию В2 , т.е.
.
Учитывая, что получаем систему уравнений для определения оптимальной стратегии S*A
и цены игры v:
Решая эту систему, получим оптимальную стратегию
и цену игры
Применяя теорему об активных стратегиях при отыскании - оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1
или А2
) средний проигрыш игрока В равен цене игры v, т.е.
Тогда оптимальная стратегия () определяется формулами:
Применим полученные результаты для отыскания оптимальных стратегий для игры, рассмотренной выше.
Игра задана платежной матрицей без седловой точки:
Поэтому ищем решение в смешанных стратегиях: для игрока А средний выигрыш равен цене игры v (при В1 и В2 ) для игрока В средний проигрыш равен цене игры v (при А1 и А2 ). Системы уравнений приведенные выше в данном случае имеют вид:
Решая эти системы, получаем 
v = 0.
Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью -1 и 2 при этом средний выигрыш равен 0.