Задача распределения ресурсов

• Шаг №1
• Шаг №2
• Видеоинструкция

Пример №1. Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0. Средства x, вложенные в 1-е предприятие в начале года, дают в конце года прибыль f1(x), и возвращаются в размере g1(x). Средства y, вложенные в 2-е предприятие в начале года, дают в конце года прибыль f2(y) и возвращаются в размере g2(y). В конце года возвращенные средства заново перераспределяются между отраслями. Определить оптимальный план распределения средств и найти максимальную прибыль.

Задачу решим методом динамического программирования. Операцию управления производственным процессом разобьём на этапы. На каждом из них управление выберем так, чтобы оно приводило к выигрышу как на данном этапе, так и на всех последующих до конца операции. В этом состоит принцип оптимальности, сформулированный американским математиком А. Беллманом.
Разобьём весь период на три этапа по годам и будем нумеровать их, начиная с первого.
Обозначим через x_k и y_k количество средств выделяемых каждому предприятию на k-ом этапе, а через x_k + y_k = a_k – общее количество средств на этом этапе. Тогда первое предприятие приносит на этом этапе 3 x_k, а второе 4 y_k единиц дохода. Общий доход на k-ом этапе 3x_k + 4y_k.
Обозначим через f_k (a_k) – максимальный доход, который получает отрасль от обоих предприятий на k-ом и всех последующих. Тогда функциональное уравнение, отражающее принцип оптимальности Беллмана, принимает вид:
f_k (a_k)=max{3x_k + 4y_k + f_k+1 (a_k+1)}. (1)
Так как x_k + y_k = a_k, то y_k = a_k - x_k и 3x_k + 4y_k = 3x_k + 4(a_k - x_k) = - x_k + 4a_k. Поэтому f_k(a_k) = max{-x_k + 4a_k + f_k+1(_ak+1)}. (2)
0 ≤ x_k ≤ a_k
Кроме того, ak – это средства выделяемые обои предприятиям на k-ом этапе, и они определяются остатком средств, получаемых на предыдущем (k-1)-ом этапе. Поэтому по условию задачи оптимальное управление на каждом этапе
a_k = 0,5x_k-1 + 0,2y_k-1 = 0,5x_k-1+0,2(a_k-1 - x_k-1) = 0,3x_k-1+0,2a_k-1. (3)

I.Условия оптимизации
Планирование начинаем с последнего третьего этапа

При k = 3 получаем из (2)
f₃(a₃) = max {- x₃ + 4a₃ + f₄(a₄)}
0 ≤ x₃ ≤ a₃
Так как четвёртого этапа нет, то f₄(a₄)=0 и
f₃(a₃) = max {- x₃ + 4a₃}=4a₃
0 ≤ x₃ ≤ a₃
(максимум выражения (- x₃ + 4a₃) будет при x₃ =0)).

Итак, для третьего последнего этапа имеем: f₃(a₃) = 4a₃, x₃ = 0,y₃ = a₃ - x₃ = a₃,
где a₃ = 0,3x₂ + 0,2a₂, что следует из формулы (3).

При k = 2 из (2) и (3) получаем:
f(a₂) = max {-x₂ + 4a₂ + f₃(a₃)}=
0 ≤ x ≤ a₂
= max {-x₂ + 4a₂ + 4a₃}= max {-x₂ + 4a₂ + 4(0,3x₂ + 0,2a₂)} max{0,2x₂ + 4,8a₂} 5a
0 ≤ x ≤ a₂
т. к. максимум выражения (0,2x₂ + 4,8a₂) будет при x₂ = a₂.
То для второго этапа имеем: f ₂(a₂) = 5a₂ , x₂ = a₂ , y₂ = a₂ x₂ = 0 , при этом
a₂ = 0,3x₁ + 0,2a₁ с учетом (3).
При k = 1 с учетом (2) и (3) получаем:
f₁(a₁) = max {-x₁ + 4a₁ + f₂(a₂)}=
0 ≤ x ≤ a₁
= max {-x₁ + 4a₁ + 5a₂}= max {-x₁ + 4a₂ + 5(0,3x₁ + 0,2a₂)}= max {0,5x₁ + 5a₁}=5,5a₁
0 ≤ x ≤ a₁
при x₁ = a₁.
Итак, для первого этапа f₁(a₁) = 5,5a₁, x₁ = a₁, y₁ = 0.
Процесс закончен. На первом этапе общее количество распределяемых средств известно –a₁ = 900 ед. Тогда максимальный доход, получаемый обоими предприятиями за три года составит f₁(a₁) = 5,5*900 = 4950 ден. ед.

II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год. Так как x₁ = a₁ и , y₁ = 0, то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год. Выделяются средства a₂ = 0,3x₁ + 0,2a₁ = 0,5 a₁ =450 ед., x₂ = a₂ , y₂ = 0.
Все они передаются первому предприятию.
3-й год. Выделяются средства a₃ = 0,3x₂ + 0,2a₂ = 0,5 a₂ = 225 ед., x₃ = 0, y₃ = a₃ . Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.

Задача распределения средств на два года