Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

9.5. Багатокроковий процес прийняття рішень

Будь-яку багатокрокову задачу можна розв’язувати по-різному: або знаходити одразу всі елементи розв’язку на всіх кроках, або будувати оптимальне управління поступово, крок за кроком (на кожному етапі розрахунків оптимізуючи лише один крок). Як правило, другий спосіб оптимізації є значно простішим, ніж перший, особливо при значній кількості кроків. Оптимізація одного кроку є простішою порівняно з оптимізацією всього процесу, тому краще багато разів розв’язувати простіші задачі, ніж один раз — складну.

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

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

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

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

Дійсно, якщо відомо початковий стан , то можна вибрати для нього оптимальне управління , що приведе до стану , для якого також відоме оптимальне управління і т. д.

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

Перший етап — знаходження умовно-оптимальних управлінь є дуже складним та довгим у порівнянні з другим. На другому етапі залишається лише «прочитати» рекомендації, що отримані на першому. Зауважимо, що «кінець» та «початок» можна поміняти місцями і здійснювати процес оптимізації також і в іншому напрямку (приклад 9.1).

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

1. Визначають специфічні показники стану досліджуваної керованої системи і множину параметрів, що описують цей стан. Стан системи описується у такий спосіб, щоб можна було забезпечити зв’язок між послідовними етапами розв’язання задачі і мати змогу одержати допустиме рішення задачі в цілому як результат оптимізації на кожному кроці окремо, а крім того, приймати оптимальні рішення на наступних етапах без урахування впливу майбутніх рішень на ті, що були прийняті раніше.
2. Поділяють процес на етапи (кроки), які, як правило, відповідають певним періодам планування динамічних процесів, або окремим об’єктам (підприємствам, видам продукції, устаткуванню тощо) у разі підготовки рішень стосовно керування ними.
3. Формулюють перелік управлінь для кожного кроку і відповідні обмеження щодо них.
4. Визначають ефект, який забезпечує управління на j–му кроці, якщо перед тим система була у стані S, у вигляді функції ефективності:
5. .
6. Визначають, як змінюється стан S системи під впливом управління на j-му кроці, тобто як здійснюється перехід до нового стану:

.

1. Будують рекурентну залежність задачі динамічного програмування, що визначає умовний оптимальний ефект починаючи з j–го кроку і до останнього, через вже відому функцію

.

Цьому ефекту відповідає умовне оптимальне управління на j-му кроці Зауважимо, що у функції необхідно замість врахувати змінений стан системи, тобто

1. Використовують умовну оптимізацію останнього n-го кроку, визначаючи множину станів S, з яких можна за один крок дійти до кінцевого стану. Умовно-оптимальний ефект на n-му кроці обчислюють за формулою:

Потім знаходять умовно-оптимальне управління в результаті реалізації якого цей максимум буде досягнуто.

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

1. Проводять безумовну оптимізацію управління у «зворотному» напрямку від початкового стану до кінцевого. Для цього з урахуванням визначеного оптимального управління на першому кроці змінюють стан системи згідно з пунктом 5. Потім для цього нового стану знаходять оптимальне управління на другому кроці і аналогічно ці дії повторюють до останнього етапу (кроку).

В результаті знаходять оптимальне покрокове управління , що забезпечує максимальну ефективність Z*.