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

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

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

W = W(u) = W(u₁, u₂, ..., u_m). (5.1)

Управление, при котором показатель W достигает оптимума (максимума или минимума), называется оптимальным управлением u^*, которое состоит из совокупности оптимальных шаговых управлений

u^* = (u₁^*, u₂^*, ..., u_m^*). (5.2)

Задача динамического программирования - определить u_i^* (u_i^* не только число, а может быть вектором, функцией) на каждом шаге, i=1,2,...,m, и тем самым u^* всей операции в целом.

Большинство практических задач имеет дело с одномерной задачей динамического программирования:

где

W_i - эффективность действий на i шаге.

Метод динамического программирования был предложен и развит Р. Беллманом и его учениками в начале 50-х годов и состоит в нахождении оптимума целевой функции при ограничении общего вида на варьируемые параметры. Задача может быть сформулирована следующим образом.

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

• от последнего шага к первому;
• от первого шага к последнему или же наоборот в зависимости от исходных данных.

На первом круге ищется так называется условное оптимальное решение. Оно выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана, который формулируется следующим образом: нельзя получить оптимальное значение целевой функции i-шагового процесса , если для любого u_i, выбранного на шаге i, значение целевой функции для оставшихся i-1 шагов не является оптимальным. При этом выбранном на i-шаге значений u_i.

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

Поясним вышесказанное, продолжая рассмотрение примера 5.1. Дадим графическую интерпретацию задачи (рис. 5.1), разделив отрезок от нижнего L до верхнего U складов в направлении сторон света, допустим, на 5 частей. В общем случае коэффициент дробления может быть каким угодно. В нашем случае трасса из L до U состоит из m=5+5=10 участков, направленных на север или восток. Проставим на каждом из отрезков число, выражающее затраты на строительство дороги на этом участке. Требуется выбрать такой путь из L в U, для которого сумма чисел, стоящих на отрезках, была бы минимальна.

Итак, условная оптимизация выполнена - в какой бы из узловых точек мы не находились, известно, куда двигаться (по стрелке) и во что обойдется прокладка трассы до конца (по числу в квадрате). В прямоугольнике при точке L записан оптимальный выигрыш на всем протяжении пути из L в U: W^*= 101 .

Теперь остается построить безусловное оптимальное управление - траекторию, ведущую из L в U самым дешевым способом. Для этого необходимо следовать указаниям стрелок. Такая оптимальная траектория отмечена на рис.5.4 утолщенными линиями. В текстовом виде безусловное оптимальное управление запишется так:

т.е. первые четыре участка трассы от нижнего склада необходимо вести на север, далее повернуть на восток, далее на север и остальные четыре участка - на восток. Задача решена.

Прежде, чем перейти к описанию блок-схемы алгоритма метода динамического программирования сделаем ряд замечаний:

1. Отметим основные свойства задач, к которым возможно применить метод линейного программирования:

• задача должна быть представлена как n-шаговый процесс принятия решений;
• задача должна быть определена для любого числа шагов и иметь структуру, независящую от их числа
• должно быть задано некоторое множество параметров, описывающих состояние системы (под параметрами состояния понимаются параметры, от которых зависят оптимальные значения управляющих переменных), на это множество накладывается условие неизменности его при увеличении числа шагов;

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

• Выбрать параметры, характеризующие состояние s управляемой системы перед каждым шагом.
• Разбить операцию на шаги.
• Определить набор шаговых управлений u_i для каждого шага и налагаемые на них ограничения.
• Определить какой выигрыш приносит на i шаге управление u_i, если перед этим система была в состоянии s, т.е. записать функцию выигрыша:

W_i = f_i(s, u_i). (5.4)

• Определить, как изменяется состояние s системы S под влиянием управления u_i на i шаге - оно переходит в новое состояние:

• Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W_i(s) (начиная с i шага и до конца) через уже известную функцию W_i+1(s):

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

W_m(s) = max {f_m(s,u_i)}. (5.7)

• Произвести условную оптимизацию (m-1) шага по (5.6), полагая в ней i=(m-1), (m-2), ... и для каждого из этих шагов указать условное оптимальное управление u_i(s), при котором максимум достигается. На первом шаге варьировать состояние системы не нужно:

W^* = W₁(s_o).

• Произвести безусловную оптимизацию управления, считывая соответствующие рекомендации на каждом шаге: взять найденное оптимальное управление на первом шаге u₁^* = u₁(s_o); изменить состояние системы по (5.6); для вновь найденного состояния найти оптимальное управление на втором шаге u₂^* и т.д. до конца.

Таблица 5.1

Хотя задача в своей постановке не содержит упоминания о времени, операцию распределения средств мысленно можно развернуть в какой-то последовательности, считая за первый шаг отправку тракторов в лесхоз F₁, за второй - в F₂ и т.д.

