Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Дослідження операцій та методи оптимізації

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

Національний транспортний університет

Контрольна робота

з дисципліни „Дослідження операцій та методи оптимізації”

спеціальність ______________________________

Варіант №9

Виконав (студент) ___________

Номер залік. книжки_________

Перевірив (викладач) ________

Дата подання роботи на перевірку „___” ___________ р.

Перевірено роботу „___” ___________ р.

Київ - 2007

ЗМІСТ

Завдання 1. Розподіл ресурсів по підприємствах

Знайти оптимальний розподіл ресурсів по роках (m = 4), якщо функціональна модель задачі має вигляд:

α = 0,58;

β = 0,87;

а = 0,77;

в = 0,64;

К = 34

Розв’язок:

Модель задачі:

Розрахункові формули:

Основне функціональне співвідношення: , причому на останньому - .

Оптимізаційна таблиця заповнюється поступово після відповідних розрахунків:

Оптимізаційна таблиця

Максимальне значення W₁

Оптимальне управління

Розв’язок почнемо з останнього кроку:

, при .

Оптимальні значення W₄, заносимо в оптимізаційну таблицю.

Третій крок:

, при .

Значення W₃, заносимо в оптимізаційну таблицю.

Другий крок:

, при .

Оптимальні значення W₂, заносимо в оптимізаційну таблицю.

Перший крок:

, при .

Оптимальні значення W₁, заносимо в оптимізаційну таблицю.

Процес умовної оптимізації закінчено. Починаємо процес безумовної оптимізації.

На першому кроці відомо значення К₁, тобто К₁ = К = 34, тому:

Для визначення оптимального управління проводимо розрахунки від початку до кінця.

Отже:

З оптимізаційної таблиці: , тобто, на першому кроці всі кошти потрібно виділити першому підприємству.

Кількість коштів К₂, яка переходить на другий крок:

Згідно з умовним оптимальним управлінням: , тобто кошти, які перейшли другий крок потрібно вкласти в друге підприємство.

Кошти, що переходять на третій крок:

Згідно з умовним оптимальним управлінням: , тобто кошти К₃ вкладаються в друге підприємство.

Кількість коштів К₃, яка переходить на четвертий крок:

Згідно з умовним оптимальним управлінням: , тобто кошти К₄ вкладаються в третє підприємство.

Знайдемо залишок коштів:

Функціональна модель розв’язку задачі:

Завдання 2. Рішення гри методом ітерацій

Знайти оптимальні стратегії гравців та ціну гри, що задана матрицею:

Р1 Р2	№1	№2	№3	№4	№5
№1	а₁₁	а₁₂	а₁₃	а₁₄	а₁₅
№2	а₂₁	а₂₂	а₂₃	а₂₄	а₂₅
№3	а₃₁	а₃₂	а₃₃	а₃₄	а₃₅
№4	а₄₁	а₄₂	а₄₃	а₄₄	а₄₅

а₁₁ = 6

а₁₂ = 8

а₁₃ = 7

а₁₄ = 3

а₁₅ = 0

а₂₁ = -7

а₂₂ = -8

а₂₃ = 4

а₂₄ = 20

а₂₅ = 16

а₃₁ = 18

а₃₂ = 14

а₃₃ = 22

а₃₄ = 36

а₃₅ = 19

а₄₁ = 29

а₄₂ = -7

а₄₃ = 6

а₄₄ = 16

а₄₅ = 26

Розв’язок:

Маємо платіжну матрицю:

Р1 Р2	1	2	3	4	5
1	6	8	7	3	0
2	-7	-8	4	20	16
3	18	14	22	36	19
4	29	-7	6	16	26

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

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

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

Р1 Р2	1	2	3	4	5	1	2	2	2	2	2	2	2	2	2	2	2	2
1	6	8	7	3	0	6	14	22	30	38	46	54	62	70	78	86	94	102
2	-7	-8	4	20	16	-7	-15	-23	-31	-39	-47	-55	-63	-71	-79	-87	-95	-103
3	18	14	22	36	19	18	32*	46*	60*	74*	88*	102*	116*	130*	144*	158*	172*	186*
4	29	-7	6	16	26	29*	22	15	8	1	-6	-13	-20	-27	-34	-41	-48	-55
4	29	-7	6	16	26
3	47	7	28	52	45
3	65	21	50	88	64
3	83	35	72	124	83
3	101	51	94	160	101
3	119	65	116	196	120
3	148	58	122	212	146
3	177	51	128	228	172
3	224	58	156	280	217
3	289	79	206	368	281
3	372	114	278	492	364
3	473	165	372	652	465
3	592	230	488	848	585

