Подклассы разрешимых задач из классов задач комбинаторной оптимизации
Наведено огляд відомих підкласів розв’язних задач із класів комбінаторної оптимізації. Для розв’язних задач комівояжера, розміщення об’єктів на заданій поверхні, задачі про призначення, кластеризації проведено аналіз зміни значень цільової функції на заданому упорядкуванні комбінаторних конфігурацій...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/44346 |
| 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: | Подклассы разрешимых задач из классов задач комбинаторной оптимизации / Н.К. Тимофеева // Кибернетика и системный анализ. — 2009. — № 2. — С. 97-105. — Бібліогр.: 56 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44346 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-443462013-05-30T03:03:14Z Подклассы разрешимых задач из классов задач комбинаторной оптимизации Тимофеева, Н.К. Системный анализ Наведено огляд відомих підкласів розв’язних задач із класів комбінаторної оптимізації. Для розв’язних задач комівояжера, розміщення об’єктів на заданій поверхні, задачі про призначення, кластеризації проведено аналіз зміни значень цільової функції на заданому упорядкуванні комбінаторних конфігурацій. The well-known subclasses of solvable problems from the classes of combinatorial optimization are reviewed. For solvable problems such as a traveling salesman problem, location problem, assignment problem, and clustering problem, the changes of values of the objective function on the given organization of combinatorial configurations is analyzed. 2009 Article Подклассы разрешимых задач из классов задач комбинаторной оптимизации / Н.К. Тимофеева // Кибернетика и системный анализ. — 2009. — № 2. — С. 97-105. — Бібліогр.: 56 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44346 519.11.176 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 |
2009 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44346 |
| citation_txt |
Подклассы разрешимых задач из классов задач комбинаторной оптимизации / Н.К. Тимофеева // Кибернетика и системный анализ. — 2009. — № 2. — С. 97-105. — Бібліогр.: 56 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT timofeevank podklassyrazrešimyhzadačizklassovzadačkombinatornojoptimizacii |
| first_indexed |
2025-07-04T02:46:29Z |
| last_indexed |
2025-07-04T02:46:29Z |
| _version_ |
1836682774975610880 |
| fulltext |
ÓÄÊ 519.11.176
Í.Ê. ÒÈÌÎÔÅÅÂÀ
ÏÎÄÊËÀÑÑÛ ÐÀÇÐÅØÈÌÛÕ ÇÀÄÀ×
ÈÇ ÊËÀÑÑΠÇÀÄÀ× ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: ðàçðåøèìûå çàäà÷è, êîìáèíàòîðíàÿ îïòèìèçàöèÿ, êîìáèíà-
òîðíàÿ êîíôèãóðàöèÿ, öåëåâàÿ è êîìáèíàòîðíàÿ ôóíêöèè .
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåé ðàáîòå ïðîâîäèòñÿ îáçîð èçâåñòíûõ è íîâûõ (ïîëó÷åííûõ àâòîðîì)
ïîäêëàññîâ ðàçðåøèìûõ çàäà÷ èç êëàññîâ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè.
Ïîä ðàçðåøèìûìè çàäà÷àìè ïîäðàçóìåâàåòñÿ îïðåäåëåííûé ïîäêëàññ çàäà÷, äëÿ
êîòîðîãî èçâåñòåí àíàëèòè÷åñêèé ìåòîä íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ áåç
ïåðåáîðà âàðèàíòîâ. Ðàññìîòðåíû ïîäêëàññû ðàçðåøèìûõ çàäà÷ èç êëàññîâ
êîìáèíàòîðíîé îïòèìèçàöèè, êîòîðûå ÿâëÿþòñÿ ìàòåìàòè÷åñêèìè ìîäåëÿìè òà-
êèõ ïðèêëàäíûõ çàäà÷: êîììèâîÿæåðà, î íàçíà÷åíèÿõ, ðàçìåùåíèÿ îáúåêòîâ íà
çàäàííîé ïîâåðõíîñòè, êëàñòåðèçàöèè.
Ïðèêëàäíûå çàäà÷è, êîòîðûå îòíîñÿòñÿ ê êëàññàì çàäà÷ êîìáèíàòîðíîé îïòè-
ìèçàöèè, äîâîëüíî ÷àñòî èìåþò áîëüøóþ ðàçìåðíîñòü. Íàïðèìåð, ïðè ïðîåêòèðî-
âàíèè ñâåðõáîëüøèõ èíòåãðàëüíûõ ìèêðîñõåì íåîáõîäèìî ðàçìåùàòü äåñÿòêè òû-
ñÿ÷ ìîäóëåé. Èçâåñòíî, ÷òî ñ âîçðàñòàíèåì ðàçìåðíîñòåé ýòèõ çàäà÷ ïðàêòè÷åñêè
íåâîçìîæíî íàõîäèòü îïòèìàëüíîå ðåøåíèå ìåòîäàìè, èñïîëüçóþùèìè ïåðåáîð
âàðèàíòîâ, ïîýòîìó âîçíèêàåò ïðîáëåìà ðàçðàáîòêè ïðèáëèæåííûõ ïîëèíîìèàëü-
íûõ àëãîðèòìîâ äëÿ èõ ðåøåíèÿ.
Äëÿ ðåøåíèÿ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè ìîæíî âûäåëèòü äâà ïîäõîäà:
à) ìåòîäû è àëãîðèòìû, îñíîâàííûå íà ÷àñòè÷íîì ïåðåáîðå âàðèàíòîâ [1–8]; á) ìåòîäû
è àëãîðèòìû, ñâÿçàííûå ñ ðàñïîçíàâàíèåì ñòðóêòóðû âõîäíîé èíôîðìàöèè.
Êî âòîðîìó ïîäõîäó îòíîñÿòñÿ ðàáîòû ïî íàõîæäåíèþ ïîäêëàññîâ ðàçðåøèìûõ
çàäà÷ è ðàçðàáîòêå àëãîðèòìîâ ðàñïîçíàâàíèÿ ñîîòâåòñòâóþùåé ýòèì ïîäêëàññàì
ñòðóêòóðû âõîäíîé èíôîðìàöèè [9–37]. Èññëåäîâàíèå ýòèõ ñëó÷àåâ ïîëîæèëî íà÷à-
ëî íàó÷íîìó íàïðàâëåíèþ, êîòîðîå çàêëþ÷àåòñÿ â íàõîæäåíèè îïòèìàëüíîãî ðåøå-
íèÿ áåç ïåðåáîðà âàðèàíòîâ. Àíàëèç êëàññîâ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè ïî-
çâîëÿåò âûÿâèòü èõ õàðàêòåðíûå ñâîéñòâà, îáîáùèòü è ðàçâèòü ýòî íàïðàâëåíèå.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè, êàê ïðàâèëî, çàäàþòñÿ íà îäíîì èëè íå-
ñêîëüêèõ ìíîæåñòâàõ, íàïðèìåð A a an� { , , }1 � è B b bn� { , , }~1 � , ýëåìåíòû
êîòîðûõ èìåþò ëþáóþ ïðèðîäó. Ïîëîæèì n n� ~. Íàçîâåì ýòè ìíîæåñòâà áàçî-
âûìè. Èìååò ìåñòî äâà òèïà çàäà÷. Â ïåðâîì òèïå êàæäîå èç ýòèõ ìíîæåñòâ A
è B ìîæíî ïðåäñòàâèòü â âèäå ãðàôà, âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ ýëåìåíòû
çàäàííîãî ìíîæåñòâà, à êàæäîìó ðåáðó ñîîòâåòñòâóåò ÷èñëî (âåñ ðåáðà) c Rst �
(R — ìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë), ò.å. ìåæäó ýëåìåíòàìè as, a At � (èëè
a As � , b Bt � ) ñóùåñòâóþò ñâÿçè, ÷èñëîâîå çíà÷åíèå êîòîðûõ íàçûâàþò âåñàìè.
Âåëè÷èíû cst íàçîâåì âõîäíûìè äàííûìè è ïðåäñòàâèì èõ ìàòðèöàìè [38]. Âî
âòîðîì òèïå çàäà÷ ìåæäó ýëåìåíòàìè çàäàííûõ ìíîæåñòâ ñâÿçåé íå ñóùåñòâóåò,
à âåñàìè âûñòóïàþò ÷èñëà � j R� , j n�{ , , }1� , êîòîðûì â ñîîòâåòñòâèå
ïîñòàâëåíî íåêîòîðîå ñâîéñòâî ýòèõ ýëåìåíòîâ.
 îáoèõ òèïàõ çàäà÷ èç ýëåìåíòîâ îäíîãî èç çàäàííûõ ìíîæåñòâ, íàïðèìåð
