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

При линейном преобразовании (21) случайного вектора Х корреляционная

матрица Y равна Кy=ВКxВT (22)

КОВАРЦИОННАЯ МАТРИЦА.

Если имеется не две, а большее число случайных величин, например,

х1,...,хn, то резко возрастает и число числовых параметров, характеризующих

эти величины. Кроме n-первых моментов, определяющих математическое ожидание

случайных величин необходимо определение еще вторых центральных моментов,

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

каждой парой случайных величин. Всю совокупность случайных величин Х1,...,

Хn, удобно представить в виде случайного вектора столбца:

X1 __ __

(23) X= ....... =(X1,...,Xn)T

Тогда совокупность математических ожиданий компонент этого вектора запишем

в виде вектора математических ожиданий:

x1 __ __

(24) X=M[X]= ...... =(x1,...,xn)T

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

(25) ?2xi=M[(xi-M[x])2] , i=1,...,n

и коварции

(26) cov(xixj)=M[(xi-M[xi])(xj-M[xj]) ,i, j=1,...,n, i?j

Удобно записать в виде коварционной матрицы:

(27) Pxx=M[(X-M(X))(X-M(X)T)]

Диагональные члены этой матрицы представляют собой дисперсии. Коварционная

матрица является симметричной.

ЭЛЕМЕНТЫ ТЕОРИИ СЛУЧАЙНЫХ ФУНКЦИЙ.

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

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

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

в данном опыте, невозможно, однако закономерности, присущие множеству

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

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

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

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

t, например времени.

Если параметр t- время, то случайную функцию называют случайным

процессом. Если зафиксировать элементарное событие ?=?0, то Х(t,?0) будет

неслучайной функцией аргумента t. Конкретный вид случайной функции при

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

функции.

Если зафиксировать параметр случайной функции t, т.е. рассмотреть

сечение этой случайной функции при t=tk, то она будет зависеть только от

элементарного события и, следовательно, станет случайной величиной Х(tk,?).

Чтобы полностью задать случайную функцию Х(t), надо знать все n-мерные

функции распределения: Fn(x1,...,xn; t1,..,tn), которые зависят от n

переменных х1,...,хn и значений t1,...,tn, или плотности распределения

вероятностей fn.

Важными характеристиками случайных величин являются моменты. Если

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

вероятностей случайной функции, то всегда можно вычислить моменты случайной

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

математически ожидания;

(1) M[X(t)]= ? xf1[x,t]dx=mx(t)

дисперсия

(2) D[X(t)]= ? [x-mx(t)]2f1(x,t)dx=D1(t)

и корреляционный момент:

? ?

(3) Kx(t1,t2)=M[X?(t1)X?(t2)]= ? ? (x1-mx(t1))(x2-mx(t2))

-? -?

f2(x1,x2;t1,t2)dx1dx2, где

(4) X?(t)=X(t)-M[X(t)], центрированная случайная функция.

Если параметру t придавать все возможные значения, то математическое

ожидание (1) и дисперсия (2) случайной функции будут функциями одной

переменной t, а корреляционный момент (3) функцией двух переменных t1 и t2.

Корреляционный момент Кx(t1,t2) называется корреляционной функцией

случайной функции Х(t).

Математическое ожидания представляет собой среднее значение случайной

функции Х(t)рис 2, а дисперсия характеризует отклонение значений,

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

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

величинами Х(t1) и Х(t2)-сечениями случайной функции при t=t1 и t=t2.

x(t)

m(x)

Рис 2

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

моментов случайных функций, рис 2 называется корреляционной теорией.

Если известны математическое ожидание m(t) и корреляционная функция

К(t1,t2) случайной функции Х(t), то всегда можно построить n-мерный вектор

математического ожидания многомерной, случайной величины x(t1),...,x(tn)

для фиксированных значений t1, t2,...,tn.

(5) mT=[m1, m2,..., mn]

и корреляционную матрицу этой случайной многомерной величины

K(t1,t1) K(t1,t2) ..... K(t1,tn)

K(t2,t1) k(t2,t2) ..... K(t2,tn)

(6) K= ........................................

........................................

K(tn,t1) K(tn,t2) K(tn,tn)

НЕКОТОРЫЕ СВОЙСТВА КОРРЕЛЯЦИОННОЙ ФУНКЦИИ.

1. Корреляционная функция при одинаковых значениях аргументов равна

дисперсии случайной функции, т.е.

K(t,t)=D(t)

2. При перемене местами аргументов корреляционная функция меняется на

комплексно - сопряженную, т.е.

______

K(t1; t2)=K(t1, t2)

3. Для всякой корреляционной функции справедливо неравенство:

1) K(t1, t2) ?? D(t1)D(t2)

