Введение. Динамическое программирование (ДП) – один из подходов к решению задач оптимизации

Динамическое программирование (ДП) – один из подходов к решению задач оптимизации. ДП является одним из немногих общих методов решения задач оптимизации и его легко можно приспособить для решения стохастических задач. Процесс решения методом ДП является многоэтапным или многошаговым, т.е. каждый этап определяется решением некоторой частной задачи, обусловленной исходной.

Можно привести много примеров и практических задач, когда простая идея расчленения процесса принятия сложного решения может оказаться исключительно продуктивной. Например, сведение задачи рационального раскроя к линейному программированию не дает ощутимых результатов в связи с колоссальной размерностью решаемых задач. А применение динамического программирования к поиску вводимого в базисе вектора-раскроя на каждой итерации линейного программирования позволило не перечислять векторы заранее, а получать их только по мере надобности. Кроме того, многие задачи динамического программирования, являясь целочисленными, решаются за полиномиальное время.

Систематическое изучение и развитие многошаговых процессов и отвечающих им рекуррентных соотношений привело к возникновению во второй половине 50-х годов нового математического направления, получившего наименование динамического программирования. Создателем этого направления по праву считается американский математик Ричард Беллман, который не только получил основополагающие теоретические результаты, но и изучил многочисленные приложения к различным экономическим, техническим и чисто математическим задачам. Здесь мы ограничились рассмотрением лишь нескольких, наиболее часто встречающихся, примеров задач динамического программирования.

Целью методических указаний (Часть 3) для самостоятельной работы студентов по дисциплинам «Математические модели и методы исследования операций», «Методы оптимизации» «Комбинаторные алгоритмы» является закрепление и систематизация теоретических знаний, приобретение умений и практических навыков по использованию метода динамического программирования для решения целочисленных задач.

В указаниях изложены принципы метода динамического программирования. Основной теоретический материал изложен в лекциях «Динамическое программирование», «Алгоритмы динамического программирования для решения различных задач исследования операций». Каждый раздел сопровождается примерами. Даны упражнения для самостоятельной работы студентов на практикумах и для выполнения домашних заданий. Приведены контрольные вопросы для проверки студентами степени усвоения материала.