a At � , îáðàçóåòñÿ êîìáèíàòîðíîå ìíîæåñòâî W — ñîâîêóïíîñòü êîìáèíàòîðíûõ
êîíôèãóðàöèé íåêîòîðîãî îäíîãî òèïà (ïåðåñòàíîâêè, âûáîðêè ðàçíûõ òèïîâ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 97
© Í.Ê. Òèìîôååâà, 2009
ðàçáèåíèÿ n-ýëåìåíòíîãî ìíîæåñòâà íà ïîäìíîæåñòâà è äð.). Íà ýëåìåíòàõ w W�
ââîäèòñÿ öåëåâàÿ ôóíêöèÿ F w( ) . Íåîáõîäèìî íàéòè ýëåìåíò w* ìíîæåñòâà W, äëÿ
êîòîðîãî öåëåâàÿ ôóíêöèÿ F w( )* ïðèíèìàåò ýêñòðåìàëüíîå çíà÷åíèå (ìèíèìóì
èëè ìàêñèìóì) ïðè âûïîëíåíèè çàäàííûõ îãðàíè÷åíèé: F w F w
w W W
( ) ( )�
� �
� extr
0
, ãäå
extr � {min , max}, W 0 — ïîäìíîæåñòâî, îïðåäåëÿåìîå îãðàíè÷åíèÿìè çàäà÷è. Ýëå-
ìåíò w W W� � �0 è åñòü îïòèìàëüíîå ðåøåíèå çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè.
Ýëåìåíòû âõîäíûõ äàííûõ êëàññà çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè, çàäàí-
íûå äâóìÿ ìàòðèöàìè, ïðåäñòàâèì êîíå÷íûìè ïîñëåäîâàòåëüíîñòÿìè (ôóíêöèÿìè
íàòóðàëüíîãî àðãóìåíòà, îäíà èç êîòîðûõ êîìáèíàòîðíàÿ). Ê ýòîìó êëàññó îòíîñÿò-
ñÿ òàêèå çàäà÷è: êîììèâîÿæåðà, çàäà÷à î íàçíà÷åíèÿõ, ðàçìåùåíèÿ îáúåêòîâ íà
çàäàííîé ïîâåðõíîñòè, êëàñòåðèçàöèÿ.
Ýëåìåíòû ìàòðèöû Q wk( ), êîòîðóþ íàçîâåì êîìáèíàòîðíîé, ñîîòâåòñòâóþò
çíà÷åíèþ âåñîâ ìåæäó as , at áàçîâîãî ìíîæåñòâà A , ãäå wk — àðãóìåíò öåëåâîé
ôóíêöèè — êîìáèíàòîðíàÿ êîíôèãóðàöèÿ, k q�{ , , }1 � — ïîðÿäêîâûé íîìåð wk
âî ìíîæåñòâå W, q — êîëè÷åñòâî wk â W. Ýëåìåíòû ìàòðèöû C ñîîòâåòñòâóþò
çíà÷åíèþ âåñîâ ìåæäó ýëåìåíòàìè bs, bt çàäàííîãî ìíîæåñòâà B èëè ðàâíÿþòñÿ
( , )0 1 , ãäå cst � 1 , åñëè as, at èìåþò ìåæäó ñîáîé ñâÿçè, è cst � 0 â ïðîòèâíîì
ñëó÷àå. Ýëåìåíòû ìàòðèöû C çàäàäèì ÷èñëîâîé ôóíêöèåé �( )j
m
1
, à Q w( )1 —
êîìáèíàòîðíîé �( ( ), )f j w
m1
1
, êîòîðàÿ èçìåíÿåòñÿ â çàâèñèìîñòè îò wk , ãäå
m n� 2 , w w Wk1, � . Ðàçìåùåíèå ýëåìåíòîâ ìàòðèö â ýòèõ ôóíêöèÿõ òàêîå: ñíà÷àëà
èäóò ýëåìåíòû ïåðâîé ñòðîêè, ïîòîì âòîðîé, òðåòüåé è ò.ä. Åñëè ìàòðèöû C è
Q w( )1 ñèììåòðè÷åñêèå, òî �( )j
m
1
è �( ( ), )f j wk m
1
ñîäåðæàò ïîñëåäîâàòåëüíî
ýëåìåíòû h íàääèàãîíàëåé ìàòðèöû ïåðâîé ñòðîêè, ïîòîì âòîðîé, òðåòüåé è ò.ä.,
h n� �{ , , }1 1� , à m n n� �( ) /1 2. Öåëåâóþ ôóíêöèþ çàïèøåì òàê:
F w f j w jk
j
j
m
k( ) ( ( ), ) ( )�
�
� � �
1
. (1)
Î ÏÎÄÕÎÄÅ Ê ÐÅØÅÍÈÞ ÇÀÄÀ× ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ,
ÎÑÍÎÂÀÍÍÎÌ ÍÀ ÐÀÑÏÎÇÍÀÂÀÍÈÈ ÑÒÐÓÊÒÓÐÛ ÂÕÎÄÍÛÕ ÄÀÍÍÛÕ
Íàä ñîçäàíèåì ìåòîäîâ, êîòîðûå ïîçâîëÿëè áû ïî ñòðóêòóðå âõîäíîé èíôîðìà-
öèè íàõîäèòü îïòèìàëüíîå ðåøåíèå çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè, ïðîâî-
äÿòñÿ èññëåäîâàíèÿ íå îäíî äåñÿòèëåòèå. Îäèí èç òàêèõ ïîäõîäîâ — ðàçðàáîòêà
ìåòîäîâ è àëãîðèòìîâ íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ ïî ñòðóêòóðå ìàòðèö,
êîòîðûìè çàäàþòñÿ âõîäíûå äàííûå. Åùå â 60-õ ãîäàõ ÕÕ ñò. äëÿ çàäà÷ êëàñ-
ñèôèêàöèè ðàçðàáàòûâàëèñü àëãîðèòìû ïåðåóïîðÿäî÷åíèÿ ïðîèçâîëüíîé ìàòðè-
öû òàêèì îáðàçîì, ÷òîáû çíà÷åíèÿ ïðèçíàêîâ, îïèñûâàþùèõ îäíîðîäíûå îáúåê-
òû, ðàçìåñòèëèñü â çàäàííîì ïîëå ìàòðèöû. Òàêîé àëãîðèòì îïèñàí â [9].
 ýòè æå ãîäû ïîÿâèëèñü ðàáîòû ïî âûäåëåíèþ ïîäêëàññîâ ðàçðåøèìûõ çàäà÷
èç êëàññîâ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè, â îñíîâíîì äëÿ çàäà÷è êîììèâîÿæå-
ðà. Ïóáëèêàöèé ïî ýòîìó ïîäõîäó íåìíîãî, íî ýòî íàïðàâëåíèå ïðîäîëæàåò ðàçâè-
âàòüñÿ è òðåáóåò îñîáîãî âíèìàíèÿ.
Ìåòîä áëèæàéøåãî ñîñåäà è «æàäíûé» àëãîðèòì òàêæå îñíîâàí íà ðàñïîçíàâàíèè
ñòðóêòóðû âõîäíûõ äàííûõ.  ðàñïîçíàâàíèè ðå÷åâûõ ñèãíàëîâ âî ìíîãèõ ïîäõîäàõ
ðåøåíèå ýòîé çàäà÷è ïðîâîäèòñÿ ïóòåì âûÿâëåíèÿ êîíôèãóðàöèè âõîäíîãî ñèãíàëà.
 ïîñëåäíåå âðåìÿ çíà÷èòåëüíî âîçðîñ èíòåðåñ ê ôðàêòàëüíûì ìíîæåñòâàì [39].
 ðàáîòàõ [40–42] ïðåäëàãàåòñÿ èñïîëüçîâàòü ôðàêòàëüíûå è ïðåäôðàêòàëüíûå ãðà-
ôû êàê èíñòðóìåíò ìîäåëèðîâàíèÿ ñòðóêòóðíîãî õàîñà (ñòðóêòóðà âõîäíûõ äàííûõ
â çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè — õàîòè÷åñêîé ïðèðîäû).  [40] äëÿ ðåøå-
íèÿ çàäà÷è î íàçíà÷åíèÿõ ðàçðàáîòàíû àëãîðèòìû ïîèñêà êîíêðåòíîé ñòðóêòóðû â
çàäà÷å î íàçíà÷åíèè ñ èñïîëüçîâàíèåì ñâîéñòâ ôðàêòàëüíûõ ìíîæåñòâ.
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
ÏÎÄÊËÀÑÑÛ ÐÀÇÐÅØÈÌÛÕ ÇÀÄÀ×
Îäíèì èç ïåðâûõ èññëåäîâàííûõ ðàçðåøèìûõ ñëó÷àåâ èç êëàññîâ çàäà÷ êîìáè-
íàòîðíîé îïòèìèçàöèè ÿâëÿþòñÿ äâà ìíîæåñòâà ïåðåñòàíîâîê ðàçíûõ óïîðÿäî÷å-
íèé, êîòîðûå àâòîðû íàçûâàþò ñèñòåìàìè ( )a è ( )b , è ÷àñòíûé ñëó÷àé áèëèíåé-
íîé ôîðìû (êâàäðàòè÷íîé çàäà÷è î íàçíà÷åíèÿõ) [43]. Äëÿ ñèñòåì ( )a è ( )b
îïðåäåëåíû ïåðåñòàíîâêè, äëÿ êîòîðûõ ab� äîñòèãàåò íàèáîëüøåãî èëè íàè-
ìåíüøåãî çíà÷åíèÿ. Èç êëàññà çàäà÷è êîììèâîÿæåðà áûë èññëåäîâàí òàê íàçûâà-
åìûé âûïóêëûé ñëó÷àé, êîãäà âñå òî÷êè â ïëîñêîñòè ðàñïîëîæåíû íà ãðàíèöå
èõ âûïóêëîé îáîëî÷êè [44].
 1957 ã. ðàçðåøèìûé ñëó÷àé äëÿ çàäà÷è êîììèâîÿæåðà îïèñàë Ô. Ñóïíèê [21].
