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

Липецкий эколого-гуманитарный институт

УДК 62.529+669:162.24 ББК 32.965.6 Б71 Блюмин, С. Л. Дискретное моделирование систем автоматизации и управления [Текст]: монография / С.Л. Блюмин, А.М. Корнеев ; Липецкий экологогуманит. ин-т. – Липецк: ЛЭГИ, 2005. – 124 с. ; библиогр. с. 121-123 ; 21 см.

С.Л. Блюмин, А.М. Корнеев

Представлены подходы к построению дискретных моделей, базирующихся на клеточной интерпретации. Рассмотрены дискретные пространственные, дискретные пространственно-временные, конечно-аргументные модели. Дискретно-аргументный подход можно использовать для описания сложных технологических процессов, характеризующихся многостадийностью обработки. Технологический процесс представлен в виде клеток, каждая из которых соответствует отдельному технологическому агрегату или переделу. Описав в виде входов, состояний и выходов характеристики сырья, технологических параметров и свойств готовой продукции, можно моделировать технологии обработки любых видов продукции. Использование конечных и вероятностных автоматов, итеративных цепей и сетей позволяет описать любой сложный технологический процесс и осуществлять управление технологией. Монография утверждена и рекомендована к печати научно-техническим советом ЛЭГИ для студентов по отдельным дисциплинам специальностей 220501 «Управление качеством», 230401 «Прикладная математика», 230102 «Автоматизированные системы обработки информации и управления», а также для аспирантов и преподавателей вузов.

Библиография: 46 назв.

АВТОМАТИЗАЦИИ

И

УПРАВЛЕНИЯ

Рецензенты: кафедра математического анализа, алгебры и геометрии Липецкого государственного педагогического университета (заведующий кафедрой, доктор физико-математических наук, профессор Калитвин А.С.); доктор технических наук, профессор О.Я. Кравец (Воронежский государственный технический университет)

ISBN 5-900037-47-9

Липецк 2005

© Блюмин С.Л., Корнеев А.М., 2005

2

Оглавление Введение ................................................................................................ 5 1. Автоматы ......................................................................................... 6 1.1. Конечные автоматы (КА). Дискретно-детерминированные схемы ....................................... 6 1.2. Описание технологии с помощью конечных автоматов.......... 16 1.3. Вероятностные конечные автоматы (ВКА) (Р-схемы). ........... 31 (Дискретно-стохастические модели) ......................................... 31 1.4. Представление технологического процесса в виде вероятностного автомата............................................................ 36 2. Дискретные пространственные модели ................................... 42 2.1. Одномерные однонаправленные линейные итеративные цепи............................................................................................. 43 2.2. Одномерные двунаправленные линейные итеративные цепи. 44 2.3. Двумерные однонаправленные линейные итеративные цепи . 46 2.4. Двумерные двунаправленные линейные итеративные цепи ... 50 2.5. Двумерные полуторанаправленные линейные итеративные цепи............................................................................................. 53 2.6. Другие двумерные цепи............................................................ 54 2.7. Трехмерные однонаправленные линейные итеративные цепи 56 2.8. Многомерные однонаправленные линейные итеративные цепи............................................................................................. 56 2.9. Использование итеративных цепей для описания технологического процесса........................................................ 58 3. Дискретные пространственно-временные модели ................... 64 3.1. Одномерные однонаправленные линейные итеративные сети 64 3.2. Одномерные двунаправленные итеративные сети .................. 69 3.3. Одномерные линейные клеточные автоматы........................... 70 3.4. Клеточные конечные автоматы (ККА)..................................... 70 3.5. Линейные клеточные автоматы. Переход к ассоциированному уравнению ................................. 74 3.6. Аналитическое представление ККА......................................... 81 3.7. Использование дискретных пространственно-временных моделей при расчете себестоимости металлопродукции.......... 91 4. Дискретные конечно-аргументные модели ............................... 98 4.1. Одномерные циклические линейные итеративные цепи (N-цепи) .................................................................................... 100

3

4.2. Одномерные полициклические линейные итеративные цепи ((m)-цепи).................................................................................. 102 4.3. Двумерные полициклические линейные итеративные цепи (двумерные (m)-цепи)............................................................... 103 4.4. Одномерные полициклические линейные итеративные сети (решетчатые модели)........................................................ 105 5. Сети Петри................................................................................... 107 5.1. Описание сетей Петри ............................................................ 107 5.2. Использование сетей Петри при расчете себестоимости продуктов металлургического производства.......................... 113 Заключение....................................................................................... 119 Библиографический список........................................................... 120

Внимание! В конец данного файла вынесены некоторые фрагменты основного текста: Таблица 1.1 (с. 10), Таблица 1.2 (с. 12), Таблица 1.3 (с. 13), Таблица 1.23 (с. 27), Таблица 1.35 (с. 40), Рис. 2.16 (с. 61), Таблица 3.1 (с. 68), Таблица 3.2 (с. 83).

4

Введение

1. Автоматы

Клеточная интерпретация в математической теории дискретно-аргументных систем играет роль, подобную теории геометрической интерпретации в математическом анализе или гидродинамической интерпретации в математической теории скалярных и векторных полей. Основанное на этой интерпретации представление дискретно-аргументных систем столь удобно, наглядно и естественно, что в обзоре [1] значительное количество таких систем объединено под названием «линейные клеточные машины». Сущность клеточной интерпретации состоит в том, что подавляющее большинство известных к настоящему времени дискретно-аргументных моделей допускает представление в виде тех или иных клеточных конфигураций в широком смысле слова. При этом используются всего два типа простейших клеток: клетка без памяти, или комбинационная цепь, и клетка с памятью, или дискретно-временная динамическая система. Они являются элементарными «дискретно-аргументными блоками» в структурной теории дискретно-аргументных систем, которая может быть разработана подобно являющейся уже классической структурной теории сосредоточенных систем или возникшей в последнее время структурной теории сложных распределенных систем [2]. В [2] предложено под «элементарным распределенным блоком» понимать всякую распределенную систему, для которой известен в явном виде оператор (аналитический или алгоритмический), однозначно относящий каждому входному сигналу некоторый выходной сигнал. В соответствии с таким определением «элементарные блоки» могут описывать весьма сложные краевые задачи для уравнений математической физики. Дискретно-аргументный подход можно использовать для описания сложных технологических процессов, характеризующихся многостадийностью обработки. Технологический процесс можно представить в виде клеток, каждая из которых соответствует отдельному технологическому агрегату или переделу. Описав в виде входов, состояний и выходов характеристики сырья, технологических параметров и свойств готовой продукции, можно моделировать технологии обработки любых видов продукции. Использование конечных и вероятностных автоматов, итеративных цепей и сетей позволяет описать любой сложный технологический процесс и осуществлять управление технологией.

1.1. Конечные автоматы (КА). Дискретно-детерминированные схемы

5

На основе теории автоматов система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени t ∈ Z 0 = { 0, 1, 2, ...} [3–5]. Автомат можно представить как некоторое устройство (черный ящик), на которое передаются входные сигналы и снимаются выходные.

v[t]

Черный ящик

y[t]

Рис. 1.1. Устройство «чёрный ящик»

Но так как у автомата по определению существует внутренняя характеристика (состояние), то это делает «черный» ящик «серым». v[t]

y[t]

Рис. 1.2. Устройство «серый ящик»

Конечный автомат – автомат, у которого множества значений внутренних состояний, входных и выходных сигналов конечны. Конечный автомат можно представить как математическую схему (F-схему), характеризующуюся шестью элементами [4,5]: 1). Конечное множество входных сигналов V (входной алфавит). Входные сигналы v [ t ] в любой момент времени принимают значения из этого входного алфавита v[ t ] ∈ V , t ∈ Z 0 . 2). Конечный внутренний алфавит X. Состояние автомата x[t] принимает значения из этого внутреннего алфавита: x[t]∈X, t∈Z0 3). Конечный выходной алфавит Y. y[t]∈Y, t∈Z0 6

4). Начальное состояние (состояние в начальный момент времени). x0 = x[0] 5). Функция переходов. Определяет состояние конечного автомата в некоторый момент времени t, если в предшествующий момент он был в каком-то состоянии x[t – 1] и на вход поступил сигнал v[t]: x[t] = ϕ(x[t – 1], v[t]). (1.1) При заданном начальном состоянии конечный автомат может функционировать, даже если нет входного воздействия (автономный автомат). 6). Функции выходов определяется типом конечного автомата (рассмотрим автоматы Мили и Мура). а). Конечный автомат Мили. Для автомата Мили выход определяется состоянием автомата в предыдущий момент времени x[t – 1] и сигналом, поступающим на вход в данный момент v[t]: y[t] = ψ(x[t – 1], v[t]). (1.2) б). Конечный автомат Мура. Для автомата Мура выход определяется состоянием автомата в тот же момент времени и не зависит от входного сигнала: y[t] = ψ% (x[t]). (1.3) Конечный автомат определяется как кортеж (шестерка) F = . (1.4) Конечный автомат функционирует в дискретном автоматном времени, моментами которого являются такты, т.е. примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Конечный автомат в каждый момент t = 0, 1, 2, … дискретного времени находится в определенном состоянии x[t], причем, в начальный момент времени t = 0 он всегда находится в начальном состоянии x0. В момент t, будучи в состоянии x[t], автомат способен воспринять на входном канале сигнал v[t] и выдать на выходном канале сигнал y[t], переходя в состояние x[t + 1]. Работа конечного автомата происходит по схеме: на каждом t-м такте на вход автомата, находящегося в состоянии x[t], подается некоторый сигнал v[t], на который он реагирует переходом в [t+1]-м такте в новое состояние x[t + 1] и выдачей некоторого выходного сигнала. В общем случае конечный автомат имеет много входов, состояний и выходов. v[t] = (v1[t], …, vm[t]) – вектор составленный из скалярных входов (m – число входов). x[t] = (x1[t], …, xn[t]), n – число состояний. y[t] = (y1[t], …, yL[t]), L – число выходов. 7

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

 v = v1 ×…× vm   x = x1 ×…× xn .  y = y ×…× y 1 L 

(1.5)

В этом случае функции переходов и выходов допускают развернутую запись: функция переходов для автоматов Мили и Мура. xi[t] = ϕi (x1[t – 1], …, xn[t – 1]; v1[t], …, vm[t]), (1.6) i = 1, …, n ; функция выходов для автомата Мили: yi[t] = ψj (x1[t–1], …, xn[t – 1]; v1[t], …, vm[t]), (1.7) j = 1, …, l ; функция выходов для автомата Мура: yi[t] = ψ% j(x1[t], …, xn[t]) , (1.8) j = 1, …, l . Автомат Мили – более общий автомат, чем автомат Мура. У каждого конечного автомата Мура есть конечный автомат Мили его интерпретирующий. Если ограничиться рассмотрением двоичных или булевых автоматов, то алфавиты входов, состояний и выходов составят произведения: V = {0, 1} × … × {0, 1} = {0, 1}m = {σα,, α = 1, …, 2m}, (1.9) n n X = {0, 1} = {ξβ, β = 1, …, 2 } (1.10) Y = {0, 1}l = {τϒ, ϒ = 1, …, 2l} , (1.11) где σα, ξβ, τϒ – элементы прямого произведения. Тогда функции переходов и выходов запишутся в виде: запись КА Мура (всегда штрих будет означать предшествующий момент времени) ξ β = ϕ (ξ β' , σ α )  ; (1.12)  τ = ψ% (ξ ) β  γ запись КА Мили ξ β = ϕ (ξ β' , σ α )  .  τ = ψ (ξ ' , σ ) β α  γ

(1.13)

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

aiji – составляющие алфавитов входов; ji = 1, …, Ji , где Ji – значность алфавита i-го выхода; i = 1,…, m – номера входов; bkjk – составляющие алфавитов состояний; jk = 1,…, Jk, где Jk – значность алфавита k-го состояния; k = 1,…, n – номера состояний; C pj p – составляющие алфавитов выходов; Jp = 1,…, Jp, где Jp – значность алфавита p-го выхода; р = 1,…, L, где p – номер выходa. Так как в общем случае конечный автомат имеет несколько входов, состояний и выходов, то алфавиты представляют собой прямые произведения более простых алфавитов. Таким образом: ♦ конечный входной алфавит m

V = {a11,…,a 1J1 } × … × {am1,…a mJ m } = {σα, α = 1,…, A; A = ∏ J i }, i =1

(1.14)

где σα – вариант сочетания алфавитов входов v[t]; ♦ конечный алфавит состояний n

X = {b11,…,b 1J1 } × … × {bn1,…,b nJ } = {ξβ ,β = 1,…,B; B = ∏ J k }, (1.15) n i =1

где ξβ – вариант сочетания алфавитов состояний x[t]; ♦ конечный выходной алфавит l

Y = {C11,…,C 1J1 } × … × {C l 1 ,…,b lJ } = {τγ,,γ = 1,…, C; C = ∏ J p }, (1.16) l p =1

где τγ – вариант сочетания алфавитов выходов y[t]. Так как количество значений входов, состояний и выходов конечно, то функции переходов и выходов могут быть представлены в табличной форме. Таблицы переходов и выходов могут быть представлены таблицами с одним входом (табл. 1.1).

9

10

Все возможные значения входов для удобства можно записывать в столбец блоками. В этом случае каждому сочетанию алфавитов входов v[t] ставятся в соответствие все возможные комбинации состояний ξβ. Выход конечного автомата Мили определяется состоянием автомата в предыдущий момент времени и сигналом, поступившим на вход в данный момент. При представлении конечного автомата Мили таблицей с одним входом, выходы заносятся в столбец (y1, …, yl). Так как входы записаны блоками, а для каждого блока представлена полная комбинация состояний, то, учитывая, что выход у конечного автомата Мура зависит от состояний и не зависит от входов, для любого блока входов полная комбинация состояний повторяется. Следовательно, выход для любого блока – блок некоторой комбинации выходов

τ γ′ , определяемый

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

(

)

Таблицы переходов и выходов могут быть представлены таблицами с двумя входами (табл. 1.2 и 1.3). У конечного автомата Мура нет таблицы выходов, аналогичной автомату Мили. Это объясняется тем, что выходы непосредственно зависят от состояний. Поэтому для автомата Мура таблица выходов сводится к строке состояний значений выходов соответствующих определенному сочетанию состояний, и располагается над значениями состояний таблицы переходов. Получена отмеченная таблица переходов конечного автомата Мура (табл. 1.4). С каждым конечным автоматом Мура связан интерпретирующий его конечный автомат Мили, описываемый не отмеченной таблицей, а двумя таблицами с двумя входами. Таблица переходов автомата Мура аналогична таблице переходов автомата Мили (табл. 1.2). Интерпретирующая функция выходов определяется как суперпозиция функции переходов Мура с его функцией выходов. Таблица выходов интерпретирующего автомата определяется по следующей схеме: 1. Из таблицы переходов (табл. 1.2) по сочетанию значений входов σ α и предыдущих состояний ξ β′ определяется новое сочетание состояний ξ β . 2. Из отмеченной таблицы переходов (табл. 1.4) для сочетания ξ β′ , совпадающего с сочетанием ξ β , определяется сочетание выходов τ γ′ . 3. В таблицу выходов интерпретирующего автомата для рассмотренных σ α и ξ β′ заносится сочетание выходов τ γ , совпадающее с сочетанием τ γ′ . 11

12

Таблица 1.4 Отмеченная таблица переходов конечного автомата Мура … c1' j , …, c'pj , …, clj' (τ'γ) … y'1, …, y'l 1 l p ' ' x'1, …, x'n b ' ,…, b ' ,…, b ' b' ,…, bkjk ,…, b nj n 11 n1 k1 … 1j1 (ξ'1) (ξ'β ) v1, …, vm a11, …,ai1, …, am1 . (σ1) . … . a1 j ,…, a ij ,…, a mj c , …, c , …,

a1J 1

(σα) … ,…, a iJ ,…, a mJ i

1 j1

m

i

1

pj p

…

b 1' J 1

,…, bkJ' ,…, b'nJ k

n

(ξ'В)

clj l

(τγ) . . .

m

(σА)

Конечные автоматы могут быть представлены с помощью матрицы соединений (табл. 1.5). Таблица 1.5 Матрица соединений конечного автомата x1,… xn,

b ,..., b ,..., b kj k 1 j1 nj n

b ,..., b ,..., b 11 k1 n1

x1',…,xn'

(ξ ) ' 1

…

( ) ξ β'

… ξ B'

( )

(ξ ) 1

…

(ξ

β

…

…

… σ

…

)

τ

α γ

σ 1 ∨ ... ∨

τ

1

…

,..., b ,..., b b 1J kJ nJ 1 k n

…

(ξ ) B

… α γ

i

или 0

…

i

…

Матрица соединений строится как квадратная матрица того же порядка В, что и число сочетаний автомата. n

B = ∏ jk . i =1

(1.17)

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

14

вующие значения выходов. На пересечении строки ξ β′ и столбца ξ β распо-

(0,0)

лагается сочетание значений входов σ α , вызывающее переход автомата из состояния ξ β′ в состояние ξ β . В знаменателе указывается сочетание значе-

0/1

0/1 (0,1)

1/0

1/0

0/1 (1,0)

(0,0)

Рис. 1.3. Граф автомата Мили

(0,1)

1/1

(1,1)

1/0

0/0

0/0 1/1

0/0

0/1v1/1

(1,0)

(0,1)

1/0

0/0

(0,1)

(0,1)

(1,1)

1/1

0/0

(0,0)

1/1

(1,0)

1/1 (1,1)

0/1

1/0 (1,0)

0/1

(0,1)

1/0

Рис. 1.5. Дерево автомата Мили

Представление конечных автоматов при помощи многочленов Жегалкина

Конечный автомат можно представить в виде ориентированного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата (направление дуги соответствует переходу из одного состояния в другое). Дуги соответствуют элементам матрицы соединений. Граф интерпретирующего автомата Мили для автомата Мура совпадает с графом исходного автомата Мура. Свойством такого графа является то, что на всех дугах, сходящихся в некоторую вершину, буква выходного алфавита – одна и та же. Конечный автомат можно представить графом другого типа – ориентированным деревом. Корнем этого дерева служит начальное состояние автомата (вершина первого ранга). Из нее проводится столько дуг, сколько букв во входном алфавите (дуги первого ранга помечаются так же, как в матрице соединений и графе автомата). Каждая дуга входит в вершину второго ранга. Из каждой вершины второго ранга проводятся, в свою очередь, дуги второго ранга, входящие в вершины третьего ранга и т.д. Тем самым, дерево автомата – ориентированный граф, в каждую вершину которого, кроме корня, входит одна дуга и который не содержит контуров. Примеры графов представлены на рис. 1.3-1.4, а дерева – на рис. 1.5.

0/0

0/1

(1,0)

(0,0)

Представление конечных автоматов графами

(1,1)

1/0

0/0

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

(0,0)

(0,0)

(0,1)

ний выходов τ γ , которое появится при осуществлении данного перехода.

0/0v1/1

(1,0)

Состояния и выходы двоичных автоматов Мили и Мура удобно описывать с помощью многочленов Жегалкина [5-7]. Рассмотрим автомат с двумя состояниями и выходами и одним входом, и получим многочлены Жегалкина для каждого состояния и каждого выхода. Для двоичного конечного автомата Мили многочлены Жегалкина будут иметь вид: x1 = a0 ⊕ a1 ⊗ x'1 ⊕ а2 ⊗ х'2 ⊕ а3 ⊗ v⊕ a12 ⊗ x'1 ⊗ х'2 ⊕ а13 ⊗ х'1 ⊗ v ⊕ а23⊗ ⊗ х'2 ⊗ v ⊕ а123 ⊗ х'1 ⊗ х'2 ⊗ v; (1.18) x2 = b0 ⊕ b1 ⊗ x'1 ⊕ b2 ⊗ х'2 ⊕ b3 ⊗ v ⊕ b12 ⊗ x'1 ⊗ х'2 ⊕ b13 ⊗ х'1 ⊗ v ⊕ ⊕ b23⊗ х'2 ⊗ v ⊕ b123 ⊗ х'1 ⊗ х'2 ⊗ v; (1.19) y1 = c0 ⊕ c1 ⊗ x'1 ⊕ c2 ⊗ х'2 ⊕ c3 ⊗ v ⊕ c12 ⊗ x'1 ⊗ х'2 ⊕ c13 ⊗ х'1 ⊗ v ⊕ c23 ⊗ ⊗ х'2 ⊗ v ⊕ c123 ⊗ х'1 ⊗ х'2 ⊗ v; (1.20) y2 = d0 ⊕ d1 ⊗ x'1 ⊕ d2 ⊗ х'2 ⊕ d3 ⊗ v ⊕ d12 ⊗ x'1 ⊗ х'2 ⊕ d13 ⊗ х'1 ⊗ v ⊕ ⊕ d23⊗ х'2 ⊗ v ⊕ d123 ⊗ х'1 ⊗ х'2 ⊗ v. (1.21) Для двоичного конечного автомата Мура многочлены Жегалкина для состояний аналогичны многочленам для автомата Мили. Для выходов автомата Мура многочлены будут иметь вид: y1 = c'0⊕c'1⊗x1⊕c'2⊗х2⊕c'12⊗x1⊗х2; (1.22) y2 = d'0⊕d'1⊗x1⊕d'2⊗х2⊕d'12⊗x1⊗х2. (1.23)

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

1/1

Рис. 1.4. Граф автомата Мура

15

16

рикаты), состояний – X (технологических параметров по каждому агрегату) и выходов – Y (свойств готовой продукции). Вектор, составленный из скалярных входов V [ t ] = (V1 [ t ], ... ,V L [ t ] ) , где L – число входов, аналогично для состояний (технологических факторов):

(

x [ t ] = x 11 [ t ], ... , x 1 M 1 [ t ], x 21 [ t ], ... , x 2 M 2 [ t ], x k 1 [ t ], ... , x kM

k

[t]

)

и выходов:

y [ t ] = ( y 1 [ t ], ... , y R [ t ] ) , где Mi – число технологических факторов i-го передела; К – число технологических переделов; R – число показателей качества. Функции переходов и выходов допускают развернутую запись: xiji [ t ] = ϕ i ( x11 [ t ], ... , x1M 1 [ t ], x 21 [ t ], ... , x 2 M 2 [ t ], ..., x( i −1 ),1 [ t ], ... , x( i −1 ),M i −1 [ t ],

v1 [ t ],...,v L [ t ]) . Последующие:

(1.24)

x ( i + 1 ), 1 [ t ], ... , x ( i + 1 ), M i + 1 [ t ] , ... , x K 1 [ t ] ... , x k M

k

[t]

считаем равными нулю, т.к. процесс еще не реализован (рис. 1.6). Можно исследовать безусловные вероятности, с которыми каждый из входов σ α ∈ V может оказаться начальным. Это позволяет оценить характеристики поступающего сырья с помощью вероятностей и законов распределения случайных величин. Алфавиты входов, состояний и выходов могут иметь различную значность (количество диапазонов изменения). Пусть L – количество характеристик, образующих входной сигнал. Каждая входная величина может иметь свою значность (количество дискретных непересекающихся значений). В качестве примера входной величины можно взять один из элементов химического состава сляба. Пусть содержание углерода в стали изменяется в интервале от 0,05 до 0,08%. Если разбить на составляющие {0,05; 0,06; 0,07; 0,08}, то получим значность алфавита равным 4. Допустим, что это первая входная величина, тогда (J1 = 4), а ai1 – i-я составляющая алфавита 1-го входа. Таким образом, конечный входной алфавит (см. 1.15): L

V = { a11 ,...,a1 J 1 } × ...× { a L1 ,...,a LJ L } = { σ α ,α = 1, ..., A; A = ∏ J i } , (1.25) i=1

где σ α – вариант сочетания алфавитов входов v [ t ] любого передела. В более общем случае каждый агрегат характеризуется набором технологических величин, определяющих процесс обработки, сырьём и затратами на агрегате. Технологический процесс может осуществляться в виде параллельных и последовательных потоков (рис. 1.6 и 1.7). 17

Рис. 1.6. Представление технологического процесса в виде параллельных потоков X imi –

mi

технологический фактор i-го передела (агрегата);

ских факторов на i-м переделе;

Z ig i

–

gi

чество элементов затрат на i-м переделе;

Mi

– количество технологиче-

элемент затрат i-го передела (агрегата);

Gi

Vili – li-я входная величина i-го передела (агрегата); Li – количество входных элементов (сырья)

18

– коли-

jr = 1, ..., J r – значность алфавита p-го выхода; r = 1, ..., R – номер выхода. Таким образом, конечный входной алфавит:

V ={a111,...,a11J1}×...×{a1L11,...,a1L1JL1 }×...×{ak11,...,ak1J1 }×...×{akLk1,...,akLk JL }= k

(1.26)

Lk

={σαk ,αk =1,...,Ak ; Ak =∏Ji} i=1

где σ α – вариант сочетаний алфавитов входов V [ t ] , Ak – максимальное количество сочетаний алфавитов входов на k-м агрегате. Рис. 1.7. Представление технологического процесса в виде последовательных потоков i = 1, …, K – число агрегатов; l = 1, …, R – число показателей качества; i-го агрегата, j = 1, …, N;

Z ig j

X im j

Vin j

Конечный внутренний алфавит (алфавит технологических факторов)

– nj-й вход для

– mj -й технологический фактор i-го агрегата, j = 1, …, M;

– gj-й элемент затрат на i-м агрегате, j = 1, …, G;

Yl

1

(1.27)

Mk

={ξβ k , βk =1,...B; B = ∏Ji} i=1

– l-й показатель качества

где ξ β k – вариант сочетания алфавитов на k-м агрегате; K – число агрегатов;

Так как в общем случае производственный процесс, представленный в виде конечного автомата, имеет несколько входов, состояний (технологических факторов), разделенных по переделам или агрегатам, и выходов, а алфавиты входов, состояний и выходов могут иметь разную значность, то их составляющие можно представить следующим образом: k = 1, ..., K – номер передела (агрегата);

a kl k j l – составляющая алфавитов входов, где j l = 1 , ..., J l , где k k

X ={b111,...,b11J1 }×...×{b1M11,...,b1M1JM }×...×{bk11,...,bk1J1 }×...×{bkMk1,...,bkMk JMk }=

mk – число факторов на k-м агрегате. Вариант сочетания алфавитов на 1-м агрегате: M1

ξ β1 = {b111 ,..., b11 J1 } × ... × {b1M11 ,..., b1M1J1 } = {ξ β1 , β 1 = 1,..., B1 ; B1 = ∏ J i } (1.28) i =1

Вариант сочетания алфавитов на k-м агрегате:

k

J lk значность алфавита l-го входа на k-м агрегате;

lk = 1, ..., Lk – номер входа (элементов сырья, полуфабрикатов) на k-м агрегате; J lk – значность алфавита l-го входа на k-м агрегате; bk ,mk jm – составляющая алфавитов состояний (технологических факторов) k

для k–го агрегата;

jmk = 1, ..., J mk , где J mk – значность алфавита m-го технологического

Mk

ξβk = {bk11,...,bk1J1}×...×{bkMk1,...,bkMk JM } = {ξβk , βk = 1,...,Bk ; Bk = ∏Ji }(1.29) k

Вариант сочетания алфавитов на последнем агрегате: MK

ξβK = {bK11,...,bK1J1 }×...×{bKMk 1,...,bKMk JM } = {ξβK , βK =1,...,BK ; BK = ∏Ji } (1.30) k

i=1

