Динамическое программирование

Курсовая
работа по теории
оптимального
управления
экономическими
системами.

Тема : Задача
динамического
программирования.

I.Основные
понятия и
обозначения.

Динамическое
программирование
– это математический
метод поиска
оптимального
управления,
специально
приспособленный
к многошаговым
процессам.
Рассмотрим
пример такого
процесса.

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

Ставится
вопрос : как в
начале каждого
года распределять
имеющиеся
средства между
предприятиями,
чтобы суммарный
доход от всех
предприятий
за N
лет был
максимальным?

Перед нами
типичная задача
динамического
программирования,
в которой
рассматривается
управляемый
процесс –
функционирование
группы предприятий.
Управление
процессом
состоит в
распределении
(и перераспределении)
средств. Управляющим
воздействием
(УВ) является
выделене каких-то
средств каждому
из предприятий
в начале года.

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

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

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

N
– число
шагов.

–
вектор,описывающий
состояние
системы на k-м
шаге.

–
начальное
состояние, т.
е. cостояние
на 1-м шаге.

–
конечное
состояние, т.
е. cостояние на
последнем шаге.

Xk
– область
допустимых
состояний на
k-ом
шаге.

–
вектор
УВ на k-ом
шаге, обеспечивающий
переход системы
из состояния
xk-1
в состояние
xk.

Uk
– область
допустимых
УВ на k-ом
шаге.

Wk
– величина
выигрыша, полученного
в результате
реализации
k-го
шага.

S –
общий выигрыш
за N
шагов.

–
вектор
оптимальной
стратегии
управления
или ОУВ за N
шагов.

Sk+1()
– максимальный
выигрыш, получаемый
при переходе
из любого состояния
в
конечное состояние
при оптимальной
стратегии
управления
начиная с (k+1)-го
шага.

S1()
– максимальный
выигрыш, получаемый
за N
шагов при
переходе системы
из начального
состояния
в конечное
при реализации
оптимальной
стратегии
управления
.
Очевидно, что
S = S1(),
если
–фиксировано.

Метод
динамического
программирования
опирается на
условие отсутствия
последействия
и условие
аддитивности
целевой функции.

Условие
отсутствия
последействия.
Состояние
,
в которое перешла
система за один
k-й
шаг, зависит
от состояния
и выбранного
УВ
и не зависит
от того, каким
образом система
пришла в состояние
,
то есть

Аналогично,
величина выигрыша
Wk
зависит
от состояния
и выбранного
УВ
,
то есть

Условие
аддитивности
целевой функции.
Общий выигрыш
за N
шагов вычисляется
по формуле

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

Условие
отсутствия
последействия
позволяет
сформулировать
принцип оптимальности
Белмана.

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

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

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

Поставленная
задача является
задачей оптимального
управления,
а управление,
при котором
показатель
S
достигает
максимума,
называется
оптимальным.
Оптимальное
управление
многошаговым
процессом
состоит из
совокупности
оптимальных
шаговых управлений:

Таким образом,
перед нами
стоит задача:
определить
оптимальное
управление
на каждом шаге
(i=1,2,...N)
и, значит, оптимальное
управление
всем процессом
.

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

Мы отметили,
что планируя
многошаговый
процесс, необходимо
выби­рать УВ
на каждом шаге
с учетом его
будущих последствий
на еще пред­стоящих
шагах. Однако,
из этого правила
есть исключение.
Среди всех
шагов существует
один, который
может планироваться
без "заглядыва-ния
в будущее".
Какой это шаг?
Очевидно, последний
— после
него дру­гих
шагов нет. Этот
шаг, единственный
из всех, можно
планировать
так, чтобы он
как таковой
принес наибольшую
выгоду. Спланировав
опти­мально
этот последний
шаг, можно к
нему пристраивать
предпоследний,
к предпоследнему
— предпредпоследний
и т.д.

Поэтому процесс
динамического
программирования
на 1-м этапе
раз­ворачивается
от конца к началу,
то есть раньше
всех планируется
послед­ний,

N-й
шаг. А как его
спланировать,
если мы не знаем,
чем кончился
предпоследний?
Очевидно, нужно
сделать все
возможные
предположе­ния
о том, чем кончился
предпоследний,
(N
— 1)-й шаг, и
для каждого
из них найти
такое управление,
при котором
выигрыш (доход)
на послед­нем
шаге был бы
максимален.
Решив эту задачу,
мы найдем условно
оптимальное
управление
(УОУ) на N-м
шаге, т.е. управление,
которое надо
применить, если
(N —
1)-й шаг закончился
определенным
образом.

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

(N
— 1)-го шага
мы знаем УОУ
на N-м
шаге и соответствующий
ему условно
оптимальный
выигрыш (УОВ).
Теперь мы можем
оптими­зировать
управление
на предпоследнем,
(N
— 1)-м шаге. Сделаем
все возможные
предположения
о том, чем кончился
предпредпоследпий,
то есть
(N
— 2)-й шаг, и
для каждого
из этих предположений
найдем такое
управление
на (N —
1)-м шаге, чтобы
выигрыш за
последние два
ша­га (из которых
последний уже
оптимизирован)
был максимален.
Далее оптимизируется
управ чение
на (N —
2)-м шаге, и т.д.

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

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

Действительно,
пусть нам известно
начальное
состояние
процесса. Те­перь
мы уже знаем,
что делать на
первом шаге:
надо применить
УОУ, найденное
для первого
шага и начального
сосюяния. В
результате
это­го управления
после первого
шага система
перейдет в
другое состояние;
но для этого
состояния мы
знаем УОУ и г
д. Таким образом,