Îí ðàññìîòðåë ñèììåòðè÷åñêóþ ìàòðèöó ðàçìåðíîñòè n n� ñ òàêèìè óñëîâèÿìè:
c c c cst rl sr tl
, c c c csl tr sr tl � , ãäå 1
� � �
s t r l n, è äîêàçàë, ÷òî äëÿ íåå
ìèíèìàëüíîå çíà÷åíèå öåëåâîé ôóíêöèè â çàäà÷å êîììèâîÿæåðà äîñòèãàåòñÿ äëÿ
ïåðåñòàíîâêè 1 3 5 7 8 6 4 2, , , , , , , ,� , êîòîðóþ íàçûâàþò ïèðàìèäàëüíûì òóðîì.
 1975 ã. Ê. Êàëüìàíñîí èññëåäîâàë ñèììåòðè÷åñêóþ ìàòðèöó ðàçìåðíîñòè
n n� , äëÿ êîòîðîé âûïîëíÿþòñÿ òàêèå óñëîâèÿ [20]:
c c c cst rl sr tl
, ãäå 1
� � �
s t r l n, (2)
c c c csl tr sr tl
, ãäå 1
� � �
s t r l n. (3)
Îí äîêàçàë, ÷òî äëÿ ýòîé ìàòðèöû ìèíèìàëüíîå çíà÷åíèå öåëåâîé ôóíêöèè â çà-
äà÷å êîììèâîÿæåðà äîñòèãàåòñÿ äëÿ ïåðåñòàíîâêè 1 2 3, , , ,� n (òóð Ìàñòåðà).
Ïî÷òè îäíîâðåìåííî ãëîáàëüíûé ìèíèìóì äëÿ ìàòðèöû, êîòîðàÿ çàäàåòñÿ
óñëîâèåì (2), íàøåë Â.Ì. Äåìèäåíêî [22]. Îí äîêàçàë, ÷òî äëÿ çàäà÷è êîììèâîÿæå-
ðà, âõîäíàÿ èíôîðìàöèÿ â êîòîðîé çàäàåòñÿ ìàòðèöåé ñ óñëîâèåì (2), ìèíèìàëüíîå
çíà÷åíèå öåëåâîé ôóíêöèè äîñòèãàåòñÿ äëÿ ïèðàìèäàëüíîãî òóðà (ïåðåñòàíîâêà
1 3 5 7 8 6 4 2, , , , , , , ,� ) [25, 26].
 [11] ïðåäëîæåíà ôîðìàëüíàÿ ïîñòàíîâêà çàäà÷è êîìáèíàòîðíîé îïòèìèçà-
öèè, àðãóìåíòîì öåëåâîé ôóíêöèè êîòîðîé ÿâëÿåòñÿ ïåðåñòàíîâêà. Â ýòîé ïîñòà-
íîâêå ýëåìåíòû ìàòðèö, êîòîðûìè çàäàåòñÿ âõîäíàÿ èíôîðìàöèÿ, ïðåäñòàâëåíû
â ëèíåéíîé ôîðìå (äâóìÿ ìíîæåñòâàìè { }� �1
� n è � � �1
� n }), à öåëåâàÿ ôóíê-
öèÿ çàäàíà êàê ñóììàðíîå ïðîèçâåäåíèå ýëåìåíòîâ ýòèõ ìíîæåñòâ, ïðè÷åì îäíî èç
íèõ ôóíêöèîíàëüíî çàâèñèò îò ïåðåñòàíîâêè. Àíàëîãè÷íóþ ôîðìàëüíóþ ïîñòàíîâ-
êó çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè ïðåäëîæèëè àâòîðû ðàáîòû [23].  [11, 13,
18, 23, 26–28, 33] èññëåäóåòñÿ ìàòðèöà ïðîèçâåäåíèé, ýëåìåíòû êîòîðîé ïðåäñòàâ-
ëåíû â ëèíåéíîé ôîðìå è ðàâíÿþòñÿ c j j j� � � , ãäå � � �1 2
� n è
� � �1 2� � �� n èëè � � �1 2
� n .
 ëèòåðàòóðå îïèñàíû ðàçðåøèìûå ñëó÷àè, êîòîðûå çàäàþòñÿ ìàòðèöàìè Ìîí-
æà ñ óñëîâèÿìè c c c cst rl sl rt
äëÿ âñåõ 1
�
s r m, 1
�
t l n. Âïåðâûå ýòè
óñëîâèÿ îïèñàë â 1781 ã. ôðàíöóçñêèé ìàòåìàòèê Ã. Ìîíæ [30].
Ðàçðåøèìûå ñëó÷àè äëÿ çàäà÷è êîììèâîÿæåðà îïèñàíû â ðàáîòàõ [12, 17, 33, 34].
 [17] èññëåäîâàíû èçâåñòíûå è ïðåäëîæåíû íîâûå ðàçðåøèìûå ñëó÷àè åâêëèäî-