σ α – вариант сочетания алфавитов V [ t ] на всех агрегатах:

фактора на k-м агрегате; m k = 1 , ... , M k – номера факторов на k-м переделе; Crjr – составляющая алфавитов r-го выхода;

σ

19

i=1

20

α

, α = 1 , ... , A ; A =

K

∏

i =1

Ai ,

(1.31)

ξ β – вариант сочетания алфавитов x [ t ] на всех агрегатах: K

ξ β , β = 1, ..., B; B = ∏ Bi .

(1.32)

i =1

Конечный выходной алфавит: R

Y = { c11 , ..., c1J1 } × ...× { cR1 , ..., cRJ R } = { τ γ ,γ = 1, ..., Γ ; Γ = ∏ J i } , (1.33) i =1

распределенный алфавит данной величины (алфавит с различной частотой появления отдельных составляющих). При необходимости получения диапазонов, вероятность попадания в которые примерно одинакова (равномерный алфавит), отрезок изменения исследуемой величины разбивается на ряд неодинаковых по длине полуинтервалов. Для примера возьмем mk -ю технологическую величину k-го передела

( X ) . Отрезок изменения входной величины разбивается на ряд полуинkmk

где τ γ – вариант сочетания алфавитов входов y [ t ] .

тервалов:

bkmk 1 , bkmk 2 , ..., bkmk jm , ..., bkmk Jm k

k

, где k – номер предела, mk –

На каждом агрегате и переделе можно оценить затраты на производство. Статьи затрат определяются калькуляцией для каждого передела. Обозначим zig i – gi -й элемент затрат на i-м агрегате. Так как затраты изменяются

вит данного фактора). Численные значения j mk выбираются таким образом,

в зависимости от сортамента и условий производства, то их также можно описать с помощью конечных автоматов. Пусть d kg k j g – составляющая алфавита g-го элемента затрат на k-м

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

k

фактор r-го передела, jmk = 1, ..., J mk – полуинтервалы, образующие алфа-

Обозначим количество попаданий в полуинтервал nkmk jm , причем: k

агрегате.

j g κ = 1 ,..., J g κ , где J

gκ

– значность алфавита g-го элемента затрат

на k-м агрегате. g k = 1, ... ,G k – номера элементов затрат на k-м агрегате (переделе). В соответствии с рис. 1.6 разложение входов и состояний (технологических факторов) по агрегатам, элементов затрат и выходных показателей можно представить в виде, представленном на рис. 1.7. Как отмечалось ранее, каждая входная величина может иметь свою значность (количество непересекающихся диапазонов), аналогичные выводы можно сделать о состояниях (технологических факторах по переделам или агрегатам) и выходах. Таким образом, алфавиты входов, состояний и выходов могут иметь различную значность. Для формирования значности алфавитов каждого входа, технологического фактора или выхода необходимо рассмотреть законы распределения изучаемых величин. Если исследуемая величина может быть представлена в виде вариационного ряда, то значность ее алфавита будет принимать значения из соответствующего вариационного ряда. В случае если величина подчиняется какому-либо закону распределения и может быть представлена в виде гистограммы, то необходимо сформировать алфавит этой величины таким образом, чтобы она принимала значения из этого внутреннего алфавита. Наиболее простой способ – разбить диапазоны изменения исследуемого фактора на равные участки, однако в этом случае вероятности попадания в каждый из них могут существенно различаться, т.е. получим неравномерно 21

J mk

∑n

jmk =1

kmk jmk

=n ,

(1.34)

где n – объем выборки. Так как количество значений входов, состояний и выходов конечны, то функции переходов (из одного состояния в другое) могут быть представлены табличной форме. При этом можно использовать 2 варианта таблиц. Первый вариант состоит в представлении перехода с предыдущего состояния в последующее с учетом входных воздействий, т.е. по входным данным для 1-го передела определяется состояние на данном переделе (V1 передел → X1 передел), затем по данным о состоянии на первом переделе и входах для второго определяются состояния на 2-м переделе (V2 передел, X1 передел → X2 передел) и т.д. В этом случае все значения входов можно представить в таблице в виде блоков, записываемых в столбец. И каждому сочетанию алфавитов входов Vκ ставятся в соответствие все возможные комбинации состояний ξ β k −1 . Таким образом, для k-го передела таблица переходов будет иметь вид, представленный в табл. 1.20.

22

Таблица 1.20 Таблица переходов для k-го передела с одним входом

Таблица 1.21 Таблица переходов для k-го передела с двумя входами

x k 1 , ... , x k , M k

x k −1,1 , ... , xk −1, M k −1

Vk 1 , ... ,VkL k

xk −1,1 ,..., xk −1,M k −1 b( k−1)11,...,b( k−1)m 1,... k−1

....,b( k−1)Mk−11

b( k −1)11 , ..., b( k −1) mk −11 , ... , b( k −1) M k −11

(ξ ) 1( k−1)

a k11 ... aklk 1 ... akLk 1

b(k−1)1j1 ,...,b(k−1)mk−1jm ,...,b(k−1)Mk−1jM

(ξ

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

k−1

)

β ( k −1 )

k −1

(ξ )

)

k −1

β( k −1)

1( k−1)

σ 1( k )

......................... ξ1(k−1)

( )

ak1 j1 ...aklk jl ...akLk jL

k

σ α( k )

…

(ξ ) β( k−1)

…

(ξ ) Β( k −1)

ak1j1 ...aklk jl ...akLk jL k

k −1

…

…

(ξ ) k−1

Β(k −1)

k

k

M

k

K O

k

σ A(k ) bk1 j1 ... bkmk −1 j m ... bkM k j M k

(ξ )

k

βk

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

…

(ξ ) β( k −1)

Β ( k −1 )

(ξ β k )

N

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

1(k−1)

(ξ

M bk1 j1 ... bkmk −1 jm ... bkM k j M

N

ak1J1 ...aklk Jl ...akLk JL

…

(ξ ) …

K

k

σ α (k )

......................... ak1J1 ...aklk J l ...akLk J

O

…

Β(k −1)

σ A( k )

(ξ

b(k−1)1J1 ,...,b(k−1)mk−1Jm ,... k−1 k−1 ....,b(k−1)Mk−1JM

a k11 ... a klk 1 ... a kLk 1

k−1

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

b(k −1)1J1 , ..., b(k −1)mk−1Jm , ..., b( k −1)Mk−1JM

k

…

k −1

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

σ 1( k )

k

(ξ )

v k 1 , ... , v kL k

b( k−1)1j1 ,...,b( k−1)mk−1 jm ....,b( k −1)Mk −1 jM

)

Более наглядный вид даст таблица переходов с двумя входами (имеются в виду входы таблиц) (табл. 1.21).

В табл. 1.20-1.21 представлена зависимость текущих состояний от предыдущих и входных воздействий. При этом предшествующими считаются состояния (факторы), реализованные на предшествующем агрегате. Более полное представление может дать включение всех ранее реализованных факторов (состояний) и входных воздействий в таблицу. Накопленные на предыдущих агрегатах и переделах факторы можно представить в табл. 1.22. Таблица 1.22 Таблица переходов с накопленными на предыдущих агрегатах и пределах факторами V11...V1L1 V21...V2L2 …

23

V(k+1)1...V(k+1)L(k+1) X11...X1M X 21 ... X 2M … 2 1

Xk1 ...XkMk … X ( k +1)1 ... X ( k +1) M

σ 1(1)

σ1(2)

σ1(k +1)

ξ1

ξ1( 2 )

ξ1( k )

M σ A(1)

M

M

M

M

σA(2)

σ A(k +1)

ξΒ

M ξ Β( k )

24

( 1)

(1 )

ξ Β( 2 )

ξ β ( k +1)

( k +1 )

Общее количество строк в такой таблице, являющейся полным перебором сочетаний алфавитов входов и состояний на всех рассмотренных переделах велико и составляет D = σ α × ξβ . (1.35) i =1,..,k + 1

i =1,..,k

Таким образом, полное заполнение таблицы практически невозможно из-за отсутствия в реальных условиях производства некоторых сочетаний алфавитов. Однако анализ реального производства позволяет выделить все основные комбинации входов и состояний при различных сочетаниях алфавитов. Эти сочетания и должны быть вынесены в данные таблицы переходов. Причем, использование такого представления дает наглядную картину реализации производственных процессов с выделением их основных траекторий. При этом, после выделения всех встречающихся сочетаний алфавитов, которые можно назвать технологическими траекториями, число опытов nσξ , приходящихся на каждую траекторию, может изменяться в пределах 0 < nσξ ≤ M ,

(1.36)

где М – число опытов. В то же время, число сочетаний алфавитов Т, для которых nσξ > 0 (при nσξ = 0 сочетание автоматически исключается из таблицы) изменяется от 1 до М, но не более D. Аналогичные подходы можно использовать при составлении таблиц входов, отражающих влияние входных воздействий и технологических параметров (состояний) на выходные характеристики. В качестве выходных величин могут выступать регламентируемые стандартами свойства полуфабриката. Также в качестве таких величин можно рассматривать элементы затрат, расходуемых на данном переделе (рис. 1.8).

Рис. 1.8. Описание технологии с помощью конечных автоматов Примечания к рис. 1.8. 1). Значение индексов для входов и состояний (факторов): 1-я цифра – передел, 2-я – номер фактора, 3-я – номер алфавита соответствующего фактора; для выходов: 1-я цифра – номер выходной величины, 2-я – номер алфавита соответствующей выходной величины. 2). При исследовании выходов после каждого агрегата или передела появится 3-я цифра – передела (аналогично входам, состояниям и затратам).

ходов. 25

26

В итоге формируются табл. 1.23-1.25, аналогичные таблицам пере-

Таблица 1.24 Таблица выходов с двумя входами для k-го передела x k −1,1 , ..., xk −1,M k −1

(ξ )

(ξ )

…

1(k −1)

β(k −1)

(ξ )

…

Β( k −1)

v k 1 , ... , v kLk

O

σ 1( k ) … σ α( k )

K

… σ A( k )

M c k 1 j1 , ... , c krk jrk , ... , c kRk j Rk τ γ (k ) d k1 j1k , ... , d kg k j g k , ... , d kGk jGk ϕ λ( k ) M

N

N

K

O

Таблица 1.25 Таблица выходов после k-го передела V11 ...V1L

V(k+1)1...V(k+1)L(k+1) X11...X1M1 X21...X 2M2

V21...V2L2

Xk1...XkMk

σ 1(1)

σ 1( 2)

σ1( k +1)

ξ1(1)

ξ1( 2)

ξ1( k )

M σ A( 1)

M

M σ A( k+1)

M

M ξ Β( 2 )

M ξ Β( k )

σ A( 2)

ξ Β(1)

Примечание к табл. 1.25. σ 1( k ) = a k 11 ... a kl 1 ... a kL 1 ; k

k

σ α( k ) = ak1 j1 ...aklk jk ...akLk jk ;

σ A( k ) = ak1J ...akl J ...akL J

(ξ ) 1( k −1)

1

(ξ ) = b (ξ ) = b 27

k lk

k Lk

= b(k −1)11,..., b(k−1)mk −11,...,b(k −1) Mk −11 ;

,...,b(k−1)mk−1 jmk−1 ,..., b(k−1)Mk−1 jMk−1 ;

β(k −1)

(k−1)1 j1k−1

Β(k −1)

(k −1)1J1k −1 ,...,b(k−1)mk−1Jmk−1 ,...,b(k−1)Mk−1JMk−1

28

;

Yk1 ...YkPk

τ γ (k )

K

K

i =1

i =1

∑ Z1 ...∑ Z G k * ∑ϕλ(i) i−1 k

k ∑d * ,...,∑d * ,... i=1 i1j1i i=1 igi jgi k ....,∑d * i=1 iGi jGi

(ξ ) = b

k11,..., bkmk−11, ..., bkMk−11 ;

1k

Таблица 1.26

(ξ ) = bk1j βk

(ξ ) = b Β(k−1)

τγ k

Матрица соединений для k-го передела

...bkmk−1 jmk−1 ...bkMk−1 jMk−1 ; 1k−1

(k)

∑

k1J1k −1

...bkmk −1 J mk−1 ...bkM k −1 J Mk−1

xk ,1 , ... , xk , M k −1

= ck1j1 ,... ,ckrjr ,... ,ckRjR

ϕλ*(i) i −1

k

k

x k −1,1 , ..., xk −1,M k −1

= ∑di1 j* ,..., ∑dig j* ,..., ∑diG j* i =1

1i

i =1

i gi

i =1

,

…

i Gi

При описании технологического процесса можно использовать матрицы соединений. Матрица соединений строится как квадратная матрица того же порядка В, что и число состояний технологического процесса, представленного в виде автомата. Однако, так как не все состояния реализуемы, то получим матрицу меньшего порядка Т. Столбцы и строки матрицы соответствуют различным состояниям автомата. Элементами такой матрицы служат дроби, в числителе которых – значения входов, обеспечивающие заданный переход состояний, а в знаменателе – соответствующие значения выходов (табл. 1.26). На пересечении строки ξ β и столбца ξ β располагается сочетание значений входов (k )

σ α k , вызывающее переход автомата из состояния ξ β в состояние ( k −1 )

ξ β (k ) . В знаменателе указывается сочетание значений выходов τ γ k и ϕλk , которое появится при осуществлении данного перехода. Если указанных дробей несколько (т.е. если из одного состояния ( ξ β ) в другое ( ξ β ) ( k −1 ) (k ) можно перейти при различных сочетаниях входов

O

M σ α (k )

1( k −1)

(ξ )

σ α k ), то ставится их

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

29

K

β( k−1)

где j *g i – номер использованного выходного алфавита затрат на i-м переделе для g-го элемента.

( k −1 )

β(k )

1( k )

(ξ )

k

(ξ )

(ξ )

…

(ξ )

( a k 1 j1 ...a kl k j k ... a kL k j k ) τ γ ( k ) ; ϕ λ( k ) ( c k 1 j1 ...c kR k j R1 )

Β( k −1)

N

(ξ ) Β(k )

N K

( d k 1 j1 k ...c kG k jG1 ) M

O

Примечание к таблице 1.26.

σ α(k )

= ak1 j1 ...aklk jk

...akLk jk

;

(ξ ) = b( k−1)11,...,b( k−1)mk−11,...,b( k−1)Mk−11 ; 1( k −1)

(ξ ) = b ,..., b (ξ ) = b(k−1)1J ,...,b(k−1)m (ξ1 ) = b ,...,b ,...,b ; β(k −1)

( k −1)1 j1k −1

Β(k −1) k

k11

(ξ ) =b Β(k−1)

1k−1

kmk−11

, ..., b( k −1) M k −1 jMk−1 ;

k −1Jmk−1

1k −1

(ξβ ) =bk1j k

( k −1) mk −1 jmk −1

,..., b(k−1)Mk−1JMk−1

kMk−11

...bkmk−1 jmk−1 ...bkMk−1 jMk−1 ;

k1J1k−1 ...bkmk−1Jmk−1 ...bkMk−1J Mk−1

Чтобы сформировать алфавит каждого фактора можно воспользоваться одним из подходов: 1) деление по среднему. Для исследуемого фактора находится среднее значение по выборке, которое можно определить до ближайшего фактического значения данного фактора. В результате чего все опыты будут разбиты приблизительно на две одинаковые по объему части. Затем каждый из полуинтервалов разбивается на два новых подинтервала. Недостатком данного подхода является кратное изменение количества полуинтервалов, а следовательно, получаемых элементов алфавита (2, 4, 8 и т.д.); 2) деление на заданное количество полуинтервалов. Разделив объем выборки на задаваемое количество полуинтервалов, определяем среднее число опытов, приходящихся на каждый полуинтервал М. 30

Затем осуществляется нормирование всех элементов выборки. «Двигаясь» по выборке от минимального к максимальному значению и расширяя границы полуинтервала, суммируя все опыты, попадающие в данный полуинтервал. При достижении среднего числа опытов, приходящихся на полуинтервал, фиксируем его границы и переходим к следующему. В итоге формируются полуинтервалы, с помощью которых определяется значность алфавита данного фактора. Если какое-либо значение фактора фиксируется многократно и число его появлений близко к M ( X kmk ) , то данное значение фактора может выступать в роли элементов алфавита, как для вариационного ряда.

Последнее условие задает начальное безусловное распределение вероятностей на конечном внутреннем алфавите Х (табл. 1.27). При этом должны выполняться требования: 1) 0 ≤ Ρβ (0 ) ≤ 1 ; (1.39) 2)

зовалась пара ( ξ β′ , σ α ) ( σ α – вариант сочетания алфавитов входов υ [t ] , ξ β′ , ξ β′ – варианты сочетания алфавитов состояний x[t] в предыдущий и последующие моменты времени соответственно; τ γ – вариант сочетания алфавитов выходов y[t]):

При этом должны выполнятся требования: 1) 0 ≤ Ρβ (0 ) ≤ 1 ; 2) ∑ Pβ, (0) = 1 . ξβ∈x

сти, с которыми каждое из состояний ξ β′ может оказаться начальным: (1.38) 31

(1.42)

одна вероятность равна 1, а все остальные равны 0. Описание функционирования вероятностного конечного автомата можно трактовать так, что для каждой пары (ξ’β, σα) из множества X × V задается совместное условное распределение вероятностей. Так как внутренний алфавит Х и выходной алфавит У конечны, то имеем пару дискретных случайных величин, которая должна быть задана своим совместным законом распределения. Число таких распределений, представляемых в виде табл. 1.28, равно числу возможных пар (ξ’β, σα). При этом должны выполняться требования: 〉 1) 0 ≤ P 〈βα βα ≤ 1 ;

2)

выходного сигнала τ γ при условии, что автомат находится в состоянии ξ β′ = ξ β′ и на его вход поступил сигнал σ α . Кроме того, для вероятностного конечного автомата не задается однозначно начальное состояние ξ( 0 ) , а задаются лишь безусловные вероятно-

(1.41)

Pβ, (0) может равняться 0 или 1 при некотором ξ β ∈ X, и в силу (1.42) только

P(ξβ, τϒ / ξ’β, σα) = P<β’, α>β, ϒ , (1.37) ′ – вероятность перехода автомата в состояние ξ β и появления

P(0)( ξβ) = Pβ, (0) .

Р1, (0),…, Ρβ (0 ) ,…,РВ,(0.

Р(0)

лишь условные вероятности появления пар ( ξ β′ , τ γ ), при условии, что реали-

(1.40)

ξ 1 ,…, ξ β ,…, ξ Β

Х

В общем виде вероятностный автомат можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом тексте зависит только от состояния памяти в нем и может быть описано стохастически [8-10]. Ранее конечный автомат был рассмотрен как детерминированный, т.е. каждой паре (ξ’β, σα) (значений состояния и поступившего входа) однозначно ставилась в соответствие пара (ξβ, τϒ) (новое состояние и выход) с помощью функций переходов и выходов. Вероятностный конечный автомат – такой автомат, который не относит однозначно каждой паре ( ξ β′ , σ α ) некоторую из пар ( ξ β′ , τ γ ), а задает

где

Ρβ (0 ) =1 .

Таблица 1.27 Вероятности, с которыми каждое из состояний ξ β ∈ X может оказаться начальным

1.3. Вероятностные конечные автоматы (ВКА) (Р-схемы). (Дискретно-стохастические модели)

P<β’, α>β, ϒ

∑

ξ β ∈Χ

∑

〈βα 〉 ∑ P βα = 1.

ξ β ∈Χ τ γ ∈Υ

(1.43) (1.44)

Для полного описания вероятностного конечного автомата следует задать такие законы распределения для всех пар (ξ’β, σα). Конечный автомат можно рассматривать как частный случай вероятностного конечного автомата, где соответствующие распределения вероятностей будут вырожденными (т.е. в ряду вероятностей лишь одна 1, остальные 0).

32

Таблица 1.28 Совместный закон распределения состояний и выходов

Ρ1βα ,…….……., Ργβα ,…….……., Ρсβα

Ργ

Ρβ Ρ1βα

ξ1

Ρ11βα ,………….., Ρ1γβα ,…………..., Ρ1сβα

. . .

. . .

………………………………………… ………………………………………… …………………………………………

Ρββα

ξβ

Ρβ1βα ,…………., Ρβγβα ,……….., Ρβсβα

. . .

. . .

…………………………………………… …………………………………………… ……………………………………………

ΡΒβα

σ τ ∈ V,

τ 1 ,………………, τ γ ,……………., τ с

Y X

ξΒ

〈 βα 〉

Совместные законы распределения всегда порождают частные законы распределений. И для состояний и выходов выполняются следующие соотношения: 1) P<β’, α>β = ∑ P<β’, α>β, ϒ ; (1.45) 2) 0 ≤

τ γ ∈Υ

∑

3)

ξ β ∈Χ

≤1 ;

(1.46)

P<β’, α>β = 1 .

(1.47)

Эти соотношения задают вероятности появления состояния ξ β при условии, что было состояние ξ β1 и на вход пришло σ τ . Аналогично для выходов: 〈 βα 〉

1) P γ

= ∑

ξ β ∈Χ

〈 βα 〉

2) 0 ≤ P γ 3)

〈 βα 〉

P βα

≤1 ;

〈 βα 〉 =1 ∑ Pγ

τ γ ∈Υ

;

τ γ ∈ Y, ξ β1 , ξ β ∈ X ,

то этот автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния автомата и его выходного сигнала, т.е. означает, что новое состояние и новый выход определяются не как пара, а независимо друг от друга. Подобно конечному автомату Мура возможен вероятностный конечный автомат, у которого выход не зависит от входа, а зависит только от текущего состояния. Тогда для P<β’, α>β, ϒ задается P<β’, α>β , для каждого ξβ задается P<β>ϒ . Вероятностный конечный автомат, у которого выход не зависит от входа, а зависит только от текущего состояния, называется вероятностным

βα βα βα ΡΒ1 ,…………, ΡΒγ ,….…….., ΡΒс

P<β’, α>β

Если у вероятностного конечного автомата выход зависит от входа и предыдущего состояния и выполняется условие: P<β’, α>β, ϒ = P<β’, α>β * P<β’, α>ϒ, (1.51)

(1.48) (1.49) (1.50)

(вероятность появления выхода τ γ при условии, что было состояние ξ β1 и на вход пришло σ τ ). 33

автоматом Мура. В этом случае для каждой пары ( ξ β1 , σ τ ) задается P β

,

для каждого ξ β задается P γ〈β 〉 и должно выполняться условие

P<β’, α>β, ϒ = P<β’, α>β × P<β>ϒ . (1.52) Вероятностный конечный автомат называется автономным, если все случайные законы распределения P<β’, α>β, ϒ одинаковы при различных вариантах сочетания алфавитов входов, т.е. не зависят от входов: P<β’, α>β, ϒ = P<β’>β, ϒ , ∀σα∈V. (1.53) То есть, у автономного вероятностного автомата выходной алфавит состоит из единственной буквы и тогда количество совместных законов распределения не |X| × |V|, а только |X| (сколько состояний, столько и таблиц). Если входной сигнал вероятностного конечного автомата определяется детерминировано, т.е. не участвует в совместных законах распределения, которые в этом случае сводятся к законам распределения в количестве |X| (X – внутренний алфавит), то такой автомат называется Y-детерминированным вероятностным конечным автоматом. Таким образом, для автономного Y-детерминированного вероятностного конечного автомата достаточно задать в вероятностном смысле только закон распределения ξβ ∈ X для каждого ξ β′ ∈ X, т.е. P<β’>β , ξβ, ξ β′ ∈ X. Это означает, что вместо ранее рассмотренных наборов совместных законов распределения следует задать один совместный закон распределения для пары ξβ, ξ β′ плюс начальное распределение. Такой вероятностный конечный автомат называется марковской цепью.

34

Рассмотрим случайный дискретный процесс или случайную последовательность x[t], t ∈ Z0 = {0, 1, 2, …}, характеризуемую следующими свойствами: 1. В любой момент времени t ∈ Z0 состояние процесса х [t] может принять значение из конечного множества состояний X={ ξ β }, т.е. х[t] равно одному из ξ β в любой момент времени; 2. Вероятность перейти в состояние ξ β в любой момент t, при условии, ξ β1

что в момент t – 1 реализовалось состояние

, зависит только от состоя-

ния ξ β1 и не зависит от предшествующих состояний. Такая случайная последовательность называется конечной марковской цепью. Она дискретна как по времени, так и по состояниям. Переход конечной марковской цепи из состояния в момент времени t – 1 в сосотояние в момент времени t полностью описывается переходной матрицей. Матрица образована условными вероятностями, но, в отличии от рассмотренных ранее условных вероятностей, в этой отсутствуют входы и выходы, а значит каждое состояние зависит только от предыдущего состояния. Матрица имеет размер |X|*|X|. Ее строки занумерованы предшествующими состояниями, а столбцы – последующими. В каждой строке записаны вероятности перехода во все возможные последующие состояния из ξ1β , и значит, сумма всех элементов строки равна единице. ∑ξβ P[t-1, t] ξβ, ξ’β = 1 . (1.54) Такая матрица называется стохастической (табл. 1.29). Таблица 1.29 Переходная матрица неоднородной марковской цепи X

ξ1 ,…….….……., ξ β ,…………..., ξΒ

Если все переходные матрицы совпадают при любом t ∈ Z, т.е. P[t-1,t] ≡ P, t0 ∈ Z , то такая марковская цепь называется однородной.

(1.55)

1.4. Представление технологического процесса в виде вероятностного автомата В реальных условиях многостадийного производства реализация технологического процесса не дает стопроцентную гарантию получения продукции строго заданного качества. Это объясняется влиянием значительного качества технологических величин, часть из которых может не регламентироваться стандартами. Кроме того, сложно выдержать слишком «узкие» допустимые режимы обработки при учёте погрешностей приборов. То есть, если технология представлена в виде конечных автоматов, то использование любой технологической цепочки, образованной сочетанием строго определенных элементов алфавитов входов и состояний в большинстве случаев не обеспечивает гарантированное попадание в заданные элементы алфавитов выходных величин. Чтобы учесть данную ситуацию необходимо использовать для описания вероятностные автоматы. Предварительное исследование технологического процесса позволяет проанализировать законы распределения факторов сквозной технологии и определить безусловные вероятности, с которыми каждое из состояний ξ β k ( k = 1,..., K ) , встречается в реальном производстве, и, следовательно, обычно используется. Данные вероятности можно анализировать с помощью гистограмм или диапазонной оценки для отдельных факторов и входных величии, а также и для их совместного появления. Для отдельного элемента X i можно создать табл. 1.32. Таблица 1.32 Вероятности реализации элементов алфавита i-го фактора

1

X

ξ11

P< ξ1ξ1 >,….,P< ξ1ξ β >,…….,P< ξ1 ξ Β >

Xi

a i1

…

a iji

…

aiJ i

. . .

…………………………………………… …………………………………………… ……………………………………………

P ( ai )

Pa i1

…

Pa iji

…

Pa iJ i

ξ β1 . .

ξΒ1

1

P< ξ ξ

1 β 1 >,…..,P<

1

1

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

ξ ξ β >,…….,P< ξ ξ Β > 1 β

1 β

…………………………………………… …………………………………………… …………………………………………… P< ξ Βξ1 >,…,P< ξ Βξ β >,…….,P< ξ Βξ Β > 1

1

1

35

36

