Надійність АСО і У
Лабораторна робота № 3
Рішення задачі оптимального резервування системи методом динамічного програмування
Варіант № 1
Студент
Корнєєва М.С.
(Шіфр605596)
Група
АУЗ-562
Введення
Мета роботи
Вивчення впливу структурного резервування на показники надійності системи, освоєння методу динамічного програмування для вирішення задачі оптимального резервування
Завдання на роботу
1. Освоїти методи розв'язання задачі оптимального резервування технічної системи.
2. Для заданого варіанту побудувати оптимальну схему системи при навантаженому резервування її елементів. Для цього вирішити завдання методами невизначених множників Лагранжа і динамічного програмування.
3. Скласти звіт по роботі, що містить всі етапи виконання завдання
Завдання
Система керування містить блок обробки і блок видачі команд. Величини ймовірностей безвідмовної роботи і приведених витрат на ці блоки P 1 (t i) = 0,5, P 2 (t i) = 0,7, з 1 = 3 ум.од., з 2 = 1 усл.ед
Знайти оптимальний навантажений резерв для кожного блоку за умови, що ймовірність безвідмовної роботи системи повинна бути не менше 0,98 при мінімальних витратах.
Хід виконання роботи
Теоретичні положення.
Велика група завдань оптимізації пов'язана з визначенням числа резервних елементів (підсистем) з урахуванням обмежуючих факторів (витрат). Такі завдання можуть бути двох видів.
Задачі оптимального резервування першого виду полягають у визначенні необхідної кількості резервних елементів, які забезпечують задане значення показника надійності системи при мінімальних витратах.
Завдання другого виду - визначення необхідної кількості резервних елементів, які забезпечують максимум значення показника надійності системи при величині витрат, що не перевищує задану.
Для вирішення перерахованих завдань використовують метод невизначених множників Лагранжа, а також методи: градієнтний, перебору і динамічного програмування.
Метод невизначених множників Лагранжа дозволяє аналітично отримати наближене рішення задачі. Похибка результатів обумовлена тим, що даний метод оперує дійсними числами, в той час як кількість резервних елементів системи виражається як ціле число. Округлення результатів до цілих чисел викликає зсув екстремуму в просторі параметрів, внаслідок чого виникає похибка рішення. Крім того метод невизначених множників Лагранжа дає рішення в явному вигляді тільки при найпростіших моделях надійності.
Метод динамічного програмування є модифікацією методу простого перебору. У цьому методі для скорочення числа варіантів при переборі вводиться поняття домінуюча послідовність - підмножина варіантів, перспективних з точки зору пошуку оптимального рішення.
Стосовно до завдання оптимального резервування будемо вважати, що один склад системи, що представляє собою деяку комбінацію розташування резервних елементів, домінує над іншим, якщо для одного і того ж рівня надійності забезпечення цього складу пов'язане з мінімальними витратами. Всі неоптимальні рішення, що не входять до складу домінуючою послідовності в силу того, що вони володіють більшою величиною витрат при тій же надійності чи меншою надійністю при тих же витратах, ніж члени домінуючою послідовності, виключаються з розгляду.
Рішення задачі методом невизначених множників Лагранжа.
Нехай система складається з підсистем і кожна підсистема має резервів. Імовірність відмови системи .
Витрати на резервну підсистему .
Оптимальний резерв i-ої підсистеми має вигляд:
,
де
Занесемо вихідні дані і проміжні розрахунки в таблицю
Лабораторна робота № 3
Рішення задачі оптимального резервування системи методом динамічного програмування
Варіант № 1
Студент
Корнєєва М.С.
(Шіфр605596)
Група
АУЗ-562
Введення
Мета роботи
Вивчення впливу структурного резервування на показники надійності системи, освоєння методу динамічного програмування для вирішення задачі оптимального резервування
Завдання на роботу
1. Освоїти методи розв'язання задачі оптимального резервування технічної системи.
2. Для заданого варіанту побудувати оптимальну схему системи при навантаженому резервування її елементів. Для цього вирішити завдання методами невизначених множників Лагранжа і динамічного програмування.
3. Скласти звіт по роботі, що містить всі етапи виконання завдання
Завдання
Система керування містить блок обробки і блок видачі команд. Величини ймовірностей безвідмовної роботи і приведених витрат на ці блоки P 1 (t i) = 0,5, P 2 (t i) = 0,7, з 1 = 3 ум.од., з 2 = 1 усл.ед
Знайти оптимальний навантажений резерв для кожного блоку за умови, що ймовірність безвідмовної роботи системи повинна бути не менше 0,98 при мінімальних витратах.
Хід виконання роботи
Теоретичні положення.
Велика група завдань оптимізації пов'язана з визначенням числа резервних елементів (підсистем) з урахуванням обмежуючих факторів (витрат). Такі завдання можуть бути двох видів.
Задачі оптимального резервування першого виду полягають у визначенні необхідної кількості резервних елементів, які забезпечують задане значення показника надійності системи при мінімальних витратах.
Завдання другого виду - визначення необхідної кількості резервних елементів, які забезпечують максимум значення показника надійності системи при величині витрат, що не перевищує задану.
Для вирішення перерахованих завдань використовують метод невизначених множників Лагранжа, а також методи: градієнтний, перебору і динамічного програмування.
Метод невизначених множників Лагранжа дозволяє аналітично отримати наближене рішення задачі. Похибка результатів обумовлена тим, що даний метод оперує дійсними числами, в той час як кількість резервних елементів системи виражається як ціле число. Округлення результатів до цілих чисел викликає зсув екстремуму в просторі параметрів, внаслідок чого виникає похибка рішення. Крім того метод невизначених множників Лагранжа дає рішення в явному вигляді тільки при найпростіших моделях надійності.
Метод динамічного програмування є модифікацією методу простого перебору. У цьому методі для скорочення числа варіантів при переборі вводиться поняття домінуюча послідовність - підмножина варіантів, перспективних з точки зору пошуку оптимального рішення.
Стосовно до завдання оптимального резервування будемо вважати, що один склад системи, що представляє собою деяку комбінацію розташування резервних елементів, домінує над іншим, якщо для одного і того ж рівня надійності забезпечення цього складу пов'язане з мінімальними витратами. Всі неоптимальні рішення, що не входять до складу домінуючою послідовності в силу того, що вони володіють більшою величиною витрат при тій же надійності чи меншою надійністю при тих же витратах, ніж члени домінуючою послідовності, виключаються з розгляду.
Рішення задачі методом невизначених множників Лагранжа.
Нехай система складається з
Витрати на резервну підсистему
Оптимальний резерв i-ої підсистеми має вигляд:
де
Занесемо вихідні дані і проміжні розрахунки в таблицю
i | 1 | 2 |
3 | 1 | |
0,5 | 0,3 | |
-0,6932 | -1,204 | |
-4,3281 | -0,8306 |
При цьому
Визначаємо оптимальну кількість елементів кожної підсистеми:
Округляючи результати до найближчих цілих значень, отримаємо наближений оптимальний склад системи:
При такому складі системи ймовірність відмови становить Q = 0.018, що менше заданої величини Q зад = 0,02, отже умова виконується
Рішення задачі методом динамічного програмування
Приймемо, що для блоку № 1 максимальне число резервних блоків дорівнює 6, а для блоку № 2 максимальне число резервних блоків дорівнює 5. Для побудова домінуючою послідовності побудуємо таблицю
Число К1 резервних блоків до блоку 1 | |||||||||||||||||||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | |||||||||||||||||||
1 | 3,0000 | 2 | 6,0000 | 3 | 9,0000 | 4 | 12,0000 | 5 | 15,0000 | 6 | 18,0000 | 7 | 21,0000 | ||||||||||||
0,5000 | 0,2500 | 0,1250 | 0,0625 | 0,0313 | 0,0156 | 0,0078 | |||||||||||||||||||
Число К2 резервних блоків до блоку 2 | 0 | 8 | 1,0000 | 14 | 4,0000 | 15 | 7,0000 | 16 | 10,0000 | 17 | 13,0000 | 18 | 16,0000 | 19 | 19,0000 | 20 | 22,0000 | ||||||||
0,3000 | 0,8000 | 0,5500 | 0,4250 | 0,3625 | 0,3313 | 0,3156 | 0,3078 | ||||||||||||||||||
1 | 9 | 2,0000 | 21 | 5,0000 | 22 | 8,0000 | 23 | 11,0000 | 24 | 14,0000 | 25 | 17,0000 | 25 | 20,0000 | 27 | 23,0000 | |||||||||
0,0900 | 0,5900 | 0,3400 | 0,2150 | 0,1525 | 0,1213 | 0,1056 | 0,0978 | ||||||||||||||||||
2 | 10 | 3,0000 | 28 | 6,0000 | 29 | 9,0000 | 30 | 12,0000 | 31 | 15,0000 | 32 | 18,0000 | 33 | 21,0000 | 34 | 24,0000 | |||||||||
0,0270 | 0,5270 | 0,2770 | 0,1520 | 0,0895 | 0,0583 | 0,0426 | 0,0348 | ||||||||||||||||||
3 | 11 | 4,0000 | 35 | 7,0000 | 36 | 10,0000 | 37 | 13,0000 | 38 | 16,0000 | 39 | 19,0000 | 40 | 22,0000 | 41 | 25,0000 | |||||||||
0,0081 | 0,5081 | 0,2581 | 0,1331 | 0,0706 | 0,0394 | 0,0237 | 0,0159 | ||||||||||||||||||
4 | 12 | 5,0000 | 42 | 8,0000 | 43 | 11,0000 | 44 | 14,0000 | 45 | 17,0000 | 46 | 20,0000 | 47 | 23,0000 | 48 | 26,0000 | |||||||||
0,0024 | 0,6170 | 0,3670 | 0,2420 | 0,1795 | 0,1483 | 0,1326 | 0,1248 | ||||||||||||||||||
5 | 13 | 6,0000 | 49 | 9,0000 | 50 | 12,0000 | 51 | 15,0000 | 52 | 18,0000 | 53 | 21,0000 | 54 | 24,0000 | 55 | 27,0000 | |||||||||
0,0007 | 0,5540 | 0,3040 | 0,1790 | 0,1165 | 0,0853 | 0,0696 | 0,0618 |
У клітинах 14-55 записуємо значення ймовірностей відмов і витрат для послідовно з'єднаних блоків 1 і 2.
У таблиці темно-сірим кольором позначені клітини-варіанти реалізації пристрою, що підходять під умову відмовостійкості. З них вибираємо варіант з найменшими витратами
Висновки
Вирішивши задачу методом невизначених множників Лагранжа і методом динамічного програмування прийшов до наступного оптимальному за витратами і відмовостійкості складу системи, з урахуванням введених навантажених блоків: .
Графічно:
SHAPE \ * MERGEFORMAT
У таблиці темно-сірим кольором позначені клітини-варіанти реалізації пристрою, що підходять під умову відмовостійкості. З них вибираємо варіант з найменшими витратами
Висновки
Вирішивши задачу методом невизначених множників Лагранжа і методом динамічного програмування прийшов до наступного оптимальному за витратами і відмовостійкості складу системи, з урахуванням введених навантажених блоків:
Графічно:
SHAPE \ * MERGEFORMAT
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |