НА ОСНОВЕ МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

ЛЕКЦИЯ 3. ПРИНЯТИЕ УПРАВЛЕНЧЕСКОГО РЕШЕНИЯ

3.1. Общая постановка задачи динамического программирования.

3.2. Решение задачи об оптимальной распределении ресурсов.

 

 

3.1.

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

 

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

 

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

 

В основе вычислительных алгоритмов динамического программирования лежит следующий принцип оптимальности, сформулированный Р. Беллманом: каково бы ни было состояние системы S в результате (n‑1) шагов, управление на n-м шаге должно выбираться так, чтобы оно по совокупности с управлениями на всех последующих шагах с (n+1)‑го до N‑го включительно доставляло экстремум целевой функции.

 

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

 

 

Постановка задачи: Рассматривается процесс управления (1,2,3,4,5…..). В результате управления система S переводится из начального состояния S₀ в состояние S_n. Управление разбивается на n – шагов, т.е. осуществляется выбор одного управления U_n последовательно на каждом шаге:

 

 

Каждый шаг выбора очередного решения связан с определенным эффектом, который зависти от текущего состояния и принятого решения: φ_n (S_n; U_n).

Общий эффект (доход) за n – шагов слагается из эффектов на отдельных шагах.

Требуется найти такую последовательность решений (U₁, …… U_n), чтобы получить максимальный эффект (доход) за n – шагов.

Любая возможная допустимая последовательность решений (U₁, …… U_n) называется последовательность решений.

Стратегия управления, доставляющая максимум критерию оптимальности – называется оптимальной.

 

Принцип оптимальности динамического программирования записывается в виде соотношения:

 

F_n (S_n) = max { φ_n (S_n; U_n) + F_n-1(S_n-1; U_n-1)}

 

где φ_n (S_n; U_n) - эффект от принятого решения U_n;

F_n-1(S_n-1; U_n-1) - эффект за оставшиеся n – шагов

 

Динамическое программирование – важный метод принятия решений, поскольку он позволяет сократить объем перебора вариантов решений и объем вычислений.

 

 

3.1.

Обозначим Х – общий объем располагаемых ресурсов, х_j (х_j≥0) – количество ресурса, используемое j –м способом, φ_j (х_j) - эффект от применения j –го способа.

 

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

 

1 этап:

F₁ (Х) = max { φ₁ (х₁)}

2 этап:

F₁₂ (Х) = max { φ₂ (х₂) + F₁(Х- х₂)}

 

3 этап:

F₁₂₃ (Х) = max { φ₃ (х₃) + F₁₂(Х- х₃)}

n – этап:

F_n (Х) = max { φ_n (х_n) + F_n-1(Х- х_n)}

 

Пример решения задачи динамического программирования табличным методом:

 

Инвестор выделяет средства в размере 50 млн.грн., которые должны быть распределены между тремя предприятиями. Средства выделяются только в размерах кратных 10 млн.грн. Постройте план распределения инвестиций между тремя предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него Х млн.грн. приносит прибыль φ_i (Х) млн.грн. по следующим данным:

 

Инвестирование средств (млн.грн), Х	Прибыль, млн.грн.
φ1 (Х)	φ2 (Х)	φ3 (Х)

 

ТАБЛИЧНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ:

 

1 этап. Все ресурсы используются 1-м способом (инвестирование в 1-е предприятие):

 

F₁ (Х) = max { φ₁ (х₁)}

 

Х	F1(Х)	х1

 

 

2 этап. Все ресурсы используются двумя способами (инвестиции распределяются между первым и вторым предприятием):

 

F₁₂ (Х) = max { φ₂ (х₂) + F₁(Х- х₂)}

 

Х	F12(Х)	х2

2.1. 2.2.

 

х2	Х=10
	F12=0+8=8
	F12=12+0=12

х2	Х=20
	F12=0+22=22
	F12=12+8=20
	F12=25+0=25

 

 

2.3. 2.4. 2.5.

х2	Х=30
	F12=0+38=38
	F12=12+22=34
	F12=25+8=33
	F12=33+0=33

 

х2	Х=50
	F12=0+61=61
	F12=12+39=51
	F12=25+38=63
	F12=33+22=55
	F12=48+8=56
	F12=56+0=56

 

х2	Х=40
	F12=0+39=39
	F12=12+38=50
	F12=25+22=47
	F12=33+8=41
	F12=48+0=48

 

3 этап. Все ресурсы используются тремя способами (инвестиции распределяются между тремя предприятиями):

 

F₁₂₃ (Х) = max { φ₃ (х₃) + F₁₂(Х- х₃)}

Х	F123(Х)	х3

 

 

3.1. 3.2

х3	Х=10
	F123=0+12=12
	F123=14+0=14

х3	Х=20
	F123=0+25=25
	F123=14+12=26
	F123=23+0=23

 

 

3.3. 3.4.

х3	Х=30
	F123=0+38=38
	F123=14+25=39
	F123=23+12=35
	F123=42+0=42

х3	Х=40
	F123=0+50=50
	F123=14+38=52
	F123=23+25=48
	F123=42+12=54
	F123=45+0=45

 

 

3.5

х3	Х=50
	F123=0+63=63
	F123=14+50=64
	F123=23+38=61
	F123=42+25=67
	F123=45+12=57
	F123=58+0=58

 

 

Ответ:: F₁₂₃=67 тыс.грн.

 

 

х₁=0 х₂=20 х₃=30

 

проверка: 0+25+42=67 тыс.грн.