Поскольку реализация конкретной технологии не обеспечивает строгое получение конечных свойств определенного качества (т.е. не позволяет получить единственное сочетание алфавитов выходов), то необходимо для каждой технологической цепочки описать свой вероятностный автомат. Описание функционирования вероятностного конечного автомата можно трактовать так, что на любом k-м переделе для каждой пары  ξ  задается совместное условное распределение вероятностей ,σ  β ( k −1 ) α ( k )  новых состояний и выходов. Т. к. внутренний алфавит (алфавит технологических факторов) и выходной алфавит конечны, то имеем пару дискретных случайных величин, которая должна быть задана своим совместным законом распределения. Число таких распределений на каждом агрегате или переделе  . Закон совместного распредеравно числу возможных пар  ξ β ,σ  ( k −1 ) α ( k )  ления можно представить в виде табл. 1.33.

<ξ β

1. Pβ

<ξ β

2. 0 ≤ Pβ( k ) ( k −1)

yk Pβ

<ξ β( k −1 ) ,σ α k >

P1

k

<ξ β( k −1 ) ,σ α k >

... Pγ

k

τγk

...

τ Γk

<ξ β( k −1 ) ,σ α k >

ξ1 k M ξβ k M ξΒ k

<ξ β( k −1 ) ,σ α k >

Pβ k M

<ξ β( k −1 ) ,σ α k >

PΒ

,σ α > k Pβ 1 ( k −1 ) (k) <ξ β ,σ α > k PΒ 1 ( k −1 ) (k)

... ...

<ξ β

,σ α > k Pβγ ( k − 1 ) (k) <ξ β ,σ α > k PΒγ ( k − 1 ) (k)

... ...

∑

(k)

∑

ξ β ∈ X k τ γ ∈Yk k k

≤1 ;

<ξ β( k −1 ) ,σ α k >

Pβγ

(k )

<ξ β

,σ α > k PβΓ ( k −1 ) (k) <ξ β ,σ α > k PΒΓ ( k −1 ) (k )

(1.70) =1 .

( k −1 ) (k)

,σ α > k

;

(1.72) (1.73)

,σ α > k

=1 .

(1.74)

,σ α > k

=

≤1 ;

∑

(1.75) <ξ β

ξ β ∈X k k <ξ β ,σ α > ( k −1 ) k =1 ∑ Pγ ( k ) τ γ ∈Yk k

<ξ β( k − 1 ) ,σ α k >

При этом должны выполняться требования: <ξ β( k −1 ) ,σ α k >

(k )

<ξ β

2. Pγ

Pβγ

k

0 ≤ Pβγ

( k −1 ) (k )

<ξ β( k −1 ) ,σ α k >

1. 0 ≤ Pγ

<ξ β ,σ α > <ξ β ,σ α > <ξ β ,σ α > k k k P11 ( k −1 ) ... P1γ ( k − 1 ) ... P1Γ ( k −1 ) (k) (k) (k ) <ξ β

τ γ ∈Yk k

( k −1 ) (k )

Pβγ

( k −1 ) (k )

,σ α > k

;

.

(1.76)

(1.77)

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

xk P1 k M

Pβγ

≤1 ;

<ξ β

Pβ

<ξ β

∑

и на вход передела или агрегата поступают входы σ α k . Аналогично для выходов:

k

...

, σα k >

=

(технологических режимов) при условии, что был реализован режим ξ β k −1

3. τ 1k

ξ β ∈X k k

,σ α > k

Т.е. эти вероятности задают вероятности появления состояний ξ β k

<ξ β( k −1 ) ,σ α k >

... PΓ

∑

3.

Таблица 1.33 Совместный закон распределения состояний и выходов на k-ом переделе

Pγ

( k −1 ) (k )

(k )

<ξ β( k −1 ) >

= Pβγ

(k)

для всех σ α k ∈ Vu .

(1.78)

Если выходной сигнал вероятностного конечного автомата определяется детерминировано (пример с затратами), т.е. не участвует в совместном законе распределения, то используется Y-детерминированный вероятностный конечный автомат. Y-детерминированный автомат можно использовать на переделах (агрегатах), после которых уровень выходных свойств не оценивается. Таким образом, для каждого варианта сочетаний алфавитов состояний, полученных до предыдущего агрегата ( ξ β ) (автономного (k )

Y-детерминированного вероятностного конечного автомата) можно задать (1.71)

вероятность Pβ< β k −1 > . Такое описание переходов (такой автомат) можно k

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

Для состояний и выходов верны следующие соотношения:

37

38

1. На любом переделе (агрегате) состояние процесса xk может принять значение из конечного множества состояний X k = { ξ β } , т.е. xk равно (k ) одному из ξ β на любой стадии обработки продукции. (k) 2. Вероятность перехода в состояние ξ β на k-м агрегате при условии, (k) что на k-1-м агрегате реализовалось состояние ξ β , зависит только от ( k −1 ) состояния ξ β и не зависит от предыдущих переделов. ( k −1 ) Такая последовательность называется конечной Марковской цепью. Она дискретна как по агрегатам, так и по состояниям (технологическим факторам). Переход конечной Марковской цепи из состояния агрегата k-1 в состояние агрегата k можно описать переходной матрицей:     [ k − 1, k ]  ξ β ( k )   P [ k − 1, k ] =  Pξ[ k − 1, k ] ,ξ = P   ξ β( k − 1 )   β ( k − 1 ) β ( k )     . (1.79) ξ β( k −1 ) ∈ X k −1 , ξ β( k ) ∈ X k Строки матрицы занумерованы предыдущими состояниями, а столбцы – последующими (табл. 1.34). Таблица 1.34 Переходная таблица из агрегата k - 1 в агрегат k X Х1 ξ'1(k-1) .

ξ1(k) ……………………………..… ξβ(k) ……………..……….. ξB(k) P[k-1,k]

1

ξ1 ξ1

………………P[k-1,k]

1

ξ1 ξ β

………….… P[k-1,k]

1

ξ1 ξ B 1

.

………………………………….……………………………….

.

P[k-1,k]ξ' β

ξ'β(k-1) . . .

ξ'B(k-1)

[k-1,k] ξ ………………..…P

1

1

ξβ ξβ

………………P[k-1,k]

1

ξβ ξ B

……………………………………………. P[k-1,k]ξ' B ξ 1 …………..…P[k-1,k]

1

ξB ξβ

…………….…P[k-1,k]

1

ξB ξ B

В реальных условиях данный подход можно использовать при определениии затрат на производство. Уровень свойств в большинстве случаев является величиной случайной или, по крайней мере, не является строго детерминированной. Следовательно, можно для каждого режима задать вероятности получения того или иного уровня свойств, т.е. вероятности реализации различных сочетаний алфавитов выходных свойств. В итоге информацию можно представить в виде табл. 1.35. 39

40

Каждая строка табл. 1.35 представляет собой отдельную реализацию технологии (технологическую цепочку). Зная распределение вероятностей выходных свойств можно выделить такие сочетания алфавитов входных величин и состояний (технологических параметров), которые обеспечивают максимальный уровень требуемых свойств. Для этого выбирается сочетание алфавитов выходных величин, отвечающих требованиям стандартов. Например, после реализации технологии обработки на k + 1 агрегатах, сочетание S + = c( k +1 )1 j1 ...c( k +1 )r( k +1 ) jr

k +1

...c( k +1 )Rk +1 jR

k +1

.

(1.80)

Необходимо подобрать технологическую цепочку (набор сочетаний алфавитов входных величин и состояний), обеспечивающую максимальную вероятность попадания в S+. Для этой цели можно использовать критерий связи технологии и свойств, основанный на принципах теории информации [11,12]. Технологическая цепочка, имеющая максимальное значение критерия связи, может быть выбрана в качестве оптимальной технологии. Если максимальное значение критерия достигается при объединении нескольких технологических цепочек, описанных в табл. 1.35, то их комбинация может использоваться как оптимальное технологическое пространство.

2. Дискретные пространственные модели В этом разделе приведены разнообразные пространственные структуры, образованные из клеток без памяти, взаимосвязанных некоторым регулярным образом. Их «динамика» трактуется как поведение относительно дискретного пространства S = Zud или Z d той или иной размерности d ≥ 1 . Опишем элементарные клетки (рис. 2.1) [13]. Клетка без памяти, или линейная комбинационная цепь, не совершает эволюций во времени и пространстве или относительно какого бы то ни было аргумента. Она не является динамической системой в полном смысле этого слова, а представляет собой «чистый преобразователь вход-выход». Ее вектор входа U ∈ K l и вектор выхода Y ∈ K m связаны линейным преобразованием, определяемым матрицей над некоторым числовым полем K: (2.1) Y = L ⋅U . так что клетка без памяти – функциональная система. U L

Y

L

U Ψ H

Y x Φ

L

a

b

Рис. 2.1. Клетки без памяти (а) и с памятью (b)

Следует подчеркнуть, что клетка без памяти «вне времени и пространства» является идеализацией: она может представлять достаточно богатую пространственно-временную структуру, но временными задержками в (2.1) пренебрегаем, а пространственная структура «зашивается» в матрицу L. Клетка с памятью, или обычная линейная стационарная дискретновременная динамическая система, описывается уравнениями состояний, входов и выходов, где x ∈ K n - вектор состояния, y ∈ K m – вектор выхода, u ∈ K l – вектор входа: x(t ) = Φx(t − 1) + Ψu (t ), x(0) = x0 , (2.2) y (t ) = Hx (t ) + Gu (t ), t ∈ T = Z 0 = {0,1, 2,...}. Она сложнее клетки без памяти в том отношении, что хотя ее пространственная структура «зашита» в матрицы уравнений (2.2), временными 41

42

задержками полностью не пренебрегаем – считая лишь, что все они кратны одной, принимаемой за единичную, и известным приемом сводим их к ней, а описание динамики – к уравнениям (2.2); при этом переменными состояния считаем входные сигналы элементов задержки. В [14,15] подробно описано «зашивание» пространственной структуры системы в матрицы уравнений (2.2) в предположении, что переменными состояниями считаются выходные сигналы элементов задержки; при этом уравнения (2.2) принимают альтернативную форму (второе уравнение – тоже): x(t + 1) = Φx(t ) + Ψu (t ), (2.3) являющуюся традиционной, или x(t ) = Φx(t − 1) + Ψu (t − 1); (2.4) наоборот, (2.2) можно записать

x( t + 1) = Фx( t ) +Ψ u( t + 1 ) = A( 0 )x( t ) + B( 1 )u( t + 1 ), y( t ) = Hx( t ) = C( 0 )x( t )

(2.5) (для дальнейшего удобства – в несколько иных обозначениях, G опущено).

2.1. Одномерные однонаправленные линейные итеративные цепи Каждая из одномерных однонаправленных линейных итеративных цепей представляет собой бесконечную вправо цепочку клеток без памяти (рис. 2.2) .

 x( s )   x( s − 1)  s ∈ Z . 1  y ( s)  = L  u ( s )  ,    

(2.6)

Разбивая матрицу L на блоки, получаем уравнения состояний и выходов одномерной однонаправленной линейной итеративной цепи: x( s) = Φx( s − 1) + Ψu ( s), x(0) = x0 , y (s ) = Hx( s − 1) + Gu ( s), s ∈ Z1 . (2.7) Эти уравнения формально идентичны уравнениям стационарной линейной дискретно-временной системы (2.2), с заменой в последних времени t на пространственную переменную s, или, в операторной форме, – с заменой оператора ξ временного сдвига на оператор z пространственного сдвига. Аргументная каузальность, априорная для временной системы, для пространственной определяется тем, что постулирован выбор одного из двух возможных направлений на пространственной оси (в следующем примере это уже не предполагается). Содержательные интерпретации рассмотренных цепей очевидны. Методы их исследования полностью заимствуются из хорошо разработанной теории дискретно-временных систем [16]. Одномерные однонаправленные цепи – класс моделей не менее богатый, чем класс временных систем, при том, что только лишь последние являются объектом изучения в классической теории управления. То же касается каждого из приводимых ниже примеров, а в совокупности этим подчеркивается широта класса дискретно-аргументных моделей.

2.2. Одномерные двунаправленные линейные итеративные цепи U(1) X0 0

1

U(S)

X(1)

.... Y(1)

X(S - 1)

S

X(S)

Каждая из одномерных двунаправленных линейных итеративных цепей представляет собой (потенциально) бесконечную в обе стороны цепочку клеток без памяти (рис. 2.3).

...

Y(S) U(S)

U(S-1)

U(S+1)

Рис. 2.2. Одномерная однонаправленная линейная итеративная цепь X(S-1) S-1

Клеткам присваиваются номера s ∈ Z0 . Каждая клетка с номером

s ∈ Z1 = {1, 2, ...} имеет внешние вход u ( s) ∈ K l и выход y ( s) ∈ K m

Y(S-1)

клетки с номером s – 1) и выход x( s) ∈ K n (вход клетки с номером s + 1). Клетка с номером 0 (краевая) имеет внутренний выход х0. Клетки идентичны (т.е. цепь пространственно однородна) и в соответствии с (2.1) каждая описывается уравнением 43

S+1

X(S+1)

X(S)

X(S-2)

и внутренние (по отношению к цепи как к целому) вход x( s − 1) ∈ K n (выход

S

Y(S)

Y(S+1)

Рис. 2.3. Одномерная двунаправленная линейная итеративная цепь 1-го типа

44

…

Клеткам присвоены номера s ∈ Z = {..., -1, 0, 1, ...} . В отличие от однонаправленной цепи, каждая клетка s имеет два внутренних входа x(s – 1) и x(s + 1), тогда как ее внутренний выход x(s) подается как на клетку s + 1, так и на клетку s – 1. Это отличие особенно наглядно проявляется при сравнении шаблонов соседства однонаправленной и двунаправленной цепей (рис. 2.4). s s б) a) s–1 s+1 s–1

.

.

так что цепь II типа получается как частный случай цепи I типа при специальном задании матриц Φ1, Φ2, Ψ.

U(S)

S–1

+1

X2(S+1) Y(S)

Двунаправленность определяет аргументную некаузальность цепи, что соответствует классу «систем ближайшего соседа». Обычно такие цепи рассматриваются на конечном отрезке, например [–N, N]: краевые клетки – N, N имеют внутренние выходы x(–N) и x(N). Клетки идентичны (цепь пространственно однородна), и в соответствии с (2.6) каждая описывается уравнением

 x( s − 1)  x( s )    .  y( s ) = L  x( s + 1 ) , s ∈ Z    u( s ) 

(2.8)

Разбивая матрицу L на блоки, получаем уравнение цепи x( s) = Φ1 x( s − 1) + Φ 2 x( s + 1) + Ψu (s ),

(2.9) y (s ) = H1 x (s − 1) + H 2 x ( s + 1) + Gu ( s), s ∈ Z . В дальнейшем основное внимание уделяем уравнению динамики. Описанную цепь относим к цепи I типа (рис. 2.5) (в отличие от цепи II типа, каждая клетка S которой имеет два внутренних выхода x1(s) и x2(s), подаваемых на клетки s + 1 и s – 1 соответственно):  x1 (s )   x1 ( s − 1)   x (s )  = L  x ( s + 1)  , s ∈ Z (2.10)  2   2   y ( s)   u (s )  или x2 ( s ) = Φ 21 x1 ( s − 1) + Φ 22 x2 ( s + 1) + Ψ 2 u (s ), s ∈ Z

… S

S X2(S)

Рис. 2.4. Шаблоны соседства Однонаправленной (а) и двунаправленной (б) цепей

x1 (s ) = Φ11 x1 (s − 1) + Φ12 x2 ( s + 1) + Ψ1u ( s),

X1(S)

X1(S – 1)

…

Рис. 2.5. Одномерная двунаправленная линейная итеративная цепь II типа

Подобное разбиение вектора состояния на составляющие (в данном случае – составляющая «вправо» x1 и составляющая «влево» x2) встретится нам и в дальнейшем. Операторная запись уравнений двунаправленной цепи использует операторы пространственного сдвига «назад» Z и «вперед» Z-1, удовлетворяющих соотношению ZZ-1 = 1, так что модель аргументнонекаузальна, как уже отмечалось выше. Содержательная интерпретация двунаправленных итеративных цепей, как и в однонаправленных, относится к таким областям как обработка сигналов, кодирование и декодирование информации, построение вычислительных систем [1]. Большое внимание моделям (2.9) уделяется в вычислительной математике, где они интерпретируются как широко известный класс разностных схем [17].

2.3. Двумерные однонаправленные линейные итеративные цепи Каждая из двумерных однонаправленных линейных итеративных цепей представляет собой бесконечную вправо и вверх таблицу клеток без памяти (рис. 2.6). Клетки занумерованы парами чисел ( s1 ,s2 ) ∈ Z0 . В отличие от од2

,

(2.11)

положим здесь x( s) = ( x1T ( s), xT2 ( s ) ) . Тогда (2.11) можно записать в виде T

Φ 0 0 Φ12  Ψ1  x(s) =  11  x(s −1) +   x(s +1) + Ψ  u(s) , Φ 0 0 Φ 22   21    2

(2.12)

45

номерной цепи, каждая клетка имеет два внутренних входа x( s1 − 1, s2 ) и x( s1 , s2 − 1) , тогда как ее внутренний выход x( s1 , s2 ) подается на две клетки

( s1 + 1, s2 ) и ( s1 , s2 + 1) (соответствующий шаблон соседства представлен на рис. 2.7).

46

S2

x(0,s2)

x(s1,s2) x(s1–1,s2)

(0,s2)

Этой цепи I типа соответствует цепь II типа (рис. 2.8), в которой кажn дая клетка ( s1, s2 ) имеет два внутренних выхода x1( s1, s2 ) ∈ R 1 n и x2 (s1, s2 ) ∈ R 2 , подаваемых на клетки ( s1 + 1, s2 ) и ( s1, s2 + 1) соответственно:  x1 (s1 , s2 )   x1 (s1 −1, s2 )   x (s , s ) = L  x (s , s +1) ,(s , s ) ∈ Z 2 , (2.15) 1  2 1 2   2 1 2  1 2  y(s1 , s2 )   u(s1 , s2 ) 

y(s1,s2) (s1,s2)

…

u(s1,s2)

x(s1,s2–1)

x(0,1) (0,1) x(1,0) (0,0)

(1,0)

так что x = ( x1T , x2T )Τ ∈ R n , n = n1 + n2 , x1 ( s1 , s2 ) = Φ11 x1 ( s1 − 1, s2 ) + Φ12 x2 ( s1 , s2 − 1) + Ψ1u ( s1 , s2 ), x2 ( s1 , s2 ) = Φ 21 x1 ( s1 − 1, s2 ) + Φ 22 x2 ( s1 , s2 − 1) + Ψ 2 u ( s1 , s2 ),

x(s1,0)

…

(s1,0) S1

Рис. 2.6. Двумерная однонаправленная линейная итеративная цепь I типа

(s1 – 1, s2)

.

(s1,s2) (s1, s2 – 1)

Рис. 2.7. Шаблон соседства двумерной одноправленной цепи

Клетки ( s1 , 0) и (0, s2 ) (краевые) имеют внутренние выходы x0 ( s1 , 0) и x0 (0, s2 ) . Как и ранее, клетки идентичны (цепь пространственная и однородная) и каждая описывается уравнением  x (s1 − 1, s2 )   x ( s1 , s2 )    2 (2.13)  y ( s , s )  = L  x (s1 , s2 − 1)  , s1 , s2 ∈ Z1  1 2   u (s1 , s2 )  так, что уравнение цепи: x(s1 , s2 ) = Φ1 x(s1 −1, s2 ) + Φ2 x(s1 , s2 −1) + Ψ1u(s1 , s2 ), y(s1 , s2 ) = H1 x(s1 −1, s2 ) + H2 x(s1 , s2 − 1) + Ψ2u(s1 , s2 ),

(2.14)

y ( s1 , s2 ) = H 1 x1 ( s1 − 1, s2 ) + H 2 x2 ( s1 , s2 − 1) + Gu ( s1 , s2 ). (2.16) – частный случай (2.14) при специальном выборе матриц Φ1, Φ2, Ψ. Состояние двумерной цепи II типа оказывается разложенным на «горизонтальную» x1 и «вертикальную» x2 составляющие. Двумерная однонаправленная цепь аргументно-каузальна в соответствии с постулированным выбором одного из множества направлений на плоскости (именно направление «северо-восток»). Это соответствует классу «многомерных систем». Операторная запись уравнения цепи использует операторы горизонтального z1 и вертикального z2 пространственных сдвигов, причем z1 z2 = z2 z1 . Модель (2.14) является частным случаем модели x ( s1 , s 2 ) = Φ 1 x ( s1 − 1, s 2 ) + Φ 2 x ( s1 , s 2 − 1) + Φ 3 x ( s1 − 1, s 2 − 1) + (2.17) + Ψ u ( s1 , s 2 ) при Φ 3 = 0. Покажем, что это уравнение (2.17) может быть, в свою очередь, приведено к виду (2.14). Для этого приведем (2.17) к (2.16). Положим x1 ( s1 , s2 ) = x ( s1 , s 2 ), (2.18) x 2 ( s1 , s2 ) = Φ 2 x ( s1 , s2 ) + Φ 3 x ( s1 − 1, s2 ). Тогда непосредственно из (2.17) получаем x1 ( s1 , s2 ) = Φ1 x1 ( s1 − 1, s2 ) + x2 ( s1 , s2 − 1) + Ψu ( s1 , s2 ) ,

Подставим в выражение для x2 ( s1 , s2 ) полученное выражение для x1 (s1 , s2 ) : +Ψ u ( s1 , s2 ) ] = (Φ 3 + Φ 2 Φ1 ) x1 ( s1 − 1, s2 ) + Φ 2 x2 ( s1 , s2 − 1) + Φ 2 Ψ u ( s1 , s2 ).

47

(2.19)

что соответствует первому уравнению (2.16) при Φ11 = Φ1 , Φ12 = Ι, Ψ1 = Ψ . x2 ( s1 , s2 ) = Φ 3 x1 ( s1 − 1, s2 ) + Φ 2 [ Φ1 x1 ( s1 − 1, s2 ) + x2 ( s1 , s2 − 1) +

где ( s1, s2 ) ∈ Z12 = Z1 × Z1 .

(2.16)

48

(2.20)

x1 ( s1 + 1, s2 ) = Φ 11 x1 ( s1 , s 2 ) + Φ 12 x 2 ( s1 , s 2 ) + Ψ 1u ( s1 , s 2 ), x2(s1,s2)

(0,s2)

x1(0,s2)

x2(s1-1,s2)

…. (0,1)

x 2 ( s1 , s 2 + 1) = Φ 21 x1 ( s1 , s 2 ) + Φ 22 x 2 ( s1 , s 2 ) + Ψ 2 u ( s1 , s 2 );

y(s1,s2)

в) обобщенная модель Форназини-Маркезини x(s1 +1, s2 +1) = Φ1x(s1 +1, s2 ) +Φ2 x(s1, s2 +1) +Ψ1u(s1 +1, s2 ) +Ψ2u(s1, s2 +1) . (s1,s2)

x1(s1,s2)

Они могут быть преобразованы одна в другую подобно тому, как это сделано выше для рассматриваемых здесь моделей. С другой стороны, последняя из указанных моделей может быть записана в виде (2.14) с несущественными отличиями: x(s1 , s2 ) = Φ1 x(s1, s2 −1) + Φ2 x(s1 −1, s2 ) + Ψ1u(s1 , s2 −1) + Ψ2u(s1 −1, s2 ) . (2.22)

x2(s1,s2-1)

u(s1,s2) x1(0,1)

Полную двумерную модель запишем в виде: x2(1,0) (0,0)

(1,0)

….

x ( s1 + 1, s 2 + 1) = A (0, 0) x ( s1 , s 2 ) + A (1, 0) x ( s1 + 1, s 2 ) +

x2(s1,0)

+ A (0,1) x ( s1 , s 2 + 1) + B (0, 0) u ( s1 , s 2 ) + B (1, 0) u ( s1 + 1, s 2 ) +

(2.23)

+ B (0,1) u ( s1 , s 2 + 1) + B (1,1) u ( s1 + 1, s 2 + 1).

(s1,0)

Рис. 2.8. Двумерная однонаправленная линейная итеративная цепь II типа

Это соответствует второму уравнению (2.16) при Φ 21 = Φ3 + Φ 2 Φ1 , Φ 22 = Φ 2 , Ψ 2 = Φ 2 Ψ , так что (2.17) приведено к (2.16). Теперь положим Τ x ( s1 , s2 ) =  x1T ( s1 , s2 ) x2T ( s1 , s2 ) и запишем: Φ1 0  x ( s1 , s 2 ) =  x ( s 1 − 1, s 2 ) + Φ + Φ Φ 0   3 2 1 Ι  0  Ψ  +  (2.21)  x ( s 1 , s 2 − 1) +  Ψ Ψ  u ( s 1 , s 2 ) = 0 Φ  2   2  = Φ 1 x ( s 1 − 1, s 2 ) + Φ 2 x ( s 1 , s 2 − 1) + Ψ u ( s 1 , s 2 ). Таким образом, все три формы (2.14), (2.16), (2.17) модели двумерной однонаправленной цепи могут быть преобразованы одна в другую. В литературе широко изучались альтернативные варианты этих моделей. Oни известны под следующими названиями [1]: а) модель Хабиби-Аттази, Форназини-Маркезини x(s1 +1, s2 +1) = Φ0 x(s1, s2 ) +Φ1 x(s1 +1, s2 ) +Φ2 x(s1, s2 +1) +Ψu(s1, s2 ) ;

Эта модель включает все рассматривавшиеся до сих пор двумерные модели и характеризуется наличием члена B(1,1)u( s1 + 1, s2 + 1) , отсутствовавшего в моделях Хабиби-Аттази, Форназини-Маркезини (и их модификациях), Россера и др. Этот член впервые был в модели мультиразмерных систем в [18,19], что в отражено [1,20,21]. Основную двумерную модель (2.11) запишем в виде: x ( s1 + 1, s 2 + 1) = A (1, 0) x ( s1 + 1, s 2 ) + A (0,1) x ( s1 , s 2 + 1) + + B (1,1)u ( s1 + 1, s 2 + 1).

Именно благодаря наличию члена B (1,1)u( s1 + 1, s2 + 1) полная двумерная модель (а значит, и все ее частные случаи) может быть приведена к основной.

2.4. Двумерные двунаправленные линейные итеративные цепи Каждая из двумерных двунаправленных линейных итеративных цепей представляет собой (потенциально) бесконечную во все стороны таблицу клеток без памяти (рис. 2.9).

б) модель Россера 49

(2.24)

50

 x( s 1 − 1 , s 2 )   x( s , s − 1 )  1 2    x ( s1 , s 2 )    ,( s 1 , s 2 ) ∈ Z 2 . = L x( s + 1 , s ) 1 2  y ( s , s )    1 2   x( s 1 , s 2 + 1 )   u ( s 1 , s 2 ) 

x(s1,s2+1) (s1,s2+1) x(s1-1, s2) x(s1+1,s2) x(s1,s2) (s1-1, s2)

u(s1,s2)

(s1,s2)

После разбиения матрицы L на блоки, уравнения динамики такой цепи записываются в виде

(s1+1, s2)

x ( s1 , s 2 ) = Φ 1 x ( s1 − 1, s 2 ) + Φ 2 x ( s1 , s 2 − 1) +

y(s1,s2)

+ Φ 3 x ( s1 + 1, s 2 ) + Φ 4 x ( s1 , s 2 + 1) + Ψ u ( s1 , s 2 ),

x(s1,s2-1)

( s1 , s 2 ∈ Z ) .

