Учебное пособие 800278

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

y(t) = Fs(x, v, h, t)

Совокупность зависимостей выходных характеристик системы от времени yj(t) для всех видов j=1, nj называется выходной траекторией y(t), а сама зависимость называется законом функционирования системы S и обозначается Fs. В общем случае, закон функционирования системы Fs может быть задан в виде функции, функционала, логических условий, в алгоритмической и табличной формах или в виде словесного правила соответствия.

Важным для описания и исследования системы S является понятие алгоритма функционирования Аs, под которым понимается метод получения выходных характеристик с учетом входных воздействий x(t), воздействий внешней среды v(t) и собственных параметров h(t). Очевидно, что один и тот же закон функционирования Fs системы S может быть реализован с помощью множества различных алгоритмов функционирования As .

Соотношения (1) являются математическим описанием поведения системы во времени t, то есть отражают динамические свойства системы.

Если рассматривать процесс функционирования системы S как последовательную смену состояний z1(t), z2(t),...,zk(t), то они могут быть интерпретированы как координаты точки в к-мерном пространстве, причем каждой реализации процесса будет соответствовать некоторая фазовая траектория. Совокупность всех возможных значений состояний {z} называется

пространством состояний объекта моделирования Z, zk Z.

В общем случае время в модели системы S может рассматриваться на интервале моделирования (0,Т) как непрерывное, так и дискретное, то есть квантованное на отрезки длиной T=m t, где m=1, mt – число интервалов дискретизации.

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

50

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

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

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

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

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

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

 Непрерывно-детерминированные (например, дифференциальные уравнения);

51

 Дискретно - детерминированные (конечные автома-

ты);

 Дискретно – стохастические (вероятностные авто-

маты);

Непрерывно – стохастические (системы массового обслуживания);

Обобщенный, или универсальный (агрегативные

системы).

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

ся через его входы =(x1,x2,...,xm) и выходы Y=(y1,y2,...,ym).

Через элемент подвергается внешним воздействиям, а через Y – сам воздействует на внешнюю среду (рис. 14).

Рис. 14

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

Поведение элемента будем рассматривать как последовательную смену его “внутреннего” состояния в некотором интервале времени. Такой динамический процесс, как правило, описывается системами дифференциальных уравнений.

В общем случае описание можно представить как ut’=f [u(t),x(t),t}, u(o)=uo; (2) y(t)=h [u(t),x(t),t]

u(t) – p-мерный вектор, компоненты которого описывают состояние элемента в момент времени t;

52

uo - начальное состояние элемента;

y(t) – n-мерный вектор выходов элемента; x(t) – m-мерный вектор входов элемента.

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

Y(t)=R(t)(x(t)),

где R(t)-символическое обозначение совокупности преобразований каждого входа в каждый выход (оператор преобразования).

В частном случае, при t=const (t ) Y=R(x)

Системный элемент, обладающий этими свойствами,

называется действующим элементом системы.

Пусть Е1 и Е2 – два действующих элемента с операторами R1 и R2 соответственно; 1=(x11,x12,...,x1m) и

2=(x21,x22,...,x2m) – их входные векторы; а Y1=(y11,y12,...,y1m)

и Y2=(y21,y22,...,y2m) – выходные векторы. Элемент Е1 воздействует на элемент Е2 только таким образом, что Е2 через свои входы “принимает” значения всех или нескольких выходов

Очевидно, что эти равенства должны быть выполнены хотя бы для одной пары значений (i, j), иначе не было бы воздействия элемента Е1 на Е2 .

Введем квадратную матрицу S21, состоящую из m2 или n1 строк и столбцов в зависимости от того m2 >= n1 или n1<= m2 . Элементы Sij матрицы определяются следующим образом:

0, при x2j = y1j.

Другими словами, элементы матрицы имеют значения 1, если соответствующая составляющая вектора входа y1 элемента E1 принимается в качестве составляющей вектора входа x1 элемента E2 , и 0, если этого не происходит. Матрица S21

53

имеет вид:

