close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Андрей Федорович
Шориков
Доктор
физико-математических
наук,
профессор, зав. кафедрой информационных
систем
в
экономике
Уральского
государственного
экономического
университета
Владимир Александрович
Тюлюкин
Кандидат
физико-математических
наук,
доцент кафедры информационных систем в
экономике Уральского государственного
экономического университета
ОПИСАНИЕ БИБЛИОТЕКИ
КОМПЬЮТЕРНЫХ ПОДПРОГРАММ
ДЛЯ МОДЕЛИРОВАНИЯ РЕШЕНИЯ ЗАДАЧИ
АПОСТЕРИОРНОГО МИНИМАКСНОГО ОЦЕНИВАНИЯ
Экономико-математические методы находят все более широкое применение в решении
задач количественного анализа и компьютерном моделировании процессов, реализующихся в
различных экономических структурах. При этом если в начальный период исследований
разрабатывались и использовались статические оптимизационные модели, то в настоящее время
для решения задач оценивания параметров систем и прогнозирования изменения их во времени
используются динамические модели. В данной работе описывается программное обеспечение для
персонального компьютера, которое позволяет осуществлять как экономико-математическое
моделирование, так и моделирование технических объектов с учетом наличия динамики
реализуемых процессов и неполноты информации о параметрах рассматриваемых систем. (Работа
поддержана грантом РФФИ, проект 97-01-00161.)
Авторами представлено описание библиотеки подпрограмм на языке Pascal, позволяющих
моделировать на компьютере решение задачи апостериорной минимаксной обработки данных
измерений [1-5] в динамической системе, состоящей из двух управляемых объектов.
Предполагается, что динамика наблюдаемого объекта описывается векторным линейным
дискретным уравнением, а объекта, с которого ведется наблюдение, – векторным нелинейным
дискретным уравнением. Действие измерителя сигнала моделируется соотношением, которое
линейно зависит от фазового состояния наблюдаемого объекта и, через матрицу преобразования,
от фазового состояния другого объекта, управляемого наблюдателем. При этом в рассматриваемой
системе не требуется наличия памяти о реализациях измеряемых по ходу процесса параметров.
Предполагается также, что известны множества, ограничивающие изменение всех априори
неопределенных параметров системы, имеющие вид выпуклых, замкнутых и ограниченных
многогранников (с конечным числом вершин) в соответствующих евклидовых пространствах. При
предположениях, сделанных в соответствии с результатами работ [1, 2, 5], в статье [3]
формулируется задача апостериорного минимаксного оценивания фазовых состояний
наблюдаемого объекта в форме нелинейного фильтра. Для ее решения в работах [3, 4] предложен
численный рекуррентный алгоритм, который исходную многошаговую задачу сводит к решению
последовательности одношаговых оптимизационных задач линейного и выпуклого
математического программирования. Этот алгоритм использует также результаты работ [6-11].
В данной статье описание алгоритма реализовано в виде комплекса стандартных
подпрограмм для персонального компьютера IBM PC/AT на алгоритмическом языке Pascal.
Отметим, что ограничениями на размерность рассматриваемой динамической системы и число
шагов процесса оценивания для моделируемого алгоритма являются только ограничения на
ресурсы памяти и быстродействие компьютера. Представленный программный комплекс может
быть использован при разработке моделирующих систем автоматического управления
подвижными объектами и при решении задач экономико-математического моделирования.
Математические модели таких систем рассмотрены, например, в работах [1-7].
Статья состоит из трех разделов: в первом приводится краткая инструкция по
использованию библиотеки подпрограмм, во втором – функциональные описания подпрограмм и
в третьем – краткое описание структуры и использования головной программы.
1. Инструкция по использованию библиотеки подпрограмм
Данная библиотека подпрограмм состоит из модуля BTULSHOR. В модуле BTULSHOR
описываются типы массивов, используемых библиотекой подпрограмм. Эти описания доступны
основной программе FILTR (краткое описание представлено в разд. 3), поскольку они
расположены в интерфейсной секции модуля. Массивы, описанные в основной программе,
должны соответствовать типу массивов, входящих в задействованные подпрограммы. В
некоторых подпрограммах создаются массивы, использующие динамическую память, длина
которой зависит от памяти ОЗУ вашего ПК. Не забывайте выделять место для динамической
памяти!
Для использования данной библиотеки подпрограмм в основной программе FILTR после
строки PROGRAM . . . ; должна присутствовать строка USES BTULSHOR;. Заметим, что модуль
BTULSHOR должен быть расположен в каталоге, соответствующем настройке вашего TurboPascal .
В заключение отметим, что все массивы, используемые в подпрограммах, являются
одномерными. Запись «А - матрица A(k)» следует понимать так: в одномерном массиве А сначала
расположен первый столбец матрицы A(k), затем – второй и т.д.
2. Описание библиотеки подпрограмм
1. Подпрограмма REACH: «Построение множества всех вершин области достижимости
для линейных дискретных систем».
Математическое описание. Для линейной дискретной системы вида
x ( t  1)  A ( t )x( t )  B( t )u( t)
(1)
при заданных ограничениях
x(t )  X(t ), u( t )  P( t ),
(2)
где момент времени t  N; фазовый вектор x  R n ; управляющее воздействие u  R p ( n, p  N );
k
N – множество всех натуральных чисел; для k  N , R – k-мерное евклидово пространство,
элементы которого будем представлять в виде векторов-столбцов, даже если из экономии места
они записаны в строку; A(t) и B(t) – известные действительные матрицы размера (n  n) и
(n  p) соответственно; X(t) и P(t) – выпуклые, замкнутые и ограниченные многогранники (с
n
p
конечным числом вершин) из R и R соответственно. Множество всех вершин области
n
достижимости [1] G( t,X ( t ),t  1) , отвечающей паре ( t , X( t ))  N  2 R , на момент времени t  1
строится согласно следующему обобщенному алгоритму.
Алгоритм 1
Шаг 1. Сформировать множество Г n ( X ( t )) всех вершин многогранника X(t).
Шаг 2. Сформировать множество Г p ( P( t )) всех вершин многогранника P(t).
Шаг 3. Сформировать следующие множества:
 ( t  1)  {x ( t  1): x ( t  1)  R n , x ( t  1)  A ( t)x( t),
X
x ( t )  Г n ( X ( t ))},
 ( t  1)  {y ( t  1): y ( t  1)  R n , y ( t  1)  B ( t)u( t),
Y
u( t )  Г p ( P( t ))},
~
G( t  1)  {~
x ( t  1): ~
x ( t  1)  R n , ~
x ( t  1)  x ( t  1)  y ( t  1),




x(t  1)  X(t  1), y( t  1)  Y(t  1)}.
Шаг 4. Для сформированного дискретного множества точек
~
G( t  1)  {~
x ( i ) ( t  1)} i1,m  G( t, X( t), t  1) (m  N)
определить все его крайние вершины, которые находятся с помощью подпрограммы (п/п)
КРАВЕР. Эти крайние вершины и будут множеством всех вершин области достижимости
G( t,X ( t ),t  1) на момент времени t  1 , являющейся выпуклым, замкнутым и ограниченным
n
многогранником (с конечным числом вершин) из R .
Конец алгоритма 1.
Использование:
REACH (n, nr, nx, np, А, В, ВЕХ, ВЕР, nxp, BERG) ;
Входные параметры:
n – размерность фазового пространства (тип: integer);
nr – размерность пространства управлений (тип: integer);
nx – число всех вершин многогранника X(t) (тип: integer);
np – число всех вершин многогранника P(t) (тип: integer);
А – матрица A(t) (тип: array [1..n  n] of real; type: t1);
В – матрица B(t) (тип: array [1..n  nr ] of real; type: t2);
ВЕХ – массив, содержащий координаты всех вершин многогранника X(t) (тип: array
[1..n  nx] of real; type: t7);
ВЕР – массив, содержащий координаты всех вершин многогранника P(t) (тип: array
[1..n  np] of real; type: t6).
Выходные параметры:
nxp – число всех вершин области достижимости (тип: integer);
BERG – массив, содержащий координаты всех вершин области достижимости (тип: array
[1..n  nx  nr  np  3  nx  nr  np] of real; type: t7).
Замечания по использованию:
1) строит область достижимости на один шаг вперед;
2) в п/п создается рабочий массив: Х (тип: array [1. .n] of real; type: t8);
3) используется п/п КРАВЕР.
2. Подпрограмма КРАВЕР: «Поиск множества всех вершин выпуклого, замкнутого и
ограниченного многогранника по его дискретному подмножеству».
Математическое описание. Пусть x (1) ,x ( 2 ) ,  x ( m ) (m  N ) есть дискретное множество точек
~
G,
являющееся подмножеством некоторого выпуклого, замкнутого и ограниченного
n
многогранника (с конечным числом вершин) G из R , содержащее все его вершины. Тогда поиск
~
множества всех вершин многогранника G по заданному дискретному множеству G сводится к
решению следующей задачи математического программирования.
Задача 1. Для фиксированного i  1, m и набора переменных  j  R 1 , j  1, m, j  i
требуется определить совместность следующей системы линейных соотношений:
  j x ( j)  x ( i ) ,
 j

  j  1,  j  0.
 j
