ОПТИМИЗАЦИЯ В ТЕОРИИ СИСТЕМ

1.10 ОПТИМИЗАЦИЯ В ТЕОРИИ СИСТЕМ.

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

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

Во многих случаях реализация процесса управления требует затрат каких-либо ресурсов: времени, материалов, топлива, электроэнергии.

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

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

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

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

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

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

ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

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

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

КЛАССИФИКАЦИЯ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ.

1. Одношаговые задачи принятия решения.

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

Одношаговая задача принятия решения считается заданной, если заданы пространство состояний природы Q с распределением вероятностей ℰ(U) для всех U∈Q, пространство решений Х и критерий качества принятого решения, который будем называть целевой функцией. Целевую функцию; выражающую в явном виде цели управления, можно рассматривать как выходную величину ОУ и обозначать q.

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

(1) q=q(х,U)

Одинаковая задача принятия решений:

(2) G=(X,Q,q)

Решение задачи (2) состоит в нахождении такого х*∈X, которое обратит в минимум функцию q, т.е. удовлетворяет условию:

(3) х*={х∈Х q(х,U)=min}

Существует ряд методов решения одношаговой задачи.

Задачу называют детерминированной, если нет неопределенности в отношении состояния природы. Пространство состояния природы Q состоит всего из одного элемента U₀, вероятность которого равна 1. В этом случае целевая функция будет зависеть только от состояния ОУ.

(4) q=q(x)=q(x⁽¹⁾,...., x⁽ⁿ⁾)

Одинаковую детерминированную задачу называют классической задачей оптимизации, если ограничения вида:

≤в ____

(5) f_i(x⁽¹⁾,..., x⁽ⁿ⁾) =в , i=1,m

≥в

примем, среди этих ограничений нет неравенств, и нет условий не отрицательности или дискретности переменных, функции f_i(x⁽¹⁾,...,x⁽ⁿ⁾) и q(х) непрерывны и имеют частные производные по крайней мере второго порядка.

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

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

Простейшим примером математического программирования является задача линейного программирования. Она соответствует случаю, когда левые части ограничений (5) и целевая функция (4) представляют собой линейные функции от х⁽¹⁾,..., х⁽ⁿ⁾. В задачах линейного программирования требуется найти неотрицательные значения переменных х⁽¹⁾,..., х⁽ⁿ⁾, которые обращают в минимум целую функцию.

(6) q(x⁽¹⁾,...,x⁽ⁿ⁾)= ∑ C_jx^(j)

j

и удовлетворяет системе ограничений:

(7) ∑ a_ijx^(j)≤в_i, i=1,m

j

Любую задачу математического программирования, отличающуюся от сформулированной, называют задачей нелинейного программирования. В этих задачах или целевая функция или левые части ограничений, или то и другое являются нелинейными функциями от x⁽¹⁾,..., х⁽ⁿ⁾, или когда целевая функция и ограничении имеют вид (6), (7), но предполагается, например, цело численность переменных. Эта задача получил название целочисленного программирования. Одношаговую задачу принятия решений называют стохастической, если пространство состояний природы Q состоит более чем из одного элемента, так что известным является не действительное состояние природы U, а распределение вероятностей ξ(U) на пространстве Q.

(8) q (x)=  ∑  ξ(U) q(x,U)

U∈Q

Поскольку q (х) является детерминированной функцией от х, то задача нахождения переменных х⁽¹⁾,...,х⁽ⁿ⁾, удовлетворяющих ограничениям (5) и обращающих в минимум целевую функцию (8), может быть решена методами линейного и нелинейного программирования.

В настоящее время большое внимание уделяется задачам, в которых решение принимается не одним лицом, а несколькими, причем интересы этих лиц противоположны. Подобные задачи получили название конфликтных ситуаций, а методы их решения рассматриваются в теории игр. При мат-ком описании конфликтной ситуации пространство решений следует рассматривать как прямое приведение двух множеств Х*Y, где Х={х₁,..., х_n} - пространство решений первого игрока; Y - пространство решений второго игрока. Целевая функция:

(9) q=q(x,y)

зависит только от элементов пространства Х*Y.

ДИНАМИЧЕСКИЕ ЗАДАЧИ ОПТИМИЗАЦИИ УПРАВЛЕНИЯ.

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

(10) q=qV[x(t),u(t)]

(10)-целевая функция, качество управления в любой момент времени может быть охарактеризовано как

(11) q(t)=u(t)/x(t)

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

Оценку процесса ОУ можно произвести путем интегрирования целевой функции за все время управления, т.е. за критерий качества принять функционал

T

(12) J(u)= ⌡ qU[x(t),u(t)]dt

 0

В динамических задачах управления наряду с ограничениями вида (5), определяющих пространство допустимых управлений V, приходится иметь дело с интегральными ограничениями вида:

 T