Так, імовірність використання гравцем №1 своїх стратегій буде дорівнювати:

Гравцю №1 використовувати свої першу та другу стратегії невигідно, тому активні будуть тільки третя та четверта стратегії.

Аналогічно для гравця №2:

Гравцю №2 вигідно використовувати лише 2-гу стратегію.

Нижня і верхня ціна гри буде дорівнювати:

Завдання 3. Рішення задачі сітьового планування та управління

В таблиці наведена інформація про роботи та їх тривалість. Виконати розрахунок сітьового графіку.

Робота	Тривалість t_ij робіт
1-2	10
1-3	5
1-4	4
2-3	8
2-5	8
3-5	8
3-6	2
3-7	0
4-7	5
5-6	3
5-8	7
5-9	3
6-7	6
6-9	6
7-9	4
7-10	7
8-11	1
9-10	9
9-11	3
10-11	7

Розв’язок:

Спочатку побудуємо сітьовий графік робіт та пронумеруємо їх:

Розрахуємо ранні терміни подій по відповідним формулам. Значення раннього початку (РП) та раннього закінчення (РЗ) записуємо на графіку над стрілками. Одержимо:

Отже, довжина критичного шляху Т_кр = 55. для визначення критичного шляху треба розрахувати пізні терміни подій, тобто пізній початок (ПП) та пізнє закінчення (ПЗ). Їх знаходимо по відповідним формулам і записуємо під стрілками на цьому ж сітьовому графіку.

Критичний шлях визначає ті роботи сітьового графіку, для яких рівні РП та ПП, або РЗ та ПЗ. Отже, критичний шлях Z_кр:1 – 2 – 3 – 5 – 6 – 7 – 9 – 10 – 11 (відмічений жирними лініями).

Розрахуємо повні резерви часу:

R_1-2 = 0 – 0 = 10 – 10 = 0

R_1-3 = 13 – 0 = 18 – 5 = 13

R_1-4 = 26 – 0 = 30 – 4 = 26

R_2-3 = 10 – 10 = 18 – 18 = 0

R_2-5 = 18 – 10 = 26 – 18 = 8

R_3-5 = 18 – 18 = 26 – 26 = 0

R_3-6 = 27 – 18 = 29 – 29 = 0

R_3-7 = 35 – 18 = 35 – 18 = 17

R_4-7 = 30 – 4 = 35 – 9 = 26

R_5-6 = 26 – 26 = 29 – 29 = 0

R_5-8 = 47 – 26 = 54 – 33 = 22

R_5-9 = 36 – 26 = 39 – 29 = 10

R_6-7 = 29 – 29 = 35 – 35 = 0

R_6-9 = 33 – 29 = 39 – 35 = 4

R_7-9 = 35 – 35 = 39 – 39 = 0

R_7-10 = 41 – 35 = 48 – 42 = 6

R_8-11 = 54 – 33 = 55 – 34 = 21

R_9-10 = 39 – 39 = 48 – 48 = 0

R_9-11 = 52 – 39 = 55 – 42 = 13

R_10-11 = 48 – 48 = 55 – 55 = 0

На критичному шляху роботи не мають резерви часу.

Завдання 4. Марківський процес з неперервним часом (неперервний харківський ланцюг)

Знайти імовірність станів в даному режимі при t → ∞ для процесу загибелі та розмноження, граф якого задано у вигляді (записати систему лінійних алгебраїчних рівнянь з нормуючою умовою):

Розв’язок:

Запишемо систему рівнянь Колмогорова:

Для граничних (стаціонарних) ймовірностей, якщо l₁₂ = 1, l₂₁ = 2, l₂₃ = 1, l₃₂ = 2, одержимо систему лінійних алгебраїчних рівнянь:

Розв’язок цієї системи:

Р₁ = 0,25, Р₂ = 0,5, Р₃ = 0,25.

Це середній відносний час, в якому перебуває система в даному стані. Отже, в граниному режимі система S в середньому:

25 % часу перебуває в стані S₁;

50 % часу перебуває в стані S₂;

25 % часу перебуває в стані S₃.

Використана література

В.М. Дякон, Л.Є.Ковальов „Математичне програмування” Навчальний посібник. Київ – 2004 р.
Дослідження операцій: Навч. посіб. / М.Г. Медведєв, О.В. Колодінська. – К.: Вид-во Європ. ун-ту, 2004. – 158 с. – Бібліогр.: с. 154.
Зайченко Ю.П. Дослідження операцій. - К.: Слово. - 2001. - 688 с.
Михалевич В.С., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.:Наука. - 208с.

Дослідження операцій та методи оптимізації 📙 Контрольная → 🆔 28966