(3)
Решение этой задачи находится с помощью модифицированного симплекс-метода (см.,
например, [10, 11]), который применяется для задачи линейного программирования с
ограничениями (3) и поиска минимума целевой функции g: R m  R 1 достаточно произвольного
вида, например
g()    j ,
j
где j  1, m, j  i .
Отметим, что такой выбор целевой функции значительно упрощает процесс проверки
условий совместности ограничений (3), происходящий на первом этапе реализации
модифицированного симплекс-метода. При этом из свойств системы (3) следует, что если она
~
x ( i ) не является вершиной многогранника co n G – выпуклой оболочки
~
~
множества G . В противном случае имеем x ( i )  Г n ( co n G ) .
совместна, то точка
Тогда, решив задачу 1 для всех значений параметра i 1, m , найдем все вершины
~
многогранника Г n ( co n G) и, следовательно, все вершины многогранника G, так как имеет место
~
равенство Г n (G )  Г n (co n G ) .
Использование:
КРАВЕР (n,m,l,А); .
Входные параметры:
n – размерность фазового пространства (тип: integer);
~
m – число всех точек множества G (тип: integer);
~
А – массив, содержащий координаты всех точек множества G (тип: array [1.. n  m  3  m ]
of real; type: t7).
Выходные параметры:
l – число всех вершин многогранника G (тип: integer);
А – массив, содержащий координаты всех вершин многогранника G.
Замечания по использованию:
1) в п/п создаются рабочие массивы: Х (тип: array [1. . n+3] of real; type: t12), NВ (тип: array
[1. . n+3] of integer; type: t13), К (тип: array [1. . n] of integer; type: t5);
2) используется п/п MODIF.
3.
Подпрограмма MODIF:
«Решение задачи
линейного программирования
модифицированным симплекс-методом».
Математическое описание.
Задача 2. Требуется решить задачу линейного программирования
с , x 
 min (max)
