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

Такие системы получили большое распространение в АСУ ТП и АСУП.

Рис. 18

Для анализа основных особенностей управления в иерархических системах общесистемное описание функционирования двухуровневых системы.

Система содержит:

вышестоящую управляющую систему C₀;

n нижележащих управляющих систем C1, …, Cn;

управляемый процесс P.

В системе выделены два вида вертикального взаимодействия между подсистемами:

Передача командных сигналов - (вниз) сигналя от управляющих систем C1, …, Cn к управляемому процессу P.

m_i - управляющее воздействие от C₀ к C_i;

s_i - координирующее воздействие или вмешательство.

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

Передача наверх информационных сигналов или сигналов обратной связи различным управляющим системам иерархии.

Благодаря этому каждая управляющая подсистема имеет сведения о ходе протекания самого процесса в объекте управления и о качестве управления.

Введем обозначения m M - множество управляющих сигналов; w W - множество внешних воздействий; r R - информирующий сигнал первого уровня;

- множество координатных сигналов

- множество выходных сигналов; - множество информационных сигналов 2-го уровня

Примечание 1. Модель функционирования 2 уравнений системы будет представлять на языке теории множеств.

Управляемый процесс задаётся отображением , где

- множество управляемых сигналов для i-го управляющего органа []

Модель функционирования i-ой локальной системы управления (i = 1,2,…,n) реализуется в виде отображения

Модель координатора выглядит как

Соответ. инф-е обратной связи 1 и 2-го уровней реализуются отображениями:

При анализе особенностей функционирования и принципов управления полагаем:

Влияние внешней среды (возмущ.) либо полностью отсутствует, либо полностью заранее известно (система, в целом, функционирует в условиях определённости)

Общая задача управления и частные задачи управления, решаемые на нижележащем уровне являются задачами оптимизации.

§2 Глобальная задача оптимизации

До отражаем глобальную цель управления 2-ур. системы и сводится к следующей подстановке:

найти

g(m) - глобальная целевая функция

При рассмотрении локальных оптимизированных задач предполагается, что управляемый процесс P представлен в виде композиции подпроцессов P_i (i = 1,2,…,n), взаимодействующих между собой, причём упр-е подпроцесса P_i находится в ведении соответствующего управляющего элемента C_i

Взаимодействие подпроцессов P_i реализуется через множество связей

Пусть D_i - локальная оптимизирующая задача, решаемая i-ым управляющим органом ниж. ур., а локальная оптимизирующая функция качества решения данной задачи выглядит =>

, где - множество задания целевой функции.

Принципы координации являются центральным звеном при построении иерархических систем управления. Имеются 2 способа воздействия на локальные задачи

Имеются 2 способа воздействия на локальные задачи оптимизации со стороны верхнего уровня.

Через функцию качества G - координация путем изменения цели.

Через изменения параметров множеств. (?) связи Ui (i = 1,…,k) в выделенном классе подпроцессов pi - координация путем изменения ограничений.

Первый способ предполагает (?) задание функции качества, в результате чего координирующий сигнал Si направлен на выбор соответствующей функции качества функционирования из заданного числа i-й упр-й (?) системы.

Второй способ на принципах:

Развязывания взаимодействий Ui

Прогнозирования взаимодействий Ui

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

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

Традиционно ИСУ изображают в виде структуры «треугольного» вида, в которой любой структурный элемент объединяет информационные и управляющие функции.

Выделим последовательно четыре уровня управления: локального регулирования (уровень САР), локальной оптимизации (уровень САУ), координации локальных систем оптимизации, оперативного управления и принятия решений.

Рис. 19 Рисунок 1 Структура иерархической системы управления

Рассмотрим задачи, решаемые на каждом уровне иерархии

2.1 Уровень САР

На этом уровне обеспечивается решение задач локального автоматического регулирования, то есть стабилизации или программного изменения параметров объектов в соответствии с установками, задаваемыми на вышерасположенном уровне САУ. В качестве технических средств на уровне САР цифровые могут быть использованы как регуляторы (в том числе и микропроцессорные), так и традиционные регуляторы непрерывного действия.

2.2 Уровень САУ

Предназначен для оптимизации при управлении ограниченным комплексом подобъектов, подчиненных соответствующим оптимизаторам. Критерии цели управления, рассматриваемые на этом уровне, могут отличаться от общего критерия функционирования всей системы. Во всяком случае в них необходимо учитывать «собственные интересы» подчиненных оптимизатору подсистем. Технические средства уровня САУ, а также средства более высоких уровней иерархии должны содержать ЭВМ, так как без них немыслима оптимизация.

2.3 Уровень координации

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

