Московський Авіаційний Інститут
(Державний технічний університет)
Курсова робота
ПО КУРСУ: «Контроль і ДІАГНОСТИКА СИСТЕМ»
ВАРІАНТ № 7
Москва 2009 р .
Зміст
Завдання
Теоретична частина
Метод гілок і меж
Метод найшвидшого спуску
Практична частина
Завдання № 1
Завдання № 2
Завдання
Визначення послідовності проведення перевірок з використанням методу гілок і меж, і кількості повторних вимірювань методом найшвидшого спуску при обмеженні на час перевірок.
Дано:
1. Граф вихідного безлічі модулів і таблиці тривалості операцій.
SHAPE \ * MERGEFORMAT
2. Характеристики параметрів, допуски і похибка вимірювань.
Ідея цього методу полягає в наступному. Безліч W (S 0) всіх допустимих варіантів рішення σ розбивається на непересічні підмножини W (S k), які, у свою чергу, розбиваються на підмножини меншої потужності W (S l) до отримання підмножини W (S v), що складається з єдиного варіанта . Процес розбиття множини допустимих варіантів W (S 0) на їх непересічні підмножини називається розгалуженням варіантів, а одержана при цьому дерево - деревом рішень. Кожній вершині дерева розгалуження відповідає певний модуль з графа, а будь-який шлях по дереву визначає відповідний граф черговості. Безліч вершин описує певний варіант процесу.
Нехай Y (S k) - безліч вершин у графі черговості D, відповідних шляху від S 0 до S к в дереві Є. з кожної вершини S до виходить стільки гілок, скільки допустимих модулів (претендентів упорядкування) мається на підмножині Z \ Y (S k). Безліч допустимих на кожному кроці процесу розгалуження модулів утворює фронт упорядкування. Наочне уявлення про освіту фронту впорядкування дає перетворений у відповідності з формулою (1.1) граф G
F (z l) = max [f (z i) + t il] (1.1)
z i → z j
Очевидно, на першому кроці процесу побудови дерева Е фронт впорядкування утворюють вершини, які з'єднані з мажоранту однією дугою, на другому кроці до них додаються всі послідовники включеної в D вершини, до якої не входять дуги з інших вершин і т.д. На довільному кроці фронт впорядкування утворюють модулі, для яких Г 0 -1 z i = Ø.
Метод гілок і меж передбачає побудову дерева розгалуження варіантів Е і фактично являє собою процедуру послідовного аналізу варіантів, доповнену прогнозуванням такого напрямку пошуку, в якому з найбільшою ймовірністю знаходиться оптимальне рішення. Ідея прогнозування полягає в оцінці нижніх меж мінімізіруемой цільової функції для розгалужується підмножин W (S k). На кожному кроці розгалуження триває з вершини, що має мінімальну оцінку. Завдання зводиться до відшукання на дереві кінцевої вершини, відповідної оптимальному допустимому рішенням зі значенням цільової функції, меншим або рівним оцінками висячих вершин дерева Є.
Як показує практика застосування методу гілок і меж, ефективність його значно залежить від способу подання рішення у вигляді дерева варіантів і методу оцінки нижньої межі цільової функції.
Для мінімізації цей метод може бути застосований такий спосіб.
На основі вихідної інформації, заданої графом G, побудуємо
τ i + t ij, якщо (i, j) належить U
b ij = (1.2)
t ij + τ i, якщо (i, j) належить U
d ij = (1.3)
- ∞, якщо (i, j) не належить U
Введемо наступні поняття:
а) найбільш ранній час початку модуля
Т н (Z к) = max {Т н (Z i) + b ik}, Т н (Z 0) = 0 (1.4)
0 <i ≤ k
б) критичний шлях - найдовший шлях, що веде від мажоранту графа до мінорант, причому за довжину будь-якого колії приймається сума тривалостей τ i для всіх модулів і всіх затримок t ij , Що входять в цей шлях.
Позначимо H = {L ij} - множина всіх незалежних шляхів на графі (шляхів, що відрізняються один від одного хоча б однією дугою), що ведуть від вершини z i до z j, і H '= {L k} є H - множина всіх незалежних шляхів, що ведуть від вершини z k до мінорант. Тоді такий шлях представляє собою частковий підграф G L = (Z L, U L), довжина якого дорівнює:
T (L) = Σ τ k + Σ t kl (1.5)
k: z k є Z L (K, l) є U L
Довжина критичного шляху може бути обчислена з рекурентної формули:
Т кр = t (L 0 *) = max {t (L 0)} = τ 0 + max {t 0, j + T (L j *)} (1.6)
L 0 єH '
j: z j єГ z 0
Так як довжина критичного шляху характеризує найменшу тривалість процесу контролю, то вираз (6) може послужити основою для оцінки нижніх меж мінімізіруемого функціоналу. Необхідними умовами для досягнення цієї межі є:
Στ k ≤ t (L 0 *) і (VR) [t k ≤ T k (z k)] (1.7)
k: z k є Z
де t k - час завершення к-го модуля, визначається з отриманого рішення D.
На підставі наведених виразів процес перетворення графа G = (Z, Г) в граф черговості G = (Z, Г D) може бути інтерпретований таким чином. Визначимо для кожної вершини S k є S дерева розгалуження варіантів Е безліч
N (S k) = {z i │ z i є Z, Г -1 z i є Y (S k)} (1.8)
яке визначає фронт упорядкування. Згідно апріорної частини впорядкованості модулів, яка виражається відображенням Г, черговий модуль при покроковому побудові графа D може бути вибраний тільки з │ N (S k) │, що виражає потужність фронту упорядкування.
На основі (6) можна записати вираз для оцінки нижніх меж для довільного підмножини варіантів W (S k) в наступному вигляді:
Т оц (S k) = t * (S k) + max {t (L i *) + max [0, Т н (z i) - t * (S k)]} (1.9)
i: z j є N (S k)
де t * (S k) = max {t i │ i: z i є Y (S k)}
На кожному кроці для подальшого розгалуження вибирається вершина S k *, для якої справедлива рівність
Т оц (S k *) = min {Т оц (S k) │ S k є S *} (1.10)
Де S * з S - підмножина вершин, з яких можна продовжувати розгалуження, тобто
S * = {S i │ S i: │ ΔS i │ <│ N (S i) │} (1.11)
Обрана вершина S k є S * в підсумку розгалуження отримує │ N (S k) │ послідовників, що визначають розбиття множини можливих варіантів W (S k) на │ N (S k) │ непересічних підмножин.
При досягненні в процесі розгалуження підмножини W (S ν), що складається з єдиного варіанта D (S ν) = (Y [S ν), Г D], Y (S ν) = Z, останній буде оптимальним якщо
t * (S ν) ≤ min {Т оц (S k) │ S k є S *}. (1.12)
якщо (12) не виконується, то пошук оптимального рішення триває з вершини, що має найменшу з оцінок Т оц (S k *).
Розглянемо завдання:
Потрібно забезпечити не менше, ніж задану достовірність результатів контролю за умови, що сумарно час вимірювання контрольованих параметрів не перевищить деякої величини.
Введемо наступні позначення:
Р - достовірність результатів контролю об'єкта (ймовірність отримання правильних результатів, Р 0 - задане значення);
Т - сумарний час вимірювання всіх параметрів (Т0 - задане значення);
m - кількість контрольованих параметрів;
n i - кількість повторних вимірювань i-го параметра;
t i - час одного виміру i-го параметра;
p i (n i) - достовірність результатів контролю i-го параметра при n i - кратному вимірі.
Тоді завдання формулюється: знайти
(2.1)
за умови, що виконується обмеження
(2.2)
контрольовані параметри незалежні.
Р (N) - достовірність результатів контролю на N-му етапі процесу рішення;
Т (N) - сумарний час вимірювання всіх параметрів на N-му етапі процесу рішення.
Суть методу полягає в наступному. Береться початковий склад контрольованих параметрів, які визначають працездатність об'єкта, і для них обчислюються значення достовірності контролю Р (1) і сумарний час вимірювання цих параметрів Т (1) при одноразових вимірюваннях (індекс " 1 " означає відсутність повторення вимірів)
(2.3)
(2.4)
обчислюємо
ψ i (n i) = (p i (n i) - p i (n i - 1)) / (p i (n i - 1) t i) (2.5)
Потім на першому етапі процесу рішення послідовно для всіх контрольованих параметрів (i = 1, 2, ..., m) обчислюються значення Р i (2) (імовірність одержання правильного результату по всіх контрольованих параметрах за умови, що i-й параметр вимірюється дворазово ) і Т i (2) (сумарний час вимірювання всіх параметрів за умови, що i-й параметр вимірюється дворазово)
P i (2) = p 1 (1) p 2 (2) ... p i-1 (1) pi (2) p i +1 (1) ... p m (1) (2.6)
T i (2) = t 1 + t 2 + ... + T i-1 + 2t i + t i +1 + ... + T m (2.7)
Далі для всіх контрольованих параметрів на першому етапі обчислюються значення відносного збільшення вірогідності результатів, в залежності від збільшення сумарного часу вимірювання.
ψ i (2) = ψ i (2) P (1) (2.8)
Серед величин ψ i (2) потрібно знайти найбільшу. Проте неважко помітити, що найбільшою величиною ψ i (2) відповідає і найбільша величина ψ i (2), так як вони відрізняються між собою лише на постійний множник Р (1). Нехай, наприклад, найбільшою виявилася величина ψ s (2). Це означає, що на першому етапі процесу виконання завдання повторно слід виміряти s-й параметр.
Таким чином, після першого етапу процесу рішення достовірність результатів контролю об'єкта, який контролюється за m параметрами, буде характеризуватися значенням
P (2) = (p s (2) / p s (1)) P (1) (2.9)
а сумарний час вимірювання всіх m параметрів значенням
T (2) = T (1) + t s (2.10)
На другому кроці вихідними значеннями вже є Р (2) і Т (2). Тепер для всіх параметрів аналогічним чином мають бути обчислені значення P i (3) і T i (3) за умови, що до загальної кількості вимірів, яке стало рівне (m +1) (m одноразових плюс одне повторне вимірювання), додано ще одне вимір. Потім обчислюються значення ψ i (3). Нехай найбільшою з цих величин виявилося ψ r (3). Це означає, що на другому етапі процесу рішення повторно слід виміряти r-й параметр. Проте найбільшою може виявитися величина ψ s (3) з тим же індексом, що і на першому етапі процесу, тобто може виявитися, що слід зробити ще одне повторне вимірювання s-го параметра, ні виробляючи, жодне повторне вимірювання інших параметрів.
Подібний процес вирішення завдання продовжується до тих пір поки:
Т (N) ≤ T 0 <T (N +1) (2.11)
Методом найшвидшого спуску може бути визначена кількість повторних вимірювань контрольованих параметрів, оптимальне за критерієм максимуму достовірності результатів контролю при обмеженні на сумарний час вимірювань контрольованих параметрів, а також за критерієм мінімуму сумарного часу вимірювання при обмеженні на достовірність результатів контролю.
Практична частина
SHAPE \ * MERGEFORMAT
Рис 1.1. Вихідний граф.
Табліца1.1.
Табліца1.2
Знайти: послідовність проведення перевірок методом гілок кордонів.
Рішення:
1. Знайдемо найбільш ранній час початку модуля Z k:
Т н (Z к) = max {Т н (Z i) + b ik}, Т н (Z 0) = 0
Т зв (Z 0) = 0
Т н (Z 1) = 0
Т н (Z 2) = 0
Т н (Z 3) = 2 +15 = 17
Т н (Z 4) = 4 +12 = 16 або Т н (Z 4) = 2 +15 +5 +7 = 29 тоді max Т н (Z 4) = 29
Т зв (Z 5) = 4 +3 = 7
Т н (Z 6) = 4 +3 +8 = 15 або Т н (Z 6) = 2 +15 +5 +7 +3 = 32 або Т н (Z 6) = 4 +12 +3 = 19 то max Т н (Z 6) = 32
2. Знайдемо довжину критичного шляху T (L):
T (L * (Z 0)) = 0 +2 +15 +5 +7 +3 = 32
T (L * (Z 1)) = 0 +2 +15 +5 +7 +3 = 32
T (L * (Z 2)) = 0 +4 +12 +3 = 19
T (L * (Z 3)) = 0 +5 +7 +3 = 15
T (L * (Z 4)) = 0 +3 = 3
T (L * (Z 5)) = 0 +8 = 8
T (L * (Z 6)) = 0
Отримані дані зведемо в таблицю
Таблиця 1.3
3. Складемо дерево перевірок:
Рис. 1.2 - Дерево перевірок
4. Розрахуємо t * (S k) і отримані значення занесемо в таблицю 1.4:
t * (S 0) = 0
t * (S 1) = 2
t * (S 2) = 4
t * (S 3) = 2 +15 +5 = 22
t * (S 4) = 2 +4 = 6
t * (S 8) = 2 +5 +15 = 22
t * (S 9) = 2 +4 +8 +3 = 17
t * (S 15) = 2 +15 +5 +7 +3 = 32
t * (S 16) = 2 +15 +5 +8 = 30
t * (S 17) = 2 +4 +3 +8 +5 = 22
t * (S 26) = 2 +4 +3 +8 +5 +7 +3 = 32
5. Розрахуємо оцінку нижньої межі для безлічі W (S k) і отримані значення занесемо в таблицю 1.4.
T оц (S 0) = 0 + max {(19,32) + max (0, (0,0) -0)} = 32 (Державний технічний університет)
Курсова робота
ПО КУРСУ: «Контроль і ДІАГНОСТИКА СИСТЕМ»
ВАРІАНТ № 7
Москва
Зміст
Завдання
Теоретична частина
Метод гілок і меж
Метод найшвидшого спуску
Практична частина
Завдання № 1
Завдання № 2
Завдання
Визначення послідовності проведення перевірок з використанням методу гілок і меж, і кількості повторних вимірювань методом найшвидшого спуску при обмеженні на час перевірок.
Дано:
1. Граф вихідного безлічі модулів і таблиці тривалості операцій.
SHAPE \ * MERGEFORMAT
z 0 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
z 6 |
| № вершини | Z 1 | Z 2 | Z 3 | Z 4 | Z 5 |
| Тривалість, τ i | 2 | 4 | 5 | 3 | 8 |
| Дуги | 1-3 | 2-4 | 2-5 | 3-4 |
| Тривалість, t ij | 15 | 12 | 3 | 7 |
2. Характеристики параметрів, допуски і похибка вимірювань.
| № параметра | 1 | 2 | 3 | 4 | 5 |
| σ изм / σ ПАР | 0.1 | 0.3 | 0.5 | 0.2 | 0.4 |
| t i | 20 | 30 | 15 | 50 | 5 |
Теоретична частина
Метод гілок і меж
Найбільш перспективним способом вирішення оптимізаційних задач контролю є метод гілок і меж.Ідея цього методу полягає в наступному. Безліч W (S 0) всіх допустимих варіантів рішення σ розбивається на непересічні підмножини W (S k), які, у свою чергу, розбиваються на підмножини меншої потужності W (S l) до отримання підмножини W (S v), що складається з єдиного варіанта . Процес розбиття множини допустимих варіантів W (S 0) на їх непересічні підмножини називається розгалуженням варіантів, а одержана при цьому дерево - деревом рішень. Кожній вершині дерева розгалуження відповідає певний модуль з графа, а будь-який шлях по дереву визначає відповідний граф черговості. Безліч вершин описує певний варіант процесу.
Нехай Y (S k) - безліч вершин у графі черговості D, відповідних шляху від S 0 до S к в дереві Є. з кожної вершини S до виходить стільки гілок, скільки допустимих модулів (претендентів упорядкування) мається на підмножині Z \ Y (S k). Безліч допустимих на кожному кроці процесу розгалуження модулів утворює фронт упорядкування. Наочне уявлення про освіту фронту впорядкування дає перетворений у відповідності з формулою (1.1) граф G
F (z l) = max [f (z i) + t il] (1.1)
z i → z j
Очевидно, на першому кроці процесу побудови дерева Е фронт впорядкування утворюють вершини, які з'єднані з мажоранту однією дугою, на другому кроці до них додаються всі послідовники включеної в D вершини, до якої не входять дуги з інших вершин і т.д. На довільному кроці фронт впорядкування утворюють модулі, для яких Г 0 -1 z i = Ø.
Метод гілок і меж передбачає побудову дерева розгалуження варіантів Е і фактично являє собою процедуру послідовного аналізу варіантів, доповнену прогнозуванням такого напрямку пошуку, в якому з найбільшою ймовірністю знаходиться оптимальне рішення. Ідея прогнозування полягає в оцінці нижніх меж мінімізіруемой цільової функції для розгалужується підмножин W (S k). На кожному кроці розгалуження триває з вершини, що має мінімальну оцінку. Завдання зводиться до відшукання на дереві кінцевої вершини, відповідної оптимальному допустимому рішенням зі значенням цільової функції, меншим або рівним оцінками висячих вершин дерева Є.
Як показує практика застосування методу гілок і меж, ефективність його значно залежить від способу подання рішення у вигляді дерева варіантів і методу оцінки нижньої межі цільової функції.
Для мінімізації цей метод може бути застосований такий спосіб.
На основі вихідної інформації, заданої графом G, побудуємо
τ i + t ij, якщо (i, j) належить U
b ij = (1.2)
t ij + τ i, якщо (i, j) належить U
d ij = (1.3)
- ∞, якщо (i, j) не належить U
Введемо наступні поняття:
а) найбільш ранній час початку модуля
Т н (Z к) = max {Т н (Z i) + b ik}, Т н (Z 0) = 0 (1.4)
0 <i ≤ k
б) критичний шлях - найдовший шлях, що веде від мажоранту графа до мінорант, причому за довжину будь-якого колії приймається сума тривалостей τ i для всіх модулів і всіх затримок t ij , Що входять в цей шлях.
Позначимо H = {L ij} - множина всіх незалежних шляхів на графі (шляхів, що відрізняються один від одного хоча б однією дугою), що ведуть від вершини z i до z j, і H '= {L k} є H - множина всіх незалежних шляхів, що ведуть від вершини z k до мінорант. Тоді такий шлях представляє собою частковий підграф G L = (Z L, U L), довжина якого дорівнює:
T (L) = Σ τ k + Σ t kl (1.5)
k: z k є Z L (K, l) є U L
Довжина критичного шляху може бути обчислена з рекурентної формули:
Т кр = t (L 0 *) = max {t (L 0)} = τ 0 + max {t 0, j + T (L j *)} (1.6)
L 0 єH '
j: z j єГ z 0
Так як довжина критичного шляху характеризує найменшу тривалість процесу контролю, то вираз (6) може послужити основою для оцінки нижніх меж мінімізіруемого функціоналу. Необхідними умовами для досягнення цієї межі є:
Στ k ≤ t (L 0 *) і (VR) [t k ≤ T k (z k)] (1.7)
k: z k є Z
де t k - час завершення к-го модуля, визначається з отриманого рішення D.
На підставі наведених виразів процес перетворення графа G = (Z, Г) в граф черговості G = (Z, Г D) може бути інтерпретований таким чином. Визначимо для кожної вершини S k є S дерева розгалуження варіантів Е безліч
N (S k) = {z i │ z i є Z, Г -1 z i є Y (S k)} (1.8)
яке визначає фронт упорядкування. Згідно апріорної частини впорядкованості модулів, яка виражається відображенням Г, черговий модуль при покроковому побудові графа D може бути вибраний тільки з │ N (S k) │, що виражає потужність фронту упорядкування.
На основі (6) можна записати вираз для оцінки нижніх меж для довільного підмножини варіантів W (S k) в наступному вигляді:
Т оц (S k) = t * (S k) + max {t (L i *) + max [0, Т н (z i) - t * (S k)]} (1.9)
i: z j є N (S k)
де t * (S k) = max {t i │ i: z i є Y (S k)}
На кожному кроці для подальшого розгалуження вибирається вершина S k *, для якої справедлива рівність
Т оц (S k *) = min {Т оц (S k) │ S k є S *} (1.10)
Де S * з S - підмножина вершин, з яких можна продовжувати розгалуження, тобто
S * = {S i │ S i: │ ΔS i │ <│ N (S i) │} (1.11)
Обрана вершина S k є S * в підсумку розгалуження отримує │ N (S k) │ послідовників, що визначають розбиття множини можливих варіантів W (S k) на │ N (S k) │ непересічних підмножин.
При досягненні в процесі розгалуження підмножини W (S ν), що складається з єдиного варіанта D (S ν) = (Y [S ν), Г D], Y (S ν) = Z, останній буде оптимальним якщо
t * (S ν) ≤ min {Т оц (S k) │ S k є S *}. (1.12)
якщо (12) не виконується, то пошук оптимального рішення триває з вершини, що має найменшу з оцінок Т оц (S k *).
Метод найшвидшого спуску
На автоматизований контроль об'єктів відводиться певний час, тим часом при одноразових вимірюваннях вибраної кількості контрольованих параметрів цей час повністю не використовується, тобто залишається деякий надлишок часу. Цю надмірність часу можна використовувати з метою підвищення достовірності результатів автоматизованого контролю складних об'єктів застосуванням багаторазових (повторних) вимірювань контрольованих параметрів. Таким чином, виникає задача оптимального використання тимчасової надмірності або, що те ж саме, при контролі сукупності параметрів виникає задача визначення оптимальної кількості повторних вимірювань, що забезпечує максимальну достовірність результатів контролю.Розглянемо завдання:
Потрібно забезпечити не менше, ніж задану достовірність результатів контролю за умови, що сумарно час вимірювання контрольованих параметрів не перевищить деякої величини.
Введемо наступні позначення:
Р - достовірність результатів контролю об'єкта (ймовірність отримання правильних результатів, Р 0 - задане значення);
Т - сумарний час вимірювання всіх параметрів (Т0 - задане значення);
m - кількість контрольованих параметрів;
n i - кількість повторних вимірювань i-го параметра;
t i - час одного виміру i-го параметра;
p i (n i) - достовірність результатів контролю i-го параметра при n i - кратному вимірі.
Тоді завдання формулюється: знайти
(2.1)
за умови, що виконується обмеження
(2.2)
контрольовані параметри незалежні.
Р (N) - достовірність результатів контролю на N-му етапі процесу рішення;
Т (N) - сумарний час вимірювання всіх параметрів на N-му етапі процесу рішення.
Суть методу полягає в наступному. Береться початковий склад контрольованих параметрів, які визначають працездатність об'єкта, і для них обчислюються значення достовірності контролю Р (1) і сумарний час вимірювання цих параметрів Т (1) при одноразових вимірюваннях (індекс "
(2.3)
(2.4)
обчислюємо
ψ i (n i) = (p i (n i) - p i (n i - 1)) / (p i (n i - 1) t i) (2.5)
Потім на першому етапі процесу рішення послідовно для всіх контрольованих параметрів (i = 1, 2, ..., m) обчислюються значення Р i (2) (імовірність одержання правильного результату по всіх контрольованих параметрах за умови, що i-й параметр вимірюється дворазово ) і Т i (2) (сумарний час вимірювання всіх параметрів за умови, що i-й параметр вимірюється дворазово)
P i (2) = p 1 (1) p 2 (2) ... p i-1 (1) pi (2) p i +1 (1) ... p m (1) (2.6)
T i (2) = t 1 + t 2 + ... + T i-1 + 2t i + t i +1 + ... + T m (2.7)
Далі для всіх контрольованих параметрів на першому етапі обчислюються значення відносного збільшення вірогідності результатів, в залежності від збільшення сумарного часу вимірювання.
ψ i (2) = ψ i (2) P (1) (2.8)
Серед величин ψ i (2) потрібно знайти найбільшу. Проте неважко помітити, що найбільшою величиною ψ i (2) відповідає і найбільша величина ψ i (2), так як вони відрізняються між собою лише на постійний множник Р (1). Нехай, наприклад, найбільшою виявилася величина ψ s (2). Це означає, що на першому етапі процесу виконання завдання повторно слід виміряти s-й параметр.
Таким чином, після першого етапу процесу рішення достовірність результатів контролю об'єкта, який контролюється за m параметрами, буде характеризуватися значенням
P (2) = (p s (2) / p s (1)) P (1) (2.9)
а сумарний час вимірювання всіх m параметрів значенням
T (2) = T (1) + t s (2.10)
На другому кроці вихідними значеннями вже є Р (2) і Т (2). Тепер для всіх параметрів аналогічним чином мають бути обчислені значення P i (3) і T i (3) за умови, що до загальної кількості вимірів, яке стало рівне (m +1) (m одноразових плюс одне повторне вимірювання), додано ще одне вимір. Потім обчислюються значення ψ i (3). Нехай найбільшою з цих величин виявилося ψ r (3). Це означає, що на другому етапі процесу рішення повторно слід виміряти r-й параметр. Проте найбільшою може виявитися величина ψ s (3) з тим же індексом, що і на першому етапі процесу, тобто може виявитися, що слід зробити ще одне повторне вимірювання s-го параметра, ні виробляючи, жодне повторне вимірювання інших параметрів.
Подібний процес вирішення завдання продовжується до тих пір поки:
Т (N) ≤ T 0 <T (N +1) (2.11)
Методом найшвидшого спуску може бути визначена кількість повторних вимірювань контрольованих параметрів, оптимальне за критерієм максимуму достовірності результатів контролю при обмеженні на сумарний час вимірювань контрольованих параметрів, а також за критерієм мінімуму сумарного часу вимірювання при обмеженні на достовірність результатів контролю.
Практична частина
Завдання № 1
Дано: граф вихідного безлічі модулів і таблиці тривалості операцій:SHAPE \ * MERGEFORMAT
z 0 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
z 6 |
Рис 1.1. Вихідний граф.
Табліца1.1.
| № вершини | Z 1 | Z 2 | Z 3 | Z 4 | Z 5 |
| Тривалість, τ i | 2 | 4 | 5 | 3 | 8 |
| Дуги | 1-3 | 2-4 | 2-5 | 3-4 |
| Тривалість, t ij | 15 | 12 | 3 | 7 |
Рішення:
1. Знайдемо найбільш ранній час початку модуля Z k:
Т н (Z к) = max {Т н (Z i) + b ik}, Т н (Z 0) = 0
Т зв (Z 0) = 0
Т н (Z 1) = 0
Т н (Z 2) = 0
Т н (Z 3) = 2 +15 = 17
Т н (Z 4) = 4 +12 = 16 або Т н (Z 4) = 2 +15 +5 +7 = 29 тоді max Т н (Z 4) = 29
Т зв (Z 5) = 4 +3 = 7
Т н (Z 6) = 4 +3 +8 = 15 або Т н (Z 6) = 2 +15 +5 +7 +3 = 32 або Т н (Z 6) = 4 +12 +3 = 19 то max Т н (Z 6) = 32
2. Знайдемо довжину критичного шляху T (L):
T (L * (Z 0)) = 0 +2 +15 +5 +7 +3 = 32
T (L * (Z 1)) = 0 +2 +15 +5 +7 +3 = 32
T (L * (Z 2)) = 0 +4 +12 +3 = 19
T (L * (Z 3)) = 0 +5 +7 +3 = 15
T (L * (Z 4)) = 0 +3 = 3
T (L * (Z 5)) = 0 +8 = 8
T (L * (Z 6)) = 0
Отримані дані зведемо в таблицю
Таблиця 1.3
| Z | τ i | Т н (Z i) | T (L * (Z i)) | U | t ij |
| Z 0 | 0 | 0 | 32 | 0,1 | 0 |
| Z 1 | 2 | 0 | 32 | 0,2 | 0 |
| Z 2 | 4 | 0 | 19 | 1,3 | 15 |
| Z 3 | 5 | 17 | 15 | 2,4 | 12 |
| Z 4 | 3 | 29 | 3 | 2,5 | 3 |
| Z 5 | 8 | 7 | 8 | 3,4 | 7 |
| Z 6 | 0 | 32 | 0 | 4,6 | 0 |
| 5,6 | 0 |
Рис. 1.2 - Дерево перевірок
4. Розрахуємо t * (S k) і отримані значення занесемо в таблицю 1.4:
t * (S 0) = 0
t * (S 1) = 2
t * (S 2) = 4
t * (S 3) = 2 +15 +5 = 22
t * (S 4) = 2 +4 = 6
t * (S 8) = 2 +5 +15 = 22
t * (S 9) = 2 +4 +8 +3 = 17
t * (S 15) = 2 +15 +5 +7 +3 = 32
t * (S 16) = 2 +15 +5 +8 = 30
t * (S 17) = 2 +4 +3 +8 +5 = 22
t * (S 26) = 2 +4 +3 +8 +5 +7 +3 = 32
5. Розрахуємо оцінку нижньої межі для безлічі W (S k) і отримані значення занесемо в таблицю 1.4.
T оц (S 1) = 2 + max {(19,15) + max (0, (0,17-2)} = 32
T оц (S 2) = 4 + max {(32,7) + max (0, (0,7) -5)} = 36
T оц (S 3) = 22 + max {19 + max (0,0-22)} = 41
T оц (S 4) = 6 + max {(15,8) + max (0, (17,7) -6)} = 32
T оц (S 8) = 22 + max {(3,8) + max (0, (29,7) -22)} = 32
T оц (S 9) = 17 + max {15 + max (0,17-17)} = 32
T оц (S 15) = 32 + max {8 + max (0,7-32)} = 40
T оц (S 16) = 30 + max {3 + max (0,29-30)} = 33
T оц (S 17) = 22 + max {3 + max (0,29-22)} = 32
T оц (S 26) = 32 + max {0 + max (0,32-32)} = 32
Таблиця 1.4.
| S | Z i / i = S k | N (S k) | Y (S k) | t * (S k) | T оц (S k) |
| S 0 | Z 0 | Z 1 Z 2 | Z 0 | 0 | 32 |
| S 1 | Z 1 | Z 2 Z 3 | Z 0 Z 1 | 2 | 32 |
| S 2 | Z 2 | Z 5 Z 1 | Z 0 Z 2 | 4 | 36 |
| S 3 | Z 3 | Z 2 | Z 0 Z 1 Z 3 | 22 | 41 |
| S 4 | Z 2 | Z 5 Z 3 | Z 0 Z 1 Z 2 | 6 | 32 |
| S 8 | Z 3 | Z 4 Z 5 | Z 0 Z 1 Z 2 Z 3 | 22 | 32 |
| S 9 | Z 5 | Z 3 | Z 0 Z 1 Z 2 Z 5 | 17 | 32 |
| S 15 | Z 3 | Z 5 | Z 0 Z 1 Z 2 Z 3 Z 4 | 32 | 40 |
| S 16 | Z 5 | Z 4 | Z 0 Z 1 Z 2 Z 3 Z 5 | 30 | 33 |
| S 17 | Z 5 | Z 4 | Z 0 Z 1 Z 2 Z 5 Z 3 | 22 | 32 |
| S 26 | Z 1 | Z 6 | Z 0 Z 1 Z 2 Z 5 Z 3 Z 4 | 32 | 32 |
Складемо дерево оптимального рішення (рис 1.3)
S 4 |
32 |
Z0 |
S 1 |
S 2 |
S 0 |
32 |
36 |
32 |
Z1 |
Z2 |
Z2 |
Z3 |
S 3 |
41 |
S 8 |
32 |
15 |
40 |
17 |
32 |
Z3 |
Z4 |
Z3 |
Z4 |
Z5 |
Z5 |
16 |
33 |
26 |
32 |
S 9 |
32 |
Ріс1.3 - Дерево оптимального рішення
Таким чином отримали, що оптимальному процесу контролю відповідає послідовність перевірок { Z 0 Z 1 Z 2 Z 5 Z 3 Z 4}, при цьому загальний час контролю становить Т опт = 32 од.
Завдання № 2
Дано: Характеристики параметрів, допуски і похибка вимірювань.
Таблиця 2.1
| № параметра | 1 | 2 | 3 | 4 | 5 |
| σ изм / σ ПАР | 0.5 | 0.3 | 0.2 | 0.1 | 0.4 |
| t i | 3 | 5 | 15 | 20 | 50 |
- Сумарний час вимірювання контрольованих параметрів не повинно перевищувати 5 хв.
Рішення:
1. Для кожного параметра визначимо значення p i (n i):
Таблиця 2.2
| n | σ изм / σ ПАР | ||||
| 0.5 | 0.3 | 0.2 | 0.1 | 0.4 | |
| 1 | 0.99110 | 0.99634 | 0.99784 | 0.99893 | 0.99419 |
| 2 | 0.99533 | 0.99775 | 0.99859 | 0.99930 | 0.99669 |
| 3 | 0.99657 | 0.99821 | 0.99886 | 0.99945 | 0.99748 |
| 4 | 0.99714 | 0.99846 | 0.99901 | 0.99955 | 0.99785 |
| 5 | 0.99756 | 0.99868 | 0.99915 | 0.99960 | 0.99816 |
| 6 | 0.99780 | 0.99879 | 0.99923 | 0.99963 | 0.99833 |
| 7 | 0.99801 | 0.99890 | 0.99931 | 0.99967 | 0.99849 |
| 8 | 0.99818 | 0.99895 | 0.99933 | 0.99970 | 0.999859 |
| 9 | 0.99828 | 0.99901 | 0.99937 | 0.99971 | 0.99867 |
| 10 | 0.99839 | 0.99909 | 0.99942 | 0.99973 | 0.99876 |
| 11 | 0.99848 | 0.99914 | 0.99945 | 0.99974 | 0.99882 |
| 12 | 0.99854 | 0.99918 | 0.99948 | 0.99975 | 0.99887 |
2. Для кожного значення параметра обчислюються значення y i (n i) вибирається найбільше значення:
3.
y 1 (n i)
y 1 (2) = (0.99533-0.99110) / 0.99110 * 3 = 0.001422661
y 1 (3) = 0.000415272
y 1 (4) = 0.000190653
y 1 (5) = 0.000140401
y 1 (6) = 0.000718243
y 1 (7) = 0.000070154
y 1 (8) = 0.000056779
y 1 (9) = 0.000033394
y 1 (10) = 0.000036729
y 1 (11) = 0.000030048
y 1 (12) = 0.00002003
y 2 (n i)
y 2 (2) = 0.000283035
y 2 (3) = 0.000092207
y 2 (4) = 0.000050089
y 2 (5) = 0.000044067
y 2 (6) = 0.000022029
y 2 (7) = 0.000022026
y 2 (8) = 0.000010011
y 2 (9) = 0.000012012
y 2 (10) = 0.000016015
y 2 (11) = 0.000010009
y 2 (12) = 0
y 3 (n i)
y 3 (2) = 0.000050108
y 3 (3) = 0.000018025
y 3 (4) = 0.000010011
y 3 (5) = 0
y 4 (n i)
y 4 (2) = 0.000018519
y 4 (3) = 0
y 5 (n i)
y 5 (2) = 0.000050292
y 5 (3) = 0.000015852
y 5 (4) = 0
Отримані результати зведемо в таблицю:
Таблиця 2.3
| n | Y 1 (n) | N | Y 2 (n) | N | Y 3 (n) | N | Y 4 (n) | N | Y 5 (n) | N |
| 1 | - | - | - | - | - | - | - | - | - | - |
| 2 | 0.001422661 | 1 | 0.000283035 | 16 | 0.000050108 | 10 | 0.000018519 | 20 | 0.000050292 | 9 |
| 3 | 0.000415272 | 3 | 0.000092207 | 6 | 0.000018025 | 21 | - | - | 0.000015852 | 23 |
| 4 | 0.000190653 | 4 | 0.000050089 | 11 | 0.000010011 | 26 | - | - | - | - |
| 5 | 0.000140401 | 5 | 0.000044067 | 12 | - | - | - | - | - | - |
| 6 | 0.000718243 | 2 | 0.000022029 | 17 | - | - | - | - | - | - |
| 7 | 0.000070154 | 7 | 0.000022026 | 18 | - | - | - | - | - | - |
| 8 | 0.000056779 | 8 | 0.000010011 | 25 | - | - | - | - | - | - |
| 9 | 0.000033394 | 14 | 0.000012012 | 24 | - | - | - | - | - | - |
| 10 | 0.000036729 | 13 | 0.000016015 | 22 | - | - | - | - | - | - |
| 11 | 0.000030048 | 15 | 0.000010009 | 27 | - | - | - | - | - | - |
| 12 | 0.00002003 | 19 | - | - | - | - | - | - | - | - |
Таблиця 2.4
| N | n 1 | n 2 | n 3 | n 4 | n 5 |
| 1 | 2 | 1 | 1 | 1 | 1 |
| 2 | 3 | 1 | 1 | 1 | 1 |
| 3 | 4 | 1 | 1 | 1 | 1 |
| 4 | 5 | 1 | 1 | 1 | 1 |
| 5 | 6 | 1 | 1 | 1 | 1 |
| 6 | 6 | 2 | 1 | 1 | 1 |
| 7 | 7 | 2 | 1 | 1 | 1 |
| 8 | 8 | 2 | 1 | 1 | 1 |
| 9 | 8 | 2 | 1 | 1 | 2 |
| 10 | 8 | 2 | 2 | 1 | 2 |
| 11 | 8 | 3 | 2 | 1 | 2 |
| 12 | 8 | 4 | 2 | 1 | 2 |
| 13 | 9 | 4 | 2 | 1 | 2 |
| 14 | 10 | 4 | 2 | 1 | 2 |
| 15 | 11 | 4 | 2 | 1 | 2 |
| 16 | 11 | 5 | 2 | 1 | 2 |
| 17 | 11 | 6 | 2 | 1 | 2 |
| 18 | 11 | 7 | 2 | 1 | 2 |
| 19 | 12 | 7 | 2 | 1 | 2 |
| 20 | 12 | 7 | 2 | 2 | 2 |
| 21 | 12 | 7 | 3 | 2 | 2 |
| 22 | 12 | 8 | 3 | 2 | 2 |
| 23 | 12 | 8 | 3 | 2 | 3 |
| 24 | 12 | 9 | 3 | 2 | 3 |
| 25 | 12 | 10 | 3 | 2 | 3 |
| 26 | 12 | 10 | 4 | 2 | 3 |
| 27 | 12 | 11 | 4 | 2 | 3 |
Т = 3 + 5 + 15 + 20 + 50 = 93 с = 1 хв 33 с
Т (1) = 93 + 3 = 96 с = 1 хв 36 с
Т (2) = 96 + 3 = 99 с = 1 хв 39 с
Т (3) = 99 + 3 = 102 з = 1 хв 42 с
Т (4) = 102 + 3 = 105 с = 1 хв 45 с
Т (5) = 105 + 3 = 108 с = 1 хв 48 с
Т (6) = 108 + 5 = 113 с = 1 хв 53 с
Т (7) = 113 + 3 = 116 с = 1 хв 56 з
Т (8) = 116 + 3 = 119 с = 1 хв 59 с
Т (9) = 119 + 50 = 169 з = 2 хв 49 с
Т (10) = 169 + 15 = 184 с = 3 хв 4 з
Т (11) = 184 + 5 = 189 с = 3 хв 9 з
Т (12) = 189 + 5 = 194 с = 3 хв 14 с
Т (13) = 194 + 3 = 197 с = 3 хв 17 з
Т (14) = 197 + 3 = 200 з = 3 хв 20 с
Т (15) = 200 + 3 = 203 с = 3 хв 23 з
Т (16) = 203 + 5 = 208 с = 3 хв 28 с
Т (17) = 208 + 5 = 213 с = 3 хв 33 с
Т (18) = 213 + 5 = 218 с = 3 хв 38 с
Т (19) = 218 + 3 = 221 с = 3 хв 41 с
Т (20) = 221 + 20 = 241 з = 4 хв 1 з
Т (21) = 241 + 15 = 256 с = 4 хв 16 з
Т (22) = 256 + 5 = 261 с = 4 хв 21 з
Т (23) = 261 + 50 = 311 с = 5 хв 11 з
Розрахунок Р (N)
Р = р 1 р 2 р 3 р 4 р 5 = 0.97857
Р (1) = (р 1 (2) / р 1 (1)) Р = 0.98275
Р (2) = (р 1 (3) / р 1 (2)) Р (1) = 0.98398
Р (3) = (р 1 (4) / р 1 (3)) Р (2) = 0.98454
Р (4) = (р 1 (5) / р 1 (4)) Р (3) = 0.98495
Р (5) = (р 1 (6) / р 1 (5)) Р (4) = 0.98519
Р (6) = (р 2 (2) / р 2 (1)) Р (5) = 0.98658
Р (7) = (р 1 (7) / р 1 (6)) Р (6) = 0.98679
Р (8) = (р 1 (8) / р 1 (7)) Р (7) = 0.98696
Р (9) = (р 5 (2) / р 5 (1)) Р (8) = 0.98944
Р (10) = (р 3 (2) / р 3 (1)) Р (9) = 0.99018
Р (11) = (р 2 (3) / р 2 (2)) Р (10) = 0.99064
Р (12) = (р 2 (4) / р 2 (3)) Р (11) = 0.99089
Р (13) = (р 1 (9) / р 1 (8)) Р (12) = 0.99099
Р (14) = (р 1 (10) / р 1 (9)) Р (13) = 0.99110
Р (15) = (р 1 (11) / р 1 (10)) Р (14) = 0.99119
Р (16) = (р 2 (5) / р 2 (4)) Р (15) = 0.99141
Р (17) = (р 2 (6) / р 2 (5)) Р (16) = 0.99152
Р (18) = (р 2 (7) / р 2 (6)) Р (17) = 0.99163
Р (19) = (р 1 (12) / р 1 (11)) Р (18) = 0.99169
Р (20) = (р 4 (2) / р 4 (1)) Р (19) = 0.99206
Р (21) = (р 3 (3) / р 3 (2)) Р (20) = 0.99233
Р (22) = (р 2 (8) / р 2 (7)) Р (21) = 0.99238
Отримані результати занесемо в таблицю:
Таблиця 2.5
| N | n 1 | n 2 | n 3 | n 4 | n 5 | Р (N) | Т (N) |
| 1 | 2 | 1 | 1 | 1 | 1 | 0.98275 | 1 хв 36 с |
| 2 | 3 | 1 | 1 | 1 | 1 | 0.98398 | 1 хв 39 с |
| 3 | 4 | 1 | 1 | 1 | 1 | 0.98454 | 1 хв 42 с |
| 4 | 5 | 1 | 1 | 1 | 1 | 0.98495 | 1 хв 45 с |
| 5 | 6 | 1 | 1 | 1 | 1 | 0.98519 | 1 хв 48 с |
| 6 | 6 | 2 | 1 | 1 | 1 | 0.98658 | 1 хв 53 с |
| 7 | 7 | 2 | 1 | 1 | 1 | 0.98679 | 1 хв 56 с |
| 8 | 8 | 2 | 1 | 1 | 1 | 0.98696 | 1 хв 59 с |
| 9 | 8 | 2 | 1 | 1 | 2 | 0.98944 | 2 хв 49 с |
| 10 | 8 | 2 | 2 | 1 | 2 | 0.99018 | 3 хв 4 с |
| 11 | 8 | 3 | 2 | 1 | 2 | 0.99064 | 3 хв 9 з |
| 12 | 8 | 4 | 2 | 1 | 2 | 0.99089 | 3 хв 14 с |
| 13 | 9 | 4 | 2 | 1 | 2 | 0.99099 | 3 хв 17 с |
| 14 | 10 | 4 | 2 | 1 | 2 | 0.99110 | 3 хв 20 с |
| 15 | 11 | 4 | 2 | 1 | 2 | 0.99119 | 3 хв 23 з |
| 16 | 11 | 5 | 2 | 1 | 2 | 0.99141 | 3 хв 28 с |
| 17 | 11 | 6 | 2 | 1 | 2 | 0.99152 | 3 хв 33 с |
| 18 | 11 | 7 | 2 | 1 | 2 | 0.99163 | 3 хв 38 с |
| 19 | 12 | 7 | 2 | 1 | 2 | 0.99169 | 3 хв 41 с |
| 20 | 12 | 7 | 2 | 2 | 2 | 0.99206 | 4 хв 1 с |
| 21 | 12 | 7 | 3 | 2 | 2 | 0.99233 | 4 хв 16 з |
| 22 | 12 | 8 | 3 | 2 | 2 | 0.99238 | 4 хв 21 з |
| 23 | 12 | 8 | 3 | 2 | 3 | 0.99317 | 5 хв 11 з |
| Далі проводити розрахунок недоцільно, тому що рішення задачі знайдено | |||||||
Програмна частина
Завдання № 1
рис.3.1. Інтерфейс програми
У дане вікно вводяться вихідні дані. При натисканні кнопки «Розрахунок» починаємо розрахунок. У результаті отримуємо наступне вікно.
рис. 3.2. Результат розрахунку
У верхній таблиці «Початкова таблиця» наведені значення найбільш ранніх часів початку модулів Z i і довжини критичних шляхів.
У нижній таблиці «Таблиця результатів» наведені результати розрахунку.
Побудуємо граф за результатами таблиці «Таблиця результатів», і перевіримо: чи збіглися результати з ручним розрахунком.
SHAPE \ * MERGEFORMAT
Z 0 |
Z 1 |
Z 2 |
Z 3 |
Z 5 |
Z 1 |
Z 3 |
Z 5 |
Z 4 |
Z 5 |
Z 3 |
Z 4 |
S 0 |
S 1 |
S 2 |
S 3 |
S 4 |
S 5 |
S 6 |
S 7 |
S 8 |
S 9 |
S 10 |
S 11 |
32 |
32 |
32 |
32 |
32 |
32 |
32 |
35 |
43 |
35 |
40 |
33 |
рис.3.3. Оптимальне рішення
Таким чином, ми бачимо, що оптимальне рішення, як і у випадку ручного розрахунку, є послідовність перевірок {Z 0, Z 2, Z 1, Z 5, Z 3, Z 4}, при цьому загальний час контролю становить Т опт = 32 од.
Завдання № 2
Рішення, отримане програмним шляхом збігається з ручним розрахунком, значить завдання виконане вірно, тобто оптимальне рішення задачі - n 1 = 12, n 2 = 8, n 3 = 3, n 4 = 2, n 5 = 2, де Т = 261с = 4хв 21 з, при цьому максимальна достовірність результатів дорівнює 0.992.
Висновок
1. Найбільш перспективним способом вирішення оптимізаційних задач контролю є метод гілок і меж, так як рішення, наприклад, простим перебором варіантів призводить до величезних витрат часу на пошук оптимального рішення.
2. Методом найшвидшого спуску може бути визначена кількість повторних вимірювань контрольованих параметрів, оптимальне за критерієм максимуму достовірності результатів контролю при обмеженні на сумарний час вимірювання контрольованих параметрів, а також за критерієм мінімуму сумарного часу вимірі при обмеженні на достовірність результатів контролю.
3. Рішення, отримані програмним шляхом і розраховані вручну, збігаються як для першої, так і для другої задачі.
Список літератури
1. Селезньов А.В. та ін «Проектування АСК бортового обладнання ЛА», Машинобудування,
2. Загрутдінов Г.М. «Достоверность автоматизированного контроля», КХГ,1980 г.
Цей текст може містити помилки.
Програмування, комп'ютери, інформатика і кібернетика | Курсова
Схожі роботи:
Векторні аналізатори ланцюгів Контроль і діагностика компонентів цифрових мереж і систем телекомунікацій
Вбудований контроль і діагностика цифрових пристроїв Методи вище
Векторні аналізатори ланцюгів Контроль і діагностика компонентів циф
Вбудований контроль і діагностика цифрових пристроїв Методи підвищення контролепригодности цифрових
Клініка діагностика і лікування відкритих артеріальних проток Класифікація клініка та діагностика
Використання корпоративних інформаційних систем систем класу MRPIIERP для управління виробництвом
Моделі систем масового обслуговування Класифікація систем массовог
Спеціальний контроль авіаційної безпеки і технологія роботи в аеропорту Пулково-2 Спеціальний контроль
Фінансовий контроль 2 Контроль як