ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ

ЗМІСТ

1 ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ.. 4

1.1 Геометрична інтерпретація задач ДП.. 4

1.2 Приклад багатоетапної операції 5

2 ОСНОВНІ ПОЛОЖЕННЯ ПОЕТАПНОГО ОПТИМАЛЬНОГО управліННЯ.. 5

2.1 Загальна схема алгоритму динамічного планування n-крокової операції 7

3 ЗАДАЧА ПРО НАЙКОРОТШИЙ ШЛЯХ.. 9

3.1 Схема алгоритму зворотньої прогонки (АЗП) по дугах, що виходять. 11

3.2 Приклад застосування алгоритму АЗП по дугах, що виходять. 12

3.3 Завдання для самостійної роботи.. 14

3.4 Схема алгоритму прямої прогонки (АПП) по дугах, що входять. 16

3.5 Приклад застосування алгоритму АПП по дуга, що входять х.. 16

3.6. Завдання для самостійної роботи.. 18

3.7 Схема алгоритму зворотної прогонки (АЗП) по дугах, що входять. 19

3.8 Відмінності алгоритмів прямої і зворотної прогонок. 20

3.9 Контрольні завдання. 21

4. ЗАДАЧА ПРО ОПТИМАЛЬНЕ ВИКОРИСТАННЯ РЕСУРСУ.. 24

4.1 Змістовна інтерпретація задачі про оптимальне використання ресурсу.. 24

4.2 Побудова рекурентного співвідношення задачі 4.1.1. 24

4.3 Побудова рекурентного співвідношення задачі 4.1.2. 25

4.4 Схема АПП для ЗОВК.. 26

4.5 Приклад розв’язання ЗОВК.. 26

4.6 Завдання для самостійної роботи.. 31

4.7 Контрольні завдання. 32

5 ЗАДАЧА ПРО ВИКОРИСТАННЯ РОБОЧОЇ СИЛИ.. 35

5.1 Постановка задачі 35

5.2 Теоретичне обґрунтування алгоритму зворотньої прогонки для розв’язку задачі про найм робочої сили 36

5.3 Алгоритм ПП розв’язку задачі 37

5.4 Приклад розв’язання ЗВРС.. 38

5.5 Контрольні завдання. 40

6 ОСНОВНІ ЕЛЕМЕНТИ і ПРИНЦИПИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ.. 41

6.1 Адитивність цільової функції і етапи задачі 41

6.2 Принцип занурення. 41

6.3 Основне рекурентне співвідношення. 42

6.4 Стани.. 42

6.5 Умова марковості (відсутність післядії) 44

6.6 Принцип оптимальності Белмана.. 45

6.7 Загальна схема застосування алгоритму ДП.. 46

7 ЗАДАЧА управліННЯ ЗАПАСАМИ.. 47

7.1 Постановка задачі 47

7.2 Елементи динамічної моделі 49

7.2.1 Етапи. 49

7.2.2 Варіанти розв’язків. 49

7.2.3 Стани. 51

7.2.4 Основне рекурентне співвідношення. 51

7.3 Приклади розв’язання ЗУЗ. 53

7.4 Контрольні завдання. 57

8 ЗАДАЧА ПРО НАДІЙНІСТЬ.. 60

8.1 Змістовна постановка задачі 60

8.2 Математична модель задачі 60

8.3 Елементи динамічної моделі 61

8.4 Приклад розв’язання задачі 62

8.5 Контрольні завдання. 64

СПИСОК ЛІТЕРАТУРИ.. 68

1 ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ

Динамічне програмування (планування) (ДП) – розділ прикладної математики, що використовується при математичному аналізі багатокрокових процесів прийняття рішень. Багатокроковий процес прийняття рішень - діяльність, при якій приймаються послідовні рішення, спрямовані на досягнення певної мети. Багатокрокові процеси прийняття рішень зустрічаються у всіляких ситуаціях: у задачах управління запасами, при приготуванні обіду, при керуванні космічним кораблем. ДП можна розглядати як єдину теорію завдяки ряду ідей і процедур, що використовувються при математичному аналізі таких задач. [2].

Динамічне програмування широко застосовується при оптимальному плануванні управляючих процесів (під управляючими маються на увазі процеси, на хід яких ми можемо впливати). Планування таких процесів може бути інтерпретоване як багатокроковий процес прийняття рішень (і навпаки).

