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

Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X)зависит от количества реализованных партий товара Х и представлен в таблице.

Решение получаем через калькулятор.

Объем товара Х (в партиях) Доход G(X)
1 2 3
0 0 0 0
1 28 30 32
2 41 42 45
3 50 55 48
4 62 64 60
5 76 76 72

Решение:
Исходные данные.

f1 f2 f3 xi
0 0 0 0
28 30 32 1
41 42 45 2
50 55 48 3
62 64 60 4
76 76 72 5

I этап. Условная оптимизация.
1-ый шаг. k = 3.
e2 u3 e3 = e2 - u3 f3(u3) F*3(e3) u3(e3)
1 0 1 0
1 0 32 32 1
2 0 2 0
1 1 32
2 0 45 45 2
3 0 3 0
1 2 32
2 1 45
3 0 48 48 3
4 0 4 0
1 3 32
2 2 45
3 1 48
4 0 60 60 4
5 0 5 0
1 4 32
2 3 45
3 2 48
4 1 60
5 0 72 72 5
2-ой шаг. k = 2.
e1 u2 e2 = e1 - u2 f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
1 0 1 0 32 32 32 0
1 0 30 0 30
2 0 2 0 45 45
1 1 30 32 62 62 1
2 0 42 0 42
3 0 3 0 48 48
1 2 30 45 75 75 1
2 1 42 32 74
3 0 55 0 55
4 0 4 0 60 60
1 3 30 48 78
2 2 42 45 87 87 2
3 1 55 32 87
4 0 64 0 64
5 0 5 0 72 72
1 4 30 60 90
2 3 42 48 90
3 2 55 45 100 100 3
4 1 64 32 96
5 0 76 0 76
3-ий шаг. k = 1.
e0 u1 e1 = e0 - u1 f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
1 0 1 0 32 32 32 0
1 0 28 0 28
2 0 2 0 62 62 62 0
1 1 28 32 60
2 0 41 0 41
3 0 3 0 75 75
1 2 28 62 90 90 1
2 1 41 32 73
3 0 50 0 50
4 0 4 0 87 87
1 3 28 75 103 103 1
2 2 41 62 103
3 1 50 32 82
4 0 62 0 62
5 0 5 0 100 100
1 4 28 87 115
2 3 41 75 116 116 2
3 2 50 62 112
4 1 62 32 94
5 0 76 0 76

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

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

Решить эту задачу онлайн

Открыть диалог Discus Помощь в решении контрольных