âîé çàäà÷è êîììèâîÿæåðà, à òàêæå ðàçðàáîòàíû íîâûå ýâðèñòè÷åñêèå àëãîðèòìû
äëÿ ðàñïîçíàâàíèÿ ïåðåóïîðÿäî÷åííûõ ìàòðèö.
Íà ñåãîäíÿøíèé äåíü ó÷åíûå èçó÷àþò îïèñàííûå â ëèòåðàòóðå ðàçðåøèìûå
ñëó÷àè (ìàòðèöû Ñóïíèêà, Äåìèäåíêà, Êàëüìàíñîíà, Ìîíæà, Òåïëèöà) äëÿ çàäà÷è
êîììèâîÿæåðà, êâàäðàòè÷íîé çàäà÷è î íàçíà÷åíèÿõ [14–17, 19, 29, 31, 32, 35–37]
è ðàçðàáàòûâàþò íîâûå àëãîðèòìû ðàñïîçíàâàíèÿ ïåðåóïîðÿäî÷åííûõ ìàòðèö. Äëÿ
íàõîäæåíèÿ ïîäêëàññîâ ðàçðåøèìûõ çàäà÷ è îïðåäåëåíèÿ äëÿ íèõ îïòèìàëüíîãî
ðåøåíèÿ åùå íå ðàçðàáîòàíû îáùèå ìåòîäû, ýòîò ïðîöåññ íå îñíîâûâàåòñÿ íà
ñòðîãèõ ïðàâèëàõ è äîâîëüíî òðóäîåìêèé. Èçëîæåííûå â ëèòåðàòóðå ðåçóëüòàòû,
êîòîðûå êàñàþòñÿ âòîðîãî íàïðàâëåíèÿ, íå îõâàòûâàþò øèðîêîãî êëàññà çàäà÷
êîìáèíàòîðíîé îïòèìèçàöèè è íåäîñòàòî÷íû äëÿ âûÿâëåíèÿ ïðèñóùèõ èì îáùèõ
çàêîíîìåðíîñòåé. Ïðèâåäåííûå â ëèòåðàòóðå ðåçóëüòàòû òðåáóþò îáîáùåíèÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 99
Êàê ïîêàçûâàåò àíàëèç ìåòîäîâ è àëãîðèòìîâ, ïðè ðåøåíèè çàäà÷ êîìáèíà-
òîðíîé îïòèìèçàöèè ïîäõîäàìè, îñíîâàííûìè íà ïåðåáîðå âàðèàíòîâ, âîçíèêà-
åò îäíà è òà æå ïðîáëåìà, à èìåííî: âûäåëåíèå èç ìíîæåñòâà çíà÷åíèé öåëåâîé
ôóíêöèè ïîäìíîæåñòâà, êîòîðîå ñîäåðæèò îïòèìàëüíîå ðåøåíèå [1–8]. Â ðàáî-
òàõ [11, 22, 23, 25, 26, 45–47] àâòîðû äëÿ êîíêðåòíîãî ïîäêëàññà ðàçðåøèìûõ çàäà÷
ñ ó÷åòîì ñòðóêòóðû ïåðåñòàíîâîê âûäåëÿþò èõ ïîäìíîæåñòâî, ñîäåðæàùåå îïòè-
ìàëüíîå ðåøåíèå.
Íåñìîòðÿ íà òî, ÷òî ìåòîäû ðàçáèåíèÿ ìíîæåñòâà çíà÷åíèé öåëåâîé ôóíê-
öèè [1–8] èëè ïåðåñòàíîâîê [11, 22, 23, 25, 26, 45–47] íà ïîäìíîæåñòâà äëÿ ðàçíûõ
èíäèâèäóàëüíûõ çàäà÷ ðàçíûå è íå îñíîâàíû íà ñòðîãèõ äîêàçàòåëüñòâàõ, âîçíèêà-
åò âîïðîñ: ñ êàêèì ñâîéñòâîì ñâÿçàíî ýòî ðàçáèåíèå.
ÍÎÂÛÅ ÐÅÇÓËÜÒÀÒÛ Â ÈÇÓ×ÅÍÈÈ ÏÎÄÊËÀÑÑΠÐÀÇÐÅØÈÌÛÕ ÇÀÄÀ×
Êàê ïîêàçàíî â [48], â çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè çàêîíîìåðíîñòü èç-
ìåíåíèÿ çíà÷åíèé öåëåâîé ôóíêöèè çàâèñèò îò çàäàííîãî óïîðÿäî÷åíèÿ êîìáè-
íàòîðíûõ êîíôèãóðàöèé, à íà ïîäìíîæåñòâå èçîìîðôíûõ êîìáèíàòîðíûõ êîíôè-
ãóðàöèé ôóíêöèÿ öåëè èçìåíÿåòñÿ òàê, êàê è íà ìíîæåñòâå ïåðåñòàíîâîê (êîìáè-
íàòîðíûå êîíôèãóðàöèè, êîëè÷åñòâî ýëåìåíòîâ â êîòîðûõ îäèíàêîâîå, íàçûâàþòñÿ
èçîìîðôíûìè). Èñïîëüçóÿ ýòî ñâîéñòâî, ìîæíî ïîñòàâèòü çàäà÷ó îòñå÷åíèÿ íåýô-
ôåêòèâíûõ âàðèàíòîâ ïî-äðóãîìó: ïðîâåñòè ðàçáèåíèå íà ïîäìíîæåñòâà íå ìíî-
æåñòâà çíà÷åíèé öåëåâîé ôóíêöèè, à ìíîæåñòâî êîìáèíàòîðíûõ êîíôèãóðàöèé
(àðãóìåíòà), èñïîëüçóÿ íåçàâèñèìûå îò âõîäíûõ äàííûõ ïàðàìåòðû, íàïðèìåð ðàç-
íûå êîìáèíàöèè ýëåìåíòîâ ìàòðèöû. Äëÿ ïîëó÷åííîãî óïîðÿäî÷åíèÿ âûðàáîòàòü
ñòðàòåãèþ îïðåäåëåíèÿ çàêîíîìåðíîñòè èçìåíåíèÿ çíà÷åíèé öåëåâîé ôóíêöèè,
êîòîðàÿ îñíîâàíà íà ðàñïîçíàâàíèè ñòðóêòóðû âõîäíûõ äàííûõ.
Êàê ñëåäóåò èç âûðàæåíèÿ (1), äëÿ ôèêñèðîâàííîãî àðãóìåíòà âåëè÷èíà ïðîèçâåäå-
íèÿ çíà÷åíèé ôóíêöèè íàòóðàëüíîãî àðãóìåíòà è êîìáèíàòîðíîé ôóíêöèè çàâèñèò îò
êîìáèíàöèè ýëåìåíòîâ çàäàííûõ ìàòðèö. Ïîñëåäîâàòåëüíîñòü ýòèõ âåëè÷èí íàçîâåì âà-
ðèàíòîì ðåøåíèÿ çàäà÷è è îáîçíà÷èì åå u w l u w u w z Hk z k
z
k
u( , ) ( ( , ), , ( , ))
1 1 1� �� ,
ãäå Hu — èõ ìíîæåñòâî, à u w l f j w jl
k
j
k( , ) ( ( ), ) ( )� � � è �( )j � 1, åñëè �( ) { , }j � 0 1 ,
z — êîëè÷åñòâî çíà÷åíèé u w ll( , ) â u w lk z
( , )
1
. Ïî ñïîñîáó îáðàçîâàíèÿ âàðèàíòîâ ðå-
øåíèÿ çàäà÷è èõ ìíîæåñòâî ðàçäåëÿåòñÿ íà ïîäìíîæåñòâà.  ïåðâîì ïîäìíîæåñòâå
íàõîäÿòñÿ ïîñëåäîâàòåëüíîñòè, çíà÷åíèÿ êîòîðûõ âûáðàíû ñ ìàòðèöû, íà÷èíàÿ ñ ýëå-
ìåíòà, èìåþùåãî àäðåñ 1 ïåðâîé ñòðîêè ìàòðèöû, âî âòîðîì ïîäìíîæåñòâå — íà÷è-
íàÿ ñ ýëåìåíòà ïî àäðåñó 2 è ò.ä. Êîëè÷åñòâî òàêèõ ïîäìíîæåñòâ äëÿ ðàçíûõ çàäà÷ ðàç-
íîå. Ñîîòâåòñòâåííî, íà ïîäìíîæåñòâà ðàçäåëÿåòñÿ è ìíîæåñòâî êîìáèíàòîðíûõ êîí-
ôèãóðàöèé, êîòîðûå îáîçíà÷èì K K K
q1 2, , ,� � , q� — êîëè÷åñòâî òàêèõ
ïîäìíîæåñòâ. Íàïðèìåð, äëÿ çàäà÷è êîììèâîÿæåðà èíäåêñ 1 â K1 îçíà÷àåò, ÷òî äëÿ
w Kk � 1 âñå âàðèàíòû ðåøåíèÿ çàäà÷è u w lk z
( , )
1
ñîäåðæàò ýëåìåíò èç àäðåñà 1 ïåð-
âîé ñòðîêè ìàòðèöû Q w( )1 , èíäåêñ 2 â K 2 îçíà÷àåò, ÷òî âàðèàíòû ðåøåíèÿ ñîäåðæàò
ýëåìåíò èç àäðåñà 2, íî íå ñîäåðæàò èç àäðåñà 1 è ò.ä. Îáðàçîâàííûå ïîäìíîæåñòâà
ñîñòîÿò èç ìåíüøèõ ïîäìíîæåñòâ. Òàêîå óïîðÿäî÷åíèå ìíîæåñòâà êîìáèíàòîðíûõ
êîíôèãóðàöèé ïðîâîäèòñÿ ïî ïåðâîìó, âòîðîìó, òðåòüåìó è äðóãèõ çíà÷åíèÿõ
âàðèàíòîâ ðåøåíèÿ çàäà÷è è íå çàâèñèò îò âõîäíûõ äàííûõ.
Çíàÿ ïðàâèëà îáðàçîâàíèÿ âàðèàíòîâ ðåøåíèÿ çàäà÷è, äëÿ çàäà÷ êîììèâîÿæåðà,
ðàçìåùåíèÿ, êëàñòåðèçàöèè, çàäà÷è î íàçíà÷åíèÿõ ñ ðåãóëÿðíîé ñòðóêòóðîé âõîäíûõ
äàííûõ (ôóíêöèè íàòóðàëüíîãî àðãóìåíòà äèñêðåòíûå è èçìåíÿþòñÿ êàê ëèíåéíûå,
ïåðèîäè÷åñêèå, ìîíîòîííûå) íåñëîæíî óñòàíîâèòü, êàê èçìåíÿåòñÿ çíà÷åíèå öåëåâîé
ôóíêöèè íà çàäàííîì óïîðÿäî÷åíèè ïîäìíîæåñòâ K K K
q1 2, , ,� � [48–54]. Â îïèñàí-
íîé íèæå çàäà÷å î íàçíà÷åíèÿõ âõîäíûå äàííûå çàäàíû äâóìÿ íåñèììåòðè÷åñêèìè
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
ìàòðèöàìè, îäíà èç êîòîðûõ — ( , )0 1 -ìàòðèöà. Êîëè÷åñòâî ïîäìíîæåñòâ, íà êîòîðûå
ðàçáèâàåòñÿ ìíîæåñòâî ïåðåñòàíîâîê äëÿ ýòîé çàäà÷è, ðàâíÿåòñÿ n.  çàäà÷å ðàçìåùå-
íèÿ âõîäíûå äàííûå çàäàíû äâóìÿ ñèììåòðè÷åñêèìè ìàòðèöàìè, ýëåìåíòû êîòîðûõ
— äåéñòâèòåëüíûå ÷èñëà. Êîëè÷åñòâî ïîäìíîæåñòâ, íà êîòîðûå ðàçáèâàåòñÿ ìíîæåñ-
òâî ïåðåñòàíîâîê äëÿ ýòîé çàäà÷è, ðàâíÿåòñÿ m.  çàäà÷å êîììèâîÿæåðà âõîäíûå äàí-
íûå çàäàíû äâóìÿ ñèììåòðè÷åñêèìè ìàòðèöàìè, îäíà èç êîòîðûõ — ( , )0 1 -ìàòðèöà.
Êîëè÷åñòâî ïîäìíîæåñòâ ìíîæåñòâà ïåðåñòàíîâîê äëÿ ýòîé çàäà÷è ðàâíÿåòñÿ n � 2.
Ïðèâåäåì ñëåäóþùèå òåîðåìû, äîêàçàòåëüñòâà êîòîðûõ èçëîæåíû â [48–54].
Çàêîíîìåðíîñòü èçìåíåíèÿ êîìáèíàòîðíîé ôóíêöèè âî âñåõ ñëó÷àÿõ çàäàíà äëÿ
ïåðâîé ïåðåñòàíîâêè w W1 � . Öåëåâàÿ ôóíêöèÿ â ýòèõ çàäà÷àõ äèñêðåòíàÿ è ìíîãî-
ýêñòðåìàëüíàÿ. Åñëè åå àðãóìåíò — ïåðåñòàíîâêà, òî êîìáèíàòîðíîé ìàòðèöåé
ìîæåò áûòü ëþáàÿ èç çàäàííûõ.
Òåîðåìà 1. Åñëè â çàäà÷å î íàçíà÷åíèÿõ �( )j k j e� 0 , �( ) ( )j k n j e� � 0 2 1
èëè � �( ) ( )j n j � , j n� 1 2, , òî öåëåâàÿ ôóíêöèÿ ïîñòîÿííàÿ íà âñåì ìíîæåñòâå ïå-
ðåñòàíîâîê íåçàâèñèìî îò èõ óïîðÿäî÷åíèÿ, ãäå k e R0, � .
Òåîðåìà 2. Åñëè â çàäà÷å î íàçíà÷åíèÿõ � �( ) ( )j n j �2 , à äëÿ 1
j n
�( ) | |j j n n e� � � è äëÿ ( )n j n
1 2 �( ) | | ( )j j n n e� � � 1 , j n� 1 2, , e R� ,
òî àðãóìåíò, äëÿ êîòîðîãî öåëåâàÿ ôóíêöèÿ ïðèíèìàåò íàèìåíüøåå çíà÷åíèå, íàõî-
äèòñÿ â êàæäîì èç ïåðâûõ � �n / 2 ïîäìíîæåñòâ K t , à äëÿ íàèáîëüøåãî — â êàæäîì
èç � �n n/ , ,2 1 � ïîäìíîæåñòâ K t .
Åñëè â çàäà÷å î íàçíà÷åíèÿõ � �( ) ( )j n j �2 , à äëÿ 1
j n �( )j �
� � | |j n e1 è äëÿ ( )n j n
1 2 �( ) | |j j n e� � , j n� 1 2, , òî äëÿ íàèáîëüøåãî
çíà÷åíèÿ öåëåâîé ôóíêöèè ïåðåñòàíîâêè íàõîäÿòñÿ â êàæäîì èç ïåðâûõ � �n / 2 ïîä-
ìíîæåñòâ K t , à äëÿ íàèìåíüøåãî — â êàæäîì èç � �n n/ , ,2 1 � .
Òåîðåìà 3. Åñëè â çàäà÷å ðàçìåùåíèÿ � ( )j k j e� 0 , � j f j w k j e( ( ), )1 0� ,
j m� 1, , òî àðãóìåíò, äëÿ êîòîðîãî F wk( ) ïðèíèìàåò íàèáîëüøåå çíà÷åíèå, íàõî-
äèòñÿ â ïîäìíîæåñòâå K1, à äëÿ íàèìåíüøåãî — â ïîäìíîæåñòâå K m .
Åñëè â çàäà÷å ðàçìåùåíèÿ � ( ) ( )j k m j e� � 0 1 è � j f j w( ( ), )1 �
� � k m j e0 1( ) , j m� 1, , òî äëÿ íàèìåíüøåãî çíà÷åíèÿ öåëåâîé ôóíêöèè àðãóìåíò
íàõîäèòñÿ â ïåðâîì ïîäìíîæåñòâå, à äëÿ íàèáîëüøåãî — â K m .
Ïîëîæèì � �( ) ( )j j �2 è �( ) [ ( ) ] [ ( ) ]j
e dj j� � � 1 1
2
1 1
2
1 ,
~
( )
~
( )� �j j �2 ,
è
~
( ) [ ( ) ] [ ( ) ]� j
d ej j� � � 1 1
2
1 1
2
1 , d e� , e d R, � , j m� �1 1, .
Òåîðåìà 4. Åñëè â çàäà÷å ðàçìåùåíèÿ � ( )j k j e� 0 , � �j f j w j( ( ), ) ( )1 � ,
j m� 1, , òî äëÿ íàèìåíüøåãî çíà÷åíèÿ ôóíêöèè öåëè àðãóìåíò íàõîäèòñÿ â êàæäîì
èç � �m m/ , ,2 1 � ïîäìíîæåñòâ, à äëÿ íàèáîëüøåãî — â êàæäîì èç ïåðâûõ � �m / 2
ïîäìíîæåñòâ K t .
Åñëè â çàäà÷å ðàçìåùåíèÿ �( )j k j e� 0 , � �j f j w j( ( ), )
~
( )1 � , j m� 1, , òî äëÿ íà-
èìåíüøåãî çíà÷åíèÿ ôóíêöèè öåëè àðãóìåíò íàõîäèòñÿ â êàæäîì èç ïåðâûõ � �m / 2
ïîäìíîæåñòâ, a äëÿ íàèáîëüøåãî — â êàæäîì èç � �m m/ , ,2 1 � ïîäìíîæåñòâ.
Òåîðåìà 5. Åñëè â çàäà÷å ðàçìåùåíèÿ � �( ) ( )j j� , � �j f j w j( ( ), ) ( )1 � èëè
� �( )
~
( )j j� , � �j f j w j( ( ), )
~
( )1 � , j m� 1, , òî äëÿ íàèìåíüøåãî çíà÷åíèÿ ôóíêöèè
öåëè àðãóìåíò íàõîäèòñÿ â êàæäîì èç ïîäìíîæåñòâ ñ ÷åòíûìè íîìåðàìè, åñëè m
÷åòíîå, è â êàæäîì èç ïîäìíîæåñòâ ñ íå÷åòíûìè íîìåðàìè, åñëè m íå÷åòíîå. Äëÿ
íàèáîëüøåãî çíà÷åíèÿ öåëåâîé ôóíêöèè wk íàõîäèòñÿ â ïåðâîì ïîäìíîæåñòâå.
Òåîðåìà 6. Åñëè â çàäà÷å êîììèâîÿæåðà ôóíêöèÿ íàòóðàëüíîãî àðãóìåíòà âû-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 101
ïóêëàÿ óíèìîäàëüíàÿ èëè �( )j k j e� 0 èëè �( )j j� 2 , òî íàèáîëüøåå çíà÷åíèå öå-
ëåâàÿ ôóíêöèÿ ïðèíèìàåò äëÿ w Kk � 1, à íàèìåíüøåå — äëÿ w Kk
n� �2 .
Åñëè â çàäà÷å êîììèâîÿæåðà ôóíêöèÿ íàòóðàëüíîãî àðãóìåíòà âîãíóòàÿ óíè-
ìîäàëüíàÿ (ìàòðèöà Ñóïíèêà) èëè � ( ) ( )j k m j e� � 0 1 (ìàòðèöû Êàëüìàíñîíà,
Äåìèäåíêà, Ìîíæà) èëè � ( )j m j� � 2 1, òî íàèáîëüøåå çíà÷åíèå ôóíêöèÿ öåëè ïðè-
íèìàåò äëÿ w Kk
n� �2 , à íàèìåíüøåå — äëÿ w Kk � 1, j m� 1, .
 [16] ðàññìàòðèâàåòñÿ çàäà÷à êîììèâîÿæåðà, â êîòîðîé êðàò÷àéøèé ãàìèëüòî-
