11.3 Контрольні запитання до тем 6-11.

1. Яка задача математичного програмування називається цілочисельною?

2. Приклади задач цілочисельного програмування.

3. Методи розв’язування задач цілочисельного програмування.

4. Зміст поняття «правильне відтинання».

5. Метод Гоморі.

6. Метод віток і меж.

7. Сформулюйте задачу дробово-лінійного програмування.

8. Метод розв’язування задач дробово-лінійного програмування.

9. Запишіть загальну задачу нелінійного програмування.

10. Труднощі розв’язування задач нелінійного програмування.

11. Функція Лагранжа.

12. Метод Лагранжа.

13. Яка функція називається опуклою (угнутою)?

14. Сформулюйте необхідні та достатні умови існування сідлової точки для деякої диференційованої функції.

15. Сформулюйте задачу динамічного програмування.

16. Методи розв’язування задач динамічного програмування.

17. Наведіть приклади реальних динамічних задач.

18. Що називається конфліктною ситуацією?

19. Що таке гра?

20. Що таке хід гри?

21. Дайте визначення платіжної матриці.

22. Сформулюйте принцип «мінімаксу».

23. Дайте визначення максмінної та мінімаксної стратегії.

24. Яка гра називається скінченою, парною?

25. Які властивості мають оптимальні стратегії гравців?

26. Дайте визначення понять виграш, ціна гри, нижня і верхня ціни гри.

27. Сформулюйте основну теорему теорії ігор.

28. Зведення гри до задачі лінійного програмування.

29. Сутність задач стохастичного програмування..

30. Яка стохастична задача називається одноетапною?

31. Яка стохастична задача називається двохетапною?

32. Методи розв’язування стохастичних задач.

11.4 Теми рефератів до тем 6-11

1. Цілочислові задачі математичного програмування.

2. Проблеми розв’язування нелінійних задач.

3. Опуклі (угнуті) функції.

4. Теорія двоїстості нелінійного програмування.

5. Необхідні та достатні умови розв’язування задач математичного програмування.

6. Теорема Куна—Таккера.

7. Квадратичне програмування.

8. Опукле програмування.

9. Сепарабельні функції та їх лінеаризація.

10. Наближені методи розв’язування нелінійних задач.

11. Принцип Беллмана.

12. Динамічне програмування та найкоротші шляхи.

13. Скінченні антагоністичні ігри.

14. Нескінченні антагоністичні ігри.

15. Багатокрокові ігри.

16. Кооперативні ігри.

17. Метод проектування стохастичних квазіградієнтів.

18. Метод стохастичної апроксимації.

12. Методи мережевого планування

12.1 Приклади розв’язування навчальнихзавдань

Приклад 12.1

Основні принципи побудови мережевого графіка. Розглянемо основні принципи побудови мережевого графіка за даними таблиці 12.1.

Таблиця 12.1

Перелік подій та робіт з підготовки масового виробництва

кузова легкового автомобіля

№	Подія	№	Роботи
1	2	3	4
0	Призначено керівника розробок	0,1	Видача завдання, узгодження ТУ на кузов
1	Завдання видано; ТУ на кузов узгоджено	1,2	Розробка конструкції нового кузова
2	Розробка нового кузова завершена	2,3 2,4 2,8	Розробка планових креслень Виготовлення дослідного зразка кузова Розробка маршрутної технології виготовлення кузова
3	Планові креслення розроблені	3,5	Проектування мастер-моделі
4	Дослідний зразок виготовлено	4,5	Випробування дослідного зразку
5	Мастер-модель спроектована, дослідний зразок випробуваний	5,6	Внесення змін у проект мастер-моделі
6	Проект мастер-моделі	6,7	Виготовлення мастер-моделі
7	Виготовлення мастер-моделі завершено	7,9	Проектування крупно габаритних штампів
8	Розробка маршрутної технології виготовлення кузова завершена	8,10	Розробка детальних технологічних процесів
9	Крупно габаритні штампи спроектовано	9,11	Розміщення замовлень на виготовлення штампів
10	Розробка технологічних процесів завершена	10,12 10,13	Розробка переліку нестандартного обладнання Проектування інструментального оснащення
11	Замовлення на виготовлення штампів розміщені	11,15	Виготовлення крупно габаритних штампів
12	Перелік нестандартного обладнання визначено	12,16	Розміщення замовлень на проектування нестандартного обладнання
13	Інструментальне оснащення спроектоване	13,14	Розміщення замовлень на інструментальне оснащення
14	Замовлення на інструментальне оснащення розміщено	14,17	Виготовлення інструментального оснащення для кузова
15	Крупно габаритні штампи виготовлені	15,21	Монтаж, наладка штампового оснащення
16	Замовлення на проектування нестандартного обладнання розташовані	16,18	Проектування нестандартного обладнання
17	Інструментальне оснащення для кузова виготовлено	17,21	Монтаж та налагодження інструментального оснащення
18	Робочі креслення на нестандартне обладнання отримано	18,19	Розміщення замовлень на виготовлення нестандартного обладнання
19	Замовлення на виготовлення нестандартного обладнання розташовано	19,20	Виготовлення нестандартного обладнання
20	Нестандартне обладнання отримано	20,21	Монтаж та наладка нестандартного обладнання
21	Інструментальне оснащення, штампи, нестандартне обладнання для виготовлення кузова сплановано та налагоджено

За даними таблиці 12.1 мережевий графік (рис. 12.1). Пунктирна робота від події 6 до події 8 називається фіктивною. Вона означає, що подія 8 пов’язана з подією 6. Робота 8,10 може розпочатися тільки після завершення події 6.

