Контрольная на тему Контрольная работа 120109-02

Вариант 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).
В двух последних столбцах таблицы проставлены максимальный по строке допол