íîâûé òóð (òóð Ìàñòåðà) ñîâïàäàåò ñ êðàò÷àéøèì ïèðàìèäàëüíûì òóðîì, åñëè ìàð-
øðóò ïðîëåãàåò, íà÷èíàÿ èç ãîðîäà ïîä íîìåðîì 1 è çàêàí÷èâàåòñÿ ïîä íîìåðîì n,
à ãîðîäà ïîñåùàþòñÿ â ïîðÿäêå âîçðàñòàíèÿ ðàññòîÿíèé ìåæäó íèìè, è íàîáîðîò.
Ýòè ñëó÷àè ÿâëÿþòñÿ çàäà÷àìè Äåìèäåíêî è Êàëüìàíñîíà.
Òóð Ìàñòåðà è ïèðàìèäàëüíûé òóð íàõîäÿòñÿ â ïîäìíîæåñòâå K1, à çíà÷åíèå
öåëåâîé ôóíêöèè, åñëè � ( ) ( )j k m j e� � 0 1 , äëÿ âñåõ ïåðåñòàíîâîê, êîòîðûå íà-
õîäÿòñÿ â ýòîì ïîäìíîæåñòâå, îäèíàêîâîå. Â [55] ïîêàçàíî, ÷òî ìàòðèöû Êàëüìàí-
ñîíà è Äåìèäåíêî ìîäåëèðóþòñÿ ôóíêöèÿìè íàòóðàëüíîãî àðãóìåíòà òèïà
� ( ) ( )j k m j e� � 0 1 . Ýòî è îáúÿñíÿåò, ïî÷åìó Êàëüìàíñîí è Äåìèäåíêî äëÿ îäíî-
ãî è òîãî æå òèïà ìàòðèö íàøëè ðàçíûå ïåðåñòàíîâêè, äëÿ êîòîðûõ öåëåâàÿ ôóíê-
öèÿ ïðèíèìàåò îäèíàêîâîå, íàèìåíüøåå çíà÷åíèå, à àâòîðû ñòàòüè [16] ïîëó÷èëè
àíàëîãè÷íûé ðåçóëüòàò.
Òåîðåìà 7. Åñëè â çàäà÷å êîììèâîÿæåðà � �( ) ( )j j� , j m� 1, , òî íàèìåíüøåå
çíà÷åíèå F wk( ) ïðèíèìàåò äëÿ ïåðåñòàíîâêè w Kk
s� , ãäå s j� �{ , , , }1 3 2 1� . Äëÿ
íàèáîëüøåãî çíà÷åíèÿ F wi( ) ïåðåñòàíîâêà w Ki
t� , ãäå t j�{ , , , }2 4 2� .
Åñëè â çàäà÷å êîììèâîÿæåðà � �( )
~
( )j j� , j m� 1, , òî íàèìåíüøåå çíà÷åíèå
F wk( ) ïðèíèìàåò äëÿ ïåðåñòàíîâêè w Kk
s� , ãäå s j�{ , , , }2 4 2� . Äëÿ íàèáîëüøåãî
çíà÷åíèÿ F wi( ) ïåðåñòàíîâêà w Ki
t� , ãäå t j� �{ , , , }1 3 2 1� .
 çàäà÷àõ, àðãóìåíòîì öåëåâîé ôóíêöèè â êîòîðûõ ÿâëÿåòñÿ ðàçáèåíèå n-ýëå-
