Согласованное управление в двухуровневых иерархических системах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

КАЗАХСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ: УНИВЕРСИТЕТ имени АЛЬ-ФАРЛБИ

Г 5 ОД Ь СЕН ЬЗЛ

На правах рукописи

Ыустефаева Алча Кдиаяовна

УДК 519.8

СОГЛАСОВАННОЕ УПРАВЛЕНИЕ В ДВУХУРОВНЕВЫХ ИЕРАРХИЧЕСКИХ СИСТЕМАХ

01.01.09 - Математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Амати - 1995

Работа выполнена в Казахском Государственном Национальном Университете им. Аль-Фараби.

Научный руководитель: кандидат физию математических

наук, доцент Мухаиедиев В.М.

Офицальные оппоненты: доктор Физико-математических

наук, профессор Айдарханов М.Б.

кандидат физико-математических наук, СНС Конурбаева Б.М.

»

Ведущая организация: . Институт Теоретической и Прикладной Математики НАН РК

Защита состоится "б" октября .1995 г. в 15°° часов на , заседании регионального специализировашюго Совета К 14/А 01.03 при Казахском Государственном Национальном Университете им. Аль-ФараОи по адресу:

430012, г. Алматы, ул. Масанчи 39/47, КазГУ, механико-математический факультет.

С диссертацией можно ознакомиться в библиотеке КазГУ.

Автореферат разослан " ^Г» Сентября 1995 г.

Ученый секретарь специализированного Совета К 14/А 01.03, 1

к.ф.-м.н., доцент Ш-А-Айпа»0*»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Б диссертационной работе в основу изложения положен подход к управлению сложными системами, который разрабатывался коллективом ученых под руководством академика Н.Н.Моисеева и профессора Ю.Б.Гермейера, и заложил основы информационной теории иерархических систем управления. Рассматриваются системы, состоящие из ряда подсистем, положение которых неравноправно и зависит от уровня, на котором расположена данная подсистема, причем кавдая подсистема обладает заданной свободой действий и собственными целями. Цели центра, расположенного на верхнем уровне считаются отражением назначения системы в целом. Центр может в какой-то степени воздействовать на возможности выбора подсистем, влиять на формирование та целей, вырабатывать механизмы согласования интересов, однако процессу управления в иерархической системе всегда присуща та или иная степень децентрализации и ее функционирование определяется совокупностью целей всех подсистем.

«

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

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

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

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

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

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

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

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

Предложены различные варианты сведения динамической задачи иерархического управления с дискретным временем к последовательности статических задач, к которым применим разработанный автором метод. Получена оценка для погрешности аппроксимации непрерывной задачи путем .дискретизация по времени. Результаты исследований проиллюстрированы на тестовых примерах. Прилагается программа на языке ФОРТРАН, численно реализующая разработанный автором метод.

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

Апробация работы. Материалы диссертационной работы докладывались и обсуждались на IX Республиканской межвузовской научной конференции по математике и механике (Алма-Ата,1989 г.), на межвузовской конференции-конкурсе молодых ученых и специалистов КазГУ (Алма-Ата,1990 г., диплом за высокий научный уровень доклада), на конференции, посвященной 50-летию КазГУ им. Аль-ФараОи (Алматы, 1994 г.), на научных семинарах кафедры вычислительной математики и компьютерных технологий (руководитель д.ф.-м.н., проф. Ш.С.Смагулов), на объединенном семинаре кафедр теории управления и мзтематэтеской кибернетики (руководитель д.т.н., проф.С.А.АйсагалиеЕ).

Структура и объем работы. Диссертационная работа изложена на 110 страницах машинописного текста и состоит из введения, двух глав, заключения, приложения с численными результатами проведенных исследований и списка [датированной .литературы. Диссертация содоркит 6 рисунков, список литературы из ЬЬ паи-

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

СОДЕРЖАНИЕ РАБОТЫ.

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

В главе I рассматриваются статические модели иерархических систем управления. Излагаются основные понятия теории иерархических игр» рассматриваются вопроса построения математических моделей многоуровневых систем управления, приводится ■ постановка задачи двухуровневой иерархической игры.

Пусть множества допустимых управлений обоих уровней задаются следующим образом:

и - { и«1Г Ц^Цл)«. 1-М }

У(Ц)= 1=1,3 },

где Г.(и)в & (и,у) - выпуклые функции. Будем считать, что и и У(и) - выпуклые ограниченные замкнутые множества.

При известном управлении и первого игрока оптимальное управление второго игрока определяется из решения задачи тах С(и,7) (1).

У£У(и)

Предполагается выполненным условие ненасыщения:, максимум в (1 > при всех иеи достигается на границе мноквства \Г(ц).

Цель первого игрока так выбрать управление иеи, чтобы максимизировать свой критерий эффективности 1Чи,?(и)), где у(и) -решение задачи (1). Целевые функции обоих уровней У(и,у) и 0(и,V) будем предполагать вогнутыми. Верхний уровень

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

?*' max гаах F(u,v) , (2)

ueu vew(u)

где

W(u) = Arg raar G(u,v) - (3)

vtV(u)

множество оптимальных откликов второго игрока на ход первого. Обозначим через Q множество вида: Q = ( <u;y) | ueU, veV(u)*0 j .

• ЛЕША 1.1 Пусть U, V - компактные множества из про

странств векторов и и v соответственно, VC): и V - многозначное отображение, непрерывное на U, функции F(u,v), G(u,v) непрерывны на UxV. Тогда многозначное отображение 'Я(и) замкнуто на U и задача (2) имеет решение.

Известны следующие утверждения:

1. В предположении выполнения условий леммы 1.1 и условия ненасыщения для нижнего уровня решение задачи (2) достигается в крайней точке ограниченного множества всех управляющих переменных (в наших обозначениях множества Q).

2. Множество

w = { (u.v)eq i uéu, v€w(u) |

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

Выберем любую допустимую точку u éU и' решим для неё за-

дачу (1). Это задача выпуклого программирования, и для неб существуют специальные методы решения.

voç Arg max G(uo,v). v€V(u0)

Точка (uo,vo) будет граничной точкой множества Q

Q = { (и,▼) I q.(u,v)«0. 1=1,1+3 }, (4)

и через неё можно провести хотя бы одну опорную гиперплоскость £ = a4u + av. где

(^,0,)= I agrad Wvj,

а- const, а>0, 10 - совокупность номеров 1 ограничений (4), которым точка (uo,vo) удовлетворяет как равенствам.

Заметим, что для линейной задачи опорную гиперплоскость можно построить, используя двойственную к (1) задачу линейного программирования [41.

Так как множество Q лежит по одну сторону от опорной гиперплоскости, то для V(u,v)ç Q и некоторого-5>0 справедливо a u+a y < а и +а v ,

й z л о 2 о

а та 7 í au +av- ô .

ä 2 & О 2 О

Определим следующие »тожества

Q0(ö) = { (u,v)fQ I atmas7 > atuo+a3vo- ö }

Vo(0,u) = {veV(u) I (u.vKcyö) },

Do(0) - { U€U I Yo(S,u)^0}.

ШШ 1.2 На множестве U0 (Ö) справедлива следующая оценка

t

a(u) = max F(u,v) < max P(u,v)= ß„(u). vew(u) vevo(ö,u) ;

Обозначим P0(u„0)= max^(3o<u) , utoeU (5) a(u#D)= шах (cu -t-av) (6)

Выберем любую другую допустимую точку и4 из множества ЦЧ0о(в) и решим для нее задачу (1). Проводя аналогичные рассуждения, определяем множества Qt(8), Vt(6,u), Ut(6) и значение At(e),pt(u$t),a(uM). Получаем последовательность значения (A^BhP^u^.aiu,,.)) на множествах U.(0).

ЛЕША 1.3 Для любого числа 6>0 метод позволяет за конечное число шагов покрыть исходное множество U множествами ^(0), т.е.

U с U Uv(6)

ISO

Если найдутся номера 1,J, lJ=07Tc, такие что выполняется : a(u*> > P/V' то множество 1^(0) "неперспективно",и в дальнейшем его можно исключить из рассмотрения, так как

a(uw')> шах a(u). иеи.(в)

На следующем шаге, исключив все "неперспективные" множества, определим

. U'= U U (б) , (7)

i«o 1

уменьшим число в, и повторим все приведенные pac<;>xn};<w{ а самого начала, заменив U на У*. Вычисления производятся до тех

пор» пока для некоторого 10:

10= arg max ßt(u,t) i =0 . k

не получаем A^s -е, где е - заданная точность нахождения решения задачи (1 )-(3).

ТЕОРЕМА 1,1. Пусть найдена точка пщо. для которой е. Полученное таким образом a(u„io) есть искомое решение задачи двухуровневого управления с заданной точностью е, реализующее его u4v0 - s-оптимальное управление верхнего уровня, a v„.o-оптимальный отклик нижнего уровня.

Проведено исследование вопроса сходимости метода.

ТЕОРЕМА 1.2 Для любого е>0 предлагаемый метод мажориру-ицих оценок позволяет за конечное число итераций, найти точку • u^iU, для которой

Р* - a(u,io) * е

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

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

дов, а в пределе и на непрерывный случай.

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

. к=0ЛМ , (8)

где хк - вектор фазовых переменных, описывающих состояние системы в момент времени k, uk,vk - значения управляющих воздействий центра и подсистемы в момент времени к, xk,u)r,vl -элементы конечномерных евклидовых пространств.

Xkexk k=ü7H , uleuk(xk)cuk, vVWcVk k=ü7TPT. (9) Введем "расширенные" векторы, множества и отображения:

х=(х0.,...,хм), U=(UQ.....V=<Vo.....V«)-

X=XD»X1....»XN, U=U0«Ut«.... «üM_t, V=Vo«Vs»... "VMi B(*)-Hn U^)» V(x,ti)=Nn,Vl(xk,uk), W(x,u)=NníWk(xk,u)()

V&o kso ksO

Критерии эффективности первого и второго игроков могут быть заданы в терминальном виде

i(i,u,t)= ff^) - (10)

J(X,U»7)= G(X^) (11)

при дальновидном поведении подсистем, и в виде

Зъ 55 WW • (12)

при одаошаговом горизонте планирования подсистем (недальновид-

нов поведение).

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

х = ф(и,У) (13)

гпах шах 1(ф(и,у)),и,у)= шах 1(ф(ц*,у),и*,7). (Н) щи уеИ»(и) чеЩи*)

