Dinamicheskoe_programmirovanie

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

Динамическое программирование (ДП) - метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы. Такие операции называются многошаговыми.

Задачи динамического программирования:

1. Задача распределения финансовых средств (капитальных вложений между направлениями их использования).

2. Замена технологического оборудования с учетом планирования текущих и капитальных затрат на его обслуживание.

3. Стратегическое планирование предприятия на несколько лет.

4. Разработка правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа.

5. Календарное планирование производства и др.

Общая постановка задачи ДП

Рассматривается управляемый процесс (например, экономический процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования), который может быть разбит на несколько состояний (шагов). В качестве шага могут выступать временные периоды, предприятия и др.

Управляемый процесс в качестве объекта имеет систему S, которая в процессе управления переводится из начального состояния s₀ в некоторое конечное состояние s_n, где n – число состояний системы или шагов.

Управленческое решение принимается последовательно на каждом шаге. Управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управлений.

Особенности модели ДП:

- задача оптимизации интерпретируется как n - шаговый процесс управления;

- целевая функция модели является аддитивной (суммарной) функцией показателей эффективности каждого шага;

- выбор управления на k-ом шаге зависит только от состояния системы на этом шаге;

- каждое состояние системы после k-го шага управления зависит только от предшествующего состояния и управления .

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

Пусть - управление, переводящее систему из начального состояния в конечное. Состояние системы после k-го шага управления - . Тогда последовательность состояний можно изобразить кружками.

X₂

X_n

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

Обозначим показатель эффективности k-го шага как : . Тогда целевая функция будет представлять собой сумму оптимальных показателей эффективности всех шагов системы: .

Так как каждое состояние системы и показатель его эффективности зависит от предыдущего состояния и от управления, выбранного на данном шаге, то состояние системы в целом и суммарная эффективность на последующем шаге будут определяться начальным состоянием системы и вектором управления . Тогда целевую функцию можно представить в следующем виде: .

Каждое состояние системы может быть выражено:

Принцип оптимальности и уравнения Беллмана

Принцип оптимальности.

На каждом шаге управление выбирается так, чтобы оно в совокупности со всеми оптимальными управлениями на всех последующих шагах приводило к наилучшему суммарному показателю эффективности. Т.е. управление должно выбираться исходя из оптимальности управления в целом, а не только на каком-то конкретном шаге. В основу этого принципа положены особенности модели ДП. На основе данного принципа были сформулированы рекуррентные формулы Беллмана. Применение данных формул возможно на базе обратной или прямой схемы Беллмана. В обоих случаях является показателем эффективности k-ого шага. На каждом шаге оптимальное управление выбирается из множества возможных управлений .

Обратная схема Беллмана.

При обратной схеме оптимизация осуществляется в результате обратного движения от последнего шага к первому. Сначала определяется оптимальная стратегия управления на n-ом шаге, затем на двух последних шагах, потом на трех последних шагах и т.д. до первого шага.

n-й шаг: состояние системы, зависящее от состояния , - управление на n-ом шаге, - целевая функция n-го шага.

Оптимальный показатель эффективности n–го шага , равный суммарному показателю эффективности всех предыдущих шагов на множестве всевозможных управлений всевозможных состояний системы.

(n-1)-ый шаг

к-ый шаг

………………

1-ый шаг

Таким образом, в результате прохождения всех шагов от последнего к первому определяется оптимальное значение целевой функции. Чтобы найти оптимальную стратегию управления, т.е. определить решение задачи - , необходимо снова пройти всю последовательность шагов, только от начала к концу.

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

Процесс решения можно представить в виде схемы:

Прямая схема Беллмана

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

1 шаг

На данном шаге состояние системы - , предыдущее состояние -. - множество управлений на первом шаге. Показатель эффективности 1-го шага - .

2 шаг

.

……………..

k – ый шаг

……………..

n-ый шаг

В результате прохождения всех шагов от первого к последнему определяется оптимальное значение целевой функции, которое приравнивается оптимальному показателю эффективности n-го шага . Чтобы найти оптимальную стратегию управления, т.е. определить решение задачи - , необходимо снова пройти всю последовательность шагов - от последнего к первому.

Поиск оптимальной стратегии можно представить в виде схемы:

Общая схема применения метода ДП

1. Выбирается способ деления процесса управления на шаги.

2. Определяются параметры состояния и переменные управления на каждом шаге.

3. Записываются уравнения состояний .

4. Вводится целевая функция.

5. Вводится в рассмотрение условные максимумы (минимумы) и условное оптимальное управление на k-м шаге: (в случае обратной схемы Беллмана), (при прямой схеме Беллмана).

6. Записываются основные уравнения для выбранной схемы Беллмана.

7. Последовательно решаются записанные уравнения Беллмана и получаются две последовательности функций: и .

8. После выполнения условной оптимизации определяется оптимальное решение поставленной задачи и .

Задача распределения средств между предприятиями

Задача распределения ресурсов между предприятиями является задачей динамического программирования.

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

