Динамическое программирование. Классические задачи

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

Происхождение термина

Использование в названии слова «динамический» первоначально предполагало, что разделение на подзадачи будет происходить в основном во времени. При использовании динамических методов для решения производственных, хозяйственных и иных задач, в которых фигурирует временной фактор, разбивание на отдельные этапы не составляет труда. Но использовать технику динамического программирования возможно и в задачах, где отдельные этапы не связаны по времени. Всегда в многошаговой задаче можно выделить параметр или свойство, по которому можно произвести разделение на отдельные шаги.

Алгоритм (метод) решения многоэтапных задач

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

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

Метод сверху и метод снизу

Несмотря то что при расчете на отдельном этапе решения задачи используются параметры процесса на текущий момент, результат оптимизации на предыдущем этапе влияет на расчеты последующих этапов для достижения наилучшего результата в целом. Динамическое программирование называет такой принцип решения методом оптимальности, который определяет, что оптимальная стратегия решения задачи вне зависимости от начальных решений и условий должна последующими решениями на всех этапах составить оптимальную стратегию относительно первоначального состояния. Как видим, процесс решения задачи представляет собой непрерывную оптимизацию результата на каждом отдельном этапе от первого до последнего. Такой метод называется методом программирования сверху. На рисунке схематически показан алгоритм решения сверху вниз. Но существует класс многошаговых задач, в которых максимальный эффект на последнем этапе уже известен, например, мы уже приехали из пункта А в пункт Б и теперь хотим узнать, правильно мы ехали на каждом предыдущем этапе или можно было что-то сделать более оптимально. Возникает рекурсивная последовательность этапов, т. е. мы идем как бы «от обратного». Этот метод решения получил название "метод программирования снизу".

Практическое применение

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

Поиск оптимального пути

С помощью динамической оптимизации возможно решение широкого класса задач по нахождению или оптимизации кратчайшего пути и других задач, в которых «классический» метод перебора возможных вариантов решения приводит к увеличению времени расчета, а иногда вообще неприемлем. Классическая задача динамического программирования - это задача о рюкзаке: дано некоторое количество предметов с определенной массой и стоимостью, и необходимо выбрать набор предметов с максимальной стоимостью и массой, не превосходящий объем рюкзака. Классический перебор всех вариантов в поисках оптимального решения займет значительное время, а с помощью динамических методов задача решается в приемлемые сроки. Задачи поиска кратчайшего пути для транспортной логистики являются основными, и динамические методы решения оптимально подходят для их решения. Наиболее простым примером такой задачи является построение кратчайшего маршрута автомобильным GPS-навигатором.

Производство

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

Научная сфера

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

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, раздел оптимального управления, посвящённый теории и методам решения многошаговых задач. В задачах оптимального управления среди возможных управлений ищется то, при котором достигается экстремальное (наименьшее или наибольшее) значение так называемой целевой функции - некоторой числовой характеристики процесса. В динамическом программировании под многошаговостью понимают либо многоступенчатую структуру процесса, либо то, что управление разбивается на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Иногда многошаговость проистекает из существа процесса, но она может вводиться и искусственно для того, чтобы обеспечить возможность применения методов динамического программирования. Под программированием в динамическом программировании понимают принятие решений (планирование), а слово «динамическое» указывает на существенную роль времени и порядка выполнения операций. Методы динамического программирования являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (например, в задачах об оптимальном распределении ресурсов, в теории управления запасами, в задачах замены оборудования) и при решении многих технических проблем (например, в задачах управления последовательными химическими процессами, в задачах оптимальной прокладки дорог).

Пусть процесс управления некоторой системой Х состоит из m шагов (этапов); на i-м шаге управление y i переводит систему из состояния x i-1 , в котором она находилась после (i - 1)-го шага, в новое состояние x i . При этом задана функция f i (х, у), и новое состояние определяется по этой функции значениями x i-1 , y i так, что x i = f i (x i-1 , y i), i = 1, 2,..., m. Таким образом, управления у 1 , у 2 , ..., у m переводят систему из начального состояния х 0 ∈ Х 0 в конечное состояние х m ∈ Х m , где Х 0 и Х m - совокупности допустимых начальных и конечных состояний системы Х.