2.4 Уровень оперативного управления и принятия решений

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

Установив основные задачи, решаемые на каждом уровне иерархии, перейдем от исходной структурной схемы к эквивалентной схеме ромбовидной формы Будем называть такие структуры «даймонд-структурами».

Приняты обозначения:

0.1-0.m₀ - объекты управления

- датчики информации для локальных регуляторов и наблюдающие устройства.

- собственно локальные регуляторы (без датчиков), реализующие выбранные законы.

- - локальные оптимизаторы

- - информационные подсистемы для локальных оптимизаторов, воспринимающие информацию от датчиков и перерабатывающие ее в необходимую форму.

- - координирующие оптимизаторы.

- - информационные подсистемы для координаторов.

- орган оперативного управления и принятия решения.

- информационная подсистема для оперативного управления и принятия решений, в том числе информационный зал с системами отображения информации и ЭВМ.

Введение «даймонд - структур» позволяет более четко выделить и связать воедино задачи двух типов, которые необходимо решать в процессе проектирования систем управления .

К первому типу относятся задачи анализа и синтеза динамических контуров ?управления?, структурируемые при проведении ?«разрезов»? «даймонд - структуры» по вертикали.

Второй тип составляют задачи статического расчета, структурируемые при выполнении «разрезов» «даймонд-структур» по горизонтали. На любом из уровней иерархической информационной или управляющей части системы.

Рис. 20 Diamond - структура

Кроме того, необходимость перехода к «даймонд - структурам» вызвана тем, что требуется:

разделить управляющие и информационные звенья системы на всех уровнях иерархии, так как их функции являются настолько сложными, что также необходимо рассматривать в виде совокупность звеньев; ?более? того, в некоторых современных многообъектных системах управляющие и информационные звенья разделены территориально;

выделить из системы локальные динамические контуры управления для проведения динамического расчета;

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

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

Для формализации функционирования задач каждого звена рассмотрим систему с «треугольной» структурой.

Любое звено в структурах такого типа с номером ; находящееся на j-м иерархическом уровне (), можно представить в виде отображения , ,

где - множество управляющих (координирующих) сигналов звена вышестоящего уровня;

- множество сигналов обратной связи, поступающих от подчиненных звеньев;

- множество возмущенных воздействий данного звена.

- множество выходных сигналов звена i воспринимаемых подчиненными звеньями j-ого уровня.

На рис.3. представлены сигналы звена j,i: Звено А типа:

141

Рис. 21

Сигналы обратной связи, поступающие от данного звена к звену более высокого уровня иерархии с индексом обозначены . Эти сигналы не включены в ? так как они являются продуктом другой функциональной задачи, того же звена j,I - задачи информационной обработки сигналов.

В простейшем случае может оказаться, что , то есть звено выполняет функции ретрансляции сигналов. Однако в большинстве случаев, информация, получаемая из сигналов , должна преобразовываться специальным образом в ту форму, которая обеспечивает функционирование звена . Этот недостаток устранен в «даймонд-структуре».

Для звена самого верхнего иерархического уровня отображается , а для управляемого объекта

Рассмотрим пару звеньев для системы с «даймонд-структурой» соответствующих звеньев j,i в системе с структурой.

Управляющее звено , информационное - j,i

Получим два отражения:

a)

б)

a) - влияет на выработку управляющих сигналов

б) - влияет на оценку достигнутых состояний или результатов

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

заменим S_n,1 для верхнего уравнения двумя отображениями:

a)

б)

141

Рис. 22 Звено в даймонд-структуре

a) определяем принятия решений по информации о достигнутых результатах , наличных ресурсах - и

б) характеризуем систему подготовки и представления информации для принятия решений на верхнем уровне.

При решении экстрем. задач методами классического анализа используется тот факт, что т. X^* доставляется экстрем. зн. f(x) заданной на [a,b] есть либо T, либо T, где произв. не определённое, либо одна из 2-х крайних точек области определения [a,b]. Другими словами т. X^* принадлежит множеству

141

Рис. 23

§3 Оптимальное управление

3.1 Постановка задачи управления

В процессе функционирования сложных систем управления проблема принятия решения реализуется как проблема выбора управления, переводящего систем из заданного состояния в желаемое.

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

Если существует выбор оптимальной стратегии поведения, то X(t) - векторная функция и целевой функции J(X(t)).

На компоненты X и X(t) обычно накладываются ограничения.

Использование классических методов отыскания экстремума точек при решении практических задач оптимизации управления наталкивается на ряд трудностей:

Сложность аналитическая, представленная исследуемой функцией. Что затрудняет отыскание совокупности стационарных точек S₁={x: x [w,b]? ds/dx = 0} и множества точен, где производная не определена. С увеличением размерности необходимо решать систему уравнений частных производных от исследуемой функции по каждой из переменных.

(15)

Многоэкстремальность целевой функции.

Это типичная ситуация.

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

Метод Ньютона

Необходимые и достаточные условия экстремума:

. К стац. точкам относятся все точки, в которых функция достигает max или min, а также точки перегиба.

Наличие ограничений.

Это затрудняет отыскание на области допустимых значений определения аргументов.

Если экстремум функции достигается на <xxx> области <xxx> значений аргументов, то сумма ??? в этих точках не равна 0 (м. <xxx>). При решении <xxx> <xxx> <xxx> <xxx> стационарных точек <xxx> <xxx> <xxx> не определенных) необходим анализ всех крайних точек.

Рис. 24

Пусть X = {x₁, x₂, …, x_n} - вектор, компонентами которого являются варьируемые переменные. Тогда ограничения делятся на:

Ограничения I-го типа (прямые): a_j ? x_j ? b_j, j = 1, 2, …, n

Частный случай прямых ограничений - ограничения на знак переменных: x_j ? 0, j = 1, 2, …, n

Ограничения II-го типа (функциональные): g_i(x₁, x₂, …, x_n) = 0, i = 1, 2, …, m

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

Если вектор X имеет размерность n, то при наличии только прямых ограничений, число крайних точек допустимого множества равен 2ⁿ и растет с увеличением n.

§4 Целочисленность переменных

Обычно, область определения критериальной функции является дискретной (переменные - неделимые объекты).

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

Глава 5. Элементы линейного программирования

§5 Общая задача линейного программирования

Определение 9. Задача линейного программирования - задача, математическая модель которой представляется в виде: a₁x₁ + a₂x₂ + ... + a_nx_n = b₀.

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

§6 Транспортная задача

Пусть имеется m пунктов производства некоторого продукта и n пунктов его потребления. Производство и потребление сбалансированы (объемы производства и потребления равны). Задача заключается в отыскании рационального плана перевозок продукции из пунктов производства в пункты назначения, при котором транспортные расходы минимальны.

План перевозок должен удовлетворять следующим требованиям (равенство объемов):

Спрос любого из пунктов потребления должен полностью удовлетворяться

Вся продукция каждого пункта производства должна полностью использоваться.

Лекция 6 Элементы вариационного исчисления и принципы максимума Понтрягина.

§7 Постановка задачи оптимального управления

Состояние системы управления в любом времени можно характеризовать с помощью набора численных значений координат в фазовом пространстве X, а эволюцию системы - траекторией в этом пространстве:

(16) X(t) = (x₁(t), x₂(t), …, x_n(t)).

В фазовом пространстве выделяют область допустимых значений (S-область).

Аналогично, вводится пространство уравнений U с числом измерений r, равным числу независимых управляемых воздействий. Тогда закон изменений управляемых воздействий задаётся однозначно траекторией в пространстве управления:

(17) U(t) = (u₁(t), u₂(t), …, u_r(t))

Вводим область допустимых управлений .

Любой процесс управления отображается траекториями одновременно в пространствах X и U. Траектория в пространстве U выбирается в процессе управления, траектория в пространстве X для заданной системы определяется выбором траектории из U.

Любое реальное движение системы отображается траекториями, не выходящими за пределы областей S и .

В крайнем случае они могут полностью или частично проходить по их границам. Из ограниченности областей S и следует невозможность мгновенного изменения состояния системы (в этом случае траектория должна выйти за пределы S и , т.к. x₁(t) … и u₁(t),… , ).

В то же время, u1(t),…, могут, оставаясь в пределах допустимой области , изменяться скачком. Такой идеализации соответствуют кусочно-непрерывные управления с конечным числом разрывов 1-го рода (скачков).

§8 Задача оптимального управления.

Отыскать управление U*(t) = (u*1(t), u*2(t), …, u*r(t)), принадлежащее -области, доставляющее экстремальное значение некоторому критерию эффективности Ф и обладающее тем свойством, что соответствующая выбранному управлению траектория X(t) = (x₁(t), x₂(t), …, x_n(t)) в фазовом пространстве принадлежит S-области.

Т.обр., численное значение критерия эффективности зависит от характера функций U(t) и X(t), т.е.

(18) Ф = Ф[U(t), X(t)] - есть функционал U(t) и X(t).

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

Это задачи с закреплёнными концами.

Эти задачи, а также задачи, в которых ограничения на U(t) и X(t) отсутствуют, могут быть решены методами классического вариационного исчисления.