4. Корреляционная функция является положительно определенной функцией.

Вместо корреляционной функции может быть рассмотрена безразмерная

нормированная корреляционная функция R(t1, t2) определяемая равенством;

(t1, t2)

5) R(t1, t2)=

? D(t1)D(t2)

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

нормированной корреляционной функции справедливо состояние:

_____ ______

R(t, t)=1 , R(t2,t1)=R(t1,t2) , R(t1,t2)?1

В теории случайных чисел большую роль играет один из видов случайной

функции, математическое ожидание которой равно 0, а корреляционная функция

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

белого шума как это следует из определения, справедливы равенства:

(6) M[X(t)=0

(7) K(t1, t2)=G(t) ?(t1-t2)

Функция G(t) называется интенсивностью белого шума. Дельта-функция при

значении аргумента, отличном от 0, равна 0, поэтому для белого шума

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

являются некоррелированными.

Рассмотри систему из n случайных функций:

(8) X1(t),X2(t),...,Xn(t)

Каждая из функций этой системы характеризуется математическим ожиданием и

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

между отдельными случайными функциями системы (8).

Такой характеристикой является взаимная корреляционная функция двух

случайных функций Xi(t) и Xi(t), и определяется равенством:

(9) Kxixj(t1,t2)=M[Xi?(t)Xj?(t)]

Для того, чтобы отличать взаимную корреляционную функцию, от

корреляционной функции, последнюю называют также автокорреляционной.

Для взаимной корреляционной функции случайных функций Хi(t) и Yj(t)

справедливы свойства:

________

(10) Kxy(t1, t2)=Kxy(t1, t2)

(11) Kxy(t1, t2) ? ?Dx(t1)Dy(t2)

Две случайные функции Х(t) и Y(t) называются некоррелированными, если их

взаимная корреляционная функция тождественно равна нулю т.е.

(12) Kxy(t1, t2)=0

В ряде случаев удобно ввести безразмерную характеристику связи между

случайными функциями нормированную взаимную корреляционную функцию:

Kxy(t1,t1)

(13) Rxy(t1, t2)=

? Dx(t1)Dy(t1)

ЛИНЕЙНЫЕ ОПЕРАЦИИ НАД СЛУЧАЙНЫМИ ФУНКЦИЯМИ.

Выясним, как образуются математические ожидания и корреляционные

функции случайных функций при осуществлении над ними линейных операций:

1. Сложение случайных функций.

Возьмем две случайные функции X(t), Y(t). Пусть известны моменты этих

функций до второго порядка включительно:

M[X(t)],M[Y(t)], Kx(t1,t2),Ky(t1,t2) Kxy(t1,t2)

Найдем математическое ожидание случайной функции:

(15) Z(t)=X(t)+Y(t)

В силу линейности операции определения математического ожидания имеем:

(16) M[Z(t)]=M[X(t)]+M[Y(t)]

т.е. математическое ожидание суммы случайных функций равно сумме

математических ожиданий этих случайных функций.

Вычитая из равенства (15) равенство (16), получим центрированную

случайную функцию:

(17) Z?(t)=X?(t)+Y?(t)

Вычислим корреляционную функцию суммы случайных функций Х(t)+Y(t). По

определению корреляционной функции имеем: _____

____________

(18) Kz(t1, t2)=M[Z?(t1)Z?(t2)]=M[(X?(t1)+Y?(t2)*(X?(t1)+Y?(t2))]=

=Kx(t1, t2)+Kxy(t1, t2)+Kyx(t1, t2)+Ky(t1, t2)

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

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

функций.

2. Дифференцирование случайных функций.

Случайная функция Y(t) называется производной в среднем квадратичном от

случайной функции Х(t) по аргументу t, если существует предел:

X?(t+h)-X?(t) 2

(19) lim M -Y?(t) =0

h>0 h

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

квадратичном, будем называть дифференцируемой. Случайная функция X(t)

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

(20) lim X(t)=X(t?)

h>0

Корреляционная функция производной dX?(t)/dt=Y?(t) равна:

d2K(t1,t2)

(21) Ky(t1,t2)=

dt1dt2

Взаимная корреляционная функция процесса Х?(t) и его производной равна:

(22) Kxy(t1,t2)=dK(t1,t2)/dt2

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

dn+mKx(t1,t2)

(23) Kx(n)x(m)(t1,t2)=

dt1n dt2n

где x(n)(t) и x(m)(t)- соответственно n-я и m-я производные в среднем

квадратичном случайной функции Х(t).

3. Интегрирование случайной функции.

Пусть заданы случайная функция Х(?) и неслучайная функция q(t, ?), где

параметр ? изменяется в интервале (а, в). Разобьем интервал (а, в) точками

??=а,??,...,?n=в, на n частей и составим сумму:

(24) S X?(?i) q(t,?i)(?i-?i-1)

i=1

значение ?i выбрано произвольно в промежутке?i-1????i. Рассмотрим предел в

среднем квадратическом суммы:

при n>? и max[?i-?i-1]>0

(25) lim S X?(?i) q(t, ?i)(?i-?i-1)

n>? i=1

Если этот предел существует, то он называется

интегралом от случайной функции X?(t) в среднем

квадратическом с весом q(t,?) и обозначается:

b n

(26) Y= ] X?(?) q(t,?) d? = lim S X?(?i) q(t,?i) ??i

a n>? i=1

Рассмотрим случайную функцию Y(t). Согласно определения интеграла от

случайной функции получим:

(27) Y(t)= ? X(?) q(t,?)d?

Математическое ожидание случайной функции Y(t):

(28) M[Y(t)]= ? mx(?) q(t,?) d?, где mx=M[X(t)]

Из неравенства (28) следует, что если существует интеграл, то

математическое ожидание интеграла от случайной функции Х(t) равно

интегралу от математического ожидания этой случайной функции.

СТАЦИОНАРНЫЕ СЛУЧАЙНЫЕ ФУНКЦИИ.

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

течением времени. Такие случайные функции называются стационарными.

Случайная функция, для которой все n-мерные функции распределения

вероятностей не изменяются с изменением начала отсчета времени, называются

стационарными в узком смысле.

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 состоит всего из одного

элемента U0, вероятность которого равна 1. В этом случае целевая функция

будет зависеть только от состояния ОУ.

(4) q=q(x)=q(x(1),...., x(n))

Одинаковую детерминированную задачу называют классической задачей

оптимизации, если ограничения вида:

?в ____

(5) fi(x(1),..., x(n)) =в , i=1,m

?в

примем, среди этих ограничений нет неравенств, и нет условий не

отрицательности или дискретности переменных, функции fi(x(1),...,x(n)) и

q(х) непрерывны и имеют частные производные по крайней мере второго

порядка.

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

математического программирования.

Математическое программирование представляет собой не аналитическую, а

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

процедуру, которая приводит к решению задачи.

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

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

ограничений (5) и целевая функция (4) представляют собой линейные функции

от х(1),..., х(n). В задачах линейного программирования требуется найти

неотрицательные значения переменных х(1),..., х(n), которые обращают в

минимум целую функцию.

(6) q(x(1),...,x(n))= S Cjx(j)

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

(7) S aijx(j)?вi, i=1,m

Любую задачу математического программирования, отличающуюся от

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

задачах или целевая функция или левые части ограничений, или то и другое

являются нелинейными функциями от x(1),..., х(n), или когда целевая функция

и ограничении имеют вид (6), (7), но предполагается, например, цело

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

программирования. Одношаговую задачу принятия решений называют

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

одного элемента, так что известным является не действительное состояние

природы U, а распределение вероятностей ?(U) на пространстве Q.

(8) q (x)= S ?(U) q(x,U)

U?Q

Поскольку q (х) является детерминированной функцией от х, то задача

нахождения переменных х(1),...,х(n), удовлетворяющих ограничениям (5) и

обращающих в минимум целевую функцию (8), может быть решена методами

линейного и нелинейного программирования.

В настоящее время большое внимание уделяется задачам, в которых

решение принимается не одним лицом, а несколькими, причем интересы этих лиц

противоположны. Подобные задачи получили название конфликтных ситуаций, а

методы их решения рассматриваются в теории игр. При мат-ком описании

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

приведение двух множеств Х*Y, где Х={х1,..., х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

до Т.

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

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

функционал

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

В динамических задачах управления наряду с ограничениями вида (5),

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

интегральными ограничениями вида:

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

Оптимальным называют управление u*(t), выбираемого из пространства

допустимых уравнений V, такое, которое для объекта описываемого

дифференциальным уравнением x=qv(u, x), x(0)=C, минимизирует критерий

качества (12) при заданных ограничениях на используемые ресурсы (13).

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

В общей задаче оптимизации требуется найти вектор x=(x(1),.., x(n)) из

допустимой области Х, который обращает в min целевую функцию q(х), т.е.

такой вектор х*?X, для которого выполняется условие:

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

Если такой вектор х* существует, то он определяет слабый глобальный минимум

q*(х) в допустимой области Х. Этот минимум называют слабым, т.к. он

удовлетворяет нестрогому (слабому) неравенству, глобальным или абсолютным,

потому что неравенство справедливо для любого х?X. Минимум при х=х*

называют сильным, если имеет место q(x*)?

б) при 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)*+Ѕ S S 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 R0 ={x; Ax=b, x?0}

