Економічна сутність динамічного програмування. Основні типи задач та моделі ДП.
ЗАДАЧІ ДИНАМІЧНОГО ПРОГРАМУВАННЯ
ТЕМА 9.
Задачі квадратного програмування і основні методи їх розв’язування.
Усі економічні процеси та явища є динамічними, оскільки функціонують і розвиваються не лише у просторі, а й у часі.
Народне господарство, його галузі, регіони чи окремі підпри ємства мають розробляти стратегічні і тактичні плани. Перші виз начаються з допомогою динамічних моделей, розв'язки яких знаходять методами динамічного програмування. Зауважимо, що сума оптимальних планів на окремих відрізках планового періоду Т не завжди являє собою план, оптимальний на всьому такому періоді.
Розглянемо задачу оптимального розподілу капітальних вкладень, які можуть бути використані двома способами: з метою розвитку рослинництва або тваринництва. Відомо, що за першого способу отримаємо прибуток , а за другого — .
У такому разі однокрокову задачу можна подати у вигляді:
(6.20)
за умов
(6.21)
Нехай
Тоді дану задачу можна записати так:
Розглянемо її як задачу оптимального використання капітальних вкладень за окремими інтервалами планового періоду Т, маючи на меті розподілити залишок капітальних вкладень на кінець j-го інтервалу двома зазначеними способами. При цьому критерій оптимізації не змінюється: максимізуємо обсяг прибутку за весь плановий період Т.
Якщо на першому інтервалі використано капітальних вкладень, то на його кінець залишилося їх:
де — коефіцієнти пропорційності, що характеризують використання капітальних вкладень першим і другим способами:
.
Задачу для другого інтервалу подамо так:
за умов
Звідси для будь-якого j-гоінтервалу маємо:
за умов
Загальна задача набирає вигляду:
(6.22)
за умов
Таку задачу розв’язують спеціальними методами [4, 10] .