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

Abstract

Постановка проблеми та аналіз останніх досліджень і публікацій. Метод динамічного програмування (ДП) – математичний метод с учасної теорії управління і знаходить застосування у вирішенні різноманітних проблем теорії прийняття рішень в різноманітних галузях знання. Він був запропонований американським математиком Р. Беллманом, який його чітко сформулював і пропагував у своїх книгах [1, 2, 3]. Методам динамічного програмування присвячені також сучасні дослідження, які представлені в багатьох монографіях та журнальних статтях [8, 13, 14]. Даний метод вивчається студентами економічних спеціальностей в таких дисциплінах, як “Математичне програмування”, “Дослідження операцій” та інших пов’язаних з оптимізацією та моделюванням економічних, екологічних, соціальних та інших процесів. Основи цього методу представлені в багатьох підручниках та навчальних посібниках, зокрема [6, 7, 12]. Метод динамічного програмування застосований до задач, у яких процес прийняття рішення можна розбити на етапи і при цьому виконується принцип оптимальності[1]. Принцип оптимальності в свою чергу є наслідком адитивності критерію оптимальності та відсутності зворотного зв’язку між етапами. Така ситуація властива багатьом практичним економіко-виробничим задачам. Зокрема, моделі динамічного програмування застосовуються в задачах управління запасами, розподілу дефіцитних ресурсів, ремонту обладнання та його заміни, планування зайнятості на виробництві та інших. Популярність ДП зумовлена достатньо простою структурою алгоритму, що дозволяє досить успішно розв’язувати оптимізаційні задачі ручним способом. Очевидно, така простота була досить суттєвою перевагою в період, коли комп’ютерні технології ще не набули широкого застосування