Планування мереж

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Зміст

Мережеве планування та управління

Вихідні дані для оптимізації завантаження

Оптимальне рішення гри двох осіб з нульовою сумою

Мережеве планування та управління

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

Визначити критичні шляху моделі;

Оптимізувати мережеву модель за критерієм "мінімум виконавців" (вказати які роботи треба зрушувати і на скільки днів, внесені зміни показати на графіках прив'язки і завантаження пунктирною лінією).

Назва роботи

Нормальна тривалість

Кількість виконавців

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

AF

12 вересня

C

6 I

DB 11

10 травня J 14 G

E 3 H

16 15

Рис.1 Мережева модель

Таблиця 2

Тимчасові параметри робіт

(I, j)

t (i, j)

T PH (i, j)

T PO (i, j)

T ПН (i, j)

T ПЗ (i, j)

R П (i, j)

R C (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 грудня

10 листопада

9

3 червень

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 грудня

10 листопада

9

3 червень

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


B 1

B 2

B 3

B 4

A 1

1

3

4

1

1

A 2

5

6

9

1

1

A 3

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


B 1

B 2

B 3

B 4

A 1

2

3

4

2

2

A 2

3

5

2

4

2

A 3

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.

Додати в блог або на сайт

Цей текст може містити помилки.

Маркетинг, реклама и торгівля | Контрольна робота
62.8кб. | скачати

Схожі роботи:
Планування балансового прибутку Показники планування нормування оборотних коштів підприємства
Основи ІР мереж
Основи ІР-мереж
Технологія роботи IP-мереж
Інтеграція різнорідних мереж
Структуризація телекомунікаційних мереж
Еволюція обчислювальних мереж
Моделі нейронних мереж
Топологія локальних мереж
© Усі права захищені
написати до нас