§9 Основные принципы вариационного исчисления

Рассмотрим простейшую задачу вариационного исчисления.

Задан функционал вида

(19)

зависящий от функции y(x), определённой на интервале (x₁, x₂). Необходимо отыскать непрерывную функцию y(x) с непрерывной первой производной, проходящей через две фиксированные точки (x₁, y(x₁)), (x₂, y(x₂)) и доставляющую экстремум (19).

Пусть для определённости необходимо обеспечить максимум (19).

Стандартный способ решения состоит в следующем. Сначала предполагают, что искомая максимальная функция y(x) уже найдена. Тогда любое отклонение от y(x) даёт меньшее значение I. Далее, выберем любую функцию Z(x), которая обращается в ноль при x=x₁ и x=x₂ и образуем y*(x) = y(x) + z(x) ( - малый параметр).

Z(x) называется вариацией функции y(x) и обозначается y.

Подставив y*(x) в (19)

(20)

(20) для выбранной функции z(x) зависит только от . Т.к. I() достигает максимума при =0, то производная по при =0 должна обращаться в 0, т.е.

.

Но

Интегрируя второе слагаемое по частям, имеем

Поскольку z(x₁) = z(x₂) = 0, то, обозначая и , получаем

(21)

(21) должно выполняться для любой функции z(x).

Отсюда дифференциальное уравнение Эйлера:

(22)

Имея в виду, что перепишем (22) в виде

(23)

(24)

Решения уравнения Эйлера называют экстремалями.

(24) представляет собой нелинейное дифференциальное уравнение 2-го порядка, интегрировать которое довольно сложно.

Рассмотрим некоторые частные случаи, когда интегрирование упрощается.

Функция F не зависит от x. При этом функционал (19) приобретает вид

(25)

Тогда в (24) и

(26)

Умножив почленно правую и левую части (26) на y'

Отсюда

(27)

называется 1-м интегралом уравнения Эйлера. Это уравнение 1-го порядка не содержит явно x и потому может быть проинтегрировано, например, путём разделения переменных или путём введения параметра.

Функция F не зависит от y, т.е. рассматривается функционал

В этом случае уравнение Эйлера или

Откуда

(28)

Дифференциальное уравнение 1-го порядка легко интегрируется.

Функция F зависит только от y', т.е.

(29)

При этом в (24) и уравнение Эйлера имеет вид

(30)

Отсюда , т.к. . Тогда y = C₁x + C₂ - семейство прямых линий.

Пример. Найти кратчайшую траекторию из точки A(x₁, y₁) в точку B(x₂, y₂).

Длина дуги кривой y(x), соединяющей A и B, определяется функционалом

(31)

Имеем (7).

Уравнение Эйлера: , откуда y = C₁x + C₂.

С₁ и С₂ находятся из условия.

y1 = C₁x₁ + C₂ ; y₂ = C₁x₂ + C₂

Отсюда

(32)

При этом уравнение экстремали представляет собой уравнение прямой

, проходящей через точки A и B.

§10 Каноническая форма уравнений Эйлера

Введём в уравнение Эйлера

(33)

так называемые канонические переменные p и H в соответствии с выражениями

(34)

Т.к. во второе слагаемое H переменная y явно не входит, то

(35)

Кроме того

(36)

Подставляя (34) и (35) в (33), имеем

(37)

Присоединяя (37) к (36), получаем систему двух уравнений 1-го порядка, эквивалентную уравнению Эйлера 2-го порядка.

(38) ;

Система называется гамильтоновой, или канонической, формой уравнения Эйлера. Заметим, что функция H достигает экстремума по y одновременно с функционалом I, т.е. уравнение Эйлера определяет условие экстремума функции H. В самом деле, т.к. ф-я H не зависит от y', поскольку

, то

Таким образом, необходимое условие экстремума H выполняется при тех условиях, что и уравнение Эйлера.

§11 Вариационные задачи при наличии ограничений

Функционалы, соответствующие критерию оптимальности, зависят от n+r … функций, т.е.

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

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

Эти задачи, также как и задачи классического математического анализа, решаются с помощью метода неопределённых множителей Лагранжа.

§12 Метод неопределённых множителей Лагранжа

Отыскать вектор X, доставляющий экстремум целевой функции

F(X) = F(x1, x2, …, xn) (1)

И удовлетворяющий системе ограничений в форме равенств

g₁(x₁, x₂, …, x_n) = 0,

…

gm(x1, x2, …, xn) = 0 (2)

Cформируем функцию Лагранжа Ф(X) следующим образом:

(3)

где - неопределённые множители Лагранжа.

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

