Динамическое программирование

 

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

F1	F2	F3	X[i]
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.

E^2	U^3	E^3=E^2-U^3	F3(U^3)	F3*(E^3)	U3(E^3)
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.

E^1	U^2	E^2=e^1-u^2	F2(u^2)	F2*(e^1)	F1(u^2,e^1)	F2*(e^2)	U2(e^2)
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.

E^0	U^1	E^1=e^0-u^1	F1(u^1)	F1*(e^0)	F0(u^1,e^0)	F1*(e^1)	U1(e^1)
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.

 

Заключение

Делая этот реферат я для себя многое узнала про динамическое программирование, думаю это пригодится в будущем.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Использованная  литература

 

1. Материалы из Википедии – свободной энциклопедии                (http://ru.wikipedia.org): Веб-сайт, Системы управления контентом, Система     управления обучением, Moodle, Веб-форум ;
2. http://math.semestr.ru/dinam/tovar.php
3. http://www.bestreferat.ru/referat-62631.html