Клочко О. В., Коліжук М. В.

Вінницький національний аграрний університет, Україна

Метод динамічного програмування

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

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

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

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

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

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

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

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

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

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

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

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

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

Основні особливості методу динамічного програмування

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

2. Метод динамічного програмування можна застосовувати за будь-якого способу завдання цільової функції та з будь-якою припустимою множиною станів та керувань. Цієї переваги позбавлені класичні методи оптимізації та інші обчислювальні методи математичного програмування.

3. Обчислювальні схеми методу динамічного програмування в дискретному випадку пов'язані з перебиранням оптимальних значень показника ефективності й керування на к-му кроці для всіх можливих значень змінної стану, але обсяг розрахунків при цьому значно менший, ніж за прямого перебирання варіантів. Це пов'язано з тим, що на етапі умовної оптимізації невдалі варіанти відразу відкидаються, а зберігаються лише умовно оптимальні на даному кроці.

4. Метод динамічного програмування дає можливість аналізу чутливості до зміни вихідних даних станів sk та їх кількості п. Фактично тут на кожному кроці розв'язується не одна задача, а множина однотипних задач для різних станів sk і різних к (1 < к < п). Тому зі зміною вихідних даних можна не розв'язувати задачу заново, а зробити лише нескладні додавання до вже виконаних розрахунків, тобто продовжити вже розв'язану задачу за рахунок збільшення кількості кроків п або кількості значень.

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

Література:

1.Щербина О. А. Методологічні аспекти динамічного програмування / / Динамічні системи, 2007, вип. 22. - C.21-36.

2.Електронний ресурс: http://archive.nbuv.gov.ua/portal/natural/VDuikt/2012_2/chaika.pdf

3.Електронний ресурс: http://posibnyky.vntu.edu.ua/k_m/t2/510..htm

4.Електронний ресурс:

http://pidruchniki.ws/14250725/menedzhment/dinamichne_programuvannya