ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
1. Выберите соответствующий вариант с данными и решите следующую задачу.
Имеются четыре предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятиях в зависимости от выделенных средств X представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.
12
X QUOTE (x) QUOTE (x) QUOTE (x) QUOTE (x)
20 22 24 28 25
40 38 32 46 33
60 45 44 57 46
80 52 56 67 58
100 51 69 70 58
Решение:
Запишем исходные данные в следующем виде:
f1 f2 f3 f4 xi
0 0 0 0 0
22 24 28 25 20
38 32 46 33 40
45 44 57 46 60
52 56 67 38 80
51 69 70 58 100
I этап. Условная оптимизация.
1-ый шаг. k = 4.
Предположим, что все средства в количестве x4 = 100 отданы предприятию №4. В этом случае, максимальный доход, как это видно из таблицы, составит f4(u4) = 58, следовательно, F4(e4) = f4(u4)
e3 u4 e4 = e3 – u4 f4(u4) F*4(e4) u4(e4)
20 0 20 0
20 0 25 25 20
40 0 40 0
20 20 25
40 0 33 33 40
60 0 60 0
20 40 25
40 20 33
60 0 46 46 60
80 0 80 0
20 60 25
40 40 33
60 20 46 46 60
80 0 38
100 0 100 0
20 80 25
40 60 33
60 40 46
80 20 38
100 0 58 58 100
2-ый шаг. k = 3.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F3(e3) = max(x3 ≤ e3)(f3(u3) + F4(e3-u3))
e2 u3 e3 = e2 – u3 f3(u3) F*3(e2) F2(u3,e2) F*3(e3) u3(e3)
20 0 20 0 25 25
20 0 28 0 28 28 20
40 0 40 0 33 33
20 20 28 25 53 53 20
40 0 46 0 46
60 0 60 0 46 46
20 40 28 33 61
40 20 46 25 71 71 40
60 0 57 0 57
80 0 80 0 46 46
20 60 28 46 74
40 40 46 33 79
60 20 57 25 82 82 60
80 0 67 0 67
100 0 100 0 58 58
20 80 28 46 74
40 60 46 46 92 92 40
60 40 57 33 90
80 20 67 25 92
100 0 70 0 70
3-ый шаг. k = 2.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №2, 3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F2(e2) = max(x2 ≤ e2)(f2(u2) + F3(e2-u2))
e1 u2 e2 = e1 – u2 f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
20 0 20 0 28 28 28 0
20 0 24 0 24
40 0 40 0 53 53 53 0
20 20 24 28 52
40 0 32 0 32
60 0 60 0 71 71
20 40 24 53 77 77 20
40 20 32 28 60
60 0 44 0 44
80 0 80 0 82 82
20 60 24 71 95 95 20
40 40 32 53 85
60 20 44 28 72
80 0 56 0 56
100 0 100 0 92 92
20 80 24 82 106 106 20
40 60 32 71 103
60 40 44 53 97
80 20 56 28 84
100 0 69 0 69
4-ый шаг. k = 1.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №1, 2, 3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F1(e1) = max(x1 ≤ e1)(f1(u1) + F2(e1-u1))
e0 u1 e1 = e0 – u1 f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
20 0 20 0 28 28 28 0
20 0 22 0 22
40 0 40 0 53 53 53 0
20 20 22 28 50
40 0 38 0 38
60 0 60 0 77 77 77 0
20 40 22 53 75
40 20 38 28 66
60 0 45 0 45
80 0 80 0 95 95
20 60 22 77 99 99 20
40 40 38 53 91
60 20 45 28 73
80 0 52 0 52
100 0 100 0 106 106
20 80 22 95 117 117 20
40 60 38 77 115
60 40 45 53 98
80 20 52 28 80
100 0 51 0 51
Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 4-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 4-го шага имеем F*1(e0 = 100) = 117. То есть максимальный доход всей системы при количестве средств e0 = 100 равен 117
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 100) = 20
При этом остаток средств составит:
e1 = e0 – u1 = 100 – 20 = 80
Из таблицы 3-го шага имеем F*2(e1 = 80) = 95. То есть максимальный доход всей системы при количестве средств e1 = 80 равен 95
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 80) = 20
При этом остаток средств составит:
e2 = e1 – u2 = 80 – 20 = 60
Из таблицы 2-го шага имеем F*3(e2 = 60) = 71. То есть максимальный доход всей системы при количестве средств e2 = 60 равен 71
Из этой же таблицы получаем, что 3-му предприятию следует выделить *3(e2 = 60) = 40
При этом остаток средств составит:
e3 = e2 – u3 = 60 – 40 = 20
Последнему предприятию достается 20
Итак, инвестиции в размере 100 необходимо распределить следующим образом:
1-му предприятию выделить 20,
2-му предприятию выделить 20,
3-му предприятию выделить 40,
4-му предприятию выделить 20,
что обеспечит максимальный доход, равный 117.
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
2. Выберите соответствующий вариант с данными и решите задачу.
Найти оптимальный план замены оборудования на 6-летний период, если известны производительность оборудования r(t) и остаточная стоимость оборудования S(t) в зависимости от возраста, стоимость нового оборудования P (