Розглянемо постановку загальної задачі оптимального управління [1]. Припустимо, що фізична система перебуває в деякому початковому стані і є управляємою. Завдяки здійсненню деякого управління зазначена система переходить із початкового стану в кінцевий стан . При цьому вартість (якість) кожного з реалізованих управлінь характеризується значенням функції . Завдання полягає в тому, щоб із множини можливих управлінь знайти таке управління , при якому функція набуває екстремального значення.

Геометрична інтерпретація задач ДП

Кожній траєкторії руху точки поставлено у відповідність значення деякої функції . Завдання полягає в знаходженні такої допустимої траєкторії , при… Така геометрична інтерпретація природна для деяких задач. До них відносяться… - визначення шляху прокладення дороги (трубопроводу);

Приклад багатоетапної операції

Нехай на початку i-го року j-е підприємство одержує у своє розпорядженняод. вартості. Завдання полягає у визначенні таких значень (тобто в… Сформулюємо поставлену задачу в термінах загальної задачі ДП.Під реалізацією… Критерієм оцінки якості обраного розподілу коштів (тобто реалізованих управлінь) узято сумарний прибуток за років, що…

Загальна схема алгоритму динамічного планування n-крокової операції

Етап 1. Планування кроку .

   

Етап . Планування кроку 1.

Рис. 6 Динамічне програмування вирішує задачу, розбиваючи її на підзадачі й поєднуючи… Обчислення на мережах характерні для ДП. Дослідження мережевих моделей дозволяє краще усвідомити специфіку (суть)…

ЗАДАЧА ПРО НАЙКОРОТШИЙ ШЛЯХ

Розглянемо ряд визначень. Спрямована мережа - це трійка , де - непорожня кінцева множина вершин (), -… Наявність дуги вказує на можливість прямого руху з вершинидо вершини . З того, що , не випливає, що . Тому ці дуги…

Схема алгоритму зворотньої прогонки (АЗП) по дугах, що виходять

1.Вважаємо, що .

2.Планування кроку .

2.1. Виділити всі можливі стани, які можуть бути на початку кроку , тобто визначити множину .

2.2. Для кожного знайти умовне оптимальне управління:

(мінімум шукаємо по дугах, що виходять).

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

3., якщо , то перейти до п. 4, інакше - перейти до п. 2.

4.Формування оптимального розв’язку. Для знаходження найкоротшого шляху пройти по мережі в напрямку, зворотньому до напрямку розрахунків, використовуючи знайдені умовні оптимальні розв’язки (вершини) .

Приклад застосування алгоритму АЗП по дугах, що виходять

  При застосуванні алгоритму зворотньої прогонки, першим планується крок 4 (останній крок). Вважаємо, що (довжина…

Завдання для самостійної роботи

       

Схема алгоритму прямої прогонки (АПП) по дугах, що входять

1.Вважаємо .

2.Планування кроку

2.1.Виділити всі можливі стани, які можуть мати місце наприкінці кроку , тобто визначити множину .

2.2.Для кожного знайти найкоротший шлях з вершини 1 у вершину

Запам'ятати , для якого досягається мінімум цього виразу (умовний оптимальний розв’язок).

3., якщо , те перейти до п. 4. Інакше - перейти до п. 2.

4.Формування оптимального розв’язку.

Приклад застосування алгоритму АПП по дуга, що входять х

Алгоритмом прямої прогонки розв’яжемо ЗЗНШ для мережі, що представлена на рис. 10.

Оскільки при розв’язанні задачі застосовується пряма прогонка, то першим будемо планувати крок 1. Вважаємо, що .

Планування кроку 1.

  ; ;

Планування кроку 2.

, – тобто, у вершину 5 найбільш вигідно можна потрапити з вершини 3. У таблиці ці розрахунки відображаються таким чином:

Завдання для самостійної роботи

1. За допомогою алгоритма прямої прогонки, знайти найкоротший шлях між вершинами 1 і 9 мережі, зображеної на рис. 14.

Рис. 14

Відповідь: найкоротший шлях 1—2—6—7—9, довжина шляху 10.

2. За допомогою алгоритма прямої прогонки, знайти найкоротший шлях між вершиною A й однієї з вершин останнього слою (вершинами G, H або I) наступної мережі (рис. 15).

 

Рис. 15

Відповідь: найкоротші шляхи: A—B—E—G; A—D—F—G; A—D—F—I, їх довжина 5.

Схема алгоритму зворотної прогонки (АЗП) по дугах, що входять

1.Покласти ; .

(- допоміжний масив. У ньому будемо зберігати поточну довжину найкоротшого шляху від всіх вершин не останнього слою. Початкове значення цієї довжини вважаємо рівним ).

2. Планування кроку

2.1Виділити всі можливі стани, які можуть мати місце наприкінці кроку : всі

2.2. Для кожного стану виконати наступне:

По кожній дузі (k,s), що входить у вершину знайти

2.3Вважаємо

3.j=j –1. Якщо j=0, то перейти до пункту 4, інакше – перейти до пункту 2.

4.Формування оптимального розв’язку.

 

Процес розв’язку ЗЗНШ АЗП по дугах, що входять, проілюстрований на рис. 16.

Рис. 16

У прямокутниках вказані значення, що послідовно принімалися величинами .

Відмінності алгоритмів прямої і зворотної прогонок

1) Потрібно знайти найкоротшу відстань між двома конкретними вершинами мережі. У цьому випадку вибір може бути довільним, тому що жоден з алгоритмів… 2) Потрібно знайти найкоротшу відстань між вершиною 1 і однією з вершин… .