при условиях Ax  b, x  0 ,
где A – матрица размерности m  n (m, n  N); x  R n ; c  R n ; b  R m .
Для решения этой задачи используется модифицированный симплекс-метод. Исходная
информация задается в виде расширенной матрицы
 a11 a12

 
A1   a m1 a m 2

c2
 c1

 a l1 a l 2
 a1n 

 
 a mn  ,

 cn 

 aln 
где l  m  2, a ij (i  1, m, j  1, n ) – элементы матрицы A, a lj   (a1 j a 2 j    a mj ) для j  1, n ;
вектор b дополняется двумя компонентами b m1  0 и b1  (b1  b 2    b m ) .
Точность вычислений характеризуется величиной невязки вида
r  b1  (a l1x 1  a l 2 x 2    a l n x n ).
Использование:
MODIF (A, l, n, eps, p, X, NB) ; .
Входные параметры:
A – матрица A1 (тип: array [1 ....l  n] of real; tуpe: t7);
l – число строк матрицы A1 (тип: integer);
n – число столбцов матрицы A1 (тип: integer);
eps – заданная абсолютная погрешность вычислений (тип: real);
p – числовой параметр такой, что p = 1, если требуется найти максимум, и (p  1)  (p  1) ,
если требуется найти минимум целевой функции (тип: integer);
Х – вектор b (тип: array [1.. l] of real; type: t12).
Выходные параметры:
p – числовой параметр такой, что p  1 , если найдено решение; p  2 , если система
ограничений несовместна; p  3 , если значение целевой функции неограниченно;
Х – в X( i ),i 1, l  2 находятся ненулевые координаты вектора-решения; в X ( l  1) –
минимальное (максимальное) значение целевой функции; в X (l ) – значение величины невязки;
NB – массив, содержащий номера ненулевых координат вектора-решения (тип: array [1. .l] of
integer; type: t13).
Замечания по использованию:
1) задача должна быть приведена к виду, в котором координаты вектора b неотрицательны;
2) в п/п создаются рабочие массивы, использующие динамическую память: U (тип: аrrау [1..
l  2 ] of real; type: t11), ХK (тип: аrrау [1. .l] of real; type: t12); в конце выполнения п/п указанные
динамические переменные уничтожаются.
4. Подпрограмма GIPBER: «Нахождение вершин выпуклого, замкнутого и ограниченного
многогранника, заданного системой неравенств».
Математическое описание. Пусть задана система неравенств вида
a j1x 1  a jn x n  a j,n 1  0, j  1, m (m, n  N) ,
где a ji  R 1 (i  1, n  1) – i-я координата нормального вектора j-й крайней опорной гиперплоскости;
x i  R l – набор действительных переменных, которые определяют выпуклый, замкнутый и
n
ограниченный многогранник (с конечным числом вершин) G из R . Требуется найти множество
Г n (G ) всех вершин многогранника G.
Для решения этой задачи используется следующая обобщенная схема.
Сформируем систему уравнений
 a j1x 1    a jn x n  a j, n1x n 1   u j ,

 x n 1   u m 1 ,


