Специальные транспозиции элементов перестановок и свойства композиции

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2017
Hauptverfasser:	Гребенник, И.В., Черная, О.С.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системний аналіз
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/144686
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:	Специальные транспозиции элементов перестановок и свойства композиции / И.В. Гребенник, О.С. Черная // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 79-90. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-144686
record_format	dspace
spelling	irk-123456789-1446862019-01-02T01:23:07Z Специальные транспозиции элементов перестановок и свойства композиции Гребенник, И.В. Черная, О.С. Системний аналіз Предложена стратегия решения задачи оптимизации линейной функции на множестве циклических перестановок на основе свойств транспозиций специального вида. Исследованы свойства специального класса транспозиций, доказаны утверждения о влиянии композиций таких транспозиций на произвольную перестановку. Для приближенного решения, полученного с помощью описанной стратегии, обоснована оценка. Запропоновано стратегію розв’язання задачі оптимізації лінійної функції на множині циклічних перестановок на основі властивостей транспозицій спеціального виду. Досліджено властивості спеціального класу транспозицій, доведено твердження про вплив композицій таких транспозицій на довільну перестановку. Для наближеного розв’язку, отриманого за допомогою описаної стратегії, обгрунтовано оцінку. In this paper, we propose a strategy for solving the problem of optimization of a linear function on the set of cyclic permutations. The strategy is based on the properties of the transpositions of a special kind. The properties of this class of transpositions are investigated. Assertions about the impact of compositions of such transpositions on an arbitrary permutation are proved. For the approximate solutions obtained using the above strategy, estimation is substantiated. 2017 Article Специальные транспозиции элементов перестановок и свойства композиции / И.В. Гребенник, О.С. Черная // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 79-90. — Бібліогр.: 15 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/144686 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	2017
topic_facet	Системний аналіз
url	http://dspace.nbuv.gov.ua/handle/123456789/144686
citation_txt	Специальные транспозиции элементов перестановок и свойства композиции / И.В. Гребенник, О.С. Черная // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 79-90. — Бібліогр.: 15 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT grebennikiv specialʹnyetranspoziciiélementovperestanovokisvojstvakompozicii AT černaâos specialʹnyetranspoziciiélementovperestanovokisvojstvakompozicii
first_indexed	2025-07-10T19:53:30Z
last_indexed	2025-07-10T19:53:30Z
_version_	1837290986701586432
fulltext	ÓÄÊ 519.85 È.Â. ÃÐÅÁÅÍÍÈÊ, Î.Ñ. ×ÅÐÍÀß ÑÏÅÖÈÀËÜÍÛÅ ÒÐÀÍÑÏÎÇÈÖÈÈ ÝËÅÌÅÍÒÎÂ ÏÅÐÅÑÒÀÍÎÂÎÊ È ÑÂÎÉÑÒÂÀ ÊÎÌÏÎÇÈÖÈÈ Àííîòàöèÿ. Ïðåäëîæåíà ñòðàòåãèÿ ðåøåíèÿ çàäà÷è îïòèìèçàöèè ëèíåéíîé ôóíêöèè íà ìíîæåñòâå öèêëè÷åñêèõ ïåðåñòàíîâîê íà îñíîâå ñâîéñòâ òðàíñ- ïîçèöèé ñïåöèàëüíîãî âèäà. Èññëåäîâàíû ñâîéñòâà ñïåöèàëüíîãî êëàññà òðàíñïîçèöèé, äîêàçàíû óòâåðæäåíèÿ î âëèÿíèè êîìïîçèöèé òàêèõ òðàíñïî- çèöèé íà ïðîèçâîëüíóþ ïåðåñòàíîâêó. Äëÿ ïðèáëèæåííîãî ðåøåíèÿ, ïîëó- ÷åííîãî ñ ïîìîùüþ îïèñàííîé ñòðàòåãèè, îáîñíîâàíà îöåíêà. Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ëèíåéíàÿ ôóíêöèÿ, ïåðåñòà- íîâêè, òðàíñïîçèöèè, öèêëè÷åñêèå ïåðåñòàíîâêè. ÂÂÅÄÅÍÈÅ Ïðè àíàëèçå ìíîãèõ íàó÷íûõ è ïðèêëàäíûõ çàäà÷ ñðåäñòâàìè ìàòåìàòè÷åñêî- ãî ìîäåëèðîâàíèÿ âûñòóïàþò êîìáèíàòîðíûå ìíîæåñòâà [1–7]. Íàèáîëåå ðàñ- ïðîñòðàíåííûì ñðåäè íèõ ÿâëÿþòñÿ ìíîæåñòâî ïåðåñòàíîâîê è åãî ðàçëè÷íûå ïîäìíîæåñòâà. Äîïîëíèòåëüíûå îãðàíè÷åíèÿ íà ïåðåìåííûå â òàêèõ çàäà÷àõ ïîçâîëÿþò âûäåëèòü ñëåäóþùèå èçâåñòíûå â ëèòåðàòóðå êëàññû ìíîæåñòâ ïå- ðåñòàíîâîê: ïåðåñòàíîâêè Pn ðàçëè÷íûõ ýëåìåíòîâ, ïåðåñòàíîâêè ñ ïîâòîðåíè- ÿìè, ïåðåñòàíîâêè Pnk èç n ýëåìåíòîâ, k èç êîòîðûõ ðàçëè÷íû, öèêëè÷åñêèå ïåðåñòàíîâêè Pn C , ïåðåñòàíîâêè PT nk m êîðòåæåé, êîìïîçèöèè ïåðåñòàíîâîê PWn , ïåðåñòàíîâêè, ñîäåðæàùèå (íå ñîäåðæàùèå) øàáëîí (pattern), ïîëèïåðåñ- òàíîâêè è äðóãèå [1, 4, 8, 9]. Èññëåäîâàíèå è èñïîëüçîâàíèå ñâîéñòâ ýòèõ êîìáèíàòîðíûõ îáúåêòîâ ïîâûøàåò ýôôåêòèâíîñòü ïðîöåññîâ ìîäåëèðîâàíèÿ è ðåøåíèÿ çàäà÷, èìåþùèõ êîìáèíàòîðíóþ ñòðóêòóðó, â ÷àñòíîñòè çàäà÷ êîì- áèíàòîðíîé ãåíåðàöèè è êîìáèíàòîðíîé îïòèìèçàöèè. Èçâåñòåí ñïîñîá èññëåäîâàíèÿ êîìáèíàòîðíûõ ìíîæåñòâ, îñíîâàííûé íà èõ ïîãðóæåíèè â åâêëèäîâî ïðîñòðàíñòâî [3, 6]. Òîãäà âûïóêëàÿ îáîëî÷êà îáðàçà êîìáèíàòîðíîãî ìíîæåñòâà, ïîëó÷åííàÿ â ðåçóëüòàòå ïîãðóæåíèÿ, ïðåäñòàâëÿåò ñîáîé êîìáèíàòîðíûé, â ÷àñòíîñòè ïåðåñòàíîâî÷íûé, ìíîãîãðàííèê [2]. Äëÿ ðàç- ëè÷íûõ ïîäìíîæåñòâ ìíîæåñòâà ïåðåñòàíîâîê ïðè ïîãðóæåíèè â åâêëèäîâî ïðî- ñòðàíñòâî â íàñòîÿùåå âðåìÿ íåèçâåñòíû îïèñàíèÿ ñîîòâåòñòâóþùèõ êîìáèíà- òîðíûõ ìíîãîãðàííèêîâ. Ïîýòîìó ïðè ðåøåíèè çàäà÷ íà ýòèõ ìíîæåñòâàõ ïðåä- ëàãàåòñÿ èñïîëüçîâàòü ïåðåñòàíîâî÷íûé ìíîãîãðàííèê, íî ïðè ýòîì èññëåäîâàòü òå åãî âåðøèíû, êîòîðûå ñîîòâåòñòâóþò ýëåìåíòàì çàäàííîãî ïîäìíîæåñòâà ìíîæåñòâà ïåðåñòàíîâîê. Îäíèì èç áàçîâûõ ñâîéñòâ ïåðåñòàíîâî÷íîãî ìíîãîã- ðàííèêà ÿâëÿåòñÿ êðèòåðèé ñìåæíîñòè åãî âåðøèí [2]. Îñíîâîé ïîñòðîåíèÿ ïåðåñòàíîâîê ÿâëÿþòñÿ òðàíñïîçèöèè ïîðîæäàþ- ùèõ ýëåìåíòîâ. Ñóùåñòâóåò êëàññ òðàíñïîçèöèé, ïðåäñòàâèòåëè êîòîðîãî ñîîòâåòñòâóþò êðèòåðèþ ñìåæíîñòè â ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå [3] â ñëåäóþùåì ïîíèìàíèè. Ïðè ïðèìåíåíèè ê ëþáîé ïåðåñòàíîâêå òðàíñïîçè- öèè äàííîãî êëàññà áóäåò ïîëó÷åíà òàêàÿ ïåðåñòàíîâêà, ÷òî âåðøèíû, ñîîò- âåòñòâóþùèå îáåèì ïåðåñòàíîâêàì â ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå, ÿâëÿ- þòñÿ ñìåæíûìè. Èñïîëüçîâàíèå òðàíñïîçèöèé äàííîãî êëàññà è ñîîòâåòñòâóþ- ùèõ ñâîéñòâ ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà ïîçâîëÿåò ðåøàòü çàäà÷è êîìáèíàòîðíîé ãåíåðàöèè è êîìáèíàòîðíîé îïòèìèçàöèè, ïðèìåíÿÿ ïåðåõîäû ïî ñìåæíûì âåðøèíàì ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà [2, 3]. Àêòóàëüíîé ÿâëÿåòñÿ çàäà÷à ïîñòðîåíèÿ è èññëåäîâàíèÿ ñâîéñòâ êîìïîçèöèè íåñêîëüêèõ òðàíñïîçèöèé ñïåöèàëüíîãî êëàññà è àíàëèçà ðåçóëüòàòîâ èõ âîçäåé- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 79 © È.Â. Ãðåáåííèê, Î.Ñ. ×åðíàÿ, 2017 ñòâèÿ íà íåêîòîðóþ ïåðåñòàíîâêó. Ïðè ýòîì ðàçíûå ïîðÿäêè ñëåäîâàíèÿ òðàíñ- ïîçèöèé â êîìïîçèöèè îïðåäåëÿþò ðàçëè÷íûå ïåðåñòàíîâêè â ðåçóëüòàòå ïðèìå- íåíèÿ êîìïîçèöèè íåñêîëüêèõ òðàíñïîçèöèé ê íåêîòîðîé ïåðåñòàíîâêå. Ñóùåñòâåííûìè ÿâëÿþòñÿ ñëåäóþùèå äâà âîïðîñà î ïðèìåíåíèè êîìïîçè- öèé òðàíñïîçèöèé ê íåêîòîðîé ïåðåñòàíîâêå. 1. Ñêîëüêî ðàçëè÷íûõ ïåðåñòàíîâîê ìîæíî ïîëó÷èòü, ïðèìåíÿÿ çàäàííóþ êîìïîçèöèþ òðàíñïîçèöèé ê íåêîòîðîé ïåðåñòàíîâêå, åñëè òðàíñïîçèöèè áóäóò ñëåäîâàòü â ðàçëè÷íûõ ïîðÿäêàõ? 2. Ñêîëüêî ðàçëè÷íûõ ïîñëåäîâàòåëüíîñòåé òðàíñïîçèöèé è êàêèå èìåííî â çàäàííîé êîìïîçèöèè ïðè ïðèìåíåíèè ê íåêîòîðîé ïåðåñòàíîâêå ïðèâåäóò ê îäíîé ðåçóëüòèðóþùåé ïåðåñòàíîâêå? Îòâåòû íà ýòè âîïðîñû ïîçâîëÿò èñïîëüçîâàòü èçâåñòíûå ìåòîäû ðåøåíèÿ çà- äà÷ íà ìíîãîãðàííèêàõ, ïðèìåíÿÿ äëÿ ýòîãî íå òîëüêî ñìåæíûå âåðøèíû, íî è ïî- ñëåäîâàòåëüíîñòè ñìåæíûõ âåðøèí, îòâå÷àþùèå êîìïîçèöèÿì òðàíñïîçèöèé, ñîîò- âåòñòâóþùèõ êðèòåðèþ ñìåæíîñòè â ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå. Â ÷àñòíîñòè, èññëåäîâàíèå äàííûõ ñâîéñòâ òðàíñïîçèöèé ïðèìåíèìî äëÿ ðåøåíèÿ çàäà÷ îïòèìè- çàöèè ëèíåéíûõ ôóíêöèé íà ïîäìíîæåñòâàõ ìíîæåñòâà ïåðåñòàíîâîê [10]. Öåëü ñòàòüè — ðåøåíèå çàäà÷ îïòèìèçàöèè ëèíåéíûõ ôóíêöèé íà ïîäìíî- æåñòâàõ ìíîæåñòâà ïåðåñòàíîâîê íà îñíîâå èññëåäîâàíèÿ ñâîéñòâ òðàíñïîçèöèé, ñîîòâåòñòâóþùèõ êðèòåðèþ ñìåæíîñòè â ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå. ÁÀÇÎÂÛÅ ÎÏÐÅÄÅËÅÍÈß Îïðåäåëåíèå 1 [8]. Ëèíåéíîå óïîðÿäî÷åíèå ýëåìåíòîâ íåêîòîðîãî ïîðîæäàþùåãî ìíîæåñòâà A a a an� � �{ , }1 2 � íàçûâàåòñÿ ïåðåñòàíîâêîé � �� ( , )a a an1 2 � � � � �( ( ), ( ), ..., ( )) ( , )� � �a a a a a an i i in1 2 1 2 � èëè n-ïåðåñòàíîâêîé, åñëè íåîáõî- äèìî îòìåòèòü òîò ôàêò, ÷òî îíà ñîäåðæèò n ýëåìåíòîâ. Ìíîæåñòâî ïåðåñòàíî- âîê, ïîðîæäåííîå ýëåìåíòàìè a a an1 2� � �� , îáîçíà÷èì Pn . Ðàññìîòðèì íåêîòîðóþ ïåðåñòàíîâêó � � � �� ( ( ), ( ), ..., ( ))a a a Pn n1 2 è åå ýëåìåíò �( )a ai j� � �i j Jn, . Òîãäà çàïèøåì � � � �( ) ( ( )) ( )a a aj i i� � 2 . Îáîá- ùåííî ýòó ôîðìóëó ìîæíî ïðåäñòàâèòü â âèäå � � � �k j k i k ia a a� �� 1 1( ) ( ( )) ( ) � �i j Jn, , k n� . Òàêèì îáðàçîì [5], åñëè äëÿ íåêîòîðîãî l 1 èìååì � l i ia a( ) � , i Jn� , è ýëå- ìåíòû a a a ai i i l i, ( ), ( ), ..., ( )� � �2 1� ðàçëè÷íû, òî ïîñëåäîâàòåëüíîñòü ( , ( ),a ai i� � �2 1( ), ..., ( ))a ai l i � íàçûâàåòñÿ öèêëîì äëèíû l . Öèêëû ( , ( ), ... , ( ))a a ai i l i� � �1 è ( ( ), ( ), ... , ( ),� � �j i j i l i ia a a a �1 1 , ... � � �� j ia1 ( )) ñ÷èòàþòñÿ ýêâèâàëåíòíûìè. Êàæäûé ýëåìåíò ìíîæåñòâà A a a an� � �{ , }1 2 � íàõîäèòñÿ â åäèíñòâåííîì öèêëå ïåðåñòàíîâêè � , è âîçìîæ- íî ðàññìàòðèâàòü � êàê ïðîèçâåäåíèå ðàçëè÷íûõ öèêëîâ C Ck1, ..., : � � � C C Ck1 2 ... [5]. Íàïðèìåð, åñëè ïåðåñòàíîâêà � îïðåäåëåíà ðàâåíñòâàìè �( )1 4� , �( )2 2� , �( )3 7� , �( )4 1� , �( )5 3� , �( )6 6� , �( )7 5� , òî � � ( )( )( )( )14 2 375 6 . Âîçìîæíû ðàçëè÷íûå îáîçíà÷åíèÿ òàêîãî ïðåäñòàâëåíèÿ �, íàïðèìåð � � ( )( )( )( )753 14 6 2 . Ìîæíî îïðåäåëèòü ñòàíäàðòíîå ïðåäñòàâëåíèå, ïðè ýòîì â êàæäîì öèêëå çàïèñûâàåòñÿ ïåðâûì åãî íàèáîëüøèé ýëåìåíò è öèê- ëû çàïèñûâàþòñÿ â ïîðÿäêå âîçðàñòàíèÿ èõ ìàêñèìàëüíûõ ýëåìåíòîâ. Òàêèì îáðàçîì, ñòàíäàðòíàÿ ôîðìà ðàññìîòðåííîé âûøå ïåðåñòàíîâêè � åñòü ( )( )( )( )2 41 6 753 [5]. Îïðåäåëåíèå 2 [5]. Öèêëè÷åñêîé ïåðåñòàíîâêîé íàçûâàåòñÿ òàêàÿ ïåðåñòà- íîâêà � èç n ýëåìåíòîâ, êîòîðàÿ ñîäåðæèò åäèíñòâåííûé öèêë äëèíû n , ò.å. � n i ia a( ) � � �i Jn . 80 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 Òàêèå ïåðåñòàíîâêè áóäåì îáîçíà÷àòü �C . Â ýòîì ñëó÷àå Pn C — ìíîæåñòâî öèêëè÷åñêèõ ïåðåñòàíîâîê �C [5, 8]. Îáîçíà÷èì E f Pn Ñ n C� ( ) îáðàç ìíîæåñòâà öèêëè÷åñêèõ ïåðåñòàíîâîê Pn C ïðè ïîãðóæåíèè â åâêëèäîâî ïðîñòðàíñòâî [3, 6]. Ïîñëå ïîãðóæåíèÿ ìíîæåñòâà a a an1 2� � �� áóäåò ïîðîæäåí ïåðåñòàíîâî÷íûé ìíîãîãðàííèê Ï n , ãäå vert Ï En n� — ìíîæåñòâî åãî âåðøèí. Ïîñêîëüêó ìåæäó ìíîæåñòâîì ïîðîæäàþùèõ ýëåìåíòîâ A a a an� � �{ , }1 2 � , a a an1 2� � �� , è ìíîæåñòâîì èõ èíäåêñîâ J n� { , , ..., }1 2 ñóùåñòâóåò âçàèìíî- îäíîçíà÷íîå ñîîòâåòñòâèå, äàëåå áåç ïîòåðè îáùíîñòè áóäåì ðàññìàòðèâàòü ìíî- æåñòâî ïåðåñòàíîâîê Pn , ïîðîæäåííîå ýëåìåíòàìè { , , ..., }1 2 n , ò.å. A Jn� . Îáîçíà÷èì � ab n( , , ..., )1 2 òàêóþ ïåðåñòàíîâêó èç ýëåìåíòîâ A Jn� , ÷òî ïðè îòîáðàæåíèè � ab nn i i i( , , ..., ) ( , )1 2 1 2� � �� ýëåìåíòû i ak � �( ) è i bl � �( ) èìåþò k l� . Ìíîæåñòâîì òàêèõ ïåðåñòàíîâîê ñîîòâåòñòâåííî áóäåò P Pab n� . Ðàññìîòðèì ôóíêöèþ � i íà ìíîæåñòâå ïîðîæäàþùèõ ýëåìåíòîâ, � i A A: � , îïðåäåëåííóþ ñëåäóþùèì îáðàçîì: �( )1 1� , �( )2 2� ,…, �( )i i� 1 , �( )i i �1 ,…, �( )n n� , (1) ãäå i Jn� �1. Ôóíêöèÿ, îïðåäåëåííàÿ òàêèì îáðàçîì, ÿâëÿåòñÿ áèåêòèâíîé è ïðåäñòàâëÿåò òðàíñïîçèöèþ ýëåìåíòîâ { , }i i A �1 [9]. Ñîãëàñíî ñâîéñòâó ôóíêöèÿ � i , çàäàííàÿ â âèäå (1), ñîîòâåòñòâóåò êðèòåðèþ ñìåæíîñòè ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà Ï n . Â ðåçóëüòàòå ïðèìåíåíèÿ ôóíêöèè � i p( ) ê ïðîèçâîëüíîé ïåðåñòàíîâêå p Pn� ïîëó÷åíà ïåðåñòàíîâêà pk òàêàÿ, ÷òî ñîîòâåòñòâóþùèå ïåðåñòàíîâêàì p è pk âåðøèíû ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà ÿâëÿþòñÿ ñìåæíûìè. Äëÿ ëþáîé âåðøèíû � �vert Ï n òðàíñïîçèöèþ � �i ( ) âèäà (1) ýëåìåíòîâ { , }i i 1 , ïðèíàäëåæàùèõ îäíîìó öèêëó äëèíû k ñîîòâåòñòâóþùåé ïåðåñòàíîâêè p Pn� , íàçîâåì òðàíñïîçèöèåé ðàçðûâà. Ïðè ïðèìåíåíèè òàêîé òðàíñïîçèöèè ê p Pn� áóäåò ïîëó÷åíà ñìåæíàÿ ñ èñõîäíîé âåðøèíà � � �i i nÏ( ) � �vert òàêàÿ, ÷òî ñîîòâåòñòâóþùàÿ åé ïåðåñòàíîâêà p Pi n� èìååò äâà öèêëà, êîòîðûå ñîñòîÿò èç ýëåìåíòîâ öèêëà äëèíû k, ñîäåðæàùåãî äëèíû k1 è k2 , ò.å. k k k1 2 � . Äëÿ ëþáîé âåðøèíû � �vert Ï n òðàíñïîçèöèþ � �i ( ) âèäà (1) ýëåìåíòîâ { , }i i 1 , ïðèíàäëåæàùèõ äâóì ðàçíûì öèêëàì äëèíû k1 è k2 ñîîòâåòñòâóþùåé ïåðå- ñòàíîâêè p Pn� , íàçîâåì òðàíñïîçèöèåé ñîåäèíåíèÿ. Ïðè ïðèìåíåíèè òàêîé òðàíñïî- çèöèè ê p Pn� ïîëó÷åíà ñìåæíàÿ ñ èñõîäíîé âåðøèíà � � �i i nÏ( ) � �vert . Ñîîòâåò- ñòâóþùàÿ åé ïåðåñòàíîâêà p Pi n� ñîäåðæèò öèêë äëèíû k, ñîñòîÿùèé èç ýëåìåíòîâ öèêëîâ äëèí k1 è k2 , k k k� 1 2 . Ñëåäîâàòåëüíî, äëÿ âåðøèí � �vert Ï n îäíà òðàíñ- ïîçèöèÿ � �i ( ) âèäà (1) ýëåìåíòîâ { , }i i 1 , i Jn� �1, ìîæåò áûòü ëèáî ðàçðûâîì, ëèáî ñîåäèíåíèåì öèêëîâ, êîòîðûì ýòè ýëåìåíòû ïðèíàäëåæàò. Â ñëó÷àå, åñëè èñõîäíàÿ ïå- ðåñòàíîâêà ïðèíàäëåæèò ìíîæåñòâó öèêëè÷åñêèõ ïåðåñòàíîâîê p Pn C� è èìååò åäèí- ñòâåííûé öèêë äëèíû n, ëþáàÿ òðàíñïîçèöèÿ âèäà (1) áóäåò ðàçðûâîì [11–13]. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ðàññìîòðèì çàäà÷ó êîìáèíàòîðíîé îïòèìèçàöèè â ñëåäóþùåé ïîñòàíîâêå: L p c pi i i n ( ) min� � � 1 ; (2) p p p p P Pn n� � � � �( , )1 2 � , (3) ãäå c Rj � , p J ni n� � { , , ..., }1 2 , i Jn� �i j, , p pi j� , P Pn�{ , Pnk , Pn C , PWn , PT nk m } . Çäåñü Pn — ìíîæåñòâî ïåðåñòàíîâîê èç n ðàçëè÷íûõ ýëåìåíòîâ, ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 81 Pnk — ìíîæåñòâî ïåðåñòàíîâîê èç n ýëåìåíòîâ, k èç êîòîðûõ ðàçëè÷íû, Pn C — ìíîæåñòâî öèêëè÷åñêèõ ïåðåñòàíîâîê, PWn — êîìïîçèöèÿ ïåðåñòàíî- âîê, PT nk m — ïåðåñòàíîâêè êîðòåæåé. Â äàííîé ñòàòüå äàëåå â êà÷åñòâå ïðèìå- ðà èç ìíîæåñòâà { , , , , }P P P PW PTn nk n C n nk m âûáåðåì ìíîæåñòâî öèêëè÷åñêèõ ïåðåñòàíîâîê, ò.å. P Pn Ñ� . Â ðåçóëüòàòå ïîãðóæåíèÿ ìíîæåñòâà P â àðèôìåòè÷åñêîå åâêëèäîâî ïðî- ñòðàíñòâî ìîæåò áûòü ñôîðìóëèðîâàíà ýêâèâàëåíòíàÿ çàäà÷å (2), (3) çàäà÷à îïòèìèçàöèè ëèíåéíîé ôóíêöèè â ïðîñòðàíñòâå R n : L x c xj j j n ( ) min� � � 1 ; (4) x x x x E E E E EW ETn n nk n C n nk m� � � � �( , ) { , , , , }1 2 � , (5) ãäå c Rj � , j Jn� , à ýëåìåíòû ìíîæåñòâà { , , , , }E E E EW ETn nk n C n nk m ïðåäñòàâ- ëÿþò îáðàçû ñîîòâeòñòâóþùèõ ìíîæåñòâ { , , , , }P P P PW PTn nk n C n nk m â R n . Äàëåå ïîëàãàåì E E f Pn C n C� � ( ). Ìíîæåñòâî En Ñ îáëàäàåò âñåìè êîìáèíàòîðíûìè ñâîéñòâàìè ìíîæåñò- âà Pn Ñ . Ñëåäîâàòåëüíî, äàëüíåéøèå âûêëàäêè ñïðàâåäëèâû êàê äëÿ çàäà÷è (2), (3) ïðè P Pn Ñ� , òàê è äëÿ çàäà÷è (4), (5) ïðè E En C� . Îòìåòèì, ÷òî çàäà÷à ïîèñêà ìèíèìóìîâ ëèíåéíûõ ôóíêöèé íà åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâàõ ïåðåñòàíîâîê è ðàçìåùåíèé áåç äîïîëíèòåëüíûõ îãðàíè÷åíèé ðåøåíà, íàïðèìåð, â [6, 14]. Ðåøåíèå çàäà÷è (2), (3) íà ìíîæåñòâå ïåðåñòàíîâîê Pnk , ïîðîæäåííîì ýëåìåíòàìè a a an1 2� � �� , èìååò âèä [6, 14] p p p p c pn p P j j j n nk * * * ( , ) min� � � � � � 1 2 1 � arg , c Rj � 1 � �j Jn , ãäå p am jj � � �j Jn , à ïîñëåäîâàòåëüíîñòü { , }m m mn1 2 � �� òàêîâà, ÷òî c c cm m mn1 2 � . Îòìåòèì, ÷òî êîìáèíàòîðíûå ñâîéñòâà ìíîæåñòâà öèêëè÷åñêèõ ïåðåñòàíî- âîê Pn C íå ïîçâîëÿþò ðåøèòü çàäà÷ó (4), (5) ïðîñòûì óïîðÿäî÷èâàíèåì. ÑÂÎÉÑÒÂÀ ÒÐÀÍÑÏÎÇÈÖÈÉ ÑÏÅÖÈÀËÜÍÎÃÎ ÂÈÄÀ Îäèí èç ïîäõîäîâ ê ðåøåíèþ çàäà÷è (4), (5) ñîñòîèò â èññëåäîâàíèè ñâîéñòâ öèêëè÷åñêèõ ïåðåñòàíîâîê è ñâîéñòâ òðàíñïîçèöèé âèäà (1). Íåîáõîäèìî îò- ìåòèòü, ÷òî âñå ðàññìàòðèâàåìûå äàëåå òðàíñïîçèöèè ïî óìîë÷àíèþ ñ÷èòàþò- ñÿ òðàíñïîçèöèÿìè âèäà (1). Ââåäåì ñëåäóþùèå ïîíÿòèÿ. Íàçîâåì äâå òðàíñïîçèöèè � i è � j íåïåðåñåêàþùèìèñÿ, åñëè ïîäìíîæåñòâà ýëåìåíòîâ { , }i i 1 è { , }j j 1 , ñîîòâåòñòâóþùèå êàæäîé òðàíñïîçèöèè, íå ïåðåñå- êàþòñÿ. Åñëè ïîäìíîæåñòâà { , }i i 1 è { , }j j 1 , ñîîòâåòñòâóþùèå äâóì òðàíñïîçè- öèÿì � i è � j , ïåðåñåêàþòñÿ è i j �1 èëè i j� 1 , òî òàêèå òðàíñïîçèöèè áóäåì íàçûâàòü ïåðåñåêàþùèìèñÿ. Åñëè â íåêîòîðîì ìíîæåñòâå òðàíñïîçèöèé { , }� � �i i ik1 2 � �� äâå òðàíñïîçè- öèè � i è � j ðàâíû, ò.å. i j� , òî òàêèå òðàíñïîçèöèè íàçîâåì êðàòíûìè. Êðàò- íîñòü m òðàíñïîçèöèè îïðåäåëÿåòñÿ êîëè÷åñòâîì îäèíàêîâûõ òðàíñïîçèöèé â íå- êîòîðîé ïîñëåäîâàòåëüíîñòè òðàíñïîçèöèé. Äâå òðàíñïîçèöèè � i è � j ÿâëÿþòñÿ 82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 êîììóòàòèâíûìè, åñëè äëÿ ëþáîé ïåðåñòàíîâêè p Pn� âûïîëíÿåòñÿ ðàâåíñòâî � � � � � �i j i j j ip p� � � �( ( )) ( ( )) � �j i� [15]. Ñóïåðïîçèöèþ k òðàíñïîçèöèé { , }� � �i i ik1 2 � �� áóäåì îáîçíà÷àòü �k � � � � �i i ik1 2 � �� . Ñóïåðïîçèöèè òðàíñïîçèöèé �k i i ik � � � � 1 2 � �� ïîñòàâèì â ñîîòâåòñòâèå ïîäìíîæåñòâî ïîðîæäàþùèõ ýëåìåíòîâ � � �j k j ji i 1 1{ , } { ,i i1 1 1 , i2 , i2 1 , ... i ik k, } 1 � A. Íàçîâåì ñóïåðïîçèöèþ òðàíñïîçèöèé �k i i ik � � � � 1 2 � �� è òðàíñïîçè- öèþ � j íåïåðåñåêàþùèìèñÿ, åñëè ïîäìíîæåñòâà � � �j k j ji i 1 1{ , } { ,i i1 1 1 , i2 , i i ik k2 1 1 , ..., , } è { , }j j 1 , ñîîòâåòñòâóþùèå èì, íå ïåðåñåêàþòñÿ. Åñëè ïîäìíî- æåñòâà � �j k j ji i 1 1{ , } è { , }j j 1 ïåðåñåêàþòñÿ è j i i j k j j� � �1 1{ , } èëè j �1 � � �j k j ji i 1 1{ , }, òî �k è � j íàçîâåì ïåðåñåêàþùèìèñÿ. Åñëè îáà ýëåìåíòà òðàíñ- ïîçèöèè � j ïðèíàäëåæàò ïîäìíîæåñòâó ñóïåðïîçèöèè �k i� � 1 � � �i ik2 �� , ò.å. { , } { , }j j i i j k j j � � � 1 1 1 , íî íè îäíà èç òðàíñïîçèöèé � � �i i ik1 2 , � �� íå ðàâíà òðàíñïî- çèöèè �j , òî òðàíñïîçèöèþ � j íàçîâåì âëîæåííîé ïî îòíîøåíèþ ê ñóïåðïîçèöèè �k . Åñëè îáà ýëåìåíòà òðàíñïîçèöèè � j ïðèíàäëåæàò ïîäìíîæåñòâó ñóïåðïîçè- öèè �k i i ik � � � � 1 2 � �� , ò.å. { , } { , }j j i i j k j j � � � 1 1 1 , è � j ðàâíà îäíîé èç òðàíñïîçèöèé { , }� � �i i ik1 2 � �� , ó÷àñòâóþùèõ â êîìïîçèöèè �k , òî òðàíñïîçè- öèþ � j íàçîâåì êðàòíîé ïî îòíîøåíèþ ê êîìïîçèöèè �k . Îáîçíà÷èì êîìïîçèöèþ � �k n i n i k nP p P p p p P( ) { \| ( ), }� � � � , i Jk� !, êàê ðåçóëüòàò ïðèìåíåíèÿ ê íåêîòîðîé ïåðåñòàíîâêå p Pn� êîìïîçèöèè �k � � � � �i i ik1 2 � �� òðàíñïîçèöèé { , }� � �i i ik1 2 � �� . Èç ìíîæåñòâà { , }� � �i i ik1 2 � �� ìîæíî ñîñòàâèòü P kk � ! ðàçëè÷íûõ ïîñëåäîâàòåëüíîñòåé òðàíñ- ïîçèöèé, êîòîðûå ìîãóò áûòü ïðèìåíåíû ê èñõîäíîé ïåðåñòàíîâêå. Ðàññìîòðèì ðåçóëüòàò âîçäåéñòâèÿ êîìïîçèöèè �k íà íåêîòîðóþ ïåðåñòàíîâêó p Pn� â çàâè- ñèìîñòè îò ñâîéñòâ çàäàííûõ òðàíñïîçèöèé { , }� � �i i ik1 2 � �� è èõ ïîðÿäêà â êîì- ïîçèöèè. Ñ ýòîé öåëüþ äîêàæåì ðÿä óòâåðæäåíèé. ÏÐÈÌÅÍÅÍÈÅ ÊÎÌÏÎÇÈÖÈÉ ÒÐÀÍÑÏÎÇÈÖÈÉ Ê ÏÐÎÈÇÂÎËÜÍÎÉ ÏÅÐÅÑÒÀÍÎÂÊÅ Ëåììà 1. Ñóïåðïîçèöèÿ �n i i in � � � � 1 2 � �� íåïåðåñåêàþùèõñÿ òðàíñïîçè- öèé { , }� � �i i in1 2 � �� òàêîâà, ÷òî äëÿ ëþáûõ äâóõ òðàíñïîçèöèé � � � � �i i i i ix y n , { , }� � � 1 2 � âûïîëíÿåòñÿ ïðàâèëî êîììóòàòèâíîñòè � � � � �i i i i iy z n1 2 � �� = � � � � �i i i i iz y n1 2 � �� . Äîêàçàòåëüñòâî ïðîâåäåì ïî èíäóêöèè. Äëÿ n �1 ýòî òðèâèàëüíûé ñëó÷àé ñ îäíîé òðàíñïîçèöèåé. Äëÿ n � 2 ðàññìîòðèì êîìïîçèöèþ èç äâóõ íåïåðåñåêàþùèõñÿ òðàíñïîçèöèé { , }� �i i1 2 è ïîêàæåì, ÷òî äëÿ òàêîãî ÷àñòíîãî ñëó÷àÿ êîììóòàòèâíîñòü âûïîëíÿåòñÿ. Ðàññìîòðèì ïðèìåíåíèå êîìïîçèöèè � �i i1 2 � = � �i i p 1 2 ( ( )): � � �i i i1 2 1 1 1 1( ( )) ( )� � , � � �i i i1 2 1 2 2 2( ( )) ( )� � , …, � � �i i ii i i 1 2 11 1 1 1( ( )) ( )� � , � � �i i ii i i 1 2 11 1 11 1( ( )) ( ) � � , … , � � �i i ii i i 1 2 12 2 21 1( ( )) ( )� � , � � �i i ii i i 1 2 12 2 21( ( )) ( ) � � , … , � � �i i in n n 1 2 1 ( ( )) ( )� � . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 83 Ïðèìåíåíèå êîìïîçèöèè � �i i2 1 � = � �i i p 2 1 ( ( )): � � �i i i2 1 2 1 1 1( ( )) ( )� � , � � �i i i2 1 2 2 2 2( ( )) ( )� � , … ... , � � �i i ii i i 2 1 21 1 11 1( ( )) ( )� � , � � �i i ii i i 2 1 21 1 11( ( )) ( ) � � , … ... , � � �i i ii i i 2 1 22 2 2 1( ( )) ( )� � , � � �i i ii i i 2 1 22 2 21 1( ( )) ( ) � � , … ..., � � �i i in n n 2 1 2 ( ( )) ( )� � . Èñõîäÿ èç ðåçóëüòàòîâ ïðèìåíåíèÿ òðàíñïîçèöèé { , }� �i i1 2 â ðàçëè÷íîì ïî- ðÿäêå, ìîæíî ñäåëàòü âûâîä, ÷òî � � � �i i i i1 2 2 1 � �� . Ïðåäïîëîæèì, ÷òî äëÿ n k� íåïåðåñåêàþùèõñÿ òðàíñïîçèöèé { , }� � �i i ik1 2 � �� ëåììà 1 âûïîëíÿåòñÿ, è äîêàæåì, ÷òî òîãäà îíà âûïîëíÿåòñÿ è äëÿ n k� 1 . Äëÿ ýòîãî ðàññìîòðèì ñóïåðïîçèöèþ �k i i i ik k � 1 1 2 1 � � � �� è äîêàæåì, ÷òî �k �1 �k ik � � � 1 � i kk � 1 � � � �s i lk � �� 1 � �s l s l k, : . Êîìïîçèöèÿ �k èç k òðàíñïîçèöèé { , }� � �i i ik1 2 � �� ÿâëÿåòñÿ áèåêòèâíîé ôóíêöèåé, è äëÿ íåå âûïîëíÿåòñÿ óñëîâèå êîììóòàòèâíîñòè, ÷òî ñëåäóåò èç èí- äóêòèâíîãî ïðåäïîëîæåíèÿ. Òàê êàê âñå òðàíñïîçèöèè { , , }� � � �i i i ik k1 2 1 � � � íå- ïåðåñåêàþùèåñÿ, ñëåäîâàòåëüíî, ïîäìíîæåñòâà ýëåìåíòîâ A Jn� , ñîîòâåòñòâó- þùèå �k è � ik 1 , íå ïåðåñåêàþòñÿ. Òàêèì îáðàçîì, êîìïîçèöèþ ôóíêöèè � ik 1 è ñóïåðïîçèöèè �k ìîæíî ðàññìàòðèâàòü êàê êîìïîçèöèþ äâóõ áèåêöèé. À äëÿ äâóõ ýëåìåíòîâ äîêàçàíî, ÷òî � �i k k ik k � 1 1 � �� . Äàëåå ðàññìîòðèì �k �1 � �s i lk � �� 1 � �s l s l k, : . Òàê êàê s è l ìåíüøå k, ñëåäîâàòåëüíî, èñõîäÿ èç èíäóêòèâíîãî ïðåäïîëîæåíèÿ �s è �l êîììóòàòèâíû. Ó÷òåì, ÷òî �s è �l ÿâëÿþòñÿ áèåêöèÿìè, òàê êàê îíè — êîìïîçèöèè áèåêöèé. Èñõîäÿ èç òîãî, ÷òî âñå òðàíñïîçèöèè { , , }� � � �i i i ik k1 2 1 � � � íåïåðåñåêàþùèåñÿ, ïîäìíîæåñòâà, ñîîòâåòñòâóþùèå �s , �l è � ik 1 , íå ïåðåñåêàþòñÿ. Òàêèì îáðà- çîì, � � �k k i lk � 1 1 � �� ÿâëÿåòñÿ êîìïîçèöèåé òðåõ íåïåðåñåêàþùèõñÿ áèåêöèé, äëÿ êîòîðûõ ëåììà 1 âåðíà, èñõîäÿ èç èíäóêòèâíîãî ïðåäïîëîæåíèÿ. Ïîñêîëüêó ëåììà 1 äîêàçàíà äëÿ n k� 1, ñëåäîâàòåëüíî, ñîãëàñíî ïðèíöèïó ìàòåìàòè÷åñêîé èíäóêöèè îíà âåðíà è äëÿ ëþáîãî êîëè÷åñòâà íåïåðåñåêàþùèõ- ñÿ òðàíñïîçèöèé n, ÷òî è òðåáîâàëîñü äîêàçàòü. Êîìïîçèöèÿ áèåêòèâíûõ ôóíêöèé àññîöèàòèâíà è, êàê áûëî äîêàçàíî â ëåì- ìå 1, êîìïîçèöèÿ íåïåðåñåêàþùèõñÿ òðàíñïîçèöèé êîììóòàòèâíà äëÿ ëþáûõ ýëå- ìåíòîâ êîìïîçèöèè. Èñõîäÿ èç ýòîãî êîëè÷åñòâî êîìïîçèöèé èç íåïåðåñåêàþùèõ- ñÿ òðàíñïîçèöèé { , }� � �i i ik1 2 � �� ðàâíî êîëè÷åñòâó ïåðåñòàíîâîê èç k ýëåìåíòîâ; ðåçóëüòàò ïðèìåíåíèÿ âñåõ êîìïîçèöèé ê ïðîèçâîëüíîé ïåðåñòàíîâêå îäèíàêîâûé. Ñëåäñòâèå 1. Åñëè ê íåêîòîðîé ïåðåñòàíîâêå p Pn� ïðèìåíèòü êîìïîçèöèþ íåïåðåñåêàþùèõñÿ òðàíñïîçèöèé { , }� � �i i ik1 2 � �� , 0 2� �k n / , òî âíå çàâèñè- ìîñòè îò ïîðÿäêà ïðèìåíåíèÿ òðàíñïîçèöèé áóäåò ïîëó÷åíà îäíà è òà æå ïåðå- ñòàíîâêà � �k n i n i k nP p P p p p P( ) { \| ( ), }� � � � , i �1. Ðàññìîòðèì êîìïîçèöèþ äâóõ ïåðåñåêàþùèõñÿ òðàíñïîçèöèé. Ëåììà 2. Äâå ïåðåñåêàþùèåñÿ òðàíñïîçèöèèè { , }� �i i 1 íå êîììóòàòèâíû, ò.å. � � � �i i i i� � �1 1 . Äîêàçàòåëüñòâî. Ðàññìîòðèì êîìïîçèöèþ èç äâóõ ïåðåñåêàþùèõñÿ òðàíñ- ïîçèöèé { , }� �i i 1 è ïîêàæåì, ÷òî êîììóòàòèâíîñòü íå âûïîëíÿåòñÿ. Ðàññìîòðèì ïðèìåíåíèå êîìïîçèöèè � �i i� 1 = � �i i p( ( )) 1 : � � �i i i( ( )) ( ) � �1 1 1 1 , � � �i i i( ( )) ( ) � �1 2 2 2 ,…, � � �i i ii i i( ( )) ( ) � � 1 1 , � � �i i ii i i( ( )) ( ) � � 1 1 2 2, � � �i i ii i i( ( )) ( ) � �1 2 1 , … ... , � � �i i in n n( ( )) ( ) � �1 . 84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 Èçìåíèì ïîðÿäîê êîìïîçèöèé � �i i 1 � = � �i i p 1 ( ( )): � � �i i i � �1 11 1 1( ( )) ( ) , � � �i i i � �1 12 2 2( ( )) ( ) ,… ..., � � �i i ii i i � � 1 1 1 2( ( )) ( ) , � � �i i ii i i � �1 11( ( )) ( ) , � � �i i ii i i � � 1 12 2 1( ( )) ( ) ,…, � � �i i in n n � �1 1( ( )) ( ) . Èñõîäÿ èç ðåçóëüòàòîâ ïðèìåíåíèÿ òðàíñïîçèöèé �� i i, } 1 â ðàçëè÷íîì ïî- ðÿäêå, ìîæíî ñäåëàòü âûâîä, ÷òî � � � �i i i i� � �1 1 . Ñëåäñòâèå 2. Åñëè ê íåêîòîðîé ïåðåñòàíîâêå p Pn� ïðèìåíèòü êîìïîçèöèþ äâóõ ïåðåñåêàþùèõñÿ òðàíñïîçèöèé �� i i, } 1 , òî â ðåçóëüòàòå ïðèìåíåíèÿ äàí- íûõ òðàíñïîçèöèé â ðàçëè÷íûõ ïîðÿäêàõ áóäåò ïîëó÷åíî ìíîæåñòâî � �2 2( ) { \| ( ), }P p P p p p Pn i n i n� � � � , i � 2, èç äâóõ ïåðåñòàíîâîê òàêèõ, ÷òî p p1 2� . Îáîçíà÷èì êîìïîçèöèè ñ ðàçëè÷íûì ïîðÿäêîì ñëåäîâàíèÿ òðàíñïîçè- öèé � � �� 2 2( ) ( )p p , ãäå � � �2 1( )p i i� �� è �� 2 1( )p i i� �� . Äàëåå ðàññìîòðèì êîìáèíàöèþ ïåðåñåêàþùèõñÿ è íåïåðåñåêàþùèõñÿ òðàíñïîçèöèé è èõ ñóïåðïîçèöèè. Ëåììà 3. Ïóñòü èìååì äâå íåïåðåñåêàþùèåñÿ òðàíñïîçèöèè { , }� �i j è îäíó òðàíñïîçèöèþ � i 1 òàêèå, ÷òî { , } { , , }j j i i i � � �1 1 2 . Òîãäà ïðè ïðèìåíåíèè êîìïîçèöèè �3 ( )p òðåõ òðàíñïîçèöèé { , , }� � �i i j 1 êîëè÷åñòâî ïîðîæäàåìûõ ïåðåñòàíîâîê âîçðàñòåò â äâà ðàçà ïî ñðàâíåíèþ ñ êîëè÷åñòâîì ïåðåñòàíîâîê, ïî- ðîæäàåìûõ êîìïîçèöèåé �2 ( )p äâóõ òðàíñïîçèöèé { , }� �i j . Ñïðàâåäëèâîñòü óòâåðæäåíèÿ âûòåêàåò èç ëåìì 1 è 2. Óòâåðæäåíèå 1. Ïóñòü èìååòñÿ êîìïîçèöèÿ �n n ïðîèçâîëüíûõ òðàíñïîçè- öèé � � �i i in1 2 , � �� . Äàííàÿ êîìïîçèöèÿ �n ïîðîæäàåò S ïåðåñòàíîâîê �n p( ) : \| ( ) \|�n p S� . Ïóñòü òàêæå ñóùåñòâóåò îäíà òðàíñïîçèöèÿ � � � �j i i in � � �{ , } 1 2 � òàêàÿ, ÷òî \|{ , } { , }\|j j i im m � �1 1 1. Òîãäà ïðèìåíåíèå êîìïîçèöèè �n 1 òðàíñ- ïîçèöèé { , , }� � � �i i i jn1 2 � �� óâåëè÷èò êîëè÷åñòâî ïîðîæäàåìûõ ïåðåñòàíîâîê â äâà ðàçà: �n p 1 ( ) , \| ( )\|�n p S �1 2 . Äîêàçàòåëüñòâî. Äëÿ n �1 è n � 2 ñïðàâåäëèâîñòü óòâåðæäåíèÿ ñëåäóåò èç ëåìì 2 è 3. Äàëüíåéøåå äîêàçàòåëüñòâî ìîæíî ïðîâåñòè ïî àíàëîãèè ñ ëåììîé 1 ïî èíäóêöèè. Ñëåäñòâèå 3. Ïóñòü èìååì äâå íåïåðåñåêàþùèåñÿ òðàíñïîçèöèè �� i i, } 2 è îäíó òðàíñïîçèöèþ � i 1 . Òîãäà ïðè ïðèìåíåíèè êîìïîçèöèè �3 òðåõ òðàíñïî- çèöèé { , , }� � �i i i 1 2 êîëè÷åñòâî ïîðîæäàåìûõ ïåðåñòàíîâîê âîçðàñòåò â ÷åòû- ðå ðàçà ïî ñðàâíåíèþ ñ êîëè÷åñòâîì ïåðåñòàíîâîê, ïîðîæäàåìûõ êîìïîçèöèåé �2 äâóõ òðàíñïîçèöèé { , }� �i i 2 . Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ìîæåò áûòü ïðîâåäåíî íà îñíîâàíèè ëåì- ìû 1, ñëåäñòâèÿ 2 è óòâåðæäåíèÿ 1. Ñëåäñòâèå 4. Èç òðàíñïîçèöèé { , , }� � �i i i 1 2 ïîëó÷àåì ñëåäóþùèå êîìïîçèöèè: � � �3 1 2� � �i i i� � , �� 3 2 1 2 1� � � � � �i i i i i i� � � � , �� 3 1 2 1 2� � � � � �i i i i i i� � � � , �� IV i i i� � � �2 1� � , ãäå � � �� 3 3 3( ) ( ) ( ) ( )p p p pIV . ÂËÈßÍÈÅ ÒÐÀÍÑÏÎÇÈÖÈÉ ÇÍÀ×ÅÍÈÉ ÏÅÐÅÌÅÍÍÛÕ ÍÀ ÇÍÀ×ÅÍÈÅ ËÈÍÅÉÍÎÉ ÔÓÍÊÖÈÈ Ðàññìîòðèì íåêîòîðóþ ïåðåñòàíîâêó p Pn� è çíà÷åíèå ôóíêöèè L p( ) � � � c pi i i n 1 äëÿ äàííîé ïåðåñòàíîâêè â çàäà÷å (2), (3). Èç óòâåðæäåíèé è ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 85 ñâîéñòâ, äîêàçàííûõ âûøå, èçâåñòíî, êàê ïðèìåíåíèå òðàíñïîçèöèé âèäà (1) âëèÿåò íà ïåðåñòàíîâêó p Pn� . Èññëåäóåì èçìåíåíèå çíà÷åíèÿ ôóíêöèè L p( ) â ðåçóëüòàòå ïðèìåíåíèÿ òðàíñïîçèöèé âèäà (1) ê ïåðåñòàíîâêå p Pn� . Ëþáàÿ òðàíñïîçèöèÿ âèäà (1) èçìåíÿåò çíà÷åíèå öåëåâîé ôóíêöèè ñëåäóþ- ùèì îáðàçîì. Åñëè áóäåò ñîâåðøåíà ïðîèçâîëüíàÿ òðàíñïîçèöèÿ � j ýëåìåíòîâ ( , ) ( , )j j i ir m �1 , òî çíà÷åíèå öåëåâîé ôóíêöèè èçìåíèòñÿ íà íåêîòîðóþ âåëè÷è- íó �rm r mc c� �\| \|, r m J nn, { , , ..., }� � 1 2 . Ëþáàÿ òðàíñïîçèöèÿ �rm ìîæåò ëèáî óâåëè÷èòü, ëèáî óìåíüøèòü çíà÷åíèå ôóíêöèè öåëè. Îáîçíà÷èì � ìíîæåñòâî âñåõ �rm è îòìåòèì, ÷òî ìîùíîñòü äàííîãî ìíîæåñòâà ðàâíà Cn 2 . Ëåììà 4. Åñëè ê íåêîòîðîé ïåðåñòàíîâêå p Pn� ïðèìåíÿåòñÿ êîìïîçèöèÿ �k òðàíñïîçèöèé { , }� � �i i ik1 2 � �� òàêàÿ, ÷òî � �i ij r � � �j r k, { , ..., }1 , òî ëþáàÿ �rm , r m Jn, � , èçìåíèò çíà÷åíèå öåëåâîé ôóíêöèè îäèí è òîëüêî îäèí ðàç. Äîêàçàòåëüñòâî. Ðàññìîòðèì èñõîäíóþ ïåðåñòàíîâêó p i i i Pn n� � � �( , )1 2 � . Âûáåðåì èç ýëåìåíòîâ ïåðåñòàíîâêè ïðîèçâîëüíóþ ïàðó ( , ) ( , )j j i ir m �1 è ñî- âåðøèì èõ òðàíñïîçèöèþ. Òîãäà çíà÷åíèå öåëåâîé ôóíêöèè èçìåíèòñÿ íà �rm r mc c� � . Äëÿ òîãî ÷òîáû â äàëüíåéøåì çíà÷åíèå öåëåâîé ôóíêöèè âíîâü èç- ìåíèëîñü íà òàêóþ æå âåëè÷èíó �rm r mc c� � , íåîáõîäèìî, ÷òîáû íà ìåñòå ïî- ðîæäàþùåãî ýëåìåíòà i jm � ïóòåì òðàíñïîçèöèé âèäà (1) îêàçàëñÿ ýëåìåíò j 2. Ýòî íåâîçìîæíî, ïîñêîëüêó åñëè òðàíñïîçèöèè íå ïîâòîðÿþòñÿ, ýëåìåíò j ìîæåò áûòü çàäåéñòâîâàí â òðàíñïîçèöèè òîëüêî ñ ýëåìåíòîì j �1. Ëåììà 5. Åñëè ê ïåðåñòàíîâêå p Pn* � , p c p p P j j j n n * min� � � arg 1 , ïðèìåíèòü êîì- ïîçèöèþ �k òðàíñïîçèöèé { , }� � �i i ik1 2 � �� òàêóþ, ÷òî � �i iz y � � �z y k, { , ..., }1 , òî � ��rm � , r m Jn, � , ñîîòâåòñòâóþùàÿ ïðèìåíÿåìîé òðàíñïîçèöèè èç ìíîæåñòâà { , }� � �i i ik1 2 � �� áóäåò óâåëè÷èâàòü çíà÷åíèå öåëåâîé ôóíêöèè. Äîêàçàòåëüñòâî. Èñõîäíàÿ ïåðåñòàíîâêà p Pn* � ÿâëÿåòñÿ òî÷êîé ìèíèìóìà ôóíêöèè L p( ) . Ñëåäîâàòåëüíî [6, 10], ýëåìåíòû ïåðåñòàíîâêè p Pn* � èìåþò âèä p p p p c pn p P j j j n nk * * * ( , ) min� � � � � � 1 2 1 � arg , c Rj � 1, p jm j � , à ïîñëåäîâàòåëüíîñòü { , }m m mn1 2 � �� òàêîâà, ÷òî c c cm m mn1 2 � . Ïðîâåäåì äîêàçàòåëüñòâî îò ïðîòèâíîãî. Ïðåäïîëîæèì, ÷òî â ðåçóëüòàòå ïðèìåíåíèÿ íåêîòîðûõ òðàíñïîçèöèé èç ìíîæåñòâà { , }� � �i i ik1 2 � �� áûëà ïîëó- ÷åíà ïðîìåæóòî÷íàÿ ïåðåñòàíîâêà p Pn� . Ïðåäïîëîæèì òàêæå, ÷òî ïðè ïðèìå- íåíèè åùå îäíîé òðàíñïîçèöèè � � � �j i i ik � � �{ , } 1 2 � , íå èñïîëüçóåìîé ðàíåå, áóäåò ïîëó÷åíà òàêàÿ ïåðåñòàíîâêà p pj j� � ( ) , ÷òî L p L pj( ) ( )� � 0. Ðàññìîòðèì p pj j� � ( ) è ó÷òåì, ÷òî ðàíåå ê ïåðåñòàíîâêå p áûëè ïðèìåíå- íû ïðîèçâîëüíûå òðàíñïîçèöèè èç ìíîæåñòâà { , }� � �i i ik1 2 � �� . Ñëåäîâàòåëüíî, â ïåðåñòàíîâêå p ïîðîæäàþùèå ýëåìåíòû { , }j j 1 , ó÷àñòâóþùèå â òðàíñïîçèöèè � j , ñîîòâåòñòâóþò ïðîèçâîëüíûì êîýôôèöèåíòàì c ca b, . Ðàññìîòðèì ðàçíîñòü L p L pj( ) ( )� = (( ) ) ( ( ) )j c j c j c j ca b a b � � � � �1 1 = � � � � � � �(( ) ) ( ( ) )j c j c j c j ca a b b1 1 = c ca b� . Èñõîäÿ èç ïðåäïîëîæåíèÿ, ÷òî L p L pj( ) ( )� � 0 , ðàçíîñòü êîýôôèöèåíòîâ ïîä÷èíÿåòñÿ ñëåäóþùåìó íåðàâåíñòâó: c ca b� � 0. Òîãäà c ca b� . Ó÷òåì, ÷òî ýëåìåíòû { , }j j 1 â ïåðåñòàíîâêå p Pn* � áûëè ðàñïîëîæåíû òà- êèì îáðàçîì, ÷òî ýëåìåíòó j ñîîòâåòñòâîâàë êîýôôèöèåíò c j , à j 1— êîýôôèöè- åíò c j 1, ïðè÷åì èñõîäÿ èç ïðàâèëà ïîñòðîåíèÿ p Pn* � èìååì c cj j 1. Íî â ïå- 86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 ðåñòàíîâêå p Pn� ýëåìåíòû { , }j j 1 áûëè ðàñïîëîæåíû òàêèì îáðàçîì, ÷òî ýëå- ìåíòó j ñîîòâåòñòâîâàë êîýôôèöèåíò ca , à ýëåìåíòó j 1 — êîýôôèöèåíò cb , ïðè÷åì c ca b� . Ñîîòíîøåíèå êîýôôèöèåíòîâ c ca b� íåâîçìîæíî, òàê êàê ýëåìåíò j ïðè ãå- íåðàöèè ïåðåñòàíîâêè p ìîã áûòü çàäåéñòâîâàí â òðàíñïîçèöèÿõ òîëüêî ñ ïîðîæ- äàþùèìè ýëåìåíòàìè, êîòîðûå ìåíüøå åãî; ñëåäîâàòåëüíî, îí ìîã ñîîòâåòñòâî- âàòü òîëüêî êîýôôèöèåíòó c j w� òàêîìó, ÷òî c cj w j� , ãäå w j�{ , , , }1 2 � . Àíàëîãè÷íî ýëåìåíò j 1 ìîã áûòü çàäåéñòâîâàí â òðàíñïîçèöèÿõ òîëüêî ñ ïîðîæäàþùèìè ýëåìåíòàìè, êîòîðûå áîëüøå åãî, è ñîîòâåòñòâîâàòü êîýôôèöè- åíòó c j u òàêîìó, ÷òî c cj j u 1 , ãäå u n j� �{ , , , }1 2 � . Òîãäà äëÿ âñåõ ðàññìîò- ðåííûõ âûøå êîýôôèöèåíòîâ ñïðàâåäëèâî ñîîòíîøåíèå c c ca j w j� � � c c cj j u b1 , ÷òî ïðîòèâîðå÷èò èñõîäíîìó ïðåäïîëîæåíèþ c ca b� è äîêàçûâàåò óòâåðæäåíèå. Îñíîâûâàÿñü íà ëåììàõ 4 è 5, ìîæíî ñôîðìóëèðîâàòü ñëåäóþùåå óòâåðæäå- íèå îá îöåíêå ìèíèìóìà ëèíåéíîé ôóíêöèè íà öèêëè÷åñêèõ ïåðåñòàíîâêàõ. Ïóñòü èçâåñòíà òî÷êà ìèíèìóìà ôóíêöèè L p( ) íà ìíîæåñòâå ïåðåñòàíîâîê Pn : p Pn* � , p c p p P j j j n n * min� � � arg 1 , è åãî öèêëè÷åñêàÿ ñòðóêòóðà ñîñòîèò èç k öèê- ëîâ. Ïóñòü � — ìíîæåñòâî âñåõ �rm r mc c� �\| \| , r m Jn, � . Óïîðÿäî÷èì ýëåìåíòû ìíîæåñòâà � ïî âîçðàñòàíèþ: � � �1 2� �� N , ãäå N Cn� 2 , è îáîçíà÷èì �i i k � 1 ñóììó k ïåðâûõ ýëåìåíòîâ èç óïîðÿäî÷åííûõ ýëåìåíòîâ � � �1 2� � �� N . Ïóñòü òàêæå p PC n C* � — òî÷êà ìèíèìóìà ôóíêöèè L p( ) íà ìíîæåñòâå öèêëè- ÷åñêèõ ïåðåñòàíîâîê: p c pC p P j j j n n C * min� � � arg 1 . Óòâåðæäåíèå 2. Äëÿ ìèíèìóìà ëèíåéíîé ôóíêöèè L p( ) âèäà (2) íà ìíîæå- ñòâå öèêëè÷åñêèõ ïåðåñòàíîâîê Pn C ñïðàâåäëèâà ñëåäóþùàÿ îöåíêà: min ( ) ( ) p P i i k n C L p L p � � � 1 . Äîêàçàòåëüñòâî. Åñëè ïåðåñòàíîâêà p Pn � , p c p p P i i i n n * min� � � arg 1 , ñîñòîèò èç k öèêëîâ, òî äëÿ òîãî ÷òîáû èç p* ïîëó÷èòü öèêëè÷åñêóþ ïåðåñòàíîâêó, íåîá- õîäèìî ïðèìåíèòü ìèíèìóì k òðàíñïîçèöèé ñîåäèíåíèÿ âèäà (1). Ñîãëàñíî ëåììàì 4 è 5 âñå k òðàíñïîçèöèé áóäóò óâåëè÷èâàòü çíà÷åíèå öå- ëåâîé ôóíêöèè, íî ëþáàÿ �rm r mc c� �\| \|, r m Jn, � , ó÷àñòâóåò â óâåëè÷åíèè òîëüêî îäèí ðàç. Ñëåäîâàòåëüíî, åñëè áóäóò âûáðàíû k ìèíèìàëüíûõ çíà÷åíèé èç âñåãî ìíîæåñòâà � , òî èõ ñóììà áóäåò ìèíèìàëüíûì çíà÷åíèåì, íà êîòîðîå íåîáõîäèìî áóäåò óâåëè÷èòü p Pn* � . Ýòî äîêàçûâàåò ñïðàâåäëèâîñòü îöåíêè. ÏÐÈÌÅÍÅÍÈÅ ÊÎÌÏÎÇÈÖÈÈ ÒÐÀÍÑÏÎÇÈÖÈÉ ÄËß ÐÅØÅÍÈß ÇÀÄÀ×È ÎÏÒÈÌÈÇÀÖÈÈ ËÈÍÅÉÍÎÉ ÔÓÍÊÖÈÈ ÍÀ ÌÍÎÆÅÑÒÂÅ ÖÈÊËÈ×ÅÑÊÈÕ ÏÅÐÅÑÒÀÍÎÂÎÊ Äîêàçàííûå óòâåðæäåíèÿ ñîñòàâëÿþò îñíîâó ñëåäóþùåé ñòðàòåãèè ðåøåíèÿ çàäà÷ âèäà (2), (3) è (4), (5). 1. Íàõîæäåíèå p Pn* � òàêîãî, ÷òî p c p p P i i i n n * min� � � arg 1 . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 87 2. Åñëè p Pn C* � , òî ðåøåíèå çàäà÷è (2), (3) íàéäåíî. Èíà÷å ðàçáèåíèå ïåðå- ñòàíîâêè p Pn* � íà ïðîèçâåäåíèå öèêëîâ. Ïîäñ÷åò k — êîëè÷åñòâà öèêëîâ, èç êîòîðûõ ñîñòîèò èñõîäíàÿ ïåðåñòàíîâêà. 3. Âûáîð èç âñåõ âîçìîæíûõ n �1 òðàíñïîçèöèè âèäà (1) k �1 òðàíñïîçèöèþ ñîåäèíåíèÿ òàêèõ, ÷òîáû ñ èõ ïîìîùüþ ìîæíî áûëî îáúåäèíèòü âñå k öèêëîâ. 4. Ïîäñ÷åò êîëè÷åñòâà M pk� \| ( )\|� 1 ðàçëè÷íûõ ïåðåñòàíîâîê, êîòîðûå ìîæíî ñîçäàòü ñ ïîìîùüþ êîìïîçèöèè �k�1, ñîåäèíÿþùåé k �1 òðàíñïîçèöèþ ñîãëàñíî óòâåðæäåíèþ 1. 5. Ãåíåðàöèÿ ïåðåñòàíîâîê ïóòåì ïðèìåíåíèÿ ê ïåðåñòàíîâêå p Pn � êîìïî- çèöèè �k�1 , ó÷èòûâàÿ ñîîòíîøåíèå ïåðåñåêàþùèõñÿ è íåïåðåñåêàþùèõñÿ òðàíñïîçèöèé â êîìïîçèöèè ñîãëàñíî óòâåðæäåíèþ 1. 6. Ïîäñ÷åò çíà÷åíèé ôóíêöèè öåëè ñîãëàñíî ëåììàì 4 è 5 íà âñåõ ïîðîæäåí- íûõ â ï. 5 ïåðåñòàíîâêàõ. Ïåðåñòàíîâêà ñ ìèíèìàëüíûì çíà÷åíèåì öåëåâîé ôóíêöèè ïðèíèìàåòñÿ êàê ïðèáëèæåííîå ðåøåíèå èñõîäíîé çàäà÷è. 7. Îöåíêà ïîëó÷åííîãî ðåøåíèÿ, îñíîâàííàÿ íà óòâåðæäåíèè 2. Èçëîæåííàÿ ñòðàòåãèÿ îïòèìèçàöèè ëèíåéíûõ ôóíêöèé íà öèêëè÷åñêèõ ïå- ðåñòàíîâêàõ áåç îãðàíè÷åíèé ðåàëèçîâàíà ïðîãðàììíî, ïðîâåäåíû âû÷èñëèòåëü- íûå ýêñïåðèìåíòû. Ñëó÷àéíûì îáðàçîì â èíòåðâàëå [ ; ]�200 200 ãåíåðèðîâàëèñü êîýôôèöèåíòû ôóíêöèè öåëè çàäà÷. Ýêñïåðèìåíòû ïðîâîäèëèñü çà äâà ýòàïà. Íà ïåðâîì ýòàïå ðåøàëèñü çàäà÷è ðàçìåðíîñòè n äî 8 ïåðåìåííûõ, èõ ðåøåíèÿ ñðàâ- íèâàëèñü ñ ðåøåíèÿìè, ïîëó÷åííûìè ïîëíûì ïåðåáîðîì. Â ðàìêàõ êàæäîé ðàç- ìåðíîñòè áûëè ðàññ÷èòàíû ñðåäíèå çíà÷åíèÿ êîëè÷åñòâà öèêëîâ k â ïåðåñòàíîâ- êå p Pn* � è ñðåäíÿÿ ìîùíîñòü M ìíîæåñòâà ïîðîæäàåìûõ öèêëè÷åñêèõ ïåðå- ñòàíîâîê. Ñðåäíåå âðåìÿ ðåøåíèÿ çàäà÷ â ðàìêàõ êàæäîé ðàçìåðíîñòè îáîçíà÷èì T . Ïîëó÷åííûå ðåçóëüòàòû ïðåäñòàâëåíû â òàáë. 1. Íà âòîðîì ýòàïå ðåøàëèñü çàäà÷è áîëüøåé ðàçìåðíîñòè. Äëÿ êàæäîé ðàç- ìåðíîñòè áûëî ðåøåíî 20 çàäà÷ ñî ñëó÷àéíûìè èñõîäíûìè äàííûìè. Íà îñíîâàíèè óòâåðæäåíèÿ 2 ïîëó÷åííûå ïðèáëèæåííûå ðåøåíèÿ çàäà- ÷è (2), (3) áûëè îöåíåíû ñëåäóþùèì îáðàçîì. Äëÿ êàæäîé çàäà÷è â ðàìêàõ îä- íîé ðàçìåðíîñòè ýëåìåíòû ìíîæåñòâà � áûëè óïîðÿäî÷åíû ïî âîçðàñòàíèþ: � � �1 2� � �� N è ïîëó÷åíî çíà÷åíèå �i i k � 1 , ïîñëå ÷åãî â ðàìêàõ îäíîé ðàçìåð- íîñòè áûëî âû÷èñëåíî ñðåäíåå çíà÷åíèå ýòèõ ñóìì: AVG i i k A� � � � � � � � � � � 1 � . Âû÷èñ- ëÿëàñü ðàçíîñòü ìåæäó ìèíèìóìîì ôóíêöèè íà ïåðåñòàíîâêàõ è ïîëó÷åííûì ïðèáëèæåííûì ðåøåíèåì çàäà÷è (2), (3) L p L pC( * ) ( )� äëÿ êàæäîé çàäà÷è è áûëî ïîñ÷èòàíî ñðåäíåå îò âñåõ ýòèõ çíà÷åíèé â ðàìêàõ êàæäîé ðàçìåðíîñòè: AVG L p L p LC A( ( ) ( *))� � . Âåëè÷èíû � A è LA ïîä÷èíÿþòñÿ ñëåäóþùåìó íåðà- âåíñòâó: � A AL� , ÷òî ïîäòâåðæäàåòñÿ ïðèâåäåííûìè äàííûìè. Ïîëó÷åííûå ðå- çóëüòàòû ïðåäñòàâëåíû â òàáë. 2. 88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 Ò à á ë è ö à 1 ×èñëî ïåðåìåííûõ, n ×èñëî ñîâïàäàþùèõ ðåøåíèé ×èëî öèêëîâ, k Ìîùíîñòü, M T , ñåê 3 20 1,9 0,9 0,00175 4 19 2,2 1,1 0,00490 5 19 2,1 0,95 0,00945 6 19 2,2 1 0,01855 7 17 2,35 1,05 0,02945 8 20 2,85 1,3 0,05075 Ðåçóëüòàòû ýêñïåðèìåíòîâ ñðàâíèâàëèñü ñ ðåçóëüòàòàìè ðåøåíèÿ çàäà- ÷è (2), (3) ìåòîäîì âåòâåé è ãðàíèö [10]. Âû÷èñëèòåëüíûå ýêñïåðèìåíòû ïîêàçà- ëè ìåíüøèé ðîñò âðåìåíè ðàáîòû àëãîðèòìà ïðè çíà÷èòåëüíîì ðîñòå ðàçìåðíî- ñòè çàäà÷ ïî ñðàâíåíèþ ñ ðåøåíèåì äàííîé çàäà÷è ìåòîäîì âåòâåé è ãðàíèö. ÇÀÊËÞ×ÅÍÈÅ Â äàííîé ñòàòüå ïðåäëîæåíà ñòðàòåãèÿ ðåøåíèÿ çàäà÷è îïòèìèçàöèè ëèíåéíîé ôóíêöèè íà ìíîæåñòâå öèêëè÷åñêèõ ïåðåñòàíîâîê íà îñíîâå ñâîéñòâ òðàíñïî- çèöèé ñïåöèàëüíîãî âèäà. Èññëåäîâàíû ñâîéñòâà êëàññà òðàíñïîçèöèé, ñîãëàñíî êîòîðûì äàííûå òðàíñ- ïîçèöèè ñîîòâåòñòâóþò êðèòåðèþ ñìåæíîñòè â ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå. Èññëåäîâàíèå ýòèõ ñâîéñòâ ïîçâîëèëî ñôîðìóëèðîâàòü è äîêàçàòü ðÿä óòâåðæäå- íèé îòíîñèòåëüíî âëèÿíèÿ äàííûõ òðàíñïîçèöèé íà ïðîèçâîëüíóþ ïåðåñòàíîâêó. Äîêàçàíû ñëåäóþùèå óòâåðæäåíèÿ: — êîëè÷åñòâî ðàçëè÷íûõ ïåðåñòàíîâîê, êîòîðûå ìîæíî ïîëó÷èòü, ïðèìåíÿÿ çàäàííóþ êîìïîçèöèþ òðàíñïîçèöèé ê íåêîòîðîé ïåðåñòàíîâêå, åñëè òðàíñïîçè- öèè ìîãóò ñëåäîâàòü â ðàçëè÷íîì ïîðÿäêå; — ðàçíûå ïîñëåäîâàòåëüíîñòè òðàíñïîçèöèé, êîòîðûå â çàäàííîé êîìïîçè- öèè ïðè ïðèìåíåíèè ê íåêîòîðîé ïåðåñòàíîâêå ïðèâîäÿò ê îäíîé ðåçóëüòèðóþ- ùåé ïåðåñòàíîâêå. Äëÿ ïðèáëèæåííîãî ðåøåíèÿ, ïîëó÷åííîãî ñ ïîìîùüþ îïèñàííîé ñòðàòå- ãèè, îáîñíîâàíà îöåíêà, êîòîðàÿ ñòðîèòñÿ íà îñíîâàíèè ìèíèìóìà çàäàííîé ëè- íåéíîé ôóíêöèè íà ìíîæåñòâå ïåðåñòàíîâîê è óïîðÿäî÷åííûõ ðàçíîñòåé êîýô- ôèöèåíòîâ äàííîé ôóíêöèè. Ïðåäëîæåííàÿ ñòðàòåãèÿ ðåàëèçîâàíà ïðîãðàììíî è ïðîòåñòèðîâàíà íà çàäà÷àõ ðàçëè÷íîé ðàçìåðíîñòè ñ èñõîäíûìè äàííûìè, ãåíåðèðóåìûìè ñëó÷àéíûì îáðàçîì. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ãðåáåííèê È.Â., Þð÷åíêî Ë.Þ. Óïîðÿäî÷åíèå ïåðåñòàíîâîê ïðè ðåøåíèè çàäà÷ êîìáèíà- òîðíîé îïòèìèçàöèè ñ ëèíåéíîé öåëåâîé ôóíêöèåé. Ñèñòåìè îáðîáêè ³íôîðìàö³¿. 2007. Âèï. 8 (66). Ñ. 139–142. 2. Åìåëè÷åâ Â.À., Êîâàëåâ Ì.Ì., Êðàâöîâ Ì.Ê. Ìíîãîãðàííèêè, ãðàôû, îïòèìèçàöèÿ. Ìîñêâà: Íàóêà, 1981. 344 ñ. 3. Ñòîÿí Þ.Ã., ßêîâëåâ Ñ.Â. Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåîìåòðè÷åñ- êîãî ïðîåêòèðîâàíèÿ. Êèåâ: Íàóê. äóìêà, 1986. 268 ñ. 4. Ãðåáåííèê È.Â., Ïàíêðàòîâ À.Â., ×óãàé À.Ì., Áàðàíîâ À.Â. Óïàêîâêà n-ìåðíûõ ïàðàëëåëåïè- ïåäîâ ñ âîçìîæíîñòüþ èçìåíåíèÿ èõ îðòîãîíàëüíîé îðèåíòàöèè â n-ìåðíîì ïàðàëëåëåïèïåäå. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2010. ¹ 5. Ñ. 122–131. 5. Ñòåíëè Ð. Ïåðå÷èñëèòåëüíàÿ êîìáèíàòîðèêà. Ïåð. ñ àíãë. Ìîñêâà: Ìèð, 1990. 440 ñ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 89 Ò à á ë è ö à 2 ×èñëî çàäà÷, n � A L A ×èñëî öèêëîâ, k Ìîùíîñòü, M T , ñåê 20 4,9 5,1 3,5 1,4 0.91 30 2,6 2,7 3,4 1 2.31 40 2,5 2,5 4,3 1 9.98 50 1,6 1,6 3,9 1 11.54 60 0,7 0,7 3,9 1 20.74 70 1,2 1,2 5,6 1,3 90.75 80 2 2,05 5,05 1,1 105.42 100 2,8 2,8 5,8 1,1 235.77 6. Ñòîÿí Þ.Ã., ªìåöü Î.Î. Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. Êè¿â: ²í-ò ñèñ- òåìíèõ äîñë³äæåíü îñâ³òè, 1993. 188 ñ. 7. Ñåìåíîâà Í.Â., Êîëº÷ê³íà Ë.Ì. Âåêòîðí³ çàäà÷³ äèñêðåòíî¿ îïòèì³çàö³¿ íà êîìá³íàòîðíèõ ìíî- æèíàõ: ìåòîäè äîñë³äæåííÿ òà ðîçâ’ÿçàííÿ. Êè¿â: Íàóê. äóìêà, 2009. 266 c. 8. B�na M. Combinatorics of permutations. Boca Raton; London; New York: Chapman & Hall/CRC, 2004. 337 c. 9. Stoyan Yu.G., Grebennik I.V. Description and generation of combinatorial sets having special characteristics. International Journal of Biomedical Soft Computing and Human Sciences, Special volume “Bilevel Programming, Optimization Methods, and Applications to Economics.” 2013. Vol. 18, N 1. P. 83–88. 10. Ãðåáåííèê È.Â., Ëèòâèíåíêî À.Ñ., Òèòîâà Î.Ñ. Îïòèìèçàöèÿ ëèíåéíîé ôóíêöèè íà ìíîæåñòâå öèêëè÷åñêèõ ïåðåñòàíîâîê. Áèîíèêà èíòåëëåêòà. 2012. ¹ 2 (79). C. 8–12. 11. Èñà÷åíêî Þ.À. Ïðèìåíåíèå ïîëèýäðàëüíîãî ïîäõîäà ê çàäà÷å íà öèêëè÷åñêèõ ïåðåñòàíîâêàõ. Ñîâðåìåííûå êîìïüþòåðíûå èíôîðìàöèîííûå òåõíîëîãèè. T. 2. Ãðîäíî: ÃðÃÓ, 2008. C. 203–206. 12. Ãðåáåííèê È.Â., ×åðíàÿ Î.Ñ. Âëèÿíèå íåêîòîðûõ òðàíñïîçèöèé íà öèêëè÷åñêóþ ñòðóêòóðó ïåðåñòàíîâîê. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2015. ¹ 6. C. 128–136. 13. Grebennik I., Chorna O. Elements transpositions and their impact on the cyclic structure of permutations. ECONTECHMOD: An International Quarterly Journal on Economics of Technology and Modelling Processes. 2015. Vol. 4, N 3. 33–38. 14. Ñòîÿí Þ.Ã., ßêîâëåâ Ñ.Â. Ñâîéñòâà âûïóêëûõ ôóíêöèé íà ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå. ÄÀÍ ÓÑÑÐ. Ñåð. À. 1988. ¹ 3. C. 238–240. 15. Âåðåùàãèí Í. Ê., Øåíü À. Íà÷àëà òåîðèè ìíîæåñòâ. ×. 1. Ëåêöèè ïî ìàòåìàòè÷åñêîé ëîãèêå è òåîðèè àëãîðèòìîâ. 2-å èçä. Ìîñêâà: ÌÖÍÌÎ, 2002. 128 ñ. Íàä³éøëà äî ðåäàêö³¿ 07.07.2016 ².Â. Ãðåáåíí³ê, Î.Ñ. ×îðíà ÑÏÅÖ²ÀËÜÍ² ÒÐÀÍÑÏÎÇÈÖ²¯ ÅËÅÌÅÍÒ²Â ÏÅÐÅÑÒÀÍÎÂÎÊ ² ÂËÀÑÒÈÂÎÑÒ² ÊÎÌÏÎÇÈÖ²¯ Àíîòàö³ÿ. Çàïðîïîíîâàíî ñòðàòåã³þ ðîçâ’ÿçàííÿ çàäà÷³ îïòèì³çàö³¿ ë³í³éíî¿ ôóíêö³¿ íà ìíîæèí³ öèêë³÷íèõ ïåðåñòàíîâîê íà îñíîâ³ âëàñòèâîñòåé òðàíñ- ïîçèö³é ñïåö³àëüíîãî âèäó. Äîñë³äæåíî âëàñòèâîñò³ ñïåö³àëüíîãî êëàñó òðàíñïîçèö³é, äîâåäåíî òâåðäæåííÿ ïðî âïëèâ êîìïîçèö³é òàêèõ òðàíñïî- çèö³é íà äîâ³ëüíó ïåðåñòàíîâêó. Äëÿ íàáëèæåíîãî ðîçâ’ÿçêó, îòðèìàíîãî çà äîïîìîãîþ îïèñàíî¿ ñòðàòåã³¿, îáãðóíòîâàíî îö³íêó. Êëþ÷îâ³ ñëîâà: êîìá³íàòîðíà îïòèì³çàö³ÿ, ë³í³éíà ôóíêö³ÿ, ïåðåñòàíîâêè, òðàíñïîçèö³¿, öèêë³÷í³ ïåðåñòàíîâêè. I.V. Grebennik, O.S. Chorna SPECIAL TRANSPOSITIONS OF PERMUTATIONS ELEMENTS AND PROPERTIES OF THEIR COMPOSITION Abstract. In this paper, we propose a strategy for solving the problem of optimization of a linear function on the set of cyclic permutations. The strategy is based on the properties of the transpositions of a special kind. The properties of this class of transpositions are investigated. Assertions about the impact of compositions of such transpositions on an arbitrary permutation are proved. For the approximate solutions obtained using the above strategy, estimation is substantiated. Keywords: combinatorial optimization, linear function, permutations, transposi- tions, cyclic permutations. Ãðåáåííèê Èãîðü Âàëåðèåâè÷, äîêòîð òåõí. íàóê, ïðîôåññîð, çàâåäóþùèé êàôåäðîé Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà ðàäèîýëåêòðîíèêè, e-mail: igorgrebennik@gmail.com. ×åðíàÿ Îëüãà Ñåðãååâíà, àññèñòåíò êàôåäðû Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà ðàäèîýëåêòðîíèêè, e-mail: titovaolga90@gmail.com. 90 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1

Специальные транспозиции элементов перестановок и свойства композиции

Institution

Ähnliche Einträge