Контрольні завдання

  Рис. 18

Змістовна інтерпретація задачі про оптимальне використання ресурсу

4.1.1 Нехай маємо деяке підприємство, що випускає n видів продуктів і використовує для цього один ресурс.

Нехай - об’єм виробництва продукту . При виробництві одиниць j-го продукту ресурс споживається в кількості , а прибуток становить одиниць. Об'єми випуску продукції обмежені величинами . Визначити ассортимент випуску продукції, при якому сумарний прибуток максимальний і витрачається не більше одиниць ресурсу.

Відзначимо, що класична задача про рюкзак (ранець) є частковим випадком ЗОВР.

4.1.2 На початку фінансового року керівництво фірми ухвалює рішення щодо модернізації n підприємств, на що виділяється одиниць вартості. Кожне підприємство подає на розгляд проекти модернізації , які характеризуються величинами необхідних інвестицій () і прибутками від них (). Нульові проекти відповідають рішенню не проводити модернізацію підприємств. Мета фірми полягає в одержанні максимального прибутку від інвестицій.

Побудова рекурентного співвідношення задачі 4.1.1

на першому кроці виробляється продукт 1, на другому – продукт 2 , …, на -му – продукт .

Побудова рекурентного співвідношення задачі 4.1.2

Задачу можна звести до багатокрокового процесу прийняття рішень, якщо припустити, що підприємства мають бути модернізовані одне за одним, тобто на… Нехай модернізовані підприємства від 1-го до -го включно і на це використані… Позначимо через максимальний прибуток, який можна отримати шляхом розподілу одиниць ресурсу для модернізації…

Схема АПП для ЗОВК

1.Вважаємо .

2.Планування кроку

2.1.Визначити всі можливі значення :

2.2.Для кожного визначити множину допустимих проектів (для яких виконується )

2.3.

3., якщо , те перейти до п. 4. Інакше - перейти до п. 2.

4.Формування оптимального розв’язку.

Приклад розв’язання ЗОВК

    Таблиця 4 Проект Підприємство 1 Підприємство 2 Підприємство 3 …

Планування кроку 1.

Спочатку відзначимо, що величина може бути інтерпретована, як кошти, спрямовані на модернізацію нульового (не існуючого підприємства), тобто… Нехай – для модернізації підприємства 1 виділені кошти в об'ємі 0 млн. одиниць… Таблиця заповнюється в такий спосіб: Крок       Можливі стани кроку…

Планування кроку 2.

    Відповідна частина таблиці має вигляд: …

Планування кроку 3.

  Повний процес розв’язку задачі наведений у табл. 5: Таблиця 5

Завдання для самостійної роботи

Задача 1.n=3, = 4 млн. одиниць вартості. Проект Підприємство 1 Підприємство 2 Підприємство 3 …   Відповідь: Підприємство … Максимальний прибуток складає 12 млн.

Контрольні завдання

Розв’язати задачу про оптимальне використання капіталовкладень. Кількість підприємств, сумарний об'єм капіталовкладень і відповідних величин і… Таблиця 6. Варіант Проект Підприємство …  

Постановка задачі

m1 m2 mn Рис. 19

Теоретичне обґрунтування алгоритму зворотньої прогонки для розв’язку задачі про найм робочої сили

Нехай - мінімальні витрати за періоди від -го до -го включно, при кількості робітників на початок-го періоду (в ()-му періоді) людей (рис. 20). І…  

Алгоритм ПП розв’язку задачі

