Лекція 25

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

Динамічне програмування (динамічне планування) являє собою математичний метод оптимізації рішень, спеціально пристосований до багатокрокових (або багатоетапних) операцій. Типовими завданнями динамічного програмування є задачі розподілу обмежених ресурсів. Наприклад: РЕА складається з декількох складових частин, що визначають її масу. З метою зменшення маси можлива зміна прийнятої елементної бази та конструкційних матеріалів, що викличе збільшення вартості РЕА. Відомий функціональний зв'язок зміни маси з витратами (вартістю). Потрібно оптимальним чином використовувати кошти, для зменшення маси РЕА.

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

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

Є деяка фізична система S, яка з плином часу змінює свій стан, тобто в системі S відбувається якийсь процес. Ми можемо керувати цим процесом, тобто тим чи іншим способом впливати на стан системи. Таку систему будемо називати керованою системою, а спосіб нашого впливу на неї - управлінням U. Припустимо, що з процесом пов'язана якась наша зацікавленість, що виражається чисельно величиною W, яку ми будемо називати виграшем. Ми хочемо так керувати процесом, щоб виграш був максимальний. Очевидно, виграш залежить від управління: W = W (U). Ми хочемо знайти таке управління (оптимальне) U = u, при якому виграш максимальний

Таким чином, поставлена ​​загальна задача оптимізації управління фізичною системою. Однак вона поставлена ​​ще не повністю. Зазвичай в таких задачах повинні бути враховані деякі умови, що накладаються на початкове S₀ і кінцеве S_w стан системи. Вони можуть точно задаватися або вказуватися їх можлива область. Тоді загальна задача оптимального управління формулюється таким чином:

з безлічі можливих управлінь U знайти таке оптимальне управління, яке переводить фізичну систему S з початкового стану S₀ в кінцевий стан S_w і так, щоб при цьому виграш W звертався в максимум.

Якщо стан системи характеризується двома параметрами x₁ і x₂ (наприклад, вартість комплектуючих елементів і вартість конструкторської розробки), то фазовий простір буде двовимірним, а процес буде зображуватися переміщенням точки S з в з певної траєкторії. В принципі траєкторій існує нескінченна безліч (або кінцеве, але їх багато) і з них потрібно вибрати ту, де виграш буде максимальним (наприклад, з мінімальною сумарною вартістю РЕА). Траєкторія руху точки S буде графічним зображенням процесу управління (рис. 25.1).

Рис.25.1

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

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

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

Розглянемо приклад. Нехай є система, стан якої залежить від двох параметрів.

Рис.25.2

Відомі також витрати по переведення системи зі стану S₀ в будь-який інший проміжний стан. Потрібно знайти оптимальне управління. Під впливом якого система перейде з початкового в кінцевий стан таким чином, щоб виграш був максимальний (мінімум витрат). Так як діапазон зміни параметрів розбитий відповідно на n₁ = 8 і n₂ = 6, то загальне число кроків m буде: m = n₁ + n₂ = 14. Щоб оптимізувати управління процесом переведення системи в кінцевий стан, треба знати витрати на кожному кроці. Запишемо ці витрати на кожному відрізку. Будь-яке управління, що переводить систему з S₀ в S_w відповідає цілком певним витратам, рівним сумі чисел, написаних на відрізках. З усіх можливих нам потрібно вибрати мінімальне. Оптимізацію почнемо з останнього кроку. Кінцевий стан системи має бути S_w. Подивимося, звідки ми можемо переміститися в цю точку за один крок? Розглянемо окремо правий верхній кут нашої моделі.

Рис.25.3

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

Якщо ми виявилися в точці С₁, то вибору немає - ми повинні переміщатися по горизонталі з витратами 15 + 17 = 32. Цю витрату ми і запишемо в кружечку при С₁. Для точки С₂ є вибір: з неї можна йти в S_w або через В₁, або через В₂. У першому випадку витрати будуть 13 + 17 = 30, у другому 17 + 14 = 31. Значить, оптимальний шлях з С₂ в S_w лежить через В₁. Відзначимо це вертикальної стрілкою і в кружечках запишемо мінімальні витрати. Для точки С₃ шлях знову єдиний з витратами 12 + 14 = 26.

Таким чином, переходячи від точки до точки справа наліво і зверху вниз, можна для кожної вузлової точки вибрати умовне оптимальне керування на наступному кроці. Рано чи пізно процес закінчується, дійшовши до вихідної точки S₀. На цьому етап умовної оптимізації закінчується, і починається етап безумовної оптимізації. При цьому оптимальне управління будується, переміщаючись по стрілках з S₀ в S_w.

