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

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

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

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

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

Рассмотрим общую постановку задачи этого программирования. Пусть исследуется некоторый экономический процесс, имеющий п последовательных этапов. На каждом 7-м этапе процесс может быть в разных состояниях бы, каждый из которых характеризуется конечным множеством параметров. С каждым этапом задачи связано принятие определенного управленческого решения хи, которое переводит систему из одного состояния в другое. Предполагается, что состояние si системы в конце 7-го этапа определяется только предыдущим состоянием si_1 и управлением хи на 7-м этапе и не зависит от предыдущих состояний и управлений. Тогда состояние si системы записывается в виде зависимости

Si = ф (в, _!, Хи), i = 1, П.

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

При названных условиях задача динамического программирования формулируется так: определить такую допустимую последовательность управленческих решений X = {x1, x2, хп}, которая переводит систему из начального состояния 50 в завершающий состояние sn и при которой достигается максимальная эффективность управления.

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

Максимум целевой функции на заключительном п-м этапе равна

^ п-О = шах / п ^ п-и хп).

Соответственно, на (п - 1) -етапи имеем

г * п-1 (5п-2) = ШaХ ((fn-1 (sn-2, хп-1) + г * п ^ п-1)).

Учитывая эту закономерность, для произвольного k-этапа можем записать рекуррентную зависимость

г * (пятый-1) = Шахи (Л (ик-1, хк) + г * + 1)).

Такая рекуррентная зависимость представляет собой математическую запись принципа оптимальности Беллмана.

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

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

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

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

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