Рис. 2.9. Двумерная двунаправленная линейная итеративная цепь I типа

Клетки занумерованы парами чисел ( s1, s2 ) ∈ Z 2 = Z × Z . В отличие от однонаправленной цепи каждая клетка ( s1 , s2 ) имеет четыре входа от четырех ближайших соседей, а ее выход подается на четырех ближайших соседей. Этим и объясняется закрепившееся за такими системами название «системы ближайшего соседа». Особенно наглядно сказанное иллюстрируется шаблоном соседства (рис. 2.10).

Описанной цепи I типа соответствует цепь второго типа (рис. 2.11), отличающаяся тем, что каждая клетка имеет не один, а четыре выхода, подаваемых каждый на одну из ближайших соседних клеток. (s1,s2+1) x4(s1,s2+1)

x2(s1,s2)

y(s1,s2) x1(s1-1,s2) (s1-1,s2)

(s1,s2+1)

.

(2.26)

2

(s1, s2-1)

(s1–1,s2)

(2.25)

S

x3(s1,s2)

x1(s1,s2) (s1,s2)

x3(s1+1,s2)

(s1+1,s2)

u(s1,s2)

(s1+1,s2)

x2(s1,s2-1)

(s1,s2–1)

x4(s1,s2) (s1,s2-1)

Рис. 2.10. Шаблон соседства двумерной двунаправленной цепи Рис. 2.11. Двумерная двунаправленная линейная итеративная цепь II типа

Двунаправленность в горизонтальных и вертикальных направлениях определяет аргументную некаузальность цепи. Обычно такие цепи рассматриваются на конечном участке плоскости, например . Краевые клетки имеют только внутренние вхо[− N 1, N 1 ] × [− N 2 , N 2 ] ды. Как и в предыдущих пунктах, клетки идентичны, каждая описывается уравнением 51

52

x1 (s1 , s2 ) = Φ1 x(s1 − 1, s2 ) + Φ2 x( s1 , s2 − 1) + Φ3 x(s1 , s2 + 1) + Ψu (s1 , s2 ), (2.28) в котором s1 ∈ Z 0 , s 2 ∈ Z . Так как здесь Z 2 Z 2− 1 = 1 , то цепь аргументно некаузальна. Вторая цепь описывается уравнением x1 ( s1 , s 2 ) = Φ 1 x ( s1 − 1, s 2 ) + Φ 2 x ( s1 − 1, s 2 − 1) + (2.29) + Φ 3 x ( s1 − 1, s 2 + 1) + Ψ u ( s1 , s 2 ),

Схема такой цепи проще, а уравнения записываются в виде: x1 (s1 , s2 ) = Ф11x1 (s1 −1, s2 ) + Ф12 x2 (s1 , s2 −1) + Ф13 x3 (s1 +1, s2 ) +

+ Ф14 x4 (s1 , s2 +1) + Ψ1u(s1 , s2 ); x2 (s1 , s2 ) = Ф21x1 (s1 −1, s2 ) + Ф22 x2 (s1 , s2 −1) + Ф23 x3 (s1 +1, s2 ) + + Ф24 x4 (s1 , s2 +1) + Ψ2u(s1 , s2 ); x3 (s1 , s2 ) = Ф31x1 (s1 −1, s2 ) + Ф32 x2 (s1 , s2 −1) + Ф33x3 (s1 +1, s2 ) +

(2.27)

+ Ф34 x4 (s1 , s2 +1) + Ψ3u(s1 , s2 ); x4 (s1 , s2 ) = Ф41x1 (s1 −1, s2 ) + Ф42 x2 (s1 , s2 −1) + + Ф43 x3 (s1 +1, s2 ) + Ф44 x4 (s1 , s2 +1) + Ψ4u(s1 , s2 ). Можно непосредственно убедиться, что цепь II типа является частным случаем цепи I типа при специальном выборе матрицы Φ1 , ..., Φ 4 , Ψ . Операторная запись уравнений двумерных двунаправленных цепей используют операторы горизонтальных (влево и вправо) и вертикальных (вверх и вниз) −1 −1 сдвигов Z 1 , Z 1 , Z 2 , Z 2 , удовлетворяющих соотношениям Z 1 Z 1− 1 =

в котором снова s1 ∈ Z 0 , s2 ∈ Z . Так как здесь нет соотношения типа δ n =1 , то система аргументно-каузальна. Стоит отметить, что в данном случае имеется специальное соотношение Z 1 Z 2 ⋅ Z 1 Z 2− 1 = Z 2 . Соотношения подобного типа не встречались в рассмотренных ниже примерах.

. .

= 1,Z 2 Z 2−1 = 1 , что еще раз говорит об аргументной некаузальности этой модели. Содержательную интерпретацию рассмотренных цепей можно найти в областях цифровой обработки изображений (случайных двумерных полей) и численного решения дифференциальных уравнений с частными производными. Именно в последней области хорошо известен шаблон «крест» (рис. 2.10). На этом основана «модель ближайшего соседа» [1, 22] для цифровой обработки изображений, обладающих определенными преимуществами перед другими. В [22] рассмотрен скалярный (n = l = 1) и изотропный, ( Φ1 ,..., Φ 4 = 1 ) вариант модели (2.26); подробно изучен скалярный вариант, для которого φ 1 = φ 2 = β , φ 3 = φ 4 = γ , и отмечено, что изотропный случай β = γ представляет особый интерес; указаны и интерпретации, связанные со случайными блужданиями в пространстве, а также со статической физикой.

.

.

. .

а)

б)

Рис. 2.12. Шаблоны соседства двумерных полуторанаправленных цепей

Двумерные полуторанаправленные цепи рассматривались в связи с задачами обработки изображений под названием «полукаузальных» процессоров. Как показано выше, по классификации, принятой в данной работе, они могут быть как аргументно-каузальными, так и аргументнонекаузальными. Шаблоны, изображенные на рис. 2.12, как и встречавшиеся ранее (а также рассмотренные в следующем пункте), хорошо известны в теории разностных схем.

2.6. Другие двумерные цепи

2.5. Двумерные полуторанаправленные линейные итеративные цепи Ограничимся двумя вариантами двумерных полуторанаправленных линейных итеративных цепей, для простоты представленных только шаблонами соседства (рис. 2.12). Первая из них описывается уравнением (частный случай (2.26)) 53

Не выписывая здесь соответствующих уравнений, можно провести сравнительный анализ шаблонов соседства некоторых цепей (рис. 2.13). На рис. 2.13а показан шаблон цепи (2.22).Такое описание двумерной однонаправленной цепи избыточно, так как сводится к (2.19), т.е. шаблону, показанному на рис. 2.7, хотя последний и является частным случаем шаблона рис. 2.13а. Другие частные случаи также показаны на рис. 2.13 в, с. Соот54

вествующие им цепи как частные случаи могут быть приведены к (2.19). Все эти цепи аргументно-каузальны. Альтернативные варианты шаблонов показаны на рис. 2.13d, f (каждому соответствуют и свои частные случаи).

.

. a

. .

b

c

. . d

e

g

2.7. Трехмерные однонаправленные линейные итеративные цепи

f

.

Полную трехмерную модель запишем в виде

.

. h

между операторами. Результаты подобного анализа допускают дальнейшее развитие. Все рассмотренные выше двумерные цепи были связаны с ортогональной (прямоугольной, в частности – квадратной) дискретизацией плоскости. В [22] обращено внимание на возможность использования других способов дискретизации, в частности – гексагональной, и предложены соответствующие «гексагональные модели». Ортогональная и гексагональная дискретизация сравниваются на рис. 2.13j, k. Некоторые шаблоны гексогональных цепей показаны на рис. 2.13. К ним также применима классификация на аргументно-каузальные и аргументно-некаузальные.

x ( s1 + 1, s 2 + 1, s 3 + 1) = A (0 , 0 , 0 ) x ( s1 , s 2 , s 3 ) + + A (1, 0 , 0 ) x ( s1 + 1, s 2 , s 3 ) + A ( 0 , 1, 0 ) x ( s 1 , s 2 + 1, s 3 ) + + A ( 0 , 0 , 1) x ( s 1 , s 2 , s 3 + 1) + A (1,1, 0 ) x ( s 1 + 1, s 2 + 1, s 3 ) +

.

i

+ A (1, 0 , 1) x ( s 1 + 1, s 2 , s 3 + 1) + A ( 0 ,1,1) x ( s1 , s 2 + 1, s 3 + 1) +

.

+ B ( 0 , 0 , 0 ) u ( s1 , s 2 , s 3 ) + B (1, 0 , 0 ) u ( s 1 + 1, s 2 , s 3 ) + + B ( 0 , 1, 0 ) u ( s 1 , s 2 + 1, s 3 ) + B ( 0 , 0 , 1) u ( s 1 , s 2 , s 3 + 1) +

(2.30)

+ B (1, 1, 0 ) u ( s 1 + 1, s 2 + 1, s 3 ) + B (1, 0 ,1) u ( s1 + 1, s 2 , s 3 + 1) + + B ( 0 , 1, 1) u ( s 1 , s 2 + 1, s 3 + 1) + B (1,1, 1) u ( s1 + 1, s 2 + 1, s 3 + 1).

j

k

Основную трехмерную модель запишем в виде x( s1 + 1, s2 + 1, s3 + 1) = A(1,1, 0) x( s1 + 1, s2 + 1, s3 ) + A(1, 0,1) x ( s1 + 1, s2 , s3 + 1) +

l

Рис. 2.13. Шаблоны соседства различных цепей

Все соответствующие цепи аргументно-каузальны, однонаправлены, меняется лишь направление, соответсвенно «юго-восток», «юго-запад», «северо-запад» (цепи (2.22) отвечает направление «северо-восток»). Цепь с шаблоном, показанным на рис. 2.13, может быть приведена к (2.22) подобно тому, как (2.22) приведена к (2.19). Она аргументно-некаузальна, хотя среди ее частных случаев (а она, по существу, охватывает все рассмотренные выше цепи) есть как каузальные, так и некаузальные. Иногда имеет значение то, что она может быть представлена как некоторая комбинация четырех каузальных цепей. На рис. 2.13 h показаны шаблоны еще двух цепей, первая из них каузальна, а вторая – нет. Из проведенного краткого сравнения можно сделать следующие выводы: цепь некаузальна всякий раз, когда на шаблоне встречается два взаимнопротивоположных направления: цепь избыточна (подобно (2.22)), когда среди направлений есть линейно-зависимые. Иными словами, избыточность связана с наличием специальных тождеств 55

(2.31) + A(0,1,1) x (s1 , s2 + 1, s3 + 1) + B (1,1,1)u( s1 + 1, s2 + 1, s3 + 1). Замечания, сделанные ранее о двумерных моделях, справедливы и здесь. Впервые предложенная в [18,19] в общем случае основная трехмерная модель описывалась уравнением x(s1 , s2 , s3 ) = Φ1 x(s1 −1, s2 , s3 ) + Φ2 x(s1 , s2 −1, s3 ) + (2.32) + Φ3 x(s1 , s2 , s3 −1) + Ψu(s1 , s2 , s3 ).

2.8. Многомерные однонаправленные линейные итеративные цепи Пусть s ∈ Z , s = ( s1 , ..., sd ), s j ∈ Z , j = 1, ..., d ; d

β ∈ B = {0,1}d

–

множество всех d-мерных двоичных векторов с координатами 0 или 1: β – 56

число единиц в векторе β (вес Хемминга), 0 ≤ β ≤ d , 1 = ( 1, ..., 1) ,

1 =d . Неявную полную d-мерную модель определим уравнением

∑ { A ( β ) x ( s + β ) + B ( β ) u ( s + β )} = 0 ,

(2.33)

β ∈B

а явную полную d-мерную модель – уравнением x ( s + 1) = ∑ { A β x s + β + B β u s + β + B (1)u ( s + 1)}.

( ) (

β ∈ B \{1}

)

( ) (

)

(2.34)

Эта модель включает все рассматривавшиеся до сих пор модели мультиразмерностных систем и характеризуется наличием члена B(1)u ( s + 1) , отсутствовавшего в ранее рассмотренных общих моделях. Этот член впервые был введен в модели мультиразмерностных систем [18,19], где рассматривалась (и была развита в [20] до основной модели дискретно-аргументных систем) основная d-мерная модель, записанная в виде

2.9. Использование итеративных цепей для описания технологического процесса Выделенная из табл. 1.35 технологическая цепочка, обеспечивающая оптимальный уровень выходных свойств и описанная с помощью конечного и вероятностного конечного автоматов, может быть использована для управления технологическим процессом с использованием итеративной цепи. Получив оптимальные диапазоны, состоящие из нескольких сочетаний алфавитов состояний (технологических величин), можно оценить вид образованного пространства (рис. 2.14). a) 1 элемент алфавита (сочетание)

x2 3

2

d

x ( s ) = ∑Φ j x(s1,..., s j −1 , s j −1, s j +1,..., sd ) + Ψu ( s ) .

1

(2.35)

j =1

В принятых здесь обозначениях основная d-мерная модель запишется в виде: (2.36) x( s + 1) = ∑ A(β )x( s + β ) + B(1)u ( s + 1) .

1

2

3

x1

1

2

3

x1

3

x1

б) прямоугольник

x2

β = d −1

Основные двумерная и трехмерная модели (2.24) и (2.31) являются частными случаями (2.36) соответственно при d = 2 и d = 3. Приведение полной d-мерной модели к основной можно выполнить, развивая методику, подробно изложенную выше для случаев d = 2 и d = 3. Тем самым и все рассматривавшиеся в литературе частные случаи полной модели могут быть приведены к основной, так что основная модель является в этом смысле наиболее общей, универсальной моделью мультиразмерностных систем. Ключевым для возможности таких преобразований представляется следующее обстоятельство: правая часть основной модели содержит только члены «максимального веса» относительно состояний β = d − 1 и отно-

3

2

1

в) сложная комбинация алфавитов

x2

1 = d ; все члены полной модели меньшего веса

3

0 ≤ β ≤ d при указанных преобразованиях «впитываются» членами «мак-

2

сительно входа

G H

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

1

1

2

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

58

В случае, если оптимальное подпространство состоит из одного сочетания алфавитов состояний (рис. 2.14а), можно сформировать новый алфавит каждого фактора, равный трем (например, А, Б, В. В этом случае Бi – будет соответствовать оптимальному диапазону, который обеспечивает максимальный уровень свойств). При объединении нескольких сочетаний алфавитов в прямоугольный параллелепипед (рис. 2.14б) новый алфавит представляет собой объединение (дизъюнкцию) исходных алфавитов. Например, для рис. 2.14б выходы можно описать для факторов xi: Б1 = {1 ∪ 2}, В1 = {3}, А1 = {Ø}, для фактора x2: А2 = {Ø}, Б2 = {1 ∪ 2 ∪ 3}, B2 = {Ø}. В итоге оптимальное сочетание выходов (требуемое продолжение) будет Б1, Б2. Для варианта, при котором формируется из сочетаний алфавитов пространство неправильной формы (рис. 2.14 в), необходимо указать объединение отдельных прямоугольных параллелепипедов, аналогичных варианту б. В этом случае формируется пространство как объединение параллелепипедов, каждый из которых идентифицируется отдельной буквой (G, H, F…). В рассмотренном примере (рис. 2.14в) можно сформировать: G = {11 , 21 , 32}, H = {21, 31, 22} (индекс – номер фактора). В итоге пространство можно представить как объединение: G ∪ H ∪ {21, 12}. Полученную технологию можно представить в виде итеративной цепи (рис. 2.15).

V11 V1l1 V1L1

1

V21 V2l2 V2L2 x11

x21

x1m1

x 2m2

. .

2

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

Vk1 ...ν kLk

xk1 ...xkM k

y k1... ykRk

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

. .

ik −1

M ik −1 = ∑ m j ,

x2M 2

x1M 1

x( k −1)1...x( k −1) M k −1

(2.38)

j =1

где mj – количество внутренних выходов j-й клетки.

Z 11 Z1g1 Z1G1 y11 y1r1 y1R1

Z21 Z2g2 Z2G2 y21 y2r2 y 2R2

Рис. 2.15. Представление технологии в виде итеративной цепи

Описать цепь можно с помощью уравнений: x(k ) = Фx (k - 1) +ψ v (k ), (2.37) y (k ) = Hx(k - 1) + Gv(k ). Данные уравнения применимы, если используется линейная итеративная цепь. В более общем случае (при учете взаимного влияния величин) необходимо перейти к нелинейным итеративным цепям. 59

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

60

a)

б)

xkik −1M ik −1

xkik−1M ik −1

ik

xkik M ik

xkik−1 ( M ik−1 +1) ik

. .

xkik M ik в)

xkik −1 ( M ik−2 +1) . .

ik

xkik M ik

xkik −1M ik −1

г)

xkik ( M ik−1 +1)

xkik −1 ( M ik−2 +1) . .

xkik−1M ik −1

ik

. .

xkik M ik

Рис. 2.17. Варианты внутренних входов и выходов клеток внутренней итеративной цепи Таблица 1.37 Таблица переходов клетки внутренней итеративной цепи

xkik −1 ( M ik −2 +1) ,....., xkik −1M ik −1

xkik ( M ik −1 +1) ,....., xkik M ik

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

62

вопрос о выборе нового, рационального сочетания алфавитов факторов, реализация которых должна быть осуществлена на последующих переделах. Для этого вновь рассматривается работа вероятностного конечного автомата и выбирается продолжение, обеспечивающие максимальную вероятность получения требуемых свойств для данного вида продукции. В случае невозможности получения требуемого уровня свойств рассматривается вариант перевода производимой продукции в другой вид продукции или в брак до завершения технологического процесса. Таким образом, в таблице переходов внутренней цепи (табл. 1.37) выходами могут служить элементы алфавитов факторов, описываемых в данной клетке (см. рис. 2.14а). (Для приведенного варианта – это сочетания: x*1 = 1; x*2 = 2 ). При выборе оптимального продолжения, состоящего из комбинации алфавитов (рис. 2.14б), в качестве выходов указывается новый алфавит, представляющий собой объединение (дизъюнкцию) алфавитов. (Для примера: x*1 = {1 ∪ 2}, x*2 = {1 ∪ 2 ∪ 3} или {Б1 ∪ Б2}). Для варианта 2.14в необходимо указать объединение отдельных прямоугольников, аналогичных варианту 2.14б. (Для приведенного варианта, как отмечалось выше, G ∪ H ∪ {21, 12}).

3. Дискретные пространственно-временные модели В этом разделе продолжаем пользоваться клеточной интерпретацией дискретно-аргументных систем. Теперь в качестве элементарных клеток используем клетки с памятью. Рассмотренные здесь системы в обзоре [1] именуются «линейными последовательностно-клеточными машинами».

3.1. Одномерные однонаправленные линейные итеративные сети Одномерные однонаправленные линейные итерактивные цепи отличаются от соответствующих цепей (подраздел 2.1) тем, что представляют собой бесконечную вправо цепочку клеток с памятью (с этим отличием сохраняется схема рис. 3.1, представленная на рис. 2.14).

u[t,s-1]

u[t,s]

x[t,s-1]

x[t,s-2] ξ[t,s-1]

y[t,s-1]

ξ[t,s]

x[t,s]

y[t,s]

Рис. 3.1. Одномерная однонаправленная линейная итеративная сеть

Сигналы в такой сети зависят уже не только от номера клеток s ∈ Z 0 , но и от времени t ∈ Z 0 . Обозначим состояние клетки s в момент t через ξ (t , s ) и используем ее описание (2.2). Кроме внешних входа u(t , s) и выхода y (t, s) , она имеет в соответствии с подразделом 2.1 внутренние вход x(t , s − 1) и выход x (t , s ) . Пусть клетки идентичны, так что сеть аргументно-инвариантна: время-стационарна (как (2.2)) и пространственно однородна (как (2.6)). Сочетая (2.2) и (2.7), запишем вместо (2.6) уравнения 63

64

 x ( t , s − 1)  ξ ( t , s ) = Φ ξ ( t − 1, s ) + Ψ  ,  u (t , s )   x (t , s )   x (t , s − 1)   y ( t , s )  = H ξ (t − 1, s ) + G  u ( t , s )  , t , s ∈ Z 0 .    

(3.1)

x ( t , s ) = H 1ξ ( t − 1, s ) + G11 x ( t , s − 1) + G12 u ( t , s ),

(3.2)

После разбиения матриц Ψ, H, G на блоки получаем уравнения одномерной однонаправленной линейной итеративной сети: ξ ( t , s ) = Φ ξ ( t − 1, s ) + Ψ 1 x ( t , s − 1) + Ψ 2 u ( t , s ), y ( t , s ) = H 2 ξ ( t − 1, s ) + G 21 x ( t , s − 1) + G 22 u ( t , s ). Эти уравнения решаются при начальных условиях ξ (0, s ) = ξ 0 ( s ), s ∈ Z 0 и краевых условиях x(t ,0) = x0 (t ), t ∈ Z 0 . Таким образом, описание одномерной однонаправленной сети формально вполне идентично описанию двумерной двунаправленной цепи II типа (2.16), но сеть эволюционирует не относительно двумерного пространственного аргумента (как цепь), а относительно одномерного пространственного и временного аргументов. Вектор состояния сети составлен из ξ (t , s ) - и x(t , s) -векторов состояний обеих эволюций. Операторная запись уравнений сети использует операторы временного ξ и пространственного z сдвигов, причем сеть аргументно-каузальна. Она имеет следующую особенность: состояние каждой клетки в момент t зависит не только от ее состояния в момент t – 1, но и от состояния соседней клетки в тот же момент t. Шаблон пространственно-временного соседства сети соответствует показанному на рис. 2.7.

(T, S) (T,S - 1) (T – 1, S) Рис. 3.2. Шаблон соседства одномерной однонаправленной сети

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

Если сеть описывается с помощью двоичного алфавита, то для представления нелинейных одномерных однонаправленных итеративных сетей можно использовать многочлены Жегалкина. Например, состояние клетки s в момент времени t определяется по формуле: ξ [t , s] = Ф0 ⊕ Ф1 ⊗ ξ [t − 1, s] ⊕ Ф2 ⊗ x[t , s − 1] ⊕ Ф3 ⊗ u[t , s] ⊕ Ф12 ⊗ ⊗ ξ [t − 1, s] ⊗ x[t , s − 1] ⊕ Ф13 ⊗ ξ [t −1, s] ⊗ u[t , s] ⊕ Ф23 ⊗ x[t , s −1] ⊗ (3.3) ⊗ u[t , s] ⊕ Ф123 ⊗ ξ [t −1, s] ⊗ x[t , s − 1] ⊗ u[t , s]. В случаях, если алфавиты входов, состояний и выходов не являются двоичными, процесс получения уравнений состояний и выходов для нелинейной итеративной сети становится более трудоемким. Одним из вариантов описания функционирования таких сетей являются представление функций переходов и выходов в табличной форме. Занеся в таблицу полную комбинацию возможных исходов, можно полностью описать работу одномерной однонаправленной нелинейной итеративной сети. Работа одномерной однонаправленной сети В каждый момент времени t = 0, 1, 2 … дискретного времени каждая клетка s сети находится в определенном состоянии ξ[t, s] и способна воспринимать на внешнем входном канале сигнал u[t, s], а на внутреннем входном канале сигнал x[t, s – 1]. На эти сигналы клетки реагируют переходом в [t + 1] такте в новое состояние ξ[t + 1, s] и выдачей некоторого внешнего выходного сигнала y[t + 1, s] и внутреннего выходного сигнала x[t + 1, s], который является внутренним входом для клетки s + 1. В общем случае одномерная однонаправленная сеть имеет несколько внутренних и внешних входов, состояний, внешних и внутренних выходов. Вектор, составленный из скалярных внешних входов: u[t , s ] = (u1[t , s ],..., xn [t , s ]), где m – число внешних входов клетки s + 1; x[t , s ] = ( x1[t , s ],..., xn [t , s ]), где n – число внутренних входов клетки s + 1; ξ [t , s ] = (ξ1[t , s],..., ξ l [t , s]), где l – число внутренних состояний клетки s; y[t , s] = ( y1[t , s ],..., yk [t , s ]), где k – число внешних выходов клетки s. Алфавиты входов, состояний и выходов могут иметь различную значность. aiji – составляющие алфавитов внешних входов; ji = 1,..., J i , J i – значность алфавита i-го внешнего входа; i = 1, …, m – номер входов; brjr – составляющие алфавитов внутренних входов и выходов; jr = 1, ..., J r , J r – значность алфавита r-го внутреннего входа или выхода; 66

r = 1, …, n – номера внутренних входов или выходов. c pj p – составляющие алфавитов состояний. j p = 1, ..., J p , J p – значность алфавита p-го состояния. р = 1, …, l – номера состояний; d qiq – составляющие алфавитов внешних выходов; jq = 1, ..., J q , J q – значность алфавита q-го внешнего входа; q = 1, …, k – номера внешних входов. В этом случае алфавиты представляются собой прямые произведения более простых алфавитов. Таким образом: m

U = {a11 ,.....,a1J1 }×{a21 ,....., a2J2 }×...×{am1 ,...,amJm } = {σα ,α = 1,....,A; A = ∏Ji }, i=1

σ α – вариант сочетания алфавитов внешних входов u[t,s] клетки s; n

X = {b11 ,..., b1 J1 } × {b21 ,..., b2 J 2 } × ... × {bi1 ,..., biJ i } = {χ β , β = 1,..., B; B = ∏ J r }, r =1

xβ – вариант сочетания алфавитов внутренних выходов x[t,s] клетки s; l

Ξ = {c11 ,..., c1J1 } × {c21 ,..., c2 J 2 } × ... × {ci1 ,..., ciJ i } = {ψ υ ,υ = 1,..., N ; N = ∏ J p }, p =1

ψ υ – вариант сочетания алфавитов состояний ξ [t , s ] клетки s. l

Y = {d11 ,..., d1J1 } × {d 21 ,..., d 2 J 2 } × ... × {di1 ,..., diJ i } = {τ γ , γ = 1,..., Γ; Γ = ∏ J q }, q =1

τ γ – вариант сочетания алфавитов внешних выходов y[t,s] клетки s. Переходы и выходы одномерной однонаправленной нелинейной итеративной сети представлены в табл. 3.1.

67

68

3.2. Одномерные двунаправленные итеративные сети

3.3. Одномерные линейные клеточные автоматы

Уравнения (2.2) и (2.9) запишем для одномерной двунаправленной итерактивной сети (рис. 3.3) в виде: ξ (t , s) = Фξ (t − 1,s) + Ψ1 x (t , s − 1) + Ψ 2 x(t , s + 1) + Ψ 3u(t , s ), x(t , s) = H1ξ (t − 1, s ) + G11 x(t , s − 1) + G12 x (t , s + 1) + G13u (t , s ), (3.4)

Одномерные линейные клеточные автоматы – это частный случай подробно рассмотренных в подглаве 3.4 классических (двумерных) клеточных автоматов Дж. фон Неймана. Шаблон соседства такого автомата представлен на рис. 3.4. Одномерные клеточные автоматы описываются уравнением x ( t , s ) = Φ 1 x ( t − 1, s ) + Φ 2 x ( t − 1, s − 1 ) + (3.5) + Φ 3 x ( t − 1, s + 1 ) + Ψ u ( t , s ) и формально идентичны двумерным полуторанаправленным цепям (2.29).

