МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
/
Розрахунково-графічна робота
з курсу «Математичні методи дослідження операцій»
Варіант 84
Теоретична частина:
1(21)) Метод критичного шляху (CPM) — це алгоритм для планування групи діяльностей проекту.
2(22)) Пізній термін здійснення подій – це такий термін, перевищення якого викликає відповідну затримку всієї розробки. Визначається пізній термін як різниця між тривалістю критичного шляху і максимального з наступних за даною подією шляхів.
Резерви часу робіт, їх початок і закінчення, розраховується по ранніх і пізніх термінах здійснення відповідних подій.
3(23)) Формальна постановка транспортної задачі Умови транспортної задачі зручно записувати за допомогою таблиці, що називається транспортною таблицею. Подана нижче таблиця відображає задачу з трьома пунктами виробництва A_1, A_2, A_3, що виробляють 15, 25 і 10 одиниць товару і чотирма пунктами споживання B_1, B_2, B_3, B_4, попит в яких рівний, відповідно 5, 15, 15 і 15. На перетині рядка A_i і B_j подається значення c_{ij} — вартість транспортування товару з пункту i в пункт j. Для даної задачі, наприклад c_{23} рівне 9, тобто транспортування одиниці товару з пункту A_2 в пункт B_3 коштує 9 грошових одиниць.
4(24)) Теорія ігор – розділ прикладної математики, який вивчає математичні моделі прийняття рішень у так званих конфліктних ситуаціях, що мають місце. Основоположниками теорії ігор є математик Дж. Фон Непман та економіст О. Моргенштерн. В подальшому її розвинули Неш Джон, Зелтен Райнхард, Харшаньї Джон Чарльз, які в 1994 р. стали лауреатами премії пам'яті Альфреда Нобеля з економіки "за пріоритетний вклад в аналіз некооперативних ігор"
Приклад 1. Побудувати математичну модель задачі
Розв’язок. Вихідні дані задачі запишемо в вигляді таблиці 1.
Таблиця 1.
Пункти
Відправлення
Пункти призначення
Запаси
7
8
1
160
2
160
4
120
5
9
8
20
140
9
2
50
3
30
6
90
170
Потреби
120
50
190
110
470
Мінімальний тариф, що дорівнює 1, знаходиться в клітинці для змінної . Припустимо , запишемо це значення в відповідну клітинку таблиці 1 і виключимо тимчасово з розгляду рядок . Потреби пункту призначення рахуємо рівними 30 од.
В частині таблиці, яка залишилася, з двома рядками і , і чотирма стовбцями , , і клітинка з найменшим значенням тарифу знаходиться на перетині рядка і стовбця , де . Припустимо і внесемо це значення в відповідну клітинку таблиці 1.
Тимчасово виключимо з розгляду стовбець і будемо рахувати, що запаси пункту дорівнюють 120 од. Після цього розглянемо частину таблиці, яка залишилася, з двома рядками і , і трьома стовбцями , і . В ній мінімальний тариф знаходиться в клітинці на перетині рядка і стовбця і дорівнює . Заповнимо описаним вище методом цю клітинку і аналогічно заповнимо (в певній послідовності) клітинки, які знаходяться на перетині рядка і стовбця , рядка і стовбця , рядка і стовбця . В результаті отримаємо опорний план
При даному плані перевезень загальна вартість перевезень складає
.
4(24)) Розв’язати гру — це означає знайти оптимальну стратегію для кожного гравця. Оптимальною стратегією гравця називається така стратегія, яка за багаторазового повторення гри забезпечує гравцеві максимально можливий середній виграш (або мінімально можливий середній програш). Для знаходження цієї пари стратегій використовують “принцип мінімакса”, сутністю якого є міркування, що супротивник зробить все для того, щоб перешкодити досягненню супротивником своєї цілі. Стратегію першого (другого) гравця називають оптимальною, якщо в разі її багаторазового застосування виграш (програш) першого (другого) гравця не зменшується (не збільшується), які б стратегії не застосовував супротивник.
Практична частина:
1)Побудувати математичну модель задачі
Склади
Пункти
Запаси
1
2
1
7
8
58
2
13
7
58
3
7
13
25
Потреба
105
36
Вхідні дані
Вартості пер...
