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

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

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

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

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

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

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

1. задача коммивояжера;
2. задача о планировании строительства объектов.