Сетевое планирование

9108
знаков
6
таблиц
3
изображения

Содержание

Сетевое планирование и управление

Исходные данные для оптимизации загрузки

Оптимальное решение игры двух лиц с нулевой суммой


Сетевое планирование и управление

Построить сетевую модель, рассчитать временные параметры событий (на рисунке) и работ (в таблице);

Определить критические пути модели;

Оптимизировать сетевую модель по критерию “минимум исполнителей” (указать какие работы надо сдвигать и на сколько дней, внесенные изменения показать на графиках привязки и загрузки пунктирной линией).

Название работы Нормальная длительность Количество исполнителей

Вариант 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.


Информация о работе «Сетевое планирование»
Раздел: Маркетинг
Количество знаков с пробелами: 9108
Количество таблиц: 6
Количество изображений: 3

Похожие работы

Скачать
17484
11
1

... граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть». Объектом управления в системах сетевого планирования и управления являются коллективы исполнителей, располагающие определенными ресурсами и выполняющие комплекс операций, который призван обеспечить достижение намеченной цели, например разработку новой услуги – ...

Скачать
13350
0
5

... . К сожалению, это наиболее распространенная ошибка, когда планирование выполняется ради того, чтобы был план. Все ошибки планирования могут стать причиной негативного отношения к плану, когда он перестает быть реальным инструментом управления работами по проекту. Детальное планирование Детальное планирование связано с разработкой детальных графиков для оперативного управления на уровне ...

Скачать
20150
5
0

... , в котором не учитывается ориентация дуг. Сетевой график – это связанный взвешенный орграф без контуров (петель). На изображении комплекса работ с помощью сетевого графика основано сетевое планирование и управление (СПУ). События обозначаются на сетевом графике вершинами. Подготовка исходных данных для построения сетевого графика включает: - определение начального и конечного событий; - ...

Скачать
9886
2
0

... и провести оптимизацию по времени на компьютере. Количество исполнителей для всех работ. Вариант № 23 Решение Для организации разработки большое распространение получил метод сетевого планирования и управления. Сетевая модель позволяет описать узловые события процесса производства и связи между ними, характеризует внутреннюю структуру процесса производства. Элементами сети являются работы ...

0 комментариев


Наверх