y(t,s) = H 2ξ (t − 1, s ) + G21 x(t , s − 1) + G22 x (t , s + 1) + G23u (t , s ). Это описание формально вполне идентично описанию двумерной полуторонаправленной цепи (2.28), шаблон пространственно-временного соседства соответствует показанному на рис. 2.12а. Для операторов ξ, Z, Z-1, участвующих в описании сети, выполняется тождество ZZ −1 = 1 , так что сеть аргументно-некаузальна. Это следует подчеркнуть, так как можно было ожидать, что такая сеть как пространственно-временная система автоматически каузальна благодаря наличию временной составляющей аргумента.

t

(t;c)

t ξ (t + 1, s)

y(t, s)

x1 (t, s − 1) ξ (t, s − 1)

x1 (t, s ) ξ (t , s )

ξ (t, s + 1) x 2 (t , s + 1)

x 2 (t , s )

(t-1;c-1)

(t-1;c)

(t-1;c+1)

c

u (t , s )

Рис. 3.4. Шаблон соседства одномерного клеточного автомата

Как и последние, одномерные автоматы аргументно-некаузальны, причем операторы ξ, ξZ, ξZ-1 удовлетворяет специальному соотношению

ξ (t − 1, s)

ξZ ⋅ ξZ −1 = ξ 2 .

3.4. Клеточные конечные автоматы

Рис. 3.3. Одномерная двунаправленная итеративная сеть

Сочетая (2.2) с (2.14), (2.26) и т.д., получим описания двумерных сетей как обобщений одномерных. Они не приводятся здесь в связи c громоздкостью и тем, что не имеют каких-либо явных особенностей (на уровне описания) по сравнению с уже рассмотренными сетями. 69

Клеточные автоматы введены Дж. фон Нейманом [23] в связи с задачами автоматического конструирования и самовоспроизведения. Последние могут быть отнесены к задачам управления клеточными автоматами, но не 70

при помощи внешних управляющих воздействий, как в классической теории управления сосредоточенными системами, а при помощи начальных распределений состояний клеток клеточного пространства. Это определяет некоторые своеобразные аспекты теории клеточных автоматов, мотивирует постановку указанных задач в классе линейных клеточных автоматов и поиск решений в рамках алгебраических методов пространства состояний. Клеточные автоматы эволюционируют в дискретном времени t ∈Τ = Ζ = {0, 1, 2...} и дискретном двумерном клеточном пространстве 0

с = (с1, с2)∈ С = ZхZ, Z = {…, -1, 0, 1, …}. =

=

(C 1 , C 2 ) – координаты,

С – клеточное пространство, Z = {…, -1, 0, 1, …} – множество любых целых чисел. Клеточное пространство представляется в виде плоскости–решетки (рис. 3.5). t – временная ось

С1

С2

Рис. 3.5. Клеточное пространство клеточного конечного автомата

В каждый момент времени t каждая клетка С может находиться в определенном состоянии: x(t; С ) = x(t; С1 , С2 ) ∈ X – внутренний алфавит. Если х – конечное множество, то клеточный автомат – конечный, но может таким и не быть. Распределение состояний всех клеток в некоторый момент t называется конфигурацией и обозначается: ξ(t) = {x(t; C1, C2), (C1, C2) ∈ C} = ξ . (3.6) Пара (C1, C2) пробегает все клеточное пространство. 71

Соответственно, данная конфигурация – ξ, предшествующая – ξ'. Как для автомата задается начальное состояние, так и для клеточного конечного автомата (ККА) задается начальная конфигурация, т.е. конфигурация в какой-то начальный момент времени: ξ0 = ξ(t0). (3.7) Каждая клетка с может находиться в некотором состоянии х(с); распределение состояний клеток клеточного пространства называется конфигурацией и обозначается через ξ = {х ( с ), с ∈ С }. Если х(t;c) = х(t; с1,с2) – состояние клетки с в момент времени t, то предположенное в [23] правило переходов запишется в виде локального управления состояний х(t ;c1, c2) = ϕ (x(t – 1;c1 ,c2), x(t – 1; c1 – 1, c2), (3.8) x(t – 1; c1, c2 – 1), x(t – 1; c1 + 1, c2), x(t – 1; c1, c2 + 1). Здесь ϕ – переходная функция состояний клеточного автомата. Она не зависит в явном виде от времени t и пространства с, так что клеточный автомат является стационарной и однородной динамической системой. Это обосновано в [23]. Кроме того, в (3.8) в явном виде не входят внешние управляющие воздействия, так что клеточный автомат – автономная система. Задается входное воздействие в каждый момент времени в каждой входной точке С: v(t; C) ∈ V – входной алфавит. В этом случае для определения ККА в дискретном времени и пространстве задается переходная функция состояний клеточного автомата: x(t; С1, C2) = ϕ(x(t – 1; С1, C2); х(t – 1; С1 – 1, C2); х(t – l; С1 + 1, C2); x(t – 1;C1; C2 – 1); x(t – 1; C1; C2 + 1); v(t; C1; C2) , (3.9) где v(t; С) ∈ V – входное воздействие в каждый момент времени t в каждой точке С (V – входной алфавит). Состояние в данный момент времени t в клетке С зависит от состояния в этой клетке в предыдущий момент времени и, креме того, от состояния в предыдущий момент в других клетках клеточного пространства. Графически характер перехода можно изобразить на рис. 3.6. Выделенные точки образуют «шаблон соседства» данного ККА: Р(С) = Р(С1, C2) = ={(С1, C2); (С1 – 1, C2); (С1, C2 – 1); (С1 + 1, C2); (С1, C2 + 1)}. (3.10) Ввиду стационарности и однородности достаточно задать шаблон Р клеточного автомата: Р = {(0, 0); (–1,0); (0,–1); (1,0); (0, 1)}. (3.11) Можно представить: Р(С) = С + Р, (3.12) где Р(С) – сдвиг шаблона Р (из клетки 0) в клетку С.

72

(t; C1, C2) (клетка С в момент t)

(t – 1; C1, C2 – 1)

(t – 1; C1 + 1, C2) (t – 1; C) = (t –1; C1, C2)

(t – 1; C1 – 1, C2)

(t – 1; C1, C2 + 1)

Рис. 3.6. Шаблон соседства клеточного конечного автомата

Для полного определения поведения клеточного автомата в дискретном пространстве – времени дополнительно к (3.8) должна быть задана начальная конфигурация ξ0 = {x0 (c), c ∈ C} в некоторый начальный момент времени t0 ∈ T, так что ξ0 = {x ( t0; c) = x0(c), c ∈ C}. Таким образом, клеточный автомат может рассматриваться как шестерка . Предполагается [23], что набор возможных состояний клеток включает специальное состояние ε, называемое состоянием покоя и определяемое тем свойством, что если некоторая клетка с и все ее соседи (клетки из Р(с)) в момент времени t – 1 находятся в состоянии покоя, то клетка с в момент времени t также находится в состоянии покоя. Кроме того, предполагается, что в каждый момент времени все клетки, за исключением конечного числа, находятся в состоянии покоя. Для выполнения последнего условия в силу конечности шаблона Р достаточно предположить, что в начальный момент времени все клетки, за исключением конечного числа, находятся в состоянии покоя. Клетки, которые не находятся в состоянии покоя, называются возбужденными. Подмножества клеточного пространства будем называть массивами (клеток). Если массив А ⊂ С состоит из конечного числа клеток, то их количество A будем называть также площадью этого массива и обозначать через S (A) [24]. Для шаблона Р клеточного автомата положим, что Р(0) = {0}, P(1) = P Р(2) = Р[Р(1) (3.13) – массив клеток, соседних с клетками шаблона Р в силу этого шаблона, и вообще для любого r∈Z0 P(r) = P[P(r – 1)] (3.14) 73

– массив клеток, соседних с клетками массива P(r – 1) в силу шаблона Р. Массив Р(r) назовем диском радиуса r. Ясно, что Р(r)⊃Р(r – l) и при r → ∞ диск Р(r) стремится покрыть все клеточное пространство С. При каждом r∈Z0 диск Р(r) состоит из конечного числа клеток; его площадь S(P(r)) = S(r) = 2r(r + l) + l . (3.15) Конфигурация ξ = {x(с), с∈С} является финитной, если x(с) = ε, за исключением конечного числа клеток. Наименьшее r∈Z0 такое, что x(c) = ε для с∉Р(r), назовем радиусом r (ξ) финитной конфигурации ξ, а Р(r (ξ)) = Р(ξ) – ее диск-носителем. Ясно, что может быть х(с) = ε и для некоторых с∈Р(ξ). Любой массив C(ξ)⊂Р(ξ), такой, что х(с) = ε для с∉С(ξ), будем называть носителем финитной конфигурации ξ. Финитную конфигурацию ξ можно записать в виде ξ = {x(c), с∈С(ξ)}. Совокупность значений х(с), с∈С(ξ) будем называть составом конфигурации ξ. Для любой клетки а∈С через zа можно обозначить сдвиг клеточного пространства С на a: za(c) = c + a ; (3.16) для любой клетки с∈С; za(A) = A + a ; (3.17) для любого массива А⊂С. Сдвиги в клеточном пространстве индуцируют сдвиги финитных конфигураций по правилу: (t, t0) = Ф(t, t – 1)Ф(t – 1, t – 2) ... Ф(t0 + 1, t0), t > t0 . (3.18) Конфигурацию клеточного автомата в момент времени t∈Z0 обозначается ξ(t) = {x(t,с), с∈С}. В силу ранее сказанного конфигурации ξ(t) финитны; их радиусы обозначаем через r (t), диск-носители – через P(t), носители – через C(t). Начальным моментом времени t0 клеточного автомата считается радиус r(ξ0 ) его начальной конфигурации ξ0. Его эволюция рассматривается во времени для t ≥ t0. Начальная конфигурация запишется в виде: ξ0 = ξ ( t0 ) = { x( t0 ;c ),c ∈ C0 = C( t0 ) = C( ξ0 ) ⊂ P( t0 )} . (3.19) Тем самым, в принятых обозначениях, r(t) = t, P(r(t)) = P(t) для t ≥ t0, так что обозначения дисков и диск-носителей конфигураций клеточного автомата согласуются.

3.5. Линейные клеточные автоматы. Переход к ассоциированному уравнению Ограничимся рассмотрением линейных клеточных автоматов (ЛКА), для которых при любых t∈T и с∈С x(t: c)∈Kn (К – некоторое числовое поле, п – натуральное число – размерность вектора состояния каждой клетки ЛКА, определяющая размерность ЛКА), а уравнение (3.8) записывается в виде: 74

x(t; c1, с2) = Ф1x(t – 1; с2, с2) + Ф2x(t – 1; c1 – 1, c2) + + Ф3х(t – l; c1, с2 – 1) + A4x(t-1; c1+1; c2) + A5x(t-1; c1; c2+1), (3.20) где Ф1 ,…, Ф5 – постоянные (не зависящие от t и с) n×n-матрицы над полем К. Роль состояния покоя играет нулевой вектор 0∈Kn. Пусть клетки клеточного пространства упорядочены (занумерованы) так, что клетка (0, 0) имеет номер 0, клетки диска P(t) имеют номера, не превосходящие S(t) – 1 = 2t(t + 1), (3.21) клетки массива P(t)|P(t – 1) имеют номера от S(t – 1) = 2t (t – l) + 1 до S(t) – l= 2t(t + 1) (3.22) при любом t∈Z0. Методы нумерации клеточного пространства играют немаловажную роль, особенно в плане перенесения результатов данной работы на случай клеточных автоматов с другими возможными шаблонами [23-25]. Использование некоторых принципов нумерации при исследовании различных классов систем с дискретным аргументом представлено, например, в [18,20,26]. Нумерующая функция, осуществляющая взаимно-однозначное отображение клеточного пространства C = Z×Z на множество Z0, определяется при помощи алгоритма (здесь k = k(с) ∈Z0 – номер клетки с∈ С) k = k(c) = 2 ||с|| (||с|| + 1) + 1 + 4[с] + {с} , (3.23)  c1 − 1, где с =  .  c2

k − (ξ + 1) при α = 0, c2 (k ) =  (3.25) (ξ + 1) − n при a = 2. Клетка (0, 0) имеет номер 0; клетки шаблона Р – номера 1, 2, 3, 4 в том порядке, в котором они записаны выше. Дальнейшее упорядочение рекуррентно: в диске Р(t) первыми идут 2t(t – 1) + 1 клеток диска Р(t – 1)⊂Р(t) в том же порядке, что и в Р(t – 1). Последними идут четыре клетки (–t, 0), (0, –t), (t, 0), (0, t); оставшиеся 4(t – 1) клеток, образующие массив Р(t)\(Р(t – 1)∪{( –t, 0), (0, –t), (t, 0), (0, t)}), следуют за клетками диска Р(t – 1) группами по четыре клетки и представляют собой последние t – 1 групп по четыре клетки массива Р(t – 1)\Р(t – 2) (в том же порядке, что и в массиве Р(t – 1)\Р(t – 2)), причем в каждой группе к координатам клеток прибавляются соответственно координаты клеток {(0, 1), (–1, 0), (0, –1), (1, 0)}. С описанным упорядочением клеток согласован алгоритм конструирования матриц Ф(t,t – 1) из матриц Ф1, ..., Ф5, состоящий в выполнении следующих шагов: 1) матрица Ф(1, 0) строится в виде Ф(1, 0) = (Ф1тФ4тФ5тФ2тФзт]т; 2) матрица Ф(2, 0) имеет вид (выделена матрица Ф(1, 0)): с = (c1, c2) k(с)

 Ф1 Ф  4 Ф 5  Ф 2 Ф 3   0 Ф ( 2 ,1 ) =  0   0  0   0   0  0   0

Каждому k∈Z0 сопоставляется клетка с = с(k) = (с1(k), c2(k))∈ c (имеющая номер k при указанной выше нумерации) при помощи алгоритма: 1) находим наибольшее k = к(k), такое, что 2n(n – 1) + 1 ≤ k; 2) находим наибольшее ξ = ξ(k)∈{0, 1, …, n – 1}, такое, что 4ξ ≤ k – 2n(n – 1) – 1; 3) находим α=α(k)=k-2n(n-1)-1-4ξ; если k четно, то α∈{1, 3}; если k нечетно, то α∈{0, 2}; 4) если k четно, то −(ξ + 1) при α = 1, c2 (k ) =  и  ξ + 1 при a = 3,

5) если k нечетно, то

−(ξ + 1) − n при ξ = 1, c1 (k ) =   n − (ξ + 1) при ξ = 3;

(3.24)

с = (c1,c2): k(с):

−(ξ + 1) при α = 0, c1 (k ) =  и  ξ + 1 при α = 2, 75

76

Ф2 Ф1 0

Ф3 0 Ф1

Ф4 0 0

0 0 Ф3

0 0 0

Ф1 0 0

Ф5 0 0

Ф4 Ф2 0

0 Ф5 Ф3

Ф4 0 0

0 Ф5 0

0 0 Ф2

0

0

0

(0,0) 0

(-1,0) 1

Ф 5  ( 0 ,0 ) 0  ( − 1,0 ) 0  ( 0 ,−1 )  0  ( 1,0 ) Ф 1  ( 0 ,1 )  Ф 4  ( − 1,1 ) 0  ( − 1, − 1 )  0  ( 1, − 1 ) Ф 2  ( 1,1 )  0  ( − 2 ,0 )  0  ( 0 , −2 ) 0  ( 2 ,0 )  Ф3  ( 0 , 2 )

(0,-1) 2

(1,0) 3

0 1 2 3 4 5 6 7 8 9 10 11 12 (0,1) 4

(3.26)

сбоку и снизу выписаны клетки и их номера, при помощи которых нумеруются строки и столбцы матрицы; 3) матрица Ф(t, t – 1) для t ≥ 3 строится из крупных блоков I-VI по схеме

Ι  V   − − Ф( t − 1, t − 2 ) − −     ΙV  ΙΙ  ΙΙΙ V Ι        

а) блоки I и II составляют полученную на предыдущем шаге матрицу Ф(t – 1, t – 2) размера S(t – 1) п×S( t– 2) п; б) блок III размера (S(t) – S(t – 1))п×S(t – 2)п – нулевой; в) блок IV порядка (S(t – 1) – S(t –2)) п блочно-диагонален – на диагонали расположены матрицы Ф1; г) блок V получен симметричным отражением блока II относительно диагонали блоков I и IV с заменой индексов 2←→4, 3←→5 у матриц Ф2, Ф3, Ф4, Ф5; д) в верхнем правом углу последнего крупного блока VI размера (S(t)– S(t – 1)n×(S(t-1) – S(t – 2))п помещается средний блок А порядка 4n; е) на выходящей из верхнего левого угла крупного блока VI диагонали расположены средние блоки В порядка 4n (их t – 1); ж) на входящей в нижний правый угол крупного блока VI диагонали расположены средние блоки С порядка 4n (их t – 1). В пп. д), е), ж) использованы средние блоки

 0 0 0 Ф4  Ф3 0 0 0  Ф4 0 0 0  Ф 0 0 0  0 Ф 0 0 0 Ф 0 0  5 4 5      . (3.27) A= , B= , С=  0 Ф2 0 0   0 0 Ф5 0   0 0 Ф2 0         0 0 Ф3 0   0 0 0 Ф2   0 0 0 Ф3  Пусть X(t)∈KS(t)n – составной вектор, образованный записанными в столбец векторами x(t;с), c∈P(t) в установленном порядке клеток X(t) = [x(t; 0)тх(t; c1)т…x(t; cs(t)-1)т]т. (3.28) При этом вектор X (t 0 ) ∈ K s (t 0 )n включает подвектор Xo(t0; Co)∈KS(Co)n, составленный из векторов x0(c), с∈С0, начальной конфигурации ξ0 (кроме них в X(t0) входит нулевой вектор 0∈Кп на местах, отвечающих клеткам c∈P(t0)\C0) в установленном порядке. Ввиду линейности клеточного автома77

та связь между векторами X(t – 1) и X(t) линейна. Тем самым с уравнением (3.20) ассоциируется уравнение X(t) = Ф(t, t – 1)X(t – 1), t > t0 , (3.29) при начальном условии Х(t0) это уравнение линейной автономной нестационарной дискретно-временной динамической системы с переменными во времени размерностями векторов и матриц. Оно представляет пространственноглобальное описание данного ЛКА, исходно заданного локальным уравнением состояний (3.20). Переход от (3.20) к (3.29) может быть назван «упаковкой пространственной структуры» клеточного автомата (в векторы X(t) и матрицы Ф(t, t – 1) ассоциированного уравнения). Матрица Ф(t, t – 1) – блочная. Она составлена из n×n-блоков Ф1,…, Ф5 и нулевых. Ее блочные размеры S(t)×S(t – 1), полные размеры S(t)n×S(t – 1)n. Блочные строки матрицы Ф(t, t – 1) занумерованы номерами клеток массива P(t), блочные столбцы – номерами клеток массива P(t – 1) (в согласии с общей нумерацией клеток клеточного пространства). Решение уравнения (3.29) записывается в виде Х(t)=Ф(t,t0)X(t0),t ≥ t0, (3.30) где Ф (t0, t0) = I s (t 0 )n – единичная матрица порядка S(t0)n, Ф(t, t0) = Ф(t, t – 1)Ф(t – 1, t – 2) ... Ф(t0 + 1,t0), t > t0. (3.31) Матрица Ф(t, t0) имеет размеры S(t)n×S(t0)n. ЛКА более подробно можно характеризовать как кортеж . (3.32) Пусть заданы ξ* = {x*(с), с∈С(ξ*) = С*} и t*∈Z0 – «желаемая» конфигурация, которую требуется сконструировать при помощи заданного ЛКА, и время, за которое это требуется сделать. Данный ЛКА способен сконструировать конфигурацию ξ* за время t*, если в силу (3.20), (3.32) х(t0 + t*;с) = х*(с), с∈С*. (3.33) Ясно, что задача имеет смысл при t* > 0 и t0 + t* ≥ r(ξ*). В момент t0 – t* могут оказаться возбужденными и некоторые клетки с∉С*, а именно: клетки с∈Р(ξ*)\С*. О состояниях этих клеток, вообще говоря, никаких предположений не делается. Если же потребовать дополнительно, чтобы такие клетки оказались в состоянии покоя, то необходимо говорить о чистом конструировании конфигурации ξ* за время t* при помощи данного ЛКА. Наряду с вектором X0(t0, С0) вводится в рассмотрение вектор *

*

X(t0 + t*; c*)∈ K s(c ) n - подвектор составного вектора X(t0 + t*)∈ K s(t 0 + t )n , полученный из последнего исключением составляющих X(t0 + t*; с), с∈Р (t0 + t*) \ С* с сохранением установленного порядка оставшихся векторов x(t0 + t*; с), с∈С*. Пусть далее Ф(t0 + t*, t0; С*, С0) – матрица, полученная из матрицы (3.31) Ф(t0 + t*, t0) исключением блочных строк с номерами клеток с∈P(t0 + t*)\С* и блочных столбцов с номерами клеток с∈P(t0)\С0 с со78

хранением установленного порядка оставшихся блочных строк и столбцов. Эта матрица имеет размеры S(C*)n× S(C0) п. Тогда в силу (3.30) (3.34) X ( t0 + t*; C*) = Ф( t0 + t*,t0 ; C*, C0 )X 0 ( t0 , C0 ). С другой стороны, (3.33) можно записать в виде: Х(t0 + t*;С*) = Х*, (3.35) где X*∈Ks(c*)n – вектор, ассоциированный описанным выше способом с конфигурацией ξ*. Он может быть записан подробнее в виде Х*(r(ξ*); С*), а также, поскольку P(r(ξ*))⊂P(t0 + t*) в силу t0 + t*≥ r(ξ*), в виде Х*(t0 + t*; С*). Итак, способность заданного ЛКА сконструировать заданную конфигурацию ξ* за заданное время t* равносильна выполнению соотношения Ф(t0 + t*, t0 ; C*, C0 ) X 0 (t0 ; C0 ) = X *(t0 + t*; C*). (3.36) Пусть в (3.36) зафиксировано все, кроме состава конфигураций ξ0 и ξ*, т.е. для ЛКА зафиксированы Ф1, ..., Ф5, t0, а для конфигурации – их носители С0 и С*. Запишем (3.36) сокращенно в виде Ф0*Х0 = Х*. (3.37) Теперь алгебраические критерии разрешимости линейного уравнения (3.37) [27] доставляют критерии способности ЛКА к конструированию. ЛКА способен сконструировать конфигурацию ξ* за время t* (в том смысле, что найдется конфигурация, ассоциированный с которой вектор Х0 удовлетворяет (3.37)) тогда и только тогда, когда ассоциированный с конфигурацией ξ* вектор X* и матрица Ф0* удовлетворяют соотношению Ф0*(Ф0*)Х* = Х*, (3.38) где (Ф0*)+ – псевдообратная к матрице Ф0* [27]. ЛКА способен сконструировать любую конфигурацию ξ* с заданным носителем С* тогда и только тогда, когда rgФ0* = S(C*)n. (3.39) Ясно, что последний критерий имеет смысл лишь при S(C*)≤S(C0). В противном случае речь может идти лишь об оптимальном конструировании конфигураций при помощи ЛКА в смысле минимума среднеквадратического уклонения конструируемой конфигурации от желаемой, когда (3.33) заменяется на Σ Sc∈C*||x(t0 + t*;c) – x*(c)|| 2→ min, (3.40) где || … || – некоторая норма в Кп (например, обычная евклидова). Задача стирания конфигурации ξ0 за время t* является частным случаем задачи конструирования, когда требуется, чтобы x(t0 + t*; с) ≡ 0, с∈Р(t0 + t*). (3.41) В этом случае соотношение (3.36) запишется в виде (3.42) Ф( t0 + t*, t0 ; P( t0 + t*),C0 )X 0 ( t0 ; C0 ) = 0.

79