Одна из возможных постановок задач динамического программирования состоит в следующем. При заданном начальном состоянии х 0 требуется выбрать управления у 1 , у 2 , ..., у m таким образом, чтобы система Х перешла в допустимое конечное состояние и при этом заданная целевая функция F(х 0 , у 1 , х 1 ,..., у m , х m) достигла максимального значения F*, т. е.

где максимум берётся по всем управлениям у 1 , ..., у m , для которых х m ∈ Х m .

В динамическом программировании обычно предполагается, что целевая функция является аддитивной. В рассмотренном примере это означает, что

Кроме того, в динамическом программировании предполагается, что в задаче отсутствует последействие: решения (управления), принимаемые на шаге i, оказывают влияние только на состояние x i системы в момент i. Оба упомянутых ограничительных условия можно ослабить, но только за счёт существенного усложнения метода.

В основе динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом. Пусть выбраны некоторые управления у 1 , у 2 , ..., y k и тем самым траектория х 0 , х 1 , ...,x k состояний и требуется завершить процесс, т. е. выбрать у k+1 , ..., у m (а значит, и x k+1 , ..., х m).

Если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции

то и весь процесс не будет оптимальным. Пользуясь принципом оптимальности Беллмана, можно получить основное функциональное соотношение динамического программирования, которое состоит в следующем. Пусть ω m (х) = 0,

k = 1, 2, ..., m, где максимум берётся по всем управлениям у, допустимым на шаге k. Соотношение, определяющее зависимость ω k-1 от ω k , называется уравнением Беллмана. Смысл этих функций достаточно ясен: если система на шаге k-1 оказалась в состоянии х, то ω k-1 (х) есть максимально возможное значение функции F k . Одновременно с построением функций ω k-1 (х) находятся условные оптимальные управления y k (х) на каждом шаге, т. е. значения оптимального управления при всевозможных предположениях о состоянии х системы на шаге k-1. Окончательно оптимальные управления находятся последовательным вычислением величин ω 0 (х 0) = F*, у 1 , х 1 , у 2 , ..., у m , x m .

С помощью динамического программирования решается не одна конкретная задача при определённом х 0 , а сразу все подобные однотипные задачи при любом начальном состоянии. Численная реализация динамического программирования довольно сложна, так как требует запоминания большого количества информации, поэтому динамическое программирование целесообразно применять в тех случаях, когда необходимо многократно решать типовые задачи (например, определение оптимального режима полёта самолёта при меняющихся погодных условиях). Обычно задача динамического программирования формулируется для дискретных процессов, но в ряде случаев динамическое программирование применяется и для решения динамических задач с непрерывными параметрами.

Динамическое программирование дало новый подход ко многим задачам вариационного исчисления. Важный раздел динамического программирования составляют стохастические задачи динамического программирования, т. е. задачи, в которых на состояние системы и на целевую функцию влияют случайные факторы.

Строгое обоснование динамического программирования следует из результатов Л. С. Понтрягина и его учеников по математической теории управляемых процессов.

Лит.: Беллман Р. Динамическое программирование. М., 1960; Математическая теория оптимальных процессов. М., 1961; Ховард Р. А. Динамическое программирование и марковские процессы. М., 1964; Хедли Дж. Нелинейное и динамическое программирование. М., 1967; Хедли Дж., Уайтин Т. Анализ систем управления запасами. М., 1969.

Раздел Динамическое программирование представлен следующими калькуляторами:

Задача распределения инвестиций . Для реконструкции и модернизации производства на четырех предприятиях выделены денежные средства С = 80 ден. ед. По каждому предприятию известен возможный прирост f i (х) (i = 1, 4) выпуска продукции в зависимости от выделенной суммы.

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

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

