Математические основы теории систем (стр. 12 из 13)
Минимум в точке х=х* называется локальным (относительным), если найдется такая окрестность Qξ(х*) точки х*, что для всех х∈Qξ(x*) имеет место q(х*)≤q(х).
Если функция q(х) дифференцируема, то задача отыскания локальных минимумов сводится к нахождению стационарных точек, в которых обращаются в нуль частные производные функции q(x)
___
(15) dq(x)/dx(i)=0, i=1,n
КЛАССИЧЕСКАЯ ЗАДАЧА ОПТИМИЗАЦИИ.
Эта задача состоит в нахождении минимума целевой функции q(х), где х=(х(1),..., х(т)) - точка в пространстве R(т) при наличии ограничений типа равенств:
___
(16) fi(x)=0, i=1,m, m<n
Если ограничения (16) имеют место ,то минимум функции q(х) называют условным минимумом. Если ограничения (16) отсутствуют, то говорят о безусловном минимуме, нахождение которого сводится к определению и исследованию стационарных точек функции q(х).
Классический способ решения данной задачи состоит в том, что уравнение (16) используется для исключений из рассмотрения m - переменных. При этом целевая функция приводится к виду:
(17) q(x(1),...,x(т))=q1(y(1),..., y(т)),
где через у(1),..., у(т) обозначены не исключенные переменные. Задача состоит теперь в нахождении значений у(1),...,у(т) которые обращают в минимум функцию q1 и на которые не наложено ни каких ограничений, т.е. сводится к задаче на безусловный экстремум.
ВЫПУКЛЫЕ И ВОГНУТЫЕ ФУНКЦИИ.
Большинство известных методов решения задачи оптимизации сводится к исследованию характера функции q(х) в окрестности рассматриваемого значения x, т.е. к выяснению того, не является ли точка х точкой относительного минимума (максимума). При этом задача усложняется, если целевая функция может иметь в допустимой области значений Х не один, а несколько минимумов или максимумов. Поэтому значительный интерес представляют также задачи, в которых целевая функция имеет всего один максимум или минимум. Для выявления классов таких задач фундаментальную роль играют понятия выпуклости и вогнутости функций.
Пусть f(х) - некоторая функция, заданная на выпуклом множестве Х, ах1, x2 - две произвольные точки из х, х=ℷх1+(1-ℷ)х2; 0≤1≤1; - произвольная точка отрезка, соединяющая х1 и х2. Рассмотрим также отрезок z=ℷf(х1)+(1-ℷ)f(х2), соединяющий значения f(х1) и f(х2) функции f(х).
Функцию f(х) называют выпуклой, если она целиком лежит ниже отрезка, соединяющего две ее произвольные точки при любых х1 и х2 и при любом 0≤ℷ≤1 значении функции в точке х будут не больше значений z отрезка, соединяющего f(х1) и f(х2) Функцию называют вогнутой, если она целиком лежит выше отрезка соединяющего две ее произвольные точки.
ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Постановка задачи.
В этой задаче требуется найти значение многомерной переменной х=(х(1),..., х(n)), минимизирующее целевую функцию q(х) при условии, когда на переменную х наложены ограничения: ___
(20) fi(x)≤0, i=1,n
а переменные х(j), не отрицательны.
МЕТОД ШТАФНЫХ ФУНКЦИЙ.
Задача минимизации целевой функции q(х) с ограничениями (20) может, быть сведена к задаче на безусловный экстремум видоизменением целевой функции путем добавления к ней функции штафа. Общая идея метода штафных функций состоит в построении последовательности новых целевых функций.
(21) Qk(x)=q(x)+rkΨ(x), r=1,2,..
где Ψ(х)-функция штафа, принимающая по возможности малые (желательно нулевые) значения внутри допустимой области, а rk, к=1,2,....... - плоскость возрастающих положительных чисел параметров штрафа. При ограничении вида (20), функция штрафа:
m
(22) Ψ(х)= ∑ (fi+(x))2
i=1
где fi+(х) - срезка функции fi(x), равная нулю, если fi(х)≤0 и равная fi(х), если fi(х)≥0.
Алгоритм решения задачи состоит в следующем:
а) выбираем произвольное начальное приближение х0 и монотонно возрастающую последовательность чисел r→∞
б) при R=1,2,.., начиная с хk-1 решаем задачу безусловной минимизации по х функции Qk(х), в результате чего находим очередное приближение xk к решению исходной задачи.
ОГРАНИЧЕНИЯ ТИПА РАВЕНСТВ И НЕОТРИЦАТЕЛЬНОСТЬ ПЕРЕМЕННЫХ.
Простейшей задачей НЛП является задача минимизации q(x) с ограничениями типа равенств
___
(24) fj(x)=0, j=1,m ___
и с требованием не отрицательности переменных х(i), i=1,n. В точки х оптимального решения выполняются соотношения:
(25) L(x,ℷ)=q(x)
Пусть х - точка, соответствующая оптимальному решению. Она может быть или внутренней, или граничной точкой допустимой области х≥0, т.е. каждая из ее компонент, будет удовлетворять либо условию х(i)>0, либо условию х(i)=0.
Если х(i)>0, то отклонения от точки х возможны как в сторону увеличения, так в сторону уменьшения х(i). Но поскольку х - оптимальная точка, то должно быть dq(x)/dx(i)-0
Если х(i) лежит на границе допустимой области, т.е. х(i)=0, то отклонения от оптимальной точки возможны в сторону увеличения dq(x)/dx(i)>0. Необходимые условия того, что точка х - решение задачи:
dL(x,ℷ) =0, если x(i)>0; ___dx(i) >0, если x(i)=0, i=1,n
____
(27) dL(x; ℷ)/dℷj=0, j=1,m
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ (КП).
Задачей КП называют задачи НЛП, в которой минимизируется сумма линейной и квадратичной форм при ограничениях типа линейных неравенств и не отрицательности переменных. В матричной форме эта задача имеет вид:
(28) q(x)=Cx+xTdx=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)*+½ ∑ ∑ akj Δx(k) Δx(j) ГДЕ X=X -X -отклонение
k j от точки оптимума.
Будет достаточным при значительном удалении от точки оптимума и в качестве матрицы Гп можно взять непосредственно матрицу А.
Однако элементы, аij матрицы А, вычисленные в точке оптимума, заранее не известны. Тем не менее, при достаточно хорошей поверхности отклика вторые производные функции q(х) вычисленные в произвольной точке х=хп будет близка к элементам aij матрицы А.
1.11. ЗАДАЧИ И МЕТОДЫ ЛИНЕЙНОГО ПРГРАММИРОВАНИЯ.
Дана система m линейно независимых уравнений с неизвестными х ,...,х называемая системой ограничений задачи линейного программирования:
a11x1+...+a1nxn=в1 (1) ............................
am1x1+...+a1mxn=вn ___
где не уменьшая общности можно считать вi≥0, i=1,m.
Характерной особенностью данной задачи является, то, что число уравнений меньше числа неизвестных, т.е. m<n. Требуется найти неотрицательные значения переменных, которые удовлетворяют уравнениям (1) и обращают в минимум целевую функцию:
(2) q=c1x+...+anx
Более компактно задачи ЛП могут быть записаны в матричной форме:q(x)=cx=min
(3) Ax=B (B≥0), x≥0
где А - матрица размером m*n, В m - мерный вектор, х и c n - мерные вектора. Матрицу А называют матрицей условий задачи векторов В - вектор ограничений задачи (3).
ГЕОМЕТРИЧЕСКА ИНТЕРПРИТАЦИЯ ОСНОВНОЙ ЗАДАЧИ ПРОГРОММИРОВАНИЯ.
В пространстве Еn множество R1 можно рассматривать как пересечение полупространств (при n=2 - полуплоскостей). ___
(Ax)i≥bi, ( i=1,m)
x≥0 (j=1,n)
СИМПЛЕКС МЕТОД.
1) Идея метода.
Этот метод - это последовательный перебор угловых точек, при которых значение целевой функции убывает от одной угловой точки к другой.
Рассмотрим задачи (каноническую) ЛП:
(4) min<c, x> R0 ={x; Ax=b, x≥0}
x∈R0
Задача (4)-невырожденная, т.е. невырожденна каждая угловая точка ∈R0. Итерационный шаг состоит в переходе от одной угловой точки х круговой точке х', при котором значение целевой функции убывает; <C, x'> < <C, x> x -угловая точка. Базис В образует, первые m столбцов матрицы А. Будем записывать матрицу А=[В,D], где В=[a1, a2,..., am].
D=[an+1, an+2,..., an]
xT=(xвТ, xдТ), CТ=(CвТ, CдТ)
хВ - базис компоненты, хд - в небазисные компоненты.
2) Выбор столбца для ввода в базис.
Известна угловая точка х: хв>0, хд=0, det(В)≠0, Вхв=в