Моделювання оптимальної стратегії заміни обладнання за допомогою динамічного програмування (стр. 2 из 5)

Однак динамічне програмування має й свої недоліки. На відміну від лінійного програмування, у якому симплексний метод є універсальним, у динамічному програмуванні такого методу не існує. Кожне завдання має свої труднощі, і в кожному випадку необхідно знайти найбільш підходящу методику рішення. Недолік динамічного програмування полягає також у трудомісткості рішення багатомірних завдань. При дуже великому числі змінних рішення завдання навіть на сучасних ЕОМ обмежується пам'яттю й швидкодією машини. Наприклад, якщо для дослідження кожного змінного одномірного завдання потрібно 10 кроків, то у двовимірному завданні їхня кількість збільшується до 100, у тривимірної – до 1000 і т.д.

Припустимо, якась система S перебуває в деякому початковому стані S₀ й є керованою. Таким чином, завдяки здійсненню деякого керування U зазначена система переходить із початкового стану S₀ у кінцевий стан S_к. При цьому якість кожного з реалізованих керувань U характеризується відповідним значенням функції W^(U). Завдання полягає в тім, щоб з безлічі можливих керувань U знайти таке U*, при якому функція W^(U) приймає екстремальне (максимальне або мінімальне) значення W^(U*).

Завдання динамічного програмування мають геометричну інтерпретацію. Стан фізичної системи S можна описати числовими параметрами, наприклад витратою пального й швидкістю, кількістю вкладених коштів і т.д. Назвемо ці параметри координатами системи; тоді стан системи можна зобразити крапкою S, а перехід з одного стану S1 в інше S2 – траєкторією крапки S. Керування U означає вибір певної траєкторії переміщення крапки S з S1 в S2, тобто встановлення певного закону руху крапки S.

Сукупність станів, у які може переходити система, називається областю можливих станів. Залежно від числа параметрів, що характеризують стан системи, область можливих станів системи може бути різної. Нехай, наприклад, стан системи S характеризується одним параметром, – координатою x. У цьому випадку зміна координати, якщо на неї накладені деякі обмеження, зобразиться переміщенням крапки S по осі О_x або по її ділянці. Отже, областю можливих станів системи є сукупність значень x, а керуванням – закон руху крапки S з початкового стану S0 у кінцеве S_k по осі O_x або її частини (рис. 1.1).

S₀ S S_k

0 x

Область можливих станів системи

Рисунок 1.1. Графічне зображення переходу системи S

Таким чином, завданню динамічного програмування можна дати наступну геометричну інтерпретацію. Із всіх траєкторій, що належать області можливих станів системи й з'єднуючих областей S₀ й S_k, необхідно вибрати таку, на якій критерій W приймає оптимальне значення.

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

Будемо вважати, що стан розглянутої системи S на K-м кроці (k=1, n) визначається сукупністю чисел X^(k) =(x₁^(k), x₂^(k),…, x_n^(k)), які отримані в результаті реалізації керування uk, що забезпечило перехід системи S зі стану X^(k-1) у стан X^(k). При цьому будемо припускати, що стан X^(k), у яке перейшла система S, залежить від даного стану X^(k-1) і обраного керування u_k і не залежить від того, яким образом система S прийшла в стан X^(k-1).

Далі із уважати, що якщо в результаті реалізації k-го кроку забезпечені певний доход або виграш, що також залежить від вихідного стану системи X^(k-1) і обраного керування u_k і рівний W_k^{(X(k-1), uk)}, те загальний доход або виграш за n кроків становить

n

F=∑ W_k(X^(k-1), u_k) (1.1)

k=1

Таким чином, завдання динамічного програмування повинна задовольняти дві умови. Першу умову звичайно називають умовою відсутності післядії, а друге – умовою адитивності цільової функції завдання.

Виконання для завдання динамічного програмування першої умови дозволяє сформулювати для неї принцип оптимальності Беллмана. Перш ніж зробити це, треба дати визначення оптимальної стратегії керування. Під такою стратегією розуміється сукупність керувань U^*=(u₁*, u₂*,…, u_n*), у результаті реалізації яких система S за n кроків переходить із початкового стану X⁽⁰⁾ у кінцеве X^(k) і при цьому функція (1.1) приймає найбільше значення.

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

