Пример решения задачи динамического программирования

Задача. Планируется распределение начальной суммы средств e0 = 40 млн руб., причем средства выделяются кратно 10 млн руб. между тремя предприятиями П1, П2, П3. Выделение предприятию Пk средств uk приносит доход fk(uk), который задан в табл. Определить, какое количество средств нужно выделить каждому предприятию, чтобы обеспечить максимальный суммарный доход.

x 0 10 20 30 40
f1(x) 0 4 5 7 8
f2(x) 0 3 3 4 6
f3(x) 0 4 4 5 6

Решение находим с помощью калькулятора.
I этап. Условная оптимизация.
1-ый шаг. k = 3.

e2 u3 e3 = e2 - u3 f3(u3) F*3(e3) u3(e3)
10
 
0 10 0 4  10
10 0 4
20 0 20 0
 4
 

 10
 
10 10 4
20 0 4
30 0 30 0 5 30
10 20 4
20 10 4
30 0 5
40 0 40 0 6 40
10 30 4
20 20 4
30 10 5
40 0 6


2-ый шаг. k = 2.

e1 u2 e2 = e1 - u2 f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
10
 
0 10 0 4 4 4
 
0
10 0 3 0 3
20 0 20 0 4 4  7
 
10
10 10 3 4 7
20 0 3 0 3
30 0 30 0 5 5  7
 
10
10 20 3 4 7
20 10 3 4 7
30 0 4 0 4
40 0 40 0 6 6 8 10
10 30 3 5 8
20 20 3 4 7
30 10 4 4 8
40 0 6 0 6


3-ый шаг. k = 1.

e0 u1 e1 = e0 - u1 f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
10
 
0 10 0 4 4 4 0
10 0 4 0 4
20 0 20 0 7 7 8 10
10 10 4 4 8
20 0 5 0 5
30 0 30 0 7 7 11 10
10 20 4 7 11
20 10 5 4 9
30 0 7 0 7
40 0 40 0 8 8 12 20
10 30 4 7 11
20 20 5 7 12
30 10 7 4 11
40 0 8 0 8

Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.
Из таблица 1-го шага имеем F*3(e0 = 40) = 12. То есть максимальный доход всей системы при количестве средств e0 = 40 равен 12
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 40) = 20
При этом остаток средств составит:
e1 = e0 - u1
e1 = 40 - 20 = 20
Из таблица 2-го шага имеем F*2(e1 = 20) = 7. То есть максимальный доход всей системы при количестве средств e1 = 20 равен 7
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 20) = 10
При этом остаток средств составит:
e2 = e1 - u2
e2 = 20 - 10 = 10
Последнему предприятию достается 10
Итак, максимальный доход в количестве 40 будет получен, если:
1-му предприятию выделить 20
2-му предприятию выделить 10
3-му предприятию выделить 10
Что обеспечит максимальный доход, равный 12

загрузка...