0 ... 0 ... 1 S21 = 1 ... 0 ... 0 0 ... 1 ... 0

S21 – нуль - единичная матрица, причем хотя бы один её элемент не является нулём. Матрица S21 называется матрицейсвязи элементов Е2 с элементом Е1 . С её помощью система равенств (4) записывается как

x2 = S21 y1.

Графически связь элементов Е2 с Е1 можно представить

(рис. 15).

Рис. 15

Матрицу связи элементов можно обобщить для любых элементов системы Еr и Еk независимо от того, связан Еk с Еr или нет. Если элемент Еk с Еr , то соответственно Skr=0 ( 0 – нулевая матрица, то есть все её элементы =0). С другой стороны, если Skr имеет все ненулевые элементы, то это означает, что каждая координата Xk со всеми координатами вектора Yr. В общем случае:

X k = Skr Y r

Обобщая получаем:

X *= R S(X); Y*=S R(Y), (5)

где X, Y - состояние входов и выходов системы до преобразования;

X*, Y* - новое состояние входов и выходов после преобразования;

R – матрица операторов преобразования отдельных элементов;

S – матрица связей между элементами.

Таким образом, приведенные соотношения позволяют

54

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

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

1.По отношению системы к окружающей среде:

o открытые (есть обмен с окружающей средой ресурсами);

o закрытые (нет обмена ресурсами с окружающей средой).

2. По происхождению системы (элементов, связей,

подсистем):

o искусственные (орудия, механизмы, машины, автоматы, роботы и т.д.);

o естественные (живые, неживые, экологические, социальные и т.д.);

o виртуальные (воображаемые и, хотя они в действительности реально не существующие, но функционирующие так же, как и в случае, если бы они реально существовали);

o смешанные (экономические, биотехнические, организационные и т.д.).

3.По описанию переменных системы:

o с качественными переменными (имеющие только лишь содержательное описание);

o с количественными переменными (имеющие дискретно или непрерывно описываемые количественным образом переменные);

o смешанного (количественно - качественное) описания. 4. По типу описания закона (законов) функционирова-

ния системы:

o типа “Черный ящик” (неизвестен полностью закон функционирования системы; известны только входные и выходные сообщения системы);

55

o не параметризованные (закон не описан, описываем с помощью хотя бы неизвестных параметров, известны лишь некоторые априорные свойства закона);

o параметризованные (закон известен с точностью до параметров и его возможно отнести к некоторому классу зависимостей);

o типа “Белый (прозрачный) ящик” (полностью известен закон).

5.По способу управления системой (в системе):

o управляемые извне системы (без обратной связи, регу-

лируемые, управляемые структурно, информационно или функционально);

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

o с комбинированным управлением (автоматические, по-

луавтоматические, автоматизированные, организационные). Под регулированием понимается коррекция управляю-

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

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

56

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

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

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

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

Сложные системы бывают:

сложности структурной или статической (не хва-

тает ресурсов для построения, описания, управления структурой);

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

информационной или информационно - логической,

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

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

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

57

ния системы);

развития или эволюции, самоорганизации (не хватает ресурсов для устойчивого развития, самоорганизации).

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

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

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

Уменьшив сложность системы можно часто увеличить её информативность, исследуемость.

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

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

58

ЛЕКЦИЯ 5 ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ

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

Задача линейного программирования (ЗЛП) заключается в определении максимального или минимального значения линейной функции при линейных ограничениях. В общем виде ЗЛП может быть записана следующим образом [3]:

n

F cj xj max (min);

j 1

n

aij xj ( , )bi ,i 1,m;

j 1

xk 0,k 1,s,s n.

Стандартной (или симметричной) ЗЛП называется cледующая задача:

n

F cj xj max (min);

xj 0, j 1,n.

Для разработки вычислительных методов в качестве стандарта принята каноническая форма записи ЗЛП:

n

F cj xj min;

j 1

n

aij xj bi ,i 1,m;

j 1

xj 0, j 1,n.

Каноническая форма ЗЛП характеризуется следующими условиями:

1. Целевая функция подлежит минимизации.

59