Метод динамического программирования основан

5.3 Метод динамического программирования

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

Условием применимости метода является аддитивность целевой функции, т.е. возможность представления функции от переменных в виде суммы функции, каждая из которых зависит только от одной переменной:

.

К числу задач динамического программирования относятся задачи: о замене и загрузке оборудования; оптимального распределения ресурсов по этапам планирования; оптимального управления запасами; оптимального распределения капиталовложений и многие другие.

Рассмотрим модель нелинейного программирования

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

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

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

,

где – варианты условий начала-го шага.

Аналогично оптимизируется решение на предпоследнем -м шаге применительно к вариантам условий начала этого шага, но с учетом решений, найденных на-м шаге и т. д.

Уравнение Беллмана для шагов, начиная с предпоследнего до начала процесса, имеет вид:

,

где – варианты условий начала-го шага;

–функция Беллмана, найденная на предыдущем шаге.

При динамическом программировании многошаговый процесс проходят два раза:

1) от конца к началу – находят условные оптимальные решения на каждом шаге с учетом выигрыша на всех шагах, начиная с данного до конца;

2) от начала к концу – находят оптимальные шаговые решения на всех шагах.

5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования

Задача эффективного использования ресурсов. Имеется некоторое количество ресурса , которое можно использовать различными способами. Пусть–количестворесурса,используемое -м способом,– доход от использования ресурса-м способом ().

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

Модель оптимального использования ресурса имеет вид:

(5.13)

(5.14)

. (5.15)

Вместо одной оптимизационной задачи (5.13)-(5.15), с заданным количеством ресурса и содержащей неизвестных, в методе динамического программирования решаетсязадач, в каждой из которых максимум находится лишь по одной переменной. Таким образом, процесс поиска решения исходной задачи как бы разворачивается во времени по шагам.

На последнем шаге определяется функция

.

Для всех остальных шагов используется рекуррентное соотношение

, ,

здесь – количество ресурса, оставшееся для распределения к началу-го шага.

.

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

Задача 5.3 Необходимо составить план вложений денежных средств в три отделения предприятия, исходя из общей суммы средств, которая равна 250 денежным единицам.

Известны функции прибыли f_i(x_i) по каждому отделению, где x_i — средства, вкладываемые в i-е отделение (таблица 5.1). Размеры вложений ограничены: для первого отделения суммой 250 ден. ед., для второго отделения – 100 ден. ед.; для третьего — 250 ден. ед.

Найти оптимальное распределение денежных средств по отделениям, соответствующее максимуму суммарной но трем отделениям прибыли.

Таблица 5.1 – Функции прибыли по трем отделениям

Источник

Динамическое программирование: его преимущества и недостатки

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

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

Что такое динамическое программирование

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

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

Как следствие, Беллману понадобилось немало времени, чтобы выбрать подходящее название. Вместо слова «планирование», которые вызывало ассоциации с тем, что в это время происходило в Советском Союзе, он предложил вариант «программирование».

А слово «динамическое» оказалось удачным не только потому, что передавало суть методики, но и потому, что оно было понятным и его сложно было подменить чем-либо другим. Для Беллмана было важно, чтобы его термин нельзя было неправильно интерпретировать, исказить смысл. Отсюда и возникло понятие «динамическое программирование».

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

«Более мелкие подзадачи» – это то же самое, что «более простые». Другими словами, это задачи, входные данные для которых имеют меньший размер. Входными данными могут быть число, массив, совокупность настраиваемых параметров и т.д. Как пример, можно привести последовательность чисел Фибоначчи, N-й член которой обозначается как Ф(N).

Чтобы найти пятое число Фибоначчи Ф(5), сначала нужно получить третье Ф(3) и четвертое Ф(4) числа в этой последовательности, то есть необходимо решить те самые мелкие подзадачи.

Источник