Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала
Математическая теория непрерывных линейных задач оптимального разбиения множеств (ОРМ) n - мерного евклидова пространства, являющихся неклассическими задачами бесконечномерного математического программирования с булевыми переменными....
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2008 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/72005 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала / Е.М. Киселёва, М.С. Дунайчук // Кибернетика и системный анализ. — 2008. — № 2. — С. 134-151. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859735452459728896 |
|---|---|
| author | Киселёва, Е.М. Дунайчук, М.С. |
| author_facet | Киселёва, Е.М. Дунайчук, М.С. |
| citation_txt | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала / Е.М. Киселёва, М.С. Дунайчук // Кибернетика и системный анализ. — 2008. — № 2. — С. 134-151. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Математическая теория непрерывных линейных задач оптимального разбиения множеств (ОРМ) n - мерного евклидова пространства, являющихся неклассическими задачами бесконечномерного математического программирования с булевыми переменными.
|
| first_indexed | 2025-12-01T15:13:18Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Å.Ì. ÊÈÑÅ˨ÂÀ, Ì.Ñ. ÄÓÍÀÉ×ÓÊ
ÐÅØÅÍÈÅ ÍÅÏÐÅÐÛÂÍÎÉ ÍÅËÈÍÅÉÍÎÉ ÇÀÄÀ×È
ÎÏÒÈÌÀËÜÍÎÃÎ ÐÀÇÁÈÅÍÈß ÌÍÎÆÅÑÒÂ
Ñ ÐÀÇÌÅÙÅÍÈÅÌ ÖÅÍÒÐÎÂ ÏÎÄÌÍÎÆÅÑÒÂ
ÄËß ÑËÓ×Àß ÂÛÏÓÊËÎÃÎ ÖÅËÅÂÎÃÎ ÔÓÍÊÖÈÎÍÀËÀ
Êëþ÷åâûå ñëîâà: áåñêîíå÷íîìåðíîå ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå,
îïòèìàëüíîå ðàçáèåíèå ìíîæåñòâ, íåãëàäêàÿ îïòèìèçàöèÿ.
ÂÂÅÄÅÍÈÅ
Ìàòåìàòè÷åñêàÿ òåîðèÿ íåïðåðûâíûõ ëèíåéíûõ çàäà÷ îïòèìàëüíîãî ðàçáèåíèÿ
ìíîæåñòâ (ÎÐÌ) n-ìåðíîãî åâêëèäîâà ïðîñòðàíñòâà, ÿâëÿþùèõñÿ íåêëàññè÷åñ-
êèìè çàäà÷àìè áåñêîíå÷íîìåðíîãî ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ áóëå-
âûìè ïåðåìåííûìè, èçëîæåíà â [1]. Íà îñíîâå ðàçðàáîòàííûõ è òåîðåòè÷åñêè
îáîñíîâàííûõ â ýòîé ìîíîãðàôèè ìåòîäîâ ðåøåíèÿ çàäà÷ ÎÐÌ ñôîðìóëèðîâà-
íû àëãîðèòìû, ñîñòàâíîé ÷àñòüþ êîòîðûõ ÿâëÿåòñÿ r-àëãîðèòì Øîðà èëè åãî
ìîäèôèêàöèè. Ïðåäëàãàåìàÿ â ìîíîãðàôèè òåîðèÿ îñíîâàíà íà åäèíîì ïîäõî-
äå, ñîñòîÿùåì â ñâåäåíèè èñõîäíûõ áåñêîíå÷íîìåðíûõ çàäà÷ îïòèìèçàöèè
îïðåäåëåííûì îáðàçîì (íàïðèìåð, ÷åðåç ôóíêöèîíàë Ëàãðàíæà) ê íåãëàäêèì, êàê
ïðàâèëî, êîíå÷íîìåðíûì çàäà÷àì îïòèìèçàöèè. Äëÿ ÷èñëåííîãî ðåøåíèÿ òàêèõ
çàäà÷ ïðèìåíÿþòñÿ ñîâðåìåííûå ýôôåêòèâíûå ìåòîäû íåäèôôåðåíöèðóåìîé
îïòèìèçàöèè — ðàçëè÷íûå âàðèàíòû r-àëãîðèòìà, ðàçðàáîòàííûå ïîä ðóêîâî-
äñòâîì Í.Ç. Øîðà â Èíñòèòóòå êèáåðíåòèêè èì. Â.Ì. �ëóøêîâà ÍÀÍ Óêðàèíû.
Îñîáåííîñòü òàêîãî ïîäõîäà çàêëþ÷àåòñÿ â òîì, ÷òî ðåøåíèå ðàññìàòðèâàåìûõ
èñõîäíûõ áåñêîíå÷íîìåðíûõ çàäà÷ îïòèìèçàöèè óäàåòñÿ ïîëó÷èòü àíàëèòè÷åñêè
â ÿâíîì âèäå, ïðè÷åì â àíàëèòè÷åñêîå âûðàæåíèå âõîäÿò ïàðàìåòðû,
îòûñêèâàåìûå êàê îïòèìàëüíîå ðåøåíèå íàçâàííûõ âûøå âñïîìîãàòåëüíûõ
êîíå÷íîìåðíûõ çàäà÷ îïòèìèçàöèè ñ íåãëàäêèìè öåëåâûìè ôóíêöèÿìè.
Èíòåðåñ ê íåïðåðûâíûì ìîäåëÿì îïòèìàëüíîãî ðàçáèåíèÿ ìíîæåñòâ âûçâàí
òåì, ÷òî ê óêàçàííûì ìîäåëÿì ñâîäèòñÿ â ìàòåìàòè÷åñêîé ïîñòàíîâêå äîñòàòî÷-
íî øèðîêèé êëàññ êàê òåîðåòè÷åñêèõ, òàê è ïðàêòè÷åñêèõ çàäà÷ îïòèìèçàöèè.
Òèïè÷íûìè ïðåäñòàâèòåëÿìè íåïðåðûâíûõ çàäà÷ ÎÐÌ ÿâëÿþòñÿ áåñêîíå÷íî-
ìåðíûå òðàíñïîðòíûå çàäà÷è èëè (áîëåå îáùèå) áåñêîíå÷íîìåðíûå çàäà÷è ðàç-
ìåùåíèÿ ïðåäïðèÿòèé ñ îäíîâðåìåííûì ðàçáèåíèåì äàííîãî ðåãèîíà, íåïðåðûâ-
íî çàïîëíåííîãî ïîòðåáèòåëÿìè, íà îáëàñòè ïîòðåáèòåëåé. Êàæäàÿ îáëàñòü îá-
ñëóæèâàåòñÿ îäíèì ïðåäïðèÿòèåì ñ öåëüþ ìèíèìèçàöèè òðàíñïîðòíûõ è
ïðîèçâîäñòâåííûõ çàòðàò. Â ðîëè ïîòðåáèòåëåé ìîãóò âûñòóïàòü òåëåôîííûå
àáîíåíòû, øêîëüíèêè, èçáèðàòåëè, òî÷êè îðîøàåìîé òåððèòîðèè, ïàöèåíòû,
êîòîðûì íàäî ïîñòàâèòü äèàãíîç.
Íåîáõîäèìîñòü â ðàññìîòðåíèè áåñêîíå÷íîìåðíûõ çàäà÷ ðàçìåùåíèÿ âîçíè-
êàåò â ñëó÷àå áîëüøîãî ÷èñëà ïîòðåáèòåëåé, íàïðèìåð, â çàäà÷àõ î òåëåâèçèîí-
íûõ, ðàäèî- è òåëåàáîíåíòàõ, øêîëüíûõ ðåãèîíàõ, èçáèðàòåëüíûõ îêðóãàõ è ò.ï.
Ôîðìóëèðîâêà çàäà÷è ðàçìåùåíèÿ êàê äèñêðåòíîé ìàòåìàòè÷åñêîé ìîäåëè ñòà-
íîâèòñÿ íåöåëåñîîáðàçíîé èç-çà òðóäíîñòåé, ñâÿçàííûõ ñ ðåøåíèåì çàäà÷
÷ðåçìåðíî áîëüøîé ðàçìåðíîñòè.
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
© Å.Ì. Êèñåë¸âà, Ì.Ñ. Äóíàé÷óê, 2008
Ñóùåñòâóþò òàêæå çàäà÷è, ñâîäÿùèåñÿ ê çàäà÷àì îïòèìàëüíîãî ðàçáèåíèÿ,
ó êîòîðûõ ìíîæåñòâî, ðàçáèâàåìîå íà ïîäìíîæåñòâà, óæå èçíà÷àëüíî êîíòèíóàëüíî
ïî ñâîåé ñòðóêòóðå. Ê íèì îòíîñÿòñÿ çàäà÷è îòûñêàíèÿ îáëàñòåé ïðèòÿæåíèÿ ëî-
êàëüíûõ ìèíèìóìîâ íåêîòîðîé ìíîãîýêñòðåìàëüíîé ôóíêöèè; íåïðåðûâíûå çàäà÷è
î øàðîâîì ïîêðûòèè; çàäà÷è îòûñêàíèÿ óçëîâ îïòèìàëüíûõ êóáàòóðíûõ ôîðìóë
äëÿ âû÷èñëåíèÿ èíòåãðàëîâ; íåëèíåéíûå çàäà÷è öåëî÷èñëåííîãî ñòîõàñòè÷åñêîãî
ïðîãðàììèðîâàíèÿ ïðè âû÷èñëåíèè ðåøàþùèõ ïðàâèë; çàäà÷è â òåîðèè ñòàòèñòè-
÷åñêèõ ðåøåíèé ïðè ðàçáèåíèè ïðîñòðàíñòâà ïðèçíàêîâ íà íåïåðåñåêàþùèåñÿ êëàñ-
ñû; çàäà÷è, â êîòîðûõ ðàçìåùàåìûé îáúåêò ðàññìàòðèâàåòñÿ íå êàê òî÷å÷íûé, à êàê
ïðîòÿæåííûé îáúåêò (òàê íàçûâàåìûå çàäà÷è ïëàíèðîâêè).
Èíòåðåñ ê íåïðåðûâíûì ìîäåëÿì îïòèìàëüíîãî ðàçáèåíèÿ ìíîæåñòâ îá-
óñëîâëåí òàêæå òåì, ÷òî îíè ÿâëÿþòñÿ åùå îäíèì èñòî÷íèêîì, ïîðîæäàþùèì
íåãëàäêèå çàäà÷è.
Íàñòîÿùàÿ ñòàòüÿ ïîñâÿùåíà äàëüíåéøåìó ðàçâèòèþ òåîðèè íåïðåðûâíûõ
çàäà÷ ÎÐÌ äëÿ ñëó÷àÿ íåïðåðûâíûõ íåëèíåéíûõ îäíîïðîäóêòîâûõ çàäà÷ îïòè-
ìàëüíîãî ðàçáèåíèÿ ìíîæåñòâ ñ ðàçìåùåíèåì öåíòðîâ ïîäìíîæåñòâ ïðè îãðàíè-
÷åíèÿõ â âèäå ðàâåíñòâ è íåðàâåíñòâ ñ âûïóêëûì öåëåâûì ôóíêöèîíàëîì.
 îòëè÷èå îò ëèíåéíûõ çàäà÷ ÎÐÌ, ðàññìîòðåííûõ â [1], äëÿ êîòîðûõ îïòè-