Составные векторы Х0, ассоциированные с конфигурациями ξ0, которые данный ЛКА способен стереть за время t, образуют ядро матрицы Ф (t0 + t*, t0; P(t0 + t*, С0) в пространстве Ks(Сo) n. В задаче чистого конструирования конфигурации ξ* к соотношению (3.36) добавляется соотношение (3.43) Ф( t0 + t*, t0 ; P( t0 + t*) / C0 )X 0 ( t0 ; C0 ) = 0. Эта задача разрешима, если множество решений задачи конструирования, если оно непусто, имеет непустое пересечение с ядром матрицы, фигурирующей в (3.43). Задача воспроизведения конфигурации ξ0 через время t∗ «в месте» а клеточного пространства является частным случаем задачи конструирования, когда требуется, чтобы ξ*= za(ξ0), т.е. ξ* = {х*(с) = x0(с – а), с∈С* = = za (С0)}. Условие (3.33) запишется в виде x(t0 + t*; c) = x0(c – α ), c∈ zα (C0). По-прежнему должно быть t0 + t* ≥ r( zα (ξ0)). В этом случае матрица Ф0*( α ) = Ф(t0 + t*, t0*, za (C0), C0) – квадратная, блочного размера S(C0)×S(С0). Вектор X* может отличаться от Х0 разве что порядком составляющих его векторов х0(с), с∈С0. Пусть I S (co )n ( a) – матрица, в которой S(C0) n×n-блоков – единичные, а остальные – нулевые, такая, что Х* = I(а)Х0. Тогда (3.37) запишется в виде Ф0*( α )Х0 = I( α )Х0 или [Ф0*( α ) – I( α )]Х0 = 0. (3.44) Таким образом, векторы Х0, отвечающие конфигурациям ξ0, которые данный ЛКА способен воспроизводить через время t* в месте а клеточного пространства, образуют ядро матрицы Ф0*( α ) – I( α ). ЛКА способен воспроизводить нетривиальные конфигурации тогда и только тогда, когда det[Ф(t0 + t*,t0; zα (C0),C0) – I( α )] = 0. (3.45) Состав таких конфигураций определяется решениями уравнения (3.44). Задача восстановления конфигурации ξ0 через время t* является частным случаем задачи воспроизведения, когда α = 0. Критерий способности данного ЛКА восстанавливать через время t∗ нетривиальные конфигурации ξ0 имеет вид det(Ф(t0 + t∗,t0;C0,С0) – I] = 0, (3.46) а состав таких конфигураций определяется решениями соответствующей однородной системы уравнений типа (3.44). Задача размножения конфигурации ξ0 за время t* в местах α 1, ..., α т клеточного пространства является частным случаем задачи конструирования, когда (3.20) записывается в виде x(t0 + t*; c) = x0(c – ai ), c∈zai (C0), I = 1, ..., m. (3.47) 80

При этом предполагается, что zai (С0 )∩ za j (С0) = φ

для любых

ί, j = 1, ..., m, i≠j, а под носителем С* желаемой конфигурации понимается U im=1 z ai (co ). Теперь одновременно должны выполняться т соотношений

типа (3.44) [Ф0*(ai ) – I(аi ) ]Х0 = 0, i = 1,..., т. (3.48) Данный ЛКА способен размножать указанным образом нетривиальные конфигурации ξ0 тогда и только тогда, когда элементы определяющих его матриц Ф1, …, Ф5 удовлетворяют одновременно т полиномиальным уравнениям det[Ф(t0 + t*, t0; zai (С0) ,С0) – I(ai )] = 0, t = 1, ..., m . (3.49) Проверка выполнения этого критерия может быть осуществлена, например, методами теории результантов [28]. Состав конфигураций, которые данный ЛКА способен размножать указанным образом, определяется пересечением ядер матриц Ф0*(аi ) – I(аi ), i = 1, ..., т.

3.6. Аналитическое представление ККА На выходе клетки ККА образуется выходной сигнал y(t; C) ∈ Y (Y – выходной алфавит клеточного конечного автомата). Образование выходного сигнала определяется функцией выходов, которая может задаваться в двух вариантах: а) ККА Мили: y(t; C1 ,C2 ) =ψ ( x(t − 1; C1 , C2 ), x(t −1; C1 −1,C2 ), x(t −1; C1 + 1,C2 ), x(t − 1; C1 , C2 − 1), x( t − 1; C1 , C2 + 1), ν ( t; C1 , C2 )

;

(3.50)

б) ККА Мура: y(t; С1, C2) = ψ~ (x(t); С1, C2). (3.51) Если функции переходов и выходов в явном виде не зависят от времени и пространства (в неявном – зависят), а единый шаблон Р путем сдвига определяет шаблон в каждой точке пространства, то ККА представляет собой стационарную (не зависит от t) и однородную (не зависит от пространства) систему или однородную структуру. Если отсутствует зависимость от входа, то ККА – автономная система. Именно в таком виде ККА были введены фон Нейманом как модели вычислительных устройств автоматического конструирования и самовоспроизведения. В случае конечных алфавитов ККА (как и конечных автоматов) может быть задан при помощи таблиц, однако их объем существенно больше, чем у конечного автомата за счет шаблона соседства (у конечного автомата шаб81

лон из одной точки, у ККА – из пяти). По этой причине практически невозможно представление ККА при помощи графов (т.к. здесь одно состояние зависит от пяти состояний, а не одного). Например, вершиной графа должно было бы считаться множество из пяти точек. Рассмотрим аналитическое представление клеточного конечного автомата. Ограничимся автономным ККА без выхода (т.е. сосредоточим внимание на функции перехода) с одномерным состоянием и двоичным внутренним алфавитом Х = {0, 1} и любым x(t ; c ) ∈ X (в момент t в точке с). В этом случае переходная функция имеет вид: x (t; c) = ϕ ( x (t − 1; c1 ; c2 ); x (t − 1; c1 − 1; c2 ); x (t − 1; c1 + 1; c2 ); (3.52) x (t − 1; c1 ; c2 − 1); x (t − 1; c1 ; c2 + 1)). Табличное представление такой функции должно содержать 25 строк (тогда как для конечного автомата было две строки (без входа)), так как используется двоичный внутренний алфавит и шаблон соседства содержит пять точек (табл. 3.2). В случае клеточного конечного автомата принято учитывать следующие ограничения. 1. Предполагается, что набор возможных состояний клеток включает специальное состояние 0, называемое состоянием покоя и определяемое тем свойством, что если некоторая клетка С и все ее соседи в момент времени t – 1 находятся в состоянии покоя, то клетка С в момент времени t также находятся в состоянии покоя. 2. Кроме того, предполагается, что в каждый момент времени все клетки, за исключением конечного числа, находятся в состоянии покоя. Для выполнения последнего условия, в силу конечности шаблона Р, достаточно предположить, что в начальный момент времени все клетки, за исключением конечного числа, находятся в состоянии покоя. Клетки, которые не находятся в состоянии покоя, называются возбужденными. Конфигурация клеточного конечного автомата, в которой все клетки, кроме конечного их числа, находятся в состояния покоя, называется финитной. Чтобы выполнялось данное требование (т.е. все конфигурации были финитны), достаточно начальную конфигурацию задать финитной. Получив исходную конфигурацию, с использованием функции перехода можно рассчитать конфигурацию автомата в любой момент t ≥ 0 , т.е. состояние любой клетки в любой момент времени, следовательно, рассматриваемый ККА детерминированный, а не вероятностный. В соответствии с табл. 3.2, функция переходов задается как функция пяти переменных двузначной логики. Примеры начальных конфигураций представлены на рис. 3.7.

82

– только в одной точке задано ненулевое состояние – начальное состояние в виде шаблона

Рис. 3.7. Примеры начальных конфигураций

Для машинного моделирования наиболее удобно представлять функцию переходов в виде многочлена Жегалкина:

X* = ϕ( x1 ,x2 ,x3 ,x4 ,x5 ) = a0 ⊕ a1 ⊗ x1 ⊕ a2 ⊗ x2 ⊕ ... ⊕ a5 ⊗ x5 ⊕ ⊕ a12 ⊗ x1 ⊗ x2 ⊕ ... ⊕ a45 ⊗ x4 ⊗ x5 ⊕ a123 ⊗ x1 ⊗ x2 ⊗ x3 ⊕ ... ⊕ ⊕ a345 ⊕ x3 ⊗ x4 ⊗ x5 ⊕ a1234 ⊗ x1 ⊗ x2 ⊗ x3 ⊗ x4 ⊕ ... ⊕ a2345 ⊕

, (3.53)

⊗ x2 ⊗ x3 ⊗ x4 ⊗ x5 ⊕ a12345 ⊗ x1 ⊗ x2 ⊗ x3 ⊗ x4 ⊗ x5 . где X* – состояние; а0 – свободный член; а1, ..., а12345 – коэффициенты, которые нужно найти. Число членов (и соответственно коэффициентов) данного многочлена: 25 = C50 C51C52C53C54C55 = 1 + 5 + 10 + 10 + 5 + 1 = 32 . Все коэффициенты данного многочлена определяются путем составления по табл. 3.2 и решения системы 32 линейных уравнений с 32 неизвестными. После получения многочлена Жегалкина расчеты конфигурации ККА могут быть реализованы на ЭВМ.

83

84

Пример 3.1 Дано: 1) 2) Найти: 1) 2) 3)

многочлен Жегалкина Общий вид:

переходная функция (табл. 3.3); финитная конфигурация. конфигурацию в следующий момент времени; радиус; площадь. Таблица 3.3 Переходная функция ККА

№ п/п

x(t − 1; c1; c2 )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

x(t −1;c1 −1;c2 )

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

x(t − 1; c1 + 1; c2 )

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

x(t − 1; c1 ; c2 − 1)

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

x(t − 1; c1 ; c2 + 1) x(t ; c1 ; c2 )

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1

x(t;c1,c2) = a0 (*) (*) (*) (*) (*) (+) a5 (*) (*) (*) (*) (*) x(t-1;c1,c2+1) (+) a4 (*) (*) (*) (*) x(t-1;c1,c2-1) (*) (+) a45 (*) (*) (*) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) (+) a3 (*) (*) (*) x(t-1;c1+1,c2) (*) (*) (+) a35 (*) (*) (*) x(t-1;c1+1,c2) (*) (*) x(t-1;c1,c2+1) (+) a34 (*) (*) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) (+) a345 (*) (*) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) (+) a2 (*) (*) x(t-1;c1-1,c2) (*) (*) (*) (+) a25 (*) (*) x(t-1;c1-1,c2) (*) (*) (*) x(t-1;c1,c2+1) (+) a24 (*) (*) x(t-1;c1-1,c2) (*) (*) x(t-1;c1,c2-1) (*) (+) a245 (*) (*) x(t-1;c1-1,c2) (*) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) (+) a23 (*) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) (*) (+) a235 (*) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) (*) x(t-1;c1,c2+1) (+) a234 (*) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) (+) a2345 (*) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) (+) a1 (*) x( t-1;c1,c2 ) (*) (*) (*) (*) (+) a15 (*) x( t-1;c1,c2 ) (*) (*) (*) (*) x(t-1;c1,c2+1) (+) a14 (*) x( t-1;c1,c2 ) (*) (*) (*) x(t-1;c1,c2-1) (*) (+) a145 (*) x( t-1;c1,c2 ) (*) (*) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) (+) a13 (*) x( t-1;c1,c2 ) (*) (*) x(t-1;c1+1,c2) (*) (*) (+) a135 (*) x( t-1;c1,c2 ) (*) (*) x(t-1;c1+1,c2) (*) (*) x(t-1;c1,c2+1) (+) a134 (*) x( t-1;c1,c2 ) (*) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) (+) a1345 (*) x( t-1;c1,c2 ) (*) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) (+) a12 (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) (*) (*) (+) a125 (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) (*) (*) x(t-1;c1,c2+1) (+) a124 (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) (*) x(t-1;c1,c2-1) (*) (+) a1245 (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) (+) a123 (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) (*) (+) a1235 (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) (*) x(t-1;c1,c2+1) (+) a1234 (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) (+) a12345(*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1)

Коэффициенты a0 a5 a4 a45 a3 a35 a34 a345 a2 a25 a24 a245 a23 a235 a234 a2345

85

86

= = = = = = = = = = = = = = = =

0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1

a1 = 1 a15 = 1 a14 = 1 a145 = 0 a13 = 1 a135 = 1 a134 = 1 a1345 = 0 a12 = 1 a125 = 0 a124 = 0 a1245 = 0 a123 = 1 a1235 = 1 a1234 = 1 a12345 = 0

x(t;c1,c2) =

(*) (*) (*) (*) x(t-1;c1,c2+1) (*) (*) (*) x(t-1;c1,c2-1) (*) (*) (*) x(t-1;c1+1,c2) (*) (*) x(t-1;c1,c2+1) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) x(t-1;c1,c2+1) x( t-1;c1,c2 ) (*) (*) (*) (*) x( t-1;c1,c2 ) (*) (*) (*) (*) x(t-1;c1,c2+1) x( t-1;c1,c2 ) (*) (*) (*) x(t-1;c1,c2-1) (*) x( t-1;c1,c2 ) (*) (*) x(t-1;c1+1,c2) (*) (*) x( t-1;c1,c2 ) (*) (*) x(t-1;c1+1,c2) (*) (*) x(t-1;c1,c2+1) x( t-1;c1,c2 ) (*) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) (*) (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) (*) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) (*) x(t-1;c1,c2+1) x( t-1;c1,c2 ) (*) x(t-1;c1-1,c2) (*) x(t-1;c1+1,c2) (*) x(t-1;c1,c2-1) (*)

(+) (+) (+) (+) (+) (+) (+) (+) (+) (+) (+) (+) (+) (+)

t = 0: возбужденных клеток 10 , радиус r = 6 , центр в клетке (3, 3) , площадь 85.

Значения x(t,c1,c2) при различных значениях выборки приведены на рис. 3.8, 3.11, а финитные конфигурации – на рис. 3.9, 3.10.

0 000 0 0

1 000 0 1

0 000 1 1

1 000 1 0

0 001 0 0

1 001 0 0

0 001 1 1

1 001 1 1

0 100 0 0

1 100 0 1

0 100 1 1

1 100 1 0

0 101 0 0

1 101 0 0

0 101 1 0

1 101 1 1

0 010 0 0

1 010 0 1

0 010 1 1

1 010 1 1

0 011 0 0

1 011 0 0

0 011 1 1

1 011 1 1

0 110 0 0

1 110 0 0

0 110 1 0

1 110 1 0

0 111 0 0

1 111 0 1

0 111 1 1

1 111 1 1

c2 -14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 /\ +---------------------------------------------------------------------------------------------------------+ 20 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 20 19 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 19 18 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 18 17 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 17 16 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 16 15 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 15 14 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 14 13 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 13 12 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 12 11 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 11 10 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 10 9|• • • • • • • • • • • • • • • • • 0 • • • • • • • • • • • • • • • • •| 9 8|• • • • • • • • • • • • • • • • 1 0 0 • • • • • • • • • • • • • • • •| 8 7|• • • • • • • • • • • • • • • 0 0 0 0 0 • • • • • • • • • • • • • • •| 7 6|• • • • • • • • • • • • • • 0 0 1 0 0 0 0 • • • • • • • • • • • • • •| 6 5|• • • • • • • • • • • • • 0 0 0 0 0 0 0 0 1 • • • • • • • • • • • • •| 5 4|• • • • • • • • • • • • 0 0 0 0 0 1 0 0 0 0 0 • • • • • • • • • • • •| 4 3|• • • • • • • • • • • 0 0 0 0 0 0 1 0 0 0 0 0 0 • • • • • • • • • • •| 3 2|• • • • • • • • • • • • 0 0 1 1 0 1 0 0 0 0 0 • • • • • • • • • • • •| 2 1|• • • • • • • • • • • • • 0 0 0 0 0 1 0 0 0 • • • • • • • • • • • • •| 1 0|• • • • • • • • • • • • • • 0 1 0 0 0 0 0 • • • • • • • • • • • • • •|0 -1 | • • • • • • • • • • • • • • • 0 0 0 0 0 • • • • • • • • • • • • • • • | -1 -2 | • • • • • • • • • • • • • • • • 0 0 0 • • • • • • • • • • • • • • • • | -2 -3 | • • • • • • • • • • • • • • • • • 0 • • • • • • • • • • • • • • • • • | -3 -4 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -4 -5 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -5 -6 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -6 -7 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -7 -8 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -8 -9 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -9 -10 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -10 -11 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -11 -12 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -12 -13 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -13 -14 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -14 +---------------------------------------------------------------------------------------------------------+ -14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Рис. 3.9. Конфигурация клеток в момент t = 0

Рис. 3.8. Значение x(t,c1,c2) при различных шаблонах соседства

87

88

Пример 3.2 Дано: 1) переходная функция Найти: 1) коэффициенты многочлена Жегалкина 2) шаблоны соседства для всех строк переходной функции. Переходная функция представлена в табл. 3.3.

t = 1: возбужденных клеток 19 , радиус r = 7 , центр в клетке (3, 3), площадь 113. c2 -14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 /\ +---------------------------------------------------------------------------------------------------------+ 20 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 20 19 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 19 18 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 18 17 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 17 16 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 16 15 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 15 14 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 14 13 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 13 12 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 12 11 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | 11 10 | • • • • • • • • • • • • • • • • • 0 • • • • • • • • • • • • • • • • • | 10 9|• • • • • • • • • • • • • • • • 1 0 0 • • • • • • • • • • • • • • • •| 9 8|• • • • • • • • • • • • • • • 0 1 0 0 0 • • • • • • • • • • • • • • •| 8 7|• • • • • • • • • • • • • • 0 0 0 0 0 0 0 • • • • • • • • • • • • • •| 7 6|• • • • • • • • • • • • • 0 0 0 1 0 0 0 0 1 • • • • • • • • • • • • •| 6 5|• • • • • • • • • • • • 0 0 0 0 1 1 0 0 0 1 0 • • • • • • • • • • • •| 5 4|• • • • • • • • • • • 0 0 0 0 0 0 1 0 0 0 1 0 0 • • • • • • • • • • •| 4 3|• • • • • • • • • • 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 • • • • • • • • • •| 3 2|• • • • • • • • • • • 0 0 0 0 0 0 1 1 0 0 0 0 0 • • • • • • • • • • •| 2 1|• • • • • • • • • • • • 0 0 1 0 0 0 1 0 0 0 0 • • • • • • • • • • • •| 1 0|• • • • • • • • • • • • • 0 0 1 0 0 1 0 0 0 • • • • • • • • • • • • •|0 -1 | • • • • • • • • • • • • • • 0 1 0 0 0 0 0 • • • • • • • • • • • • • • | -1 -2 | • • • • • • • • • • • • • • • 0 0 0 0 0 • • • • • • • • • • • • • • • | -2 -3 | • • • • • • • • • • • • • • • • 0 0 0 • • • • • • • • • • • • • • • • | -3 -4 | • • • • • • • • • • • • • • • • • 0 • • • • • • • • • • • • • • • • • | -4 -5 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -5 -6 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -6 -7 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -7 -8 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -8 -9 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -9 -10 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -10 -11 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -11 -12 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -12 -13 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -13 -14 | • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • | -14 +---------------------------------------------------------------------------------------------------------+ -14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -> c1

Решение Общий вид многочлена Жегалкина: x(t;c1,c2) = a0⊕a5x(t-1;c1,c2+1)⊕ a4x(t-1;c1,c2-1)⊕a45x(t-1;c1,c2-1) x(t-1;c1,c2+1) ⊕ ⊕a3x(t-1;c1+1,c2) ⊕a35 x(t-1;c1+1,c2) x(t-1;c1,c2+1) ⊕ ⊕a34 x(t-1;c1+1,c2) x(t-1;c1,c2-1)⊕a345 x(t-1;c1+1,c2) x(t-1;c1,c2-1) x(t-1;c1,c2+1)⊕ ⊕a2 x(t-1;c1-1,c2)⊕a25 x(t-1;c1-1,c2) x(t-1;c1,c2+1) ⊕ ⊕a24 x(t-1;c1-1,c2) x(t-1;c1,c2-1)⊕a245 x(t-1;c1-1,c2) x(t-1;c1,c2-1) x(t-1;c1,c2+1)⊕ ⊕a23 x(t-1;c1-1,c2) x(t-1;c1+1,c2)⊕a235 x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2+1)⊕ ⊕a234 x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1) ⊕ ⊕a2345 x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1) x(t-1;c1,c2+1) ⊕a1 x( t-1;c1,c2) ⊕ ⊕a15 x(t-1;c1,c2) x(t-1;c1,c2+1) ⊕a14 x( t-1;c1,c2 ) x(t-1;c1,c2-1) ⊕ ⊕a145 x( t-1;c1,c2 ) x(t-1;c1,c2-1) x(t-1;c1,c2+1) ⊕a13 x( t-1;c1,c2 ) x(t-1;c1+1,c2) ⊕ ⊕a135 x( t-1;c1,c2 ) x(t-1;c1+1,c2) x(t-1;c1,c2+1) ⊕ ⊕a134 x( t-1;c1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1) ⊕ ⊕a1345 x( t-1;c1,c2 ) x(t-1;c1+1,c2) x(t-1;c1,c2-1) x(t-1;c1,c2+1) ⊕ ⊕a12 x( t-1;c1,c2 ) x(t-1;c1-1,c2)⊕ a125 x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1,c2+1)⊕ ⊕ a124 x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1,c2-1) ⊕ ⊕a1245 x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1,c2-1) x(t-1;c1,c2+1) ⊕ ⊕a123 x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1+1,c2) ⊕ ⊕a1235 x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2+1) ⊕ ⊕a1234 x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1) ⊕ ⊕a12345 x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1) x(t-1;c1,c2+1 .

Коэффициенты: a0 = 0 a2 = 0 a5 = 1 a25 = 0 a4 = 1 a24 = 0 a45 = 0 a245 = 0 a3 = 0 a23 = 0 a35 = 1 a235 = 0 a34 = 0 a234 = 1 a345 = 0 a2345 = 1

Рис. 3.10. Конфигурация клеток в момент t = 1

89

90

a1 = 1 a15 = 1 a14 = 1 a145 = 0 a13 = 1 a135 = 1 a134 = 1 a1345 = 0

a12 = 1 a125 = 0 a124 = 0 a1245 = 0 a123 = 1 a1235 = 1 a1234 = 1 a12345 = 0

Многочлен Жегалкина: x(t;c1,c2) = x(t-1;c1,c2+1) ⊕ x(t-1;c1,c2-1) ⊕ x(t-1;c1+1,c2) x(t-1;c1,c2+1)⊕ ⊕x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1)⊕ ⊕x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1) x(t-1;c1,c2+1)⊕ ⊕x( t-1;c1,c2 ) ⊕ x( t-1;c1,c2 ) x(t-1;c1,c2+1) ⊕x( t-1;c1,c2 ) x(t-1;c1,c2-1)⊕ ⊕x( t-1;c1,c2 ) x(t-1;c1+1,c2) ⊕x( t-1;c1,c2 ) x(t-1;c1+1,c2) x(t-1;c1,c2+1)⊕ ⊕x( t-1;c1,c2 ) x(t-1;c1+1,c2) x(t-1;c1,c2-1) ⊕x( t-1;c1,c2 ) x(t-1;c1-1,c2)⊕ ⊕x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1+1,c2)⊕ ⊕x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2+1)⊕ ⊕x( t-1;c1,c2 ) x(t-1;c1-1,c2) x(t-1;c1+1,c2) x(t-1;c1,c2-1). 0 000 0 0

1 000 0 1

0 000 1 1

1 000 1 0

0 001 0 0

1 001 0 0

0 001 1 1

1 001 1 1

0 100 0 0

1 100 0 1

0 100 1 1

1 100 1 0

0 101 0 0

1 101 0 0

0 101 1 0

1 101 1 1

0 010 0 0

1 010 0 1

0 010 1 1

1 010 1 1

0 011 0 0

1 011 0 0

0 011 1 1

1 011 1 1

0 110 0 0

1 110 0 0

0 110 1 0

1 110 1 0

0 111 0 0

1 111 0 1

0 111 1 1

1 111 1 1

Рис. 3.11. Шаблоны соседства для всех строк переходной функции

3.7. Использование дискретных пространственно-временных моделей при расчете себестоимости металлопродукции Стоимость металлопродукции в значительной степени определяется стоимостью сырья и полуфабриката, а также затратами на его обработку по всем агрегатам технологической цепочки. Основные из них: ♦ стоимость технологического топлива (газ природный, коксовый, доменный); 91

♦ энергетические затраты (электроэнергия, пар, вода); ♦ вспомогательные материалы; ♦ отчисления в фонд оплаты труда; ♦ отчисления в соцстрах и фонд занятости; ♦ затраты на сменное оборудование; ♦ отчисление в ремонтный фонд; ♦ амортизация; ♦ содержание основных средств; ♦ расходы на внутрикомбинатовское перемещение полуфабрикатов и продукции; и т.д. При расчете себестоимости необходимо учитывать ряд важных, факторов [29]: 1. Длина технологической цепочки, набор и последовательность прохождения агрегатов существенно зависят от типоразмеров готовой продукции и производимых марок стали; 2. Однотипные операции могут проводиться на различных агрегатах (например, обезжиривание в башенных и горизонтальных печах, вторая холодная прокатка на двадцативалковых и реверсивном станах). С другой стороны, различные технологические операции могут выполняться на одном агрегате (например, обезжиривание и обезуглероживание – в башенных печах, вторая и третья холодные прокатки – на двадцативалковом стане); 3. Необходимо учитывать расходные коэффициенты по металлу, связанные с обрезкой кромок и концевых участков полос; 4. Чтобы анализировать действительные затраты производства, необходимо учитывать различия в затратах на технологию производства каждого типоразмера, т.е. необходимо получить реальные коэффициенты трудоемкости производства различных видов металлопродукции; 5. На каждом этапе обработки необходимо учитывать незавершенное производство предыдущих календарных периодов (объем, сортамент и текущую накопленную стоимость для каждого вида продукции). Количество тонн полуфабриката, которое требуется для производства заданного количества продукции, вычисляется по формуле: VФ = VT ∗ K P , (3.54) где VФ – это фактический объем загрузки; VT – требуемый объем готовой продукции; K P – расходный коэффициент. Сами же расходные коэффициенты рассчитываются как произведения коэффициентов для каждого агрегата по всем маркам продукции: 92

n

K P = ∏ k ai ,

(3.55)

i =1

Исходные условия

где k ai – расходный коэффициент i-го агрегата на производство определенной марки продукции; п – количество операций. Расчетная загрузка металла по операциям представлена на рис. 3.12. Сортамент

Требуется, тн

Расчетная загрузка

1-й вид продукции

VTP1

VTP1K P1

…

…

…

m-й вид продукции

VTPm

VTPm K Pm

1-я операция

… коэффициент

тонн

k11

VTP1K P1 k11

…

…

k1m

VTPm K Pm k1m

Расчет себестоимости продукции происходит итеративно, от агрегата к агрегату. Себестоимость готовой продукции равна себестоимости после обработки на последнем агрегате. Для определения себестоимости необходимо иметь расходные коэффициенты ресурсов для всех видов продукции по каждому переделу. Они определяются по методике, описанной в [30-32]. В итоге на основе теоретических представлений и с учетом технологических особенностей осуществляется расчет затрат электроэнергии, валков, пара, газа, зарплаты и т.д. для каждого агрегата в отдельности. Процесс производства металлопродукции является длительным многоступенчатым процессом. После каждой операции получаемые полуфабрикаты (рулоны) складываются или передаются на последующие агрегаты (рис. 3.13). Так как себестоимость рассчитывается каждый месяц, то на окончание календарного периода за каждым агрегатом скапливается определенное количество полуфабриката, которое можно считать незавершенным производством. Рулоны могут храниться на складах достаточно длительное время. Туда же поступают рулоны, обработанные в другие периоды. Они могут иметь другую текущую стоимость, например из-за изменения цены ресурсов. Таким образом, необходимо учитывать разницу в затратах и корректно переносить ее в себестоимость готовой продукции. агрегат

i-я операция

…

Vreali

агрегат

Vnpi

i

i–1

коэффициент

тонн

ki1

VTP1K P1 ki1

…

…

kim

VTPm K Pm kim

Рис. 3.13. Движение металла между агрегатами

коэффициент

тонн

k n1

VTP1K P1 k n1

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

…

…

k nm

VTPm K Pm k nm

VHH3i−1

VHK3i−1

Voi −1

… n-я операция

Vnpi −1

Voi

Ci =

S прi + S H 3i Vпрi + VHH3 i

,

(3.56)

где S npi – это стоимость в рублях годного полуфабриката, обработанного i-м агрегатом; S H 3i – сумма в рублях незавершенного производства на начало

Рис. 3.12. Определение расчетной загрузки металла по операциям

93

94

x1 (i, j, t ) = Vпр (i , j , t )

периода i-го агрегата; Vnpi – объем годного полуфабриката после i-го агрегаK H 3i

та, VHH3i , V

  x2 (i , j , t ) = Vreal (i, j, t )  ξ (i, j , t ) = Vнзн (i, j, t )  .  ξ (i, j , t + 1) = Vнзк (i, j , t )  x1* (i, j , t ) = S пр (i , j , t )   ξ * (i, j , t ) = S нз (i, j , t ) 

– объем незавершенного производства после i-го агрегата (на-

чало и конец месяца); Vreali – объем полуфабриката, обработанного на i-м агрегата (за исследуемый календарный период). При этом: Vnpi −1 + VHH3i−1 = Vreali + VHК3i−1 ;

(3.57)

Vreali = Vnp + Vo ; i

Vnpi =

(3.58)

i

Vnpi −1 + V

H H 3i −1

−V

K H 3i −1

kai

.

t

Voi = Vreali ( kai – 1)

S npi = Ci −1 +

Одномерная двунаправленная итеративная сеть, описывающая движение металла с учетом стоимости полуфабриката, представлена на рис. 3.14.

(3.59)

Объем отходов: Стоимость годного полуфабриката:

(3.63)

3i − Soi Vnpi

(3.60)

,

T+ 1 i – 1, t + 1

Ξ(i − 1, t )

Ξ* (i −1, t )

(3.61)

рикатов на i-м агрегате.

i– 1, t m

3i = ∑ zij k zij ,

Ξ* (i, t )

x1 (i − 1, t )

t

где Soi – суммарная стоимость отходов; 3i – затраты на обработку полуфаб-

i, t + 1

x1* (i − 1, t ) x2 (i, t )

i + 1, t + 1

Ξ(i,t) Ξ* (i + 1, t )

Ξ(i + 1, t )

x1 (i, t ) i, t

x1* (i, t )

i + 1, t

x2 (i + 1, t )

(3.62)

j =1

i–1

где zij – затраты на единицу ресурсов; k zij – коэффициент трудоемкости; m – количество ресурсов. Использование итеративных сетей позволяет учесть незавершенное производство металла от агрегата к агрегату в течение длительного времени за счет наличия временной переменной. Величины, описанные в формулах (3.56)-(3.61), необходимо представить в терминах одномерных двунаправленных сетей. Для каждого состояния необходимо ввести дополнительные индексы: i – номер агрегата; j – номер элемента сортамента (j = 1, …, m); t – календарный период. В итоге с помощью внутренних состояний и внутренних входов и выходов можно описать основные переменные:

