Серед завдань, що вирішуються за допомогою математичного програмування, можна виділити окремий клас задач, що вимагають оптимізації багатокрокових (багатоетапних) процесів. Такі завдання відрізняються можливістю розбиття рішення на кілька взаємопов`язаних етапів. Для вирішення подібних завдань використовується динамічне програмування або, як його ще називають, багатоетапний програмування. Його методи оптимізовані для пошуку оптимального рішення багатокрокових завдань, які можна розділити на кілька етапів, кроків і т. Д.
походження терміна
Використання в назві слова «динамічний» спочатку передбачало, що поділ на підзадачі буде відбуватися в основному в часі. При використанні динамічних методів для вирішення виробничих, господарських та інших завдань, в яких фігурує часовий чинник, розбивання на окремі етапи не складає труднощів. Але використовувати техніку динамічного програмування можливо і в завданнях, де окремі етапи не пов`язані за часом. Завжди в багатокрокової задачі можна виділити параметр або властивість, по якому можна зробити поділ на окремі кроки.
Алгоритм (метод) рішення багатоетапних завдань
Алгоритм іліметод динамічного програмування заснований на використанні принципу послідовного оптимизирования завдання, коли рішення загальної задачі розбивається на ряд рішень окремих підзадач з подальшим об`єднанням в єдине рішення. Дуже часто окремі підзадачі виявляються однаковими, і одне загальне рішення значно скорочує час розрахунку. 
Особливістю методу є автономність рішення задачі на кожному окремому етапі, т. Е. Незалежно від того, як оптимізувався і вирішувалося процес на попередньому етапі, в поточному розрахунку використовуються тільки параметри процесу, що характеризують його в даний момент. Наприклад, водій, що рухається по дорозі, приймає рішення про поточний повороті незалежно від того, як і скільки він їхав до цього.
Метод зверху і метод знизу
Незважаючи те що при розрахунку на окремому етапі рішення задачі використовуються параметри процесу на поточний момент, результат оптимізації на попередньому етапі впливає на розрахунки наступних етапів для досягнення найкращого результату в цілому. Динамічне програмування називає такий принцип рішення методом оптимальності, який визначає, що оптимальна стратегія вирішення задачі незалежно від початкових рішень і умов повинна наступними рішеннями на всіх етапах скласти оптимальну стратегію щодо початкового стану. Як бачимо, процес вирішення завдання являє собою безперервну оптимізацію результату на кожному окремому етапі від першого до останнього. Такий метод називається методом програмування зверху. На малюнку схематично показаний алгоритм рішення зверху вниз. Але існує клас багатокрокових завдань, в яких максимальний ефект на останньому етапі вже відомий, наприклад, ми вже приїхали з пункту А в пункт Б і тепер хочемо дізнатися, правильно ми їхали на кожному попередньому етапі або можна було щось зробити більш оптимально. Виникає рекурсивна послідовність етапів, т. Е. Ми йдемо як би «від зворотного». Цей метод вирішення отримав назву "метод програмування знизу".
Практичне застосування
Динамічне програмування може використовуватися в будь-який сфері діяльності, де присутні процеси, які можна по якомусь параметру (час, сума, температура і т. д.) розділити на ряд однакових невеликих етапів. Найбільше застосування динамічні способи вирішення отримали в теорії управління і при розробці обчислювальних систем.
Пошук оптимального шляху
За допомогою динамічної оптимізації можливе вирішення широкого класу задач по знаходженню або оптимізації найкоротшого шляху і інших завдань, в яких «класичний» метод перебору можливих варіантів вирішення призводить до збільшення часу розрахунку, а іноді взагалі неприйнятний. Класична задача динамічного програмування - це завдання про рюкзаку: дано кілька предметів з певною масою і вартістю, і необхідно вибрати набір предметів з максимальною вартістю і масою, що не перевищує обсяг рюкзака. Класичний перебір всіх варіантів в пошуках оптимального рішення займе чимало часу, а за допомогою динамічних методів завдання вирішується в прийнятні терміни. Завдання пошуку найкоротшого шляху для транспортної логістики є основними, і динамічні методи вирішення оптимально підходять для їх вирішення. Найбільш простим прикладом такого завдання є побудова найкоротшого маршруту автомобільним GPS-навігатором.
виробництво
Динамічне програмування широко використовується при вирішенні різноманітних виробничих завдань, таких як управління складськими запасами для підтримки потрібної кількості комплектуючих в будь-який момент часу, календарне планування виробничого процесу, поточний і капітальний ремонт обладнання, рівномірне завантаження персоналу, максимально ефективний розподіл інвестиційних коштів і т. Д. для вирішення виробничих завдань методами динамічного програмування розроблено спеціальні програмні пакети, інтегровані в популярні системи управління підприємствами, такі як SAP.
Галузь наукових інтересів
Методи динамічного програмування широко застосовуються в різних наукових дослідженнях. Наприклад, вони успішно використовуються в алгоритмах розпізнавання мови і образів, при обробці великих масивів даних в соціології та господарської діяльності.