Ø Етап відповідає -му періоду. Ø Кожному етапу ставиться у відповідність своя керована змінна . Ø На кожному етапі (крім етапу ) можливі стани (значення числа робітників ): ÷ .

Приклад розв’язання ЗВРС

Відповідно до теорії ДП у цій задачі діапазон можливих значень і – всі цілі від 4 до 7. Процес розв’язку цієї ЗВРС…

Контрольні завдання

Таблиця 8 Варі-ант Склад-ність Витрати по… 6 ОСНОВНІ ЕЛЕМЕНТИ і ПРИНЦИПИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ Розглянуті задачі ЗЗНШ, ЗОВР (ЗОВК) і ЗВРС мають особливості, характерні для всіх багатокрокових процесів прийняття…

Адитивність цільової функції і етапи задачі

де - це або скалярна величина, або вектор. Саме адитивність ЦФ задачі дозволяє розбити задачу на етапи. При цьому з кожним з етапів зв'язується тільки одна…

Принцип занурення

В ЗОВК було потрібно визначити таке використання інвестицій у підприємства від 1 до , при якому прибуток максимальний і витрачено одиниць ресурсу,… ; ;

Основне рекурентне співвідношення

Множина розв’язків оптимізаційних задач описується рекурентними співвідношеннями, аналогічними (1), (2), (4), (6) і (8).

Основне рекурентне співвідношення (ОРС) являє собою систему рівнянь, які зв'язують між собою розв’язки побудованої множини оптимізаційних задач.

У такій системі кожне рівняння відповідає одній вершині мережі. Ці рівняння зазвичай містять оператори типу мінімум або максимум праворуч від знака рівності, а величини й (або ) по обидві сторони від нього.

Синоніми ОРС: функціональне рівняння, основне функціональне рівняння Белмана.

Розв’язки множини оптимізаційних задач можна знайти за допомогою алгоритму зворотньої (або прямої) прогонки, що є впорядкованою процедурою розв’язання послідовності рекурентних рівнянь.

Стани

Стан системи є найбільш важливим поняттям у ДП.

Стан системи в деякий момент часу визначається, як множина значень змінних системи в цей момент часу [2].

Стани забезпечують зв'язок між послідовними етапами, тобто, перехід здійснюється зі стану в стан суміжних етапів. Стан містить у собі всю передісторію процесу, тобто він містить у собі всю інформацію, що необхідна для прийняття допустимого рішення на даному кроці без перевірки допустимості рішень, прийнятих на попередніх кроках.Таким чином стан повинен бути описаний зі ступенем детальності, що дозволяє оцінити поточні альтернативні розв’язки

АПП. У ЗОВР стан описуються парою (у підприємства від 1 до вкладено одиниць вартості) (рис. 21).

 

	Крок j
fj-1(yj-pj(0))
...
yj-pj(0)
	xj=0
fj-1(yj-pj(1))
... yj-pj(1)
yj-pj(1)
	xj=1 fj(yj)
fj-1(yj-pj(2)) ...	yj
	xj=2
yj-pj(2)
	xj=3
fj-1(yj-pj(3))
...
yj-pj(3)

Рис. 21.

 

У цій парі міститься інформація, достатня для прийняття поточного рішення, а саме: які проекти допустимі для -го підприємства. У даній ситуації не треба знати, як ми прийшли в стан , тобто, як були розподілені кошти в об'ємі на інвестування підприємств від 1 до .

 

 

АЗП. У ЗЗНШ вершини мережі є можливими станами системи. Дуги, що виходять із деякої вершини, представляють різні рішення, які можна приймати в даному стані.

У ЗЗНШ у номері вершини () міститься інформація, достатня для ухвалення поточного рішення, а саме: по яких дугах можна перейти до наступного (()-го) слою (рис. 22). У даній ситуації не треба знати, як ми підемо зі станів наступного шару, тобто, яким чином були досягнуті довжини найкоротших шляхів й .

 

	Крок j		Крок j+1			Крок n
		fj+1(k1)		...
fj(s)
		fj+1(k2)		...		...
		fj+1(k3)
				...

Рис. 22.

 

У моделях ДП стани зазвичай групуються в етапи (кроки, слої) і перехід здійснюється послідовно від етапу до етапу. Слід зазначити, що існує ряд задач, у яких мережа станів не має властивість слоїстості.

Із властивостей стану випливають наступні особливості моделей ДП.

6.5 Умова марковості (відсутність післядії)

Умові марковості повинна задовольняти будь-яка модель ДП.

Нехай - множина всіх можливих станів на етапі .

