Планируется распределение начальной суммы S0 = 80 усл. ед. между четырьмя предприятиями, причем средства выделяются только в размерах, кратных 20 усл. ед. Предполагается, что выделенные предприятию в начале планового периода средства x приносят прибыль fk(x).
Считать, что:
1) прибыль fk(x), полученная от вложения средств в предприятие, не зависит от вложения средств в другие предприятия;
2) прибыль, полученная от разных предприятий, выражается в одинаковых условных единицах;
3) суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.
Функции fk(x) заданы в таблице:
x f1(x) f2(x) f3(x) f4(x)
20 14 2 2 10
40 15 5 4 11
60 18 6 8 16
80 19 7 12 22
Задание.
1. Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей (используйте принцип оптимальности и уравнения Беллмана).
2. Приведите расчетные таблицы (возможно использование Excel).
3. Опишите особенности модели.
Решение
Составляем математическую модель задачи. Пусть xk количество средств, выделенных k-тому предприятию таким образом, что суммарная прибыль F достигает максимума F = max при выполнении условий = 80, xk ≥ 0, xk {20, 40, 60, 80}.
Распределение средств между четырьмя предприятиями рассматривается как четырехшаговый процесс, на каждом шаге которого выделяются средства xk соответствующему предприятию. При этом Sk – нераспределенные средства после k-того шага. Первоначально S0 = 80, а после четвертого шага все средства должны быть распределены, то есть S4 = 0.
Для произвольного k (0 ≤ k ≤ 4) оставшиеся нераспределенными после k-того шага средства Sk связаны с распределяемыми на этом шаге средствами xk и остатком средств после предыдущего шага Sk–1 следующим соотношением: Sk = Sk–1 – xk (k = 1,2,3,4).
Будем рассматривать Fk*(Sk–1) – условно оптимальную прибыль, полученную от k-го, …, 4-го предприятий, если между ними оптимально распределены средства Sk–1 (0 ≤ Sk–1 ≤ 80). Средства xk, распределяемые на k-том шаге, удовлетворяют условию 0 ≤ xk ≤ Sk–1 (k-тому предприятию либо ничего не выделяется, либо выделяется не более того, что имеется к k-тому шагу).
В соответствии с принципом оптимальности Беллмана, на каждом шаге нужно выделять средства xk так, чтобы в совокупности с оптимальным распределением на всех последующих шагах получить наибольшую суммарную прибыль. Применение принципа оптимальности на каждом шаге приводит к следующим уравнениям Беллмана:
(a) k = 4; S4 = 0; F4*(S3) = {f4(x4)};
(b) k = 3; F3*(S2) = {f3(x3) + F4*(S3)};
(c) k = 2; F2*(S1) = {f2(x2) + F3*(S2)};
(d) k = 1; F1*(S0 = 80) = {f1(x1) + F2*(S1)}.
Эти уравнения следует решать последовательно, проводя условную оптимизацию на каждом шаге, начиная с последнего четвертого предприятия
.
Этап I. Условная оптимизация.
4-ый шаг; k = 4.
В исходной таблице f4(x) – возрастающая функция, поэтому все средства, оставшиеся к четвертому шагу, необходимо для получения максимальной прибыли вложить в это четвертое предприятие, то есть, в соответствии с (a), имеем F4*(S3) = {f4(x4)} = f4(S3); при этом x4*(S3) = S3.
Распределяемые средства, оставшиеся к четвертому шагу; S3 Средства, выделяемые четвертому предприятию; x4 Остаток; S4 = S3 – x4 Прибыль; f4(x4) F4*(S3) x4*(S3)
0 0 0 0 0 0
20 20 0 10 10 20
40 40 0 11 11 40
60 60 0 16 16 60
80 80 0 22 22 80
3-ий шаг; k = 3.
Решаем уравнение (b). Делаем все предположения об остатках средств S2 к третьему шагу. Остаток средств S2 может принимать значения 0, 20, 40, 60, 80. В зависимости от этого выбираем 0 ≤ x3 ≤ S2, находим S3 = S2 – x3 и находим максимум выражения {f3(x3) + F4*(S3)}. Для каждого S2 наибольшее из этих значений есть условно оптимальная прибыль, полученная при оптимальном распределении средств S2 между третьим и четвертым предприятиями.
S2 x3 S3 = S2 – x3 f3(x3) {f3(x3) + F4*(S3)} F3*(S2) x3*(S2)
0 0 0 0 0 + 0 = 0 0 0
20 0 20 0 0 + 10 = 10 10 0
20 0 2 2 + 0 = 2
40 0 40 0 0 + 11 = 11
20 20 2 2 + 10 = 12 12 20
40 0 4 4 + 0 = 4
60 0 60 0 0 + 16 =16 16 0
20 40 2 2 + 11 = 13
40 20 4 4 + 10 = 14
60 0 8 8 + 0 = 8
80 0 80 0 0 + 22 = 22 22 0
20 60 2 2 + 16 = 18
40 40 4 4 + 11 = 15
60 20 8 8 + 10 = 18
80 0 12 12 + 0 = 12
2-ой шаг; k = 2.
Решаем уравнение (c)
Задать вопрос
на новый заказ в Автор24.
