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

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

В основе динамического программирования лежат 2 принципа:

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

Второй- принцип вложения: природа задачи, допускающая использование метода динамического программирования, не меняется при изменении числа шагов.

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

· небольшое число переменных

· * управляемый процесс- Марковский, т.е. предыстория не имеет значения при определении будущих действий

· * критерий эффективности J является аддитивным.

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

72. Составить математическую модель и записать функциональное уравнение Беллмана (рекуррентное соотношение), расшифровать все переменные и функции, входящие в него для следующей задачи:

Предприятие производит некоторое изделие, на которое оно имеет заказ на п месяцев.

Необходимо спланировать объем выпуска и хранения

продукции для каждого месяца его работы при условии, что суммарные затраты на производство и хранение продукции за п месяцев будут минимальными при полном удовлетворении спроса на продукцию. При этом уровень запасов к началу первого месяца задан, а к концу последнего . Известны также спрос на продукцию в каждом j-м месяце и затраты на производство и хранение единиц продукции в каждом j-ммесяце.

F(x₁, x₂, x₃, x₄) =f₁(x₁) + f₂(x₂) + f₃(x₃) + f₄(x₄)

x₁+x₂+x₃+x₄= Z(700)

g_k= max( f_k(x_k) + g_k-₁ (Z-x_k)) F= g₄(Z)

x_k= 0, 100, 200, 300, 400

G3 F3	0 100 200 300 400

g₃(400) =105

73.Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:

Предполагается, что принимают целые неотрицательные значения.

2). Пусть требуется загрузить в самолет грузоподъемностью W тоннгруз, состоящий из предметов п различных типов, таким образом, чтобы стоимость всего груза была

максимальной. Для каждого предмета j-го типа, j= 1,2,. . . ,п, заданы вес в тоннах и

стоимость в тысячах рублей одного предмета этого типа, где все и -целые

положительные числа. Причем предметов каждого типа можно загружать в самолет по несколько штук.

Ур-ние Беллмана: F_k*(ξ) = max {f_k (x_k) + F_k-1(ξ-x_k)} = f_k( ) + F(ξ- )

0 x_k ξ x_k

0 ξ b

F_k*(ξ) – max приращение прибыли по k предприятиям.

74.Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:

Средства в размере b млн. рублей распределяются между п предприятиями в количествах,

кратных а млн. руб., причем - целое число. При выделении j-му предприятию млн. рублей оно приносит доход млн. рублей.Требуется распределить выделенные средства так, чтобы суммарный доход по всем предприятиям был максимальным.

Ур-ние Беллмана: F_k*(ξ) = max {f_k (x_k) + F_k-1(ξ-x_k)} = f_k( ) + F(ξ- )

0 x_k ξ x_k

0 ξ b

F_k*(ξ) – max приращение прибыли по k предприятиям.

Обозначим через прирост мощности или прибыли на i-м предприятии, если оно получит рублей капитальных вложений. Требуется найти такое распределение капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

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

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

75. Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:

Предприятие может производить п видов изделий, располагая некоторым ресурсом в объеме

b единиц (b - целое положительное число). Известны затраты ресурса на изготовление

одного изделия j-го вида, а также известна ожидаемая прибыль с_j от реализации одного

изделия j-го вида ( . - целые положительные числа), j = 1, 2,..., п.

Требуется составить план выпуска изделий, максимизирующий суммарную прибыль.

Требуется найти такой план выпуска изделий (x₁,x₂, ... , x_n), которое максимизирует суммарную прибыль: z = c₁x₁ + c₂х₂ + ... + c_nx_n

при ограниченности ресурсов:

причем все переменные x_j принимают только целые неотрицательные значения: x_j = 0, 1, 2 ...

За параметр состояния x принимаем количество ресурсов, выделяемых для производства нескольких видов изделий, а функцию состояния С_k(x) определим как максимальную прибыль при производстве k видов изделий, если для их производства имеется x единиц ресурса, функцию А_k(x) как издержки при производстве k видов изделий, если для их производства имеется x единиц ресурса. Параметр x может изменяться от 0 до b.

F_k(x)=max{(c_k-a_k) x_k + С_k-1(x-x_k)-A _k-1(x-x_k)}, 0 £ x_k £ x

76. Составить математическую модель и записать функциональное уравнение Беллмана
(рекуррентное соотношение), расшифровать все переменные и функции, входящие в него
для следующей задачи:

Пусть п предприятиями некоторого объединения должен быть произведен определенный

продукт в количестве bединиц. При изготовлении х_j единиц продукта на j-м предприятии

издержки составляют денежных единиц. Требуется спланировать производство