Інформаційні технології та моделювання бізнес-процесів - Томашевський О.М. - 8.1. Задачі динамічного програмування

8.1. Задачі динамічного програмування

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

o функція мети повинна бути адитивною, тобто складатись із суми функцій, кожна з яких залежить лише від відповідної змінної;

o задача повинна допускати інтерпретацію як багатокроковий процес прийняття рішень;

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

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

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

1. До складу виробничого об'єднання входить m підприємств. Припустимо, що для розвитку цих підприємств впродовж п років виділені кошти в розмірі k у.о. Ці кошти на початку кожного року розподіляються між підприємствами. Одночасно з тим між підприємствами розподіляється одержаний ними прибуток за минулий рік, який залежить від вкладених коштів. Задача полягає у наступному: необхідно визначити такий розподіл коштів на початок кожного року підприємству, щоб сумарний прибуток всіх підприємств за n років був максимальним.

2. Нехай літак, що знаходиться на висоті ho і має швидкість v0, повинен піднятись на висоту hk та досягнути швидкості vk. Відомі витрати пального для підйому з будь якої висоти h до висоти H при сталій швидкості v та витрати пального для збільшення швидкості від v до V при сталій висоті h . Необхідно визначити таку траєкторію польоту (набирання висоти та швидкості), за якої загальні витрати пального будуть мінімальними.

3. Для здійснення ефективної діяльності фірма повинна періодично проводити заміну обладнання, яке нею використовується. При цій заміні враховуються: продуктивність обладнання, що використовується; витрати, пов'язані з утриманням і ремонтом обладнання; вартість обладнання, яке передбачається придбати, і вартість обладнання, що підлягає заміні.

Припустимо, що на початок планового періоду фірма придбала нове обладнання, причому відомо, що в k -му році, використовуючи придбане обладнання, фірма може випустити продукції на s1 у.о., а щоденні витрати, пов'язані з утриманням і ремонтом обладнання, становлять s2 у.о. В k -ому році обладнання може бути продане за s3 у.о., а нове придбане за s4 у.о. З врахуванням усіх цих факторів знайти оптимальний план заміни обладнання впродовж N років.

Загальна постановка задачі динамічного програмування. Принцип оптимальності Белмана. Припустимо, що деяку фізичну систему 5 за допомогою керованого n - крокового процесу можна перевести з відомого

Рис.8.1. Стан системи керування

Сформульовані вимоги лежать в основі принципу оптимальності Белмана, який визначається наступним чином:

Властивість оптимального керування - для довільного початкового стану та початкового керування u1 керування на k-му (k=2,3,..,n) кроці повинно бути оптимальним лише стосовно поточного стану системи і не залежати від попередніх станів

Зауважимо, що початкове керування при розв'язуванні задачі методом динамічного програмування (як буде показано далі) завжди вибирається так, щоб забезпечити максимальну ефективність не першого кроку, а процесу в цілому.

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

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

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

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

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

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

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

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

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