Оптимизация последовательности действий при совместном функционировании объектов или систем с учётом синергетических эффектов

При решении многих практических задач может возникать необходимость совместного использования нескольких однородных или разнородных объектов или систем. При этом действия одних объектов или систем и их последовательность могут существенно влиять на действия других [1]. Примером такой задачи является использование подразделений силовых ведомств при ликвидации чрезвычайных обстоятельств (ЧО) [2, 3].

При функционировании сразу нескольких взаимодействующих систем или объектов могут возникать ситуации конфликта, безразличия или содействия, приводящие к появлению как положительных, так и отрицательных синергетических эффектов [1]. В ряде случаев удаётся получить численные оценки этих эффектов. В частности, в [4] построена модель оценки влияния взаимодействия подразделений силовых ведомств при возникновении ЧО на величину предотвращенного ущерба. Указанная величина зависит от времени начала выполнения действия каждым подразделением и имеющегося ресурса.

В [5] показано, что процесс функционирования подразделений силовых ведомств при ликвидации ЧО является динамической системой и, следовательно, эффективным аппаратом моделирования действий таких подразделений является теория конечных автоматов [6]. В связи с необходимостью моделирования координации действия сразу нескольких подразделений следует использовать общую автоматную модель, агрегирующую отдельные модели функционирования всех взаимодействующих подразделений. Для этого могут использоваться операции последовательной и/или параллельной композиции автоматных моделей отдельных подразделений [7]. Численный метод агрегирования автоматных моделей с использованием алгебры символьных матриц описан в [8].

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

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

Агрегируемые в процессе моделирования отдельные взаимодействующие объекты или системы будем называть составляющими. Рассмотрим автомат, описывающий действия отдельной b -й составляющей общей модели:

AbЦ Хь, Yb, Qb, Fb), (1) где Хь — входной алфавит, описывающий входные воздействия на объект (систему), Yb - выходной алфавит, Qb - множество состояний, в которые могут переходить составляющие общей модели в результате поступления входных символов из Хb, Fb - оператор, описывающий пере- ходы из состояния в состояние и соответствующие им выходы в зависимости от поступающих входов, представляемый в следующем виде:

{Fbqb - {qb (x Iy)..... qb (xb / yb).....qb (xj । ykni)},- - i0}.

Запись q^ (x; I yk) e Fbqb означает, что если автомат находится в состоянии qb и на вход посту-j                                                                    ik пил символ x l , то автомат переходит в состояние q l и выходным символом является y l .

Моделирующий совместное функционирование m объектов или систем автомат

A - ( Х , Y , Q , F )

представляет собой композицию m автоматов вида (1), численный метод его построения описан в [8]. Элементы автомата (2) определяются следующим образом:

Х - входной алфавит, элементы которого xj e X имеют вид xj -{xj1,—,x;s},s - |xj| < n, где каждый xj| представляет собой действие автомата Ab ;

Y - выходной алфавит, элементы которого yk e Y имеют вид yk -{yk*,—,yks},s - |yk| < n, где каждый ykl представляет собой результат выполнения действия автомата Ab ;

Q - множество состояний, элементы которого q i e Q имеют вид q i - { q /¹

q n } ,^где q A b

состояние, в котором находится автомат A_b , при этом исключены недопустимые с точки зрения предметной области комбинации состояний;

F - оператор, описывающий переходы из состояния в состояние и соответствующие им выходы в зависимости от поступающих входов.

В автомате (2) могут возникать возможности альтернативного выбора комбинаций действий отдельных составляющих, и, следовательно, возникает задача оптимизации выбора комбинаций действий. Однако эта задача может быть решена только при конкретизации описаний результатов действий отдельных составляющих. Приведём такое описание применительно к действиям подразделений силовых ведомств при ликвидации ЧО [2, 4].

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

Общий предотвращенный ущерб на протяжении всего времени выполнения действий по ликвидации ЧО монотонно возрастает [2, 4, 9]. Действительно, чем дольше осуществляется ликвидация ЧО, тем большее количество людей можно эвакуировать из зоны ЧО и сохранить больший объём материальных ценностей. Вместе с тем, чем позже будет выполнено какое-либо конкретное действие по ликвидации ЧО, тем оно будет менее эффективным и, следовательно, приведёт к меньшему значению предотвращённого ущерба. Поэтому каждое действие каждого подразделения силовых ведомств характеризуется величиной предотвращенного ущерба в зоне ЧО в момент начала совершения этого действия.

Кроме того, предотвращенный ущерб зависит от момента начала действия, т. е. если подразделение находится в некотором состоянии qⁱ , то предотвращенный ущерб от совершения одного

Математика

и того же действия в моменты времени t и t^j + A t может быть различен [9]. Для пояснения рассмотрим пример эвакуации граждан и материальных ценностей из зоны ЧО: при первом и втором этапе эвакуации её объём может быть различен в силу изменения обстоятельств [4].

Для совершения каждого действия подразделения расходуют определённый ресурс, который для каждого подразделения описывается ограниченной функцией времени [4]. При переходах из состояния в состояние подразделения расходуют или восполняют определенное количество ресурсов. Время является ограниченным параметром.

Каждое действие подразделения в состоянии qbi при поступлении на вход x j охарактеризу- ется тремя параметрами [4, 9]:

^pb = { ^pb i , ного ущерба);