Рассмотрим общее описание задачи динамического программирования .
Пусть многошаговый процесс принятия решений разбивается на n шагов. Обозначим через ε 0 – начальное состояние системы, через ε 1 , ε 2 , … ε n – состояния системы после первого, второго, n -го шага. В общем случае состояние ε k – вектор (ε k 1 , …, ε k s ).
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) u k = (u k 1 , ..., u k r ), принимаемых на каждом шаге k и переводящих систему из состояния ε k -1 = (ε k- 1 1 , …, ε k -1 s ) в состояние ε k = (ε k 1 , …, ε k s ).
В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе. Например, выпуск продукции любым предприятием – управляемый процесс, так как он определяется изменением состава оборудования, объемом поставок сырья, величиной финансирования и т. д. Совокупность решений, принимаемых в начале года, планируемого периода, по обеспечению предприятия сырьем, замене оборудования, размерам финансирования и т. д. является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции. Следовательно, выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов. Необходимо предусмотреть мероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т. е. по периодам времени. Последнее хотя и приводит к уменьшению первоначального объема выпускаемой продукции, но обеспечивает в дальнейшем возможность расширения производства. Таким образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов (шагов), на каждом из которых осуществляется влияние на его развитие.
Началом этапа (шага) управляемого процесса считается момент принятия решения (о величине капитальных вложений, о замене оборудования определенного вида и т. д.). Под этапом обычно понимают хозяйственный год.
Обычно на управление на каждом шаге u k накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Предполагая, что показатель эффективности k -го шага процесса зависит от начального состояния на этом шаге k -1 и от управления на этом шаге u k , получим целевую функцию всего многошагового процесса в виде:
.

Сформулируем теперь задачу динамического программирования : «Определить совокупность допустимых управлений (u 1 , …, u n ), переводящих систему из начального состояния ε 0 в конечное состояние ε n и максимизирующих или минимизирующих показатель эффективности F ».
Управление, при котором достигается максимум (минимум) функции F называется оптимальным управлением u * = (u 1* ,…, u n *).
Если переменные управления u k принимают дискретные значения, то модель ДП называется дискретной . Если переменные u k изменяются непрерывно, то модель ДП называется непрерывной .
В зависимости от числа параметров состояния s и числа управляющих переменных r различают одномерные и многомерные задачи ДП.
Число шагов в задаче может быть конечным или бесконечным .

Прикладные задачи динамического программирования

задача о планировании строительства объектов.

Для выбора оптимального решения при выполнении задач программирования иногда требуется перебирать большое количество комбинаций данных, что нагружает память персонального компьютера. К таким методам относится, например, метод программирования «разделяй и властвуй». В данном случае алгоритмом предусмотрено разделение задачи на отдельные мелкие подзадачи. Такой метод применяется только в тех случаях, когда мелкие подзадачи независимы между собой. Для того чтобы избежать выполнения лишней работы в том случае, если подзадачи взаимозависимы, используется метод динамического программирования, предложенный американцем Р.Беллманом в 50-х годах.

Суть метода

Динамическое программирование заключается в определении оптимального решения n-мерной задачи, разделяя ее n отдельных этапов. Каждый из них является подзадачей по отношению к одной переменной.

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

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

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

Метод усовершенствует выполнение задач, решаемых с помощью перебора вариантов или рекурсий.

Построение алгоритма задачи

Динамическое программирование предполагает построение такого алгоритма задач, при котором задача так разбивается на две или больше подзадач, чтобы ее решение складывалось из оптимального решения всех подзадач, входящих в нее. Далее возникает необходимость в написании рекуррентного соотношения и вычислении оптимального значения параметра для задачи в целом.

Иногда на 3-м шаге нужно дополнительно запоминать некоторую вспомогательную информацию о ходе выполнения каждой подзадачи. Это называется обратным ходом.

Применение метода

Динамическое программирование применяется при наличии двух характерных признаков:

оптимальность для подзадач;
наличие в задаче перекрывающихся подзадач.

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

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

Особенно эффективно применение динамического программирования тогда, когда по существу задачи нужно принимать решения поэтапно. Например, рассмотрим простой пример задачи замены и ремонта оборудования. Допустим, на литейной машине завода по изготовлению шин делают одновременно шины в двух разных формах. В том случае, если одна из форм выходит из строя, приходится машину разбирать. Понятно, что иногда выгоднее заменить и вторую форму для того, чтобы не разбирать машину на случай, если и эта форма окажется неработоспособной на следующем этапе. Тем более, бывает проще заменить обе работающие формы до того, как они начнут выходить из строя. Метод динамического программирования определяет наилучшую стратегию в вопросе о замене таких форм, учитывая все факторы: выгоду от продолжения эксплуатации форм, потери от простоя машины, стоимость забракованных шин и другое.