02_Сущность методов

,

где u=(u₁, u₂, …, u_n)

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

Задача состоит в нахождении оптимальной стратегии управления, т.е. такой совокупности управлений u*=(u₁*, ..., u_n*), в результате реализации которых система S за n шагов переходит из начального состояния х⁽⁰⁾ в конечное х⁽ⁿ⁾ и при этом функция дохода W(u) принимает наибольшее значение.

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

Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага. Для того чтобы найти решение на последнем, n-м шаге, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление u_n°, обеспечивающее максимальное значение функции дохода W_n(x^(n-1);u_n). Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным управлением. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага.

Чтобы построить алгоритм решения задач, дадим математическую формулировку принципа оптимальности. Для этого введем некоторые дополнительные обозначения. Обозначим через F₀(x⁽⁰⁾) максимальный доход, получаемый за n шагов при переходе системы S из начального состояния х⁽⁰⁾ в конечное состояние х⁽ⁿ⁾ при реализации оптимальной стратегии управления u* = (u₁*, ..., и_n*), а через F_k(x^(k)) - максимальный доход, получаемый при переходе из любого состояния x^(k) в конечное состояние х⁽ⁿ⁾ при оптимальной стратегии управления на оставшихся (n-k) шагах. Тогда

, (1)

(2)

при .

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

Этот процесс является довольно громоздким. Однако использование ЭВМ позволяет находить на основе метода динамического программирования решение и более сложных практических задач.

Решение задач

Решение задачи 1. Состояние системы к началу k-гo сезона определяется фактическим временем использования покрытия (его возрастом) x^(k). В качестве управлений, как уже говорилось, выступают решения о замене (u_k = 3) и сохранении (u_k = С) покрытия. Решая задачу методом динамического программирования, на первом этапе при движении от начала 5-го сезона пятилетки к началу 1-го сезона для каждого допустимого состояния покрытия найдем условное оптимальное управление. На втором этапе при движении от начала 1-го сезона пятилетки к началу 5-го сезона из условных оптимальных решений для каждого сезона составим оптимальный план замены покрытия (капитальных ремонтов) на пятилетку.

Так как прибыль предприятия за k-ый сезон пятилетки (k=l,...,5) составит

то уравнение Беллмана имеет вид

=

=

Используя уравнение Беллмана, определим условно оптимальные решения для последнего (5-го) сезона пятилетки, в связи с чем находим множество допустимых состояний покрытия к началу данного сезона. Так как к началу пятилетки имеется новое покрытие (τ⁽¹⁾=0), то возраст покрытия к началу 5-го сезона может составлять 1, 2, 3 и 4 года. Поэтому допустимые состояния системы на данный период времени таковы =1, =2, =3, =4.

Для каждого из этих состояний найдем условно оптимальное решение и соответствующее значение функции F₅(τ⁽⁵⁾).

Из соотношения F₆(τ⁽⁶⁾)=0 (т.к. рассматривается последний год расчетного периода) следует

Подставляя в полученную формулу вместо τ⁽⁵⁾ его значения и учитывая данные таблицы 1, находим

Полученные результаты вычислений сведем в табл. 2.

Таблица 2

Возраст покрытия, τ(5) лет	Значения функции дохода F5, тыс. руб.	Условно оптимальное решение
1	50	С
2	35	С
3	25	С
4	20	3

Рассмотрим теперь возможные состояния покрытия к началу 4-го сезона. Очевидно, допустимыми состояниями являются =1, =2, =3. Для каждого из них определяем условно оптимальное решение и соответствующее значение функции F₄(τ⁽⁴⁾). Для этого используем данные табл. 1 и табл. 2. Имеем:

Полученные результаты вычислений сведем в табл. 3.

Таблица3

Возраст покрытия, τ(4) лет	Значения функции дохода F4, тыс. руб.	Условно оптимальное решение
1	85	С
2	70	С
3	70	З

Определим теперь условно оптимальное решение для каждого из допустимых состояний покрытия к началу 3-го сезона пятилетки. Очевидно, такими состояниями являются=1 и =2. Имеем:

Полученные результаты вычислений сведем в табл. 4.

Таблица. 4

Возраст покрытия, τ(3) лет	Значения функции дохода F3, тыс. руб.	Условно оптимальное решение
1	120	С
2	105	С или З

Наконец, к началу 2-го сезона пятилетки возраст покрытия может быть равен только лишь одному году (=1). Поэтому

Так как к началу пятилетки покрытие новое (=0), то

F₁(0)=R(0)-Z(0)+F₂(l) = 80-20+155=215.

Просматривая полученные результаты в обратном порядке получим: для 1-го сезона пятилетки решение единственно — следует сохранить покрытие. Значит, возраст покрытия к началу 2-го сезона пятилетки равен одному году. Тогда оптимальным решением для 2-го сезона пятилетки является решение о сохранении покрытия. Возраст покрытия к началу 3-го сезона пятилетки становится равным двум годам. При таком возрасте (см. табл. 4) покрытие можно заменить, а можно и сохранить. После замены покрытия его возраст к началу 4-го сезона пятилетки составит один год, а после сохранения – 3 года. Как видно из табл. 3, при возрасте покрытия 1 год его менять не следует, а при возрасте 3 года - следует. Поэтому возраст покрытия к началу 5-го сезона пятилетки составит либо один год либо два года, а значит, согласно табл. 2, в обоих случаях оборудование менять нецелесообразно.