ЛЕША 2.1 Если и , Ук являются компактами, многозначные отображения иь (' >: Х^»^, Ккх1!к*7к непрерывны, функции Гк(хк,и1[,Ук), I(х,и,у) и Л(х,и,у) непрерывны по совокупности аргументов, то многозначное отображение *?(•) замкнуто, и задача (14) имеет решение, то есть и* существует.

Построены вычислительные алгоритмы решения динамической игры (14) для управлений вида ц=и, 7=7(и) (программное управление центра с одноразовой передачей информации) при дальновидном поведении нижнего уровня и для управлений и={ик(хк)), 7={ук(хк,ик)) (управление центра в форме синтеза с пошаговой передачей информации) при недальновидном поведении нижнего уровня.

Проведено теоретико-игровое исследование конкретной динамической экономической модели распределения дефицитного ресурса между независимыми производственными процессами.

хк=(х^.....х^) - вектор фазовых переменных, определяет запасы

Э видов ресурсов у Центра в начале периода к.

... - вектор управляющих воздействий Центра, определяет количество ресурса наделенного Производителю. Ук=(у£,....V™) - вектор управляющих воздействий Производителя, определяет интенсивности производственных процессов в период к.

* Л VI' т

С- К ^ <15>

х(0)=хо к=0Л5,

т

\<Ч«>: I ^^ < <16>

а*»

г

■ ^ < ^ к=0. (17)

Р = сх„„ , Ск=ькук (18)

Задача Центра при доброжелательности никнего уровня запи-вется еледущим. образом

I* « шах шах ... тах шах (20)

Ч,««» <*о > ■ ^о Ч ) Ч > V« Ч > +

где множества реакций нижнего уровня определяются так-

же как и в статическом случав.

Запасы фондообразующего ресурса определяются первой компонентой вектора х: к

ТЕОРЕМА 2.2 Управление верхнего уровня и со-

ответствующее ему на каждом шаге управление нижнего уровня у*(и*), будут оптимальными управлениями в многошаговой

ирархической игре (15)-(20) тогда и только тогда, когда на каждом шаге ¡с=0,К-1 они доставляют максимум промежуточному критерия вэрхнего уровня х^ на множестве ик(хк)«!?к(ик), а на последнем шаге N являются решением статической задачи иерархического управления

