Разработка управленческих решений

Подводя итоги вышесказанного можно  сказать, что динамическое программирование пользуется следующими свойствами задачи:

• перекрывающиеся подзадачи;
• оптимальная подструктура;
• возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению  задач:

• нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
• восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme, Common Lisp,Perl), а в некоторых требует дополнительных расширений (C++).

Известны сериальное динамическое программирование, включённое во все  учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

Обычное динамическое программирование является частным случаем несериального  динамического программирования, когдаграф взаимосвязей переменных — просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность. Неаддитивные задачи решаются другими методами. Например, многие задачи по оптимизации инвестиций компании являются неаддитивными и решаются с помощью сравнения стоимости компании при проведении инвестиций и без них.

 

Задача.

Совет директоров фирмы рассматривает  предложения по наращиванию производственных мощностей для увеличения выпуска  однородной продукции на четырех  предприятиях, принадлежащих фирме. Для модернизации предприятий совет  директоров инвестирует средства в  объеме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска продукции  зависит от выделенной суммы, его  значения представлены в таблице.

Инвестиции, млн. р.	Прирост выпуска продукции, млн. р.
	Предприятие 1	Предприятие 2	Предприятие 3	Предприятие 4
50	23	24	25	22
100	32	31	33	30
150	44	43	42	41
200	53	52	54	55
250	70	72	71	73

 

Найти распределение инвестиций между  предприятиями, обеспечивающее фирме  максимальный прирост выпуска продукции, причем на одно предприятие можно  осуществить только одну инвестицию.

 

Решение.

Исходные  данные.

 

f1	f2	f3	f4	xi
0	0	0	0	0
23	24	25	22	50
32	31	33	30	100
44	43	42	41	150
53	52	54	55	200
70	72	71	73	250

 

 

 

I этап. Условная оптимизация.

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

 

e3	u4	e4 = e3 - u4	f4(u4)	F*4(e4)	u4(e4)
50	0	50	0
	50	0	22	22	50
100	0	100	0
	50	50	22
	100	0	30	30	100
150	0	150	0
	50	100	22
	100	50	30
	150	0	41	41	150
200	0	200	0
	50	150	22
	100	100	30
	150	50	41
	200	0	55	55	200
250	0	250	0
	50	200	22
	100	150	30
	150	100	41
	200	50	55
	250	0	73	73	250

 

 

 

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

 

e2	u3	e3 = e2 - u3	f3(u3)	F*3(e2)	F2(u3,e2)	F*3(e3)	u3(e3)
50	0	50	0	22	22
	50	0	25	0	25	25	50
100	0	100	0	30	30
	50	50	25	22	47	47	50
	100	0	33	0	33
150	0	150	0	41	41
	50	100	25	30	55	55	50
	100	50	33	22	55
	150	0	42	0	42
200	0	200	0	55	55
	50	150	25	41	66	66	50
	100	100	33	30	63
	150	50	42	22	64
	200	0	54	0	54
250	0	250	0	73	73
	50	200	25	55	80	80	50
	100	150	33	41	74
	150	100	42	30	72
	200	50	54	22	76
	250	0	71	0	71

 

 

 

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

 

e1	u2	e2 = e1 - u2	f2(u2)	F*2(e1)	F1(u2,e1)	F*2(e2)	u2(e2)
50	0	50	0	25	25	25	0
	50	0	24	0	24
100	0	100	0	47	47
	50	50	24	25	49	49	50
	100	0	31	0	31
150	0	150	0	55	55
	50	100	24	47	71	71	50
	100	50	31	25	56
	150	0	43	0	43
200	0	200	0	66	66
	50	150	24	55	79	79	50
	100	100	31	47	78
	150	50	43	25	68
	200	0	52	0	52
250	0	250	0	80	80
	50	200	24	66	90	90	50
	100	150	31	55	86
	150	100	43	47	90
	200	50	52	25	77
	250	0	72	0	72