5.1. Основні поняття дп

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

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

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

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

Суть методу ДП полягає в тому, що замість пошуку оптимального розв'язку для всієї складної задачі знаходять оптимальні розв'язки для декількох більш простих аналогічного змісту, на які вона розбивається.

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

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

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

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

ДП має суттєві недоліки. Якщо для розв'язування ЗЛП є універсальний метод їх розв'язування – симплексний метод, то для задач ДП такого методу не існує. Кожна задача має свої труднощі, для подолання яких потрібно щоразу знаходити нові методи. Крім того, сам процес розв'язування багатокрокових задач є досить громіздким і створює значні проблеми для використання обчислювальної техніки.