(13) ⌡ H [x(t),u(t)]dt ≤ k = const

0

Оптимальным называют управление u*(t), выбираемого из пространства допустимых уравнений V, такое, которое для объекта описываемого дифференциальным уравнением x=q_v(u, x), x(0)=C, минимизирует критерий качества (12) при заданных ограничениях на используемые ресурсы (13).

ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ.

В общей задаче оптимизации требуется найти вектор x=(x⁽¹⁾,.., x⁽ⁿ⁾) из допустимой области Х, который обращает в min целевую функцию q(х), т.е. такой вектор х*∈X, для которого выполняется условие:

(14) q(x*) ≤ q(x) для всех х∈Х

Если такой вектор х* существует, то он определяет слабый глобальный минимум q*(х) в допустимой области Х. Этот минимум называют слабым, т.к. он удовлетворяет нестрогому (слабому) неравенству, глобальным или абсолютным, потому что неравенство справедливо для любого х∈X. Минимум при х=х* называют сильным, если имеет место q(x*)<q(x) для x≠x*. Если поменять знаки неравенств, получим слабый и сильный максимум. Однако max q(x) дает min q(x), поэтому в дальнейшем рассматриваем задачу минимизации. Сильный глобальный минимум всегда единственен. Слабый глобальный минимум допускает не единственность оптимальной точки, т.к. х, удовлетворяющий условию q(х)=q(х*), так же является оптимальной точкой.

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

Минимум в точке х=х* называется локальным (относительным), если найдется такая окрестность Q_ξ(х*) точки х*, что для всех х∈Q_ξ(x*) имеет место q(х*)≤q(х).

Если функция q(х) дифференцируема, то задача отыскания локальных минимумов сводится к нахождению стационарных точек, в которых обращаются в нуль частные производные функции q(x)

___

(15) dq(x)/dx_(i)=0, i=1,n

КЛАССИЧЕСКАЯ ЗАДАЧА ОПТИМИЗАЦИИ.

Эта задача состоит в нахождении минимума целевой функции q(х), где х=(х⁽¹⁾,..., х^(т)) - точка в пространстве R^(т) при наличии ограничений типа равенств:

___

(16) f_i(x)=0, i=1,m, m<n

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

Классический способ решения данной задачи состоит в том, что уравнение (16) используется для исключений из рассмотрения m - переменных. При этом целевая функция приводится к виду:

(17) q(x⁽¹⁾,...,x^(т))=q₁(y⁽¹⁾,..., y^(т)),

где через у⁽¹⁾,..., у^(т) обозначены не исключенные переменные. Задача состоит теперь в нахождении значений у⁽¹⁾,...,у^(т) которые обращают в минимум функцию q₁ и на которые не наложено ни каких ограничений, т.е. сводится к задаче на безусловный экстремум.

ВЫПУКЛЫЕ И ВОГНУТЫЕ ФУНКЦИИ.

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

Пусть f(х) - некоторая функция, заданная на выпуклом множестве Х, ах₁, x₂ - две произвольные точки из х, х=ℷх₁+(1-ℷ)х₂; 0≤1≤1; - произвольная точка отрезка, соединяющая х₁ и х₂. Рассмотрим также отрезок z=ℷf(х₁)+(1-ℷ)f(х₂), соединяющий значения f(х₁) и f(х₂) функции f(х).

 Функцию f(х) называют выпуклой, если она целиком лежит ниже отрезка, соединяющего две ее произвольные точки при любых х₁ и х₂ и при любом 0≤ℷ≤1 значении функции в точке х будут не больше значений z отрезка, соединяющего f(х₁) и f(х₂) Функцию называют вогнутой, если она целиком лежит выше отрезка соединяющего две ее произвольные точки.

ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Постановка задачи.

В этой задаче требуется найти значение многомерной переменной х=(х⁽¹⁾,..., х⁽ⁿ⁾), минимизирующее целевую функцию q(х) при условии, когда на переменную х наложены ограничения: ___

(20) f_i(x)≤0, i=1,n

а переменные х^(j), не отрицательны.

МЕТОД ШТАФНЫХ ФУНКЦИЙ.

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

(21) Q_k(x)=q(x)+r_kΨ(x), r=1,2,..

где Ψ(х)-функция штафа, принимающая по возможности малые (желательно нулевые) значения внутри допустимой области, а r_k, к=1,2,....... - плоскость возрастающих положительных чисел параметров штрафа. При ограничении вида (20), функция штрафа:

m

(22) Ψ(х)= ∑ (f_i+(x))²

i=1

где f_i+(х) - срезка функции f_i(x), равная нулю, если f_i(х)≤0 и равная f_i(х), если f_i(х)≥0.

Алгоритм решения задачи состоит в следующем:

а) выбираем произвольное начальное приближение х₀ и монотонно возрастающую последовательность чисел r→∞