Математическая модель для каждого вида предприятия имеет вид:

Целевая функция при ограничениях:

В модели использованы следующие обозначения:

- цена на j-ый вид товара для k-ого предприятия;

- оптимальный объем закупки i-ого вида ресурса k-ым предприятием;

- уровень запаса i-ого вида ресурса на k-ом предприятии;

- оптимальный план производства j-ого вида продукции на k-ом предприятии;

- норма расхода i-ого вида ресурса для производства единицы продукции j-ого вида на k-ом предприятии;

- рыночная цена i-ого вида ресурса для k-ого предприятия;

- объем финансовых средств, выделенных k-ому предприятию;

- минимальный объем заказов j-ого вида продукции на k-ом предприятии;

- предельная емкость рынка по j-ому виду продукции для k-ого предприятия.

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

Вычисленные методами линейного программирования показатели эффективности деятельности каждого предприятия в зависимости от объема получаемых финансовых средств в дальнейшем используются для нахождения оптимального распределения средств между предприятиями методами динамического программирования.

Предполагается, что:

1. дополнительный доход каждого предприятия не зависит от объемов вложения средств в другие предприятия;

2. дополнительный доход каждого предприятия выражается в одних и тех же единицах;

3. совокупный дополнительный доход равен сумме дополнительных доходов, полученных каждым предприятием.

Для определения оптимальных средств инвестирования необходимо пройти следующие этапы:

1. интервал изменения выделяемых средств разбивается на элементарные отрезки;

2. для заданных значений выделяемых средств определяются показатели эффективности для всех предприятий;

3. по обратной (прямой) схеме используются уравнения Беллмана;

4. в обратной (прямой) последовательности, начиная от находятся оптимальные значения выделяемых средств .

Пример. Планируется деятельность 4 промышленных предприятий на очередной год. Необходимо между ними распределить 400 единиц ограниченного ресурса Q. Каждое предприятие i в зависимости от объема выделенных средств x получает дополнительный доход f_i(x). Распределение ресурсов производится с точностью 80 единиц. Необходимо определить оптимальное распределение средств между предприятиями, обеспечивающее максимальную эффективность деятельности всех предприятий.

Объемы получаемых дополнительных доходов в зависимости от выделенных ресурсов x представлены в таблице 1.

Таблица 1

Объем выделенных ресурсов, x	Дополнительный доход предприятия в зависимости от объема выделенных средств, fi(x)
	f1(x)	f2(x)	f3(x)	f4(x)
0	0	0	0	0
80	30	28	35	27
160	57	62	67	73
240	120	122	130	125
320	150	146	144	152
400	180	175	180	178

Рассмотрим обратную схему Беллмана.

Согласно обратной схеме Беллмана начинаем с определения условно оптимальных капиталовложений, выделяемых для последнего четвертого (n-ого) предприятия. Для этого находим значения для каждого x, принимающего значения 0, 80, 160, 240, 320, 400.

4 шаг.

Показатель эффективности 4-ого предприятия, равный суммарному показателю эффективности на всех шагах определяется как .

3 шаг

Находим - суммарный показатель эффективности деятельности 3 и 4 предприятий .

2 шаг

Вычислим объединённый показатель эффективности деятельности 2, 3 и 4 предприятий - .

1 шаг

Объединённый показатель эффективности деятельности 4-х предприятий - .

Таблица 2

Объем выделенных ресурсов, x	Показатели эффективности предприятий в зависимости от объема выделенных средств, Z i(x)
	Z4(x)	Z 3(x)	Z 2(x)	Z 1(x)
0	0	0	0	0
80	27	35	35	35
160	73	73	73	73
240	125	130	130	130
320	152	160	160	160
400	178	203	203	203

Чтобы найти оптимальную стратегию управления, необходимо рассмотреть всю последовательность шагов от последнего к первому.

В результате решения задачи распределения средств между предприятиями получили, что для обеспечения максимальной эффективности деятельности 4-х предприятий, равной 203 у.е., 1-ому и 2-ому предприятиям следует не выделять ресурсов, 3 предприятию необходимо выделить 240 единиц ресурса, 4-ому – 160 единиц.

№ вари-анта	Прирост выпуска продукции i - ого предприятия, fi(x)	Часть средств, выделяемых предприятиям, млн руб, x
		0	20	40	60	80	100
	f1(x)	0	9	18	24	38	50
		0	9	17	29	38	47
		0	7	29	37	41	47
		0	9	20	35	44	48
		0	9	18	29	41	52
		0	11	21	40	54	63
		0	12	26	40	60	74
		0	14	24	37	45	47
		0	16	28	36	39	44
		0	18	28	39	47	55
		0	12	19	30	44	69
		0	11	34	46	53	68
		0	9	19	28	37	68
		0	12	25	34	46	58
		0	11	19	30	47	52
		0	9	20	42	45	59
		0	8	22	36	49	64
		0	8	24	42	58	67
		0	7	27	42	50	66
		0	5	30	40	52	65