УДК 51: 621.1
ИСПОЛЬЗОВАНИЕ динамического ПРОГРАММИРОВАНИЯ в лесозаготовительной промышленности
БГТУ (Минск, Беларусь)
Научный руководитель – канд. физ-.мат. наук, доцент
В лесной экономике, технологии и технике есть задачи, в которых необходимо учитывать изменения параметров систем во времени. Например, из года в год происходит старение машин и оборудования, изменяются производственная мощность и производительность труда на предприятиях, фондоотдача. Очевидно, что необходимо принимать оптимальные решения на год (или другой срок) и одновременно на весь рассматриваемый период в целом с учетом возможных изменений параметров. Для решения такого рода многошаговых задач разработан соответствующий математический аппарат, который получил название «динамического программирования».
Процесс называется управляемым, если на него можно повлиять. Влиять на процесс можно по шагам. Тем самым процесс при управлении разбивается на ряд шагов.
В динамическом программировании используется последовательное шаговое принятие решений, когда процесс при управлении разбивается на ряд шагов и управление выбирается на каждом шаге.
Примером многошагового разбиения управляемого процесса служит анализ деятельности лесопромышленного предприятия за ряд лет. Вторым примером может служить задача нахождения кратчайшего расстояния между поставщиками и потребителями заданной транспортной сети.
В первом и втором примерах шаг задан. В первом случае – это календарный год, во втором – расстояние между соседними транспортными узлами.
На практике часто встречаются случаи, когда шаг не бывает заданным, например прокладка трассы лесовозной дороги и т. д. В этом случае процесс искусственно разбивается на шаги. При этом необходимо учитывать, что:
1) шаг не должен быть слишком малым, чтобы процесс вычислений не был громоздким;
2) шаг должен отображать особенности и точность рассматриваемой задачи, позволять осуществлять оптимизацию с помощью несложных процедур.
Решение задачи должно обеспечить оптимальное управление рассматриваемым процессом. Количественной оценкой оптимизации является критерий эффективности W. Его значение называется «выигрышем». Величина W зависит от характера решаемой задачи. Например, при оценке деятельности лесопромышленного предприятия в качестве W может быть объем выпускаемой продукции, показатель рентабельности и т. д.
Спецификой метода динамического программирования является то, что процесс развивается последовательно, от шага к шагу. Решение, которое принимается на каждом шаге, называется шаговым управлением. Совокупность всех шагов управлений представляет собой управление процессом в целом: u = (u1, u2, …, um), где ui - шаговые управления. Если обозначить wi как выигрыш i-го шага, то выигрыш всего процесса равен
, где m – число шагов. Управление, при котором показатель W достигает максимального или минимального значения, называется оптимальным управлением u*, которое состоит из совокупности оптимальных управлений шагов u* = (u1*, u2*, …, um*). Решение задач методом динамического программирования осуществляется в два этапа:
1. От последнего шага к первому (от конца к началу);
2. От первого шага к последнему (от начала к концу).
На первом этапе ищутся условные оптимальные управления и выигрыши на каждом шаге. Условное оптимальное управление выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана: каково бы ни было состояние системы перед очередным шагом, управление на этом шаге надо выбирать так, чтобы выигрыш на данном шаге плюс выигрыш на всех последующих шагах был максимальным (минимальным).
Другими словами, управление на i-м шаге выбирается таким образом, чтобы не выигрыш на данном шаге был максимальным (минимальным), а чтобы была оптимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный. Исключение составляет заключительный шаг, который может планироваться без учета будущих последствий. Поэтому процесс динамического программирования разворачивается от конца к началу – первым планируется последний шаг. Для этого необходимо сделать разные предположения о том, чем завершился m - 1 шаг и для каждого из этих предположений найти условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на m шаге. Далее, двигаясь назад, оптимизируется управление на m - 1 шаге и т. д. пока не дойдем до первого.
На втором этапе определяются оптимальное управление u* и оптимальный выигрыш w*. На этом этапе вычисления практически уже не выполняются, а просматриваются и сравниваются решения, полученные на первом этапе. Для этого достаточно, двигаясь от начала к концу, прочитать уже готовые рекомендации и найти u*, состоящее из u1*, u2*, …, um*. Что касается оптимального выигрыша w* в целом, то он нам уже известен, именно на его оптимальности выбрано управление на первом шаге. Следует отметить, что в отличие от оптимального выигрыша w*, оптимальное управление u* может быть неоднозначно [1].
Среди многочисленных задач, решаемых на ЭВМ методами динамического программирования, к управлению и оптимизации лесозаготовок могут быть отнесены следующие:
Задача об оптимальном режиме работы машины. Например, при заданной мощности привода требуется рассчитать режим скорости протаскивания дерева через сучкорезный механизм сучкорезной машины с тем, чтобы время протаскивания было минимальным, а усилие протаскивания не превышало определенного значения. В данной задаче путь перемещения каретки можно условно разделить на следующие участки (шаги): холостой ход, бессучковая зона дерева, зона ствола с наиболее крупными сучьями, вершинная часть дерева.
Задача об управлении запасами. Например, требуется обосновать вместимость склада под сезонный запас древесины, учитывая сезонную неравномерность вывозки. Годовой период работы лесозаготовительного предприятия можно условно разделить на следующие этапы: зимний период (наиболее интенсивные заготовка и вывозка), период весенней распутицы (вывозка минимальная), летний период, период осенней распутицы. Оптимальным будет вариант, при котором суммарные денежные издержки на создание запасов из-за простоев оборудования вследствие преждевременного расхода запаса будут наименьшими.
Задача о проектировании лесовозной дороги и многие другие задачи.
Покажем, как может быть использовано динамическое программирование на примере проектирования лесовозной дороги [2].
Пусть прокладывается участок лесовозной дороги между нижним складом L леспромхоза и погрузочной площадкой M по пересеченной местности. Требуется построить дорогу так, чтобы затраты на ее сооружение были минимальными.
Разделим отрезок от нижнего склада L до верхнего склада M прямыми, параллельными направлениям сторон света, допустим, на 5 частей. Будем считать на каждом шаге участок пути прямолинейным. В нашем случае трасса от L до М состоит из m = 5 + 5 = 10 участков, направленных на север или восток. Проставим на каждом из отрезков число, выражающее затраты на строительство дороги на этом участке (рис.1). Требуется выбрать такой путь из L в М, для которого сумма чисел, стоящих на отрезках, была бы минимальна.
9 1 | 1 2 | 8 1 | 9 1 | 1 2 | M4 | |
8 1 | 4 3 | 1 5 | 9 1 | 4 1 | 8 | |
1 1 | 3 4 | 1 5 | 8 1 | 9 9 | 1 | |
8 2 | 1 2 | 3 6 | 6 5 | 1 1 | 2 | |
2 1 | 1 3 | 2 1 | 3 5 | 3 4 | 1 | |
L | 4 | 3 | 2 | 1 | 3 |
Рис.1. Затраты на сооружение отдельных участков дороги
Шаговое управление на i-ом шаге представляет собой направление движения север (), юг (¯), восток (®) или запад (). Требуется найти такое оптимальное управление u*, при котором суммарные затраты W на сооружение участков минимальны, т. е. 
. Для каждой узловой точки прямоугольной сетки, необходимо найти условное оптимальное управление-направление движения. Выбирается это управление так, чтобы затраты всех оставшихся до конца шагов (включая данный) были минимальными.
Условную оптимизацию начинаем с последнего 10-го шага. Рассмотрим правый верхний угол прямоугольной сетки (рис. 2). За один (последний) шаг можно попасть в точку М из точек А1 и А2. Из этих точек управление вынужденное: из А1 необходимо двигаться на восток (®), что обойдется в 1 условную единицу, а из А2 - на север (), что приводит к затратам в 4 единицы.
Таким образом, условная оптимизация последнего шага проведена и условный оптимальный выигрыш для каждой из точек А1 и А2 найден и записан в соответствующем квадрате.
Аналогично оптимизируем предпоследний 9-й шаг, который может быть сделан из точек В1, В2 и В3. Отличие данного шага от последнего 10-го заключается в том, что управление здесь уже не вынужденное. Например, из точки В2 возможно движение как на север () с затратами до точки М в 2 + 1 = 3 единицы, так и на восток (®) с затратами 4 + 4 = 8 единиц. Условное оптимальное управление из точки В2 помечено на рис.3 в виде стрелки - (). Найденные для В1, В2 и В3 условные оптимальные управления и условные оптимальные выигрыши также представлены на рис.3 соответственно в виде стрелок и значений в квадратах. Двигаясь от предпоследнего шага назад к L, найдем для каждой точки условное оптимальное управление (), (¯), (®) или () и условный оптимальный выигрыш (затраты до конца пути), который записывается в квадрате. Конечный результат процедуры оптимизации показан на рис.4. В прямоугольнике при точке L записан оптимальный выигрыш на всем протяжении пути из L в М: W* = 21.
Рис.2. Десятый шаг Рис.3. Девятый шаг
Рис.4. Оптимальная трасса
Оптимальная трасса отмечена на рис. 4 утолщенными линиями. Отметим, что возможны два равнозатратных оптимальных решения. u* = (,,,®,®,®,,,®,®) и u* = (,,,®,®,®,®,,,®).
ЛИТЕРАТУРА
1. Габасов, Р. Основы динамического программирования / Р. Габасов, - Мн.: Изд-во БГУ, 1975. - 264 с.
2. Игнатенко, и оптимизация процессов лесозаготовок: учеб. пособие для студентов специальности «Лесоинженерное дело» / , , . – Мн.: БГТУ, 2004. – 180 с.