Управляемая система в данном случае - трактора, которые распределяются. Состояние системы перед каждым шагом характеризуется одним числом - количество еще нераспределенных машин. Шаговыми управлениями являются число тракторов u₁, u₂, ..., u_m, выделяемые лесхозам. Требуется найти оптимальное управление, т.е. такую совокупность чисел u₁^*, u₂^*, ..., u_m^*, которое дает максимальное повышение уровня технической готовности машинно-тракторного парка по управлению в целом, что эквивалентно следующему выражению:

Начнем оптимизацию с 5 лесхоза (шага). Пусть остаток тракторов к этому шагу s. Очевидно, что необходимо все s тракторов передать лесхозу F₅. Поэтому условное оптимальное управление на 5 шаге

u₅(s) = s,

а условный оптимальный выигрыш

W₅(s) = f₅(s).

Задаваясь целой гаммой значений s = 1, 2, ...7 по табл. 5.1 (функция технической готовности f_i(u)) для каждого значения s определим u₅(s) и W₅(s):

u₅(0)= 0; W₅(0)=0,70;

u₅(1)= 1; W₅(1)=0,76;

u₅(2)= 2; W₅(1)=0,80;

u₅(3)= 3; W₅(1)=0,85;

u₅(4)= 4; W₅(1)=0,88;

u₅(5)= 5; W₅(1)=0,91;

u₅(6)= 6; W₅(1)=0,93;

u₅(7)= 7; W₅(1)=0,94.

Полученные данные занесем в табл. 5.2. Последний шаг оптимизирован.

Таблица 5.2.

Перейдем к предпоследнему 4 лесхозу (шагу). Пусть имеем s нераспределенных тракторов. Обозначим W₄(s) условный оптимальный выигрыш на двух последних шагах: 4 и 5 (который уже оптимизирован). Если выделить на 4 шаге 4 лесхозу u тракторов, то на последний шаг останется s-u. Следовательно выигрыш на двух последних шагах будет равен

W₄(s) = f₄(u) + W₅(s-u).

Вновь задаваясь целой гаммой значений s = 1, 2, ...7 и используя данные табл.5.1 для каждого значения s определим u₄(s), W₄(s) и выделим максимальное значение, что и есть оптимальный выигрыш за два последних шага:

• s=0: u₄(0)= 0; W₄(0)=0,88+0,70=1,58;
• s=1: u₄(1)= 1; W₄(1)=0,91+0,7=1,61; u₄(1)= 0; W₄(1)=0,88+0,76=1,64;
• s=2: u₄(2)= 2; W₄(2)=0,92+0,7=1,62; u₄(2)= 1; W₄(2)=0,91+0,76=1,67; u₄(2)= 0; W₄(2)=0,88+0,80=1,68;
• s=3: u₄(3)= 3; W₄(3)=0,93+0,7=1,63; u₄(3)= 2; W₄(3)=0,92+0,76=1,68; u₄(3)= 1; W₄(3)=0,91+0,80=1,71; u₄(3)= 0; W₄(3)=0,88+0,85=1,73;
• s=4: u₄(4)= 4; W₄(4)=0,94+0,7=1,64; u₄(4)= 3; W₄(4)=0,93+0,76=1,69; u₄(4)= 2; W₄(4)=0,92+0,80=1,72; u₄(4)= 1; W₄(4)=0,91+0,85=1,76; u₄(4)= 0; W₄(4)=0,88+0,88=1,76;
• s=5: u₄(5)= 5; W₄(5)=0,95+0,7=1,65; u₄(5)= 4; W₄(5)=0,94+0,76=1,70; u₄(5)= 3; W₄(5)=0,93+0,80=1,73; u₄(5)= 2; W₄(5)=0,92+0,85=1,77; u₄(5)= 1; W₄(5)=0,91+0,88=1,79; u₄(5)= 0; W₄(5)=0,88+0,91=1,79;
• s=6: u₄(6)= 6; W₄(6)=0,95+0,7=1,65; u₄(6)= 5; W₄(6)=0,95+0,76=1,71; u₄(6)= 4; W₄(6)=0,94+0,80=1,74; u₄(6)= 3; W₄(6)=0,93+0,85=1,78; u₄(6)= 2; W₄(6)=0,92+0,88=1,80; u₄(6)= 1; W₄(6)=0,91+0,91=1,82; u₄(6)= 0; W₄(6)=0,88+0,93=1,81;
• s=7: u₄(7)= 7; W₄(7)=0,95+0,7=1,65; u₄(7)= 6; W₄(7)=0,95+0,76=1,71; u₄(7)= 5; W₄(7)=0,95+0,80=1,75; u₄(7)= 4; W₄(7)=0,94+0,85=1,79; u₄(7)= 3; W₄(7)=0,93+0,88=1,82; u₄(7)= 2; W₄(7)=0,92+0,91=1,83; u₄(7)= 1; W₄(7)=0,91+0,93=1,84; u₄(7)= 0; W₄(7)=0,88+0,94=1,82.