j  1, m,
где u i  R 1 ( i  1, m  1) – неотрицательные числовые параметры. Тогда, применив к этой системе
алгоритм Гаусса для исключения неизвестных, получим
x j  s j1u1    s j, m1u m 1 , j  1, n  1;
(4)
ri1u1    ri ,m 1u m 1  0, i  n  2, m  1,
(5)
где s jk  R 1 (k  1, m  1) и ril  R 1 ( l 1, m  1) есть фиксированные числовые параметры.
Применив к (5) вычислительную схему Н.В. Черниковой [9], получим
u j  q j1p1  q jk p k , j  1, m  1,
(6)
где p i  R l ( i  1, k ) – произвольные неотрицательные числа; q ji  R 1 - фиксированные числовые
параметры.
Подставив выражения из (6) в (4), получим
x j  b j1p1  b jk p k , j  1, n  1,
где b ji  R 1 ( i  1, k ) есть фиксированные числовые параметры. Тогда для b n 1,i  0 выражение
b ji b n1,i является значением j-й координаты i-й вершины многогранника G, т.е. таким образом
определяется все искомое множество Г n (G ) .
Использование:
GIPBER (A, n, m, im, C1);.
Входные параметры:
А – массив координат нормальных векторов и свободных членов, определяющих систему
неравенств, описывающую многогранник G (тип: array [ 1..m  (n  m) ] of real; type: t7);
n – размерность фазового пространства + 1 (тип: integer);
m – число исходных неравенств + 1 (тип: integer).
Выходные параметры:
im – число всех вершин многогранника G (тип: integer);
С1 – массив, содержащий координаты всех вершин многогранника G (тип: array [ 1..n  im ]
of real; type: t7).
Замечания по использованию:
1) данная п/п работает при условии m  n; в противном случае необходимо продублировать
одно из неравенств до выполнения этого условия;
2) в п/п создаются рабочие массивы, использующие динамическую память: B (type: t10), C
(type: t10); размеры массивов В и С рекомендуется задавать максимально возможными; в конце
выполнения п/п указанные переменные уничтожаются;
3) используются п/п TABLEX и MATRB;
4) в п/п MATRB создается массив IR (тип: аrrау [ 1..m ] of integer;
type: t9).
5. Подпрограмма CRAPOV: «Нахождение крайних опорных гиперплоскостей выпуклого,
замкнутого и ограниченного многогранника по его заданным вершинам».
Математическое описание. Пусть Z есть выпуклый, замкнутый и ограниченный
n
многогранник (с конечным числом вершин) из R . Тогда, зная Г n ( Z)  {z ( i ) }i1, m – множество
всех вершин многогранника Z, требуется найти множество всех его крайних опорных
гиперплоскостей (m  N ) .
Для решения этой задачи применяется следующий обобщенный алгоритм.
Алгоритм 2
Шаг 1. Сформировать систему линейных уравнений
z 1i z1  z 2i z 2  z ni z n  z n 1  p i , i 1, m (m, n  N ),
(7)
где z ji – j-я координата ( j 1, n) i-й вершины многогранника
многогранника; p i – неотрицательные числовые параметры;
Z; m – число вершин этого
z k – действительные переменные
(k  1, n  1) .
Шаг 2. Преобразовать систему уравнений (7), применив алгоритм Гаусса для исключения
неизвестных, к виду
z i  1i p1   2i p 2   r i p r   r 1,i z r 1   n 1,i z n 1 , i  1, r;
1j p1   2 j p 2   mj p m  0, j  r  1, m,
где r  N и является рангом системы (7).
(8)
(9)
Шаг 3. Преобразовать систему (9), применив вычислительную схему Н.В.Черниковой [9], к
виду
p j  1j  1   2 j  2   kj  k , j  1, m,
(10)
где  i , i  1, k – произвольные неотрицательные числа (k  N ) .
Шаг 4. Подставить (10) в (8), тогда получим
z i  1i  1   2 i  2   ki  k   r 1,i z r 1   n 1,i z n 1 , i  1, r.
Отсюда крайние опорные гиперплоскости многогранника Z определяются соотношениями
~
 i , ~z  0,
 ~
  z  0,