Действительно, получаем систему из (n+m) уравнений с таким же количеством неизвестных:

(4)

Пусть область S состоит из всех X, для которых выполняются ограничения (2), тогда понятно, что для XS

(5)

т.к. gi(x1, x2, …, xn) = 0

С другой стороны, замечаем, что экстремальная точка функции Лагранжа X*S, т.к. (2) входят в (4). Отсюда с учётом (4) получаем требуемое: экстремальная точка функции Лагранжа , получаемая в результате решения системы уравнений (4) определяет набор {x*j}, удовлетворяющий ограничениям (2) и доставляющий экстремальное значение целевой функции (1).

Пример. (Задача Д…)

Отыскать набор {x1, x2}, максимизирующий целевую функцию F(x1, x2) = x1x2 и удовлетворяющий ограничению 2x1 + x2 = C.

Решение. Формируем функцию Лагранжа

Беря частные производные по x1, x2 и , образуем систему уравнений

(6)

Выразив x1 и x2 из первых двух уравнений системы (6) через , подставим полученные значения в третье уравнение и решим его относительно .

При этом =c/4, откуда, используя первые два уравнения системы (6),

x1=c/4

x2=c/2

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

,

причём функции x(t) и u(t) связаны между собой соотношениями вида

Тогда составляется вспомогательный функционал

где - неопределённые функции,

Этот функционал исследуется уже на безусловный экстремум. В результате получаем систему из n+r уравнений Эйлера:

(1)

дополненную уравнениями связей

(2)

Решения (1) совместно с (2) дают искомые экстремали.

Несмотря на наличие методов решения вариационных задач на условный экстремум, необходимо отметить, что возможности классического вариационного исчисления заметно сокращаются в задачах, где на траектории x(t) и u(t) накладываются какие-либо ограничения.

В самом деле, пусть рассматривается задача отыскания экстремума функционала

(3)

и ограничения (4)

Равенство определяет границу допустимой области, только внутри которой может находиться функция, доставляющая экстремум функционалу.

Ограниченная область, включающая и свою границу, называется замкнутой.

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

Основное необходимое условие экстремума (уравнение Эйлера) выводилось в предположении о свободе варьирования, т.е. считалось, что если y(x) - экстремаль, то y(x)+z(x) и y(x)-z(x) - допустимые функции и можно сравнивать значение функционала (3) на экстремали y(x) со значением его на y(x)+z(x) и y(x)-z(x). Однако, это не всегда возможно, т.к. если y(x) проходит на некотором участке X0 по границе допустимой области, т.е. y(x)=(x), xX0, то функция y(x)-z(x), где >0, на этом участке уже выйдет за пределы допустимой области.

Таким образом, для замкнутой допустимой области вывод уравнения Эйлера становится некорректным, а экстремаль, найденная из уравнения Эйлера, уже может не определять оптимальную реализуемую траекторию.

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

§13 Принцип максимума Понтрягина (1956-61 гг.).

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

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

(1)

где X=(x₁, x₂, …, x_n) - вектор фазовых координат объекта,

U=(u₁, u₂, …, u_r) - вектор управления.

Более сжатый вид системы уравнений: .

Управление U(t) принадлежит ограниченной замкнутой области , а фазовая траектория X(t) - к ограниченной, но открытой области S'.

Задача состоит в том, чтобы из кусочно-непрерывных управлений выбрать такое U(t), что при переходе из заданной начальной точки X(t_н)=(x_1н, x_2н, …, x_nн) в заданную конечную точку X(t_к)=(x_1к, x_2к, …, x_nк) функционал

(2)

достигал экстремума.

В дальнейшем для определённости будем рассматривать задачу отыскания управления, минимизирующего I.

Введя дополнительную координату состояния системы

и присоединив к исходной системе ещё одно уравнение

,

получаем систему уравнений

(3)

правые части которых не зависят от x₀.

Введение дополнительной координаты x₀(t) расширяет вектор состояния системы, увеличивая его размерность на единицу. Используя расширенный вектор фазовых координат и его производную

,

запишем систему (3) в виде

.

Введём, наконец, совокупность вспомогательных произвольных функций ₀(t), ₁(t), …, _n(t), с помощью которых образуем так называемую функцию Гамильтона:

(4)

Структура функции Гамильтона аналогична структуре функции Лагранжа, если считать, что функции играют роль ограничений, а функции - роль неопределённых множителей Лагранжа.

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

(5)

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

Для того, чтобы управление u*(t), переводящее систему из X_н в X_к , было оптимальным, т.е. доставляло минимум функционалу (2), необходимо, чтобы при любом t_н t t_к :