Кожному етапу ставиться у відповідність своя керована змінна таким чином, що кожному варіанту розв’язку відповідає певне значення керованої змінної. Значення цієї змінної фігурує у виразі ЦФ, наприклад:

ЗЗНШ: керована змінна – дуга ; складова ЦФ: .

ЗОВР: кожному варіанту розв’язку стану відповідає своє значення керованої змінної ; складова ЦФ: .

Нехай:

- множина всіх допустимих розв’язків, за умови, що на етапі система перебуває в стані (цій множині відповідає множина всіх можливих значень керованої змінної);

- перетворений стан, тобто, стан , у який система перейде, якщо в станібуде обрано варіант рішення .

Умова відсутності післядії:

Стан , в який переходить система, залежить тільки від стану і обраного рішення й не залежить від того, яким чином система прийшла в стан .

Принцип оптимальності Белмана

Мережевий варіант принципу оптимальності:підшлях найкоротшого шляху сам є найкоротшим шляхом. Цей варіант принципу оптимальності застосовується тільки до оптимізаційних… Принцип оптимальності Белмана. Оптимальна стратегія має таку властивість: якими б не були поточні стан і рішення,…

Загальна схема застосування алгоритму ДП

Сутність динамічного підходу полягає в заміні розв’язання -крокової задачі послідовністю задач: однокрокової, двокрокової і т.п.

Основні властивості задач, що необхідні для можливого застосування цього підходу.

1. Задача повинна допускати інтерпретацію як n-кроковий процес прийняття рішень.

2. Задача повинна бути визначена для будь-якої кількості кроків і мати структуру, що не залежить від їхньої кількості.

3. При розгляді -крокової задачі повинна бути задана деяка множина параметрів, що описують стан системи, від яких залежать оптимальні значення змінних. Причому ця множина не повинна змінюватися при збільшенні кількості кроків.

4. Вибір рішення (управління) на -му кроці не повинен впливати на попередні рішення, крім необхідного перерахунку змінних.

 

При застосуванні методу ДП необхідно виконати наступні дії.

1. Описати побудову оптимальних розв’язків (при цьому процес прийняття рішення повинен бути розбитий на ряд однотипних кроків або етапів, кожен з яких планується окремо, але з урахуванням результатів, отриманих на інших кроках).

2. Визначити етапи (їх кількість і суть планування на кожному етапі).

3. Для кожного етапу визначити множину можливих станів системи.

4. Для кожного стану визначити множину можливих варіантів рішень (значень керованих змінних).

5. Вивести ОРС.

6. Знайти розв’язки множини оптимізаційних задач (за допомогою алгоритму зворотньої або прямої прогонки).

7. Сформувати оптимальний розв’язок (рухаючись у напрямку, зворотньому до розрахунків).

7 ЗАДАЧА управліННЯ ЗАПАСАМИ

Задача управління запасами (ЗУЗ) – одна з найпоширеніших на практиці задач. Правильне визначення стратегії управління запасами дозволяє вивільнити значні оборотні кошти, заморожені у вигляді запасів, що в остаточному підсумку підвищує ефективність використання ресурсів. Елементами системи (задачі) управління запасами є :

1) Кількість періодів. Може бути:

- скінченним;

- нескінченним.

2) Попит на предмети постачання. Розрізняють попит:

- детермінований;

- випадковий;

- стаціонарний.

3) Спосіб поповнення запасів:

- миттєва поставка;

- затримка поставок на фіксований інтервал часу;

- затримка поставок на випадковий інтервал часу.

4) Спосіб споживання запасів:

- миттєве споживання;

- споживання, розтягнуте в часі.

5) Функції витрат – у сукупності вони визначають критерій ефективності прийнятої стратегії управління запасами. Вони можуть враховувати:

- витрати на зберігання,

- вартість поставок,

- витрати, пов'язані із замовленням кожної нової партії,

- витрати на штрафи. пов'язані з відсутністю (недостачею) необхідної продукції й т.п.

6) Обмеження на:

- максимальний об'єм (вага) запасів;

- максимальний об'єм (вага) поставок;

- максимальна вартість запасів;

- кількість поставок у заданому періоді;

- імовірність недостачі продукції.

Постановка задачі

Змістовна постановка задачі Нехай маємо систему постачання підприємства, що планує поставки продукції… 1) повністю задовольнити попит кожного періоду;

Елементи динамічної моделі