У мережі на рис. 12.1 від вхідної до завершальної події приводять кілька шляхів, які ведуть через події:

Рис. 12.1. Мережевий графік технічної підготовки виробництва кузова легкового автомобіля.

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

Оцінки часу виконання робіт в мережах. Відповідальний по кожному виду робіт мережевої моделі визначає час робіт. Для повторювальних робіт, які зустрічалися в минулому, за якими є статистичні дані або розроблені нормативи, встановлюється найбільш ймовірна або нормативна тривалість ( або ), наприклад, в календарних днях:

,

де  трудомісткість цієї роботи, норм-год.;

 частка додаткових робіт, яка доручена цій групі робітників паралельно з роботою, яка ввійшла до сітьового графіка;

 кількість робітників, які беруть участь у виконанні цієї роботи;

 кількість годин у робочому дні;

 коефіцієнт переводу робочих днів у календарні з урахуванням відпусток робітників ( );

 коефіцієнт виконання норм ( ).

По роботах, час виконання яких не визначено, виконавець надає залежно від прийнятої системи дві або три ймовірні оцінки часу. При цьому оцінки розглядаються як пропозиція, яка основана на досліді, інтуїції та врахуванні факторів, які впливають на тривалість роботи.

У системі з трьома оцінками задають: мінімальну ( ), максимальну ( ) та найбільш імовірну ( ) оцінки часу. Ці величини є початковими для розрахунку очікуваного часу виконання роботи ( ).

Величина представляє собою математичне очікування випадкової величини, якою в цьому випадку є тривалість роботи. Для більш повної характеристики розподілу випадкової величини використовується дисперсія . Природно припускати, що тривалість кожної роботи в мережі, як випадкова величина, має свій власний вид розподілу, який може змінюватись залежно від місця та часу проведення робіт. Найбільш часто при розробці сітьових моделей використовують бета-розподіл , функція щільності розподілу якого має вигляд:

,

де  щільність розподілу;

 постійна величина;

;

Тут та  параметри розподілу;

та  мінімальний та максимальний час виконання роботи: ; .

Зазвичай, величину визначають за наближеною формулою:

;

величину дисперсії

;

час очікування

.

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

.

До основних параметрів мережевої моделі відносяться резерви часу.

Резерв часу події визначається як різниця між пізнім та раннім строками настання події:

.

Якщо позначити попередню подію як , а наступну – як , то відповідно ранній та пізній строки звершення подій будуть позначатися як та , та , тобто поряд з індексом, який визначає характер строку завершення події записується номер події. Якщо  початкова подія, а  завершальна, то

де  максимальний шлях;

 критичний шлях;

 час критичного шляху;

 час від початкової до -тої події максимальний;

 час від -тої події до завершальної максимальний.

Всі події, які знаходяться на критичному шляху мають нульовий резерв часу.

Для табл. 12.1 складаємо зведену таблицю параметрів мережевого графіка (табл. 12.2). Критичний шлях дорівнює 1380 дням.

Таблиця 12.2

Вихідні дані параметрів мережевого графіка

Початкова подія	Кінцева подія
1	2	3	4	5	6	7	8
0	1	30	30	30	0	0	0
1	2	150	180	180	0	0	0
2	3	100	280	360	80	80	0
2	4	150	330	330	0	0	0
2	8	30	400	500	100	290	190
3	5	20	380	380	80	80	80
4	5	50	380	380	0	0	0
5	6	20	400	100	0	0	0
6	7	80	480	480	0	0	0
6	8	0	400	500	100	100	0
7	9	150	630	630	0	0	0
8	10	120	520	620	100	100	0
9	11	30	660	660	0	0	0
10	12	30	550	650	100	100	0
10	13	150	670	1050	380	380	0
11	15	510	1170	1170	0	0	0
12	16	100	650	750	100	100	0
13	14	30	700	1080	380	380	0
14	17	200	900	1280	380	380	0
15	21	210	1380	1380	0	0	0
16	18	150	800	900	100	100	0
17	21	100	1380	1380	0	380	380
18	19	30	830	930	100	100	0
19	20	250	1080	1180	100	100	0
20	21	200	1380	1380	0	100	100

Резерви часу мають не тільки події, але і шляхи (крім критичного), а також роботи, які знаходяться на некритичному шляху. Для визначення повного резерву часу шляху необхідно знову повернутися до тієї умови, що довжина критичного шляху в мережевому графіку більша, ніж довжина будь-якого іншого шляху. Різниця між часом критичного шляху та часом будь-якого шляху називається повним резервом часу шляху

.

Повний резерв шляху показує, наскільки може бути збільшена тривалість всіх робіт, які належать шляху в сумі (граничне допустиме значення збільшення тривалості шляху).

Повний резерв часу роботи – це максимальна кількість часу, на який можна збільшити тривалість цієї роботи, не змінюючи при цьому тривалість критичного шляху.

Тобто повний резерв роботи буде:

,

де  початкова подія цієї роботи;

 кінцева подія цієї роботи;

 тривалість роботи від -тої до -тої події.

В окремих роботах, крім повного резерву часу, є вільний резерв часу

.

Вільний резерв часу – це максимальна кількість часу, на яку можна збільшити тривалість роботи або відстрочити її початок, не змінюючи при цьому ранніх строків початку наступних робіт, за умови, що початкова подія цієї роботи настала в свій ранній строк.

Якщо для роботи , то ця робота знаходиться на критичному шляху. Для нашого випадку критичний шлях проходить через роботи:

.