существовала непрерывная ненулевая вектор-функция (t) = (₀(t), ₁(t), …, _n(t)), составляющие которой удовлетворяли бы системе уравнений

(6)

(7)

функция Гамильтона

,

представляющая собой скалярное произведение вектора (t) на вектор скорости изображающей точки фазовой траектории, достигала бы максимума по u(t) на управлении u*(t).

в момент времени t=t_к выполнялись соотношения

Система уравнений (6) и (7) называется гамильтоновой и содержит две группы уравнений:

(6) - уравнения движения объекта;

(7) - служит для непосредственного отыскания функций (t).

Обычно система (6) и (7) записывается в более сжатом виде:

(8)

Заметим, что решение системы уравнений (8) в общем случае может оказаться весьма трудоёмким или даже невыполнимым делом.

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

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

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

В этом случае оптимизируемый функционал равен

и

Поэтому для функции Гамильтона выполняется

Поскольку, как отмечалось выше, , не зависят от x0, то и , откуда следует, что максимум достигается одновременно с максимумом функции

(9)

Кроме того, т.к. для оптимального управления и , то

(10)

Для задачи о предельном быстродействии гамильтонова система приобретает вид:

(11)

Пример. Управляемый объект массой m=1 , движущийся без трения по горизонтальной прямой, снабжён двигателем, развивающим силу u, причём |u|1.

Введём фазовые координаты объекта следующим образом:

x₁(t) - положение объекта на прямой в момент времени t;

x₂(t)=dx₁(t)/dt - скорость объекта в момент времени t.

В соответствии со вторым законом Ньютона уравнения движения объекта имеют вид:

(12)

(13)

Требуется отыскать управление, удовлетворяющее (13) и переводящее объект из заданного начального состояния с координатами в начало координат за минимальное время.

В рассматриваемом случае и .

Поэтому в соответствии с (9) функция H имеет вид:

(14)

Составим гамильтонову систему уравнений:

(15а)

(15б)

Используем систему (15б) для отыскания ₁ и ₂.

Решение этой системы легко находится и имеет вид:

(16)

d1 и d2 - постоянные интегрирования.

Найдём оптимальное управление u*(t), максимизирующее H:

Подставляя (16) в (14), получаем

(17)

Функция H линейно зависит от u и потому имеет максимум в одной из крайних точек допустимого интервала значений u. Действительно,

, т.е.

Здесь

Величина max H для оптимального управления равна:

Проверим выполнение условия 3 принципа максимума:

т.е. требуемое условие выполняется.

Заметим, что линейная функция может менять знак на любом интервале лишь один раз. Таким образом, оптимальное управление u*(t) является кусочно-постоянной-функцией, принимающей значение 1 и имеющей на интервале t_н t t_к одно переключение.

Для отрезка времени, на котором u*(t)1 в силу (12) имеем

(18)

где С1, С2 - постоянные интегрирования.

Таким образом, кусок фазовой траектории, для которого u1 представляет собой дугу параболы (18). Семейство парабол (18) показано на рисунке 1а.

По этим параболам фазовые точки движутся снизу вверх (т.к. , т.е. ).

Аналогично для отрезка времени, когда u-1, имеем

(19)

Семейство парабол, соответствующих (19) изображено на рисунке 1б, причём по этим параболам фазовая точка движется сверху вниз (т.к. , т.е. ).

Рис. 25 Семейство парабол

Как показано выше, любое оптимальное управление имеет на интервале tн t tк не более одного переключения. Фазовая траектория состоит из двух кусков парабол (рис. 2 а, б), примыкающих друг к другу, причём второй кусок лежит на той параболе, которая проходит через начало координат.

Рис. 26

Таким образом, в любом семействе парабол (18) и (19) особую роль играет парабола, проходящая через начало координат, т.к. ветвь любой из этих парабол, ведущая в начало координат, является линией переключения (соответствует моменту изменения знака уравнения).

Рис. 27 Линия переключения

На рисунке 3 изображено всё семейство полученных оптимальных траекторий (линия переключения АОВ - выделена). Если начальное положение объекта соответствует точке выше линии АОВ, то фазовая точка под воздействием управления u=-1 должна двигаться до тех пор, пока не попадёт на дугу АО. В этот момент управление переключается на u=+1, и фазовая точка по дуге АО достигает начала координат. Если же начальное положение объекта соответствует точке, лежащей ниже АОВ, то начальное оптимальное управление u=+1 и фазовая точка движется по соответствующей параболе до пересечения с дугой ВО. При этом управление переключается на u=-1, под воздействием которого фазовая точка по дуге ВО достигает начала координат. Наконец, если начальная точка лежит на АОВ, то оптимальное управление не имеет переключения и принимает значение +1 или -1 в зависимости от того, на какой дуге линии АОВ (АО или ВО) находится начальная точка.