Итак, получаются следующие оптимальные планы капитальных ремонтов (табл. 5).

Таблица 5

	Годы пятилетки
	1	2	3	4	5
Оптимальное решение 1	Сохранить	Сохранить	Заменить	Сохранить	Сохранить
Оптимальное решение 2	Сохранить	Сохранить	Сохранить	Заменить	Сохранить

Максимальная эффективность перевозок по данной автомобильной дороге равна 215 тыс.руб.

Общая схема возможных состояний системы и управлений за пятилетку приведена на рис.

П Р А К Т И К А № 7

Пример решения расчетной работы: шифр – 123456

r0 (тыс.руб)	=	150	z0 (тыс.руб)	=	37
r1 (тыс.руб)	=	146	z1 (тыс.руб)	=	38
r2 (тыс.руб)	=	142	z2 (тыс.руб)	=	39
r3 (тыс.руб)	=	138	z3 (тыс.руб)	=	41
r4 (тыс.руб)	=	135	z4 (тыс.руб)	=	41
r5 (тыс.руб)	=	131	z5 (тыс.руб)	=	43
r6 (тыс.руб)	=	130	z6 (тыс.руб)	=	44
r7 (тыс.руб)	=	126	z7 (тыс.руб)	=	45
r8 (тыс.руб)	=	123	z8 (тыс.руб)	=	47
r9 (тыс.руб)	=	119	z9 (тыс.руб)	=	48
r10 (тыс.руб)	=	115	z10 (тыс.руб)	=	49
			Z	=	42

Составляем общую схему возможных состояний системы и управлений за 10 лет (см. рис.1).

Составляем таблицу зависимости эффективности перевозок и затрат на ремонт и содержание от времени.

Таблица 1

	Время t, в течение которого эксплуатируется дорога, лет
	0	1	2	3	4	5	6	7	8	9	10
Эффективность перевозок R(t) в стоимостном выражении тыс.руб.	150	146	142	138	135	131	130	126	123	119	115
Ежегодные затраты Z(t), связанные с содержанием и ремонтом дороги тыс.руб.	37	38	39	41	41	43	44	45	47	48	49

По рис. 1, так как к началу срока службы имеется новое покрытие (τ⁽¹⁾=0), то возраст покрытия к началу 10-го сезона может составлять 1, 2, …, 10 лет. Поэтому допустимые состояния системы на данный период времени таковы =1, =2, …, =9. Для каждого из этих состояний найдем условно оптимальное решение и соответствующее значение функции F₁₀(τ⁽¹⁰⁾).

Из уравнения Беллмана и соотношения F₁₁(τ⁽¹¹⁾)=0 следует

Подставляя в полученную формулу вместо τ⁽¹⁰⁾ его значения и учитывая данные таблицы 1, находим

Рис. 1

Полученные результаты вычислений сведем в табл. 2.

Таблица 2. Начало 10-го сезона.

Возраст покрытия, τ(10) лет	Значения функции дохода F10, тыс. руб.	Условно оптимальное решение
1	108	С
2	103	С
3	97	С
4	94	С
5	88	С
6	86	С
7	81	С
8	76	С
9	71	С или 3

Рассмотрим теперь возможные состояния покрытия к началу 9-го сезона. Очевидно, допустимыми состояниями являются =1, =2, …, =8. Для каждого из них определяем условно оптимальное решение и соответствующее значение функции F₉(τ⁽⁹⁾). Для этого используем данные табл. 1 и табл. 2. Имеем:

Полученные результаты вычислений сведем в табл. 3.

Таблица 3. Начало 9-го сезона.

Возраст покрытия, τ(9) лет	Значения функции дохода F9, тыс. руб.	Условно оптимальное решение
1	211	С
2	200	С
3	191	С
4	182	С
5	179	З
6	179	З
7	179	З
8	179	З

Определим теперь условно оптимальное решение для каждого из допустимых состояний покрытия к началу 8-го, 7-го и т.д. до 2-го сезона пятилетки. Имеем⁷:

Таблица 4. Начало 8-го сезона.

Возраст покрытия, τ(8) лет	Значения функции дохода F8, тыс. руб.	Условно оптимальное решение
1	308	С
2	294	С
3	282	З
4	282	З
5	282	З
6	282	З
7	282	З

Таблица 5. Начало 7-го сезона.

Возраст покрытия, τ(7) лет	Значения функции дохода F7, тыс. руб.	Условно оптимальное решение
1	402	С
2	385	С
3	379	С или З
4	379	З
5	379	З
6	379	З

Таблица 6. Начало 6-го сезона.

Возраст покрытия, τ(6) лет	Значения функции дохода F6, тыс. руб.	Условно оптимальное решение
1	493	С
2	482	С
3	476	С
4	473	С или З
5	473	З