Решение дискретных задач оптимизации

 

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

 

(3.1)

 

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

 

(3.2)

 

Математическая постановка задачи:

определить

 

 

На основании выражения (3.2) можно утверждать, что величина критерия оптимизации в конечном итоге зависит только от начального состояния и искомой стратегии:

 

 

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

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

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

 

(3.4)

 

Обозначим минимальное значение критерия оптимизации на этом шаге тогда

 

(3.5)

 

Затем рассматриваются два последних участка траектории с номерами и . Считается, что оптимальное управление и соответствующее ему значение критерия на последнем участке известно, тогда минимальное значение критерия оптимизации на двух участках можно представить:

 

(3.6)

 

Из выражения (3.6) следует, что при оптимизации критерия на двух участках решается задача с одним переменным , т.е.:

 

(3.7)

 

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

 

(3.8)

 

Для определения необходимо найти оптимальное управление в момент времени , т.е. на третьем от конца траектории участка. По аналогии минимальное значение критерия на всей траектории ( участков)

 

(3.9)

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

 

 

…………………………………………………………………………… (3.10)

 

 

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

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

Требуется определить оптимальную траекторию, на которой критерий оптимизации принимает минимальное значение:

 

(1.П)

 

где - индекс состояния системы, через который пройдет оптимальная траектория, - индекс временного шага.

Так как при допустимых состояний два, согласно принципу Беллмана решение начинается с момента времени . По заданному правилу (аналитическому выражению) вычисляется значение критерия для всех допустимых состояний процесса в момент времени т.е. значения . Из каждого допустимого состояния временного слоя можно перейти в каждое допустимое состояние временного слоя : для каждого состояния для можно определить три значения критерия соответствующих двум переходам. Затем из них определяется переход с минимальным значением критерия. Этот переход отмечается(запоминается) и это состояние оценивается этим значением критерия. Для примера на рис.3 оптимальные переходы помечены жирной линией. Следовательно, в общем случае величина определяет минимальную стоимость перехода из всех возможных состояний времени в состояние

 

(2.П)

 

Например, для рассматриваемой задачи, для узла с индексом значение стоимости перехода в этот узел:

 

 

для узла с индексом :

 

 

При этом стоимость перехода в общем случае когда критерий зависит от "пути" перехода определяется

 

(3.П)

 

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