О решении и свойствах простейшей динамической задачи оптимального разбиения множеств
Наведено математичну постановку найпростішої динамічної задачі оптимального розбиття множини n-вимірного евклідового простору. Доведено теорему про редукцію цієї задачі до сім’ї задач оптимального керування системою з зосередженими параметрами. Отримано в аналітичному вигляді і досліджено оптимальні...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schriftenreihe: | Проблемы управления и информатики |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/207619 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О решении и свойствах простейшей динамической задачи оптимального разбиения множеств / Е.М. Киселева, Л.С. Коряшкина // Проблемы управления и информатики. — 2013. — № 3. — С. 102–112. — Бібліогр.: 4 назви. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-207619 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2076192025-10-12T00:09:00Z О решении и свойствах простейшей динамической задачи оптимального разбиения множеств Про розв’язання та властивості найпростішої динамічної задачі оптимального розбиття множин On the Solving and the Properties of the Simplest Dynamic Optimal Set Partitioning Problem Киселева, Е.М. Коряшкина, Л.С. Методы обработки информации Наведено математичну постановку найпростішої динамічної задачі оптимального розбиття множини n-вимірного евклідового простору. Доведено теорему про редукцію цієї задачі до сім’ї задач оптимального керування системою з зосередженими параметрами. Отримано в аналітичному вигляді і досліджено оптимальні розв’язки можливих варіантів задачі. The mathematical statement of the simplest dynamic optimal set partitioning problem is presented. It is proved the theorem on the reduction of this problem to the family of problems of optimal control of system with lumped parameters. The optimal solutions of possible problems are obtained in an analytical form and investigated. 2013 Article О решении и свойствах простейшей динамической задачи оптимального разбиения множеств / Е.М. Киселева, Л.С. Коряшкина // Проблемы управления и информатики. — 2013. — № 3. — С. 102–112. — Бібліогр.: 4 назви. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207619 519.6 10.1615/JAutomatInfScien.v45.i6.10 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Методы обработки информации Методы обработки информации |
| spellingShingle |
Методы обработки информации Методы обработки информации Киселева, Е.М. Коряшкина, Л.С. О решении и свойствах простейшей динамической задачи оптимального разбиения множеств Проблемы управления и информатики |
| description |
Наведено математичну постановку найпростішої динамічної задачі оптимального розбиття множини n-вимірного евклідового простору. Доведено теорему про редукцію цієї задачі до сім’ї задач оптимального керування системою з зосередженими параметрами. Отримано в аналітичному вигляді і досліджено оптимальні розв’язки можливих варіантів задачі. |
| format |
Article |
| author |
Киселева, Е.М. Коряшкина, Л.С. |
| author_facet |
Киселева, Е.М. Коряшкина, Л.С. |
| author_sort |
Киселева, Е.М. |
| title |
О решении и свойствах простейшей динамической задачи оптимального разбиения множеств |
| title_short |
О решении и свойствах простейшей динамической задачи оптимального разбиения множеств |
| title_full |
О решении и свойствах простейшей динамической задачи оптимального разбиения множеств |
| title_fullStr |
О решении и свойствах простейшей динамической задачи оптимального разбиения множеств |
| title_full_unstemmed |
О решении и свойствах простейшей динамической задачи оптимального разбиения множеств |
| title_sort |
о решении и свойствах простейшей динамической задачи оптимального разбиения множеств |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| topic_facet |
Методы обработки информации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/207619 |
| citation_txt |
О решении и свойствах простейшей динамической задачи оптимального разбиения множеств / Е.М. Киселева, Л.С. Коряшкина // Проблемы управления и информатики. — 2013. — № 3. — С. 102–112. — Бібліогр.: 4 назви. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT kiselevaem orešeniiisvojstvahprostejšejdinamičeskojzadačioptimalʹnogorazbieniâmnožestv AT korâškinals orešeniiisvojstvahprostejšejdinamičeskojzadačioptimalʹnogorazbieniâmnožestv AT kiselevaem prorozvâzannâtavlastivostínajprostíšoídinamíčnoízadačíoptimalʹnogorozbittâmnožin AT korâškinals prorozvâzannâtavlastivostínajprostíšoídinamíčnoízadačíoptimalʹnogorozbittâmnožin AT kiselevaem onthesolvingandthepropertiesofthesimplestdynamicoptimalsetpartitioningproblem AT korâškinals onthesolvingandthepropertiesofthesimplestdynamicoptimalsetpartitioningproblem |
| first_indexed |
2025-10-12T01:11:46Z |
| last_indexed |
2025-10-13T01:10:48Z |
| _version_ |
1845827047850508288 |
| fulltext |
© Е.М. КИСЕЛЕВА, Л.С. КОРЯШКИНА, 2013
102 ISSN 0572-2691
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 519.6
Е.М. Киселева, Л.С. Коряшкина
О РЕШЕНИИ И СВОЙСТВАХ
ПРОСТЕЙШЕЙ ДИНАМИЧЕСКОЙ ЗАДАЧИ
ОПТИМАЛЬНОГО РАЗБИЕНИЯ МНОЖЕСТВ
Введение. Впервые математическая постановка простейшей динамической
задачи оптимального разбиения множества n-мерного евклидова пространства
была представлена в [1]. В [2] эта постановка обобщена на случай, когда измене-
ние состояния процесса (объекта) может описываться системой нелинейных диф-
ференциальных уравнений, а также когда на фазовые переменные накладываются
интегральные ограничения. Все эти задачи требуют детального исследования [3].
Для частного случая задачи в [4] представлены два подхода к ее решению и выяв-
лены некоторые свойства решений. В данной работе доказана теорема о редукции
простейшей динамической задачи оптимального разбиения множества (ДЗОРМ)
к семейству задач оптимального управления системой с сосредоточенными пара-
метрами. На основе этой теоремы предложен метод и соответствующий числен-
ный алгоритм решения простейшей ДЗОРМ. Получены оптимальные решения
возможных вариантов динамической задачи ОРМ, связанных с выбором коэффи-
циентов приоритета слагаемых целевого функционала.
Постановка задачи. Пусть — ограниченное, измеримое по Лебегу множе-
ство из пространства .nE Совокупность измеримых по Лебегу подмножеств
N ...,,1 множества называется возможным разбиением этого множества, если
;
1
i
N
i
,0)(mes ji ,ji ,,1, Nji
где )(mes — мера Лебега.
Пусть )(NP — класс всех возможных разбиений множества на N под-
множеств:
.,1,,,0)(mes,:)...,,()(
1
1
NjijiP jii
N
i
NN
Введем в рассмотрение функционал
,),(),()),,(()( 2
0
1
10
0 dtdxtxudtdxtxatxcJ
T
ii
N
i
T
i
(1)
где )),,(),,(,( u ),( NP ]),,0[(),( 2 TLu ),],0[(),( 1 TC
0T — заданный момент времени; ,0, 10 02
1
2
0 — коэффициенты,
определяющие приоритет слагаемых в функционале и содержащие величины,
с помощью которых слагаемые становятся безразмерными; ),,( txc i — действи-
тельные, ограниченные, определенные на ],,0[ T измеримые по x при
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 3 103
произвольном фиксированном векторе параметров ,)...,,( 1 n
iii ;,1 Ni
,ia ,,1 Ni — заданные неотрицательные величины; функция ),( tx для каждо-
го x является решением задачи Коши
).()0,(
],,0[),,(),(
0 xx
Tttxutx
(2)
Здесь )(0 x — известная, как правило, неотрицательная определенная на
функция. Точки ,)...,,( 1 n
iii ,,1 Ni — так называемые «центры» под-
множеств, считаются заданными.
Под простейшей динамической задачей оптимального разбиения множества
nE на подмножества N ...,,1 (среди которых могут быть и пустые) будем
понимать следующую задачу.
Задача. Необходимо найти такие разбиение )()...,,( **
1
* NN P , уп-
равление ]),0[(),( 2
* TLtxu и соответствующую фазовую траекторию
),,(* tx удовлетворяющую задаче (2), при которых функционал (1) достигал бы
минимального значения.
Оптимальным решением задачи будем называть допустимую тройку
)),,(),,(,( **** u которая доставляет минимальное значение функционалу J.
Обоснование метода решения задачи. Исследование свойств ее опти-
мальных решений. Согласно теории непрерывных задач оптимального разбиения
множеств [2] для решения задачи сначала вводятся характеристические функции
)(...,),(1 хх N подмножеств N ...,,1 , и от задачи совершается переход к задаче
бесконечномерной оптимизации с булевыми переменными: найти вектор-функцию
,))(...,),(()( **
1
* N а также такое управление ]),0[(),( 2
* TLtxu и со-
ответствующую фазовую траекторию ),,(* tx которые доставляют минимальное
значение функционалу
,),()](),()),,(([)),(),,(),(( 2
1
1
0
0
dxdttxuxtxatxcuI iii
N
i
T
(3)
где
,,1,10)(:))(,),(()( 1 Nixxxx iN
.дляп.в.1)(
1
xxi
N
i
Справедлива следующая теорема.
Теорема. Пусть ,)(* х ]),,0[(),( 2
* TLtxu )],0[(),( 1* TCtx —
решение задачи Коши (2), соответствующее функции ).,(* u Для того чтобы до-
пустимый процесс )),(),,(),(( *** u доставлял минимальное значение функци-
оналу (3), необходимо и достаточно, чтобы почти всюду для x выполнялось
равенство
dttxuxtxatxc iii
N
i
T
2*
1
**
1
0
0
)),(()](),()),,(([
,),()](),()),,(([min 2
1
1
0
0
]),0[(),(
)(
2
0
dttxuxtxatxc iii
N
i
T
TLхu
х
(4)
104 ISSN 0572-2691
где функция ),( x — решение задачи Коши (2), соответствующее функции
управления ),,( xu .1,,1,10:),,(
1
10
i
N
i
iN Ni
Доказательство. Учитывая, что в соответствии с условием (2) функ-
ция ),( tx для каждого x изменяется лишь со временем, поменяем порядок
интегрирования в функционале (3):
dtdxtxuxtxatxcuI iii
N
i
T
),()](),()),,(([)),(),,(),(( 2
1
1
0
0
и введем обозначение:
,),()](),()),,(([)),(),,(),(( 2
1
1
0
0
dttxuxtxatxcххuхВ iii
N
i
T
]),,0([),(,)(:)),(),,(),(({ 20 TLxuxxxuxV x
,,})()0,(],,0[),(),( 0 хxxTttxutx
.x
x
VV
Тогда задачу (3), (2) можно записать так:
.min)),(),,(),((
)),(),,(),(( Vu
dxххuхВ
Необходимость. Пусть )),(),,(),(( *** u — оптимальное решение зада-
чи (3), (2), т.е.
)),(),,(),(()),(),,(),(( *** uIuI ,)( ),],0[(),( 2 TLu
),( — решение задачи Коши (2), соответствующее функции управления ).,( u
Покажем, что почти всюду для x этот процесс удовлетворяет условию (4).
Предположим противное: существует подмножество
~
множества такое, что
0)
~
(mes и
~
x условие (4) не выполняется, т.е.
~
x существует про-
цесс
xVxxux )),(~),,(~),(
~
( , для которого справедливо неравенство
dttxuxtxatxc iii
N
i
T
),(~)](
~
),(~)),,(([ 2
1
1
0
0
dttxuxtxatxc iii
N
i
T
2*
1
**
1
0
0
)),(()](),()),,([(
или, применяя введенные обозначения, запишем
)).,(),,(),(()),(~),,(~),(
~
( *** ххuхВххuхВ (5)
Составим новый процесс:
.
~
\)),(),,(),((
,
~
)),(~),,(~),(
~
(
)),(),,(),((
*** хVxxux
хVxxux
xxux
x
x
Вычислим значение функционала задачи (3) на этом процессе:
.)),(),,(),(()),(~),,(~),(
~
()),(),,(),(( ***
~
\
~
dxххuхВdxххuхВdxxxuxВ
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 3 105
Разбивая аналогичным образом выражение функционала )),(),,(),(( uI в точ-
ке )),(),,(),(( *** u и сравнивая правые части полученных соотношений, при-
ходим к выводу:
)),,(),,(),(()),(),,(),(( *** uIuI
что противоречит условию оптимальности процесса )).,(),,(),(( *** u
Достаточность. Пусть тройка )),(),,(),(( *** u удовлетворяет условию (4)
почти всюду для .x Покажем, что этот процесс является оптимальным для за-
дачи (3), (2). Пусть для всех x xVххuх )),(),,(),(( — произвольный до-
пустимый процесс. Тогда почти для всех x
)).,(),,(),(()),(),,(),(( *** ххuхВххuхВ (6)
Интегрируя (6) по всем x и учитывая, что неравенство может не выполняться
лишь на множестве тех точек из , значение подынтегральной функции в кото-
рых не влияет на величину интеграла, получим
,)),(),,(),(()),(),,(),(( *** dxххuхВdxххuхB
что указывает на оптимальность допустимого процесса )).,(),,(),(( *** u
Теорема доказана.
Таким образом, теорема 1 сводит решение задачи (3), (2) к решению семей-
ства задач оптимального управления почти всюду для :x
)),(),,(),((1 xxuxI
xVxxux
iii
N
i
T
dttxuxtxatxc
)),(),,(),((
2
1
1
0
0
min),()](),()),,(([ (7)
при условиях (2).
Для решения задачи (7), (2) применим необходимые условия оптимальности
в форме принципа максимума Понтрягина. Исследуем свойства оптимальных ре-
шений для отдельных случаев задачи, связанных с выбором коэффициентов при-
оритета слагаемых функционала.
Случай 1. Пусть ,00 .01 Тогда задача теряет смысл как задача опти-
мального разбиения множества и имеет тривиальное решение относительно
функции управления: 0),(* txu ,x ].,0[ Tt
Случай 2. Пусть ,01 .10 Задача (7), (2) становится линейной по
управляющему воздействию и фазовой переменной, поэтому в ее постановку
нужно включить ограничения на функцию управления:
,),( maxutxu ,x ].,0[ Tt (8)
Будем рассматривать задачу (7) , (2) как задачу оптимального управления, в кото-
рой )(x выступает параметром. Учитывая свойства функционала (7) и пра-
вой части дифференциальной связи (2), принцип максимума Понтрягина опреде-
ляет не только необходимые, но и достаточные условия оптимальности для
задачи (7), (2) при каждом фиксированном векторе .)( 0 x
Рассмотрим критерий оптимальности для задачи (7), (2): для того чтобы для
любого x процесс
xVu )),(),,(),(( ***
доставлял минимальное значение
106 ISSN 0572-2691
функционалу задачи (7), необходимо и достаточно существования такого значе-
ния 00 и функции ,)(tх одновременно не обращающихся в нуль ни при ка-
ком значении ],,0[ Tt при которых выполняются:
а) условия стационарности по :),( х
,
H
dt
d х
где функция Гамильтона–Понтрягина имеет вид
)(),()),(),,(),,(),,(( 0 ttxuххuхH хх
,),()(),()),,(( 2
1
0
txuxtxatxc iii
N
i
т.е.
);()),,(()(
1
0 xatxct iii
N
i
х
(9)
б) условия трансверсальности:
;0)( Tх (10)
в) условия оптимальности по :),( хu
).,)(),,(),,(),,((max:),( 0
max
х
uu
ххuхHtxu (11)
Решение задачи Коши (9) , (10) имеет вид
,)()),,(()(
1
0
dxaxct iii
T
t
N
i
х (12)
а функцию управления, доставляющую максимум гамильтониану, запишем так:
.0)(,
,0)(],,[
,0)(,
),(
max
maxmax
max
*
tu
tuuu
tu
txu
x
x
x
(13)
Очевидно, что в случае, когда ,00 сопряженная функция 0)( tх
],0[ Tt , и задача (7), (2) не имеет решения. Положим .10 По условию ис-
ходной динамической задачи оптимального разбиения множества (1), (2) подын-
тегральная функция в выражении (12) неотрицательна, и поэтому 0)( tх почти
для всех ],,0[ Tt за исключением момента Tt или тех точек x и
],,0[ Tt в которых .0),,( ii atxc Таким образом, функция ),,( х соответ-
ствующая оптимальному управлению ),,(* txu должна неуклонно убывать на
всем промежутке .)(),(:],0[ max0
* tuxtxTt
Для того чтобы избежать падения значения функции ),( х ниже определен-
ного уровня (например, если ),( х — спрос на продукцию), дополним постанов-
ку задачи (7), (2) условием ограниченности снизу этой функции:
,),( min tх ,x ].,0[ Tt (14)
При наличии фазовых ограничений условия принципа максимума несколько
изменятся, а именно: для того чтобы x процесс
xVu )),(),,(),(( ***
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 3 107
доставлял минимальное значение функционалу задачи (7), необходимо и доста-
точно существования наряду со значением параметра 00 и функцией ),(tх
одновременно не равных нулю ни при каком значении ],,0[ Tt такой функции
0)( tх ],,0[ Tt при которой выполнялись бы следующие условия:
а) стационарности по :),( х
,
L
dt
d х
где лагранжиан L имеет вид
))(,),(),,(),,(),,(( 0 tttхtхutхL xх
),),(()()),(),,(),,(),,(( min0 txtttхtхutхH xх
т.е.
);()()),,(()(
1
0 txatxct хiii
N
i
х
(15)
б) трансверсальности:
;0)( Tх (16)
в) оптимальности по :),( хu
);),(),,(),,(),,((maxArg),( 0
max
х
uu
ххuхHtxu (17)
г) дополняющей нежесткости:
0)),(()( min txtx ].,0[ Tt (18)
Как и в предыдущем случае, при 00 сопряженная функция 0)( tх
],0[ Tt и задача не имеет решения. Поэтому положим .10
При отсутствии фазового ограничения (14) управляющее воздействие
max
* ),( utxu ],0[ Tt и функция ),( х убывает на всем промежутке
],0[ Tt
.)(),( max0
* tuxtx (19)
Очевидно, что при minmax0 )( Тux решение задачи (7), (2) с фазовым огра-
ничением (14) будет совпадать с (19). Предположим, что minmax0 )( Тux . Из
условия дополняющей нежесткости при min),( tx следует ,0)( tx
,)()),,(()(
1
dxaxct iii
T
t
N
i
х ,),( max
* utxu .)(),( max0
* tuxtx
В силу непрерывности сопряженной функции )(tх в первой точке контакта
траектории ),( tx с фазовым ограничением t (рисунок) имеет место соотно-
шение
).0()0( хх (20)
Начальное условие выхода траектории на фазовое ограничение имеет вид
,)( minmax0 ux откуда .
)(
max
min0
u
x
Очевидно, что, коснувшись
ограничения min),( tx , фазовая траектория на нем и останется. Предположим,
что траектория сошла с ограничения. Тогда дальше на некотором отрезке времени
при t ,),( min tx т.е. функция ),( х должна возрастать. Управляющее воз-
действие, удовлетворяющее условию (17), имеет вид (13), из чего следует, что на
108 ISSN 0572-2691
указанном временном интервале
.0)( tх Учитывая (20), приходим к
выводу, что .0)( х Правый конец
фазовой траектории остается свободным,
поэтому выполняется условие трансвер-
сальности (16). Таким образом, имеем
)(Тх ,0)( х тогда как функция
)(tх строго убывает за пределами фазового ограничения. Полученное противоре-
чие доказывает, что предположение о том, что оптимальная траектория может сойти с
фазового ограничения, не является верным.
Таким образом, запишем решение задачи оптимального управления (7), (2), (14):
если ,)( minmax0 Тux то ,),( max
* utxu tuxtx max0
* )(),(
для всех ];,0[ Tt
если ,)( minmax0 Тux то
;],(,0
,],0[,
),(
max*
Тt
tu
txu
].,[,
],,0[,)(
),(
min
max0*
Tt
ttux
tx
Перейдем к решению задачи оптимального разбиения (3), (2). Подставим найден-
ные выражения функции ),(* tx в функционал (3), помня, что ;10 :01
.min)](),()),,(([)),(),,(),((
)(
*
10
**
х
iii
N
i
T
dxdtxtxatxcuI (21)
Оптимальным решением задачи (21) есть вектор-функция, компоненты кото-
рой удовлетворяют условиям
случаях,остальныхв0
,),()),,((min),()),,((если,1
)(
*
0
,1
*
0
* dttxatxcdttxatxc
x kk
T
Nk
ii
T
i
почти всюду для x имеем .,1 Ni
Случай 3. Предположим, что 0, 10 и решим почти всюду для x за-
дачу оптимального управления (7), (2) при произвольной, но фиксированной век-
тор-функции 0)( x без каких-либо дополнительных условий на управляю-
щую функцию или фазовую переменную.
С помощью принципа максимума Понтрягина решение указанной задачи
удается найти в аналитической форме:
;)()),,((
2
),(
11
0*
dxaxctxu iii
N
i
t
T
(22)
.)()),,((
2
)(),(
101
0
0
*
ddxaxcxtx iii
N
iT
t
(23)
Подставив найденные выражения (22), (23) для функций ),(* txu и ),(* tx в
функционал (7), получим задачу оптимального разбиения множества в терминах
характеристических функций подмножеств: почти для каждого x найти век-
тор 0)( x такой что
(t)
min
)(0 t
t
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 3 109
dtddxaxcxatxcхJ iii
N
iT
t
jj
N
j
T
)()),,((
2
)()),,(())((
101
0
0
10
0
.min)()),,((
2 0)(
2
11
0
0
1
х
iii
N
i
t
T
T
dtdxaxc (24)
Очевидно, что функционал задачи (24) нелинейный, поэтому процесс решения
задачи несколько усложняется. Исследуем другие свойства функционала задачи (24)
и ее оптимального решения. Введем обозначение .),,(),( iii atxctxQ В отличие
от традиционного подхода к решению непрерывных задач оптимального разбие-
ния множеств не будем погружать множество в симплекс :1
,,1],1,0[)(:))(,),(()( 11 Nixxxx iN
,всехдляпочти1)(
1
N
i
i xx
и совершать переход от задачи нелинейного программирования с булевыми пере-
менными к минимизации функционала (24) на множестве .1 Акцентируем вни-
мание лишь на специфике множества и воспользуемся его свойствами для
упрощения функционала (24). Структура множества такова, что имеют место
равенства
),()(2 xx ii
,),(
,,0
)()(
jix
ji
xx
i
ji ,x .,1, Nji
Учитывая указанные соотношения и введенные обозначения, перепишем целевой
функционал в виде
dtxxtxQхJ jj
TN
j
)()(),())(( 0
0
0
1
.)(),(
4
)()(),(),(
2
2
101
2
0
1001
0 dtdxxQdtddxxxQtxQ ii
N
i
T
t
T
ji
T
i
N
i
t
j
T
Второе и третье слагаемые после упрощений запишем так:
dtddxxtxQxQI jij
T
i
N
i
tTN
i
N
j
)()(),(),(
2 100111
2
0
2
);(),(),(
2
0011
2
0 xdtddtxQxQ jjj
TtTN
j
T
ii
T
t
N
i
ii
N
i
T
t
T
dtxdxQdtdxxQI
0
2
11
2
0
2
101
2
0
3 )(),(
4
)(),(
4
.)(),(
4
2
101
2
0 dtxdxQ jj
T
t
N
j
T
110 ISSN 0572-2691
Учитывая приведенные равенства и структуру множества , запишем аналитиче-
ское решение задачи (24):
,,1случаях,остальныхв0
),(min)(если,1
)( ,1*
Ni
хBхB
x
k
Nk
i
i
где величина )(xBi определяется так:
dtddxQtxQdtxtxQхB ii
TtT
i
T
i ),(),(
2
)(),()(
001
2
0
0
0
0
,),(
4
2
01
2
0 dtdxQi
T
t
T
где второе и третье слагаемые похожи между собой. Покажем это, записав 2I в виде
.),(),(
2
),(),(
2
001
2
0
001
2
0
2 dtddxQtxQdtddtxQxQI
T
j
t
j
T
jj
TtT
Введем обозначение ,),(),(
0
dxQtxG j
t
j тогда
dtdxGTxGtxQI jj
t
j
T
)),(),((),(
2
001
2
0
2
.),(),(),(),(),(
2
000
2
1
2
0
dtdxGtxQdttxGTxGTxTG j
t
j
T
j
T
jj
dtdxQdtdxQI
T
t
j
TT
t
j
T 2
01
2
0
2
01
2
0
3 ),(
4
),(
4
.),(),(),(2),(
4
2
00
2
1
2
0
dttxGdttxGTxGTxTG j
T
j
T
jj
После подстановки этих соотношений в выражение для )(xBi и приведения по-
добных слагаемых получим
dtxtxQхB i
T
i )(),()( 0
0
0
dtdxGtxQdttxGTxGTxTG j
t
j
T
j
T
jj ),(),(),(),(),(
2
000
2
1
2
0
dtxtxQdttxGdttxGTxGTxTG i
T
j
T
j
T
jj )(),((),(),(),(2),(
4
0
0
0
2
00
2
1
2
0
.),(
4
),(),(
2
),(
4
2
01
2
0
001
2
02
1
2
0 dttxGdtdxGtxQTxTG j
T
j
t
j
T
j
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 3 111
Таким образом, оптимальное решение задачи (3) имеет вид
п.в. для x
,,1случаях,остальныхв0
),(min)(если,1
)( ,1*
Ni
хBхB
x
k
Nk
i
i (25)
где
dtxtxQхB j
T
j )(),()( 0
0
,),(),(),(2),(
4
2
000
2
1
0
dttxGdtdxGtxQTxTG j
T
j
t
j
T
j
,),,(),( jjj atxctxQ ,),(),(
0
dxQtxG j
t
j .,1 Nj
Оптимальное значение целевого функционала (3) равно:
.)(min
,1
0* dxxBІ j
Nj
Если функция ),,( txc i не зависит от времени, т.е. ),,(),,( ii xctxc )(xQ j
,),( jj axc ),()(),(
0
xQtdxQtxG jj
t
j ,,1 Nj то выражения для )(xBi
и *I упрощаются:
),(
12
)()()( 23
1
0
0 xQTxxTQхB jjj
(26)
.)(
12
)()(min 23
1
0
0
,1
0* dxxQTxxTQІ jj
Nj
(27)
Формулы (26) и (27) можно получить и другим способом [4].
Таким образом, подход, основанный на теореме, приведенной в настоящей
работе, позволяет найти оптимальное решение простейшей динамической задачи
оптимального разбиения множества в аналитическом виде. Для получения чис-
ленных результатов нужно только произвести конечномерную аппроксимацию
функционала (3), заменяя интегралы их конечномерными аналогами, и записать
соответствующие формулы (25), (23), (22) для вычисления характеристических
функций подмножеств, фазовой траектории и управляющей функции. Свойства
полученного оптимального решения задачи в случае, когда ),,(),,( ii xctxc
приведены в [4].
Замечание. Минимум выражения справа в расчетной формуле (25) может до-
стигаться на нескольких индексах. Это означает, что оптимальное разбиение
в задаче определяется не единственным образом и по указанным формулам мож-
но получить различные разбиения множества , на которых целевой функционал
приобретает одно и то же минимальное значение. Определенность в выборе ха-
рактеристических функций некоторых подмножеств ,*
i ,,1 Ni образующих
разбиение, важна для наглядной интерпретации решения (25) и при программной
реализации метода. Что касается применения формул (25) при программной реа-
лизации алгоритма, то неоднозначность устраняется с помощью общепринятого
приема: из нескольких индексов, на которых достигается минимум справа в вы-
ражении (25), выбирается наименьший.
112 ISSN 0572-2691
В работе [4] описан еще один подход к решению задачи (3), (2), основанный
на переходе от этой задачи к задаче минимизации функционала (3) на множестве
]),0[(21 TL при условиях (2). Применяя к последней необходимые условия
оптимальности в форме принципа Эйлера–Лагранжа, решение динамической за-
дачи ОРМ удается получить в виде операторного уравнения относительно харак-
теристических функций подмножеств. Однако алгоритм решения задачи (3), (2)
в этом случае приобретает итерационный характер, в отличие от алгоритма, пред-
ставленного в данной работе. Результаты численного решения различных модель-
ных задач также подтверждают преимущества подхода, основанного на теореме.
Заключение. В работе доказана теорема, которая позволяет свести простей-
шую динамическую задачу оптимального разбиения множества n-мерного евкли-
дова пространства к семейству задач оптимального управления и найти опти-
мальные решения этой задачи для различных ее вариантов в аналитическом виде.
Частным случаем полученных результатов исследований свойств самой задачи и
ее оптимальных решений являются результаты, приведенные в [4]. В дальнейшем
представленная модель будет обобщена на случай наличия фазовых ограничений,
а также неизвестных центров подмножеств.
О.М. Кісельова, Л.С. Коряшкіна
ПРО РОЗВ’ЯЗАННЯ ТА ВЛАСТИВОСТІ
НАЙПРОСТІШОЇ ДИНАМІЧНОЇ ЗАДАЧІ
ОПТИМАЛЬНОГО РОЗБИТТЯ МНОЖИН
Наведено математичну постановку найпростішої динамічної задачі оптималь-
ного розбиття множини n-вимірного евклідового простору. Доведено теорему
про редукцію цієї задачі до сім’ї задач оптимального керування системою з зо-
середженими параметрами. Отримано в аналітичному вигляді і досліджено оп-
тимальні розв’язки можливих варіантів задачі.
E.М. Кiseleva, L.S. Коriashkina
ОN THE SOLVING AND THE PROPERTIES
OF THE SIMPLEST DYNAMIC OPTIMAL SET
PARTITIONING PROBLEM
The mathematical statement of the simplest dynamic optimal set partitioning problem
is presented. It is proved the theorem on the reduction of this problem to the family
of problems of optimal control of system with lumped parameters. The optimal solu-
tions of possible problems are obtained in an analytical form and investigated.
1. Киселева Е.М. Математические методы и алгоритмы решения непрерывных задач опти-
мального разбиения множеств и их приложения : Автореф. дис. ... д-ра физ.-мат. наук:
01.01.09. — Киев : Ин-т кибернетики НАН Украины им. В.М. Глушкова, 1991. — 33 с.
2. Киселева Е.М., Шор Н.З. Непрерывные задачи оптимального разбиения множеств: теория,
алгоритмы, приложения. — Киев : Наук. думка, 2005. — 564 с.
3. Кісельова О.М., Коряшкіна Л.С., Шевченко Т.О. Напрямки розвитку динамічних задач оп-
тимального розбиття множин // Системний аналіз та інформаційні технології: Матеріали
12-ї Міжнар. наук.-практ. конф. SAIT 2010, Київ, 25-29 травня 2010 р. — К. : ННК «ІПСА»
НТУУ «КПІ», 2010. — С. 98.
4. Коряшкіна Л.С., Шевченко Т.О. Нові підходи до розв’язання динамічної задачі оптималь-
ного розбиття множини // Питання прикладної математики і математичного моделювання.
2009. — С. 220–231.
Получено 20.11.2012
|