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

из "Математические исследования операций в экономике "

Поскольку логарифм функции типа (5.2) является аддитивной функцией, достаточно ограничиться рассмотрением функций вида (5.1). [c.159]
Отметим, что в отличие от задач, рассмотренных в предыдущих главах, о линейности и дифференцируемости функций fa ) не делается никаких предположений, поэтому применение классических методов оптимизации (например, метода Лаг-ранжа) для решения задачи (5.3)-(5.4) либо проблематично, либо просто невозможно. [c.159]
Таким образом, динамическое программирование представляет собой целенаправленный перебор вариантов, который приводит к нахождению глобального максимума. Уравнение (5.1 1), выражающее оптимальное решение на й-м шаге через решения, принятые на предыдущих шагах, называется основным рекуррентным соотношением динамического программирования. В то же время следует заметить, что описанная схема решения при столь общей постановке задачи имеет чисто теоретическое значение, так как замыкает вычислительный процесс на построение функций Ak( ) (ft el я), т. е. сводит исходную задачу (5.3)-(5.4) к другой весьма сложной проблеме. Однако при определенных условиях применение рекуррентных соотношений может оказаться весьма плодотворным. В первую очередь это относится к задачам, которые допускают табличное задание функций Л ( ). [c.162]
Чтобы не усложнять обозначения, условимся операции целочисленной арифметики записывать стандартным образом, полагая, что промежуточные результаты подвергаются правильному округлению. Так, например, будем считать, что 12/5 = 2. [c.162]
Поскольку Ъ, jtj принимает конечное число целых значений от 0 доб/а,. Это позволяет, например, путем перебора значений (j ,) найти функцию Л,( ) и задать ее в форме таблицы следующей структуры (табл. 5.1). [c.163]
Последняя колонка табл. 5.1 (, ( )) содержит значение xl, на котором достигается оптимальное решение первого шага. Его необходимо запоминать для того, чтобы к последнему шагу иметь значения всех компонент оптимального плана. [c.163]
На последующих шагах с номером k ( е2 (я-1)) осуществляются аналогичные действия, результатом которых становятся таблицы значений ЛД ), где е 0,1. Ь] (см. табл. 5.2). [c.163]
Подчеркнем одно из преимуществ описанного метода с точки зрения его практической реализации в рамках программного обеспечения для ЭВМ на каждом шаге алгоритма непосредственно используется только таблица, полученная на предыдущем шаге, т. е. нет необходимости сохранять ранее полученные таблицы. Последнее позволяет существенно экономить ресурсы компьютера. [c.164]
Выигрыш, который дает применение рассмотренного алгоритма, может также быть оценен с помощью следующего простого примера. Сравним приблизительно по числу операций (состоящих, в основном, из вычислений целевой функции) описанный метод с прямым перебором допустимых планов задачи (5.3Ы5.4) при а =а2=...ап=1. [c.164]
Эффективность управления на каждом шаге k зависит от текущего состояния 4, выбранного управления xk и количественно оценивается с помощью функций fk(xk, Л), являющихся слагаемыми аддитивной целевой функции, характеризующей общую эффективность управления объектом. (Отметим, что в определение функции fk(xk, k) включается область допустимых значений xk, и эта область, как правило, зависит от текущего состояния .) Оптимальное управление, при заданном начальном состоянии , сводится к выбору такого оптимального плана х, при котором достигается максимум суммы значений fk на соответствующей траектории. [c.167]
Оптимальная стратегия управления должна удовлетворять следующему условию каково бы ни было начальное состояние на k-м шаге и выбранное на этом шаге управление xk, последующие управления (управленческие решения) должны быть оптимальными по отношению к состоянию k+l= k(xk9 %k), получающемуся в результате решения, принятого на шаге k. [c.168]
Важно еще раз подчеркнуть, что сформулированный выше принцип оптимальности применим только для управления объектами, у которых выбор оптимального управления не зависит от предыстории управляемого процесса, т. е. от того, каким путем система пришла в текущее состояние. Именно это обстоятельство позволяет осуществить декомпозицию задачи и сделать возможным ее практическое решение. [c.169]
В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспределенным ресурсом . При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется уже набором параметров ,, 2. т, и табулировать значения функций Ал( ,, %2. я) необходимо для многократно большего количества точек. Последнее обстоятельство делает применение метода динамического программирования явно нерациональным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал проклятием многомерности . В настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную информацию о них можно найти в специальной литературе [4, 5]. [c.169]

Вернуться к основной статье