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

Основные понятия и определения

ТЕМА 19. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

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

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

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

Методом ДП опти­мизируют работу управляемых систем с аддитивной или мультипликативной целевой функцией.

Аддитивная ЦФ имеет вид

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

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

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

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

Математическая формулировка задачи. Общий доход W равен сумме доходов на отдельных шагах (годах):

Управление на каждом шаге состоит в том, что в начале i-го года предприятиям 1,2,…., k выделяются средства (первый индекс – номер шага (года), второй – номер предприятия). Управление на i-м шаге - вектор с k составляющими

.

Доход на каждом шаге зависит от вложенных средств. Так как управление u всей операцией состоит из совокупности всех шаговых управлений

,

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