4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных состояний sk и их количества п. Фактически здесь на каждом шагу решается не одна задача, а множество однотипных задач для различных состояний sk и различных к (1 <к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

Выводы

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

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

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

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

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

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

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

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

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X . Переменная определяет, в каких состояниях может оказаться система на данном k -м шаге. В зависимости от на этом шаге можно применить некоторые управления, которые характеризуются переменной . Применение управления на k -м шаге приносит некоторый результат и переводит систему в некоторое новое состояние . Для каждого возможного состояния на k -м шаге среди всех возможных управлений выбирается оптимальное управление такое, чтобы результат, который достигается за шаги сk -го по n -й оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана и зависит от номера шага k и состояния системы .

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

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

В общем случае задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состоянияв конечное состояние, при котором целевая функция
принимает наибольшее (наименьшее) значение.

Особенности математической модели динамического программирования заключаются в следующем:

задача оптимизации формулируется как конечный многошаговый процесс управления;

целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

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

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

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X .

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n -го по первый (на первом шаге k =1 состояние системы равно ее начальному состоянию ), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге, применение которого переведет систему в состояние
, зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнегоn -го шага.

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

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

О чём вообще речь? Что такое динамическое программирование?

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

Хорошо, как это использовать?

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

И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.

Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:

Вычислить n-й член последовательности, заданной формулами:
a 2n = a n ­+ a n-1 ,
a 2n+1 = a n — a n-1 ,
a 0 = a 1 = 1.

Идея решения

Здесь нам даны и начальные состояния (a 0 = a 1 = 1), и зависимости. Единственная сложность, которая может возникнуть - понимание того, что 2n - условие чётности числа, а 2n+1 - нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.

Рекурсивное решение

Очевидная реализация состоит в написании следующего метода:

Private static int f(int n){ if(n==0 || n==1) return 1; // Проверка на начальное значение if(n%2==0){ //Проверка на чётность return f(n/2)+f(n/2-1); // Вычисляем по формуле для чётных индексов, // ссылаясь на предыдущие значения }else{ return f((n-1)/2)-f((n-1)/2-1); // Вычисляем по формуле для нечётных //индексов, ссылаясь на предыдущие значения } }

И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть - мемоизация (кеширование значений).

Рекурсивное решение с кэшированием значений

Идея мемоизации очень проста - единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу - все действия в ней выполняются за O(1) , что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево .

Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:

Private static HashMap cache = new HashMap(); private static int fcashe(int n){ if(!cache.containsKey(n)){//Проверяем, находили ли мы данное значение cache.put(n, f(n)); //Если нет, то находим и записываем в таблицу } return cache.get(n); }

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

Последовательное вычисление

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

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

Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log 2 (N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.

Private static int f(int n){ if(n<2) return 1; //Может, нам и вычислять ничего не нужно? int fs = int[n]; //Создаём массив для значений fs=fs=1; //Задаём начальные состояния for(int i=2; i

Ещё одним минусом такого подхода является сравнительно большой расход памяти.

Создание стека индексов

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

Зависимости вычисляются следующим образом:

LinkedList stack = new LinkedList(); stack.add(n); { LinkedList queue = new LinkedList(); //Храним индексы, для которых ещё не вычислены зависимости queue.add(n); int dum; while(queue.size()>0){ //Пока есть что вычислять dum = queue.removeFirst(); if(dum%2==0){ //Проверяем чётность if(dum/2>1){ //Если вычисленная зависимость не принадлежит начальным состояниям stack.addLast(dum/2); //Добавляем в стек queue.add(dum/2); //Сохраняем, чтобы //вычислить дальнейшие зависимости } if(dum/2-1>1){ //Проверяем принадлежность к начальным состояниям stack.addLast(dum/2-1); //Добавляем в стек queue.add(dum/2-1); //Сохрнаяем, чтобы //вычислить дальнейшие зависимости } }else{ if((dum-1)/2>1){ //Проверяем принадлежность к начальным состояниям stack.addLast((dum-1)/2); //Добавляем в стек queue.add((dum-1)/2); //Сохрнаяем, чтобы //вычислить дальнейшие зависимости } if((dum-1)/2-1>1){ //Проверяем принадлежность к начальным состояниям stack.addLast((dum-1)/2-1); //Добавляем в стек queue.add((dum-1)/2-1); //Сохрнаяем, чтобы //вычислить дальнейшие зависимости } } /* Конкретно для этой задачи есть более элегантный способ найти все зависимости, здесь же показан достаточно универсальный */ } }

Полученный размер стека – то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172.

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

HashMap values = new HashMap(); values.put(0,1); //Важно добавить начальные состояния //в таблицу значений values.put(1,1); while(stack.size()>0){ int num = stack.removeLast(); if(!values.containsKey(num)){ //Эту конструкцию //вы должны помнить с абзаца о кешировании if(num%2==0){ //Проверяем чётность int value = values.get(num/2)+values.get(num/2-1); //Вычисляем значение values.add(num, value); //Помещаем его в таблицу }else{ int value = values.get((num-1)/2)-values.get((num-1)/2-1); //Вычисляем значение values.add(num, value); //Помещаем его в таблицу } }

Все необходимые значения вычислены, осталось только написать

Return values.get(n);

Конечно, такое решение гораздо более трудоёмкое, однако это того стоит.

Хорошо, математика - это красиво. А что с задачами, в которых не всё дано?

Для больше ясности разберём следующую задачу на одномерную динамику:

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Идея решения

На первую ступеньку можно попасть только одним образом - сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки - всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки - по одному маршруту на каждый маршрут до неё, со второй или с третьей - аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3) . Первые три ступеньки будем считать начальными состояниями.

Реализация через рекурсию

Здесь ничего хитрого нет.

Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх.

Int vars = new int; vars=1;vars=2;vars=4; for(int i=3; i

Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно.

Там вверху ещё было написано про какую-то двумерную динамику?..

С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё.

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

Идея решения

Логика решения полностью идентична таковой в задаче про мячик и лестницу - только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1) . Итого F(x,y) = F(x-1, y)+F(x,y-1) . Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут - по прямой вниз или по прямой вправо.

Реализация через рекурсию

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

Private static int f(int i, int j) { if(i==1 || j==1) return 1; return f(i-1, j)+f(i, j-1); }

Реализация через массив значений