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

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

Походження терміна

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

Алгоритм (метод) розв'язання багатоетапних задач

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

Метод зверху і метод знизу

Попри те що при розрахунку на окремому етапі вирішення задачі використовуються параметри процесу на поточний момент, результат оптимізації на попередньому етапі впливає на розрахунки наступних етапів для досягнення найкращого результату в цілому. Динамічне програмування називає такий принцип рішення методом оптимальності, який визначає, що оптимальна стратегія вирішення завдання незалежно від початкових рішень і умов повинна наступними рішеннями на всіх етапах скласти оптимальну стратегію щодо початкового стану. Як бачимо, процес рішення задачі являє собою безперервну оптимізацію результату на кожному окремому етапі від першого до останнього. Такий метод називається методом програмування зверху. На малюнку схематично показано алгоритм рішення зверху вниз. Але існує клас багатокрокових задач, в яких максимальний ефект на останньому етапі вже відомий, наприклад, ми вже приїхали з пункту А в пункт Б і тепер хочемо дізнатися, чи правильно ми їхали на кожному попередньому етапі чи можна було щось зробити більш оптимально. Виникає рекурсивна послідовність етапів, тобто ми йдемо як би «від зворотного». Цей метод рішення отримав назву "метод програмування знизу".

Практичне застосування

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

Пошук оптимального шляху

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

Виробництво

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

Наукова сфера

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