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

 

Спочатку метод динамічного програмування був розроблений для дискретних систем. Як зазначалося раніше (див. п. 2.3), дискретні об’єкти управління описуються не диференціальними, а різницевими рівняннями стану:

, =0, 1, 2, …

Для одновимірного об’єкта

, =0, 1, 2, …,                  (5.1)

де , .

Для дискретного об’єкта критерій оптимальності має вигляд

.                                    (5.2)

Розглянемо задачу із закріпленим лівим кінцем, для якої задано початковий стан  та область допустимих управлінь . Необхідно знайти таку послідовність управлінь , , …, , при яких критерій оптимальності  (5.2) досягне мінімального значення.

Розв’язання задачі починають із правого кінця.

Припустимо, що всі управління , , …,  знайдені, а за формулою (5.1) знайдені змінні стану , …,  ( задано за умовою). Необхідно знайти тільки .

Оскільки критерій оптимальності (5.2)  і нам невідомо тільки , то згідно з принципом оптимальності (див. п. 5.1) кінцева ділянка оптимальної траєкторії також є оптимальною. Математично це можна записати у вигляді такого виразу:

.                            (5.3)

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

.                                (5.4)

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

.                     (5.5)

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

Розв’язання задачі можна розбити на три етапи.

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

Аналогічно розбивається й діапазон допустимих станів  на  відрізків із кроком  при .

Далі шукають критерій оптимальності  (5.3) у точці  спочатку для першого значення змінної стану  горизонтального відрізка області допустимих станів . Для цього при фіксованому , підставляючи різні , обчислюють послідовність , , …, . Із цієї послідовності  визначають мінімальне значення й позначають його  (див. (5.5)), а управління –  (див. (5.4)).

Таким чином, у пам’яті ЕОМ залишаються три величини , ,.

Далі береться наступне значення змінної стану  у точці  і виконуються такі самі дії. Усі операції повторюються до останньої точки  горизонтального відрізка області допустимих станів . У результаті в пам’яті машини зберігаються значення змінних стану , , …,  та відповідних їм оптимальних управлінь ,  у точці .

Етап 2. Наступним етапом є знаходження оптимальних управлінь  для попередньої  точки. У цій точці критерій оптимальності  буде залежати не тільки від значень  та , але й від наступних  та , а саме:

.     (5.6)

Мінімальне значення другого доданка   вже було знайдено на попередньому етапі. Тоді умову (5.6) можна переписати у такій формі:

.         (5.7)

Із (5.7) видно, що критерій якості  не залежить від управління  в точці , але залежить від змінної стану . Для зняття цієї залежності можна скористатися різницевим рівнянням (5.1), записаним у вигляді

.                     (5.8)

Отже, критерій (5.7) можна переписати в такий спосіб:

.   (5.9)

Аналогічно (5.4) оптимальне управління в точці  позначимо

.                              (5.10)

Тоді мінімальне значення критерію  у точці  аналогічно (5.5) позначимо . Із урахуванням уведених позначень вираз для  набуде вигляду

 

.                            (5.11)

Із виразу (5.11) видно, що мінімальне значення критерію  в точці  залежить тільки від  та .

У цьому випадку, при , як і в точці , область допустимих управлінь  розбиваємо на  відрізків, а область допустимих станів  – на  відрізків, на кінцях яких відмічають точки , , …,  та , , …,  відповідно.

На підставі формули (5.8) знаходимо  при  та кожному , тобто

,   .

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

У результаті при  та різних ,  формується система

,   .

Записавши  виразів при , шукаємо мінімальне , що позначається . У пам’ять машини записується , , .

Потім дії повторюються при , …, .

У результаті в пам’яті машини будуть записані стани , , …, ; оптимальні управління  та мінімальні значення критерію якості , . При цьому інформацію про мінімальні значення критерію якості  у точці  із пам’яті машини можна видалити.

Аналогічні операції проводяться для змінних стану  тощо.

Дійшовши до -го кроку, вираз (5.11) набуде такого вигляду:

 

.                  (5.12)

Оптимальне управління аналогічно (5.10) можна записати в такий спосіб:

.                            (5.13)

Надаючи  зростаючих значень, дійдемо до .

Для цього випадку

.     (5.14)

Як і у випадку (5.10), з (5.14) знаходимо оптимальне управління  та величину  як функції від заданого стану об’єкта . Ця операція виконується аналогічно операції, описаній для точки , тільки змінна  набуде одного значення, а управління  –  значень: , , …, .

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

За формулою (5.1) обчислюється змінна . Далі всі операції повторюються до . У результаті знаходимо всю послідовність оптимальних управлінь , , …, .

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

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