Сутність динамічного підходу полягає в заміні розв’язку -крокової задачі послідовністю задач: однокрокової, двокрокової і т.д. ЗУЗ має необхідні властивості задач, до яких можливо застосувати цей підхід: задача припускає інтерпретацію як n-кроковий процес прийняття рішень; задача визначена для будь-якої кількості кроків і має структуру, що не залежить від їхньої кількості.

Отже, для мінімізації z можна скористатися методом динамічного програмування.

Етапи

Задача природно розбивається на етапи: k-й етап (крок) відповідає k-му періоду. Стан системи на кожному кроці визначається величиною запасів у відповідному періоді планування. Для даної задачі простіше спочатку визначитися з можливими варіантами розв’язку, а вони вже дозволять визначити можливі стани системи.

Варіанти розв’язків

Твердження. Оптимальним розв’язком задачі (14)-(16) є одна із крайніх точок допустимої множини розв’язків, зумовлених обмеженнями (15)-(16). Доведення цього твердження витікає з того, що шукається мінімум суми опуклих… Визначимо координати крайніх точок.

Стани

Стан системи на кожному етапі будемо описувати за допомогою змінної . Значення визначаються значеннями змінних попередніх етапів. Якщо то

 

, ,…,...

 

 

 

На початку -ого періоду система перебуває в одному із станів , а наприкінці цього періоду – у стані .

Основне рекурентне співвідношення

Нехай – мінімальні витрати протягом перших періодів (з першого по k-й включно), за умови, що запас на кінець -ого періоду (на початок (+1)-ого)… (20) являє собою мінімальні витрати за періоди від 1-го до включно, за умови, що на кінець -ого періоду є одиниць…

Приклади розв’язання ЗУЗ

Задача 1. Визначити об'єми поставок у кожному з періодів, щоб повністю задовольнити попит кожного періоду і мінімізувати сумарні витрати на поставку і зберігання продукції в наступній ЗУЗ: кількість періодів планування: n = 6; рівні запасів: і ; попит у періодах: d₁ =15; d₂ = 8; d₃ = 20; d₄ = 11; d₅ =8; d₆ = 15; витрати на зберігання: h_k = 5; ; витрати на доставку (виробництво) продукції: A₁= A₂ =…=A₆=50.

Планування кроку 1.

Планування кроку 2.

- поставка продукції для двох періодів здійснюється на початку першого періоду (тобто остання поставка здійснюється в першому періоді); - поставки здійснюються таким чином: у першому - для першого, у другому - для… У першому випадку сумарні витрати складаються з витрат на поставку необхідної продукції для перших двох періодів (A1)…

Контрольні завдання

Таблиця 11 Ва- рі- ант Попит Витрати на зберігання … Продовження таблиці 11 Варіант Витрати на поставку… 8 ЗАДАЧА ПРО НАДІЙНІСТЬ

Змістовна постановка задачі

Конструюється електричний прилад, що складається з компонентів (рис. 25) [5].

 

 

 

Рис. 25

 

Усі компоненти з'єднані послідовно, тому вихід з ладу однієї з них приводить до відмови в роботі всього приладу. Надійність (ймовірність безаварійної роботи) приладу можна підвищити шляхом дублювання кожної компоненти (рис. 26).

 

 

 

 

Рис. 26

 

Конструкція приладу допускає використання декількох запасних блоків, тобтота компонента може містити до блоків, з'єднаних паралельно. Відомі ймовірність безаварійної роботи і вартість ої компоненти, що включає в себе паралельно з'єднаних блоків. Визначити кількість блоків у компоненті , , при яких надійність приладу максимальна, а його вартість не перевищує величини .

Математична модель задачі

Змінні: – кількість паралельно з'єднаних блоків компоненти.

Цільова функція: надійність приладу, що складається з послідовно з'єднаних компонент .

Обмеження: вартість приладу не може перевищувати величину :

.

 

Елементи динамічної моделі

Стани. Нехай – сумарна вартість перших компонент. Стан на -ому етапі будемо описувати величиною . Можливі значення цієї величини приведені в табл.… Таблиця 12 Можливі значення Коментар …

Основне рекурентне співвідношення

Якщо – кількість блоків компоненти , то на це грошей витрачено , а на комплектацію компонентів пішло од. вартості. Тоді (26) є максимальною ймовірністю безвідмовної роботи, яку можна одержати від розподілу одиниць вартості на комплектацію…

Приклад розв’язання задачі

Таблиця 13   Компонента 0,6 2 …   У нашому випадку можливі стани на кожному із трьох етапів такі:

Контрольні завдання

Таблиця 15 Ва-рі-ант Компонента …