Контрольная работа Сетевое планирование
Работа добавлена на сайт bukvasha.net: 2015-10-25Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Содержание
Сетевое планирование и управление
Исходные данные для оптимизации загрузки
Оптимальное решение игры двух лиц с нулевой суммой
Сетевое планирование и управление
Построить сетевую модель, рассчитать временные параметры событий (на рисунке) и работ (в таблице);
Определить критические пути модели;
Оптимизировать сетевую модель по критерию “минимум исполнителей” (указать какие работы надо сдвигать и на сколько дней, внесенные изменения показать на графиках привязки и загрузки пунктирной линией).
Название работы | Нормальная длительность | Количество исполнителей | Вариант 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
Решение. Все расчеты удобно проводить в таблице, к которой, кроме матрицы Р, введены столбец и строка (табл.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. 2. Курсовая на тему Illumination in Bonaventure’s Epistemology 3. Реферат на тему Network Debate Essay Research Paper It was 4. Реферат Чарльз Бэббидж 5. Реферат Мировые круизные компании 6. Реферат на тему Понятие о методах и средствах воспитания 7. Реферат на тему Византия в VI в Димы Восстание Ника 8. Статья Функции лингвистических стопперов в пресс-рекламном тексте региональный аспект 9. Реферат на тему A UK Bill Of Right 10. Реферат на тему The Great Gatsbysuper Notes Essay Research Paper |