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

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

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

 

 

 

 

 

 

 

 

 

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

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

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

 

Варіант №9

 

 

 

 

 

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

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

 

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

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

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

 

 

 

 

Київ - 2007 

ЗМІСТ

 

 

 

 

 

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

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

 

 

 

 

 

α = 0,58;

β = 0,87;

а = 0,77;

в = 0,64;

К = 34

Розв’язок:

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

 

 

 

 

 

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

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

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

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

Максимальне значення W1	Оптимальне управління

 

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

   , при .

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

Третій крок:

, при .

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

Другий крок:

, при .

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

Перший крок:

, при .

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

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

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

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

Отже:

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

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

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

Р1 Р2	№1	№2	№3	№4	№5
№1	а11	а12	а13	а14	а15
№2	а21	а22	а23	а24	а25
№3	а31	а32	а33	а34	а35
№4	а41	а42	а43	а44	а45

 

 

а₁₁ = 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. Рішення задачі сітьового планування та управління

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

Робота	Тривалість tij робіт
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

 

Розв’язок:

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

 

 

 

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