95

i

i+1

Рис. 3.14. Одномерная двунаправленная итеративная сеть движения металла с учетом стоимости полуфабриката Х 1 , Х 2 , Х 1* , Ξ, Ξ∗ – векторы, учитывающие обрабатываемый сортамент. Х1 (i − 1, t ) = { x1 (i − 1,1, t ), ..., x1 (i − 1, m, t )}   Х1* (i − 1, t ) = { x1* (i − 1,1, t ), ..., x1* (i − 1, m, t )}    Х 2 (i, t ) = { x2 (i,1, t ), ..., x2 (i, m, t )}   Ξ (i, t ) = {ξ (i,1, t ), ..., ξ (i, m, t )}   Ξ∗ (i, t ) = {ξ * (i,1, t ), ..., ξ * (i, m, t )} 

96

.

(3.64)

Управление данной сетью можно представить в виде:    x1 (i, j , t ) = f1 [ Х 1 (i − 1, t ), Х 2 (i + 1, t ), Ξ (i, t − 1)]   x2 (i, j , t ) = f 2  Х 1 (i − 1, t ), Х 2 (i + 1, t ), Ξ (i, t − 1)   .  ξ (i, j , t ) = f3  Х 1 (i − 1, t ), Х 2 (i + 1, t ), Ξ (i, t − 1)    ∗    x1* (i, j , t ) = ψ 1  Х 1 (i, t ), Ξ (i , t − 1), Ξ (i , t − 1)      *   ξ * (i, j, t ) = ψ 2  Х 1 (i, t ), Ξ (i, t − 1), Ξ (i, t − 1), Х 1* (i, t )     

4. Дискретные конечно-аргументные модели

(3.65)

97

Теория сигналов и систем на конечных множествах возникла в связи с задачами цифровой обработки сигналов, заданных конечным числом отсчетов. Конечное множество значений аргумента может, например, представлять множество моментов времени, в которые сняты отсчеты временного сигнала, или множества точек плоскости, в которых сняты отсчеты яркости изображения, и т.п. Эта теория в некоторых своих аспектах существенно отличается от классической, обнаруживая в то же время далеко идущие аналоги с последней. Одна из причин отличия – в том, что в случае конечного множества значений аргумента нарушаются некоторые фундаментальные для классической теории соотношения между структурой порядка и законами композиции в множестве значений аргумента. В частности, системы на конечных множествах аргументно-некаузальны. Возникновение теории сигналов и систем на конечных множествах связано с тем, что для дискретных методов обработки сигналов, особенно при их реализации на ЭВМ, характерны ограниченная память и возможность извлечения из блока памяти отсчетов сигнала в любой последовательности. Именно в силу ограниченности памяти для таких методов является естественным представление о конечности множества значений аргумента. С возможностью извлечения из блока памяти отсчетов сигнала в любой последовательности связан фундаментальный для этой теории подход, состоящий в наделении конечного множества A значений аргумента структурой конечной группы. Основы этого подхода в отечественной литературе освещены и обоснованы в [33], где указано, что в результате такого подхода теория сигналов и систем на конечных множествах приобретает своеобразие, которое позволяет считать ее новым направлением общей теории сигналов и систем. Групповая операция в конечном множестве значений аргумента A индуцирует сдвиг сигналов, определяемый в виде некоторой перестановки их отсчетов и не выводящий их за пределы конечного множества [34]. Это обстоятельство является главным, что отличает рассматриваемую теорию от классической дискретной теории, основанной на дискретных преобразованиях Лапласа или Фурье, в которой дискретные сигналы и системы определяются на бесконечном интервале, сдвиг понимается как параллельный перенос сигнала во времени и отсчеты сигнала в системах обработки всегда следуют друг за другом в натуральном порядке. Конечность множества A задания сигналов и новое толкование сдвига заставляют пересмотреть многие привычные понятия и приводят к необходимости использовать новые системы базисных функций и новые виды уравнений, описывающих системы, подробно изученные в пособии [34]. При наделении конечного множества A структурой конечной абелевой группы адекватный базис в пространстве скалярных сигналов автоматически 98

определяется как соответствующая группа характеров. Характеры – аналоги классических экспонент – обладают свойствами ортогональности относительно естественного определяемого скалярного произведения сигналов, а также рядом других замечательных свойств, в силу чего играют в теории на конечных множествах важнейшую роль. Такие базисы являются конечными аналогами мультипликативных систем функций. Они находят применение в различных областях технической кибернетики. Их крайними частными случаями являются такие широко распространенные системы функций, как функции Уолша, основанные на двоичной арифметике (когда конечное множество содержит 2d элементов при некотором натуральном d и наделяется структурой диадической группы) и дискретные экспоненциальные функции, основанные на N-ичной арифметике (когда конечное множество содержит N элементов и наделяется структурой циклической группы). Широкое многообразие мультипликативных базисов существенно расширяет возможности теории сигналов и систем на конечных множествах. Появляется возможность производить спектральные преобразования точно, так как они выражаются конечными суммами. Спектральные преобразования систематически используются и при исследовании конечно-аргументных систем [34]. Новые виды уравнений, описывающих системы на конечных множествах, возникают как аналоги классических, с заменой традиционных понятий сверки, сдвига, дифференцирования соответствующими понятиями, отвечающими наделению конечного множества структурой конечной группы. Так определяются подробно рассматриваемые [34] сверточные и десверточные системы, {m}-цепи, гармонические дифференциальные системы и их частные случаи – диадические и циклические дифференциальные системы. Даже в том случае, когда параметры этих систем постоянны, они не являются стационарными в традиционном понимании, но стационарны в смысле нового понятия сдвига сигналов, определяемого групповой операцией в конечном множестве. Так трактуется аргументная стационарность этих систем. Для систем на конечных множествах большим своеобразием обладает трактовка таких фундаментальных понятий теории систем, как динамика, каузальность (причинность), рекурсивность. Своеобразие связано с тем, что групповая операция в конечном множестве, сводящаяся к перестановке его элементов, не согласована с отношениями линейного или частного порядка, которыми может быть наделено это множество. Возникают трудности и при реализации систем на конечных множествах. Классическая проблема реализации состоит в восстановлении уравнений состояния системы по ее описанию вход-выход; ее решение на разных уровнях абстрактности известно для многих классов каузальных систем, причем в случае стационарных систем описание вход-выход стандартно задается в виде сверки, а уравнения состояний – в виде дифференциальных или разностных уравнений. В случае систем на конечных группах принятие сверки на группе в качестве стандартного 99

описания вход-выход представляется вполне естественным; между тем, повидимому, не существует до сих пор общепринятого мнения о том, что считать стандартной формой уравнений состояния систем на конечных множествах. В [34] в качестве основных претендентов на эту роль представлены K-дифференциальные и K-разностные системы.

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

O (N)

N-1

1

Y(S) X(S)

S

X(S - 1) U(S)

Рис. 4.1. Одномерная однонаправленная циклическая линейная итеративная сеть

Клеткам присвоены номера s ∈ Z0 ( N ) = { 0, 1, ..., N − 1} , каждая имеет внешний вход u ( s ) ∈ K l и выход y ( s ) ∈ K q и внутренние (по отношению к цепи как к целому) вход x( s − 1) ∈ K n (вход предыдущей клетки) и выход x( s ) ∈ K n (вход последующей клетки): при этом фиксировано, например, направление нумерации по часовой стрелке (альтернативное направление против часовой стрелки). Так как клетка, имеющая номер 0, отождествляется с клеткой номер N, то естественно обычные арифметические операции сложения и вычитания (+ и –) заменить операциями сложения и вычитания по

100

•

•

N

N

модулю N, обозначаемыми через + и − соответственно [34]. Уравнения такой N-цепи (по терминологии [35]) запишутся в виде: •

x( s ) = Φ x( s − 1 ) +Ψ u( s ), N

(4.1)

•

y( s ) = Hx( s − 1) + Gu( s ), s ∈ Z0 ( N ).

4.2. Одномерные полициклические линейные итеративные цепи ((m)-цепи) Если число N не является простым, то в соответствии с основной теоремой арифметики оно представляется, причем многими различными способами, в виде произведения (не обязательно простых и различных) сомножителей N = m1 ⋅ ... ⋅ md , совокупность которых обозначим через {m}: этим опре-

N

Такие цепи являются конечно-аргументными аналогами линейных стационарных дискретно-временных моделей (2.2) и линейных однородных одномерных однонаправленных дискретно-пространственных моделей (2.7). В операторной записи оператор ξ временного сдвига или оператор Z пространственного сдвига заменяются оператором µ N-сдвига. Отметим существенные отличия. Хотя матрицы в уравнениях (4.1) постоянны, N-цепь не является время-стационарной или пространственно однородной в принятом смысле этих понятий: эта модель оказывается инвариантной относительно N-сдвига, или N-стационарной [33]; так трактуется ее аргументная стационарность. N-цепь аргументно-некаузальна, что сближает ее с двунаправленной цепью (2.9). В то же время можно указать конечно-аргументный аналог последней, представленный на рис. 4.2 и описываемый уравнениями: •

•

N

N

x( s ) = Φ 1 x( s − 1) + Φ 2 x( s + 1 ) +Ψ u( s ), •

•

N

N

•

•

•

делены [34,35] операции {m}-сдвига +

{m}

{m}

в множестве Z0 ( N ) = Z0 ( m1 , ..., md ) , которые, как и операции N-сдвига, не выходят за множество Z 0 ( N ) : в частном случае N = m d ; такие операции •

•

{m}

{m}

m-сдвига в Z0 ( m1 , ..., m d ) обозначаются + и − [33,34]. Заменяя обычный арифметический сдвиг {m}-сдвигом, получим уравнения {m}-цепи [35]: •

x( s ) = Φ x( s − 1 ) +Ψ u( s )

(4.3)

y( s ) = Hx( s ) + Gu( s ). Клеточное представление такой структуры в случае N = 12 = 3 ⋅ 4 предложено на рис. 4.3.

(4.2)

y( s ) = H 1 x( s − 1 ) + H 2 x( s + 1 ) + Gu( s ). 2

…

0 0

…

1

2 0|3

1|0

1

…

2

2 0

Рис. 4.2. Одномерная двунаправленная циклическая линейная итеративная цепь 2

1

Рис. 4.3. Полициклическая {4,3}-цепь

101

•

(коротко просто + и − )

и −

102

Относительно {m}-цепей справедливы замечания, сделанные об N-цепях, являющихся их частным случаем: аргументная некаузальность близка к предложенной в [33] трактовке m-цепей как нерекурсивных. В [36] подробно обсуждаются возможности использования m-цепей как процессоров для цифровой обработки конечных массивов информации.

запишем (4.6) в виде одного уравнения:

4.3. Двумерные полициклические линейные итеративные цепи (двумерные (m)-цепи)

та»:

Трактовка систем на конечных множествах как процессоров для обработки массивов информации позволяет ввести аналог {m}-цепей (предназначенных для обработки массивов с формально одномерным носителем) для случая массивов с двумерным носителем. Пусть двумерный массив информации задан на квадрате Z 02 (m d ) = (s1, s2 ), s1,s 2 ∈ Z 0 (m d ) (это – непосредственное обобщение сигнала, определенного на конечном интервале). Соответствующий процессор можно моделировать двумерной m-цепью, которая, сочетая (2.14) и (4.1), определяется уравнениями:

{

}

•

•

•

•

x1 ( s1 ,s2 ) = Φ 11 x1 ( s1 − 1,s2 ) + Φ 12 x2 ( s1 ,s2 − 1) +Ψ 1u( s1 ,s2 ),

x( s1 ,s2 ) = Φθ x( s1 ,s2 ) +Ψ u( s1 ,s2 ), ( s1 ,s2 ) ∈ Z 02 ( m d ).

(4.8) Установим связь такой двумерной m-цепи с одномерной (4.1). Поскольку m-сдвиг не выводит за интервал Z 0 ( m d ) для любой точки

( s1 ,s2 ) ∈ Z02 ( m d ), s1 + s2 = K ∈ Z0 ( m d ) . Определим «классы точек квадраG( k ) = {( s1 ,s2 ) ∈ Z02 ( m d ) : s1 + s2 = K } . Каждый класс содержит md точек и

G( k ) ∩ G( l ) = 0, k ≠ l,

U

G( k ) = Z02 ( m d ).

(4.10)

K ∈Z0 ( m ) d

Предположим, что точки каким-либо образом упорядочены внутри класса, и обозначим:

Χ ( k ) = ( xΤ ( s1 ,s2 ))

∈ C 2m ,

U( k ) = ( u ( s1 ,s2 ))

∈C .

Τ

d

( s1 ,s2 )∈G( k )

Τ

Τ

(4.4)

(4.11) md

( s1 ,s2 )∈G( k )

•

Если ( s1 ,s2 ) ∈ G( k ), т.е. s1 + s2 = k , то

x2 ( s1 ,s2 ) = Φ 21 x1 ( s1 − 1,s2 ) + Φ 22 x2 ( s1 ,s2 − 1 ) +Ψ 2 u( s1 ,s2 ).

•

•

•

•

•

•

•

( s1 − 1 ) + s2 = s1 +( s2 − 1 ) = ( s1 + s2 ) − 1 = k − 1,

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

x( s1 ,s2 ) = Φ 1 x( s1 − 1,s2 ) + Φ 2 x( s1 ,s2 − 1 ) +

(4.9)

•

•

(4.12)

•

(4.5)

так что ( s1 − 1,s2 ), ( s1 ,s2 − 1 ) ∈ G( k − 1 ) поэтому из уравнений (4.8) не-

Для упрощения рассмотрений ограничимся случаем n1 = n2 = l = 1 , так что n = 2 (вход и составляющая выхода цепи скалярны). В этом случае уравнения (4.4) запишутся в виде:

посредственно следует, что Χ(k ) линейно выражается через Χ ( k − 1 ) (а также через U (k ) ). Эту связь можно описать уравнением:

+ Φ 3 x( s1 − 1,s2 − 1) +Ψ u( s1 ,s2 ).

•

•

x1 ( s1 ,s2 ) = ϕ11 x1 ( s1 − 1,s2 ) + ϕ12 x2 ( s1 ,s2 − 1 ) +Ψ 1u( s1 ,s2 ), •

•

(4.6)

x2 ( s1 ,s2 ) = ϕ21 x1 ( s1 − 1,s2 ) + ϕ 22 x2 ( s1 ,s2 − 1 ) +Ψ 2 u( s1 ,s2 ), где ϕ11 , ..., ψ 2 скаляры.

•

X ( k ) = Φ x( k − 1 ) +Ψ U( k ), k ∈ Z0 ( m d ), где структура матрицы Ψ определяется соотношением: Ψ = I md ⊗Ψ ,

(4.13) (4.14)

так что матрица Ψ одна и та же для все k ∈ Z 0 ( m ) , здесь ⊗ – кронекеровское или тензорное произведение матриц. Всегда можно так упорядочить точки внутри классов и так согласовать эти упорядочивания между классами, d

Полагая •   x1( s1 − 1,s2 )   x1( s1 ,s2 )   x( s1 ,s2 ) =  , θ x( s ,s ) = , 1 2  •    x2 ( s1 ,s2 )  x2 ( s1 ,s2 − 1 ) ϕ12  ϕ Ψ  Φ =  11 , Ψ =  1,  ϕ 21 ϕ 22  Ψ 2 

•

(4.7)

103

что матрица Φ даже не будет зависеть от k ∈ Z 0 (md ) и ее структура определяется соотношением: (4.15) Φ = I md −1 ⊗ (Wm × Φ ) .

104

Здесь Wm – блочная матрица блочного порядка m (одна и та же для всех k ∈ Z 0 (md ) ).

…

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

Рис. 4.5. Решетчатая система как одномерная однонаправленная цепь, составленная из циклических цепей

Различные трактовки расширяют использование таких структур при моделировании реальных объектов. Таким образом, решетчатые модели сочетают классические дискретно-временные модели и конечно-аргументные модели. В [37] рассмотрено сведение решетчатых моделей на многомерных решетках к моделям на одномерных решетках и наоборот: эти преобразования аналогичны переходу к ассоциированным моделям от многоразмерностных, а также приведение двумерных {m}-цепей к одномерным, рассмотренных в подглаве 3.3. Рис. 4.4. Решетчатая система как одномерная циклическая сеть

Подобно тому, как в подглаве 3.1, сигналы такой сети зависят от номера клетки s ∈ Z 0 ( N ) , так и от времени t ∈ Z 0 . Такие модели под названием «решетчатые системы» рассмотрены в [37], где предложено описание их динамики

x( t + 1,s ) =

∑

ϕ ( σ )x( t ,s − σ ) +

∑

ϕ ( s − σ )x( t ,σ ) +

σ ∈Z0 ( N )

=

σ ∈Z 0 ( N )

∑

Ψ ( θ )u( t ,s − θ ) =

∑

Ψ ( s − θ )u( t ,θ ) = (4.16)

θ ∈Z0 ( N )

θ ∈Z0 ( N )

= ( Φ ⊗ s x )( t ,s ) + (Ψ ⊗s u )( t,s ). С формальной точки зрения описание (4.16) является более общим, чем например (2.14), так как его слагаемые представляют собой K-свертки [20]: некоторые важные свойства при этом сохраняются, например, линейность и {m}-стационарность. С точки зрения содержательной интерпретации такие модели можно трактовать (заменяя время t на другую пространственную переменную p, отличную от s) и как бесконечные вправо цепочки из клеток, каждая из которых представляет собой {m}-цепь: пример такой трактовки представлен на рис. 4.5.

105

106

5. Сети Петри

I (t j ) – позиции на входах перехода t j ;

5.1. Описание сетей Петри

O (t j ) – позиции на выходах перехода t j ;

Сети Петри (СП) являются удобным аппаратом моделирования параллельных процессов, т.е. процессов, протекающих в системе независимо один от другого. На выполнение таких процессов не накладываются какие-либо условия синхронизации. Моменты начала и завершения параллельных процессов, интервалы их реализации не являются в системе взаимообусловленными. Параллельным процессам соответствуют состояния сетей Петри, в которых разрешены сразу несколько переходов, и каждый из них может сработать. Но какой именно переход сработает, решается всякий раз случайным образом по правилам равновероятного выбора. Сети Петри широко используются при моделировании и управлении гибкими производственными системами. В отличие от конечных автоматов, в терминах которых описываются глобальные изменения состояния системы, сеть Петри конкретизирует внимание на локальных событиях (им соответствуют переходы), на локальных условиях (им соответствуют позиции), на локальных связях между событиями и условиями. Поэтому сеть Петри более адекватно, чем конечные автоматы, моделируют поведение распределенных асинхронных систем. Тем самым СП приспособлены для моделирования параллельных вычислительных процессов и систем [43]. Для полного описания функционирования СП задаются: 1). Множество позиций Р = {Р1, …, Рn}, т.е. конечное число позиций (|p| = n); 2). Множество переходов Т = {t1, …, tm}, т.е. конечное число переходов (|T| = m); Позиции и переходы не пересекаются, и совпадать не могут: P IT = ∅ ; 3). Начальная маркировка или разметка сети: М0 = (М0(Р1), …, (М0(Рn )), ∈ Z n0 , где n – вектор, компоненты целые неотрицательные числа (Z0). Координаты вектора указывают количество меток или фишек в каждой позиции СП в начальный момент времени. В результате функционирования СП в каждый момент времени k возникает текущая разметка, M k = ( M k ( P1 ),...,M k ( Pn )), M k ( Pi ) ∈ Z0 , опре-

I ( p i ) – переходы на входах позиции p i ; O ( p i ) – переходы на выходах позиции pi ; 5). Функция переходов ϕ , определяющая М% = ϕ( C; М ) , – возможное состояние сети при начальной маркировке М0, следующее за состоянием М, но не обязательно непосредственно за М. Функция ϕ определяется правилами функционирования: а) в каждый момент времени срабатывает только разрешенный переход, т.е. такой, во всех входных позициях которого при заданной маркировке М имеются ненулевые метки; б) срабатывание перехода может наступить через любой конечный промежуток времени после его разрешения (т.е. переход срабатывает не обязательно сразу непосредственно после его разрешения); в) если в некотором состоянии разрешены несколько переходов, то всегда срабатывает только какой-то один из них; в этом правиле заключается недетерминизм функционирования сети Петри (т.е. если в какой-то момент времени несколько переходов могут сработать, то неизвестно, какой именно сработает); г) в результате срабатывания перехода метки во всех его входных позициях уменьшаются на единицу, а в выходных – на единицу; д) срабатывание перехода – неделимый акт; считается, что изменение количества во входных и выходных позициях при срабатывании осуществляется мгновенно. При графическом изображении сети Петри вершинами графа служат позиции и переходы, образующие две доли Р и Т. Дуги отражают связь позиций и переходов. Дуга ( pi , t j ) направлена от позиции pi к переходу t j , аналогично ( t j , pi ). Дуги обозначаются d . Позиции обозначают окружностями, а переходы – планками. Ниже приведен пример сети Петри на рис. 5.1, 5.2.

деляющая состояние сети в этот момент времени ( M 0 – начальное состояние); 4). Взаимосвязь позиций и переходов задаются компонентами: 107

108

В первоначальном изображении отображается и начальная разметка (чтобы двигаться – на входе перехода все позиции должны быть заняты). Правила функционирования могут быть частично отражены с помощью матрицы СП. Пусть µ (j) – m-мерный вектор из нулей с единицей на j-м месте, j = 1, …, m (показывает, какой переход срабатывает). Этот вектор используется как отражение правила (б). Тогда правило (а) записывается в виде: М ≥ µ (j) R − .

Рис. 5.1. Графическое представление сети Петри

Условие разрешения перехода tj (используется R − , т.к. речь о входных позициях, а R − – оговаривает все входные позиции). Правило (г) записывается в виде:

Рис. 5.2. Представление сети Петри в виде двудольного графа

M1 = M0 + µ (j) R = M0 – µ ( j ) R − + µ ( j ) R + .

Для данной сети Петри |P| = n = 4, |T| = m = 2. I(t1) = {p1, p3} O(t1) = {p2} I(p1) = ∅ O(p1) = {t1}

где

I(t2) = {p2} O(t2) = {p3, p4} I(p2) = {t1} O(p2) = {t2}

(5.4)

(5.5)

Для любого момента времени связь разметок выражается соотношением:

I(p3) = {t2} O(p3) = {t1}

I(p4) = {t2} O(p4) = ∅

Матрица сети Петри размера m×n: R = R + − R− ,

(5.1)

1, если pi ∈ O(t j ), , R + =  rji+  , rji+ =  0, в любом другом случае

(5.2)

1, если pi ∈ O(t j ), . R − =  rji−  , rji− =  0, в любом другом случае 

(5.3)

Mk = Mk-1 + µ (j) R (5.6) Разметка Mk оказывается непосредственно достижимой из разметки Mk1 (но не обязательно непосредственно следует). Последовательно применяя формулу (5.6), получим: Mk = M0 + µ R , (5.7) где µ = µ (j1) + µ (j2) +…+ µ (jk) (5.8) есть m-мерный вектор, координатами которого могут быть уже любые неотрицательные целые числа (n – количество шагов). Разметка Mk – достижима из разметки M0. Функционирование: M1 = M0 + µ(j)R . Рассмотрим маркировки: M 0' = [0 0 0 0] и M 0'' = [1 1 1 0] . Необходимо определить разрешенность данных маркировок: 1 0 1 0 µ (1) R − = [1 0]⋅   = [1 0 1 0] ; 0 1 0 0

Отсюда − 1 1 − 1 0 1 0 1 0 0 1 0 0 , R= R+ =  , R− =   .   0 0 1 1 0 1 0 0  0 − 1 1 1 Вершинами этого графа служат позиции и переходы, образующие две доли: Р и Т. Дуги отражают связь позиций и переходов. Дуга (tj, pj) направлена от позиции pj к переходу tj (дуга от позиции к позиции не идет, и от перехода к переходу), аналогично (tj, pj). Позиции обозначают кружками, переходы – планками. Граф – наиболее наглядное изображение СП. 109

т.к. M 0' = [0 0 0 0] , то условие M 0' ≥ µ (1) R − не выполняется;

1 0 1 0 ' µ (2) = [0 1]⋅   = [0 1 0 0] ≤ M 0 не выполняется, следователь0 1 0 0   но, такая сеть функционировать не будет и маркировка M 0' не разрешена.

110

В то же время M 0'' = 1 1 1 0 > 1 0 1 0 = µ (1) R − – переход разрешен; маркировка разрешена. Функционирование сети с данной маркировкой на один шаг:

M

(1) 1

 −1 0 −1 0  = M 0 + µ ( 1 )R = [1 1 1 0 ] + [1 0 ] ⋅  =  0 −1 1 1  = [0 2 0 0 ] ;

Имеем систему четырех уравнений с двумя неизвестными; µ не может равняться –1 или 0,5; следовательно, маркировка M″ не достижима.

[

Если M ′′ = 0

[µ1, µ 2 ]⋅ 

−1

0

 −1 1 −1 0  M 1( 2 ) = M 0 + µ ( 2 )R = [1 1 1 0 ] + [0 1] ⋅  =  0 −1 1 1  = [1 0 2 1] ,

0 1 1] , то

1 − 1 0 = [0 0 1 1] − [0 1 0 0] = [0 − 1 1 1] , − 1 1 1  − µ1 = 1,  µ1 − µ2 = −1,   − µ1 + µ 2 = 1,  µ2 = 1.

Следовательно, µ2 = 1, µ1 = 0, µ = µ(2) = [0 1] . Это означает, что разрешен второй переход и метка M″ достижима.

следовательно, сработать может любой переход. Дерево маркировок представлено на рис. 5.3.

Проблема сохранения Сеть Петри с разметкой М называется сохраняющей относительно ве-

Рис. 5.3. Дерево маркировок после первого шага

Следующий этап – исследование достижимости некоторой маркировки М ′′ . Задача достижимости сводится к определению неотрицательного целочисленного вектора µ = µ(j1) + µ(j2) + µ(j3) +…+ µ(jk), где k – количество шагов. Необходимо решить уравнение: (5.9) µ R = M ′′ − M . Пусть

M 0 = [0 1 0 0 ] , M ′′ = [1 1 1 0 ] ;

[µ1, µ 2 ] ⋅ 

−1

0

1 −1

− 1 0 = [1 1 1 0] − [0 1 0 0] = [1 0 1 0] ; 1 1 

 − µ1 = 1,  µ − µ = 0,  1 2  − µ + µ 2 = 1,  1  µ 2 = 0.

111

сового вектора W = (w1, …, wn) ∈ Z 0n (число координат по числу позиций ~ у этого вектора), если для любой достижимой разметки M выполняется соотношение n n ~ (5.10) ∑ wi M ( pi ) = ∑ wi M ( pi ) i =1

i =1

(для всех последующих разметок весовая функция не должна изменяться). Краткая запись: ~ (5.11) MW = M W , ~ т.к. M = M + μR, то умножив скалярно все члены этого выражения на W, получим: ~ M W = MW + μRW . (5.12) Но по условию (5.10) следует: μRW = Ø. (5.13) Т.к. это должно выполняться при любом μ, то проверка сохранности и отыскания сохраняющих весов полностью решается уравнением RW = Ø . (5.14) В случае W = (1, 1, 1, …, 1) (все веса единичны), СП называется строго сохраняющей. Она характеризуется тем, что для любого перехода tj число выходных и входных позиций одинаково: |O(tj) |= |I(tj)| для всех tj. (5.15) 112

