Розділ «8. Прийняття рішень у системах управління. Динамічне програмування»

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

Оскільки кожне знайдене умовне оптимальне керування на (n -1)-му кроці переводить систему в один з можливих передостанніх станів (а яке оптимальне керування переведе систему з цього стану у кінцевий, нам вже відомо), то для кожного можливого стану системи перед виконанням (n -1) -го кроку ми знайдемо умовне оптимальне керування на (n -1) -му кроці й умовний оптимальний виграш на останніх двох кроках. Далі переходимо до оптимізації керування на (n - 2)-му кроці і т. д., поки не дійдемо до першого кроку.

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

Нехай So - початковий стан системи. Тоді ми можемо вибрати оптимальне керування u1 , яке на першому кроці переведе систему із стану So в деякий стан S1. На другому кроці нам відомо умовно оптимальне керування u2*, яке переведе систему із стану S1 в деякий стан S2, і т. д. Отже, ми знайдемо оптимальне керування U* = (u1*, u2*,..., un*), яке переведе систему із початкового стану в деякий кінцевий стан Бп. Це оптимальне керування і забезпечить максимальний виграш від керування процесом в цілому.

Отже, в процесі оптимізації керування методом динамічного програмування багатокроковий процес треба "проходити" двічі. Перший раз - від кінця до початку, в результаті чого знаходять умовні оптимальні керування і умовні оптимальні виграші на всіх кроках. Другий раз - від початку до кінця, в результаті чого знаходять оптимальні керування на кожному кроці і, відповідно, оптимальне керування процесом в цілому. Тобто,

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

8.2. Основне функціональне рівняння Белмана

Запишемо принцип оптимальності у формалізованій формі. Для цього позначимо через Fn (So) максимальний виграш, який одержується за n кроків при переході системи S з початкового стану So в кінцевий стан Sn при реалізації оптимальної стратегії керування U * = (u1*, u2*,..., un*), а через Fn-k (Sк) - максимальний виграш, який одержується при переході системи з будь-якого стану Sк в кінцевий стан Sn при оптимальній стратегії керування на останніх n - k кроках. Тоді

Формула (8.1) представляє собою математичний запис принципу оптимальності і називається основним функціональним рівнянням Белмана або рекурентним співвідношенням. Використовуючи це рівняння, можна знайти розв'язок заданої задачі динамічного програмування. Процес відшукання розв'язку є наступним.

Покладемо в рекурентне співвідношення (8.1) k = п -1, одержимо

Отже, на n -му кроці знаходимо умовно оптимальні керування для будь-якого допустимого стану системи після (n - 1)-го кроку. Іншими словами, в який би стан система не перейшла після (n -1) -го кроку, нам вже відомо, яке оптимальне керування вибрати на n -му кроці і яке при цьому буде значення функції (8.2).

Після того, як знайдені всі умовно оптимальні керування на n -му кроці, переходимо до відшукання всіх умовно оптимальних керувань на (n -1) -му кроці. Для цього покладемо у формулу (8.1) k = и - 2. Одержимо

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

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

Для відшукання оптимальної стратегії керування, якій відповідатиме максимальний виграш, треба тепер пройти всю послідовність кроків від початкового до кінцевого. На першому кроці за оптимальне керування u1* беремо умовно оптимальне керування, знайдене на цьому кроці. Керування u1* переведе систему S із стану So в деякий стан S11*. Цей стан визначає знайдене умовно оптимальне керування на другому кроці, яке приймаємо за оптимальне керування u2* на другому кроці. Знаючи u2*, знаходимо стан S2, в який керування u2* переведе систему із стану S1*. На основі S2 знаходимо u3* і т. д. В результаті цього знайдемо оптимальну стратегію керування U* = (u1*, u2*,..., un*), якій відповідатиме максимальний виграш, тобто розв'яжемо задачу.

8.3. Задача про розподіл ресурсів

8.4. Задача про будівництво та експлуатацію підприємств

Припустимо, що фірма планує будівництво и підприємств однакової потужності. Ці підприємства фірма має можливість розмістити в m (m < и) регіонах. Відомі витрати на будівництво та експлуатацію підприємств в кожному регіоні в залежності від їх кількості. Необхідно так розмістити підприємства серед регіонів, щоб сумарні витрати на їх будівництво та експлуатації були мінімальними.

Запишемо математичну модель задачі. Для цього введемо величини:

Тоді математична модель задачі буде такою: