Реферат: Сетевое планирование
Содержание
Сетевое планирование и управление
Исходные данные для оптимизации загрузки
Оптимальное решение игры двух лиц с нулевой суммой
Сетевое планирование и управление
Построить сетевую модель, рассчитать временные параметры событий (на рисунке) и работ (в таблице);
Определить критические пути модели;
Оптимизировать сетевую модель по критерию “минимум исполнителей” (указать какие работы надо сдвигать и на сколько дней, внесенные изменения показать на графиках привязки и загрузки пунктирной линией).
Название работы
Нормальная длительность
Количество исполнителей
Вариант 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
--PAGE_BREAK--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
6
6
(1,3)
5
5
1
6
1
(1,7)
16
16
25
41
25
(2,4)
9
6
15
6
15
(3,5)
10
5
15
6
16
1
1
(4,6)
12
15
27
15
27
(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
(7,8)
15
41
56
41
56
Исходные данные для оптимизации загрузки
Таблица 3
Код работ
Продолжительность работ
Количество исполнителей
(1,2)
6
6
(1,3)
5
4
(1,7)
16
5
(2,4)
9
8
(3,5)
10
продолжение--PAGE_BREAK----PAGE_BREAK--
Решение
Все расчеты удобно проводить в таблице, к которой, кроме матрицы Р, введены столбец /> и строка /> (табл.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.