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

Назначение сервиса. Онлайн-калькулятор предназначен для решения задачи оптимального распределения ресурсов заданных в виде функций f(x). Результаты вычислений оформляются в отчете формата Word (см. пример оформления).
Инструкция. Выберите количество предприятий.
Количество предприятий

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

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

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

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

Итак, для третьего последнего этапа имеем: f3(a3) = 4a3, x3 = 0,y3 = a3 - x3 = a3,
где a3 = 0,3x2 + 0,2a2, что следует из формулы (3).

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

II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год. Так как x1 = a1 и , y1 = 0, то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год. Выделяются средства a2 = 0,3x1 + 0,2a1 = 0,5 a1 =450 ед., x2 = a2 , y2 = 0.
Все они передаются первому предприятию.
3-й год. Выделяются средства a3 = 0,3x2 + 0,2a2 = 0,5 a2 = 225 ед., x3 = 0, y3 = a3 . Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.

Период Средства Предприятие №1 Предприятие №2 Остаток Доход
1 900 900 0 450 2700
2 450 450 0 225 1350
3 225 0 225 45 900
4950

Пример №2. Оптимальное поэтапное распределение средств между предприятиями в течении планового периода.
Руководство фирмы, имеющей договор о сотрудничестве с тремя малыми предприятия, на плановый годовой период выделила для них оборотные средства в объеме 100000 у.е. Для каждого предприятия известны функции поквартального дохода и поквартального остатка оборотных средств в зависимости от выделенной на квартал суммы x. В начале квартала средства распределяются полностью между тремя предприятиями (из этих вложенных средств и вычисляется доход), а по окончанию квартала остатки средств аккамулируются у руководства фирмы и снова распределяются полностью между предприятиями.
Составить план поквартального распределения средств на год (4 квартала), позволяющего достичь максимальный общий доход за год.
f1(x)=1,2x, f2(x)=1.5x, f3(x)=2x; g1(x)=0.7x, g2(x)=0.6x, g3(x)=0.1x
Открыть диалог Discus Помощь в решении