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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2016
Hauptverfasser:	Пичугина, О.С., Яковлев, С.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системный анализ
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/142062
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:	О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации / О.С. Пичугина, С.В. Яковлев // Кибернетика и системный анализ. — 2016. — Т. 52, № 6. — С. 102-113. — Бібліогр.: 36 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-142062
record_format	dspace
spelling	irk-123456789-1420622018-09-25T01:22:55Z О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации Пичугина, О.С. Яковлев, С.В. Системный анализ Введены понятия функционального представления множества точек евклидового арифметического пространства и продолжения функций с данного множества в его надмножество. Показана связь функциональных представлений множеств и продолжений с них. Получены строгие функциональные представления булевого, общего перестановочного и полиперестановочного множеств. Продемонстрированы преимущества применения строгих представлений евклидовых комбинаторных множеств в построении функциональных продолжений с этих множеств и решении комбинаторных задач. Введено поняття функціонального представлення множини точок евклідового арифметичного простору і продовження функцій з даної множини у її надмножину. Показано зв'язок функціональних представлень множин і продовжень з них. Отримано строгі функціональні представлення булевої, загальної перестановочної та поліперестановочної множин. Продемонстровано переваги застосування строгих представлень евклідових комбінаторних множин у побудові функціональних продовжень з цих множин і розв'язанні комбінаторних задач. The concepts of functional representation of a set of points of the Euclidean arithmetic space and an extension of functions from the set onto its superset are introduced. Functional representations of sets are related to their extensions. Strict functional representations of the Boolean set, general permutation, and polypermutation sets are derived. The advantages of applying strict representations of Euclidean combinatorial sets to construct functional extensions from them and to solve combinatorial problems are presented. 2016 Article О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации / О.С. Пичугина, С.В. Яковлев // Кибернетика и системный анализ. — 2016. — Т. 52, № 6. — С. 102-113. — Бібліогр.: 36 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/142062 519.85 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Пичугина, О.С. Яковлев, С.В. О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации Кибернетика и системный анализ
description	Введены понятия функционального представления множества точек евклидового арифметического пространства и продолжения функций с данного множества в его надмножество. Показана связь функциональных представлений множеств и продолжений с них. Получены строгие функциональные представления булевого, общего перестановочного и полиперестановочного множеств. Продемонстрированы преимущества применения строгих представлений евклидовых комбинаторных множеств в построении функциональных продолжений с этих множеств и решении комбинаторных задач.
format	Article
author	Пичугина, О.С. Яковлев, С.В.
author_facet	Пичугина, О.С. Яковлев, С.В.
author_sort	Пичугина, О.С.
title	О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации
title_short	О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации
title_full	О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации
title_fullStr	О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации
title_full_unstemmed	О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации
title_sort	о непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
topic_facet	Системный анализ
url	http://dspace.nbuv.gov.ua/handle/123456789/142062
citation_txt	О непрерывных представлениях и функциональных продолжениях в задачах комбинаторной оптимизации / О.С. Пичугина, С.В. Яковлев // Кибернетика и системный анализ. — 2016. — Т. 52, № 6. — С. 102-113. — Бібліогр.: 36 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT pičuginaos onepreryvnyhpredstavleniâhifunkcionalʹnyhprodolženiâhvzadačahkombinatornojoptimizacii AT âkovlevsv onepreryvnyhpredstavleniâhifunkcionalʹnyhprodolženiâhvzadačahkombinatornojoptimizacii
first_indexed	2025-07-10T14:04:19Z
last_indexed	2025-07-10T14:04:19Z
_version_	1837269009867735040
fulltext	ÓÄÊ 519.85 Î.Ñ. ÏÈ×ÓÃÈÍÀ, Ñ.Â. ßÊÎÂËÅÂ Î ÍÅÏÐÅÐÛÂÍÛÕ ÏÐÅÄÑÒÀÂËÅÍÈßÕ È ÔÓÍÊÖÈÎÍÀËÜÍÛÕ ÏÐÎÄÎËÆÅÍÈßÕ Â ÇÀÄÀ×ÀÕ ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ Àííîòàöèÿ. Ââåäåíû ïîíÿòèÿ ôóíêöèîíàëüíîãî ïðåäñòàâëåíèÿ ìíîæåñòâà òî÷åê åâêëèäîâîãî àðèôìåòè÷åñêîãî ïðîñòðàíñòâà è ïðîäîëæåíèÿ ôóíêöèé ñ äàííîãî ìíîæåñòâà â åãî íàäìíîæåñòâî. Ïîêàçàíà ñâÿçü ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé ìíîæåñòâ è ïðîäîëæåíèé ñ íèõ. Ïîëó÷åíû ñòðîãèå ôóíêöèî- íàëüíûå ïðåäñòàâëåíèÿ áóëåâîãî, îáùåãî ïåðåñòàíîâî÷íîãî è ïîëèïåðåñòàíî- âî÷íîãî ìíîæåñòâ. Ïðîäåìîíñòðèðîâàíû ïðåèìóùåñòâà ïðèìåíåíèÿ ñòðîãèõ ïðåäñòàâëåíèé åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ â ïîñòðîåíèè ôóíêöèî- íàëüíûõ ïðîäîëæåíèé ñ ýòèõ ìíîæåñòâ è ðåøåíèè êîìáèíàòîðíûõ çàäà÷. Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, åâêëèäîâî êîìáèíàòîðíîå ìíîæåñòâî, íåïðåðûâíîå ôóíêöèîíàëüíîå ïðåäñòàâëåíèå ìíîæåñòâà, ïðî- äîëæåíèå ôóíêöèé, îáùåå ìíîæåñòâî ïåðåñòàíîâîê, áóëåâî ìíîæåñòâî. ÂÂÅÄÅÍÈÅ Íàñòîÿùàÿ ñòàòüÿ ïîñâÿùåíà ðàçðàáîòêå íîâûõ ïîäõîäîâ ê ïðåäñòàâëåíèþ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ [1], èõ êëàññèôèêàöèè è èññëåäîâàíèþ ñâîéñòâ ôóíêöèé, çàäàííûõ íà ýòèõ ìíîæåñòâàõ. Óêàçàííûå íàïðàâëåíèÿ èññëå- äîâàíèé òåñíî ñâÿçàíû ñ ðàáîòàìè [2, 3], ïîñâÿùåííûìè îáùåé êëàññèôèêàöèè êîìáèíàòîðíûõ îáúåêòîâ è ìåòîäîâ êîìáèíàòîðíîé îïòèìèçàöèè. Ïîíÿòèå åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ êàê íàáîðîâ ÷èñëîâûõ êîì- áèíàòîðíûõ êîíôèãóðàöèé, îòëè÷àþùèõñÿ ñîñòàâîì èëè ïîðÿäêîì ñëåäîâàíèÿ ýëåìåíòîâ, ïðè èõ îòîáðàæåíèè â àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî âïåð- âûå áûëî ââåäåíî Þ.Ã. Ñòîÿíîì [1]. Äàëüíåéøåå ðàçâèòèå ýòîãî íàïðàâëåíèÿ ïî- ëó÷èëî íàçâàíèå «åâêëèäîâà êîìáèíàòîðíàÿ îïòèìèçàöèÿ» [4–6]. Ôóíäàìåíòàëüíûå èññëåäîâàíèÿ â ýòîé îáëàñòè óñëîâíî ìîæíî ðàçäåëèòü íà òðè âçàèìîñâÿçàííûõ íàïðàâëåíèÿ: • èçó÷åíèå òîïîëîãî-ìåòðè÷åñêèõ ñâîéñòâ åâêëèäîâûõ êîìáèíàòîðíûõ ìíî- æåñòâ è èõ ïîäìíîæåñòâ; • èññëåäîâàíèå ñâîéñòâ ôóíêöèé, çàäàííûõ íà åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâàõ, âêëþ÷àÿ âûïóêëûå è ñèëüíîâûïóêëûå ïðîäîëæåíèÿ ýòèõ ôóíêöèé íà âûïóêëûå îáîëî÷êè óêàçàííûõ ìíîæåñòâ; • ðàçðàáîòêà íîâûõ ìåòîäîâ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè. Ñâîéñòâà åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ è èõ âûïóêëûõ îáîëî÷åê îïèñàíû â ðàáîòàõ [4, 5, 7–12]. Çàìåòèì, ÷òî øèðîêèé êëàññ åâêëèäîâûõ êîìáè- íàòîðíûõ ìíîæåñòâ îáëàäàåò ñâîéñòâîì, ñîãëàñíî êîòîðîìó òî÷êè ìíîæåñòâà è òîëüêî îíè ÿâëÿþòñÿ âåðøèíàìè ñâîèõ âûïóêëûõ îáîëî÷åê — êîìáèíàòîðíûõ ìíîãîãðàííèêîâ. Òàêèå ìíîæåñòâà íàçîâåì âåðøèííî ðàñïîëîæåííûìè. Âåð- øèííî ðàñïîëîæåííûå ìíîæåñòâà, ïðèíàäëåæàùèå îäíîâðåìåííî îïèñàííîé ãèïåðñôåðå, íàçîâåì ïîëèýäðàëüíî-ñôåðè÷åñêèìè. Òåîðèÿ âûïóêëûõ ïðîäîëæåíèé ôóíêöèé, çàäàííûõ íà âåðøèííî ðàñïîëîæåí- íûõ ìíîæåñòâàõ, ïîäðîáíî èçëîæåíà â [13, 14] è ïîëó÷èëà ðàçâèòèå, â òîì ÷èñëå äëÿ ïîëèýäðàëüíî-ñôåðè÷åñêèõ ìíîæåñòâ, â ðàáîòàõ [15–19]. Îñíîâíûå àëãîðèòìû è ìå- òîäû åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè îñâåùåíû â [4, 5, 20–27]. Ïðàêòè÷åñêèå çàäà÷è îïòèìèçàöèè ÷àñòî èìåþò ðàçëè÷íûå ôîðìóëèðîâ- êè — â âèäå çàäà÷ íà ãðàôàõ, öåëî÷èñëåííûõ, êîìáèíàòîðíûõ èëè íåïðåðûâíûõ 102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 © Î.Ñ. Ïè÷óãèíà, Ñ.Â. ßêîâëåâ, 2016 çàäà÷ [7–9], ïðåäñòàâëÿÿ äîïóñòèìóþ îáëàñòü ãðàôîì, öåëî÷èñëåííîé ðåøåòêîé ñ äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè, êîìáèíàòîðíûì ìíîæåñòâîì èëè ïåðåñå÷å- íèåì íåïðåðûâíûõ îáëàñòåé åâêëèäîâîãî àðèôìåòè÷åñêîãî ïðîñòðàíñòâà ñîîòâåòñòâåííî. Êàæäàÿ èç òàêèõ ïîñòàíîâîê ïîðîæäàåò ñâîè ìåòîäû îïòèìèçà- öèè, ñðåäè êîòîðûõ ïîñëåäíèå ôîðìóëèðîâêè, èñïîëüçóþùèå íåïðåðûâíûå ïðåäñòàâëåíèÿ äèñêðåòíûõ ìíîæåñòâ, çàíèìàþò îñîáîå ìåñòî, ïîñêîëüêó äàþò âîçìîæíîñòü èñïîëüçîâàòü âåñü àðñåíàë ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ. Åâêëèäîâû êîìáèíàòîðíûå ìíîæåñòâà ïðåäñòàâëÿþò îñîáûé èíòåðåñ îòíî- ñèòåëüíî âîçìîæíîñòè íåïðåðûâíûõ ïðåäñòàâëåíèé, ïîñêîëüêó ïîçâîëÿþò ïî- ãðóæåíèå â ïðîñòðàíñòâî òî÷åê R n , èññëåäîâàíèå èõ ãåîìåòðè÷åñêèõ îáðàçîâ è ñîîòâåòñòâóþùèõ êîìáèíàòîðíûõ ìíîãîãðàííèêîâ. Òàê, íàïðèìåð, ìíîãîãðàí- íèê àíàëèòè÷åñêè çàäàåòñÿ ñèñòåìîé ëèíåéíûõ îãðàíè÷åíèé, è ýòà ñèñòåìà ÿâëÿ- åòñÿ åãî íåïðåðûâíûì ïðåäñòàâëåíèåì. Â äàííîé ñòàòüå èññëåäóåòñÿ âîçìîæ- íîñòü àíàëèòè÷åñêîãî çàäàíèÿ ïðîèçâîëüíîãî ãåîìåòðè÷åñêîãî ìåñòà òî÷åê, â òîì ÷èñëå åâêëèäîâîãî êîìáèíàòîðíîãî ìíîæåñòâà, è ïðèìåíåíèå ýòèõ àíàëè- òè÷åñêèõ ïðåäñòàâëåíèé ìíîæåñòâ â åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè. 1. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ðàññìîòðèì çàäà÷ó îïòèìèçàöèè âèäà f x( ) min� , (1) x E R n� � , (2) ïîëàãàÿ, ÷òî ôóíêöèÿ (1) îïðåäåëåíà íà ìíîæåñòâå E. Ìíîæåñòâîì E ìîæåò áûòü ïðîèçâîëüíîå ìíîæåñòâî òî÷åê R n : äèñêðåòíîå èëè êîí- òèíóàëüíîå, îäíîñâÿçíîå èëè ìíîãîñâÿçíîå ìíîæåñòâî ñ êîìïîíåíòàìè ñâÿçíîñòè è ò.ä. 2. ÔÓÍÊÖÈÎÍÀËÜÍÛÅ ÏÐÅÄÑÒÀÂËÅÍÈß ÌÍÎÆÅÑÒÂ 2.1. Îñíîâíûå îïðåäåëåíèÿ. Ôóíêöèîíàëüíûì íàçîâåì ïðåäñòàâëåíèå ìíîæå- ñòâà E R n� ñ ïîìîùüþ ôóíêöèîíàëüíûõ çàâèñèìîñòåé âèäà f x j J mj m( ) , , ...,� � � ��0 1{ }, (3) f x j J Jj m m( ) , \� � �0 . (4) Â çàâèñèìîñòè îò òèïà ôóíêöèé (3), (4) ôóíêöèîíàëüíûå ïðåäñòàâëåíèÿ ìî- ãóò áûòü ëèíåéíûìè è íåëèíåéíûìè, íåïðåðûâíûìè, äèôôåðåíöèðóåìûìè, ãëàäêèìè, âûïóêëûìè è ò.ï. Â îáîçíà÷åíèÿõ M x R f x j J f x j J Jj n j m j m m � � � � � � � � � � : ( ) , , ( ) , \ , 0 0 (5) ôóíêöèîíàëüíîå ïðåäñòàâëåíèå (3), (4) ïðèîáðåòàåò ôîðìó E M j J j m = � � . (6) Ââåäåì íåñêîëüêî òèïîâ òàêèõ ïðåäñòàâëåíèé. Òàê, ñèñòåìa (3), (4) íàçûâàåòñÿ: à) ñòðîãèì ïðåäñòàâëåíèåì E, åñëè m m� �, (7) â ïðîòèâíîì ñëó÷àå — íåñòðîãèì; ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 103 á) íåèçáûòî÷íûì ïðåäñòàâëåíèåì E, åñëè èçâëå÷åíèå ëþáîãî èç îãðàíè÷å- íèé (3), (4) ïðèâîäèò ê íàðóøåíèþ (6): � � � � i J M Em j i j ; (8) â) îãðàíè÷åííûì ïðåäñòàâëåíèåì E, åñëè â (5) åñòü îãðàíè÷åííûå ìíîæåñòâà: � �j Jm , rj > 0 , a R M C aj n j r jj � �: ( ) (C ar jj ( ) — øàð ðàäèóñà rj ñ öåíòðîì â òî÷êå a j ). Äëÿ íåèçáûòî÷íûõ ïðåäñòàâëåíèé ââåäåì òàêæå êëàññèôèêàöèþ ïî ÷èñëó ôóíêöèé â ñòðîãîé ÷àñòè (3). Òàê, ïðåäñòàâëåíèå (3), (4), (8) íàçîâåì: • îäíîêîìïîíåíòíûì, åñëè m� �1; • êàñàòåëüíûì, åñëè m� � 2 è E — ìíîæåñòâî òî÷åê êàñàíèÿ äâóõ ïîâåðõíîñòåé; • ïåðåñåêàþùèìñÿ â ñëó÷àå, åñëè m n� � , (9) ò.å. E îáðàçóåòñÿ â ïåðåñå÷åíèè n ïîâåðõíîñòåé; • ñìåøàííûì â ñëó÷àå 2� ��m n. Çàìå÷àíèå 1. Ïðåäñòàâëåíèå (3), (4) ìîæåò îáëàäàòü îïðåäåëåííûìè ñâîéñòâàìè â ïîäîáëàñòÿõ R n , ïîýòîìó â ñëó÷àå íåîáõîäèìîñòè óêàçûâàåòñÿ åãî òèï è îáëàñòü. Öåëü ñòàòüè — ðåøåíèå çàäà÷ âèäà (1), (2), â ïåðâóþ î÷åðåäü êîìáèíàòîð- íûõ, ñ ïîìîùüþ ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé äîïóñòèìîé îáëàñòè. 2.2. Àíàëèç ëèòåðàòóðíûõ äàííûõ: ôóíêöèîíàëüíûå ïðåäñòàâëåíèÿ è ïðèìåíåíèÿ. Äëÿ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ ïåðñïåêòèâà ôóíêöèî- íàëüíîãî ïðåäñòàâëåíèÿ îçíà÷àåò âîçìîæíîñòü íåïðåðûâíîé ïîñòàíîâêè äèñ- êðåòíîé çàäà÷è (1), (2) íà êîíå÷íîì ìíîæåñòâå òî÷åê \| \|E � � (10) è ïðèìåíåíèÿ íåëèíåéíîé îïòèìèçàöèè ê åå ðåøåíèþ [28]. Ðàññìîòðèì èçâåñòíîå ìíîæåñòâî áóëåâûõ âåêòîðîâ [8, 21, 29–31] E Bn n� � � �{ , }1 1 . (11) Çàäà÷à (1), (2), (11) èìååò ìíîæåñòâî ïðàêòè÷åñêèõ ïðèëîæåíèé [29] è ÿâëÿ- åòñÿ, êàê ïðàâèëî, NP-òðóäíîé. Ïîñêîëüêó îíà ïðåäñòàâëÿåò èíòåðåñ êàê ñ ïðàê- òè÷åñêîé, òàê è ñ òåîðåòè÷åñêîé òî÷åê çðåíèÿ, äëÿ åå ðåøåíèÿ ðàçðàáîòàíî ìíî- æåñòâî ìåòîäîâ [21, 29–33] êàê êîìáèíàòîðíûõ, òàê è íåïðåðûâíûõ. Íåïðåðûâ- íûå ïîäõîäû ê (1), (2), (11) îñíîâàíû íà åå íåïðåðûâíûõ ïåðåôîðìóëèðîâêàõ è ðåëàêñàöèÿõ [29, 30]. Ê ïîñëåäíèì îòíîñÿòñÿ, íàïðèìåð, ïîëóîïðåäåëåííûå ðå- ëàêñàöèè [31]. Îäíèì èç ìåòîäîâ òðàíñôîðìàöèè ýòîé äèñêðåòíîé çàäà÷è â íå- ïðåðûâíóþ ÿâëÿåòñÿ ïðèìåíåíèå ñëåäóþùåãî àíàëèòè÷åñêîãî ïðåäñòàâëåíèÿ óñëîâèÿ áóëåâîñòè (2), (11) [21, 30, 32, 33]: E B x R x x i Jn n i i n� � � � � �{ }: ,2 0 ( : , )E B x R x i Jn n i n� � � � � �{ }2 1 . (12) Êàê âèäèì, (12) — ñòðîãîå ïðåäñòàâëåíèå áóëåâîãî ìíîæåñòâà âèäà (3), (7), ãäå B f x x x i Jn i i i n: ( ) ,= 2 � � ( � � �B f x x i Jn i i n: ( ) ,= 2 1 ). (13) Áåçóñëîâíàÿ áóëåâàÿ çàäà÷à (1), (2), (11) òðàíñôîðìèðóåòñÿ â óñëîâíóþ íå- ïðåðûâíóþ (1), (2), (12), à ïîñëåäíÿÿ, â ñâîþ î÷åðåäü, — â áåçóñëîâíóþ çàäà÷ó c ôóíêöèåé Ëàãðàíæà: �( , ) ( ) ( ) minx f x f xj j j n � �� 1 , (14) 104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 ãäå { }f xj j( ) çàäàíî ñ ïîìîùüþ (13), ��R n . Â âû÷èñëèòåëüíûõ ñõåìàõ ðåøå- íèÿ (1), (2), (12) ðàññìàòðèâàåòñÿ ðåëàêñàöèÿ òèïà [30] �1 1 ( , ) ( ) ( ) minx f x f xj j n � �� âìåñòî (14), êîòîðàÿ äëÿ Bn , íàïðèìåð, ìîæåò áûòü ïðåäñòàâëåíà â âèäå �1 2 1 2 1 1 2 ( , ) ( ) ( ) ( )x f x x x f x xi i j n i i n � � �� n 4 min. (15) Êàê âèäèì, â (15) îãðàíè÷åíèÿ (12) ñóùåñòâåííî îñëàáëåíû è âûðàæàþò òå- ïåðü ñâîéñòâî Bn áûòü âïèñàííûì â ñôåðó ñ öåíòðîì â 1 2 � � � � � � n ðàäèóñà n 2 [21]. Äëÿ ïåðåõîäà ê ýêâèâàëåíòíîé ïåðåôîðìóëèðîâêå èñõîäíîé çàäà÷è ìîæíî èñ- ïîëüçîâàòü ñëåäóþùèé ñïîñîá [30]: � â (15) âûáèðàåòñÿ òàê, ÷òîáû ãàðàíòèðîâàòü âîã- íóòîñòü�1 ( , )x � , è äîáàâëÿåòñÿ óñëîâèå ïðèíàäëåæíîñòè åäèíè÷íîìó ãèïåðêóáó: x PB Bn n� � conv , (16) PB x R xn n� � � �{ }: 0 1 . (17) Çàäà÷à (15), (16) ýêâèâàëåíòíà èñõîäíîé (1), (2), (11), òàê êàê ìíîæåñòâî Bn — âåðøèííî ðàñïîëîæåíî, à ìèíèìóì âîãíóòîé ôóíêöèè íà âûïóêëîì ìíî- ãîãðàííèêå äîñòèãàåòñÿ â åãî âåðøèíå. Ïðåäñòàâëåíèå (12) òàêæå èñïîëüçóåòñÿ â ðàçëè÷íûõ ñõåìàõ øòðàôíûõ ôóíêöèé äëÿ ðåøåíèÿ áóëåâûõ çàäà÷. Òàê, íàïðèìåð, â [32] îíî ñëóæèò îñíîâîé äëÿ ïîñòðîåíèÿ êâàäðàòè÷íîé øòðàôíîé ôóíêöèè: �2 2 2 1 ( , ) ~ ( ) ( ) minx f x x xi i j n � �� , (18) ãäå ~ ( )f x — ñãëàæèâàíèå ôóíêöèè (1). Ýòî ïîçâîëÿåò ñâåñòè èñõîäíóþ çàäà÷ó ê ñåðèè âûïóêëûõ çàäà÷ âèäà (18) c ïàðàìåòðîì � : � � �� { }j j j j , . (19) Çàìåòèì, ÷òî (15) ìîæåò áûòü íàçâàíà ñôåðè÷åñêîé ðåëàêñàöèîííîé çàäà- ÷åé, â òî âðåìÿ êàê (1), (16) ÿâëÿåòñÿ ïîëèýäðàëüíîé ðåëàêñàöèîííîé çàäà÷åé [8, 29, 30] ê èñõîäíîé. Èòàê, â áóëåâîé îïòèìèçàöèè íàðÿäó ñ ôóíêöèîíàëüíûì ïðåäñòàâëåíè- åì (12) íàõîäèò ïðèìåíåíèå ïðåäñòàâëåíèå Bn êàê ïåðåñå÷åíèå ãèïåðêóáà (16) è ãèïåðñôåðû: x n i i n � � � � � � � � � � 1 2 4 2 1 . (20) Â ðàçä. 2.3 ýòî íàáëþäåíèå îáîáùàåòñÿ íà ïðîèçâîëüíîå ìíîæåñòâî, âïèñàí- íîå â ñôåðó. Èçâåñòíî ìíîæåñòâî äðóãèõ íåïðåðûâíûõ ïîñòàíîâîê áóëåâûõ çàäà÷. Òàê, íàïðèìåð, â [30] ïðåäñòàâëåíî óñëîâèå áóëåâîñòè x yi i� �1 , x yi i� � 0 , x yi i, � 0 , i J� n , ïîçâîëÿþùåå ïåðåôîðìóëèðîâàòü èñõîäíóþ çàäà÷ó â âèäå íå- ïðåðûâíîé â ïðîñòðàíñòâå R n2 . ×àñòî íåïðåðûâíûå ôîðìóëèðîâêè ïðèâÿçûâàþòñÿ ê êîíêðåòíîìó êëàññó çà- äà÷. Òàê, íàïðèìåð, èçâåñòíà ýêâèâàëåíòíàÿ ôîðìóëèðîâêà áåçóñëîâíîé áóëåâîé ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 105 êâàäðàòè÷íîé çàäà÷è (Unconstrained Binary Quadratic Problem) [21, 29–33] f x x Ax c x x E ( ) min� � � �� T T , E B Bn n= , � (21) â âèäå ëèíåéíîé çàäà÷è íà ìíîãîãðàííèêå conv = T( : , )y R y x x x Bn n� � � 2 ñ ïîñëå- äóþùåé åå ðåëàêñàöèåé íà ìíîæåñòâå ïîëóîïðåäåëåííûõ ìàòðèö ïîðÿäêà n [31]. Â [33] çàäà÷à (21) íà E Bn= � ñâåäåíà ê íåëèíåéíîé â ïðîñòðàíñòâå R Cn� 1 2 ââå- äåíèåì äîïîëíèòåëüíûõ ïåðåìåííûõ y x x yij i j ij� �: 2 1 , i j< , i, j Jn� . Êàê âèäíî, ïîñëåäíèå ñïîñîáû ïðèâîäÿò ê íåïðåðûâíîé ôîðìóëèðîâêå áó- ëåâûõ çàäà÷ â ïðîñòðàíñòâå áîëüøåé ðàçìåðíîñòè. Ïðåèìóùåñòâî ïîñòðîåíèÿ ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé (3), (4) ñîñòîèò â âîçìîæíîñòè íåïðåðûâíûõ ïî- ñòàíîâîê äèñêðåòíûõ çàäà÷ ïðè íåèçìåííîé ðàçìåðíîñòè çàäà÷è. 2.3. Ïîëèýäðàëüíî-ñôåðè÷åñêèå ôóíêöèîíàëüíûå ïðåäñòàâëåíèÿ. Ïóñòü E — ìíîæåñòâî âèäà (10), âïèñàííîå â ñôåðó S ar ( ) ðàäèóñà r ñ öåíòðîì a R n� : E S ar� ( ) . (22) Òîãäà îíî îáðàçóåòñÿ â ïåðåñå÷åíèè S ar ( ) ñ ìíîãîãðàííèêîì P E� conv : E P S ar� � ( ) . (23) Ïðåäñòàâëåíèå (23) íàçûâàåòñÿ ïîëèýäðàëüíî-ñôåðè÷åñêèì ïðåäñòàâëåíè- åì E. Äëÿ åãî ïîñòðîåíèÿ íåîáõîäèìî óñòàíîâèòü âïèñàííîñòü äàííîãî ìíîæåñòâà â ñôåðó è ðåøèòü òðàäèöèîííóþ â ïîëèýäðàëüíîé êîìáèíàòîðèêå çàäà÷ó àíàëèòè- ÷åñêîãî îïèñàíèÿ ìíîãîãðàííèêà P [8], â ÷àñòíîñòè ïîècêà åãî íåïðèâîäèìîé ñèñ- òåìû îãðàíè÷åíèé. Ïîëèýäðàëüíî-ñôåðè÷åñêîå ïðåäñòàâëåíèå E ïîçâîëÿåò ýêâèâàëåíòíî ïåðå- ôîðìóëèðîâàòü (1), (2), (10) â âèäå íåïðåðûâíîé çàäà÷è f x E x P S ar ( ) min ( ) � � � , ïî- ëèýäðàëüíàÿ è ñôåðè÷åñêàÿ ðåëàêñàöèè êîòîðîé èìåþò ñîîòâåòñòâåííî âèä f x P ( ) min� , f x S ar ( ) min ( ) � . (24) Êàê ïðàâèëî, â îïòèìèçàöèîííûõ àëãîðèòìàõ èñïîëüçóåòñÿ ïîëèýäðàëüíàÿ ðåëàêñàöèÿ [8, 29, 30]. Ïðèìåðîì ñîâìåñòíîãî èñïîëüçîâàíèÿ îáåèõ çàäà÷ (24) ñëóæèò ïîëèýäðàëüíî-ñôåðè÷åñêèé ìåòîä ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷ [24]. Îòìåòèì, ÷òî ïîëèýäðàëüíî-ñôåðè÷åñêîå ïðåäñòàâëåíèå íåâûðîæäåííîãî â òî÷êó äèñêðåòíîãî ìíîæåñòâà (\| \|E �1) ÿâëÿåòñÿ íåñòðîãèì íåëèíåéíûì ôóíêöèî- íàëüíûì ïðåäñòàâëåíèåì âèäà (3), (4), 1� ��m m . Äëÿ íåêîòîðûõ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ, âïèñàííûõ â ñôåðó, òàêèõ êàê îáùåå ìíîæåñòâî ïåðå- ñòàíîâîê, ïîëèïåðåñòàíîâîê, îòäåëüíûå êëàññû ðàçìåùåíèé è ñî÷åòàíèé, ýòî ïðåäñòàâëåíèå ëåãêî âûïèñûâàåòñÿ, ïîñêîëüêó àíàëèòè÷åñêèé âèä ñîîòâåòñòâóþ- ùèõ ìíîãîãðàííèêîâ èçâåñòåí [4, 5, 7, 11, 12, 34]. Îäíàêî ïðèìåíåíèå äàííîãî ïðåäñòàâëåíèÿ óæå âûçûâàåò çàòðóäíåíèå, òàê êàê ÷èñëî îãðàíè÷åíèé ìíîãîãðàííèêà èíîãäà ñðàâíèìî ñ ìîùíîñòüþ êîìáèíàòîðíîãî ìíîæåñòâà. Çàìå÷àíèå 2. Äëÿ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ âèäà (22): dim P n� , ê êîòîðûì îòíîñèòñÿ îáùåå ìíîæåñòâî ðàçìåùåíèé [5, 12, 21], ñãåíåðèðîâàííîå èç äâóõ ðàçëè÷íûõ ýëåìåíòîâ, â ÷àñòíîñòè áóëåâî ìíîæåñòâî, íåèçáûòî÷íîå ïîëèýä- ðàëüíî-ñôåðè÷åñêîå ïðåäñòàâëåíèå îïðåäåëÿåòñÿ îäíîçíà÷íî è ôîðìèðóåòñÿ äî- áàâëåíèåì ê íåïðèâîäèìîé ñèñòåìå íåðàâåíñòâ ìíîãîãðàííèêà P óðàâíåíèÿ îïè- ñàííîé ñôåðû, ò.å. ÿâëÿåòñÿ îäíîêîìïîíåíòíûì. Â îñòàëüíûõ ñëó÷àÿõ îíî áóäåò ñìåøàííûì è íåîäíîçíà÷íûì. Òàê, íàïðèìåð, äëÿ îáùåãî ìíîæåñòâà ïåðåñòàíî- 106 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 âîê [4, 5, 7, 34] E Gnk ( ) èç ìóëüòèìíîæåñòâà G gi i Jn � �{ } , â êîòîðîì k ýëåìåíòîâ ðàçëè÷íû, â ñòðîãóþ ÷àñòü (3) áóäóò âõîäèòü óðàâíåíèå îïèñàííîé ñôåðû, íàïðè- ìåð x gi i n i i n 2 1 2 1� � � �� , è óðàâíåíèå ãèïåðïëîñêîñòè x gi i n i i n � � � �� 1 1 , íà êîòîðîé ðàñïîëî- æåíî E Gnk ( ). 2.4. Ñòðîãèå ïðåäñòàâëåíèÿ íåêîòîðûõ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ. Ïîëèýäðàëüíî-ñôåðè÷åñêîå íåñòðîãîå ïðåäñòàâëåíèå Bn ñîäåðæèò âñåãî m n� �2 1 îãðàíè÷åíèé, à ñòðîãîå ïðåäñòàâëåíèå (12) ñîäåðæèò m n� óðàâíåíèé. Òåì íå ìåíåå, ñ ó÷åòîì òîãî, ÷òî ïðàêòè÷åñêèå çàäà÷è çà÷àñòóþ ôîðìó- ëèðóþòñÿ êàê áóëåâûå áîëüøîé ðàçìåðíîñòè [29], öåëåñîîáðàçíî ñîêðàòèòü ÷èñëî m ñ ïîìîùüþ äðóãèõ ñòðîãèõ ïðåäñòàâëåíèé äàííîãî ìíîæåñòâà. Ïðåäñòàâèì êàñà- òåëüíîå è îäíîêîìïîíåíòíîå ïðåäñòàâëåíèÿ Bn . Óòâåðæäåíèå 1. Ñèñòåìà \| \|x ni i n � � � 1 , (25) x ni i n 2 1� � � (26) çàäàåò êàñàòåëüíîå ïðåäñòàâëåíèå ìíîæåñòâà �Bn , êîòîðîå îáðàçóåòñÿ â ïåðåñå- ÷åíèè ïîâåðõíîñòè (25) ìîäóëüíîãî ìíîãîãðàííèêà è ãèïåðñôåðû (26). Äîêàçàòåëüñòâî. Â ñèëó ñèììåòðèè (25), (26) äîñòàòî÷íî ðàññìîòðåòü îá- ëàñòü D x x� �{ }: 0 è ïîêàçàòü, ÷òî òî÷êà x B Dn 0 1� � � � îáðàçóåòñÿ â êàñà- íèè (26) è ïëîñêîñòè: x ni i n � � � 1 , (27) ò.å. (27) — êàñàòåëüíàÿ ê (26) â òî÷êå x 0 . Çàïèñàâ óðàâíåíèå êàñàòåëüíîé ïëîñêîñòè ê âûïóêëîé ïîâåðõíîñòè (26) â x 0 � � � � � � � � � � � � � � ! � � ! � � � x x x x x xi i n x i i 2 1 0 2 0 2 1 0 1 1( ) ( ) ( ) 1 n n� � , ïîëó÷àåì èñêîìîå. Ñëåäñòâèå 1. Ñèñòåìà \| . \|x n i i n � � � � 05 21 , ( . )x n i i n � � � � 05 4 2 1 çàäàåò êàñàòåëüíîå ïðåäñòàâëåíèå ìíîæåñòâà Bn . Ïðîâåäåì ñðàâíåíèå äâóõ ñòðîãèõ ïðåäñòàâëåíèé áóëåâîãî ìíîæåñòâà �Bn — ðàíåå èçâåñòíîãî (12) è ïîëó÷åííîãî ïðåäñòàâëåíèÿ (25), (26). Îáà ïðåäñòàâëåíèÿ ñòðîãèå, íåëèíåéíûå, íåïðåðûâíûå, äèôôåðåíöèðóåìûå, âûïóêëûå. Èõ íåèçáû- òî÷íîñòü î÷åâèäíà, ïîñêîëüêó èçâëå÷åíèå ëþáîãî èç óñëîâèé (12) íàðóøàåò äèñ- êðåòíîñòü; ýòî êàñàåòñÿ òàêæå ëþáîãî èç îãðàíè÷åíèé (25), (26). Îòñþäà ñîãëàñ- íî (9) ñëåäóåò, ÷òî (12) — ïåðåñåêàþùååñÿ, à (25), (26) — êàñàòåëüíîå ïðåäñòàâëå- íèÿ �Bn , êîòîðîå â îòëè÷èå îò (12) ÿâëÿåòñÿ îãðàíè÷åííûì. Îãðàíè÷åííîñòü ïðåäñòàâëåíèÿ (25), (26) è ÷èñëî îãðàíè÷åíèé, íå çàâèñÿùåå îò ðàçìåðíîñòè çàäà- ÷è, — îñíîâíûå åãî ïðåèìóùåñòâà â ñðàâíåíèè ñ ïåðåñåêàþùèìñÿ ïðåäñòàâëåíè- åì (12). Ïðè ýòîì îíî ïîðîæäàåò äâå íåïðåðûâíûå ðåëàêñàöèîííûå çàäà÷è ïî îò- íîøåíèþ ê èñõîäíîé (1), (2), (11): ñôåðè÷åñêóþ (ñì. (24)) è çàäà÷ó íà ïîâåðõíîñòè ìîäóëüíîãî ìíîãîãðàííèêà M : f x x M ( ) min� � , ãäå äëÿ Bn çàäàåòñÿ M x x n i i n � � � � " # $� �: \| . \|05 21 , äëÿ �Bn çàäàåòñÿ (25). ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 107 Êàê è ëþáîå ñòðîãîå ïðåäñòàâëåíèå äèñêðåòíîãî ìíîæåñòâà îäíîêîìïîíåíò- íîå ïðåäñòàâëåíèå Bn îïðåäåëåíî íåîäíîçíà÷íî. Îäíî èç òàêèõ ïðåäñòàâëåíèé ôîðìèðóåòñÿ èç øòðàôíîãî ñëàãàåìîãî ôóíêöèè (18): F x x xi i j n 1 2 2 1 0( ) ( )� � � � � . (28) Äåéñòâèòåëüíî, F x x xi i1 2 20 0( ) ( )� ! � � , i J xn i� ! �{ }0 1, , i J x Bn n� ! � . Êðîìå (28) ïðåäñòàâëåíèå (12) ïîðîæäàåò ìíîæåñòâî îäíîêîìïîíåíòíûõ ïðåä- ñòàâëåíèé: F x f xi i n i1 1 2( ) ( )� � � � , � i � 0 , i Jn� , (29) ãäå f xi ( ) îïðåäåëåíî â (13). Êàê âèäèì, ñòðîãèå ôóíêöèîíàëüíûå ïðåäñòàâëåíèÿ àêêóìóëèðóþòñÿ â äðó- ãèõ ñòðîãèõ ïðåäñòàâëåíèÿõ, â òîì ÷èñëå îäíîêîìïîíåíòíûõ, êîòîðûå, â ñâîþ î÷åðåäü, öåëåñîîáðàçíî ïðèìåíÿòü â áóëåâîé îïòèìèçàöèè, ïîñêîëüêó lim min ( ) * �i F x x Bn �� arg 1 . Íà ïðèìåðå áóëåâîãî ìíîæåñòâà ïîêàçàíû ïðåèìóùåñòâà ïîñòðîåíèÿ ñòðî- ãèõ ïðåäñòàâëåíèé (3), (7) åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ. Îñîáûé èíòå- ðåñ îíè ïðåäñòàâëÿþò äëÿ ìíîæåñòâ, ïîëèýäðàëüíî-ñôåðè÷åñêèå ïðåäñòàâëåíèÿ êîòîðûõ íåèçâåñòíû ëèáî ñîäåðæàò ÷èñëî îãðàíè÷åíèé, çíà÷èòåëüíî ïðåâîñõîäÿùåå ðàçìåðíîñòü ïðîñòðàíñòâà. Òàê, èçâåñòíî [4, 7, 11], ÷òî íåïðèâîäèìàÿ ñèñòåìà îáùåãî ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà ñîäåðæèò îò n�1äî 2 1n � îãðàíè÷åíèé, ñîîòâåòñòâåííî åãî ïîëèýä- ðàëüíî-ñôåðè÷åñêîå ïðåäñòàâëåíèå âêëþ÷àåò äî 2n îãðàíè÷åíèé. Íî ñîãëàñíî [35] ìíîæåñòâî E Gnk ( ) ïîçâîëÿåò òàêæå ñòðîãèå ôóíêöèîíàëüíûå ïðåäñòàâëåíèÿ âèäà f x x g j Ji i j i n i j i n n( ) ,� � � � � � � � 1 1 0 ; (30) f x x g j Ji i iJ j i iJ j n n n ( ) , , \| \| , \| \| � � � � �� %� %� �� 0 , (31) êîòîðûå ìîãóò áûòü èñïîëüçîâàíû äëÿ ðàçëè÷íûõ íåïðåðûâíûõ ðåëàêñàöèé èñõîäíîé çàäà÷è, à òàêæå àêêóìóëèðîâàíû â îäíîêîìïîíåíòíîå ïðåäñòàâëåíèå âèäà (29) è ïðèìåíåíû ïîäîáíî (18) â ÷èñëåííûõ ñõåìàõ ðåøåíèÿ (1), (2), íà- ïðèìåð â øòðàôíûõ ìåòîäàõ. Îáîáùèì ïðåäñòàâëåíèÿ (30), (31) ñ îáùåãî ìíîæåñòâà ïåðåñòàíîâîê íà ïî- ëèïåðåñòàíîâî÷íîå ìíîæåñòâî [5] E Gnk ( ) èç ìóëüòèìíîæåñòâà, ðàçáèòîãî íà êîðòåæ èç L ìóëüòèìíîæåñòâ G G l l JL � �{ } , ãäå G gl i l i J nl � �{ } ñîäåðæèò k l ðàç- ëè÷íûõ ýëåìåíòîâ (l J n n k kL l l J l l JL L � � �, ( ) , ( )= = ) (ìíîæåñòâî êîðòåæåé ïåðå- ñòàíîâîê [10]). Ýòî ìíîæåñòâî ïðåäñòàâèìî äåêàðòîâûì ïðîèçâåäåíèåì íå- ñêîëüêèõ ïåðåñòàíîâî÷íûõ ìíîæåñòâ, êàæäîå èç êîòîðûõ èìååò ñòðîãèå ïðåä- ñòàâëåíèÿ âèäà (30), (31), â ðåçóëüòàòå èìåþò ìåñòî ñëåäóþùèå ñòðîãèå ïðåäñòàâëåíèÿ E Gnk ( ) : x g l J j J il j i n i l j i n L n l l � � � �� 1 1 ( ) , , ; x g l J j Jij iJ j i j iJ j L n nl nl �� %� %�� , \| \| , \| \| , , . 108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 3. ÏÐÎÄÎËÆÅÍÈß ÔÓÍÊÖÈÉ Ñ ÌÍÎÆÅÑÒÂ ÍÀ ÍÀÄÌÍÎÆÅÑÒÂÀ 3.1. Îñíîâíûå ïîíÿòèÿ. Ïðîäîëæåíèåì ôóíêöèè f x( ) c ìíîæåñòâà E íà E E� & ÿâëÿåòñÿ ôóíêöèÿ F x( ) , îïðåäåëåííàÿ íà E� è ñîâïàäàþùàÿ ñ f x( ) íà E : F x f x E ( ) ( )� . (32) Ïðîäîëæåíèå (32) ôóíêöèè f x( ) íàçûâàåòñÿ: à) ñòðîãèì ïðîäîëæåíèåì ñ ìíîæåñòâà E, åñëè âûïîëíåíî óñëîâèå F x f x x E( ) ( )� ! � , (33) â ïðîòèâíîì ñëó÷àå — íåñòðîãèì; á) ìàæîðèðóþùèì ïðîäîëæåíèåì ñ ìíîæåñòâà E íà E�, åñëè F x f x( ) ( )� �x E . Çàìå÷àíèå 3. Ïîäîáíî êëàññèôèêàöèè ïðåäñòàâëåíèé ìíîæåñòâ ïðîäîëæå- íèÿ ôóíêöèé â çàâèñèìîñòè îò åå òèïà ìîãóò áûòü íåïðåðûâíûìè, äèôôåðåíöè- ðóåìûìè, ãëàäêèìè, âûïóêëûìè íà êîìïàêòå E E� ' , ñòðîãî è ñèëüíîâûïóêëû- ìè íà E� è ò.ï. Åñëè îáëàñòü ïðîäîëæåíèÿ ôóíêöèè íå óêàçàíà, ïðåäïîëàãàåòñÿ, ÷òî îíà ñîâïàäàåò ñ R n . 3.2. Ïðèìåíåíèå ïðîäîëæåíèé ôóíêöèé â êîìáèíàòîðíîé îïòèìèçàöèè. Ïóñòü E — åâêëèäîâî êîìáèíàòîðíîå ìíîæåñòâî (2), (10). Ïî îïðåäåëåíèþ ïðî- äîëæåíèé (32) çàäà÷à îïòèìèçàöèè ïðîäîëæåíèÿ, F x( ) min� , (34) â îáëàñòè (2) è èñõîäíàÿ çàäà÷à (1), (2) ýêâèâàëåíòíû. Ïðîäåìîíñòðèðóåì, êàêèå ïðåèìóùåñòâà â ðåøåíèè çàäà÷ îïòèìèçàöèè äàåò êîíñòðóèðîâàíèå ïðîäîëæåíèé öåëåâûõ ôóíêöèé ñî ñïåöèàëüíûìè ñâîéñòâàìè. Òàê, âîãíóòûå ïðîäîëæåíèÿ ïîçâîëÿþò ñâåñòè äèñêðåòíóþ çàäà÷ó (1), (2) ê íåïðå- ðûâíîé: F x P ( ) min� , ãäå F x( ) — âîãíóòàÿ (ñì., íàïðèìåð, (15), (16) äëÿ Bn ). Âûïóêëûå ïðîäîëæåíèÿ ñ ìíîæåñòâà E íà êîìïàêò E E� ' ïîçâîëÿþò îöå- íèòü z f x E � min ( ) ñ ïîìîùüþ ðåøåíèé âûïóêëûõ ðåëàêñàöèîííûõ çàäà÷: z f x F x E P � � �min ( ) min ( ) min ( ) min ( ) E R F x F x n� � , ãäå F x( ) — âûïóêëîå ïðîäîë- æåíèå f x( ) c E íà E�. Îäíàêî ñóùåñòâóþò êëàññû âûïóêëûõ ôóíêöèé, äëÿ êîòîðûõ èçâåñòíû ýêñòðåìóìû íà íåêîòîðûõ âûïóêëûõ ïîâåðõíîñòÿõ. Ïðèìåðîì ñëóæàò âû- ïóêëûå êâàäðàòè÷íûå ôóíêöèè íà ýëëèïñîèäå [36] è, â ÷àñòíîñòè, íà ñôåðå. Ýòî ïî- çâîëÿåò óñïåøíî ïðèìåíÿòü ïîëèýäðàëüíî-ñôåðè÷åñêèé ìåòîä [24] ê ðåøåíèþ êâàä- ðàòè÷íûõ çàäà÷ íà ìíîæåñòâàõ òèïà (10), (22) ïîñëå ïåðåõîäà ê çàäà÷å (34) îïòèìèçà- öèè êâàäðàòè÷íîãî âûïóêëîãî ïðîäîëæåíèÿ, ïîñêîëüêó îáå ðåëàêñàöèîííûå çàäà÷è òèïà (24), F x P ( ) min� è F x S ar ( ) min ( ) � , ðåøàþòñÿ â äàííîì ñëó÷àå ýôôåêòèâíî. Íàêîíåö, ñòðîãèå ìàæîðèðóþùèå ïðîäîëæåíèÿ (ñì. (33)) ïîçâîëÿþò ñâåñòè èñõîäíóþ çàäà÷ó ê ñåðèè íåïðåðûâíûõ. Ïðîäåìîíñòðèðóåì ýòî íà ïðèìåðå áóëå- âîãî ìíîæåñòâà. Â ðàçä. 2.2 áûëî ïîêàçàíî ïðèìåíåíèå ñòðîãîãî ïðåäñòàâëåíèÿ (12) ìíîæåñòâà Bn â îïòèìèçàöèè. Íåòðóäíî âèäåòü, ÷òî âñå ïðèâåäåííûå öåëå- âûå ôóíêöèè (14), (15), (18), ïîñòðîåííûå íà åãî îñíîâå, ÿâëÿþòñÿ ïðîäîëæåíèÿ- ìè èñõîäíîé èëè ñãëàæåííîé ôóíêöèé ñ ìíîæåñòâà Bn â R n . Ïðè ýòîì (15) — íåñòðîãîå ïðîäîëæåíèå, ïîñêîëüêó ÿâëÿåòñÿ îäíîâðåìåííî ïðîäîëæåíèåì ñî âñåé îïèñàííîé ñôåðû (20) â R n , â òî âðåìÿ êàê (18) — ñòðîãîå ïðîäîëæåíèå ñ Bn . Îñòàíîâèìñÿ áîëåå äåòàëüíî íà ïðîäîëæåíèè (18). Â òåðìèíàõ îäíîêîìïî- íåíòíîãî ïðåäñòàâëåíèÿ (28) îíî èìååò âèä �2 1( , ) ~ ( ) ( )x f x F x� �� . Ñ ó÷åòîì ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 109 F x1 0( ) � èìååì �2 ( , ) ~ ( )x f x� � ïðè � � 0 , ò.å. �2 ( , )x � — ìàæîðèðóþùåå ñòðî- ãîå ïðîäîëæåíèå ~ ( )f x , êîòîðîå îáåñïå÷èâàåò íå òîëüêî ïîëó÷åíèå òî÷êè ìíî- æåñòâà Bn â ïðåäåëå èòåðàöèîííîãî ïðîöåññà (18), (19), íî è ýêâèâàëåíòíîñòü êîìáèíàòîðíîé çàäà÷è (1), (2) è íåïðåðûâíîé çàäà÷è �2 ( , ) minx � �� . Çàìå÷àíèå 4. Äëÿ ïðîèçâîëüíîãî ìíîæåñòâà E ïðîáëåìó íåïðåðûâíîé ôîð- ìóëèðîâêè çàäà÷è (1), (2) â èñõîäíîì ïðîñòðàíñòâå R n ìîæíî ïîñòàâèòü ñëåäóþ- ùèì îáðàçîì: ïîñòðîèòü ñòðîãîå ìàæîðèðóþùåå ïðîäîëæåíèå F x( ) c E: arg ( )min E F x E� . Òåïåðü çàäà÷à (1), (2) ýêâèâàëåíòíà íåïðåðûâíîé: F x( ) min� . Íàïðèìåð, ïîñëåäîâàòåëüíîñòü ðåøåíèé çàäà÷è (18), (19) äàåò â ïðåäåëå òî÷êó ìíîæåñòâa Bn , ò.å. äëÿ áóëåâûõ çàäà÷ èñêîìûì ñòðîãèì ìàæîðèðóþùèì ïðî- äîëæåíèåì áóäåò F x x k k( ) lim ( , )� �� 2 � . 3.3. Ïîñòðîåíèå ïðîäîëæåíèé ôóíêöèé ñ ïîëèýäðàëüíî-ñôåðè÷åñêèõ êîìáè- íàòîðíûõ ìíîæåñòâ. Ïîëèýäðàëüíî-ñôåðè÷åñêèå ìíîæåñòâà çàíèìàþò âàæíîå ìåñòî ñðåäè åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ. Ê íèì îòíîñÿòñÿ îáùåå ïåðå- ñòàíîâî÷íîå ìíîæåñòâî [4, 5, 7, 34], îòäåëüíûå êëàññû ñî÷åòàíèé è ðàçìåùå- íèé [5, 12, 21], â òîì ÷èñëå áóëåâî ìíîæåñòâî, à òàêæå èõ êîìïîçèöèîííûå îáðà- çû [10]. Ïîêàæåì, ÷òî âûøåïåðå÷èñëåííûå íåïðåðûâíûå ïîäõîäû ïðèìåíèìû ê îïòèìèçàöèè íà òàêèõ ìíîæåñòâàõ ïîñëå ïîñòðîåíèÿ èõ ñòðîãèõ ïðåäñòàâëåíèé. Èòàê, ðàññìîòðèì çàäà÷ó (1), (2) íà ìíîæåñòâå E âèäà (10), (22), äëÿ êîòîðî- ãî èçâåñòíî ñòðîãîå ïðåäñòàâëåíèå (3), (7). Ïðîäåìîíñòðèðóåì, êàê äëÿ ïðîèç- âîëüíîé öåëåâîé ôóíêöèè çàäà÷è (1) ïîñòðîèòü âîãíóòûå, âûïóêëûå è ñòðîãèå ìàæîðèðóþùèå ïðîäîëæåíèÿ. 1. Ìíîæåñòâî E âåðøèííî ðàñïîëîæåíî, à äëÿ òàêèõ ìíîæåñòâ â [13] îáîñ- íîâàíî ñóùåñòâîâàíèå âûïóêëûõ è âîãíóòûõ äèôôåðåíöèðóåìûõ ïðîäîëæåíèé è ïðèâåäåíà òåõíèêà èõ ïîñòðîåíèÿ. Áîëåå òîãî, åñëè f x C R n( ) ( )� 2 , (35) òî ñóùåñòâóþò ñòðîãî âîãíóòûå è âîãíóòûå ïðîäîëæåíèÿ ñ ìíîæåñòâà (22) âèäà F x f x x a r( ) ( ) (( ) )� � � �� 2 2 , ïðè÷åì âûïóêëîñòü îáåñïå÷èâàåòñÿ âûáîðîì äî- ñòàòî÷íî áîëüøîãî � � 0, âîãíóòîñòü — äîñòàòî÷íî ìàëîãî �� 0 [28, 30]. Òåïåðü äëÿ èñïîëüçîâàíèÿ âîãíóòûõ ìåòîäîâ ê çàäà÷å (1), (2) îñòàåòñÿ ðåøèòü çàäà÷ó àíàëèòè÷åñêîãî îïèñàíèÿ P. 2. Ñòðîãîå ìàæîðèðóþùåå ïðîäîëæåíèå F x� ( ) ñòðîèì ñ ïîìîùüþ íåïðå- ðûâíî äèôôåðåíöèðóåìîãî ñòðîãîãî ïðåäñòàâëåíèÿ E , îáúåäèíÿÿ (3) â îäíîêîì- ïîíåíòíîå ïðåäñòàâëåíèå � �( ) ( )x f xj j l j m � � � 2 1 ïðè � j� 0 ( , )l N j Jm� � è äîïîë- íÿÿ åãî ôóíêöèåé f x( ) : F x f x x� � �( ) ( ) ( )� . (36) Ôóíêöèè F x F x( ), ( )� ìîãóò êîìáèíèðîâàòüñÿ. Íàïðèìåð, ñóììèðóÿ �( )x ñ F x( ) , ïîëó÷àåì ïðîäîëæåíèå �� F x f x x a r f xj j l j m ( ) ( ) ) ( )�� 2 2 2 1 , äëÿ êîòîðîãî �( : � �� j mj J(, , ôóíêöèÿ ��F x( ) — âûïóêëàÿ. Ïðè ýòîì arg min ( ) *�� F x x E � . Âûïóêëûå ìåòîäû â ïðèìåíåíèè ê �� F x( ) min îïðåäåëÿþò â õóäøåì ñëó÷àå ëîêàëüíûé ìèíèìóì f x( ) íà E. 110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 4. ÎÁÑÓÆÄÅÍÈÅ ÐÅÇÓËÜÒÀÒÎÂ È ÍÀÏÐÀÂËÅÍÈÅ ÄÀËÜÍÅÉØÅÃÎ ÈÑÑËÅÄÎÂÀÍÈß Ðåøåíèå çàäà÷è ïîèñêà ñòðîãîãî ïðåäñòàâëåíèÿ êîìáèíàòîðíîãî ìíîæåñòâà îçíà÷àåò âîçìîæíîñòü ïðèìåíåíèÿ íåïðåðûâíûõ ìåòîäîâ ê îïòèìèçàöèè (ñì. çàìå÷àíèå 4) ñòðîãîãî ìàæîðèðóþùåãî ïðîäîëæåíèÿ (36). Îäíàêî ñóùåñòâóåò êëàññ ìíîæåñòâ, ê êîòîðûì ïðèìåíèìû âñå ïðèâåäåííûå â ðàçä. 3.3 ðåçóëüòàòû. Ýòî âåðøèííî ðàñïîëîæåííûå ìíîæåñòâà, ïîñêîëüêó, êàê áûëî óêàçàíî, âûïóêëûå äèôôåðåíöèðóåìûå ïðîäîëæåíèÿ ñ ýòèõ ìíîæåñòâ ñó- ùåñòâóþò [13]. Åñëè ê òîìó æå âûïîëíåíî (35), òî, ðåøèâ çàäà÷ó ïîèñêà îïèñàí- íîé âîêðóã E ãëàäêîé âûïóêëîé ïîâåðõíîñòè S x f x� �{ }: ( )1 0 (îòëè÷íîé îò ãèïåð- ïëîñêîñòè), áóäåò íàéäåíà ñòðîãî âûïóêëàÿ ôóíêöèÿ f x1 ( ) , ñ ïîìîùüþ êîòîðîé ìîãóò ñòðîèòüñÿ êàê âûïóêëûå, òàê è âîãíóòûå ïðîäîëæåíèÿ âèäà F x f x f x( ) ( ) ( )� � � 1 âûáîðîì ñîîòâåòñòâóþùåãî � . Èòàê, àêòóàëüíûìè ÿâëÿþòñÿ çàäà÷è: à) îáîñíîâàíèå ñóùåñòâîâàíèÿ äâàæäû íåïðåðûâíî äèôôåðåíöèðóåìîãî ïðîäîëæåíèÿ ïðîèçâîëüíîé ôóíêöèè ñ âåðøèí- íî ðàñïîëîæåííîãî ìíîæåñòâà; á) ïîñòðîåíèå êàê ñòðîãèõ, òàê è íåñòðîãèõ ïðåä- ñòàâëåíèé äðóãèõ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ. ÇÀÊËÞ×ÅÍÈÅ Â íàñòîÿùåé ñòàòüå èçâåñòíûå íåïðåðûâíûå ïîäõîäû ê ðåøåíèþ áåçóñëîâíûõ êîìáèíàòîðíûõ çàäà÷ â ïðîñòðàíñòâå èñõîäíîé ðàçìåðíîñòè îáîáùåíû è ñôîðìóëèðîâàíû â òåðìèíàõ ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé äîïóñòèìûõ ìíîæåñòâ è ïðîäîëæåíèé öåëåâûõ ôóíêöèé ñ ýòèõ ìíîæåñòâ. Äëÿ èõ ïðèìåíå- íèÿ íåîáõîäèìî ðåøèòü çàäà÷è ïîñòðîåíèÿ ñòðîãèõ ôóíêöèîíàëüíûõ ïðåä- ñòàâëåíèé åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ è ñèñòåì îãðàíè÷åíèé ñîîò- âåòñòâóþùèõ êîìáèíàòîðíûõ ìíîãîãðàííèêîâ. Â ñòàòüå ïðèâåäåí ðÿä òàêèõ ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé áóëåâîãî ìíîæåñòâà, à òàêæå îáùèõ ïåðåñòà- íîâî÷íîãî è ïîëèïåðåñòàíîâî÷íîãî ìíîæåñòâ. Äàëüíåéøåå èññëåäîâàíèå ýòèõ ïðåäñòàâëåíèé ìíîæåñòâ è ñèñòåì ìíîãî- ãðàííèêîâ, â ÷àñòíîñòè ôîðìèðîâàíèå íåèçáûòî÷íûõ ôóíêöèîíàëüíûõ ïðåäñòàâëå- íèé ìíîæåñòâ è íåñâîäèìûõ ñèñòåì îãðàíè÷åíèé ìíîãîãðàííèêîâ, öåëåñîîáðàçíî êàê ñ òåîðåòè÷åñêîé, òàê è ñ ïðàêòè÷åñêîé òî÷åê çðåíèÿ, ïîñêîëüêó ïîçâîëÿåò óâåëè- ÷èòü ýôôåêòèâíîñòü êîìáèíàòîðíûõ àëãîðèòìîâ, ïîñòðîåííûõ íà èõ îñíîâå. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ñ ò î ÿ í Þ . Ã . Íåêîòîðûå ñâîéñòâà ñïåöèàëüíûõ êîìáèíàòîðíûõ ìíîæåñòâ. — Õàðüêîâ, 1980. — 22 ñ. — (Ïðåïð. / ÀÍ ÓÑÑÐ. Èí-ò ïðîáëåì ìàøèíîñòðîåíèÿ; 85). 2. Ã ó ë ÿ í è ö ê è é Ë . Ô . , Ñ å ð ã è å í ê î È . Â . Ìåòàýâðèñòè÷åñêèé ìåòîä äåôîðìèðîâàííîãî ìíîãîãðàííèêà â êîìáèíàòîðíîé îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 6. — Ñ. 70–79. 3. Ñ å ð ã è å í ê î È . Â . , Ã ó ë ÿ í è ö ê è é Ë . Ô . , Ñ è ð å í ê î Ñ . È . Êëàññèôèêàöèÿ ïðèêëàäíûõ ìåòîäîâ êîìáèíàòîðíîé îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 5. — Ñ. 71–83. 4. Ñ ò î ÿ í Þ . Ã . , ß ê î â ë å â Ñ . Â . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåî- ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Ê.: Íàóê. äóìêà, 1986. — 268 ñ. 5. Ñ ò î ÿ í Þ . Ã . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Ê. : ²í-ò ñèñòåìíèõ äîñë³äæåíü îñâ³òè, 1993. — 188 ñ. 6. ß ê î â ë å â Ñ . Â . , Ã è ë ü Í . È . , Ê î ì ÿ ê Â . Ì . , À ð è ñ ò î â à È . Â . Ýëåìåíòû òåîðèè ãåîìåò- ðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Ê.: Íàóê. äóìêà, 1995. — 241 ñ. 7. Å ì å ë è ÷ å â Â . À . , Ê î â à ë å â Ì . Ì . , Ê ð à â ö î â Ì . Ê . Ìíîãîãðàííèêè, ãðàôû, îïòèìèçà- öèÿ (êîìáèíàòîðíàÿ òåîðèÿ ìíîãîãðàííèêîâ). — Ì.: Íàóêà. Ãëàâíàÿ ðåäàêöèÿ ôèçèêî-ìàòåìà- òè÷åñêîé ëèòåðàòóðû, 1981. — 344 ñ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 111 8. B a l i n s k i M . L . , H o f f m a n A . J . Polyhedral combinatorics: Dedicated to the memory of D.R. Fulkerson. — New York: Elsevier Science Ltd, 1978. — 242 p. 9. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. Àëãîðèòìû è ñëîæ- íîñòü. — Ì. : Ìèð, 1984. — 512 ñ. 10. Ã ð å á å í í è ê È . Â . , Ë è ò â è í å í ê î À . Ñ . Ãåíåðàöèÿ êîìáèíàòîðíûõ ìíîæåñòâ ñ çàäàííûìè ñâîéñòâàìè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 6. — Ñ. 96–105. 11. ª ì å ö ü Î . Î . , Í å ä î á à ÷ ³ é Ñ . ² . Çàãàëüíèé ïåðåñòàâíèé ìíîãîãðàííèê: íåçâ³äíà ñèñòåìà ë³í³éíèõ îáìåæåíü òà ð³âíÿííÿ âñ³õ ã³ïåðãðàíåé // Íàóêîâ³ â³ñò³ ÍÒÓÓ «ÊÏ²». — 1998. — ¹ 1. — Ñ. 100–106. 12. Ï è ÷ ó ã è í à Î . Ñ . Ìåòîäû è àëãîðèòìû ðåøåíèÿ íåêîòîðûõ çàäà÷ îïòèìèçàöèè íà ìíîæå- ñòâàõ ñî÷åòàíèé è ðàçìåùåíèé: Äèñ. ... êàíä. ôèç.-ìàò. íàóê. — Õàðüêîâ, 1996. — 169 ñ. 13. ß ê î â ë å â Ñ . Â . Òåîðèÿ âûïóêëûõ ïðîäîëæåíèé ôóíêöèé íà âåðøèíàõ âûïóêëûõ ìíîãîãðàí- íèêîâ // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 1994. — 34, ¹ 7 — Ñ. 1112–1119. 14. Ñ ò î ÿ í Þ . Ã . , ß ê î â ë å â Ñ . Â . Ïîñòðîåíèå âûïóêëûõ è âîãíóòûõ ôóíêöèé íà ïåðåñòàíî- âî÷íîì ìíîãîãðàííèêå // ÄÀÍ ÓÑÑÐ. Ñåð. À. — 1988. — ¹ 5. — Ñ. 66–68. 15. Ã ð è ö è ê Â . Â . , Ê ³ ñ å ë ü î â à Î . Ì . , ß ê î â ë å â Ñ . Â . , Ñ ò å ö þ ê Ï . ² . òà ³í. Ìàòåìàòè÷í³ ìåòîäè îïòèì³çàö³¿ òà ³íòåëåêòóàëüí³ êîìï'þòåðí³ òåõíîëîã³¿ ìîäåëþâàííÿ ñêëàäíèõ ïðîöåñ³â ³ ñèñòåì ç óðàõóâàííÿì ïðîñòîðîâèõ ôîðì îá'ºêò³â // ²í-ò ïðîáëåì øòó÷íîãî ³íòåëåêòó ÍÀÍ Óêðà¿íè. — Äîíåöüê: Íàóêà ³ îñâ³òà, 2012. — 480 ñ. 16. Ñ ò î ÿ í Þ . Ã . , ß ê î â ë å â Ñ . Â . , Å ì å ö Î . À . , Â à ë ó é ñ ê à ÿ Î . À . Ïîñòðîåíèå âûïóêëûõ ïðîäîëæåíèé äëÿ ôóíêöèé, çàäàííûõ íà ãèïåðñôåðå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1998. — ¹ 2. — Ñ. 27–37. 17. Â à ë ó é ñ ê à ÿ Î . À . , Ï è ÷ ó ã è í à Î . Ñ . , ß ê î â ë å â Ñ . Â . Âûïóêëûå ïðîäîëæåíèÿ ïîëèíî- ìîâ íà êîìáèíàòîðíûõ ìíîæåñòâàõ è èõ ïðèëîæåíèÿ // Ðàäèîýëåêòðîíèêà è èíôîðìàòèêà. — 2001. — ¹ 2. — Ñ. 121–129. 18. Â à ë ó é ñ ê à ÿ Î . À . , Å ì å ö Î . À . , Ð î ì à í î â à Í . Ã . Âûïóêëîå ïðîäîëæåíèå ìíîãî÷ëåíîâ, çàäàííûõ íà ïîëèïåðåñòàíîâêàõ, ìîäèôèöèðîâàííûì ìåòîäîì Ñòîÿíà–ßêîâëåâà // Æóðí. âû- ÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 2002. — 42, ¹ 4. — C. 591–596. 19. Ï ³ ÷ ó ã ³ í à Î . Ñ . Îïóêëå ïðîäîâæåííÿ êóá³÷íèõ ìíîãî÷ëåí³â íà ïåðåñòàâëåííÿõ òà éîãî çà- ñòîñóâàííÿ ó ðîçâ'ÿçàíí³ ïðàêòè÷íèõ çàäà÷ îïòèì³çàö³¿ // Ìàòåìàòè÷íå òà êîìï'þòåðíå ìîäå- ëþâàííÿ. Ñåð.: Ô³çèêî-ìàòåìàòè÷í³ íàóêè. — Êàì'ÿíåöü-Ïîä³ëüñüêèé: Êàì'ÿíåöü-Ïîä³ëüñüêèé íàö³îíàëüíèé óí³âåðñèòåò ³ìåí³ ²âàíà Îã³ºíêà, 2010. — 4. — Ñ. 176–189. 20. Ñ ò î ÿ í Þ . Ã . , ß ê î â ë å â Ñ . Â . , Ï à ð ø è í Î . Â . Êâàäðàòè÷íàÿ îïòèìèçàöèÿ íà êîìáèíà- òîðíûõ ìíîæåñòâàõ â Rn // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1991. — ¹ 4. — Ñ. 97—104. 21. ß ê î â ë å â Ñ . Â . , Ã ð å á å í í è ê È . Â . Î íåêîòîðûõ êëàññàõ çàäà÷ îïòèìèçàöèè íà ìíîæåñòâå ðàçìåùåíèé è èõ ñâîéñòâàõ // Èçâ. âóçîâ. Ìàòåìàòèêà. — 1991. — ¹ 11. — Ñ. 74–86. 22. ß ê î â ë å â Ñ . Â . , Ã ð å á å í í è ê È . Â . Ëîêàëèçàöèÿ ðåøåíèÿ íåêîòîðûõ çàäà÷ íåëèíåéíîé öå- ëî÷èñëåííîé îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1993. — ¹ 5. — Ñ. 116–124. 23. ª ì å ö ü Î . Î . , Â à ë ó é ñ ü ê à Î . Î . , Ï ³ ÷ ó ã ³ í à Î . Ñ . Äî ïèòàííÿ ïðî íåë³í³éíó òà ïàðàìåò- ðè÷íó îïòèì³çàö³þ íà êîìá³íàòîðíèõ ìíîæèíàõ // Â³ñíèê Ëüâ³âñüêîãî óí³âåðñèòåòó. Ñåê. ïðè- êëàäíà ìàòåìàòèêà ³ ³íôîðìàòèêà. — 2002. — ¹ 4. — C. 94–101. 24. Ï è ÷ ó ã è í à Î . Ñ . , ß ê î â ë å â Ñ . Â . Ïîëèýäðàëüíî-ñôåðè÷åñêèé ïîäõîä ê ðåøåíèþ íåêîòî- ðûõ êëàññîâ êîìáèíàòîðíûõ çàäà÷ // Ïðàö³ V² Ì³æíàðîäíî¿ øêîëè-ñåì³íàðó «Òåîð³ÿ ïðèéíÿò- òÿ ð³øåíü». — Óæãîðîä, 2012. — Ñ. 152–153. 25. Ñ ò î ÿ í Þ . Ã . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Îïòèì³çàö³ÿ íà ïîë³ðîçì³ùåííÿõ: òåîð³ÿ òà ìå- òîäè. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ. 26. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê ³ í à Ë . Ì . Çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³ÿ ç äðîáîâî-ë³í³éíèìè ôóíêö³ÿìè. — Ê.: Íàóê. äóìêà, 2005. — 117 ñ. 27. Ñ å ì å í î â à Í . Â . , Ê î ë º ÷ ê ³ í à Ë . Ì . Âåêòîðí³ çàäà÷³ äèñêðåòíî¿ îïòèì³çàö³¿ íà êîìá³íà- òîðíèõ ìíîæèíàõ: ìåòîäè ¿õ äîñë³äæåííÿ òà ðîçâ'ÿçàííÿ. — Ê.: Íàóê. äóìêà, 2009. — 266 ñ. 28. B e r t s e k a s D . P . Nonlinear programming. — Belmont: Athena Scientific, 1995. — 378 p. 29. K o c h e n b e r g e r G . , H a o J . - K . , G l o v e r F . , L e w i s M . , L u Z . , W a n g H . , W a n g Y . The unconstrained binary quadratic programming problem: A survey // Journal of Combinatorial Optimization. — 2014. — 1. — P. 58–81. 112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 30. H i l l i e r F . S . , A p p a G . , P i t s o u l i s L . , W i l l i a m s H . P . , P a r d a l o s P . M . , P r o k o - p y e v O . A . , B u s y g i n S . Continuous approaches for solving discrete optimization problems // Handbook on Modelling for Discrete Optimization, 2006. — P. 1–39. 31. H e l m b e r g C . , R e n d l F . Solving quadratic (0,1)-problems by semidefinite programs and cutting planes // Mathematical Programming. — 1998. — 82, N 3. — P. 291–315. 32. M u r r a y W . , N g K . - M . An algorithm for nonlinear optimization problems with binary variables. Computational Optimization and Applications. — 2008. — 47, N 2. — P. 257–288. 33. Ñ ò å ö þ ê Ï . È . Î ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèÿõ äëÿ áóëåâûõ îïòèìèçàöèîííûõ çàäà÷ êâàäðàòè÷íîãî òèïà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 6. — C. 168–172. 34. P o s t n i k o v A . Permutohedra, associahedra, and beyond // IMRN: International Mathematics Research Notices. — 2009. — 2009, Issue 6. — P. 1026–1106. 35. Ï è ÷ ó ã è í à Î . Ñ . , ß ê î â ë å â Ñ . Â . Ôóíêöèîíàëüíî-àíàëèòè÷åñêèå ïðåäñòàâëåíèÿ îáùåãî ïåðåñòàíîâî÷íîãî ìíîæåñòâà // Âîñòî÷íî-Åâðîïåéñêèé æóðíàë ïåðåäîâûõ òåõíîëîãèé. — 2016. — 4, ¹ 1 — Ñ. 27–38. 36. D a h l J . Convex problems in signal processing and communications // Ph.D. Thesis, Aalbort University, 2003. — 100 p. Íàä³éøëà äî ðåäàêö³¿ 08.02.2016 Î.Ñ. Ï³÷óã³íà, Ñ.Â. ßêîâëåâ ÏÐÎ ÍÅÏÅÐÅÐÂÍ² ÏÐÅÄÑÒÀÂËÅÍÍß ÒÀ ÔÓÍÊÖ²ÎÍÀËÜÍ² ÏÐÎÄÎÂÆÅÍÍß Â ÇÀÄÀ×ÀÕ ÊÎÌÁ²ÍÀÒÎÐÍÎ¯ ÎÏÒÈÌ²ÇÀÖ²¯ Àíîòàö³ÿ. Ââåäåíî ïîíÿòòÿ ôóíêö³îíàëüíîãî ïðåäñòàâëåííÿ ìíîæèíè òî÷îê åâêë³äîâîãî àðèôìåòè÷íîãî ïðîñòîðó ³ ïðîäîâæåííÿ ôóíêö³é ç äàíî¿ ìíî- æèíè ó ¿¿ íàäìíîæèíó. Ïîêàçàíî çâ'ÿçîê ôóíêö³îíàëüíèõ ïðåäñòàâëåíü ìíîæèí ³ ïðîäîâæåíü ç íèõ. Îòðèìàíî ñòðîã³ ôóíêö³îíàëüí³ ïðåäñòàâëåííÿ áóëåâî¿, çàãàëüíî¿ ïåðåñòàíîâî÷íî¿ òà ïîë³ïåðåñòàíîâî÷íî¿ ìíîæèí. Ïðîäåìî- íñòðîâàíî ïåðåâàãè çàñòîñóâàííÿ ñòðîãèõ ïðåäñòàâëåíü åâêë³äîâèõ êîìá³íà- òîðíèõ ìíîæèí ó ïîáóäîâ³ ôóíêö³îíàëüíèõ ïðîäîâæåíü ç öèõ ìíîæèí ³ ðîçâ'ÿ- çàíí³ êîìá³íàòîðíèõ çàäà÷. Êëþ÷îâ³ ñëîâà: êîìá³íàòîðíà îïòèì³çàö³ÿ, åâêë³äîâà êîìá³íàòîðíà ìíîæè- íà, íåïåðåðâíå ôóíêö³îíàëüíå ïðåäñòàâëåííÿ ìíîæèíè, ïðîäîâæåííÿ ôóíêö³é, çàãàëüíà ìíîæèíà ïåðåñòàíîâîê, áóëåâà ìíîæèíà. O.S. Pichugina, S.V. Yakovlev CONTINUOUS REPRESENTATIONS AND FUNCTIONAL EXTENSIONS IN COMBINATORIAL OPTIMIZATION Abstract. The concepts of functional representation of a set of points of the Euclidean arithmetic space and an extension of functions from the set onto its superset are introduced. Functional representations of sets are related to their extensions. Strict functional representations of the Boolean set, general permutation, and polypermutation sets are derived. The advantages of applying strict representations of Euclidean combinatorial sets to construct functional extensions from them and to solve combinatorial problems are presented. Keywords: combinatorial optimization, euclidean combinatorial set, continuous functional sets' prime representation, an extension of functions, the general permutation set, the boolean set. Ïè÷óãèíà Îëüãà Ñåðãååâíà, êàíäèäàò ôèç.-ìàò. íàóê, äîêòîðàíò Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà ðàäèîýëåêòðîíèêè, e-mail: pichugina@mail.ru. ßêîâëåâ Ñåðãåé Âñåâîëîäîâè÷, äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð Íàöèîíàëüíîãî àýðîêîñìè÷åñêîãî óíèâåðñèòåòà èì. Í.Å. Æóêîâñêîãî «ÕÀÈ», e-mail: svsyak@mail.ru. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 6 113

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

Institution

Ähnliche Einträge