Вариант 8
Задание № 1.
Планируется распределение начальной суммы средств Е0 = 6 условных единиц между четырьмя предприятиями при условии, что средства выделяются в размерах, кратных одной условной единице, и функции дохода i-го предприятия заданы в таблице.
1
2
3
4
5
6
f1
2
3
5
6
7
8
f2
2
2
4
5
6
7
f3
2
2
5
6
7
8
f4
2
3
4
6
6
7
Определить, какое количество средств нужно выделить конкретному предприятию, чтобы получить наибольшую прибыль.
Решение.
В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай n=1, т.е. предположим, что все имеющиеся средства выделяются для одного предприятия. Обозначим через F1(x) максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме x. Каждому значению x отвечает вполне определенное (единственное) значение f1(c) дохода, поэтому можно записать, что:
(1)
В соответствии с формулой (1) в зависимости от начальной суммы c получаем с учетом таблицы 1 значения F1(E), помещенные в таблицу 2.
Таблица 2
Значения максимально возможного дохода в зависимости от выделенных средств
x1(E)
F1(E)
0
0
1
2
2
3
3
5
4
6
5
7
6
8
Пусть теперь n=2, т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма x, то доход на нем составит f2(x). Оставшиеся другому предприятию средства (E-x) в зависимости от величины x позволят увеличить доход до максимально возможного значения (1(E-x). При этом условии общий доход на двух предприятиях:
(2)
Оптимальному значению F2(E) дохода при распределении суммы с между двумя предприятиями соответствует такое x, при котором сумма (2) максимальна.
Это можно выразить записью:
(3)
Значение F3(E) можно вычислить, если известны значения F2(E), и т.д.
Функциональное уравнение Беллмана для рассматриваемой задачи запишется в следующем виде:
(4)
Теперь необходимо найти значения функции (3) для всех допустимых комбинаций Е и x. Рассматриваемому шагу соответствует таблица 3.
Таблица 3
Значения функции на втором шаге
Е\x
0
1
2
3
4
5
6
F2(E)
x2(E)
1
0+2
2+0
2
0,1
2
0+3
2+2
2+0
4
1
3
0+5
2+3
2+2
4+0
5
0,1
4
0+6
2+5
2+3
4+2
5+0
7
1
5
0+7
2+6
2+5
4+3
5+2
6+0
8
1
6
0+8
2+7
2+6
4+5
5+3
6+2
7+0
9
1
Для каждого значения (1,2,3,4,5,6) начальной суммы с распределяемых средств предусмотрена отдельная строка, а для каждого возможного значения x (0,1,2,3,4,5,6) распределяемой суммы – столбец. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям Е и x.
В каждую клетку таблицы будем вписывать значение суммы (2).
В двух последних столбцах таблицы проставлены максимальный по строке допол