Теперь не представляет никакого труда непосредственно вычислить момент переключения. Пусть для определённости координаты начальной точки x_1н и x_2н таковы, что точка (x_1н , x_2н) лежит выше линии АОВ (u-1). Тогда в соответствии с (19) начальный участок фазовой траектории лежит на параболе, описываемой уравнениями

причём

Положив t = t_н = 0, имеем

, откуда

(20)

Точка пересечения С может быть найдена как точка пересечения параболы (20) с линией АО, уравнение которой имеет вид

(21)

Решив уравнения (20) и (21) совместно, имеем

Координату x2 точки пересечения С следует взять со знаком минус, т.к. эта точка лежит на линии АО, т.е. ниже оси абсцисс. Итак,

(22)

Т.к. при движении из начальной точки до точки С

, то обозначив момент переключения через tC , имеем

(23)

Объединяя (22) и (23), получаем

Также легко вычислить общую продолжительность процесса. Начиная с момента переключения tC до окончания процесса, фазовая точка движется под воздействием управления u=+1 и её траектория описывается уравнением (18).

Поскольку x₂(t_к) = 0 и на этом участке траектории , откуда

(24)

Подставляя в (24) t = tC и используя (23), имеем

Теперь , откуда имея в виду (22) получаем

Аналогично отыскивается момент переключения и общее время процесса для случая, когда начальная точка лежит ниже линии АОВ.

Глава 6 Элементы динамического программирования.

§14 Оптимизация непрерывных систем

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

В основы метода положен принцип оптимальности. Приведём его формулировку.

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

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

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

Управление определяется конечной целью управления и состоянием системы в рассматриваемый момент времени.

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

Рассмотрим задачу о минимизации функционала

(1)

для системы, поведение которой описывается совокупностью дифференциальных уравнений вида

(2)

Х - вектор из области допустимых значений параметров системы, характеризующий состояние системы в данный момент времени;

U - вектор управления из области допустимых управлений ,

В начальный момент времени t = 0, x = x_н , время T фиксировано.

Пусть в некоторый момент времени 0 < < T состояние системы характеризуется вектором x(). Начиная с момента времени в течение временного интервала продолжительностью используем некоторое произвольное управление u(t).

Тогда в соответствии с (2) в момент времени + система будет находиться в точке

Будем считать теперь, что начиная с момента времени + и до конца, т.е. до t = T, используется оптимальное управление

u*(t), + t T.

Обозначим через I*() минимальное значение функционала (1) при оптимальном управлении u*() (при t T), т.е.

Тогда значение функционала (1) при использовании управления

может быть найдено из соотношения

Понятно, что ввиду неоптимальности управления

(3)

При этом равенство в (3) может быть получено, только если в качестве будет использовано оптимальное управление, т.е.

(4)

С точностью до бесконечно малых более высокого порядка, чем , можно считать, что

С учётом этого, меняя на t , перепишем (4) в виде

(5)

Допустим теперь, что для I(t) имеем частные производные по всем координатам xi и по времени t. Тогда, разлагая I*(t) в ряд Тейлора, имеем с точностью до бесконечно малых первого порядка

(6)

(7)

Имея в виду (7), подставим (6) в (5). При этом

(8)

Принимая во внимание, что I*(t) и не зависит от u(t), получаем

(9)

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

Метод динамического программирования оказывается весьма эффективным при решении дискретных оптимизационных задач.

§15 Оптимизация дискретных систем

Пусть система может находиться в одном из состояний дискретного множества S. S* - дискретное фазовое пространство.

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

(12)

Здесь - состояние системы на i-м шаге.

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

§16 Градиентные методы.

Пример отыскания максимума функции одной переменной.

Пусть y=f(x) (Рис. 28).



Рис. 28

Выберем произвольную точку х из области определения функции y=f(x). Заметим, что если точка выбрана слева от точки максимума (х = х₁), то производная от f(x) в точке х₁ и следовательно точка при разумном выборе величины параметра k находится ближе к экстремальной точке х₀.

Если же выбранная точка оказалась правее точки х₀ (х = х₂), то та же конструкция по прежнему приближает решение к экстремальной точке.

Таким образом, может быть построена последовательность точек

x(1), x(2), …, x(l), x(l+1), … , (1)

вычисляемых по рекуррентному правилу

, (2)

стягивающаяся к искомой экстремальной точке х₀.