С помощью матричного представления СП рассматриваются и другие проблемы (проблема живости (живая СП), проблемы тупиков и ограниченности, и т.д.) [38-43].

5.2. Использование сетей Петри при расчете себестоимости продуктов металлургического производства При расчете себестоимости продуктов металлургического производства представляет интерес проблема выбора соответствующего математического аппарата, позволяющего упростить процесс расчета и представить его более наглядными (в том числе и графическими) средствами. Процесс расчета себестоимости может быть представлен в виде функционирования сети Петри. В такое представление входят следующие элементы. 1. Непустое конечное множество позиций P = { P1 , P2 , ..., Pn } . Каждый элемент этого множества соответствует одному материалу, занятому в металлургическом производстве. Для каждого материала в любой текущий дискретный момент времени k = 0, 1, 2, ... себестоимость либо известна (задана изначально или рассчитана в один из предыдущих моментов времени), либо не известна (расчет для этого материала еще не производился). Материал может быть либо сырьем (его себестоимость, т.е. в данном случае покупная цена, известна заранее), либо продуктом (включает в себя несколько материалов вида «сырье» и может включать один или несколько материалов вида «продукт»; себестоимость продукта рассчитывается в один из моментов времени функционирования сети Петри). Себестоимость продуктов металлургического производства складывается из себестоимости сырья, расходов по переделу и вспомогательных материалов, таких как сжатый воздух, пар, техническая вода, электроэнергия и т.п. Поэтому нахождение искомой себестоимости ct каждого из продуктов сводится к вычислению суммы произведений [44]: n

ci = ∑ c jα ij ,

i = 1, 2, ..., m,

(5.16)

j =1

где c j , и n – себестоимость j-го материала (продукта либо сырья) и количество материалов, используемых при производстве i-го продукта; α ij – коэффициент, характеризующий долю объема j-го материала в общем объеме производства i-го продукта; т – общее количество продуктов. 2. Непустое конечное множество переходов T = { t1 , t 2 , ..., tm } . Каждый элемент этого множества соответствует моменту расчета себестоимости одного из элементов вида «продукт» из множества позиций Р, поэтому одно-

113

значно закреплен за этим элементом. Множества позиций и переходов не пересекаются. 3. Вектор текущей маркировки, возникающей в процессе функционирования сети Петри в каждый момент времени k и определяющей состояние производимого расчета в этот момент времени: µ k = [µ k ( P1 ) µ k ( P2 )...µ k ( Pn )]T ,

(5.17)

где 0, если себестоимость материала Pi ,   i = 1,...,n, ещё не расчитана;  µk ( Pi ) =  1, если себестоимость материала Pi ,  i = 1,...,n, расчитана или известна первоначально. Рассматриваемая сеть Петри является безопасной, поскольку ни один из элементов вектора µ k текущей маркировки не может превысить единицу и допускает реализацию в виде триггера. 4. Вектор начальной маркировки в момент времени k = 0: (5.18) µ0 = [ µ 0 ( P1 ) µ 0 ( P2 )...µ 0 ( Pn )]T , где  0, если материал Pi , i = 1,..., n,  является продуктом ;  µ0 ( Pi ) =  1, если материал Pi , i = 1,..., n ,   является сырьем. Структура расчета себестоимости может быть представлена в виде двудольного ориентированного графа. На рис. 5.4 показан фрагмент структуры расчета себестоимости продукции Новолипецкого металлургического комбината (НЛМК) на примере аглопроизводства. Для удобства восприятия из материалов вида «сырье» взяты только те, которые используются при производстве агломерата (позиция Р26). Материалы вида «сырье», используемые при производстве промежуточных продуктов P1, …, P9, опущены. Вершинами графа являются позиции и переходы, т.е. материалы и моменты расчета себестоимости, которые образуют две доли: Р и Т. Дуги отражают связь позиций и переходов. Позиции изображены окружностями, переходы – отрезками. Взаимосвязь позиций и переходов задается множествами: 1(t j ) – для позиций на входах перехода t j ; 0(t j ) – для позиций на выходах перехода t j .

114

Правило 2. Если в некоторый момент времени разрешены несколько переходов, то срабатывает только какой-то один из них. Иначе, говоря, если есть информация для расчета себестоимости сразу нескольких продуктов, то на конечный результат расчета не влияет результат выбора какого-либо одного из них. Правило 3. В результате срабатывания j-го перехода все равные нулю элементы вектора текущей маркировки µ k , соответствующие позициям из множества 0(t j ) , становятся равными единице, что отвечает появлению ин-

t6

t1 p1

t4

t2

P5

t3

P8 t8

P3

p2

P6

P9 P10 P11

P26

t7

t5 P4

P7 P25

формации об окончании расчета себестоимости для продукта для этого перехода. Пусть Bk ( j ) – вектор размерности m из нулей с единицей на j-м месте (j = 1, 2, ..., m). Этот вектор используется как отражение правила 2. Тогда правило 1 запишется в следующем виде: если µ k = R − Bk ( j ) (5.20) (сравнение векторов производится поэлементно), то переход t j разрешен,

t9

Рис. 5.4. Фрагмент структуры расчета себестоимости продукции ОАО «НЛМК» в виде графа на примере аглопроизводства

Для описания функционирования сети Петри применяется ее матричное представление. В матрицах R + = [ rij+ ] , R − = [rij− ] со строками п и столбцами от строки соответствуют позициям (материалам), а столбцы – переходам (моментам расчета): 1, если Pi - элемент множества 0(t j ); rij+ =  0 в противном случае. (5.19) 1 , если P элемент множества 1 ( t );  i j rij− =  0 в противном случае.  Функционирование данной сети Петри осуществляется в соответствии с основными правилами. Правило 1. В каждый момент времени срабатывает только разрешенный переход t j , т.е. такой, для которого все элементы вектора текущей маркировки µ k , соответствующие позициям из множества 1(t j ) , равны единице. Таким образом, в текущий момент времени можно определить себестоимость только тех продуктов, для которых уже известна себестоимость всех используемых при их производстве материалов. 115

т.е. в текущий момент времени k можно рассчитать себестоимость продукта, за которым закреплен переход t j . Правило 3 для любого момента времени k >0 выглядит следующим образом: µ k = µ k −1 + R + Bk ( j ) , где Bk ( j ) удовлетворяет соотношению (5.20). Последовательно применяя соотношение (5.21), получим

(5.21)

µ k = µ0 + R + B ,

(5.22)

B = B1 ( j ) + B2 ( j ) + ... + Bk ( j ) .

(5.23)

где Очевидно, что k

∑ bi = k ,

i =1

(5.24)

где bi – i-я координата вектора B. Таким образом, текущая маркировка µ k отражает информацию о том, себестоимость каких продуктов производства уже рассчитана и используется в правиле 1, определяющем для текущего момента времени k, все ли составляющие себестоимости для продукта, которому соответствует переход t j , уже известны.

116

t6

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

t8

P5

t1

t3

t2 P1

P2

P8

t5 t9

P3

P6

P9

ходы сработали; это равносильно µ k = [11...1]T – единичный вектор размерности п, B = [11...1]T – единичный вектор размерности m. Важное применение в описанных расчетах находит проблема достижимости в сетях Петри. Пусть заданы структура сети Петри (в матричном графическом представлении); начальная маркировка µ0 конечная маркиров-

P10

P11 P26

ка µ = [11...1]T , т.е. единичный вектор размерности п. Необходимо определить, достижима ли конечная маркировка µ ; иначе: возможно ли рассчитать себестоимость всех продуктов производства при заданной структуре исходных данных и известной себестоимости материалов вида «сырье»? Эта задача сводится к проверке равенства R+ B = µ − µ0 , (5.25) в котором B и µ единичные векторы размерности m и n соответственно. Такая проверка является частным случаем более общей задачи исследования целочисленных систем линейных алгебраических уравнений вида Ах = b на наличие целочисленных неотрицательных решений из множества {0, 1} [45, 46]. Все вышеизложенное справедливо для несколько идеализированной структуры внутризаводских производственных связей, допускающей представление в виде сети Петри с отсутствующими тупиковыми разметками [46]. Однако металлургическое производство характеризуется наличием обратных связей, возникающих в случае, когда часть производимого продукта в дальнейшем используется для производства этого же самого продукта. С учетом этого структура, приведенная на рис. 5.4, примет более сложный вид (рис. 5.5). Обратные связи могут быть как непосредственными, когда часть продукта используется на собственные нужды, например электроэнергия в цехе сетей и подстанций НЛМК (продукт Р4 на рис. 5.5), так и опосредованными, например цепочка из продуктов 3 → 2 → 1 → 3 на рис. 5.5. Такая структура сети Петри уже содержит тупиковые разметки, и поэтому равенство (5.25) не выполнимо. Однако тупиковые разметки могут быть устранены с помощью следующих простых преобразований.

117

t10

t7

t4 P4

P7 P25

Рис. 5.5. Фрагмент структуры расчета себестоимости продукции ОАО «НЛМК» на примере аглопроизводства (с учетом обратных связей)

Для расчета себестоимости продукта, входящего в непосредственную обратную связь, необходимо решить линейное уравнение вида y = x + αy , равносильное уравнению у = х/(1 – а), где у – искомая себестоимость продукта; х – себестоимость используемых в его производстве материалов; α – коэффициент, имеющий тот же смысл, что и α ij в уравнении (5.16). Для расчета себестоимости продуктов, входящих в опосредованную обратную связь, необходимо решить систему из п уравнений с п неизвестными, где п – количество продуктов, входящих в эту обратную связь. Для каждой обратной связи ввиду ее индивидуальности такая система уравнений будет иметь свой уникальный вид. В силу экономического смысла производимых вычислений определители систем будут ненулевыми и каждая из систем будет иметь единственное решение.

118

Заключение

Библиографический список

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

1. Блюмин, С. Л. Линейные клеточные машины: подход пространства состояний (обзор) [Текст] / С.Л. Блюмин, Р.Г. Фараджев // Автоматика и телемеханика. – 1982. – № 2. – С. 125-162. 2. Бутковский, А. Г. Структурная теория распределенных систем [Текст] / А.Г. Бутковский. – М.: Наука, 1977. – 320 с. 3. Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений. – 2-е изд.; пер. с англ. [Текст] / Д. Хопкрофт, Р. Мотвин, Д. Ульман. – М.: Вильямс, 2002. – 528 с. 4. Карпов, Ю. Г. Теория автоматов [Текст] / Ю.Г. Карпов.– СПб.: Питер, 2002. – 224 с. 5. Мелихов, А. Н. Ориентированные графы и конечные автоматы [Текст] / А.Н. Мелихов. – М.: Наука, 1971. – 416 с. 6. Коршунов, Ю. М. Математические основы кибернетики [Текст] / Ю.М. Коршунов. – М.: Энергоиздат, 1987. – 376 с. 7. Сигорский, В. П. Математический аппарат инженера [Текст] / В.П. Сигорский. – Киев: Техника, 1975. – 768 с. 8. Бухараев, Р. Г. Вероятностные автоматы [Текст] / Р.Г. Бухараев. – Казань: КГУ, 1970. – 288 с. 9. Бухараев, Р. Г. Основы теории вероятностных автоматов [Текст] / Р.Г. Бухараев. – М.: Наука, 1985. – 288 с. 10. Поспелов, Д. А. Вероятностные автоматы [Текст] / Д.А. Поспелов. – М.: Наука, 1970. – 178 с. 11. Кузнецов, Л. А. Введение в САПР производства проката [Текст] / Л.А. Кузнецов. – М.: Металлургия, 1991. – 112 с. 12. Кузнецов, Л. А. Автоматизированная система выбора оптимальной технологии производства проката [Текст] / Л.А. Кузнецов, А.М. Корнеев // Известия вузов, Черная металлургия. – 1994. – № 5. – C. 45-48. 13. Блюмин, С. Л. Дискретно-аргументное моделирование систем обработки информации и управления [Текст]: учеб. пособие / С.Л. Блюмин, А.М. Корнеев. – Липецк: ЛипПИ, 1993. – 90 с. 14. Гилл, А. Линейные последовательные машины [Текст] / А. Гилл. – М.: Наука, 1974. – 288 с. 15. Фараджев, Р. Г. Линейные последовательные машины [Текст] / Р.Г. Фараджев. – М.: Наука, 1975. – 248 с.

119

120

16. Блюмин, С. Л. Преобразование сигналов и анализ систем [Текст]: учеб. пособие / С.Л. Блюмин, Л.А. Кузнецов, Ю.П. Качановский. – Воронеж: ВорПИ-ЛипПИ, 1990. – 78 с.

31. Кузнецов, Л. А. Система расчета затрат на производство проката [Текст] / Л.А. Кузнецов [и др.] // Известия вузов. Черная металлургия. – 1998. – № 9. – С. 72-76.

17. Воеводин, А. Ф. Численные методы расчета одномерных систем [Текст] / А. Ф. Воеводин, С. М. Шугрин. – Новосибирск: Наука, 1981. – 208 с.

32. Кузнецов, Л. А. Расчет коэффициентов трудоемкости для определения себестоимости производства трансформаторной стали [Текст] / Л.А. Кузнецов [и др.] // Вестник ЛГТУ-ЛЭГИ – 2001. – № 1. – C. 134-139.

18. Барышев, В. Г. К управлению системами с многомерным параметром [Текст] / В.Г. Барышев, С.Л. Блюмин, Л.А. Кузнецов // Автоматика и телемеханика. – 1977. – № 4. – C. 37-42. 19. Блюмин, С. Л. О дискретизации дифференциально-разностных систем [Текст] / С.Л. Блюмин, Л.А. Кузнецов // Автоматика и телемеханика. – 1978. – № 11. – C. 188-190. 20. Блюмин, С. Л. Соотношения типа Кэли-Гамильтона в теории дискретно-аргументных систем [Текст] / С.Л. Блюмин // Автоматика и телемеханика. – 1981. – № 9. – С. 133-142. 21. Кузнецов, Л. А. Применение УВМ для оптимизации тонколистовой прокатки [Текст] / Л.А. Кузнецов. – М.: Металлургия, 1988. – 304 с. 22. Даджон, Д. Цифровая обработка многомерных сигналов [Текст] / Д. Даджон, Р. Мерсеро. – М.: Мир, 1998. – 376 с. 23. Нейман, Дж. Теория самовоспроизводящихся автоматов [Текст] / Дж. Нейман. – М.: Мир, 1974. – 382 с. 24. Блюмин, С. Л. О конструировании линейными клеточными автоматами [Текст] / С.Л. Блюмин // Автоматика и телемеханика. – 1981. – № 11. – C. 131-138. 25. Мур, Э. Ф. Математические модели самовоспроизведения [Текст] / Э.Ф. Мур // Математические проблемы в биологии / Э.Ф. Мур. – М.: Мир, 1966. – C. 36-62. 26. Блюмин, С. Л. Двумерные m-цепи [Текст] / С. Л. Блюмин // Автоматика и телемеханика. – 1979. – № 10. – C. 58-64. 27. Алберт, А. Регрессия, псевдоинверсия и рекуррентное оценивание [Текст] / А. Алберт. – М.: Наука, 1977. – 285 с. 28. Варден, Б. Л. Алгебра [Текст] / Б.Л. Варден. – М.: Наука, 1976. – 353 с. 29. Кузнецов, Л. А. Расчет себестоимости трансформаторной стали с учетом незавершенного производства [Текст] / Л.А. Кузнецов [и др.] // Современные системы управления предприятием: cб. трудов междунар. науч.-техн. конф. – Липецк, 2001. – C. 119-121. 30. Кузнецов, Л. А. Система расчета затрат на производство проката [Текст] / Л.А. Кузнецов, В.А. Бреус, А.М. Корнеев // Сталь. – 1995. – № 3. – С. 63-64. 121

33. Трахтман, А. М. Основы теории дискретных сигналов на конечных интервалах [Текст] / А.М. Трахтман, В.А. Трахтман. – М.: Советское радио, 1975. – 208 с. 34. Блюмин, С. Л. Конечные преобразования Фурье и анализ конечных систем [Текст]: учеб. пособие / С.Л. Блюмин. – Воронеж: ВорПИ-ЛипПИ, 1991. – 80 с. 35. Блюмин, С. Л. О некоторых математических аспектах цифровой обработки сигналов [Текст] / С.Л. Блюмин, А.М. Шмырин // Радиотехника. – 1975. – № 8. – С. 24-27. 36. Блюмин, С. Л. Моделирование класса систем, состоящих из распределенной и сосредоточенной подсистем [Текст] / С.Л. Блюмин, Л.А. Кузнецов // Управление распределенными системами с подвижным воздействием. – Куйбышев: КПтИ, 1983. – С. 37. 37. Вунш, Г. Теория систем [Текст] / Г. Вунш – М.: Советское радио, 1978. – 288 с. 38. Технология системного моделирования [Текст] / под ред. С.В. Емельянова. – М.: Машиностроение, 1988. – 580 с. 39. Питерсон, Дж. Теория сетей Петри и моделирование систем [Текст] / Дж. Питерсон. – М.: Мир, 1984. – 264 с. 40. Слепцов, А. И. Автоматизация проектирования управляющих систем гибких автоматизированных производств [Текст] / А.И. Слепцов, А.А. Юрасов. – Киев: Техника, 1986. – 110 с. 41. Управление гибкими производственными системами: модели и алгоритмы [Текст] / под ред. С. В. Емельянова. – М.: Машиностроение, 1986. – 368 с. 42. Лескин, А. А. Сети Петри в моделировании и управлении [Текст] / А.А. Лескин, П.А. Мальцев, А.М. Спиридонов. – Л.: Наука, 1989. – 133 с. 43. Васильев, В. В. Сети Петри: параллельные алгоритмы и модели мультипроцессорных систем [Текст] / В.В. Васильев, В.В. Кузьмук. – Киев: Наукова Думка, 1991. – 213 с.

122

44. Блюмин, С. Л. Использование Сетей Петри при расчете себестоимости продуктов металлургического производства [Текст] / С.Л. Блюмин, Ю.В. Машковцев // Известия вузов. Черная металлургия. – 1995. – № 10. – С. 74-77. 45. Грегори, Р. Безошибочные вычисления [Текст] Е. Кришнамурти. – М.: Высшая математика, 1988. – 208 с.

/

Р.

НАУЧНОЕ ИЗДАНИЕ

Грегори,

46. Иванов Н. Н. / Н.Н. Иванов// Автоматика и телемеханика. – 1991. – № 7. – С. 125-130.

Блюмин Семен Львович доктор физико-математических наук, профессор Корнеев Андрей Мстиславович кандидат технических наук, доцент

УДК 62.529+669:162.24 ББК 32.965.6

Б71

Блюмин С.Л., Корнеев А.М. Дискретное моделирование систем автоматизации и управления: монография. – Липецк: ЛЭГИ, 2005. – 124 с.

ISBN 5-900037-47-9 Представлены подходы к построению дискретных моделей, базирующихся на клеточной интерпретации; рассмотрены дискретные пространственные, дискретные пространственно– временные, конечно-аргументные модели. Технологический процесс представлен в виде клеток, каждая из которых соответствует отдельному технологическому агрегату или переделу. Использование конечных и вероятностных автоматов, итеративных цепей и сетей позволяет описать любой сложный технологический процесс и осуществлять управление технологией.

Техническое редактирование

Н.С. Правильниковой, И.Ф. Ковешниковой

Подписано в печать 21.11.2005. Формат 60х84/16. Бумага 55-60 г/м². Гарнитура «Таймс». Усл. печ. л. 7,75. Тираж 200 экз. Заказ № 904. Цена свободная. Липецкий эколого-гуманитарный институт. 398600, г. Липецк, ул. Интернациональная, 5а

123

124

Таблица 1.1 Таблица переходов и выходов конечного автомата

v1, …, vm

x'1, …, x'n

y1, …, yl (для КА Мили)

y'1, …, y'l (для КА Мура)

. . .

. . .

. . .

b1′Jt ,..., bkJ′ k ,..., bnJ′ n .

c1 j1 ,..., c pj p ,..., cljl

c1 j1 ,..., c pj p ,..., cljl

(ξβ) . . .

(τγ) . . .

(τ’γ) . . .

X1,

…, X n

b11′ ,..., bk′1 ,..., bn′1 (ξ'1) … a11,…,ai1,…,am1 (σ1)

b1′j1 ,..., bkj′ k ,..., bnj′ n (ξ'β) …

b1′Jt ,..., bkJ′ k ,..., bnJ′ n …..

a1 j1 ,..., aiji ,..., amjm (σα) …..

a1J1 ,..., aiJ i ,..., amJ m (σА)

(ξ'В) ….. (ξ'1) … (ξ'β) … (ξ'В) ….. (ξ'1) … (ξ'β) … (ξ'В)

1

Таблица 1.2 Таблица переходов автоматов Мили и Мура

х'1, …, x'n v1, …, vm

b1′l ,..., bkl′ ,..., bnl′ (ξ'1 )

…

b1′j1 ,..., bkj′ k ,..., bnj′ n (ξ'β)

…

b1′J1 ,..., bkJ′ k ,..., bnJ′ n (ξ'В )

a11, …, ai1,…, am1 (σ1) …

(σα)

. . . b1′j1 ,..., bkj′ k ,..., bnj′ n

…

. . .

a1 j1 ,…, aiji ,…, amj m

a1J1 ,…, aiJ i ,…, amJm (σА)

2

Таблица 1.3 Таблица выходов автомата Мили

x'1, …, x'n v1, …, vm А11, …, ai1, …, am1 (σ1)

b11′ ,..., bk′1 ,..., bn′1 (ξ'1)

…

b1′j1 ,..., bkj′ k ,..., bnj′ n (ξ'β)

…

b1′J1 ,..., bkJ′ k ,..., bnJ′ n (ξ'В)

… a1 j1 ,..., aiji ,..., amjm

. . .

(σα)

c1 j1 , …, c pj p , …, clj l

…

. . .

a1J1 ,..., aiJ i ,..., amJ m (σА)

3

Таблица 1.23 Таблица выходов с одним входом для k-го передела

vk 1 , ... , v kLk

ak11 ...aklk 1 ...akLk 1 (σ 1( k ) )

zk1 , ... , z kG

y k1 , ... , y k P

x k −1,1 , ... , x k −1, M k − 1

k

k

b(k −1)11,..., b(k −1)mk −11,..., b(k −1)Mk −11

(ξ ) 1(k −1)

b(k−1)1j1k−1 ,..., b(k−1)mk−1jmk−1 ,...,b(k−1)Mk−1 jMk−1

(ξ ) β(k−1)

...........

b( k−1)1J1k −1 , ..., b(k −1) mk −1Jmk−1 , ..., b(k −1) Mk −1JMk−1

(ξ

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

ak1j1 ...aklk jk ...akLk jk σ α( k )

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

ak1J1 ...aklkJlk ...akLkJLk σ A( k )

Β ( k −1 )

)

(ξ ) 1( k −1)

(ξ )

…

ck1 j1 ... ckrk jr ... ckRk jR

(τ ) k

γ (k )

k

dk 1 j1 ... dkgk j g ... k ...dkGk jG

(ϕλ(k) ) k

β ( k −1)

(ξ ) Β(k −1)

(ξ ) (ξ ) 1( k −1)

β( k −1)

(ξ ) Β( k −1)

4

Таблица 1.35 Вероятности получения свойств для различных режимов

V( k +1)1 ...V( k +1)( k +1)

x11 .. x1 M 1

xk1 ..xkM k

σ 1( 2 )

σ1(k+1)

ξ1(1)

ξ1( k )

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

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

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

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

σA(k+1)

ξ B( 1 )

ξ B( k )

V 11 ..V 1 L 1

V21..V2L2

σ 1(1) . . . . . . . . . . . . . . . .

σ A(1)

σ A( 2 )

..

. . . .

P1( k +1) … Pγ ( k +1) … PГ( k +1) Pτ1( k +1 )

… Pτ

γ ( k +1)

…

Pτ Г( k +1)

. . . . . . . . . .

P(C(k+ 1)

11 C (k+1 ) R (

, ...,

C (k+1)r k+1 1 , ...,

… P(C(k+1)j

1(k+1)

1) k+1 )

, ..., C(k+1)r

C(k+1) R k+1J R k+1

… P(C(k+1)1J

1(k+1) C(k+1) R k+1 J R

, ..., C(k+1)r

j k+1 rk+1

)

j k+1 r k+1

, ...,

, ...,

) k+1

5

k

k – номер передела

x xk −1, Nk −1 ,1 xk −1, Nk −1 , Mk −1

xk 2( m1 +1)

xk11

1

xk1m1

2

x

i−2

kik −1 (

∑ mj +1)

i −1

kik (

∑ mj +1)

ik

xk 2( m1 + m2 ) … x kik −1 (

i −1

∑ mj ) j =1

x

∑ mj +1)

kik (

x i

∑

mj )

k ( Nk −1 )(

N k −1

kN k (

j =1

∑ m j +1) j =1

Nk

… x

x

N k −2

k ( Nk −1 )(

j =1

j =1

Nk −1

∑ mj )

xkNk M k

j =1

j =1

Рис. 2.16. Представление внутренней итеративной цепи

6

Таблица 3.1 Переходы и выходы одномерной однонаправленной нелинейной итеративной сети для клетки s в момент времени t um [t,s]

x1 [t,s-1],...,xn[t,s-1]

ξ1 [t-1,s],…,ξ1[t-1,s]

(a11,…ai1, ...,aml)

χ1 M χβ

ψ 1 , ..., ψν , ..., ψ N M ψ 1 , ..., ψν , ..., ψ N M ψ 1 , ..., ψν , ..., ψ N

σ1 M

(aj1,…aiji, ...,amjm)

σa

(aj1,…aiji, ...,amjm)

σA

M χB χ1 M χβ M χB χ1 M χβ M χB

ψ 1 , ..., ψν , ..., ψ N M ψ 1 , ..., ψν , ..., ψ N M ψ 1 , ..., ψν , ..., ψ N ψ 1 , ..., ψν , ..., ψ N M ψ 1 , ..., ψν , ..., ψ N M ψ 1 , ..., ψν , ..., ψ N

ξ1 [t,s],...,ξ1[t,s]

c 1 j1 ,...., c p j p ,...., c m jm

(ψ ν )

c 1 j1 ,...., c p j p ,...., c m jm

(ψ ν )

c 1 j1 ,...., c p j p ,...., c m jm

(ψ ν )

x1 [t,s],..,xn [t,s]

b1 j1 ,...,brjr ,...,bnjn ( χβ )

b1 j1 ,...,brjr ,...,bnjn ( χβ )

b1 j1 ,...,brjr ,...,bnjn ( χβ )

У1 [t,s],..., yk [t,s]

d1 j1 ,...,d qjq ,...,d kjk

(τ γ )

d1 j1 ,...,d qjq ,...,d kjk

(τ γ )

d1 j1 ,...,d qjq ,...,d kjk

(τ γ )

7

Таблица 3.2

Функция переходов автономного ККА

x ( t − 1; c1 ; c 2 )

x ( t − 1; c1 − 1; c 2 )

x ( t − 1; c1 + 1; c2 )

x ( t − 1; c1 ; c 2 − 1)

x ( t − 1; c1 ; c 2 + 1)

x ( t ; c1 ; c 2 )

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 -

8