Звідси треба, що оптимальну стратегію керування можна одержати, якщо спочатку знайти оптимальну стратегію керування на n-м кроці, потім на двох останніх кроках, потім на трьох останніх кроках і т.д., аж до першого кроку. Таким чином, рішення розглянутого завдання динамічного програмування доцільно починати з визначення оптимального рішення на останньому, n-м кроці. Для того щоб знайти це рішення, мабуть, потрібно зробити різні припущення про те, як міг скінчитися передостанній крок, і з обліком цього вибрати керування un0, що забезпечує максимальне значення функції W_n(X^(n-1), u_n). Таке керування un0 обране при певних припущеннях про те, як скінчиться попередній крок, називається умовно оптимальним керуванням. Отже, принцип оптимальності вимагає знаходити на кожному кроці умовно оптимальне керування для кожного з можливих варіантів попереднього кроку.

Щоб це можна було здійснити практично, необхідно дати математичне формулювання принципу оптимальності. Для цього введемо деякі додаткові позначення. Позначимо через F_n(X⁰) максимальний доход, одержуваний за n кроків при переході системи S з початкового стану X⁽⁰⁾ у кінцевий стан X^(k) при реалізації оптимальної стратегії керування U=(u₁, u₂,…, u_n), а через F_n-k(X^(k)) – максимальний доход, одержуваний при переході з будь-якого стану X(k) у кінцевий стан X⁽ⁿ⁾ при оптимальній стратегії керування на що залишилися n-k кроках. Тоді:

F_n(X⁰)=max[W₁(X⁽⁰⁾, u₁)+ … + W_n(X^(n-1), u_n)] (1.2)

U_k+j

F_n-k(X^(k))=max[W_k+1(X^(k), u_k+1)+F_n-k-1(X^k+1))] (k=0, n-1) (1.3)

U_k+1

Останнє вираження являє собою математичний запис принципу оптимальності й зветься основного функціонального рівняння Беллмана або рекуррентного співвідношення. Використовуючи дане рівняння можна знайти рішення завдання динамічного програмування.

Думаючи k=n-1 у рекуррентном співвідношенні (1.3), одержимо наступне функціональне рівняння:

F₁(X^(n-1)=max[W_n(X^(n-1), u_n)+F₀(X⁽ⁿ⁾)] (1.4)

u_n

У цьому рівнянні F₀(X⁽ⁿ⁾) будемо вважати відомим. Використовуючи тепер рівняння (1.4) і розглядаючи всілякі припустимі із системи S на (n-1) – м кроці X₁^(n-1), X₂^(n-1),…, X_m^(n-1),…, знаходимо умовні оптимальні рішення u_n⁰(x₁^(n-1)), u_n⁰(x₂^(n-1)),…, u_n⁰(x_m^(n-1)),…

і відповідні значення функції (1.4)

F₁⁰ (X₁^(n-1)), F₁⁰ (X₂^(n-1)), …, F₁⁰ (X_m^(n-1)),…

Таким чином, на n-м кроці знаходимо умовно оптимальне керування при будь-якому припустимому стані системи S після (n-1) – го кроку. Тобто, у якому би стані система не виявилася після (n-1) – го кроку, буде відомо, яке варто прийняти рішення на n-м кроці. Відомо також і відповідне значення функції (2.4). Розглянемо функціональне рівняння при k=n-2:

F₂(X^(n-1))=max[W_n-1(X^(n-2), u_n-1)+F₁(X^(n-1))] (1.5)

U_n-1

Для того щоб знайти значення F₂ для всіх припустимих значень X^(n-2), необхідно знати W_n-1(X^(n-2), u_n-1) і F₁(X^(n-1)). Що стосується значень F₁(X^(n-1)), те вони вже визначені. Тому потрібно зробити обчислення для W_n-1(X^(n-2), u_n-1) при деякому відборі припустимих значень X^(n-2) і відповідних керувань u_n-1. Ці обчислення дозволять визначити умовно оптимальне керування u0n-1 для кожного X^(n-2). Кожне з таких керувань разом із уже обраним керуванням на останньому кроці забезпечує максимальне значення доходу на двох останніх кроках.

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

Таким чином, у результаті послідовного проходження всіх етапів від кінця до початку визначається максимальне значення виграшу за n кроків і для кожного з них знаходимо умовно оптимальне керування.

Щоб знайти оптимальну стратегію керування, тобто визначити шукане рішення завдання, потрібно тепер пройти всю послідовність кроків, тільки цього разу від початку до кінця. А саме: на першому кроці як оптимальне керування u₁* візьмемо знайдене умовно оптимальне керування u₁⁰. На другому кроці знайдемо стан X₁*, у яке переводить систему керування u₁*. Цей стан визначає знайдене умовно оптимальне u₂⁰, що тепер уважається оптимальним. Знаючи u₂*, знаходимо X₂*, а виходить, визначаємо u₃* і т.д. У результаті цього найдеться рішення завдання, тобто максимально можливий доход й оптимальну стратегію керування U*, що включає оптимальні керування на окремих кроках: U*= (u₁*, u₂*,…, u_n*).