В табл. 5.2 приведены результаты условной оптимизации на 4 шаге.

Далее оптимизируем 3 и 2 шаги по (5.6):

W_i (s) = max {f_i(u) + W_i+1(s-u)}

и записываем соответствующее ему условное оптимальное управление u_i(s) (значение u, при котором этот максимум достигается) в табл. 5.2.

Продолжая таким образом, дойдем, наконец, до 1 лесхоза F₁. Здесь нам не нужно будет варьировать значения s, так как число тракторов перед первым шагом равно 7:

W^* = W₁(7) = max {f₁(u) + W₂(7-u)}= .

Таким образом, максимальное повышение коэффициента технической готовности по всем лесхозам найден. Теперь остается только считать рекомендации. Максимум технической готовности машинно-тракторного парка достигается при отправке 1 трактора в 1 лесхоз. После первого шага остается 7-1=6 тракторов. Считывая рекомендацию для этого значения по табл. 5.2, выделяем второму лесхозу оптимальное число тракторов - 1, третьему - , четвертому - и, наконец, 5 - .

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

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

Метод динамического программирования единый подход к решению всех видов задач о замене.

При составлении модели динамического программирования процесс замены рассматривается как n-шаговый, разбив весь период на N промежутков. Так как в начале каждого из этих промежутков принимается решение о сохранении оборудования, либо его замене, то управление на i шаге (i=1,2,...,n) содержит лишь две альтернативные переменные. Обозначим через u^c решение, состоящее в сохранении старого оборудования, а через u^з - решение, состоящее в замене старого оборудования новым. Условная оптимизация на каждом шаге состоит в вычислении двух величин и в выборе из них наибольшей (наименьшей). Это значительно упрощает расчеты на стадии условной оптимизации и позволяет решать вручную задачи о замене с большим числом шагов.

Процесс эксплуатации форвардера описывается шестью шагами. Состояние s_i-1 системы в начале i шага характеризуется одним параметром t - возрастом машины. Управление на каждом шаге состоит в выборе одного из двух решений: u^c решение, состоящее в сохранении форвардера, а через u^з - решение, состоящее в его замене. Основные функциональные уравнения модели динамического программирования имеют вид:

Условная оптимизация на последнем 6 шаге сводится к оптимизации по следующему уравнению, учитывая заданные в исходных условиях функции z_i

где

Числовые данные приведены в табл.5.4. Числовые данные по условной оптимизации с 5 по 1 шаг приведены в табл. 5.5 и 5.6 согласно уравнениям:

Таблица 5.4.

Таблица 5.5.

Таблица 5.6.

Безусловная оптимизация приводит к результату: W^*=173875 руб.; оптимальное управление U^*=(u^c, u^c, u^c, u^з, u^c, u^c). Следовательно, приобретенный форвардер целесообразно эксплуатировать в течении трех лет, на четвертом году его следует заменить новым и продолжать эксплуатировать оставшееся время.

1. Дать общую формулировку задач оптимизации в форме модели динамического программирования.
2. Рассмотрите и поясните ситуации из лесной экономики, лесного хозяйства или лесоэксплуатации, требующие применения для их решения методов динамического программирования.
3. Поясните понятия: управление, оптимальное и условно оптимальное управления, состояние системы, траектории перехода. Приведите примеры.
4. Как определяются условно оптимальные управления на каждом из шагов?
5. Почему безусловно оптимальное управление может быть определено только для последнего шага (считая от конечного состояния) и при условии, что рассмотрены условно оптимальные управления на всех предыдущих шагах?
6. Проанализируйте основные правила решения задач динамического программирования.

Разработать оптимальную политику замены оборудования (не старше 10 лет), если известны: стоимость p(t) продукции, производимой в течении года с использованием данного оборудования; ежегодные расходы g(t), связанные с эксплуатацией оборудования; его остаточная стоимость s(t); стоимость z нового оборудования (с расходами, связанными с установкой, накладкой и запуском оборудования). После составления матрицы максимальных прибылей сформировать оптимальные политики в отношении оборудования данного возраста t в плановом периоде данной продолжительности N. Числовые данные в десяти вариантах приведены в табл. 5.3 и табл. 5.4.

Таблица 5.3

 Таблица 5.4.

В табл. 5.5 приведены значения f_i(u) возможного прироста выпуска продукции в четырех лесхозах в зависимости от выделенной на модернизацию производства суммы u. Распределить между лесхозами 1 млн. руб., чтобы общий прирост выпуска продукции был максимальным. Для упрощения вычислений значения u принимать кратными 200 тыс. руб.

Таблица 5.5.

Распределите имеющиеся средства S между тремя лесхозами при заданных функциях прибыли f_i(u), i=1,2,3, из условия максимизации суммарной прибыли согласно данным табл. 5.6.

Таблица 5.6.