Інформаційні технології та моделювання бізнес-процесів - Томашевський О. М. - 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*), яке переведе систему із початкового стану в деякий кінцевий стан Бп. Це оптимальне керування і забезпечить максимальний виграш від керування процесом в цілому.
Отже, в процесі оптимізації керування методом динамічного програмування багатокроковий процес треба "проходити" двічі. Перший раз - від кінця до початку, в результаті чого знаходять умовні оптимальні керування і умовні оптимальні виграші на всіх кроках. Другий раз - від початку до кінця, в результаті чого знаходять оптимальні керування на кожному кроці і, відповідно, оптимальне керування процесом в цілому. Тобто,
Принцип оптимальності - який би не був стан системи перед черговим кроком, треба вибрати керування на цьому кроці так, щоб виграш на даному кроці плюс оптимальний виграш на всіх наступних кроках був максимальним
Схожі статті
-
8.1. Задачі динамічного програмування Розглянемо так звані задачі динамічного програмування і метод їх розв'язування (метод динамічного програмування)....
-
На сьогоднішній день штучний інтелект (Artifical Intelligence, AI) залишається одним із найбільш перспективних і нерозкритих напрямків розвитку...
-
7.1. Роль інформаційних технологій в системі організаційного управління Система (від грецького systema - ціле, складене з частин, з'єднання) - це...
-
7.1. Роль інформаційних технологій в системі організаційного управління Система (від грецького systema - ціле, складене з частин, з'єднання) - це...
-
Окрім вибору системи шифрування, яка оптимально відповідає характеру інформації, що обробляється, зберігається та передається в інформаційній системі,...
-
Інформаційні технології та моделювання бізнес-процесів - Томашевський О. М. - 6.4. Експертні системи
Експертною системою (EC) називають систему підтримки прийняття рішень, яка містить знання з певної вузької предметної області, а також може пропонувати...
-
Для забезпечення повноцінного і ефективного обміну інформацією як всередині ІС, так і між різними ІС, автоматизації роботи з даними різних типів,...
-
4.1. Принципи функціонування автоматичних засобів видобування знань Для аналізу і розв'язання задач різного характеру, в тому числі і економічних,...
-
Різноманітність сфер і форм застосування сучасних інформаційних технологій породжує різноманітність способів їх класифікації. За масштабністю...
-
Інформація, що циркулює в системі управління, об'єднується в групи за змістом та фіксується на конкретному матеріальному носії. Таке об'єднання носить...
-
Data Mining (добування знань, даних) - технологія аналізу сховищ даних, що грунтується на методах штучного інтелекту та інструментах підтримки прийняття...
-
4.1. Принципи функціонування автоматичних засобів видобування знань Для аналізу і розв'язання задач різного характеру, в тому числі і економічних,...
-
Комплексна автоматизація інформаційних потоків підприємства, організації, відомства, галузі вимагає створення єдиного інформаційного простору для...
-
Штучний інтелект є одним з напрямів інформатики, завданням якого є розробка апаратно-програмних засобів, які дозволяють користувачу формулювати і...
-
Життєвий цикл (ЖЦ) фіксує найбільш істотні, характерні для певного об'єкту стани, визначає їх основні характеристики та значення в даних станах, а також...
-
Кодування представляє собою процес присвоєння коду об'єкту класифікації. Кодування забезпечує унікальну ідентифікацію об'єктів, яка в сукупності з...
-
Пакет бізнес-додатків Oracle Applications - це 55 інтегрованих програмних модулів, кожний з яких представляє повністю функціональні рішення в області...
-
Пакет бізнес-додатків Oracle Applications - це 55 інтегрованих програмних модулів, кожний з яких представляє повністю функціональні рішення в області...
-
Під терміном ERP (Enterprise Resource Planning) розуміють спеціалізоване програмне забезпечення, яке виконує функції автоматизації певних напрямів...
-
OLAP (On-Line Analytical Processing) є ключовим компонентом організації сховищ даних. Ця технологія заснована на побудові і візуалізації багатовимірних...
-
Обов'язковим реквізитом електронного документа є електронний підпис. Його визначення вказано у Законі України "Про електронний цифровий підпис": Це вид...
-
Основною метою систем чи підсистем, що розробляються, є необхідність отримання бажаного результату в межах деякого інтервалу часу. В інформаційних...
-
Self Organizing Maps - SOM, або мапи Кохонена, що самоорганізуються, є різновидом нейронної мережі і використовуються для вирішення задач кластеризації і...
-
3.1. Етапи розвитку інформаційних технологій Інформаційні технології посідають чільне місце в нашому житті, тому це поняття є багатофункціональним та...
-
3.1. Етапи розвитку інформаційних технологій Інформаційні технології посідають чільне місце в нашому житті, тому це поняття є багатофункціональним та...
-
Опис класифікаційних угруповань, кодових позначень та найменувань об'єктів міститься в документі, який називається класифікатором. Класифікатор -...
-
Практика використання інформаційних технологій для моделювання та автоматизації підтримки прийняття рішень в управлінні соціально-економічними процесами...
-
Історія створення і розвитку інформаційних систем тісно пов'язана з автоматизацією діяльності підприємств та організацій, розвитком моделей їх...
-
Дані представляють собою спосіб представлення, збереження та елементарних операцій обробки інформації. Дані - це основа інформації. Поняття "дані" -...
-
1.1. Визначення поняття технології Словник іншомовних слів визначає технологію як сукупність способів переробки матеріалів, виготовлення виробів і...
Інформаційні технології та моделювання бізнес-процесів - Томашевський О. М. - 8.1. Задачі динамічного програмування