~
где i  1, k ;  i  (  i1 ,  i 2 ,  ,  ir , 0
,0
,
,0)  R n 1 ;



( n  1 r )
~z  ( z , z ,  z ,1)  R n 1 ,
1
2
n
  r 1,1


   r 1,1
  r  2,1
   

r  2,1
 

  n 1,1

   n 1,1
 r 1, 2

 r 1, r
0
0 


 1 00 
0
10 

0  10  .

 

0
01 

0 0 1
1
( n 1 r )
  r 1, 2
 r  2,2
  r  2, 2

 n 1, 2
  n 1, 2
   r 1,r

 r  2 ,r
   r  2, r



 n 1,r
   n 1, r
Конец алгоритма 2.
Использование:
CRAPOV (A, n, m, mj, mi, C1); .
Входные параметры:
A – массив, содержащий координаты всех вершин заданного многогранника Z (тип: аrrау [
1..m  (n  m) ] of real; type: t7);
{Структура массива А: сначала расположены первые координаты m вершин многогранника
Z, а затем - вторые и т. д.};
n – размерность фазового пространства + 1 (тип: integer);
m – число всех вершин заданного многогранника Z (тип: integer);
mj – число крайних опорных гиперплоскостей других множеств, находящихся в массиве С1
(тип: integer).
Выходные параметры:
mi – число всех крайних опорных гиперплоскостей многогранника Z (тип: integer);
C1 – массив, содержащий координаты нормальных векторов и свободных членов,
определяющих все крайние опорные гиперплоскости многогранника Z (тип: array [1..n  mi ] of
real; type: t7).
Замечания по использованию:
1) данная п/п работает без условия телесности заданного многогранника Z;
2) в п/п создаются рабочие массивы, использующие динамическую память: B (type: t l0), C
(type: tl0); размеры массивов В и С рекомендуется задавать максимально возможными; в конце
выполнения п/п указанные переменные уничтожаются;
3) в п/п создаются рабочие массивы: IK, IМ (тип: аrrау [1..n] of integer; type: t4);
4) используются п/п TABLEX и MATRB;
5) в п/п MATRB создается массив IR (тип: аrrау [1..m] of integer;
type: t9).
6. Подпрограмма CHEBR: «Нахождение чебышевского центра и значения величины
чебышевского радиуса выпуклого, замкнутого и ограниченного многогранника».
Математическое описание. Пусть для заданного выпуклого, замкнутого и ограниченного
n
многогранника (с конечным числом вершин) Z из R известно дискретное множество
Г n ( Z)  {z ( i ) }i1,m всех его вершин. Требуется найти чебышевский центр и значение величины
чебышевского радиуса [2,5] многогранника Z.
Решение этой задачи осуществляется с помощью следующей обобщенной схемы.
(i)
1. На основе множества Г n ( Z)  {z }i1,m всех вершин многогранника Z формируются
функционалы
i: R n 
 R 1 ,
