Реферат: Сетевое планирование

Содержание

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

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

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

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

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

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

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

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

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

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 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 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

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

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

1 3 4 1 1

5 6 9 1 1

2 8 4 3

5 8 9

Решение

Все расчеты удобно проводить втаблице, к которой, кроме матрицы Р, введены столбец /> и строка /> (табл.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

2 3 4 2 2

3 5 2 4 2

2 5 4 6 2

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:

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

и цену игры

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

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

Игра задана платежной матрицейбез седловой точки:

/> />

Решая эти системы, получаем /> v = 0.

Это означает, что оптимальнаястратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегиислучайным образом, выбирая каждое из убежищ с вероятностью -1 и 2 при этомсредний выигрыш равен 0.

еще рефераты

Еще работы по маркетингу

Реферат по маркетингу

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

31 Августа 2013

Реферат по маркетингу

Сетевой маркетинг

31 Августа 2013

Реферат по маркетингу

Сетевой маркетинг как форма организации бизнеса

31 Августа 2013

Реферат по маркетингу

Сетевые коммуникации

31 Августа 2013