ìàëüíîå ðåøåíèå èñõîäíîé áåñêîíå÷íîìåðíîé çàäà÷è óäàåòñÿ íàéòè â ÿâíîì
âèäå, â íåëèíåéíîì ñëó÷àå îòûñêàíèå îïòèìàëüíîãî ðåøåíèÿ èñõîäíîé áåñêî-
íå÷íîìåðíîé çàäà÷è ñâîäèòñÿ ê îòûñêàíèþ ðåøåíèÿ íåêîòîðîãî
âñïîìîãàòåëüíîãî îïåðàòîðíîãî óðàâíåíèÿ ñ ïàðàìåòðàìè.
Ðåçóëüòàòû, ïîëó÷åííûå â ðàáîòå [2] äëÿ íåëèíåéíûõ çàäà÷ ÎÐÌ ñ ôèêñèðî-
âàííûìè öåíòðàìè ïîäìíîæåñòâ, êîîðäèíàòû êîòîðûõ çàäàþòñÿ çàðàíåå, îáîáùå-
íû â äàííîé ñòàòüå íà ñëó÷àé íåëèíåéíûõ çàäà÷ ÎÐÌ ñ íåèçâåñòíûì çàðàíåå ðàñ-
ïîëîæåíèåì öåíòðîâ ïîäìíîæåñòâ, êîîðäèíàòû êîòîðûõ îòûñêèâàþòñÿ â ïðîöåññå
ðåøåíèÿ èñõîäíîé çàäà÷è. Ïðèâåäåíî òåîðåòè÷åñêîå îáîñíîâàíèå ìåòîäà ðåøåíèÿ
íàçâàííîé âûøå çàäà÷è, íà åãî îñíîâå ðàçðàáîòàí àëãîðèòì, ñîñòàâíîé ÷àñòüþ êî-
òîðîãî ÿâëÿåòñÿ ìîäèôèêàöèÿ r-àëãîðèòìà Øîðà. Èçëîæåíû ðåçóëüòàòû ðåàëèçà-
öèè ðàçðàáîòàííîãî àëãîðèòìà äëÿ íåêîòîûõ ìîäåëüíûõ çàäà÷.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü � — îãðàíè÷åííîå, èçìåðèìîå ïî Ëåáåãó ìíîæåñòâî â n-ìåðíîì åâêëè-
äîâîì ïðîñòðàíñòâå En . Ñîâîêóïíîñòü èçìåðèìûõ ïî Ëåáåãó ïîäìíîæåñòâ
� �1, ,� N èç � � En íàçîâåì âîçìîæíûì ðàçáèåíèåì ìíîæåñòâà, åñëè
i
N
i
� 1
� � ��, mes (� �i j� �) 0, i j� ; i, j N� 1, ,� ,
ãäå mes ( )� îçíà÷àåò ìåðó Ëåáåãà.
Îáîçíà÷èì �
N êëàññ âñåõ âîçìîæíûõ ðàçáèåíèé ìíîæåñòâà � :
� � �N
N � {( , , ) :1 �
i
N
i
� 1
� � ��, mes( )� �i j� � 0 i j� ; i, j N� 1, ,� }.
Ââåäåì ôóíêöèîíàë
F N( , ,{� �1 � }, {� �1, ,� N }) =
i
N
i x dx
i
�
�
1
[ ( ( ) )� �
�
c x x dxi
i
( , ) ( ) ].� �
�
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 135
(Çäåñü è â äàëüíåéøåì èíòåãðàëû ïîíèìàþòñÿ â ñìûñëå Ëåáåãà.) Áóäåì ñ÷è-
òàòü, ÷òî ìåðà ãðàíè÷íûõ òî÷åê ïîäìíîæåñòâ � i , i N�1, ,� , ðàâíà íóëþ.
Ôóíêöèè c x i( , )� — äåéñòâèòåëüíûå, îãðàíè÷åííûå, îïðåäåëåííûå íà � ��,
èçìåðèìûå ïî x ïðè ëþáîì ôèêñèðîâàííîì � � �i i i
n� ( , ,( ) ( )1 � ) èç � äëÿ âñåõ
i N� 1, ,� ; ôóíêöèÿ �( )x — äåéñòâèòåëüíàÿ, îãðàíè÷åííàÿ, èçìåðèìàÿ, íåîò-
ðèöàòåëüíàÿ íà �; � i � (� �i i
n( ) ( ), ,1 � ) — íåêîòîðàÿ íåèçâåñòíàÿ çàðàíåå, ýòà-
ëîííàÿ òî÷êà äëÿ ïîäìíîæåñòâà � i , i N�1, ,� , íàçûâàåìàÿ öåíòðîì ýòîãî
ïîäìíîæåñòâà; � i ( )� , i N�1, ,� , — äåéñòâèòåëüíûå, îãðàíè÷åííûå, âûïóêëûå,
äâàæäû íåïðåðûâíî-äèôôåðåíöèðóåìûå ôóíêöèè ñâîåãî àðãóìåíòà.
Òîãäà ïîä íåïðåðûâíîé íåëèíåéíîé îäíîïðîäóêòîâîé çàäà÷åé îïòèìàëüíî-
ãî ðàçáèåíèÿ ìíîæåñòâà � èç En íà åãî íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà
� �1, ,� N ñ îòûñêàíèåì êîîðäèíàò öåíòðîâ (ñ ðàçìåùåíèåì öåíòðîâ) ïîäìíî-
æåñòâ ïðè îãðàíè÷åíèÿõ â âèäå ðàâåíñòâ è íåðàâåíñòâ áóäåì ïîíèìàòü
ñëåäóþùóþ çàäà÷ó.
Çàäà÷à À. Íàéòè
min ( , ,
( , , , , , ){ } { }
{
� �
� �
1 1
1
� �
�
N N
F N
� �
}, {� �1, ,� N })
ïðè óñëîâèÿõ
�( ) , , ..., ðx dx b i
i
i
�
� �1 ,
�( ) , ð , ...,x dx b i N
i
i
�
� �1 ,
{� �1, ,� N } � �
N , � � �� ( , , )1 � N � � �� ��� �� ��
N
�� N ,
ãäå õ õ õ n� �( , , )( ) ( )1 � �; � � �i i i
n� ( , , )( ) ( )1 � ��; b bN1, ,� — çàäàííûå íå-
îòðèöàòåëüíûå ÷èñëà, ïðè÷åì âûïîëíÿþòñÿ óñëîâèÿ ðàçðåøèìîñòè çàäà÷è
S x dx�
�( )
�
�
i
N
ib
1
, 0 1�
�b S i Ni , , ,� . (1)
Ðàçáèåíèå { }� �1
* *, ,� N , ÿâëÿþùååñÿ ðåøåíèåì çàäà÷è A, íàçîâåì
îïòèìàëüíûì.
Íà ðèñ. 1 èçîáðàæåíî ðàçáèåíèå ìíîæåñòâà � � E2 íà òðè ïîäìíîæåñòâà:
�1, � 2 , � 3 ñ öåíòðàìè � � �1 2 3, , ýòèõ ïîäìíîæåñòâ ñîîòâåòñòâåííî.
Ââåäåì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ
� i
i
i
x
x
x i N
( )
, ,
, \ , , , ,
�
�
� �
�
�
�
1
0 1
�
� � �
ïîäìíîæåñòâà � i , i N�1, ,� .
Ðàññìîòðèì ôóíêöèîíàë
I ( ( ), )� �� �
� �
�
i
N
i ix x dx
1
[ ( ( ) ( ) )� � �
�
�
�
c x x x dxi i( , ) ( ) ( ) ]� � � , (2)
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Ðèñ. 1
�3
�2
�1
� � �3 3
1
3
2� ( , )
( ) ( )
� � �2 2
1
2
2� ( , )
( ) ( )
� � �1 1
1
1
2� ( , )
( ) ( )
x x x� ( , )( ) ( )1 2
ãäå âåêòîð-ôóíêöèÿ èìååò âèä � � �( ) ( ( ), , ( )x x xN� 1 � ). Î÷åâèäíî,
I F N( ( ), ) ( , , , )� � �� � { }� �1 � .
Ïåðåïèøåì çàäà÷ó À â òåðìèíàõ õàðàêòåðèñòè÷åñêèõ ôóíêöèé � i x( ) ïîä-
ìíîæåñòâ � i , i N�1, ,� , â ñëåäóþùåì âèäå.
Çàäà÷à Â. Íàéòè
min ( ( ), )
( ( ), )� �
� �
� � �
�
� �1
N
I ,
ãäå
�1 � {� ( )x : �( )x � �� 1 ïî÷òè âñþäó äëÿ x � �;
�
� �� �( ) ( ) , , , ðx x dx b ii i 1 � ,
� �( ) ( ) , ð , ...,x x dx b i Ni i
�
� �1 };
� � � �1 1{� � �( ) ( ( ), , ( )x x xN� ): � i x( ) � �0 1 ïî÷òè âñþäó äëÿ x � �,
i N�1, ,� ,
i
N
i x
�
�
1
1� ( ) ïî÷òè âñþäó äëÿ x � �}; � � �� �( , , )1 � N
N� .
Çàäà÷à B ÿâëÿåòñÿ çàäà÷åé áåñêîíå÷íîìåðíîãî ìàòåìàòè÷åñêîãî ïðîãðàììèðî-
âàíèÿ ñ áóëåâûìè ïåðåìåííûìè � ( )� .
Îò çàäà÷è B ñ áóëåâûìè çíà÷åíèÿìè ïåðåìåííûõ � i ( )� , i N�1, ,� , ïåðåéäeì
ê ñîîòâåòñòâóþùåé çàäà÷å ñî çíà÷åíèÿìè � i ( )� èç îòðåçêà [0,1].
Çàäà÷à Ñ. Íàéòè
min ( ( ), )
( ( ), )� �
� �
� � �
�
� �2
N
I ,
ãäå �2 � {�( )x : �( )x �� ïî÷òè âñþäó äëÿ x � �;
�
� �� �( ) ( ) , , , ðx x dx b ii i 1 � ,
�
� �� �( ) ( ) , ð , ,x x dx b i Ni i 1 � };
� � �{� �( ) ( ( )x x1 , …, � N x( )): 0 1
� i x( ) , x � �, i N�1, ,� ,
i
N
i x
�
�
1
1� ( )
ïî÷òè âñþäó äëÿ x ��};
� � �� �( , , )1 � N
N� .
Êàê äîêàçàíî â [1], �2 — îãðàíè÷åííîå, çàìêíóòîå, âûïóêëîå ìíîæåñòâî
ãèëüáåðòîâà ïðîñòðàíñòâà L N
2
( )� ñ íîðìîé
| | ( )| | [ ( )]
/
� �� �
�
�
�
�
�
�
�
�
�� i
N
i x dx
1
2
1 2
.
Òîãäà ñîãëàñíî [3] ìíîæåñòâî �2 ñëàáî êîìïàêòíî â ãèëüáåðòîâîì ïðîñòðà-
íñòâå L N
2
( )� .
Î÷åâèäíî,
I I
N
( ( ), ) min ( ( ), )* *
( , )
� � � �
� �
� � � �
� �� �2
� ��
�
�
�
�
�
� � �
min min ( ( ), )
( )� �
� �
� �N
I
2
. (3)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 137
Èçó÷èì ñíà÷àëà ñâîéñòâà ôóíêöèîíàëà I ( ( ), )� �� èç (2).
Îáîçíà÷àÿ f x x dxi i i( ( )) ( ) ( )� � �� �
�
, ïåðåïèøåì ôóíêöèîíàë (2) â âèäå
I f c x x x dx
i
N
i i i i i( ( ), ) [ ( ( ( ))) ( , ) ( ) ( )� � � � � � �� � � �
�
1 �
]. (4)
Èìååò ìåñòî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 1. Åñëè � i ( )� , i N�1, ,� , — âûïóêëûå ôóíêöèè ñâîåãî àðãó-
ìåíòà, òî ïðè êàæäîì ôèêñèðîâàííîì � �� N ôóíêöèîíàë I ( ( ), )� �� èç (4) ÿâëÿ-
åòñÿ âûïóêëûì ïî �( )� íà LN
2
( )� .
Äîêàçàòåëüñòâî. Èç âûïóêëîñòè ôóíêöèé � i i N( ), , ,� �1 � , â îáëàñòè îïðå-
äåëåíèÿ, ëèíåéíîñòè ôóíêöèîíàëîâ
f i ( ( )) ( ) ( )� � �i ix x dx� �
�
, i N�1, ,� ,
íà L2 ( )� è ñâîéñòâ ñëîæíûõ ôóíêöèé ñëåäóåò, ÷òî ôóíêöèîíàëû
� �i i if( ( ( )))� , i N�1, ,� , áóäóò âûïóêëû ïî � i ( )� íà L2 ( )� .
Ïóñòü �1 ( )x , �2
2
( ) ( )x LN� � ïî÷òè âñþäó äëÿ x ��. Âîçüìåì �� ( )x �
� � �� � � �1 21( ) ( ) ( )x x ïî÷òè âñþäó äëÿ x ��, � �[ , ]01 . Î÷åâèäíî, ÷òî
�� ( ) ( )� �LN
2
� . Äëÿ ôóíêöèîíàëà I ( ( ), )� �� � ïðè ôèêñèðîâàííîì � �� N èìååì
I ( ( ), )� �� � � � �
�
�
�
�
�
�
�
i
N
i i i i if c x x x dx
1
� � � � �� �( ( ( ))) ( , ) ( ) ( )
�
� � � � ��
�
�
�
�
�
�
�
�
�
�
� �
�
i
N
i i i i if c x
1
1 21� � � � � �( ) ( ) ( ) ( ,
�
) ( )� x
�
�
�
�
� � � �
�
�
�
�
�
�
�
�
� � � �i ix x d x1 21( ) ( ) ( )
� � � � �
�
i
N
i i i i i if f c x
1
1 21� � � � � � � �( ( ( ))) ( ) ( ( ( ))) ( ,
�
i ix x dx) ( ) ( )� �1
�
�
�
�
� �
�
�
( ) ( , ) ( ) ( )1 2� � � �
�
c x x x dxi i
� � �
�
�
�
�
�
�
�
� � � � � �
i
N
i i i i if c x x x dx
1
1 1( ( ( ))) ( , ) ( ) ( )
�
� � ��
�
� �
�
� �
�
( ) ( ( )) ( , ) ( ) ( )1
1
2 2� � � � � �
i
N
i i i i if c x x x d
�
x
�
�
�
�
�
�
� � � � � � �� � � � � �I I( ( ), ) ( ) ( ( ), )1 21 .
Óòâåðæäåíèå 1 äîêàçàíî.
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Çàìå÷àíèå 1. Èç âûïóêëîñòè ôóíêöèîíàëà ! "I � �( ),� ïî �( )� íà LN
2
( )� ñëå-
äóåò åãî íåïðåðûâíîñòü ïî � ( )� íà LN
2
( )� [4].
Òåîðåìà 1. Âíóòðåííÿÿ çàäà÷à èç (3) èìååò ðåøåíèå ïðè êàæäîì ôèêñèðî-
âàííîì � �� N .
Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, èç îáîáùåííîé òåîðåìû Âåéåðøòðàññà [3]
ñëåäóåò, ÷òî íåïðåðûâíûé âûïóêëûé ïî �( )� ôóíêöèîíàë ! "I � �( ),� èç (3), îïðåäå-
ëåííûé íà ãèëüáåðòîâîì ïðîñòðàíñòâå LN
2
( )� , äîñòèãàåò ïðè êàæäîì ôèêñèðî-
âàííîì � �� N ñâîåãî ìèíèìóìà ïî �( )� íà ëþáîì âûïóêëîì, çàìêíóòîì, îãðà-
íè÷åííîì ìíîæåñòâå (â äàííîì ñëó÷àå íà ìíîæåñòâå �2).Òåîðåìà 1 äîêàçàíà.
Òàêèì îáðàçîì, êàê ñëåäóåò èç óòâåðæäåíèÿ 1 è òåîðåìû 1, ïðè êàæäîì ôèê-
ñèðîâàííîì � �� N âíóòðåííÿÿ çàäà÷à èç (3) ãëîáàëüíî ðàçðåøèìà îòíîñèòåëü-
íî �( )� íà ìíîæåñòâå �2 .
Çàìå÷àíèå 2. Óñëîâèÿ òåîðåìû 1 ìîãóò áûòü îñëàáëåíû, òàê êàê áóäóò äîñ-
òèãàòü íà �2 ñâîåé íèæíåé ãðàíè íå òîëüêî âûïóêëûå íåïðåðûâíûå ôóíêöèîíà-
ëû, íî è íåïðåðûâíûå ñíèçó (ñëàáî ïîëóíåïðåðûâíûå ñíèçó) ôóíêöèîíàëû.
Äåéñòâèòåëüíî, êàê îòìå÷àëîñü âûøå, îãðàíè÷åííîå, çàìêíóòîå, âûïóêëîå
ìíîæåñòâî â ãèëüáåðòîâîì ïðîñòðàíñòâå LN
2
( )� ñëàáî êîìïàêòíî. Ïî îáîáùåí-
íîé òåîðåìå Âåéåðøòðàññà [3] ïîëóíåïðåðûâíûé ñíèçó ïî �( )� (ñëàáî ïîëóíåïðå-
ðûâíûé ñíèçó ïî �( )� ) ôóíêöèîíàë I ( ( ), )� �� íà ñëàáî êîìïàêòíîì ìíîæåñòâå �2
ãèëüáåðòîâà ïðîñòðàíñòâà LN
2
( )� îãðàíè÷åí ñíèçó è äîñòèãàåò íà ýòîì ìíîæåñ-
òâå ñâîåé íèæíåé ãðàíè ïî � ( )� ïðè êàæäîì ôèêñèðîâàííîì � �� N .
ÎÁÎÑÍÎÂÀÍÈÅ ÌÅÒÎÄÀ ÐÅØÅÍÈß ÇÀÄÀ×È
Ââåäåì äëÿ çàäà÷è Ñ ôóíêöèîíàë Ëàãðàíæà
h I x x dx b
i
N
i i i( ( ), , ) ( ( ), ) ( ) ( ){ }� � � � � � � �� � � � �
�
�
�
�
1 ��
�
�
�
! "� � �
�
�
�
�
i
N
i i i i ix x dx c x x x dx
1
� � � � � � �( ( ) ( ) ) ( , ) ( ) ( )
� ��
�
�
�
�
i
N
i ib
1
� ,(5)
ãäå � � �� ( )1� N — N -ìåðíûé âåêòîð âåùåñòâåííûõ ÷èñåë, ó êîòîðîãî êîì-
ïîíåíòû � �1 � p ïðîèçâîëüíû ïî çíàêó, à � �p N� 1 � — íåîòðèöàòåëüíû;
�( )x �� äëÿ x ��; ! "� � �� �1, ,� N
N� .
Ïàðó ýëåìåíòîâ ( ( ), , )* *
*{ }� � �� íàçîâåì ñåäëîâîé òî÷êîé ôóíêöèîíàëà (5)
íà ìíîæåñòâå { }� � #� �N , ãäå
# � � � $ � �{ }� � � �( ) : , , ,1 0 1� �N N iE i p N ,
åñëè
h h h( ( ), , ) ( ( ), , ) ( ( ), , )* * * *
* *{ } { } { }� � � � � � � � ��
�
�
äëÿ âñåõ �( )x ��, � �� N , � �#,
èëè
h ( ( ), , )* *
*{ }� � �� � max min ( ( ), , )
( ( ), )� � �
� � �
� � � �
� �
# � �N
h { }
�
� � � �
min max
( ( ), )� � �� � #N
h ( ( ), , ){ }� � �� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 139
Íå îñòàíàâëèâàÿñü ïîêà íà èññëåäîâàíèè âîïðîñà î ñóùåñòâîâàíèè ñåäëîâîé
òî÷êè, ïåðåéäåì ê ðåøåíèþ çàäà÷è
max min ( ( ), , )
( ( ), )� � �
� � �
� � � �
�
# � � N
h { } .
Îáîçíà÷èì
G h
N
( ) min ( ( ), , )
( ( ), )
� � � �
� �
� �
� � �� �
{ } , � �#.
Çàäà÷à, äâîéñòâåííàÿ ê çàäà÷å Ñ, èìååò âèä
G ( ) max� % , � �#. (6)
Äëÿ îòûñêàíèÿ min ( ( ), , )
( ( ), )� �
� � �
� � �
�
� �N
h { } ïåðåéäåì ê çàäà÷å
min min ( ( ), , )
( )� �
� � �
� � �
�
� �N
h { } ïðè � �#. (7)
Óòâåðæäåíèå 2. Ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàí-
íîì � �# ôóíêöèîíàë h ( ( ), , ){ }� � �� èç (7), îïðåäåëÿåìûé ïî ôîðìóëå (5), áóäåò
âûïóêëûì ïî � ( )� íà L N
2
( )� , åñëè � i ( )� , i N�1, ,� , — âûïóêëûå ôóíêöèè
ñâîåãî àðãóìåíòà.
Äîêàçàòåëüñòâî óòâåðæäåíèÿ 2 àíàëîãè÷íî äîêàçàòåëüñòâó óòâåðæäåíèÿ 1.
Óòâåðæäåíèå 3. Ïî àíàëîãèè ñ òåîðåìîé 1 ëåãêî äîêàçàòü, ÷òî ïðè êàæäîì
ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàííîì � �# ìèíèìóì ïî �( )� ôóíê-
öèîíàëà h ( ( ), , ){ }� � �� äîñòèãàåòñÿ íà ñèìïëåêñå �.
Òàêèì îáðàçîì, âíóòðåííÿÿ çàäà÷à â (7) ãëîáàëüíî ðàçðåøèìà ïî �( )� íà �.
Îáîçíà÷èì â (7)
G h1 ( , ) min ( ( ), , )
( )
� � � � �
�
� �
� ��
{ } , � �� N , � �#. (8)
Äàëåå âìåñòî äâîéñòâåííîé çàäà÷è (6) ñ ó÷åòîì (7), (8) ïåðåéäåì ê ðåøåíèþ
ñëåäóþùåé çàäà÷è:
max min ( , )
� �
� �
� �# �N
G1 .
Äëÿ ýòîãî ñíà÷àëà êîíêðåòèçèðóåì âûðàæåíèå G1 ( , )� � èç (8).
Ïîäñòàâëÿÿ â (8) âûðàæåíèå äëÿ h ( ( ), , ){ }� � �� èç (5), ïîëó÷àåì
G b
i
N
i i1
1
( , )� � �� � �
�
�
�
�
�
�
�
�
�
�
� �
� � �
min ( ) ( ) ( ( , )
( )�
� � � �
�
� �i
N
i i ix x dx c x
1
� � �i ix x dx) ( ) ( )
�
�
�
�
�
�
, (9)
� �� N , � �#.
Îáîçíà÷èì â (9)
! "&i i i i i� � � �( ), ,� �
�
�
�
�
�
�
�
�
�
� �( ) ( )x x dxi � �
�
( ( , ) ) ( ) ( )c x x x dxi i i� � � �
è ðàññìîòðèì çàäà÷ó
min ( ( ), , )
( )�
� � �
� �
�
�
& , � �� N , � �#,
140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
ãäå
& &( ( ), , ) ( ( ), , )� � � � � �� � �
�
i
N
i i i i
1
. (10)
Î÷åâèäíî, ÷òî ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàí-
íîì � �# äëÿ ôóíêöèîíàëà & ( ( ), , )� � �� èç (10) èìåþò ìåñòî óòâåðæäåíèÿ, àíà-
ëîãè÷íûå óòâåðæäåíèÿì 2 è 3, ò.å. ôóíêöèîíàë & ( ( ), , )� � �� èç (10) áóäåò âûïóê-
ëûì ïî � ( )� íà LN
2
( )� , åñëè � i ( )� , i N�1, ,� , — âûïóêëûå ôóíêöèè ñâîåãî àðãó-
ìåíòà è ìèíèìóì ïî � ( )� ôóíêöèîíàëà & ( ( ), , )� � �� äîñòèãàåòñÿ íà ìíîæåñòâå �.
Îáîçíà÷èì sgrad � ! "& � � �( ), ,� ñóáãðàäèåíò ïî � ( )� âûïóêëîãî ïî � ( )� ïðè
êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàííîì � �# ôóíêöèîíàëà
& ( ( ), , )� � �� .
Ìîæíî ïîêàçàòü, ÷òî sgrad �& ( ( ), , )� � �� ïðè êàæäîì ôèêñèðîâàííîì
� �� N è êàæäîì ôèêñèðîâàííîì � �# èìååò âèä
sgrad �& ( ( ), , )� � �� �
� � � � � �( ( ( ), , ), , ( ( ), , ), , ( (& & &� � �� � � � � � �
1 1 1 1 � �
i Ni i i N �), , ))� �N N ,
ãäå
� � � �& � � � � �
i ii i i iY( ( ), , )
�
�
�
�
�
�
�
�
�
� �( ) ( )x x dxi �� ( )x � �( ( , ) ) ( )c x xi i� � � ,
i N�1, ,� ,
çäåñü
Y x x dxi i�
�
� �( ) ( ) . (11)
Ñîãëàñíî [5] ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàííîì
� �# íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå ìèíèìóìà ïî � ( )� âûïóêëîãî ïî � ( )�
ôóíêöèîíàëà & ( ( ), , )� � �� íà ñèìïëåêñå � èìååò âèä
min ( ( ( ), , ), ( ( ) ( )))
( )
* *
�
� � � � � �
� �
� � �
�
�
&sgrad x x dx 0.
Ïåðåïèøåì ïîëó÷åííîå ðàâåíñòâî â âèäå
�
&
� �( ( ( ), , ), ( ))* *sgrad x dx� � � � �
� �
� �
min ( ( ( ), , ), ( ))
( )
*
�
� � � � �
�
�
&sgrad x dx. (12)
Ïðåäïîëîæèì, ÷òî ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðî-
âàííîì � �# äëÿ ôóíêöèîíàëà &( ( ), , )� � �� èç (10) ïî ïåðåìåííîé � ( )� âûïîëíÿ-
åòñÿ óñëîâèå, êîòîðîå íàçîâåì, ñëåäóÿ [5], óñëîâèåì ñèëüíîé ðåãóëÿðíîñòè, åñëè
� ��
�
�
�
�
� �& � � � �
i i i i
* ( ), , �� iYi
�
�
�
�
�
�
�
�
�
� �( ) ( )*x x dxi � � ( )x ! "� � �c x xi i( , ) ( )� � � 0,
i N�1, ..., ,
çà èñêëþ÷åíèåì ìíîæåñòâà òî÷åê x �� íóëåâîé ìåðû, èëè, â äðóãîé çàïèñè,
mes{x c x x x dxi i iY ii
� � � �
�
�
�
�
�
�
�
�
�
�
: ( , ) ( ( ) ( ) ) (*� � � � � � x) � �0 0} , (13)
ãäå Yi , i N�1, ,� , èìååò âèä (11).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 141
Óñëîâèå ñèëüíîé ðåãóëÿðíîñòè îçíà÷àåò, ÷òî äëÿ îïòèìàëüíîé âåêòîð-ôóíê-
öèè �* ( )x íè íà îäíîì ìíîæåñòâå òî÷åê x �� íåíóëåâîé ìåðû íå óäîâëåòâîðÿåò-
ñÿ íè îäíî èç óðàâíåíèé Ýéëåðà
&� � �� � � �
i i i i( ( ), , )* 0, i N�1, ,� ,
äëÿ çàäà÷è ìèíèìèçàöèè áåç îãðàíè÷åíèé ôóíêöèîíàëà & ( ( ), , )� � �� èç (10).
Êàê ñëåäóåò èç [1, 5], â ñëó÷àå âûïîëíåíèÿ óñëîâèÿ ñèëüíîé ðåãóëÿðíîñòè
(13) âåêòîð-ôóíêöèÿ � *( )x , äîñòàâëÿþùàÿ ìèíèìóì ëèíåéíîìó ôóíêöèîíàëó èç
ïðàâîé ÷àñòè ôîðìóëû (12), îïðåäåëÿåòñÿ ïðè êàæäîì ôèêñèðîâàííîì � �� N è
êàæäîì ôèêñèðîâàííîì � �# î÷åâèäíûì îáðàçîì èç ñëåäóþùåãî îïåðàòîðíîãî
óðàâíåíèÿ:
�
� � � � �
i
i i iY i
x
c x x x dx
i
*
*
( )
, ( , ) ( ) ( )
�
� � �
�
�
�
�
�
�
�
0 åñëè
�
�
�
�
�
�
�
�
�
�
'
� � �
�
� � � � �
( ) ,
, ( , ) ( ) ( )*
x
c x x xi i iY ii
0
1 åñëè
�
dx x i N
c x i
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� ��
�
( ) , , , ,
[ , ], ( , )
0 1
01
�
åñëè � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
(
(
� � � � �i iY ii
x x dx x
�
( ) ( ) ( ) .* 0
(
(
(
�
(
(
(
(
(
Ñ ó÷åòîì (13) è òîãî, ÷òî ìåðà ìíîæåñòâà ãðàíè÷íûõ òî÷åê ïîäìíîæåñòâ � i ,
i N�1, ,� , ðàâíà íóëþ, èìååì
�
� � � � �
i
i i iY i
x
c x x x dx
c
i
*
*
( )
, ( , ) ( ) ( )
�
� � �
�
�
�
�
�
�
�
�
1
�
( , ) ( ) ( ) ,*x x x dx
i k
k k kY kk
� � � � �� � �
�
�
�
�
�
�
�
�
� )
�
ïî òè âñþäó äë äðóãèìè ñëîâàìè
òîëüêî íà ìíîæåñòâå ìåðû íîëü
x i k� �� ( ,
, ò.å. â òî êàõ ãðàíèöû ìåæäó
ïîäìíîæåñòâàìè è
)
�� �i k i k), , 1, , ;� N
0 â îñòàëüíûõ ñëó àõ.)
�
�
(
(
(
(
((
�
(
(
(
(
(
(
Ñ ó÷åòîì îáîçíà÷åíèé (11), ïðèáàâëÿÿ è âû÷èòàÿ ïîä çíàêîì ñóììû â (9)
âûðàæåíèå � � �iY ii
x x dx�
�
�
�
�
�
�
�
�
�
( ) ( ) , ïåðåïèøåì G1 ( , )� � èç (9) â âèäå
G b
i
N
i i1
1
( , )� � �� � �
�
�
�
�
�
�
�
�
�
�
� �
� � �
min ( ) ( ) (
( )�
� � � � �
�
� �i
N
i i i iYx x dx x
i
1
) ( ) ( ) ( )� � �i i ix dx x x dx
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � � �
� �
( ( , ) ( ( ) ( ) )) ( ) ( ) ]c x x x dx x x dxi i iY i ii
� � � � � � � , (15)
142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
� �� N , � �#.
Ïîäñòàâëÿÿ âûðàæåíèå äëÿ � i x* ( ) èç (14) â òó ÷àñòü ôîðìóëû (15), êîòîðàÿ
ëèíåéíî çàâèñèò îò � ( )� , è îñòàâëÿÿ ïåðåìåííîé âåëè÷èíó Yi , i N�1, ,� , ñâÿçàí-
íóþ ñ � ( )� çàâèñèìîñòüþ (11), ïîëó÷àåì (ñ ó÷åòîì îãðàíè÷åíèé çàäà÷è C) âûðà-
æåíèå äëÿ G1 ( , )� � â ñëåäóþùåì âèäå:
G Y b
i
N
i i2
1
( , , )� � �� � �
�
i
N
i i iY i iY Y Y
i
�
� � �
�
�
�
�1
( ( ) ( ) )� �
� � � �
�
�
�
�
min ( ( , ) ( )) ( )
,k N
k k kY kc x Y x dx
k
1
� � � � ,
(16)
� �� N , � �#, Y U Y Y Y E Y b i NN N i i� � � �
�{ }( , , ) : , , ,1 0 1� � .
Òàêèì îáðàçîì, êîíêðåòèçèðóÿ âûðàæåíèå äëÿ G1 ( , )� � èç (8), äâîéñòâåííóþ
çàäà÷ó (6) ïðèâåëè ê âèäó
max min max ( , , )
� �
� �
� � �# �N Y U
G Y2 . (17)
Ïðåæäå ÷åì ñôîðìóëèðîâàòü àëãîðèòì ðåøåíèÿ çàäà÷è (17), îñòàíîâèìñÿ íà
íåêîòîðûõ ñâîéñòâàõ ôóíêöèè G Y2 ( , , )� � , îïðåäåëÿåìîé ïî ôîðìóëå (16).
Ïðè êàæäîì ôèêñèðîâàííîì � �# è êàæäîì ôèêñèðîâàííîì Y U� ôóíêöèÿ
ïåðåìåííîé � íà � N îáëàäàåò ñâîéñòâàìè, óñòàíîâëåííûìè â [1]. Èíûìè ñëîâà-
ìè, ôóíêöèÿ G Y2 ( , , )� � èç (16) ïðè êàæäîì ôèêñèðîâàííîì � �# è êàæäîì ôèê-
ñèðîâàííîì Y U� ÿâëÿåòñÿ ïî � �� N íåäèôôåðåíöèðóåìîé ìíîãîýêñòðåìàëü-
íîé. Îäíàêî â íåêîòîðûõ ÷àñòíûõ ñëó÷àÿõ (ñì. [1]), ââîäÿ íà ìíîæåñòâå � � En
îïðåäåëåííûå îòíîøåíèÿ ïîðÿäêà ìåæäó êîîðäèíàòàìè òî÷åê � �1, ,� N , ìîæíî
ìíîæåñòâî � N ïðåäñòàâèòü â âèäå îáúåäèíåíèÿ òàêèõ âûïóêëûõ ïîäìíîæåñòâ,
êàæäîå èç êîòîðûõ áóäåò îïðåäåëÿòüñÿ ñâîèì îòíîøåíèåì ïîðÿäêà ìåæäó êîîð-
äèíàòàìè òî÷åê � �1, ,� N , è íà êàæäîì èç òàêèõ âûïóêëûõ ïîäìíîæåñòâ ìíî-
æåñòâà � N ôóíêöèÿ G Y2 ( , , )� � èç (16) áóäåò âûïóêëîé ïî � è èìåòü ïî � òî÷êó
ëîêàëüíîãî ìèíèìóìà. Ïðè÷åì çíà÷åíèå ôóíêöèè G Y2 ( , , )� � ïðè êàæäîì ôèê-
ñèðîâàííîì � �# è êàæäîì ôèêñèðîâàííîì Y U� â ýòèõ òî÷êàõ ëîêàëüíûõ ìè-
íèìóìîâ áóäóò ñîâïàäàòü. Ñëåäîâàòåëüíî, â ýòîì ñëó÷àå çàäà÷à îòûñêàíèÿ
min ( , , )
�
� �
��N
G Y
2
ïðè êàæäîì ôèêñèðîâàííîì � �# è êàæäîì ôèêñèðîâàííîì
Y U� áóäåò îäíîýêñòðåìàëüíîé.
Ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàííîì � �# ôóíê-
öèÿ G Y2 ( , , )� � èç (16) ïî ïåðåìåííîé Y áóäåò âîãíóòîé íà âûïóêëîì ìíîæåñòâå
U , åñëè � i ( )� , i N�1, ,� , — âûïóêëûå ôóíêöèè ñâîåãî àðãóìåíòà [2]. È, íàêîíåö,
ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàííîì Y U� ôóíêöèÿ
G Y2 ( , , )� � èç (16) ïî ïåðåìåííîé � áóäåò âîãíóòîé è íåäèôôåðåíöèðóåìîé íà
ìíîæåñòâå # [1].
Ó÷èòûâàÿ âûøåèçëîæåííîå è îáîáùàÿ íà ñëó÷àé çàäà÷è Ñ ðåçóëüòàòû, ïîëó-
÷åííûå â [1] äëÿ àíàëîãè÷íîé íåïðåðûâíîé ëèíåéíîé îäíîïðîäóêòîâîé çàäà÷è
îïòèìàëüíîãî ðàçáèåíèÿ ìíîæåñòâ ñ ðàçìåùåíèåì öåíòðîâ ïîäìíîæåñòâ, ìîæíî
ñäåëàòü âûâîä, ÷òî äëÿ çàäà÷è Ñ èìååò ìåñòî òåîðåìà Êóíà–Òàêêåðà â äâîéñòâåí-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 143
íîé ôîðìå, ò.å. I G( ( ), ) ( )* *
*� � �� � , ãäå ( ( ), )* *� �� — îïòèìàëüíîå ðåøåíèå çà-
äà÷è Ñ, � * — îïòèìàëüíîå ðåøåíèå äâîéñòâåííîé çàäà÷è (17), ïðè÷åì
ìàêñèìóì â äâîéñòâåííîé çàäà÷å (17) äîñòèãàåòñÿ.
Ñôîðìóëèðóåì òåîðåìó, ïîäâîäÿùóþ èòîã íàøèì ðàññóæäåíèÿì è îáóñëîâ-
ëèâàþùóþ ïåðåõîä îò áåñêîíå÷íîìåðíîé çàäà÷è Ñ ê ïîèñêó ñåäëîâîé òî÷êè
ôóíêöèîíàëà (5) ïîñðåäñòâîì ðåøåíèÿ íåãëàäêîé êîíå÷íîìåðíîé çàäà÷è (17), ê
êîòîðîé ñâåäåíà äâîéñòâåííàÿ çàäà÷à (6).
Òåîðåìà 2. Ïóñòü
1) � i ( )� , i N�1, ,� , — âûïóêëûå, äâàæäû íåïðåðûâíî-äèôôåðåíöèðóåìûå
ôóíêöèè ñâîåãî àðãóìåíòà;
2) ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàííîì � �# èìå-
åò ìåñòî óñëîâèå ñèëüíîé ðåãóëÿðíîñòè (13)
mes{x c x x x dxi i iY ii
� � � �
�
�
�
�
�
�
�
�
�
�
: ( , ) ( ( ) ( ) ) (*� � � � � � x) � �0 0} , i N�1, ,� .
Òîãäà ñåäëîâàÿ òî÷êà ( ( ), , )* *
*{ }� � �� (ãäå ïåðâàÿ êîìïîíåíòà { }� �* *( ),� ÿâëÿ-
åòñÿ îïòèìàëüíûì ðåøåíèåì çàäà÷è Ñ) ôóíêöèîíàëà (5) íà ìíîæåñòâå
{ T }� #� �
� '� �1, ,� N
j (çäåñü T
� '� �1, ,� N
j — âûïóêëûå ïîäìíîæåñòâà ìíîæåñòâà
� N , îïðåäåëÿåìûå ñâîèì îòíîøåíèåì ïîðÿäêà ìåæäó êîîðäèíàòàìè òî÷åê
� �1, ,� N , íà êîòîðûõ ôóíêöèÿ G Y2 ( , , )� � èç (16) — âûïóêëà è îáúåäèíåíèå
êîòîðûõ ñîñòàâëÿåò ìíîæåñòâî � N ) îïðåäåëÿåòñÿ äëÿ i N�1, ,� è ïî÷òè âñåõ
x �� ñëåäóþùèì îáðàçîì:
� i
i q
i
x
x x q i
x
* * *
*
( )
, ,
.
�
� *
*
�
�
�
1
0
ïðè è
ïðè
� �
�
Çäåñü
� �*
* * *: ( , ) ( )i i i iY ix c x Y
i
� � � � � �{ � � �
� � � � �
�
min ( ( , ) ( )),
, ,
* * *
k N
k k kY kc x Y i k
k1 �
� � � ïî÷òè âñþäó äëÿ x ��},
â êà÷åñòâå Y Y N1
* *, ,� , � �1
* *, ,� N , � �1
* *, ,� N âûáèðàåòñÿ îïòèìàëüíîå ðåøå-
íèå äâîéñòâåííîé çàäà÷è (6), ïðèâåäåííîé ê âèäó
G G Y b
N NY U Y U i
N
i( ) min max ( , , ) min max� � � �
� �
� � �
� � � � �
� �
2
1
i �
�
�
(
�(
� � � � � �
�
�
�
� �
i
N
i i iY i i
k N
kY Y Y c x
i
1 1
( ( ) ( ) ) min ( ( , )
,
� � �
��
� � �k kY kk
Y x dx� �
�
�
+
,
-
%( )) ( ) max
ïðè óñëîâèÿõ � i $ 0, i p N� �1, ,� .
Óòâåðæäåíèå 4. Ïðè âûïîëíåíèè óñëîâèÿ ñèëüíîé ðåãóëÿðíîñòè (13) ìíî-
æåñòâà îïòèìàëüíûõ ðåøåíèé çàäà÷ B è Ñ ñîâïàäàþò.
144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Äîêàçàòåëüñòâî óòâåðæäåíèÿ 4 îñíîâàíî íà ñïðàâåäëèâîñòè óòâåðæäåíèé 4.1–4.3.
Óòâåðæäåíèå 4.1. Ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðî-
âàííîì � �# îãðàíè÷åííîå, çàìêíóòîå, âûïóêëîå ìíîæåñòâî � ãèëüáåðòîâà ïðî-
ñòðàíñòâà L N
2
( )� ñëàáî êîìïàêòíî è (ñîãëàñíî òåîðåìå Êðåéíà-Ìèëüìàíà [4])
ñîäåðæèò ïî êðàéíåé ìåðå îäíó êðàéíþþ òî÷êó.
Óòâåðæäåíèå 4.2. Ñðåäè ìíîæåñòâà òî÷åê, â êîòîðûõ ëèíåéíûé îòíîñèòåëü-
íî � ( )� ôóíêöèîíàë
R sgrad x dx( ( ), , ) ( ( ( ), , ), ( ))*� � � � � � ��� � �
�
& (18)
äîñòèãàåò ïðè êàæäîì ôèêñèðîâàííîì � �� N è êàæäîì ôèêñèðîâàííîì � �#
ìèíèìóìà ïî � ( )� íà �, íàéäåòñÿ õîòÿ áû îäíà êðàéíÿÿ òî÷êà ñèìïëåêñà �.
Óòâåðæäåíèå 4.3. Kðàéíèå òî÷êè ñèìïëåêñà � ïðåäñòàâëÿþò ñîáîé õàðàêòå-
ðèñòè÷åñêèå ôóíêöèè íåêîòîðûõ ïîäìíîæåñòâ � i , îáðàçóþùèõ ïðè êàæäîì
ôèêñèðîâàííîì � �� N è � �# ðàçáèåíèå ìíîæåñòâà �.
Tàêèì îáðàçîì, ìíîæåñòâà îïòèìàëüíûõ ðåøåíèé çàäà÷ B è Ñ ñîâïàäàþò.
ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÇÀÄÀ×È
Ðàññìîòðèì àëãîðèòì ðåøåíèÿ çàäà÷è B, îñíîâàííûé íà òåîðåìå 2.
Äëÿ îòûñêàíèÿ îïòèìàëüíîãî ðåøåíèÿ çàäà÷è (17) áóäåì èñïîëüçîâàòü ýâ-
ðèñòè÷åñêèé àëãîðèòì îáîáùåííûõ ïñåâäîãðàäèåíòîâ ñ ðàñòÿæåíèåì ïðîñòðà-
íñòâà, áëèçêèé ê r-àëãîðèòìó Øîðà [6].
Äëÿ ýòîãî îò çàäà÷è (17) ââåäåíèåì â öåëåâóþ ôóíêöèþ (16) íåãëàäêèõ
øòðàôíûõ ôóíêöèé ìíîæåñòâ { }� i i p N$ � �0 1, , ,� , {Yi $ 0, i � 1, ,� N },
{ }Y b i Ni i
�, , ,1 � ïåðåéäåì ê ñëåäóþùåé çàäà÷å:
íàéòè
max min max ( , , )
� �
� �
� � �E Y EN N N
P Y
�
, (19)
ãäå
P Y G Y S S
i
N
i( , , ) ( , , ) max ,� � � � �� � � � �
�
2 1
1
20{ } � �
�
i
N
iY
1
0max ,{ }
� � �
�
S Y b
i
N
i i3
1
0max ,{ }. (20)
Çäåñü S1, S 2 , S 3 — äîñòàòî÷íî áîëüøèå ïîëîæèòåëüíûå ÷èñëà, çíà÷èòåëüíî
áîëüøèå ìàêñèìàëüíûõ èç ìíîæèòåëåé Ëàãðàíæà äëÿ ôóíêöèè (16). (Î âîç-
ìîæíîñòè ïåðåõîäà îò çàäà÷è (17) ê çàäà÷å (19), (20) ñì. â [1,6,7].)
Îïðåäåëèì i-þ êîìïîíåíòó 3 � N -ìåðíîãî âåêòîðà îáîáùåííîãî ïñåâäî-ãðà-
äèåíòà
g Y( , , )� � � ( ( , , ), ( , , ), ( , , ))� � �g Y g Y g Yp
Y
p p� � � � � �� �
� � �( ( , , ), , ( , , );g Y g Yp
Y
p
YN1 � � � �� g Y g Yp p
N� �� � � �1 ( , , ), , ( , , )� ;
� �g Y g Yp p
N� �� � � �1 ( , , ), , ( , , ))�
ôóíêöèè (20) â òî÷êå ( , , )Y � � � ( , , ; , , ; , , )Y Y N N N1 1 1� � �� � � � ñëåäóþùèì
îáðàçîì:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 145
g Y Y Y S Y Sp
Y
iY Y i i i
i
i i
( , , ) ( ) max[ , ( )]� � �� � � � � � � �2 30 sign max[ , ( )],
, : [ ( , ) (
0 sign
åñë ãäå
Y b
è i k k c x
i i
k k kYk
�
� � � �� � � Y
c x Y
g Y
k
l N
l l lY l
p
Y
l
k
)]
min [ ( , ) ( )], ( )
( , ,
,
�
� � � �
� 1
21� � �
� � � � � �) ( ) ( ) ( ) ( )� � � � � � � � � �
�
kY Y k k kY Y k kk k k k
Y Y Y x x dx
S
�
2 max[ , ( )] max[ , ( )],0 03sign sign� � �
�
�
(
(
(
((
�
(
(
(
(
Y S Y bk k k(
i N�1, ,� ;
g Y x g x x dxp c i i
i i� �� � � � �( , , ) ( ) ( , ) ( )� �
�
, i N�1, ,� , (22)
ãäå g xc i
i� �( , ) — i-ÿ êîìïîíåíòà N -ìåðíîãî âåêòîðà îáîáùåííîãî ãðàäèåíòà
g xc i
i� �( , ) ôóíêöèè c x i( , )� â òî÷êå � � � �� ( , , , , )1 � �i N ïðè ôèêñèðîâàí-
íîì x,
g x
g x
g x
c
c
c
i
i
i
n
�
�
�
�
�
�
( , )
( , )
( , )
( )
( )
� � � � �
�
�
�
�
�
�
�
�
�
�
�
�
1
;
. /g Y x x dx b Sp i i i
i� � � � � �( , , ) ( ) ( ) max , ( )� � � �
�
1 0 sign , i N�1, ,� . (23)
 ôîðìóëàõ (21)–(23) � i x( ), i N�1, , ,� îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
�
� � � � � �
i
i i iY i
k N
k k
x
c x Y c x
i
( )
, ( , ) ( ) min [ ( , )
,
�
� � � � � �
�
1
1
kY kk
Y
i k x
�
� ) �
)
�
�
(
( )],
;ïî òè âñþäó äë
â îñòàëüíûõ ñëó àõ.
�
0
(
�
(
(
(24)
Îïèøåì àëãîðèòì ðåøåíèÿ çàäà÷è B.
Àëãîðèòì
Ïðåäâàðèòåëüíûé ýòàï. Îáëàñòü � çàêëþ÷àåì â n-ìåðíûé ïàðàëëåëåïèïåä
0, ñòîðîíû êîòîðîãî ïàðàëëåëüíû îñÿì äåêàðòîâîé ñèñòåìû êîîðäèíàò, ïîëàãà-
åì � ( )x � 0 ïðè x �0 �\ , j M�1, ,� . Ïàðàëëåëåïèïåä 0 ïîêðûâàåì ïðÿìîóãîëü-
íîé ñåòêîé è çàäàåì íà÷àëüíîå ïðèáëèæåíèå ( , , ) ( , , )( ) ( ) ( )Y Y� � � �� 0 0 0 . Âû÷èñ-
ëÿåì çíà÷åíèå �( ) ( )0 x â óçëàõ ñåòêè ïî ôîðìóëàì (24) ïðè Y Y� ( )0 , � �� ( )0 ,
� �� ( )0 . Âû÷èñëÿåì çíà÷åíèå g Yp
Y ( , , )( ) ( ) ( )0 0 0� � , g Yp
� � �( , , )( ) ( ) ( )0 0 0 ,
g Yp
� � �( , , )( ) ( ) ( )0 0 0 â óçëàõ ñåòêè ïî ôîðìóëàì (21)–(23) ïðè Y Y� ( )0 , � �� ( )0 ,
� �� ( )0 , � �( ) ( )( )x x� 0 . Âûáèðàåì íà÷àëüíûé ïðîáíûé øàã h0 0' r-àëãîðèòìà
Øîðà.
Ïåðâûé øàã àëãîðèòìà ïðîâîäèì ïî ôîðìóëàì
Y Y h g Yp
Y( ) ( ) ( ) ( ) ( )( , , )1 0
0
0 0 0� � � � ,
� � � ��( ) ( ) ( ) ( ) ( )( ( , , ))1 0
0
0 0 0� �P0 h g Yp ,
� � � ��( ) ( ) ( ) ( ) ( )( , , )1 0
0
0 0 0� � h g Yp ,
ãäå P0 — îïåðàòîð ïðîåêòèðîâàíèÿ íà 0.
146 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Ïåðåõîäèì êî âòîðîìó øàãó. Ïóñòü â ðåçóëüòàòå âû÷èñëåíèé ïîñëå k,
k �12, , ,� øàãîâ àëãîðèòìà ïîëó÷åíû îïðåäåëåííûå çíà÷åíèÿ
Y xk k k k( ) ( ) ( ) ( ), , , ( )� � � � 1 â óçëàõ ñåòêè.
Îïèøåì (k + 1)-é øàã àëãîðèòìà.
1. Âû÷èñëÿåì çíà÷åíèÿ � ( ) ( )k x â óçëàõ ñåòêè ïî ôîðìóëàì (24) ïðè
Y k k k( ) ( ) ( ), ,� � .
2. Âû÷èñëÿåì çíà÷åíèÿ g Yp ( , , )� � ïî ôîðìóëàì (21)–(23) ïðè
� �( ) ( )( )x xk� , Y Y k� ( ) , � �� ( )k , � �� ( )k .
3. Ïðîâîäèì ( )k � 1 -é øàã r-àëãîðèòìà îáîáùåííûõ ïñåâäîãðàäèåíòîâ ñ
ðàñòÿæåíèåì ïðîñòðàíñòâà, áëèçêîãî ê r-àëãîðèòìó Øîðà â H-ôîðìå [6], èòåðà-
öèîííàÿ ôîðìóëà êîòîðîãî èìååò âèä
Y Y h
H g Y
H g Y
k k
k
k p
Y k k k
k p
Y k
( ) ( )
( ) ( ) ( )
( )
( , , )
( (
� �
�
� �1 1
1
� �
, , ), ( , , ))( ) ( ) ( ) ( ) ( )� � � �k k
p
Y k k kg Y
,
� �
� ��
�
( ) ( )
( ) ( ) ( )
(
( , , )
( (
k k
k
k p
k k k
k p
h
H g Y
H g Y
� �
�
� �1 1
1
P0
k k k
p
k k kg Y) ( ) ( ) ( ) ( ) ( ), , ), ( , , ))� � � ��
�
�
�
�
�
�
�
�
�
�
,
� �
� ��
�
( ) ( )
( ) ( ) ( )
( )
( , , )
( (
k k
k
k p
k k k
k p
k
h
H g Y
H g Y
� �
�
� �1 1
1 , , ), ( , , ))( ) ( ) ( ) ( ) ( )� � � ��k k
p
k k kg Y
.
Çäåñü H k�1 — ìàòðèöà ðàñòÿæåíèÿ ïðîñòðàíñòâà ñ êîýôôèöèåíòîì � (åãî öå-
ëåñîîáðàçíî áðàòü ðàâíûì òðåì) â íàïðàâëåíèè ðàçíîñòè äâóõ ïîñëåäîâàòåëü-
íûõ îáîáùåííûõ ãðàäèåíòîâ,
H Hk k� � � �
�
�
�
�
�
�
�
�1 2
1
1
�
H H
H
k k k
T
k
k k k
1 1
1 1( , )
,
1 k p
T k k k
p
T k k kg Y g Y� � � � �( , , ) ( , , )( ) ( ) ( ) ( ) ( ) ( )� � � �1 1 1 ,
ãäå T — îäíà èç ïåðåìåííûõ Y , � èëè �.
Åñëè H k � 1 ââèäó îêðóãëåíèÿ ñ÷åòà ïåðåñòàåò áûòü ïîëîæèòåëüíî îïðåäå-
ëåííîé, òî çàìåíÿåì åå åäèíè÷íîé ìàòðèöåé.
Øàãîâûé ìíîæèòåëü hk âûáèðàåì èç óñëîâèÿ ìèíèìóìà ðàçíîñòè
[ ( , , ) ( , , )]( ) ( ) ( ) ( ) ( ) ( )G Y G Yk k k k k k
2
1
2
1 1� �� � ��2 2 ïî íàïðàâëåíèþ àíòèï-
ñåâäîãðàäèåíòà � g Y( , , )� 2 â ïðåîáðàçîâàííîì ïðîñòðàíñòâå.
4. Åñëè óñëîâèå
| | ( , , ) ( , , )| | ,( ) ( ) ( ) ( ) ( ) ( )Y Yk k k k k k� � � � � ��
'� � �1 1 1 0, (25)
íå âûïîëíÿåòñÿ, ïåðåõîäèì ê ( )k � 2 -ìó øàãó àëãîðèòìà, â ïðîòèâíîì ñëó÷àå
— ê ï. 5.
5. Ïîëàãàåì, ÷òî Y Y l
*
( )� , � �*
( )� l , � �*
( )� l , � �*
( )( ) ( )x xl� , ãäå l —
íîìåð èòåðàöèè, íà êîòîðîé âûïîëíèëîñü óñëîâèå (25).
6. Âû÷èñëÿåì îïòèìàëüíîå çíà÷åíèå öåëåâîãî ôóíêöèîíàëà ïî ôîðìóëå (20)
ïðè Y Y� * , � �� * , � �� * è äëÿ êîíòðîëÿ ïðàâèëüíîñòè ñ÷åòà — ïî ôîðìóëå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 147
I x x dx c x
i
N
i i( ( ), ) ( ) ( ) ( ,* * * *� � � � � �� �
�
�
�
�
�
�
�
�
�
�
1 � �
i ix x dx) ( ) ( )*� �
�
�
�
�
�
�
.
Àëãîðèòì îïèñàí.
ÐÅØÅÍÈÅ ÌÎÄÅËÜÍÛÕ ÇÀÄÀ×
Îïèñàííûé àëãîðèòì ðåàëèçîâàí äëÿ ìîäåëüíûõ áåñêîíå÷íîìåðíûõ çàäà÷ ðàç-
ìåùåíèÿ â çàäàííîé îáëàñòè òðåõ ïðåäïðèÿòèé, ïðîèçâîäÿùèõ îäíîðîäíóþ
ïðîäóêöèþ äëÿ ðàñïðåäåëåííîãî â ýòîé îáëàñòè ñ çàäàííîé ïëîòíîñòüþ ïîòðå-
áèòåëÿ, ñ îãðàíè÷åíèÿìè íà ìîùíîñòè ïðåäïðèÿòèé â âèäå ðàâåíñòâ è
íåðàâåíñòâ.
Ìîäåëüíàÿ çàäà÷à 1. Ïîòðåáèòåëü íåêîòîðîé îäíîðîäíîé ïðîäóêöèè, ïðî-
èçâîäèìîé òðåìÿ ïðåäïðèÿòèÿìè, íåïðåðûâíî ðàñïðåäåëåí â îáëàñòè
� �
{ }( , ) : ;x y x y0 10 0 10 . Çàäàíû íà÷àëüíûå êîîðäèíàòû ðàñïîëîæåíèÿ
ïðåäïðèÿòèé � � �i i i� �( , ) ( ; )( ) ( )1 2 0 0 , i �13, . Äëÿ êàæäîãî i-ãî ïðåäïðèÿòèÿ, i �13, ,
çàäàíà ôóíêöèÿ
c x y x yi i i( , , ) ( ) ( )( ) ( )� � �� � � �1 2 2 2 ,
îïèñûâàþùàÿ ñòîèìîñòü òðàíñïîðòèðîâêè åäèíèöû ïðîäóêöèè èç i-ãî ïðåäïðèÿ-
òèÿ ê ïîòðåáèòåëþ ñ êîîðäèíàòàìè ( , )x y . Èçâåñòåí ñïðîñ � ( , )x y íà ïðîäóêöèþ
äëÿ êàæäîãî ïóíêòà ïîòðåáëåíèÿ ñ êîîðäèíàòàìè ( , )x y . Äëÿ ïðîñòîòû ïîëàãàåò-
ñÿ � ( , )x y x3 4 �1 �. Ôóíêöèè � i iY( ), îïèñûâàþùèå çàâèñèìîñòü ñòîèìîñòè
ïðîèçâîäñòâà ïðîäóêöèè íà i-ì ïðåäïðèÿòèè îò åãî ìîùíîñòè, èìåþò âèä
� i i iY Y( ) � 3 , i �12 3, , , ãäå ìîùíîñòü i-ãî ïðåäïðèÿòèÿ îïðåäåëÿåòñÿ ïî ôîðìóëå
Y x y dx dyi
i
�
�
� ( , ) . (26)
Ìíîæåñòâî ïîòðåáèòåëåé � ìîæíî ðàçáèâàòü íà çîíû îáñëóæèâàíèÿ � i ïî-
òðåáèòåëåé i-ì ïóíêòîì ïðîèçâîäñòâà òàê, ÷òîáû
i
i
�
�
1
3
� � �, mes ( )� �i k i k� �� 0, i �12 3, , , (27)
ïðè÷åì ìîùíîñòü i-ãî ïðåäïðèÿòèÿ, i �12 3, , , îïðåäåëÿåòñÿ ñóììàðíûì ñïðîñîì
ïîòðåáèòåëåé, ïðèíàäëåæàùèõ � i , i �12 3, , , è íå äîëæíà ïðåâûøàòü çàäàííûõ
îáúåìîâ
0
�i
x y dx dy bi� ( , ) , i �12 3, , , (28)
b1 90� , b2 50� , b3 35� .
Òðåáóåòñÿ ðàçáèòü ìíîæåñòâî ïîòðåáèòåëåé � íà çîíû èõ îáñëóæèâàíèÿ
òðåìÿ ïðåäïðèÿòèÿìè, ò.å. íà ïîäìíîæåñòâà � i , i �12 3, , , è ðàçìåñòèòü ýòè ïðåä-
ïðèÿòèÿ â îáëàñòè � òàê, ÷òîáû ìèíèìèçèðîâàòü ôóíêöèîíàë ñóììàðíûõ çàòðàò
íà ïðîèçâîäñòâî ïðîäóêöèè è äîñòàâêó åå ê ïîòðåáèòåëþ:
F N N( , , , , , ){ } { }� �1 1� �� � �
�
�
�
�
�
�
�
�
�
�
�
i
i i
i i
x y dx dy c x x y dx
1
3
� � � �
� �
( , ) ( , ) ( , ) dy
�
�
�
�
�
�
(29)
ïðè óñëîâèÿõ (27), (28).
Äëÿ ðåøåíèÿ ñôîðìóëèðîâàííîé çàäà÷è ñ ïîìîùüþ îïèñàííîãî âûøå àëãî-
ðèòìà îáëàñòü � ïîêðûâàëàñü ïðÿìîóãîëüíîé ñåòêîé ñ óçëàìè ( , )i j , i �1 21,� ,
148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
j �1 21, ,� .  êà÷åñòâå íà÷àëüíûõ äàííûõ áûëè âûáðàíû íà÷àëüíûå çíà÷åíèÿ
äâîéñòâåííûõ ïåðåìåííûõ � i
( )0 0� , i �12 3, , , íà÷àëüíûå çíà÷åíèÿ Y
1
0 1( ) � ,
Y
2
0 1( ) � , Y
3
0 10( ) � ìîùíîñòåé, íà÷àëüíûå êîîðäèíàòû ðàñïîëîæåíèÿ ïðåäïðèÿ-
òèé � i
( ) ( ; )0 0 0� , i �12 3, , . Óñëîâèåì ïðåêðàùåíèÿ ñ÷åòà ÿâëÿëîñü âûïîëíåíèå
íåðàâåíñòâà
| | ( , , ) ( , , )| |( ) ( ) ( ) ( ) ( ) ( )Y Yk k k k k k� � � � ��
� � �1 1 1 , �' 0,
ãäå k — íîìåð èòåðàöèè àëãîðèòìà, íà êîòîðîé ïðîèçîøåë îñòàíîâ, � � �10 5
— òî÷íîñòü âû÷èñëåíèé r-àëãîðèòìîì Øîðà. Äâîéíûå èíòåãðàëû, âõîäÿùèå
â ôîðìóëû (26), (28), (29), âû÷èñëÿëèñü ñ ïîìîùüþ êóáàòóðíîé ôîðìóëû
òðàïåöèé.
 ðåçóëüòàòå ðàáîòû îïèñàííûì àëãîðèòìîì çà 106 èòåðàöèé ïîëó÷åíû:
— îïòèìàëüíîå ðàçáèåíèå ìíîæåñòâà ïîòðåáè-
òåëåé � íà çîíû îáñëóæèâàíèÿ � � �1 2 3, , ñîîòâå-
òñòâåííî êàæäûì èç òðåõ ïðåäïðèÿòèé ñ ðàçìåùåíè-
åì öåíòðîâ ïîäìíîæåñòâ äëÿ ìîäåëüíîé çàäà÷è 1
(ðèñ. 2);
— îïòèìàëüíûå êîîðäèíàòû ðàçìåùåííûõ
ïðåäïðèÿòèé:
� 1 6 05 7 91* ( , ; , )� , � 2 194 4 29* ( , ; , )� , � 3 711 2 68* ( , ; , )� ;
— îïòèìàëüíûå ìîùíîñòè êàæäîãî ïðåäïðèÿ-
òèÿ
Y 1 33 33* ,� ; Y 2 33 34* ,� ; Y 3 33 33* ,� ;
— ìèíèìàëüíîå çíà÷åíèå ïðÿìîãî ôóíêöèîíàëà (29): F* ,5111363 8;
— ìàêñèìàëüíîå çíà÷åíèå ôóíêöèîíàëà äâîéñòâåííîé çàäà÷è G * ,5111348 5.
Ìîäåëüíàÿ çàäà÷à 2. Èñõîäíûå äàííûå òå æå, ÷òî è äëÿ ìîäåëüíîé çàäà-
÷è 1, çà èñêëþ÷åíèåì îãðàíè÷åíèé íà ìîùíîñòè ïðåäïðèÿòèé. Ìîùíîñòü ïåðâî-
ãî ïðåäïðèÿòèÿ ðàâíà çàäàííîìó îáúåìó, à ìîùíîñòè âòîðîãî è òðåòüåãî ïðåä-
ïðèÿòèé íå äîëæíû ïðåâûøàòü çàäàííûõ îáúåìîâ:
Y Y Y1 2 390 0 50 0 35�
, , .
B ðåçóëüòàòå ðàáîòû àëãîðèòìà çà 461 èòåðàöèþ ñ òî÷íîñòüþ � � �10 3 ïîëó÷åíû:
— îïòèìàëüíîå ðàçáèåíèå ìíîæåñòâà ïîòðåáè-
òåëåé � íà òðè çîíû îáñëóæèâàíèÿ êàæäûì èç òðåõ
ïðåäïðèÿòèé ñ ðàçìåùåíèåì öåíòðîâ ïîäìíîæåñòâ
äëÿ ìîäåëüíîé çàäà÷è 2 (ðèñ. 3);
— îïòèìàëüíûå êîîðäèíàòû ðàçìåùåííûõ
ïðåäïðèÿòèé
� 1 5 00 5 00* ( , ; , )� , � 2 110 8 92* ( , ; , )� , � 3 8 98 107* ( , ; , )� ;
— îïòèìàëüíûå ìîùíîñòè êàæäîãî èç òðåõ
ïðåäïðèÿòèé
Y 1 90 00* ,� ; Y 2 4 99* ,� ; Y 3 4 99* ,� ;
— ìèíèìàëüíîå çíà÷åíèå ïðÿìîãî ôóíêöèîíàëà (29) F* , ;5 7295711
— ìàêñèìàëüíîå çíà÷åíèå ôóíêöèîíàëà äâîéñòâåííîé çàäà÷è G * , .5 729585 9
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 149
Fig. 2
�1
*
�2
*
�3
*
Fig. 3
�1
*
�2
*
�3
*
Ìîäåëüíàÿ çàäà÷à 3. Äëÿ ñðàâíåíèÿ ñ ìîäåëüíîé çàäà÷åé 2 ðåøåíà çàäà÷à ñ
òåìè æå äàííûìè, òîëüêî ïðè çàäàííûõ çàðàíåå ôèêñèðîâàííûõ êîîðäèíàòàõ
ïðåäïðèÿòèé:
�
1
0 2 2( ) ( ; )� , �
2
0 3 9( ) ( ; )� , �
3
0 5 7( ) ( ; )� .
Ïîëó÷åíû ñëåäóþùèå ðåçóëüòàòû çà 136 èòåðà-
öèé:
— îïòèìàëüíîå ðàçáèåíèå ìíîæåñòâà ïîòðåáè-
òåëåé � íà òðè çîíû îáñëóæèâàíèÿ êàæäûì èç òðåõ
ïðåäïðèÿòèé áåç ðàçìåùåíèÿ öåíòðîâ ïîäìíîæåñòâ
äëÿ ìîäåëüíîé çàäà÷è 3 (ðèñ. 4);
— îïòèìàëüíûå ìîùíîñòè êàæäîãî èç òðåõ
ïðåäïðèÿòèé
Y 1 90 00* ,� ; Y 2 5 00* ,� ; Y 3 5 00* ,� ;
— ìèíèìàëüíîå çíà÷åíèå ïðÿìîãî ôóíêöèîíàëà (29) F* ,5 729720 8;
— ìàêñèìàëüíîå çíà÷åíèå ôóíêöèîíàëà äâîéñòâåííîé çàäà÷è
G * ,5 729723 2.
Ðåçóëüòàòû ðåøåíèé ìîäåëüíûõ çàäà÷ 1–3:
1) ñóììû îïòèìàëüíûõ ìîùíîñòåé ïðåäïðèÿòèé â êàæäîé çàäà÷å ðàâíû ñóì-
ìàðíîé ìîùíîñòè S �100 (ñì. ïîñòàíîâêó çàäà÷è À, óñëîâèÿ ðàçðåøèìîñòè (1));
2) îïòèìàëüíàÿ ìîùíîñòü ïåðâîãî ïðåäïðèÿòèÿ â ìîäåëüíûõ çàäà÷àõ 2, 3 ñî-
îòâåòñòâóåò îãðàíè÷åíèþ â âèäå ðàâåíñòâà 5 90;
3) îïòèìàëüíîå çíà÷åíèå öåëåâîãî ôóíêöèîíàëà ïðÿìîé çàäà÷è ïðè îïòèìàëü-
íîì ðàçìåùåíèè ïðåäïðèÿòèé (ìîäåëüíàÿ çàäà÷à 2) ìåíüøå (÷òî åñòåñòâåííî), ÷åì
â ñëó÷àå, êîãäà êîîðäèíàòû ïðåäïðèÿòèé ôèêñèðîâàíû (ìîäåëüíàÿ çàäà÷à 3).
×èñëåííûå ýêñïåðèìåíòû ïðîâîäèëèñü òàêæå äëÿ ñëåäóþùèõ îãðàíè÷åííûõ âûïóê-
ëûõ íà [0; 100] ôóíêöèé � i iY( ), i �1 3, ,� : ìîíîòîííî âîçðàñòàþùèõ íà [0; 100] ôóíê-
öèé � i i iY Y( ) � 2 ; � i i iY Y( ) , /� �0 5 3 2 ; � i i
Y
Y e i( )
( , )� �0 1
; � i i iY Y( ) � 4 è ìîíîòîííî
óáûâàþùåé íà [0; 100] ôóíêöèé � i i iY Y( ) ( )� �100 2 .
Îïèñàííûé àëãîðèòì ðåàëèçîâàí â ñðåäå Ìiñrîsîft Visuàl Studiî ÿçûêîì C++
ñ ïðèìåíåíèåì òåõíîëîãèè ðàçðàáîòêè ïðîãðàììíîãî èíòåðôåéñà WinÀÐi.
Àëãîðèòì ñîñòîèò èç äâóõ ÷àñòåé: èíòåðôåéñíîé ÷àñòè, ðåàëèçîâàííîé ÿçûêîì
Visuàl C++ 6.0, è âû÷èñëèòåëüíîé ÷àñòè, êîòîðàÿ ðåàëèçóåò r-àëãîðèòì Øîðà ìèíè-
ìèçàöèè ôóíêöèé, íàïèñàííîé íà ÿçûêå Visual Fortran 6.5.
Çàìå÷àíèå 3. Ïî ðåçóëüòàòàì ìíîãî÷èñëåííûõ âû÷èñëèòåëüíûõ ýêñïåðè-
ìåíòîâ ìîæíî çàêëþ÷èòü, ÷òî îïèñàííûé àëãîðèòì ðàáîòàåò è äëÿ ñëó÷àÿ, êîãäà
� i ( )� , i N�1, ,� , — îãðàíè÷åííûå âîãíóòûå ôóíêöèè ñâîåãî àðãóìåíòà. Òîãäà
äâîéñòâåííàÿ çàäà÷à (6) ïðèâîäèòñÿ âìåñòî âèäà (17) ê ñëåäóþùåìó:
max min min ( , , )
� �
� �
� � �# �N Y U
G Y2 .
×èñëåííûå ýêñïåðèìåíòû ïðîâîäèëèñü, â ÷àñòíîñòè, äëÿ òàêèõ îãðàíè÷åí-
íûõ âîãíóòûõ íà [0;100] ôóíêöèé � i ( )� , i �1 3, ,� , êàê ìîíîòîííî âîçðàñòàþùèå
íà [0;100]: � i i iY Y( )
/� 1 2
, � i i iY Y( )
/� 3 2
è ìîíîòîííî óáûâàþùèå íà [0;100]:
�
i i
iY
Y
( ) cos�
��
�
�
�
�
�
200
.
150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Fig. 4
�1
*
�2
*
�3
*
ÇÀÊËÞ×ÅÍÈÅ
Ñôîðìóëèðîâàíà íåïðåðûâíàÿ îäíîïðîäóêòîâàÿ íåëèíåéíàÿ çàäà÷à îïòèìàëü-
íîãî ðàçáèåíèÿ ìíîæåñòâà � èç n-ìåðíîãî åâêëèäîâà ïðîñòðàíñòâà íà åãî íå-
ïåðåñåêàþùèåñÿ ïîäìíîæåñòâà ñ ðàçìåùåíèåì èõ öåíòðîâ ïðè îãðàíè÷åíèÿõ
â âèäå ðàâåíñòâ è íåðàâåíñòâ äëÿ ñëó÷àÿ âûïóêëîãî öåëåâîãî ôóíêöèîíàëà.
Ïðèâîäèòñÿ îáîñíîâàíèå ìåòîäà ðåøåíèÿ ýòîé çàäà÷è, êîòîðûé îñíîâàí íà ïå-
ðåõîäå îò èñõîäíîé íåëèíåéíîé áåñêîíå÷íîìåðíîé çàäà÷è îïòèìèçàöèè ÷åðåç
ôóíêöèîíàë Ëàãðàíæà ñ ïðèìåíåíèåì òåîðèè Êóíà-Òàêêåðà ê êîíå÷íîìåðíîé
ñ íåãëàäêèì öåëåâûì ôóíêöèîíàëîì, äëÿ ìèíèìèçàöèè êîòîðîãî ïðèìåíÿåòñÿ
ìåòîä îáîáùåííûõ ïñåâäîãðàäèåíòîâ ñ ðàñòÿæåíèåì ïðîñòðàíñòâà, áëèçêèé ê
r-àëãîðèòìó Øîðà.  îòëè÷èå îò ëèíåéíûõ çàäà÷ îïòèìàëüíîãî ðàçáèåíèÿ
ìíîæåñòâ, ðàññìîòðåííûõ â [1], äëÿ êîòîðûõ îïòèìàëüíîå ðåøåíèå èñõîäíîé
áåñêîíå÷íîìåðíîé çàäà÷è óäàåòñÿ íàéòè â ÿâíîì âèäå, â íåëèíåéíîì ñëó÷àå
îòûñêàíèå îïòèìàëüíîãî ðåøåíèÿ èñõîäíîé áåñêîíå÷íîìåðíîé çàäà÷è
ñâîäèòñÿ ê îòûñêàíèþ ðåøåíèÿ íåêîòîðîãî âñïîìîãàòåëüíîãî îïåðàòîðíîãî
óðàâíåíèÿ ñ ïàðàìåòðàìè.
Íà îñíîâå ïðåäëîæåííîãî ìåòîäà ðàçðàáîòàí è ïðîãðàììíî ðåàëèçîâàí àëãî-
ðèòì, êîòîðûé ïðîèëëþñòðèðîâàí íà ìîäåëüíûõ çàäà÷àõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê è ñ å ë å â à Å . Ì . , Ø î ð Í . Ç . Íåïðåðûâíûå çàäà÷è îïòèìàëüíîãî ðàçáèåíèÿ ìíîæåñòâ: òåîðèÿ,
àëãîðèòìû, ïðèëîæåíèÿ. — Ê.: Íàóê. äóìêà, 2005. — 564 ñ.
2. Ó ñ Ñ . À . Ðåøåíèå îäíîãî êëàññà áåñêîíå÷íîìåðíûõ çàäà÷: Àâòîðåô. äèñ. … êàíä. ôèç.-ìàò. íàóê.
— Õàðüêîâ, 1992. — 16 ñ.
3. Â à ñ è ë ü å â Ô . Ï . Ìåòîäû ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷. — Ì.: Íàóêà, 1981. — 400 ñ.
4. È î ô ô å À . Ä . , Ò è õ î ì è ð î â Â . Ì . Òåîðèÿ ýêñòðåìàëüíûõ çàäà÷. — Ì.: Íàóêà, 1974. — 480 ñ.
5. Ò ð ó õ à å â Ð . Í . , Õ î ì å í þ ê  .  . Òåîðèÿ íåêëàññè÷åñêèõ âàðèàöèîííûõ çàäà÷. — Ë.: ËÃÓ,
1971. — 168 ñ.
6. Ø î ð Í . Ç . Ìåòîäû ìèíèìèçàöèè íåäèôôåðåíöèðóåìûõ ôóíêöèé è èõ ïðèëîæåíèå. — Ê.: Íàóê.
äóìêà, 1979. — 200 ñ.
7. Ô å ä î ð î â  .  . ×èñëåííûå ìåòîäû ìàêñèìèíà. — Ì.: Íàóêà, 1979. — 280 ñ.
Ïîñòóïèëà 03.07.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 151
|
| id | nasplib_isofts_kiev_ua-123456789-72005 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-01T15:13:18Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Киселёва, Е.М. Дунайчук, М.С. 2014-12-15T22:24:11Z 2014-12-15T22:24:11Z 2008 Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала / Е.М. Киселёва, М.С. Дунайчук // Кибернетика и системный анализ. — 2008. — № 2. — С. 134-151. — Бібліогр.: 7 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72005 519.8 Математическая теория непрерывных линейных задач оптимального разбиения множеств (ОРМ) n - мерного евклидова пространства, являющихся неклассическими задачами бесконечномерного математического программирования с булевыми переменными. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала Article published earlier |
| spellingShingle | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала Киселёва, Е.М. Дунайчук, М.С. Системный анализ |
| title | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала |
| title_full | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала |
| title_fullStr | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала |
| title_full_unstemmed | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала |
| title_short | Решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала |
| title_sort | решение непрерывной нелинейной задачи оптимального разбиения множеств с размещением центров подмножеств для случая выпуклого целевого функционала |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/72005 |
| work_keys_str_mv | AT kiselevaem rešenienepreryvnoinelineinoizadačioptimalʹnogorazbieniâmnožestvsrazmeŝeniemcentrovpodmnožestvdlâslučaâvypuklogocelevogofunkcionala AT dunaičukms rešenienepreryvnoinelineinoizadačioptimalʹnogorazbieniâmnožestvsrazmeŝeniemcentrovpodmnožestvdlâslučaâvypuklogocelevogofunkcionala |