значения которых для z  ( z 1 ,z 2 ,,z n )   R n определяются по формулам
 i ( z )  z  z ( i ) (i 1, m) ,
n
где 
n
n
– символ евклидовой нормы в R .
2. Вводится дополнительная действительная переменная z n1 , и формируется система
выпуклых неравенств
 i ( z)  z n 1 ,
т. е. система
n
Z n 1 : (  ( z j  z (ji ) ) 2 )
1
2
 z n 1  0 (i 1, m).
j 1
3. Формируется задача математического программирования
z n1 
 min
при условиях  i ( z )  z n 1  0 ( i  1, m).
Для решения этой задачи используется итерационный градиентный алгоритм метода
Зойтендейка (случай нелинейных ограничений-неравенств) (см., например, [10]). Тогда для части
(e )
(e)
(e )
(e)
(e)
координат сформированного значения вектора z n 1  ( z 1 , z 2 ,,z n ,z n 1 )   Z n 1 , где z (ne)1 –
решение задачи математического программирования), будет выполняться (с заданной точностью)
следующее соотношение:
min max  i ( z )  max  i (z (e ) )  z (ne)1  r (n ) (Z),
zZ i1,m
i1,m
 ( z , z , , z (ne ) )   R n является чебышевским центром множества Z (его
минимаксной оценкой), а
z (ne)1  r ( n ) (Z )  R 1 есть значение величины его чебышевского
т.е.
z
( e)
(e)
1
(e)
2
радиуса.
Использование:
CHEBR (n, m, C, X); .
Входные параметры:
n – размерность фазового пространства (тип: integer);
m – число всех вершин многогранника Z (тип: integer);
С – массив, содержащий координаты всех вершин многогранника Z (тип: аrrау [1..n  m] of
real; type: t7).
Выходные параметры:
Х – в X ( i ), i  1, n находятся координаты чебышевского центра многогранника Z, в Х(n+1)
- значение величины чебышевского радиуса многогранника Z (тип: array [1. . n+1] of real; type: 13).
Замечания по использованию:
1) в п/п создаются рабочие массивы: А (тип: аrrау [1. . (m  4)  ( 2  (n  m  9)) ] of real;
type: t7), NI (тип: array [l . . m] of integer; type: tl4), SI (тип: array [ 1. . m] of real; type: t15), D (тип:
array [1. .n+1] of real; type: t3), NВ (тип: аrrау [1. . m+4] of integer; type: t13), ХХ (тип: аrrау
[1. . m+4] of real; type: tl2);
2) используется п/п MODIF.
7. Подпрограмма HSG: «Построение в фазовом пространстве информационного
множества, совместимого с заданным сигналом, и при наличии ошибок измерений».
Математическое описание. Пусть G(t) есть выпуклый, замкнутый и ограниченный
многогранник (с конечным числом вершин) возможных фазовых состояний z( t )  R n (n  N)
наблюдаемого объекта в момент времени t  N . За этим объектом ведется наблюдение, в
результате которого измеряется сигнал ( t )  R m (m  N, m  n) . Этот сигнал формируется в
соответствии с векторным уравнением
( t )  C( y ( t ))z ( t )  D( t )( t )
(11)
при заданных ограничениях
z( t )  G( t ), ( t )  ( t ) ,
(12)
где фазовый вектор наблюдателя y ( t )  R k ( k  N ) ; ошибка измерения сигнала ( t )  R l ( l  N ) ;
C( y ( t )) и D(t) – действительные матрицы размера (m  n) и (m  l ) соответственно, и матрица
C( y ( t )) имеет ранг, равный m; (t ) – выпуклый, замкнутый и ограниченный многогранник (с
l
конечным числом вершин) из R допустимых ошибок измерений. Множества G(t ) и (t )
заданы соответственно множествами n (G( t )) и 1 (( t )) всех своих вершин каждое.
Требуется найти множество n ( Z(t ))  R n всех вершин множества Z( t )  R n , которое есть
множество всех возможных фазовых состояний наблюдаемого объекта в момент времени t,
совместимых с сигналом (t ) и имеющейся информацией об элементах системы (11), (12), т.е.
Z(t) – информационное множество [1, 2] для данной системы. Отметим, что искомое
информационное множество Z(t) представляет собой выпуклый, замкнутый и ограниченный
n
многогранник (с конечным числом вершин) из R .
Решение сформулированной задачи может быть найдено с помощью следующего
обобщенного алгоритма.
Алгоритм 3
Шаг 1. Сформировать следующее дискретное множество:
H( t )  {x ( t ) : x( t )  R m , x( t)  CP( t )[( t )  D( t )( t )],
( t )  1 ( ( t ))},
где CP(t) есть матрица размера m  m, являющаяся обратной матрицей к матрице,
соответствующей базисному минору матрицы C(y(t)).
Шаг 2. Для сформированного дискретного множества H(t) найти множество m (co m ( H( t )) всех
вершин множества co m H(t ) , которое определяется с помощью п/п KPABEP.
Шаг 3. На основе сформированного множества m (co m ( H( t )) определить все крайние
опорные
Пусть
гиперплоскости множества co m H(t ) , которые находятся с помощью п/п GIPBER.
b ji – j-я координата нормального вектора i-й крайней опорной гиперплоскости
( j  1, m, i  1, s ; s – число всех гиперплоскостей, s  N ), a b m 1,i – свободный член i-й
гиперплоскости. Если m = n, то перейти на шаг 6; иначе, на шаг 4.
Шаг 4. Построить следующие m векторов:
g 1  (1, 0, ..., 0, p 1,m 1 , ..., p 1n ),
g 2  ( 0, 1, ..., 0, p 2 ,m 1 , ..., p 2 n ) ,
 ,
g m  (0
,0
,
,1, p m ,m 1 , ..., p mn ).



(13)
m
Здесь для любого i  1, m координаты вектора gi являются i-й строкой матрицы, которая
есть произведение матриц CP(t) и C(y(t)). В (13) приведен случай, когда базисный минор
матрицы C(y(t)) находится в левом верхнем углу. В общем случае расположение элементов этой
матрицы произвольно.
Шаг 5. В пространстве R n (случай m  n ) определить крайние опорные гиперплоскости
множества co n (H( t )), которые находятся следующим образом:
h ji  b1i g 1  ...  b mi g m , h n 1,i  b m1,i
( j  1, n, i  1, s; s  N),
где h ji – j-я координата нормального вектора i-й крайней опорной гиперплоскости, a h n 1,i – ее
свободный член.
Шаг 6. На основе множества n (G (t )) сформировать с помощью п/п GIPBER множество
всех крайних опорных гиперплоскостей множества G(t).
Шаг 7. С помощью п/п CRAPOV найти множество всех вершин пересечения множеств
co n ( H( t )) и G(t), которое и будет искомым множеством n ( Z(t )) – множеством всех вершин
информационного множества Z( t )  co n (H( t ))  G( t ) для системы (11), (12).
Конец алгоритма 3.
Использование:
HSG (n, m, l, ng, lk, G, S, KS, w, D, np, GG);
Входные параметры:
n – размерность фазового пространства (тип: integer);
m – размерность сигнала (t ) (тип: integer);
l – размерность ошибки измерения сигнала (t ) (тип: integer);
ng – число всех вершин многогранника G(t) (тип: integer);
lk – число всех вершин многогранника (t ) (тип: integer);
G – массив, содержащий координаты всех вершин многогранника G(t) (тип: array [
1. . n  ng ] of real; type: t7);
S – матрица C(y(t)) (тип: array [ 1. . m  n ] of real; type: t1);
KS – массив, содержащий координаты всех вершин многогранника (t ) (тип: аrrау [
1. . l  lk ] of real; type: t6);
w – массив, содержащий координаты сигнала ( t ) (тип: аrrау [1. .m] of real; type: t3);
D – матрица D(t) (тип: аrrау [ 1. . m  1 ] of real; type: t2).
Выходные параметры:
np – число всех вершин многогранника Z(t) (тип: integer);
GG – массив, содержащий координаты всех вершин многогранника Z(t) (тип: аrrау
[1..(n+1)  np] of real; type: t7).
Замечания по использованию:
1) если ранг матрицы C(y(t)) меньше m, то выдается соответствующее сообщение, и
выполнение основной программы прерывается;
2) в п/п создаются рабочие массивы, использующие динамическую память: B(type: t10),
C(type: t10); размеры массивов В и С рекомендуется задавать максимально возможными; в конце
выполнения п/п указанные переменные уничтожаются;
3) используются п/п MTRAB, CRAPOV, OBREACH и GIPBER.
3. О головной программе FILTR
Моделирование решения задачи апостериорного минимаксного оценивания для дискретной
динамической системы из [3] осуществляется в соответствии с алгоритмом, предложенным в
работе [4], и реализуется с помощью головной программы FILTR, написанной на языке
программирования Turbo-Pascal для персонального компьютера IBM PC/AT. Эта программа
оформлена в виде модуля BTULSHOR.TPU и использует библиотеку стандартных подпрограмм,
описанную в разд. 2.
ЛИТЕРАТУРА
1. Красовский Н.Н. Теория управления движением. М.: Наука, 1968.
2. Куржанский А.Б. Управление и наблюдение в условиях неопределенности. М.: Наука,
1977.
3. Шориков А.Ф. Алгоритм решения задачи апостериорного минимаксного оценивания
состояний дискретных динамических систем. I // Автоматика и телемеханика. 1996. № 7.
4. Шориков А.Ф. Алгоритм решения задачи апостериорного минимаксного оценивания
состояний дискретных динамических систем. II // Автоматика и телемеханика. 1996. № 9.
5. Шориков А.Ф. Минимаксные фильтры для нелинейных дискретных систем //
Кибернетика. 1990. № 4.
6. Лотов А.В. Численный метод построения множеств достижимости для линейных
управляемых систем с фазовыми ограничениями // Журн. вычисл. математики и мат. физики. 1975.
Т.15. № 1.
7. Лотов А.В. Введение в экономико-математическое моделирование. М.: Наука, 1984.
8. Черников С.Н. Линейные неравенства. М.: Наука, 1968.
9. Черникова Н.В. Алгоритм для нахождения общей формулы неотрицательных решений
системы линейных уравнений // Журн. вычисл. математики и мат. физики. 1964. Т.4. № 4.
10. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир,
1982.
11. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. М.: Наука, 1969.
*****
1/--страниц
Пожаловаться на содержимое документа