x?R0

Задача (4)-невырожденная, т.е. невырожденна каждая угловая точка ?R0.

Итерационный шаг состоит в переходе от одной угловой точки х круговой

точке х', при котором значение целевой функции убывает; < x

-угловая точка. Базис В образует, первые m столбцов матрицы А. Будем

записывать матрицу А=[В,D], где В=[a1, a2,..., am].

D=[an+1, an+2,..., an]

xT=(xвТ, xдТ), CТ=(CвТ, CдТ)

хВ - базис компоненты, хд - в небазисные компоненты.

2) Выбор столбца для ввода в базис.

Известна угловая точка х: хв>0, хд=0, det(В)?0, Вхв=в

Рассмотрим векторы: хк=хк(?)= xв-?bak-1 ______

? k=(m+1,n)

где ? является к - й компонентой вектора х.

Если хв>0, то при малых ?>0; хk?0, т.к. Ахk=в, то хk?R? при малых ?>0.

Кроме того:

=-?[-Ck]=-??k

?к - определитель для любого к=1,n, причем при к=1,m;

?к=-Ck=Cк=Cк-Cк=0

Окончательно; =-??x (k=1,n)

3)Выбор столбца для ввода из базиса.

В зависимости от значков величины ?к и (В-1ak); возникает 3 случая.

___

a)Если для любого к=1,n будет ?к=0, то точка х - оптимальная.

_____

б) Если найдется номер к?m+1 такой, что ?к>0 и В-1ak?0, то

множество R0 неограниченно и функция неограниченна снизу на R0.

в) Пусть найдутся такие к?m+1 и i?m, что ?к>0 и (В-1akа )>0.

4)Конечность метода.

хk - новая угловая точка, причем =-?0 ?k < . Из этого

следует, что итерационный шаг симплексного метода состоит в таком переходе

от базиса а1, а2,..., аs, аs+1, am к базису a1, a2,..., as-1, as+1,..., am,

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

приводит к угловой точке х*, в которой достигает минимума за конечное число

итераций.

-----------------------

исполнительный орган

объект

управления

устройство управле-ния(отбор информа-ции и обработка

S определяется

ур-ми (1),(2)

квантование и запоминание

И.М.

САР

Страницы: 1, 2, 3, 4

МЕНЮ

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

ИНТЕРЕСНОЕ