33. Постановка задачи динамического программирования. Состояния системы. Управление. Уравнение состояний. Поясните смысл отсутствия последействия в динамической системе.

Система переходит из нач состояния S₀=S_нач в конечное S_кон

Это управления, где S₁…S_n – сост системы после 1-го, 2-го и т.д. шагов.

U_i- соотв управление.

Отсутствие последействия в ДС: S_k(k=1,2…k) зависит только от предыд сост S_k-1

Системы и послед управ-я u_k .

Уравнение сост-я: S_k=F_k( S_k-1,u_k), где F_k –задан.функ-я

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

Выбрать управлен сис таким образом, чтобы оптимиз-ть z₀ : z₀^#= opt z^#= z(S₀)

U^#= {u₁^#,…,u_n^#}

34. Эффективность шага в задаче динамического программирования. Как оценивается эффективность всего процесса всего процесса в задаче динамического программирования? Поясните обозначения.

Шаг S_k-1 S_k называется показателем существования эффективности.

f_k( S_k-1,u_k),

эф-ть всего процесса оценив-ся суммой z₀=f₁(S₀,u₁)+…+f_n(S_n-1,u_n), т.е.

суммы эффективности отд. Шагов z₀= ∑f_k(S_k-1,u_k)

S₁…S_n – сост системы после 1-го, 2-го и т.д. шагов.

U_i- соотв управление., F_k –задан.функ-я

35. Дайте определение функций z (s) в в задаче динамического программирования. Поясните обозначения.

Z_k=f_k+1(S_k,u_k+1)+…+f_n(S_n-1,,u_n)- показатель эффективности

…S_n – сост системы после 1-го, 2-го и т.д. шагов.

U_i- соотв управление., F_k –задан.функ-я

S_k=φ₁(u_k1)+φ₂(S_k-1-u_k-1)- ур-е сост-й.

36. Запишите уравнения Беллмана для общей задачи динамического программирования. Поясните обозначения. В каком порядке их решают?

Пусть найдена функция z₁^#(s₁), кот есть opt_u1 [f₂(S₁,u₂)+..+f_n(S_n-1,u_n)]

Тогда z₀^#(S₀)=opt [f₁(S₀,u₁)+ z₁^#(s₁)], где S₁=F₁(S₀,u₁) ….(1.1)

Это равенство служит для нахожд z₀ ,если известно z₁^#.

Z₁(S₁)=f₂(S₁,u₂)+[f₃(S₂,u₃)+..+f_n(S_n-1,u_n)]

Z₁ ^#(S₁)=opt _u2[ f2(S₁,u₂)+ Z₂ ^#(S₂)], где S₂=F₂(S₁,u2)…..(1.2)

Z_n-1^#(S_n-1)= opt_un(f_n(S_n-1,u_n))… (1.n)

Ур-я (1.1)-(1.n) наз-ся ур Беллмана. При их решении исп-я обратный ход вычисления процесса.

37. Непрерывная задача о распределении средств между предприятиями. Постановка задачи. Уравнения Беллмана.

f_1,f_2,φ_1, φ_2 Рассмотрим задачу о распределении средств S_0 между двумя п/п на n лет. Доход: f_1 (U_k )+f_2 (S_(K-1)-U_k) Уравнение состояния S_n=φ_1 (U_k )+φ_2 (S_(K-1)-U_k) Z_(n-1)^* (S_(n-1) )= max┬(0≤U_n≤S_(n-1) ) [f_1 (U_n )+f_2 (S_(n-1)-U_n )] Z_(n-2)^*=max┬(0≤U_n≤S_(n-2) )⁡〖[f_1 (U_(n-1) )〗+f_2 (S_(n-2)-U_(n-1) )+Z_(n-1)^* (S_(n-1))] …………………… Z_0^* (S_0 )=max┬(0≤U1≤S_0 )⁡〖[f_1 (U_1 )+f_2 (S_0-U_1 )〗+Z_1^* (S_1)

38. Дискретная задача о распределении средств между предприятиями. Постановка задачи. Уравнения Беллмана.

Планируется распределение начальной суммы млн. р. Между четырьмя предприятиями некоторого объединения. Средства выделяются только в размерах кратных a = 80млн. р. Решить задачу на основе уравнения Беллмана.

Функциональное уравнение Беллмана для нашей задачи имеет вид:

F_n (x_0)=max┬(0≤x≤x_0 )⁡〖(f_n (x)+F_(n-1) (x_0 〗-x)),n=(1,4,) ̅ где

F_1 (x)=f_1 (x) Первый шаг. Вычислим значения F_2 (x_0) по формуле: F_2 (x_0)=max┬(0≤x≤x_0 )⁡〖(f_2 (x)+F_1 (x_0 〗-x)) ,т.е. решим задачу для двух предприятий.  Второй шаг. Распределим вложения между тремя предприятиями. Будем использовать формулу: F_3 (x_0)=max┬(0≤x≤x_0 )⁡〖(f_3 (x)+F_2 (x_0 〗-x)). Затем аналогично вычислим F_4 (x_0).