Сходимость последовательности (1) к точке х₀ обеспечивается рациональным выбором численного значения k, определяющего длину шага. Рекурсивное соотношение (2) легко обобщается на случай отыскания экстремума функции многих переменных.

Пусть X*^T=(x*₁, x*₂, …, x*_n) - вектор, доставляющий максимальное значение функции F(x₁, x₂, …, x_n). Введём вектор-столбец значений частных производных от оптимизируемой функции F(X) в точке X^l , называемый градиентом, т.е.

(39)

и матрицу K(X^l).

Теперь вычисление точки X^l+1 на очередном шаге градиентной процедуры осуществим по формуле

(40) (3)

В соответствии с (3) вектор-градиент определяет направление перемещения от X^l к X^l+1, а матрица K(X^l) - длину шага.

Длина шага выбирается из следующих соображений:

её не следует выбирать слишком большой, чтобы не «проскочить» экстремум, т.к. при этом появляется опасность зацикливания;

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

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

При этом (3) записывается в виде

,

где скаляр kl определяется из условия

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

В результате проведения некоторого числа шагов в соответствии с (3) обеспечивается попадание внутрь произвольно малой окрестности экстремальной точки.

Критерием для останова может служить величина модуля вектора-градиента

Градиентную процедуру считаем законченной, как только численное значение модуля окажется < .

Существенный недостаток: при реализации каждая итерация выполняется независимо от других, т.е. информация, которая могла бы ускорить сходимость, не накапливается и не используется.

«Метод переменной метрики» использует информацию о поведении оптимизируемой функции в уже пройденных точках.

Достоинство: не требуется наличия аналитического представления производной от оптимизируемой функции и умение решать систему уравнений (7.1).

Необходимо уметь вычислять частные производные от функции F(X) в отдельных точках области определения.

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

Методы, использующие случайный поиск (Нелокальный метод)

Градиентный метод приводит к экстремальной точке, если эта точка является единственной в области определения функции S.

Обычно целевая функция многоэкстремальна. Нужны нелокальные методы.

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

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

С ростом числа проб вероятность достижения экстремума 1.

Недостаток: информация об уже проведённых опытах не используется для проведения последующих.

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

Рассмотрим два возможных варианта построения таких процедур.

Вариант 1. Пусть задача состоит в отыскании набора переменных Х*, минимизирующего целевую функцию f(X) , т.е.

В области S определения функции f(X) выбираем в соответствии с некоторым случайным механизмом совокупность точек

Используя каждую из этих точек в качестве начальной для организации градиентной процедуры, получаем в результате её реализации совокупность точек

- локальные минимумы.

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

Теперь в качестве приближения к глобальному экстремуму выберем такую точку из Z, для которой

С увеличением числа проб q вероятность достижения глобального экстремума монотонно возрастает.

Вариант 2. Выбираем в области определения функции f(X) совокупность точек

.

Далее вычисляем значения функции f(X) в каждой из этих точек, получая при этом совокупность чисел

Теперь, в отличие от варианта 1, осуществляем однократный градиентный спуск из той точки , для которой значение функции минимально, т.е.

В результате градиентного спуска получаем точку

которую и принимаем в качестве оценки для глобального экстремума X*.

С увеличением q вероятность достижения глобального экстремума возрастает.

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

§17 Метод оврагов (нелокальный метод).

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

К 1-группе (несущественные переменные) относят переменные, изменение которых приводит к существенным, легко обнаруживаемым изменениям функции.

Ко 2-й группе (существенные переменные) относят переменные, изменение которых вызывает весьма малые, несущественные изменения функции.

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

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

Метод оврагов реализуется следующим образом:

Из произвольной точки А0 (рисунок 1), используя любую локальную процедуру (градиентные методы), производится ряд итераций спуска.

Рис. 29 Итерации спуска

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

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

Обнаружив это, остановимся (пусть это будет точка В0).

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

Полученная в результате «овражного» шага точка А2, очевидно, вновь окажется на склоне оврага и может быть выбрана в качестве начальной для очередной процедуры локального спуска.

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

Случайный шаг используется лишь один раз (от точки В0 к точке А1). В дальнейшем чередуются градиентные и овражные шаги.

Поиск глобального экстремума по методу оврагов содержит элементы самоорганизации.

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

Глава 8 Структурный синтез

§18 Постановка задачи структурного синтеза

При определении структуры БСУ производится

выбор задач управления, возлагаемых на технические средства;

выбор алгоритмов их реализации;

формирование общей структуры системы и распределение выбранных задач по узлам и уровням системы;

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

Перечисленные выше этапы создания БСУ взаимно связаны, и задачи каждого из них решаются с учётом ресурсов, выделяемых на создание системы.

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