Отже, особливість завдань, що вирішуються методом динамічного програмування, полягає в наступному:

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

2.Процесс ділиться на певне число кроків. На кожному кроці проводиться вибір одного рішення (управління) U_i = U_i (U₁, U₂,..., U_m), під впливом якого процес переходить зі стану S_i-1 в новий стан

S_i = S_i (S_i-1, U_i). Оскільки процес не має післядії, то управління U_i залежить тільки від досягнутого поточного стану S_i-1 тобто U_i = U_i (S_i-1).

3.Кожен крок пов'язаний з певним ефектом (вартості, зміною точності, надійності, габаритів) W_i, який залежить від поточного стану і прийнятого рішення W_i = W_i (S_i-1, U_i). Загальний ефект за m кроків складається з ефектів на окремих кроках:

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

- мультиплікативний критерій;

4. Потрібно знайти таке рішення U_i для кожного кроку, щоб отримати максимальний ефект за m кроків.

Як правило, на вектори S і вектори рішень (управлінь) U бувають накладені обмеження, що задають допустимі області їх зміни S Î G₁, U Î G₂. Будь-яка допустима послідовність рішень U = {U₁, U₂,..., U_m}, переводить систему зі стану S₀ в кінцевий S_m, називається стратегією управління. Послідовність рішень, що доставляє оптимум обраним критерієм, називається оптимальною стратегією, тобто величина Wi (S) повинна мати максимальне значення.

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

1. Виконується попередня підготовка даних, яка включає:

- Конкретизацію кроків розв'язання задачі та аналітичний опис процесу,

- Встановлення дискретності виконання обчислень,

- Обчислення ефекту W (S, U) для кожного стану і кожного дискретного значення управління і «витрат» Z (S, U) на отримання даного ефекту. Результати розрахунку зводять в табл. 25.1.

U U

Стан

Домінарна послідовність

S1

S2

Sm

y1

y2

W1

Z1

Z2

W2

Wm

m

y1

y1

y2

y2

U U0

W1^0(S1U0)

Z1^0(S1U)

2^0(2U0)

Z2^0(S2U)

Wm^0(mU)

m^0(m0)

y1^1

y1^1

y2^1

y2^1

U U1

W1^1(S1U1)

Z1^1(S1U)

…

…

Wm^1(Sm1)

m^1(m1)

y1^2

y1^2

y2^2

y2^2

U Uk

W1^k(S1Uk)

Z1^k(S1U)

Wm^k(Smk)

m^k(mU)

y1^k

y1^k

y2^k

y2^k

2. Виконують перший крок розв'язання задачі. Здійснюється композиція двох станів (ділянок), наприклад m і m-1. Розраховується показник якості управління (ефект)

Розрахунок виконується для всіх можливих поєднань управлінь одного і другого стану. При адитивному критерії якості:

При мультиплікаційному:

Визначаються витрати, відповідні отриманим показникам якості:

Результати розрахунків зводять в табл.25.2

Таблиця 25.2

3. Аналізують результати розрахунків. Систематизують дані табл. 25.2 в порядку зростання витрат Z_{m, m-1}. Результати, які мають найбільший показник якості W при одних і тих же витратах підкреслюються (або виділяються). В результаті розглянутої процедури буде отримана послідовність, звана домінуючою, яку зводять в табл. 25.1 і позначають y₁. Число станів в системі зменшилася на один.

4. Виконується другий крок розв'язування задачі. Здійснюється композиція домінуючої послідовності y₁ і стану S_m-2. Результати заносять в табл.25.3, де

Результати розрахунків аналізуються методом, розглянутим раніше і складається друга домінуюча послідовність y₂, яка заноситься в табл. 25.1.

5. Зазначена процедура триває до тих пір, поки не буде побудована остаточна домінуюча послідовність. У практичних розрахунках іноді зручніше отримувати спочатку попарні композиції окремих станів, а потім компонувати попарно отримані домінуючі послідовності. Отриманням y_m-1 закінчується перша стадія виконання завдання.

6. Друга стадія рішення складається з знаходження оптимального виграшу і оптимальної стратегії. Оптимальний виграш і відповідні йому витрати, що задовольняють заданим вимогам і обмеженням знаходять в остаточній домінуючій послідовності y_m-1. Тут же знаходять і оптимальне управління U^P(S₁). Далі по ланцюжку:

буде знайдена оптимальна стратегія, що складається з оптимальних управлінь U^P(S₁), U^P(S₂), …, U^P(S_m) на кожному кроці.

Таблиця 25.3

Дата добавления: 2014-01-07