Постановка задачи

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

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

Рассмотрим пример. Самолёт авиатранспортной компании загружается промышленным оборудованием 3 типов. Каждый предмет оборудования i-го типа (таблица 1) имеет вес w_i (в тоннах) и стоимость v_i (в тыс. рублей). Максимальная грузоподъёмность самолёта равна 5 тоннам. Какова наибольшая стоимость груза, которую может перевезти самолёт за один рейс?

Таблица1

Это простой пример, он решается перебором вариантов. Ясно, что наиболее выгодно перевезти 2 предмета 1-го типа и 1 предмет 3-го типа общей стоимостью 160 тыс. рублей. При увеличении типов предметов задача станет не такой простой, процедура перебора окажется громоздкой.

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

Имеется экономическая система, текущее состояние которой описывается вектором состояния , - i-ый показатель состояния системы. Состояние системы может изменяться под действием вектора управления , - мера управляющего воздействия j-го типа. Тогда модель управления системой.

Пусть управление системой не непрерывно во времени t, а происходит дискретно, в конце каждого из промежутков времени (t₀ , t₁], (t₁ , t₂], …, (t_n-1 , t_n]. В моменты времени t₁, t₂, …, t_n принимаются управляющие решения . Поэтому в период (t_k-1 , t_k) сохраняется состояние , наступившее после принятия решения в момент времени t_k-1.

Упрощающие предположения.

а) Состояние системы в момент t_k зависит только от состояния на предыдущем шаге и принятого в момент t_k решения:

б) Состояние системы в период (t_k-1, t_k) характеризуется числом – эффективностью ; эффективность аддитивна по шагам:

,

в) Система не должна иметь обратной связи, то есть принятие решения не влияет на состояния .

г) Состояние задано.

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