ìåíòíîãî ìíîæåñòâà íà ïîäìíîæåñòâà (êëàñòåðèçàöèÿ, êîìïîíîâêà), çàêîíîìåð-
íîñòü èçìåíåíèÿ çíà÷åíèé öåëåâîé ôóíêöèè çàâèñèò îò ñòðóêòóðû âõîäíûõ äàí-
íûõ, îò òèïîâ ðàçáèåíèé è îò óïîðÿäî÷åíèÿ àðãóìåíòà.
Óòî÷íèì íåêîòîðûå ïîíÿòèÿ. Ðàçáèåíèåì n-ýëåìåíòíîãî ìíîæåñòâà
A a an� { , , }1 � íà �k ïîäìíîæåñòâ (áëîêîâ) íàçîâåì ìíîæåñòâî ïîäìíîæåñòâ
�
k k k
k
�
( )
1
� òàêîå, ÷òî
�1
k k
k
A�� � � , s
k � �, t
k
s
k
� � �, t s� , t s, �
�{ , , }1� �k , �k n�{ , , }1 � . Ïîäìíîæåñòâî
s
k a a
s
k� ( , , )1 � , a Ar � , r s
k�{ , , }1 �
,
à
s
k n�{ , , }1� . Äâà ðàçáèåíèÿ k è i íàçîâåì èçîìîðôíûìè, åñëè � �k i� , è äëÿ
ëþáîãî ïîäìíîæåñòâà t
k k� èìååòñÿ ïîäìíîæåñòâî s
i i� , äëÿ êîòîðîãî
t
k
s
i� . Ïî êîëè÷åñòâó áëîêîâ è ýëåìåíòîâ ðàçáèåíèÿ â íèõ k ðàçäåëÿþòñÿ íà ÷åòûðå
òèïà [56]. Ê ïåðâîìó òèïó îòíîñÿòñÿ k , êîëè÷åñòâî ýëåìåíòîâ âî âñåõ áëîêàõ êîòîðîãî
ðàçíîå. Êîëè÷åñòâî ýëåìåíòîâ â áëîêàõ j
k ðàçáèåíèÿ âòîðîãî òèïà îäèíàêîâîå. Ðàçáèå-
íèÿ òðåòüåãî òèïà ñîäåðæàò äâà è áîëüøå áëîêîâ ñ îäíèì ýëåìåíòîì, ïðè ýòîì õîòÿ áû
îäèí áëîê äîëæåí ñîäåðæàòü áîëüøå îäíîãî ýëåìåíòà.  ðàçáèåíèå ÷åòâåðòîãî òèïà âõî-
äÿò äâà è áîëüøå áëîêîâ, êîëè÷åñòâî ýëåìåíòîâ â êîòîðûõ îäèíàêîâîå. Èç íèõ îäèí
áëîê äîëæåí èìåòü áîëüøå ýëåìåíòîâ, íåæåëè äðóãèå.
Ðàññìîòðèì íåêîòîðûå ðàçðåøèìûå ñëó÷àè çàäà÷è êëàñòåðèçàöèè äëÿ ïîäìíî-
æåñòâà èçîìîðôíûõ ðàçáèåíèé. Ïîëîæèì, ÷òî âõîäíûå äàííûå çàäàíû êîìáèíà-
òîðíîé ñèììåòðè÷åñêîé ìàòðèöåé C , ãäå crp — êîëè÷åñòâî ñâÿçåé ìåæäó çàäàííû-
ìè ýëåìåíòàìè a a Ar p, � . Ýëåìåíòû ñèììåòðè÷åñêîé ( , )0 1 -ìàòðèöû
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
Q k( )
Q k( ) qrp
k( ) � 1, åñëè a a Ar p, � , íàõîäÿòñÿ â îäíîì áëîêå j
k k� è g rp
k( ) � 0
— â ïðîòèâíîì ñëó÷àå.
Åñëè â k �k � 2, ïðè÷åì
1
1k n� � , à
2
1k � , òî êîëè÷åñòâî ïîäìíîæåñòâ â W�
ðàâíÿåòñÿ òðåì: K1, K 2 è K n . Åñëè �k � 2, à
�1 2
k k k
k
� � �� , ïðè÷åì
p
k � 1, òî
êîëè÷åñòâî ïîäìíîæåñòâ â W� ðàâíÿåòñÿ n �1. Äëÿ �k � 2 è
1 2
k k� êîëè÷åñòâî
ïîäìíîæåñòâ ðàâíÿåòñÿ q n
n� � �
� 2
2
. Åñëè � ( )j k j e� 0 , òî íàèáîëüøåå çíà÷åíèå
ôóíêöèÿ (1) ïåðâîãî òèïà ðàçáèåíèÿ ïðèíèìàåò äëÿ i , â êîòîðîì
�
�1 2
i i i
i
� �� ,
à íàèìåíüøåå — äëÿ ðàçáèåíèÿ, â êîòîðîì
�1 2
k k k
k
� � �� .  îáîèõ ñëó÷àÿõ
� i k K� 1 . Åñëè �k � 2 è
�k
k � 1, òî âàðèàíò ðåøåíèÿ çàäà÷è äëÿ íàèáîëüøåãî
F i( ) ïðèíàäëåæèò ïîäìíîæåñòâó K
q� .
Åñëè � ( ) ( )j k m j e� � 0 1 , òî íàèáîëüøåå çíà÷åíèå ôóíêöèÿ (1) ïåðâîãî òèïà
ðàçáèåíèé ïðèíèìàåò äëÿ i , â êîòîðîì
�1 2
i i i
i
� �� , à íàèìåíüøåå — äëÿ ðàç-
áèåíèÿ, â êîòîðîì
�
�1 2
k k k
k
� �� .  îáîèõ ñëó÷àÿõ � k i K� 1. Åñëè �k � 2 è
2
1k � , òî âàðèàíò ðåøåíèÿ çàäà÷è äëÿ íàèìåíüøåãî F k( ) ïðèíàäëåæèò ïîäìíî-
æåñòâó K q� .
Åñëè ôóíêöèÿ íàòóðàëüíîãî àðãóìåíòà äëÿ ïåðâîãî òèïà ðàçáèåíèé èçìåíÿåò-
ñÿ êàê âûïóêëàÿ óíèìîäàëüíàÿ ôóíêöèÿ, òî íàèáîëüøåå çíà÷åíèå F i( ) ïðèíèìà-
åò äëÿ i
q
K� � , à íàèìåíüøåå — äëÿ k K� 1. Åñëè �k � 2 è
2
1k � , òî äëÿ íàèáîëü-
øåãî F i( ) ðàçáèåíèå i
q
K� � , à äëÿ íàèìåíüøåãî — ñîîòâåòñòâåííî �
k K� .
Äëÿ F i( ) íàèáîëüøåãî âòîðîãî òèïà ðàçáèåíèé i K� 1, à äëÿ íàèìåíüøåãî —
� � �k
q
K n� � �� , ( ) /1 2 .
Åñëè � ( )j äëÿ ïåðâîãî òèïà ðàçáèåíèé èçìåíÿåòñÿ êàê âîãíóòàÿ óíèìîäàëüíàÿ
ôóíêöèÿ, òî íàèáîëüøåå çíà÷åíèå öåëåâàÿ ôóíêöèÿ (1) ïðèíèìàåò äëÿ i K� 1,
à íàèìåíüøåå — äëÿ k
q
K� � . Åñëè �k � 2 è
2
1k � , òî äëÿ íàèìåíüøåãî F k( )
k
q
K� � , à äëÿ íàèáîëüøåãî — ïîäìíîæåñòâó K � . Äëÿ íàèìåíüøåãî F k( ) âòîðî-
ãî òèïà ðàçáèåíèé k K� 1, à äëÿ íàèáîëüøåãî — ïîäìíîæåñòâó K
q� .
ÇÀÊËÞ×ÅÍÈÅ
Ìîäåëèðîâàíèå ñòðóêòóðû âõîäíûõ äàííûõ ôóíêöèÿìè íàòóðàëüíîãî àðãóìåíòà
ñóùåñòâåííî ðàñøèðÿåò ïîäêëàññû ðàçðåøèìûõ çàäà÷, ïîçâîëÿåò âûäåëÿòü èõ â
îòäåëüíûå ãðóïïû, äëÿ êîòîðûõ öåëåâàÿ ôóíêöèÿ èçìåíÿåòñÿ îäèíàêîâî, à òàêæå
îïðåäåëÿòü ïîäêëàññû, ê êîòîðûì îòíîñÿòñÿ èçâåñòíûå ðàçðåøèìûå ñëó÷àè.
Ïîëó÷åííûå ðåçóëüòàòû ðåøåíèÿ ðàçðåøèìûõ çàäà÷ ÿâëÿþòñÿ òàáëè÷íûìè
çíà÷åíèÿìè äëÿ ðàññìîòðåííûõ ñòðóêòóð. Óñëîæíÿÿ ñòðóêòóðó âõîäíûõ äàííûõ,
ñëåäóåò íàõîäèòü íîâûå ðàçðåøèìûå ñëó÷àè äëÿ ðàçíûõ çàäà÷ êîìáèíàòîðíîé
îïòèìèçàöèè, îïðåäåëÿòü äëÿ íèõ çàêîíîìåðíîñòü èçìåíåíèÿ çíà÷åíèé öåëåâîé
ôóíêöèè íà çàäàííîì óïîðÿäî÷åíèè êîìáèíàòîðíûõ êîíôèãóðàöèé, âûäåëÿòü
ñòðóêòóðû, äëÿ êîòîðûõ öåëåâàÿ ôóíêöèÿ èçìåíÿåòñÿ îäèíàêîâî, è ðàçðàáàòûâàòü
äëÿ íèõ îäèíàêîâûå ïðàâèëà ðåøåíèÿ. Ýòè ïðàâèëà ñïîñîáñòâóþò ñîçäàíèþ ïîëè-
íîìèàëüíûõ àëãîðèòìîâ íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ äëÿ øèðîêîãî êëàññà
çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 103
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. Àëãîðèòìû è ñëîæíîñòü:
Ïåð. ñ àíãë. — Ì.: Ìèð, 1985. — 510 ñ.
2. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíàòîðíûõ
çàäà÷ îïòèìèçàöèè. — Êèåâ: Íàóê. äóìêà, 1981. — 281 ñ.
3. Ñ å ð ã è å í ê î È .  . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè. —
Êèåâ: Íàóê. äóìêà, 1988. — 471 ñ.
4. Ê î ð á ó ò À . À . , Ô è í ê å ë ü ø ò å é í Þ . Þ . Äèñêðåòíîå ïðîãðàììèðîâàíèå. — Ì.: Íàóêà, 1969.
— 368 ñ.
5. Â à ã í å ð Ã . Îñíîâû èññëåäîâàíèÿ îïåðàöè. — Ì.: Ìèð, 1972. — Ò. 1. — 336 ñ.; Ò. 2. — 488 ñ.
6. C ò î ÿ í Þ . Ã . , Ñ î ê î ë î â ñ ê è é Â . Ç . Ðåøåíèå íåêîòîðûõ ìíîãîýêñòðåìàëüíûõ çàäà÷ ìåòîäîì
ñóæàþùèõñÿ îêðåñòíîñòåé. — Êèåâ: Íàóê. äóìêà, 1980. — 205 ñ.
7. Ì è õ à ë å â è ÷ Â . Ñ . Ïîñëåäîâàòåëüíûå àëãîðèòìû îïòèìèçàöèè è èõ ïðèìåíåíèå. I, II // Êèáåðíå-
òèêà. — 1965. — ¹ 1. — Ñ. 45–56; ¹ 2. — Ñ. 85–89.
8. Ì è õ à ë å â è ÷  . Ñ . , Ò ð ó á è í  . À . , Ø î ð Í . Ç . Îïòèìèçàöèîííûå çàäà÷è ïðîèçâîäñòâåí-
íî-òðàíñïîðòíîãî ïëàíèðîâàíèÿ. — Ì.: Íàóêà, 1986. — 264 ñ.
9. Ø ê ó ð á à  .  . Î ìàòåìàòè÷åñêîé îáðàáîòêå îäíîãî êëàññà áèîõèìè÷åñêèõ ýëåìåíòîâ // Êèáåðíå-
òèêà. — 1965. — ¹ 1. — Ñ. 62–67.
10. Á ó ð ä þ ê  . ß . , Ñ å ì å í î â  . À . Ðàçðåøèìûå ñëó÷àè íîâîé êîìáèíàòîðíîé çàäà÷è îïòèìèçà-
öèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1999. — ¹ 2. — Ñ. 175–178.
11. Ñ ó ï ð ó í å í ê î Ä . À . Î çíà÷åíèÿõ ëèíåéíîé ôîðìû íà ìíîæåñòâå ïåðåñòàíîâîê // Êèáåðíåòèêà.
— 1968. — ¹ 2. — Ñ. 59–63.
12. Á ó ð ä þ ê  . ß . , Ä å é í å ê î  . à . Îïòèìàëüíûå êðóãîâûå óïîðÿäî÷åíèÿ (çàäà÷à î êîììèâîÿ-
æåðå). — Äíåïðîïåòðîâñê: ÄÃÓ, 1983. — 103 ñ.
13. Ç à è ê à Â . Â . , Ø â à ð ò è í Ñ . Ì . Î öèêëàõ, ïîðîæäåííûõ ïðîèçâîëüíûì ìíîæåñòâîì ýëåìåíòîâ
ìàòðèöû // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 1984. — 24, ¹ 8. — Ñ. 1230–1240.
14. Ä å ì è ä å í ê î Â . Ì . , Ã î ð ä î í Â . Ñ . , Ï ð î ø Æ . - Ì . Óñëîâèÿ ïîëèíîìèàëüíîé ðàçðåøèìîñòè
çàäà÷è î êîììèâîÿæåðå è âåðõíèå îöåíêè åå îïòèìóìà // Äîêë. ÍÀÍ Áåëàðóñè. — 2003. — 47, ¹ 1.
— Ñ. 36–40.
15. Ä å ì å í ò ü å â  . Ò . , Ø à ì à ð ä è í Þ .  . Äâóõóðîâíåâàÿ çàäà÷à î íàçíà÷åíèÿõ ïðè îáîáùåííîì
óñëîâèè Ìîíæà // Äèñêðåòíûé àíàëèç è èññëåäîâàíèå îïåðàöèé. Ñåð. 2. — 2003. — 10, ¹ 2. — Ñ. 19–28.
16. J a c k A . A . , v a n D e r V . , S i e r k s m a G . , v a n D a l R . Pyramidal tours and the travelling
salesman problem // Eur. J. Oper. Res. — 1991. — 52, N 1. — P. 90–102.
17. Ä å é í å ê î  . à . Ðîçâ’ÿçí³ñòü â êîìá³íàòîðí³é îïòèì³çàö³¿. Ðîçâ’ÿçí³ âèïàäêè ïðîáëåìè êîì³âîÿæå-
ðà òà åâð³ñòè÷í³ àëãîðèòìè: Àâòîðåô. äèñ. ... ä-ðà ô³ç.-ìàò. íàóê / ²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóø-
êîâà ÍÀÍ Óêðà¿íè. — Êè¿â, 1995. — 48 ñ.
18. À é ç å í ø ò à ò  . Ñ . , Ì à ê ñ è ì î â è ÷ Å . Ï . Íåêîòîðûå êëàññû çàäà÷ î áðîäÿ÷åì òîðãîâöå // Êè-
áåðíåòèêà. — 1978. — ¹ 4. — Ñ. 80–83.
19. Ä å ì è ä å í ê î  . Ì . Ïîñòðîåíèå ðåëàêñàöèè ïîëèòîïà ñèììåòðè÷åñêîé çàäà÷è î êîììèâîÿæåðå íà
îñíîâå ñèëüíî ðàçðåøèìîãî ñëó÷àÿ Êàëüìàíñîíà // Äèñêðåòíûé àíàëèç è èññëåäîâàíèå îïåðàöèé.
Ñåð. 2. — 2004. — 11, ¹ 2. — Ñ. 324.
20. K a l m a n c o n K . Edgeconvex circuits and the traveling salesman problem // Canad. J. Math. — 1975. —
27, N 5. — P. 1000–1010.
21. S u p n i c k F . Extreme Íamiltonian lines // Annals of Math. — 1957. — 66. — P. 179–201.
22. Ä å ì è ä å í ê î  . Ì . Ñïåöèàëüíûé ñëó÷àé çàäà÷è î áðîäÿ÷åì òîðãîâöå // Èçâ. ÀÍ ÁÑÑÐ. Ñåð.
ôèç.-ìàò. íàóê. — 1976. — ¹ 5. — Ñ. 28–32.
23.  î ë î ä à ð ñ ê è é ß . Ì . , à à á î â è ÷ Å . ß . , Ç à õ à ð è í À . ß . Îäèí ðàçðåøèìûé ñëó÷àé â äèñê-
ðåòíîì ïðîãðàììèðîâàíèè // Èçâ. ÀÍ ÑÑÑÐ. Òåõí. êèáåðíåòèêà. — 1976. — ¹ 1. — Ñ. 34–44.
24. Ð ó á è í ø ò å é í Ì . È . Î ñèììåòðè÷åñêîé çàäà÷å êîììèâîÿæåðà // Àâòîìàòèêà è òåëåìåõàíèêà. —
1971. — ¹ 9. — Ñ. 126–133.
25. Ä å ì è ä å í ê î  . Ì . Ê îïòèìèçàöèè âåëè÷èíû � �( , )A íà ìíîæåñòâå öèêëîâ// Âåñö³ ÀÍ ÁÑÑÐ.
Ñåð. ô³ç.-ìàò. íàâóê. — 1978. — ¹ 1. — Ñ. 21–26.
26. Ä å ì è ä å í ê î  . Ì . Îá ýêñòðåìàëüíûõ çàäà÷àõ íà ïîäñòàíîâêàõ: Àâòîðåô. äèñ. ... êàíä. ôèç.-ìàò.
íàóê: 01.01.09 / Èí-ò ìàòåìàòèêè ÀÍ ÁÑÑÐ. — Ìèíñê, 1980. — 14 ñ.
27. À é ç å í ø ò à ò Â . Ñ . , Ê ð à â ÷ ó ê Ä . Í . Îá ýêñòðåìóìå ëèíåéíîé ôîðìû íà ìíîæåñòâå âñåõ öèê-
ëè÷åñêèõ ïîäñòàíîâîê // Êèáåðíåòèêà. — 1968. — ¹ 6. — Ñ. 76–81.
28. À é ç å í ø ò à ò Â . Ñ . , Ê ð à â ÷ ó ê Ä . Í . Î ìèíèìóìå ëèíåéíîé ôîðìû íà ìíîæåñòâå âñåõ ïîëíûõ
öèêëîâ ñèììåòðè÷åñêîé ãðóïïû // Òàì æå. — 1968. — ¹ 2. — Ñ. 64–66.
29. Ä å ì è ä å í ê î  . Ì . Îáîáùåíèå óñëîâèé ñèëüíîé ðàçðåøèìîñòè êâàäðàòè÷íîé çàäà÷è î íàçíà÷å-
íèÿõ ñ ìàòðèöàìè Àíòè-Ìîíæà è Òåïëèöà // Äîêë. ÍÀÍ Áåëàðóñè. — 2003. — 47, ¹ 2. — Ñ. 15–18.
30. M o n g e G . M�moire sur la th�orie des d�blais et des remblais // Histoire de l’Acad�mie Royale des Sci-
ences, Ann�e M. DCCLXXXI, avec les M�moires de Math�matique et de Physique, pour la �meme Ann�e,
Tir�s des Registres de cette Acad�mie. — Paris, 1781. — P. 666–704.
104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2
31. B u r k a r d R . E . , K l i n z B . , R u d o l f R . Perspectives of Monge properties in optimization // Dis-
crete Appl. Math. — 1996. — 70. — P. 95–161.
32. Ä å ì è ä å í ê î  . Ì . Êîíè÷åñêàÿ õàðàêòåðèçàöèÿ ìàòðèö Ìîíæà // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2004. — ¹ 4. — Ñ. 87–98.
33. Ä å é í å ê î  . à . , Ò ð î ô è ì î â  . Í . Î âîçìîæíûõ çíà÷åíèÿõ ôóíêöèîíàëà â ñïåöèàëüíûõ çàäà-
÷àõ êîììèâîÿæåðà // Êèáåðíåòèêà. — 1981. — ¹ 6. — Ñ. 135–136.
34. Á ó ð ä þ ê Â . ß . , Ò ð î ô è ì î â Â . Í . Îáîáùåíèå ðåçóëüòàòîâ Ãèëìîðå è Ãîìîðè ïî ðåøåíèþ çà-
äà÷è êîììèâîÿæåðà // Èçâ. ÀÍ ÑÑÑÐ. Òåõí. êèáåðíåòèêà. — 1976. — ¹ 3. — Ñ. 16–22.
35. Ä å ì è ä å í ê î  . Ì . , Ï ð î ò Æ . - Ì . Êâàäðàòè÷íàÿ çàäà÷à î íàçíà÷åíèÿõ: äîñòèæåíèå îïòèìóìà
íà çàäàííûõ ïîäñòàíîâêàõ // Âåñö³ ÍÀÍ Áåëàðóñè. Ñåð ôèç.-ìàò. íàâóê. — 2005. — ¹ 2. —
Ñ. 60–64.
36. Ä å ì è ä å í ê î  . Ì . , Ä î ë ã è é À . Ýôôåêòèâíî ðàçðåøèìûå ñëó÷àè êâàäðàòè÷íîé çàäà÷è î
íàçíà÷åíèÿõ: ñ îáîáùåííî ìîíîòîííûìè è íåïîëíûìè ìàòðèöàìè Àíòè-Ìîíæà // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2007. — ¹ 1. — Ñ. 135–151.
37. P a r n a s M . , R o n D . , R u b i n f e l d R . On testing convexity and submodularity // SIAM J. Comput.
— 2003. — 32, N 5. — P. 1158–1184.
38. Ò è ì î ô å å â à Í . Ê . Î íåêîòîðûõ îñîáåííîñòÿõ ïîñòðîåíèÿ ìàòåìàòè÷åñêèõ ìîäåëåé çàäà÷ êîìáè-
íàòîðíîé îïòèìèçàöèè // ÓÑèÌ. — 2004. — ¹ 5 — Ñ. 38–45.
39. Ò ó ð á è í À . Ô . , Ï ð à ö å â è ò û é Í . Â . Ôðàêòàëüíûå ìíîæåñòâà, ôóíêöèè, ðàñïðåäåëåíèÿ. —
Êèåâ: Íàóê. äóìêà, 1992. — 207 ñ.
40. Ñ à ë ï à ã à ð î â Ñ . È . Çàäà÷à î íàçíà÷åíèÿõ íà ôðàêòàëüíûõ è ïðåäôðàêòàëüíûõ ãðàôàõ (Ìíîãî-
êðèòåðèàëüíàÿ ïîñòàíîâêà) / Êàðà÷àåâî-×åðêåñ. ãîñ. òåõí. àêàä. — ×åðêåññê, 2003. — 34 ñ. — Äåï.
â ÂÈÍÈÒÈ 31.12.2003, ¹ 2323 — Â2003.
41. Ï å ð å ï å ë è ö à Â . À , Ñ å ð ã è å í ê î È . Â . , Ê î ÷ ê à ð î â À . Ì . Ê ïðîáëåìå ðàñïîçíàâàíèÿ
ôðàêòàëüíûõ ãðàôîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1999. — ¹ 4. — Ñ. 72–89.
42. Á î á û ë å â à Å .  . ×àñòíûé ñëó÷àé çàäà÷è ðàñïîçíàâàíèÿ ïîëíîãî íåêàíîíè÷åñêîãî ïðåäôðàêòàëü-
íîãî ãðàôà // Ìàòåìàòè÷í³ ìàøèíè ³ ñèñòåìè. — 2005. — ¹ 2. — Ñ. 3–14.
43. Õ à ð ä è Ã . Ã . , Ë è ò ò ë ü â ó ä Ä æ . Å . , Ï î ë è à Ã . Íåðàâåíñòâà. — Ì.: Ãîñ. èçä-âî èíîñòð. ëèò.,
1948. — 456 ñ.
44. à ý ð è Ì . , Ä æ î í ñ î í Ä . Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è: Ïåð. ñ àíãë. —
Ì.: Ìèð, 1982. — 416 ñ.
45. C o r r i z o s a E . , H a m a c h e r H . W . , K l e i n R . , N i c k e l S . Solving nonconvex planar location
problems by finite dominating sets // J. Clob. Optimiz. — 2000. — 18, N 2. — Ð. 195–210.
46. C o r n u e j o l s G . , N a d d e f D . , P u l l e y b l a n k W . The traveling salesman problem in graphs with
3-edge cutsets // J. Assoc. Comput. Mach. — 1985. — 32, N 2. — P. 383–410.
47. B u r k a r d R . E . , F i n c k e U . The asymptotic probabilistic behaviour of quadratic sum assigument
problems // J. Oper. Res. — 1983. — A27, N 3. — Ð. 73–81.
48. Ò è ì î ô å å â à Í . Ê . Çàâèñèìîñòü öåëåâîé ôóíêöèè çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè îò
óïîðÿäî÷åíèÿ êîìáèíàòîðíûõ êîíôèãóðàöèé // Êîìïüþòåðíàÿ ìàòåìàòèêà. — 2005. — ¹ 2. —
Ñ. 135–146.
49. Ò è ì î ô å å â à Í . Ê . Îá îäíîì ïîäõîäå ê íàõîæäåíèþ îïòèìàëüíîãî ðåøåíèÿ â çàäà÷å î
íàçíà÷åíèÿõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1996. — ¹ 1. — Ñ. 104–112.
50. Ò è ì î ô å å â à Í . Ê . Êîìáèíàòîðíûå ôóíêöèè â çàäà÷å ðàçìåùåíèÿ // Êîìïüþòåðíàÿ ìàòåìàòèêà.
— 2004. — ¹ 1. — Ñ. 47–56.
51. Ò è ì î ô å å â à Í . Ê . Èññëåäîâàíèå öåëåâîé ôóíêöèè â çàäà÷å ðàçìåùåíèÿ / Èí-ò êèáåðíåòèêè
èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû. — Êèåâ, 1991. — 25 ñ. — Äåï. â ÂÈÍÈÒÈ 01.03.91, ¹ 930– Â91.
52. Ò è ì î ô å å â à Í . Ê . ×àñòíûé ñëó÷àé çàäà÷è êîììèâîÿæåðà // Ðàçðàáîòêà ìàò. è ïðîãðàììíîãî
îáåñïå÷åíèÿ ÏÏÏ è ðåøåíèå çàäà÷ äèñêðåòíîé îïòèìèçàöèè. — Êèåâ: Èí-ò êèáåðíåòèêè
èì. Â.Ì. Ãëóøêîâà ÀÍ Óêðàèíû, 1992. — Ñ. 95–101.
53. Ò è ì î ô å å â à Í . Ê . Íàõîæäåíèå îïòèìàëüíîãî ðåøåíèÿ â çàäà÷å êîììèâîÿæåðà // Ïðîãðàì-
ìíî-àëãîðèòìè÷åñêîå îáåñïå÷åíèå ðåøåíèÿ çàäà÷ ïðèêëàäíîé ìàòåìàòèêè. — Êèåâ: Èí-ò
êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÀÍ Óêðàèíû, 1993. — Ñ. 21–26.
54. Ò è ì î ô ³ º â à Í . Ê . Ðîçâ’ÿçíèé âèïàäîê çàäà÷³ ðîçì³ùåííÿ // ³ñí. Êè¿â. óí-òó. Ñåð. ô³ç.-ìàò.
íàóêè. — Ê.: Êè¿âñüê. óí-ò ³ì. Òàðàñà Øåâ÷åíêà, 2006. — ¹ 4. — Ñ. 227–231.
55. Ä î í å ö ü à . Ï . , Ò è ì î ô ³ º â à Í . Ê . Ìåòîä ìîäåëþâàííÿ ñòðóêòóðè âõ³äíèõ äàíèõ ³ ï³äêëàñè
ðîçâ’ÿçíèõ çàäà÷ // Ìàòåìàòè÷íå òà ïðîãðàìíå çàáåçïå÷åííÿ ³íòåëåêòóàëüíèõ ñèñòåì (MPZIS —
2007). Ï’ÿòà ì³æíàð. íàóê.-ïðàêò. êîíô. Äí³ïðîïåòðîâñüê, 14–16 ëèñòîïàäà 2007 ð. — Äí³ïðî-
ïåòðîâñüê, 2007. — Ñ. 52–53.
56. Ò è ì î ô å å â à Í . Ê . Î íåêîòîðûõ ñâîéñòâàõ ðàçáèåíèé ìíîæåñòâà íà ïîäìíîæåñòâà // ÓÑèÌ. —
2002. — ¹ 5. — Ñ. 6–23.
Ïîñòóïèëà 03.05.2007
Ïîñëå äîðàáîòêè 18.09.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 2 105
|