б) при R=1,2,.., начиная с х_k-1 решаем задачу безусловной минимизации по х функции Q_k(х), в результате чего находим очередное приближение x_k к решению исходной задачи.

ОГРАНИЧЕНИЯ ТИПА РАВЕНСТВ И НЕОТРИЦАТЕЛЬНОСТЬ ПЕРЕМЕННЫХ.

Простейшей задачей НЛП является задача минимизации q(x) с ограничениями типа равенств

 ___

(24) f_j(x)=0, j=1,m ___

и с требованием не отрицательности переменных х⁽ⁱ⁾, i=1,n. В точки х оптимального решения выполняются соотношения:

(25) L(x,ℷ)=q(x)

Пусть х - точка, соответствующая оптимальному решению. Она может быть или внутренней, или граничной точкой допустимой области х≥0, т.е. каждая из ее компонент, будет удовлетворять либо условию х⁽ⁱ⁾>0, либо условию х⁽ⁱ⁾=0.

Если х⁽ⁱ⁾>0, то отклонения от точки х возможны как в сторону увеличения, так в сторону уменьшения х⁽ⁱ⁾. Но поскольку х - оптимальная точка, то должно быть dq(x)/dx⁽ⁱ⁾-0

Если х⁽ⁱ⁾ лежит на границе допустимой области, т.е. х⁽ⁱ⁾=0, то отклонения от оптимальной точки возможны в сторону увеличения dq(x)/dx⁽ⁱ⁾>0. Необходимые условия того, что точка х - решение задачи:

dL(x,ℷ) =0, если x⁽ⁱ⁾>0; ___

dx⁽ⁱ⁾ >0, если x⁽ⁱ⁾=0, i=1,n

____

(27) dL(x; ℷ)/dℷ_j=0,  j=1,m

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ (КП).

Задачей КП называют задачи НЛП, в которой минимизируется сумма линейной и квадратичной форм при ограничениях типа линейных неравенств и не отрицательности переменных. В матричной форме эта задача имеет вид:

(28) q(x)=Cx+x^Tdx=min,

Ax≤в,  x≥0

ИНТЕРАТИВНЫЕ МЕТОДЫ ПОИСКА ОПТИМУМА.

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

ГРАДИЕНТНЫЙ МЕТОД.

Этот метод представляет собой последовательность шагов, каждый из которых содержит две операции:

1)  определение направления антиградиента функции q(х)

2)  перемещение в выбранном направлении на заданное расстояние.

МЕТОД НАИСКОРЕИШЕГО СПУСКА (ПОДЪЕМА).

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

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

АЛГОРИТМ НЬЮТОНА.

В тех случаях, когда поверхность отклика достаточно хорошо описывается уравнением второго порядка, резкое уменьшение числа шагов можно получить, если воспользоваться алгоритмом Ньютона, при этом представлении q(х) в виде;

q(x)=q(x)*+½ ∑ ∑ ak_j Δx^(k) Δx^(j) ГДЕ X=X -X -отклонение

k j от точки оптимума.

Будет достаточным при значительном удалении от точки оптимума и в качестве матрицы Г_п можно взять непосредственно матрицу А.

Однако элементы, а_ij матрицы А, вычисленные в точке оптимума, заранее не известны. Тем не менее, при достаточно хорошей поверхности отклика вторые производные функции q(х) вычисленные в произвольной точке х=х_п будет близка к элементам a_ij матрицы А.

Похожие работы

Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем

Скачать

30399

31

10

... D=1- W3W4(W1W5W6+ W7+ W1W8+ W2W6 W7+ W2W7+2W2W8+ 1)+ W5W6(W3W4(W7+ W1W5W6+ W2W7+ W2W8+1)-1)   Для x1 Для x4 Для y Для х13 Задание 2. Синтез комбинационных схем. 2.1 Определение поставленной задачи Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n ...

Основы теории систем и системный анализ

Скачать

71710

1

1

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

Дифференциальные уравнения и описание непрерывных систем

Скачать

38497

0

12

... в момент t, образует пространство выхода системы. Множество всех значений, которые может принять вектор состояния x в момент t, образует пространство состояний системы. 3.3. Описание непрерывных систем с помощью системы дифференциальных уравнений В любой момент времени t состояние системы является функцией начального состояния x(t0) и вектора входа m(t0, t), то есть x(t)=F[x(t0); m(t0; t)], ...

Математические основы информатики

Скачать

41359

0

6

... Рассела и во многом базируется на работе Бертрана Рассела и Альфреда Уайтхэда «Principia Mathematica» (этот фундаметальный трёхтомник математической логики до сих пор не издан на русском языке)[8]. Заключение Прародителем информатики является кибернетика, основанная американским математиком Норбертом Винером, опубликовавшим в 1948 году одноименную книгу. Основоположником ...