...

, p bf } - предотвращенным ущербом ( f_p - количество категорий предотвращен-

kk r b = { ^rb 1 ,

...

, r f } - ресурсы ( f_r - количество категорий ресурса);

t_b^k – время.

Таким образом, элементы yk е ¥ь представляют собой кортеж k    k kk yb = \pb , rb , tb / .                                                (3)

В таком случае в автомате (2), моделирующем совместное функционирование подразделений, элемент y^k е Y имеет вид y^k = { y k 1 ,...,y k s } , s = | y^k | ^ n , где каждый y k l представляет собой кортеж вида (3).

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

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

Процесс ликвидации ЧО должен быть организован таким образом, чтобы максимизировать предотвращенный ущерба в зоне ЧО при ограничениях R и T – соответственно на выделенные ресурсы и отведённое время для ликвидации ЧО, что достигается оптимизацией последовательности действий подразделений, которая может быть описана как модель оптимизации выбора

.* 1 1

,...

последовательности входных символов X = ( x

, x * i n ) автомата (2). При этом величина n ап-

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

( i-     ,'   s-1      1„/

и

Для поиска данной последовательности введем функции p q ^s , x^{J s} , V т ( q^h, x^{J h} )

У         h=0

(         s - 1

R q i s , x^Js, V t ( q^h, x^Jh )

I          h = 0 ^X

, где т(q1, x* ) - время, необходимое для перехода из состояния qlh при входе x jh . Данные функции отображают величину предотвращенного ущерба и количество ресурсов соответственно от действий подразделений в соответствии с входным символом x js

1s-1

при нахождении автомата (2) в состоянии q i s в момент времени V t ( q h , x^Jh ) . При этом

h=0

R ( q i s , x * ,0 ) - начальное количество ресурсов у подразделений.

В этом случае решаемая задача имеет вид нахождения

X * = Argmax V ^р q‘^s, x

X      s =1   I

js

s -1

, V T (qh, xh )| , h=0 V       v)

при ограничениях:

о <  r q i s , x^js

s -1   ,

, ^r (qh, xj h=0

) + r ( q i , x^j ) < R ,

^ t ( q i s , x^j ) < T ,                                       (6)

s = 1

q i ^{+ 1} ( x^j / y k l ) e Fq i ,l = 1,..., n - 1.                                   (7)

Условия (5) и (6) описывают требования по выполнению ограничений на соответственно ре- сурс и время; в частности, в (5) r(qis, xjs) - вектор значений изменения ресурсов при переходе из состояния qis автомата (2) по входу xjs . Условие (7) определяет корректность последовательности смены состояний в автомате (2).

Описание численного метода

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

Задачи, решаемые с использованием схемы ветвей и границ, различаются тремя составляющими: способом построения дерева частичных решений, методом оценки частичных решений и обходом построенного дерева решений. В данной работе описываются только указанные составляющие, считая известной общую схему [8, 9].

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

X t = ( x i ¹ ,..., x i ) ,                                                (8)

Указанные подмножества образуют дерево частичных решений, вершинами которого являются последовательности вида (8), а дуги направлены от X t к X t ^{+ 1}, причём принимается, что X ⁰ содержит все возможные последовательности.

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

t

Ф ( X t ) = £ Р s = 1

( qis, Xs V

s -1   /           \^

, ^ T ( q i , x^jh )

h = 0             ⁷ J

+ max p q , X'

x ^j e X

V

■^j , ^ t ( q i h , x^jh ) h = 0             ⁷ J

T - ^ T ( q^h , x^jh ) h =0 _____________ min t \q^lh , x^j | xj e X           /

где T - ^ t ( q¹¹¹ , x^j ) /min t ( q h , x^j )

h =0  ⁷          ! ^x ^X ^{7        7}

– максимальное количество итераций, которое может со-

h

вершить автомат (2) за оставшееся время.

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

На первом шаге обхода дерева частичных решений производится поиск начального решения. Спуск по дереву осуществляется до тех пор, пока выполняются условия (5)–(7). Если условия (5), (6) или (7) не выполняются, то обход дерева решений по данной ветви не продолжается и происходит подъем на один уровень. Когда пройдена вся ветвь, также происходит подъем на один уровень. Окончание первого шага наступает, когда достигнута конечная вершина дерева решений или невозможно достичь конечной вершины, т. е. задача не имеет решения. В последнем случае следует пересмотреть ограничения (5) и (6).

Математика

После того как достигнута конечная вершина, соответствующее ей решение X ^{t 1} представляет собой начальное решение и называется рекордом. Соответствующие ей оценки обозначим Ф t ¹ .

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

• 1)    обход будет начинаться с вершины, находящейся на уровень выше начального решения;

• 2)    к условию (5)–(7) добавляется условие

ф( Xt ) >Ф t1

При выполнении следующих шагов могут возникнуть следующие ситуации:

• 1)    если ф ( X t ) >Ф t ¹   и выполняются условия (5)-(7), то соответствующая вершина

становится рекордной, а ее оценка – новым временным рекордом;

2)если ф ( X t ) <Ф t ¹ , то спуск по дереву решений прекращается и осуществляется подъём на один уровень.

Если на очередном шаге не удастся достичь конечной вершины, то выполнение алгоритма заканчивается и решением задачи (4)–(7) объявляется последний рекорд.

Заключение

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