max „ шах „. Vl(^)

Из теорему следует процедура вычисления решения многоаа-

»

говой Hi'p« (15)-(20) в виде реиения последовательности статических задач иерархического управления, к которым применим метод главы I.

В последнем разделе второй главы исследованы вопросы аппроксимации непрерывной иерархической игры вида (23) иерархической игрой с дискретным временем вида (24):

X~AX+BU+Cy Х(0)=Хо

U(x): Ku+Hx+hX) (23)

V(х,u): Eu+Dv+Rx+d<0 (Kt^T

?(x(T))= cx(T) ►max

G(v(t))= bv(t) * шах где x.u.v, h,d - векторы, .A,B,C,D,E,K,H,R - матрицы соответствующих размерностей.

^WW» Zo=Io

Kuv+Hzk+hii) (24)

Eu)t+D7)(+Rzt+d^0 k=07fPT

F(zn)=czm *> шах

G(vk)=bvk »• шах

ТЕОРЕМА 2.3 Оптимэльное значение Функционала первого игрока в непрерывной иерархической игре (23) и оптимальное значение функционала первого игрока в многошаговой игре (24) связаны соотношениями

l?*(x*(T)bF*(Ol* 0(т) ■

где т=Ы! - диаметр разбиения о отрезка СОД]. Основные результаты диссертации.

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

2« На оснований теоретико-игрового подхода и с использованием аппарата теории иерархических кгр рассмотрена статическая задача двухуровневой оптимизации в иерархических системах, разработан и предложен новый метод решения данной задачи. Выделим его преимущества:

- ИрйМэйиы как для линейных, так и для более широкого класса выпуклых задач; . .

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

- позволяет построить решение с заданной точность»;.

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

3. Построен реализующий этот метод алгоритм, сходящийся за конечное число итераций. Приведен текст программы на языке ФОРТРАН с результатами численных расчетов.

'4. Распространено применение разработанного автором ме-

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

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

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

1. Мустгфаева Л.И. Линейная игра двух лиц с несовпадающими интересами. //Рук.деп. в НазГосИНТИ 04.08.Э4. -Яб216-К94,-7с.

2. Мустгфаева А.и. Линейная дифференциальная игра двух объектов при налички сил трэшя с дискретными наблюдениями. //Рук.деп. в КазГосИНТИ 04.08.94. -.№5217-К94,-9с.

3. Мустафаева А.И. Динамические иерархические системы с последовательными управляющими воздействиями верхнего уровня. //Весник КазГУ, -Алматн, 1995, -60.

4. Мустафаева А.И. Линейная игра диух лиц при доброжелательности второго игрока. //Тезисы докл. конференции-конкурса молодых ученых и специалистов КазГУ им.С.М.Кирова. -Алматы, 1990, -с.14.

5. Мустафаева А.И., Мухаыедиев Б.М. Линейная дифференциальная

игра с дискретными наблюдениями. //Тезисы докл. Реснубли-

/

канской конференции по математике и механике. Алма-Ата, 1989, -с.133.

. Цуста&аева Aliwa Ндияклзы

Eni сатили нерархкюищ яуйедег! кед1с1лген мегеру.

Диссертацияда экономикалык, салада кец таралган оптималды мецгеруд1ц ек! сатылы системасы кдрастырылган. Иерархиялик бас-кдрудыц жац eflici жене ойын 1ске асыратыц алгоритм! к^растырыл-гал.

Бул ед!ет1н динамикалы^ есептерд! шешуде и,олдацуга болатын-дыгы керсет!лген. Алынган гылымы нетюкелер компьютерд1ц квмет!л-ген есептел!нген. Усынылып отырган ед1с ресурсты таратудыц ди-намикадык модел!нде колданылган.

liustafayeva Alma Idianovna

Co-ordinate control in two-level

hierarchical systems

Dissertation consider the problems of information theory of hierarchical systems, which Is the moat natural language to describe problems oi optimal control In large multilevel economic systems.

Subject of conducted research la an evaluation of new method, determining optimal control In two-level system, and realization of thi3 method aa computational algorithm.

Several techniques based on this method are developed for dynamic two-level problems of control. Results are illustrated on the model of allocation of scarce resources, and stimulation of Its rational use.