Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Задача Джонсона Симплекс метод Метод прогонки Задача замены оборудования Задача распределения инвестиций Параметры сетевой модели Задача коммивояжера Многоканальные СМО

Уравнение Беллмана

Условиями, которым должна удовлетворять общая задача оптимизации, чтобы её можно было описать моделью ДП, являются следующие:
1. Задача должна интерпретироваться как n-шаговый процесс.
2. Целевая функция должна быть аддитивной, т. е. представляться в виде суммы показателей эффективности на каждом шаге.
3. Структура задачи должна быть определена для любого n и не зависеть от этого числа (принцип вложенности).
4. На каждом шаге система определяется конечным числом s параметров состояния и управляется конечным числом r переменных управления, причем s и r не зависят от k.
5. Выбор управления на k-м шаге не влияет на предшествующие шаги, а состояние в конце этого шага есть функция этого управления и предшествующего состояния (принцип отсутствия последействия).

Выполнение этих условий иногда оказывается очевидным, а иногда достигается после соответствующих преобразований. Чтобы построить модель ДП, необходимо выяснить, как на основе принципа оптимальности строится оптимальное уравнение n-шагового процесса.
Пусть система на k-м шаге под действием управления uk переходит из состояния εk-1в состояние εk. Из принципа отсутствия последействия имеем, что εk зависит только от εk-1 и uk.
Эти условия записываются в виде уравнений состояний:
εk = Tkk-1, uk), k = 1,..,n (5.1)
Из принципа оптимальности следует, что последующие управления uk+1, …, un должны выбираться оптимальными относительно состояния εk. Это значит, что при этих управлениях оптимизируется целевая функция на шагах k + 1 ,..., n.

Задача оптимизации процесса, начиная с (k + 1)-го шага, похожа на исходную задачу при начальном состоянии системы εk, управлении uk+1 = (uk+1 , …, un) и показателе эффективности Fk+1 = Fk+1k, uk+1, …, un). Выбрав оптимальное управление uk+1 = (u(k+1)*, …, un*) нa шагах k + 1,..., n, получим величину критерия , которая зависит только от εk – начального состояния для шагов k + 1,..., n.
Величина F*k+1k) называется условным максимумом.
Возникает задача, как выбрать оптимальное управление на k-м шаге, если известны оптимальные управления u(k+1)*,..., un* на последующих шагах k + 1,..., n и максимальное значение показателя эффективности F*k+1k) на этих шагах k + 1,...., n.
Так как состояние εk зависит от управления uk (5.1), то и величина F*k+1k) зависит от uk. Поэтому uk* необходимо выбирать так, чтобы это управление в совокупности с оптимальными управлениями u(k+1)*,..., un* приводило бы к общему максимуму показателя эффективности на шагах k + 1, …, n плюс данный шаг k. Аналитически это записывается так:

. (5.2)

Это основное функциональное уравнение динамического программирования – уравнение Беллмана.
Оптимальное управление на k-м шаге uk*, при котором достигается максимум (5.2), зависит от состояния k* в начале k-го шага uk* = uk*k-1) – это условное оптимальное управление на k-м шаге.
Отметим особенность уравнения (5.2) для k = n:
,
т. к. F*n+1 = 0, поскольку (n + 1) шага нет.

Общими рекомендациями при построении модели ДП являются следующие:
1. Выбирается способ деления процесса на шаги.
2. Вводятся параметры состояния εk = (ε1k,…, εsk) и переменные управления uk = (u1k,..,urk)
3. Записываются уравнения состояний εk = Tkk-1, u k)
4. Из ограничений задачи определяется для каждого шага множество допустимых управлений Dk.
5. Вводятся показатели эффективности fkk-1, u k) и суммарный показатель .
6. Вводятся условные максимумы показателя эффективности от k-го шага до конца процесса F*kk-1) и условные оптимальные управления на k-м шаге uk*k-1).
7. Записываются функциональные уравнения Беллмана:

Рассмотрим построение модели ДП на примере.
Задача 1. Планируется распределение начальной суммы средств ε0 между n предприятиями П1, П2, …, Пn. Выделение предприятию Пk средств uk приносит доход fk(uk), . Определить, какое количество средств нужно выделить каждому предприятию, чтобы обеспечить максимальный суммарный доход.
Математическая модель задачи имеет вид

Построим модель динамического программирования.
Распределение средств между n предприятиями можно рассматривать как n-шаговый процесс. Поэтому за номер k-го шага процесса примем номер предприятия, которому выделяются средства uk. Очевидно, что переменные uk, k=1,n можно рассматривать как управляющие переменные. Начальное состояние системы характеризуется начальной величиной средств ε0. В конце первого шага состояние системы ε1= ε0-u1 характеризуется остатком средств после выделения предприятию П1 средств u1. Величины ε0, ε1,…, εn характеризуют остаток средств после распределения на предшествующих шагах, будем рассматривать их как параметры состояний. Уравнения состояний в этом случае имеют вид
εk= εk-1-uk, k=1,n
Найдем допустимые управления. Рассмотрим k-й шаг. Предприятию Пk можно выделить любое количество из имеющих к началу шага средств εk-1. Поэтому допустимое управление uk удовлетворяет неравенствам 0 ≤uk ≤ εk-1.
Показателем эффективности каждого шага является доход fk(uk), суммарным показателем – суммарный доход .
Тогда условным максимумом F*kk-1) будет максимальный суммарный доход на шагах k,…, n с начальным состоянием k-го шага εk-1. Условное оптимальное управление u*kk-1) будет определять оптимальное количество средств, выделяемых предприятию Пk, если остаток средств для распределения εk-1. Запишем теперь функциональные уравнения Беллмана:
(5.3)
Эти уравнения Беллмана соответствуют обратному ходу вычислений, т. е. когда мы движемся от n-го шага к первому.

Требуются авторы студенческих работ!
  • регулярный поток заказов;
  • стабильный доход
Подробнее
Учебно-методический
  • курсы переподготовки и повышения квалификации;
  • вебинары;
  • сертификаты на публикацию методического пособия
Подробнее
Яндекс 360 для бизнеса
  • Бесконечный почтовый ящик;
  • Объем облачного хранилища от 100 Гб;
  • Загрузка больших файлов — от 1 ГБ
  • Поддержка файлов MS Office
  • Трансляции и их планирование в календаре
Подробнее
Курсовые на заказ