Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности
Розглянуто застосування методу побудови лексикографічної еквівалентності для розв’язування частково комбінаторних задач оптимізації на розміщеннях. Запропоновано узагальнення відношення еквівалентності, яке використовується для розбиття простору, вивчено його властивості. Модифіковано запропоновані...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/86298 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности / Т.Н. Барболина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 137-149. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-86298 |
|---|---|
| record_format |
dspace |
| spelling |
Барболина, Т.Н. 2015-09-12T18:04:08Z 2015-09-12T18:04:08Z 2013 Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности / Т.Н. Барболина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 137-149. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86298 519.85 Розглянуто застосування методу побудови лексикографічної еквівалентності для розв’язування частково комбінаторних задач оптимізації на розміщеннях. Запропоновано узагальнення відношення еквівалентності, яке використовується для розбиття простору, вивчено його властивості. Модифіковано запропоновані раніше алгоритми методу, обґрунтовано наближений алгоритм. The paper considers the solution of mixed combinatorial optimization problems on arrangements by the method of construction of lexicographic equivalence. A generalization of the relation of equivalence, which is used for space splitting, is proposed and its properties are analyzed. The algorithms of the method known earlier are modified, an approximated algorithm is validated. R ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности Розв’язування частково комбінаторних задач оптимізації на розміщеннях методом побудови лексикографічної еквівалентності Solution of mixed combinatorial optimization problems on arrangements by the method of construction of lexicographic equivalence Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности |
| spellingShingle |
Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности Барболина, Т.Н. Системный анализ |
| title_short |
Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности |
| title_full |
Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности |
| title_fullStr |
Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности |
| title_full_unstemmed |
Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности |
| title_sort |
решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности |
| author |
Барболина, Т.Н. |
| author_facet |
Барболина, Т.Н. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Розв’язування частково комбінаторних задач оптимізації на розміщеннях методом побудови лексикографічної еквівалентності Solution of mixed combinatorial optimization problems on arrangements by the method of construction of lexicographic equivalence |
| description |
Розглянуто застосування методу побудови лексикографічної еквівалентності для розв’язування частково комбінаторних задач оптимізації на розміщеннях. Запропоновано узагальнення відношення еквівалентності, яке використовується для розбиття простору, вивчено його властивості. Модифіковано запропоновані раніше алгоритми методу, обґрунтовано наближений алгоритм.
The paper considers the solution of mixed combinatorial optimization problems on arrangements by the method of construction of lexicographic equivalence. A generalization of the relation of equivalence, which is used for space splitting, is proposed and its properties are analyzed. The algorithms of the method known earlier are modified, an approximated algorithm is validated. R
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/86298 |
| citation_txt |
Решение частично комбинаторных задач оптимизации на размещениях методом построения лексикографической эквивалентности / Т.Н. Барболина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 137-149. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT barbolinatn rešeniečastičnokombinatornyhzadačoptimizaciinarazmeŝeniâhmetodompostroeniâleksikografičeskoiékvivalentnosti AT barbolinatn rozvâzuvannâčastkovokombínatornihzadačoptimízacíínarozmíŝennâhmetodompobudovileksikografíčnoíekvívalentností AT barbolinatn solutionofmixedcombinatorialoptimizationproblemsonarrangementsbythemethodofconstructionoflexicographicequivalence |
| first_indexed |
2025-11-24T21:10:51Z |
| last_indexed |
2025-11-24T21:10:51Z |
| _version_ |
1850497663747751936 |
| fulltext |
ÓÄÊ 519.85
Ò.Í. ÁÀÐÁÎËÈÍÀ
ÐÅØÅÍÈÅ ×ÀÑÒÈ×ÍÎ ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÇÀÄÀ× ÎÏÒÈÌÈÇÀÖÈÈ
ÍÀ ÐÀÇÌÅÙÅÍÈßÕ ÌÅÒÎÄÎÌ ÏÎÑÒÐÎÅÍÈß
ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÎÉ ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ
Êëþ÷åâûå ñëîâà: ìóëüòèìíîæåñòâî, ÷àñòè÷íî êîìáèíàòîðíàÿ åâêëèäîâà çà-
äà÷à îïòèìèçàöèè, ëåêñèêîãðàôè÷åñêèé ïåðåáîð.
ÂÂÅÄÅÍÈÅ
Àêòóàëüíûì íàïðàâëåíèåì èññëåäîâàíèé â îáëàñòè îïòèìèçàöèè ÿâëÿþòñÿ ìå-
òîäû è àëãîðèòìû åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè [1–10]. Åâêëèäîâû
çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè êëàññèôèöèðóþò êàê ïî âèäó öåëåâîé
ôóíêöèè è äîïîëíèòåëüíûõ îãðàíè÷åíèé, òàê è â ñîîòâåòñòâèè ñ åâêëèäîâûì
êîìáèíàòîðíûì ìíîæåñòâîì, êîòîðîå îïðåäåëÿåò êîìáèíàòîðíîå îãðàíè÷åíèå.
Òàêèì îáðàçîì âûäåëÿþò îïòèìèçàöèîííûå çàäà÷è íà ïåðåñòàíîâêàõ, ñî÷åòà-
íèÿõ, ðàçìåùåíèÿõ, ïîëèïåðåñòàíîâêàõ è ò.ä. Â íàñòîÿùåå âðåìÿ íàèáîëåå èñ-
ñëåäîâàííû çàäà÷è íà âåðøèííî ðàñïîëîæåííûõ ìíîæåñòâàõ, ò.å. ñîâïàäàþ-
ùèõ ñ ìíîæåñòâîì âåðøèí ñâîåþ âûïóêëîé îáîëî÷êîé [1–5]. Îäíàêî ó ðåøå-
íèÿ çàäà÷ íà ìíîæåñòâàõ, êîòîðûå òàêîãî ñâîéñòâà íå èìåþò (íàïðèìåð,
îáùåãî ìíîæåñòâà ðàçìåùåíèé), åñòü ðÿä ñóùåñòâåííûõ îñîáåííîñòåé.
Ðàíåå áûëè èçó÷åíû ñâîéñòâà äîïóñòèìîé îáëàñòè [6, 7], îñîáåííîñòè ðåøåíèÿ
áåçóñëîâíûõ çàäà÷ [1], ïðåäëîæåíû ìåòîäû ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ íà
ðàçìåùåíèÿõ [8–10]. Îäèí èç ïîäõîäîâ ê ðåøåíèþ òàêèõ çàäà÷ ñîñòîÿë â èñïîëüçî-
âàíèè ðàçáèåíèÿ ìíîãîãðàííèêà íà êëàññû ýêâèâàëåíòíîñòè ñ ïîñëåäóþùèì íà-
ïðàâëåííûì ïåðåáîðîì ïîëó÷åííûõ êëàññîâ [8–10].  êà÷åñòâå îòíîøåíèÿ ýêâèâà-
ëåíòíîñòè â ýòîì ñëó÷àå èñïîëüçîâàëîñü îòíîøåíèå ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíò-
íîñòè òî÷åê ïðîñòðàíñòâà îòíîñèòåëüíî ðàçìåùåíèé. Ýòî îòíîøåíèå îïðåäåëÿëîñü
äëÿ ñëó÷àÿ, êîãäà ðàçìåðíîñòü ïðîñòðàíñòâà u áûëà ðàâíà äëèíå âûáîðêè k , ÷òî ïî-
çâîëÿëî ïðèìåíÿòü ìåòîä òîëüêî äëÿ ðåøåíèÿ ïîëíîñòüþ êîìáèíàòîðíûõ îïòèìèçà-
öèîííûõ çàäà÷. Â íàñòîÿùåé ñòàòüå ðàññìîòðåíî îáîáùåíèå äàííîãî îòíîøåíèÿ äëÿ
ñëó÷àÿ k u� è îáîñíîâàíû àëãîðèòìû ðåøåíèÿ ëèíåéíûõ ÷àñòè÷íî êîìáèíàòîðíûõ
çàäà÷ íà ðàçìåùåíèÿõ ñ ó÷åòîì èññëåäóåìûõ ñâîéñòâ îòíîøåíèÿ.
 èçëîæåíèè ðåçóëüòàòîâ îòíîñèòåëüíî åâêëèäîâûõ êîìáèíàòîðíûõ ìíî-
æåñòâ èñïîëüçîâàíû òåðìèíîëîãèÿ è îáîçíà÷åíèÿ èç [1]. Ïîä ìóëüòèìíîæåñòâîì
ïîíèìàåòñÿ ñîâîêóïíîñòü ýëåìåíòîâ, ñðåäè êîòîðûõ ìîãóò áûòü è îäèíàêîâûå.
Êîðòåæ ðàçëè÷íûõ ýëåìåíòîâ ìóëüòèìíîæåñòâà íàçûâàåòñÿ åãî îñíîâîé.
Óïîðÿäî÷åííîé k-âûáîðêîé èç ìóëüòèìíîæåñòâà G g g� � �{ }1 � � íàçûâàåòñÿ
íàáîð ( )g gi ik1
� �� , ãäå g Gij
� , i ij t� � �i i Jj t, � � �j t Jk, (çäåñü è äàëåå Jn —
ìíîæåñòâî n ïåðâûõ íàòóðàëüíûõ ÷èñåë). Ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ k-âû-
áîðîê èç ìóëüòèìíîæåñòâà G íàçûâàåòñÿ îáùèì ìíîæåñòâîì k-ðàçìåùåíèé.
Îòíîñèòåëüíî ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà èñïîëüçîâàíà òåðìèíîëîãèÿ
èç [11, 12].  ÷àñòíîñòè, âåêòîð x R u� ëåêñèêîãðàôè÷åñêè áîëüøå âåêòîðà
y R u� (çàïèñûâàåòñÿ x y� ), åñëè ïåðâàÿ îòëè÷íàÿ îò íóëÿ êîîðäèíàòà èõ ðàç-
íîñòè ïîëîæèòåëüíà. Åñëè âåêòîð x ëåêñèêîãðàôè÷åñêè áîëüøå âåêòîðà y , òî
y ëåêñèêîãðàôè÷åñêè ìåíüøå x (x y� ). Ãîâîðÿò òàêæå, ÷òî âåêòîð x ëåêñèêî-
ãðàôè÷åñêè íå ìåíüøå âåêòîðà y (x y� ), åñëè x y� èëè x y� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 137
© Ò.Í. Áàðáîëèíà, 2013
ÎÁÎÁÙÅÍÍÎÅ ÎÒÍÎØÅÍÈÅ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÎÉ ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ
ÎÒÍÎÑÈÒÅËÜÍÎ ÐÀÇÌÅÙÅÍÈÉ
Ïóñòü k u N, � (k u� ), äëÿ òî÷êè x x x x Rk u
u� � � � � �( )1 � � îáîçíà÷èì
�k kx x x( ) ( )� � �1 � . Ïóñòü òàêæå E Gn
k
� ( ) — îáùåå ìíîæåñòâî k-ðàçìåùåíèé èç
ìóëüòèìíîæåñòâà G g g g� { , , ... }1 2 � ñ îñíîâîé S G e en( ) ( )� � �1 � . Â äàëüíåé-
øåì ïîëàãàåì, ÷òî ýëåìåíòû ìóëüòèìíîæåñòâà óïîðÿäî÷åíû ïî íåóáûâàíèþ,
à ýëåìåíòû îñíîâû — ïî âîçðàñòàíèþ.
Îïðåäåëåíèå 1. Òî÷êè x y R u, � (x y� ) íàçûâàþòñÿ ëåêñèêîãðàôè÷åñêè ýê-
âèâàëåíòíûìè îòíîñèòåëüíî k-ðàçìåùåíèé (� k -ýêâèâàëåíòûìè), åñëè âûïîëíÿ-
åòñÿ îäíî èç äâóõ óñëîâèé:
— íå ñóùåñòâóåò òàêîãî z z z E Gk n
k� � � �( ) ( )1 � � , ÷òî � �k kx z y( ) ( )� � ;
— ñïðàâåäëèâî ðàâåíñòâî � �k kx y( ) ( )� .
Åñëè òî÷êè x è y ÿâëÿþòñÿ � k -ýêâèâàëåíòûìè, áóäåì çàïèñûâàòü x y~ ,
â ïðîòèâíîì ñëó÷àå x y~/ .
Óòâåðäæåíèå 1. Îòíîøåíèå � k ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòîñòè òî÷åê
ïðîñòðàíñòâà îòíîñèòåëüíî k-ðàçìåùåíèé ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè.
Äîêàçàòåëüñòâî. Ïîñêîëüêó äëÿ ëþáîé òî÷êè x R u� âûïîëíÿåòñÿ óñëîâèå
� �k kx x( ) ( )� , èìååò ìåñòî ðåôëåêñèâíîñòü îòíîøåíèÿ � k . Ñèììåòðè÷íîñòü
ñëåäóåò íåïîñðåäñòâåííî èç îïðåäåëåíèÿ. Äëÿ äîêàçàòåëüñòâà óòâåðæäåíèÿ îñòà-
åòñÿ äîêàçàòü òðàíçèòèâíîñòü îòíîøåíèÿ.
Ïóñòü äëÿ òî÷åê x x x R u
1 2 3, , � âûïîëíÿþòñÿ ñîîòíîøåíèÿ x x1 2~ , x x2 3~ .
Íå íàðóøàÿ îáùíîñòè, ìîæåì ñ÷èòàòü, ÷òî x x1 3� . Ïðåäïîëîæèì, ÷òî x x1 3~/ ,
òîãäà � �k kx x( ) ( )1 3� , ïðè÷åì ñóùåñòâóåò òàêîå z E Gn
k� � ( ) , ÷òî
� �k kx z x( ) ( )1 3� � . Äëÿ òî÷åê z è x2 èìååò ìåñòî îäíî èç ñîîòíîøåíèé:
z xk� � ( )2 èëè �k x z( )2 � .  ïåðâîì ñëó÷àå èìååì � �k kx z x( ) ( )1 2� � , ÷òî ïðî-
òèâîðå÷èò � k -ýêâèâàëåíòíîñòè òî÷åê x1 è x2 , âî âòîðîì — âñëåäñòâèå ñîîòíîøå-
íèÿ � �k kx z x( ) ( )2 3� � ïîëó÷àåì ïðîòèâîðå÷èå ñ òåì ôàêòîì, ÷òî x x2 3~ . Òà-
êèì îáðàçîì, ïðåäïîëîæåíèå î íåýêâèâàëåíòíîñòè òî÷åê x1 è x3 íåïðàâèëüíî è
îòíîøåíèå � k ÿâëÿåòñÿ òðàíçèòèâíûì. Óòâåðæäåíèå äîêàçàíî.
Èç óòâåðæäåíèÿ 1 ñëåäóåò, ÷òî îòíîøåíèå � k ðàçáèâàåò ìíîãîãðàííèê
M R u� íà êëàññû ýêâèâàëåíòíîñòè, ìíîæåñòâî êîòîðûõ (ôàêòîð-ìíîæåñòâî ïî
ýêâèâàëåíòíîñòè � k ) îáîçíà÷èì F , ò.å. F M k� / � .
Îïðåäåëåíèå 2. Ýëåìåíòû ôàêòîð-ìíîæåñòâà ïî ýêâèâàëåíòíîñòè � k áóäåì
íàçûâàòü � k -êëàññàìè.
Èç îïðåäåëåíèÿ 1 ñëåäóåò, ÷òî êàæäûé ýëåìåíò x x x E Gk n
k� � � �( ) ( )1 � �
îïðåäåëÿåò îòäåëüíûé êëàññ ýêâèâàëåíòíîñòè, ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ
âñå òî÷êè ìíîãîãðàííèêà M âèäà ( , )x x x xk k u1 1� � � � � � . Ìíîæåñòâî òàêèõ
� k -êëàññîâ îáîçíà÷èì FE . Îñòàëüíûå êëàññû ýêâèâàëåíòíîñòè íå ñîäåðæàò òî-
÷åê, ïåðâûå k êîîðäèíàò êîòîðûõ îáðàçóþò ýëåìåíò ìíîæåñòâà E Gn
k
� ( ) .
Îïðåäåëåíèå 3. Êîìáèíàòîðíûì íàçûâàåòñÿ � k -êëàññV , åñëè � �k n
kx E G( ) ( )�
äëÿ ëþáîãî x V� , â ïðîòèâíîì ñëó÷àå � k -êëàññV íàçûâàåòñÿ íåêîìáèíàòîðíûì.
Ðàññìîòðèì âîçìîæíîñòü óïîðÿäî÷èâàíèÿ ýëåìåíòîâ ôàêòîð-ìíîæåñòâà F .
Îïðåäåëåíèå 4. Áóäåì ãîâîðèòü, ÷òî � k -êëàññ V ëåêñèêîãðàôè÷åñêè áîëüøå
� k -êëàññà V
òîãäà è òîëüêî òîãäà, êîãäà � �x V è �
�
x V âûïîëíÿåòñÿ óñëîâèå
x x�
.
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
Îáîçíà÷èì V V�
òîò ôàêò, ÷òî � k -êëàññ V ëåêñèêîãðàôè÷åñêè áîëüøå
� k -êëàññà V
. Êàê è äëÿ ñëó÷àÿ u k� , ïðîöåäóðó ñðàâíåíèÿ � k -êëàññîâ ìîæíî
óïðîñòèòü íà îñíîâå ñëåäóþùåãî óòâåðæäåíèÿ.
Óòâåðæäåíèå 2. Ïóñòü V V F,
� , ïðè÷åì V V�
è äëÿ íåêîòîðûõ x V� , x V
�
âûïîëíÿåòñÿ ñîîòíîøåíèå x x�
. Òîãäà � k -êëàññ V ëåêñèêîãðàôè÷åñêè áîëüøå
� k -êëàññà V
.
Äîêàçàòåëüñòâî. Ïóñòü y è
y — ïðîèçâîëüíûå ïðåäñòàâèòåëè ñîîòâåòñòâåííî
� k -êëàññîâ V è V
. Ïîêàæåì, ÷òî y y�
. Ïîñêîëüêó x è x
ïðèíàäëåæàò ðàçíûì
� k -êëàññàì, òî x x~/ ,
ò.å. íàéäåòñÿ òàêàÿ òî÷êà z E Gn
k� � ( ) , ÷òî � �k kx z x( ) ( )� �
.
Òàê êàê x y~ , òî �k y z( ) � . Àíàëîãè÷íî èç x y
~ ñëåäóåò, ÷òî z yk� � ( )
. Òàêèì
îáðàçîì, � �k ky z y( ) ( )� �
, îòêóäà � �k ky y( ) ( )�
, à çíà÷èò, è y y�
. Íî ðàâåí-
ñòâà íå ñóùåñòâóåò, ïîñêîëüêó y è
y ïðèíàäëåæàò ðàçíûì êëàññàì ýêâèâàëåíò-
íîñòè. Ñëåäîâàòåëüíî, y y�
, îòêóäà V V�
. Óòâåðæäåíèå äîêàçàíî.
Íåñëîæíî óáåäèòüñÿ, ÷òî ââåäåííîå íà ìíîæåñòâå � k -êëàññîâ îòíîøåíèå �
(ëåêñèêîãðàôè÷åñêè áîëüøå) ÿâëÿåòñÿ îòíîøåíèåì ñòðîãîãî ëèíåéíîãî ïîðÿäêà.
Ó÷èòûâàÿ ýòî è òîò ôàêò, ÷òî ôàêòîð-ìíîæåñòâî F M k� / � êîíå÷íîå âñëåä-
ñòâèå êîíå÷íîñòè ìíîæåñòâà E Gn
k
� ( ) , ìîæåì ïðåäñòàâèòü ôàêòîð-ìíîæåñòâî F
â âèäå êîðòåæà � k -êëàññîâ, óïîðÿäî÷åííûõ ïî âîçðàñòàíèþ:
F V V V F� ( , , ..., )| |1 2 , V Vi i� 1 � � �i J F| | 1 . (1)
Äàëåå ðàññìîòðèì ìíîãîãðàííèê M òàêîé, ÷òî äëÿ ëþáîãî x M� èìååò ìåñ-
òî � �k n
kx G( ) ( )�� . Êàê ïîêàçàíî â [8], äëÿ ëþáîé òî÷êè � �k n
kx G( ) ( )�� òàêîé,
÷òî � �l n
lx E G( ) ( )� (l k� ), íàéäóòñÿ òàêèå òî÷êè
�x x E Gn
k, ( )� , ÷òî
� � �l l lx x x( ) ( ) ( )
�
� ,
x x xk� �� ( ) .
Óòâåðæäåíèå 3. Ïóñòü V M k� / � — íåêîìáèíàòîðíûé � k -êëàññ; �( )x —
íàèìåíüøåå ÷èñëî òàêîå, ÷òî äëÿ òî÷êè x V� âûïîëíÿåòñÿ óñëîâèå
� � �
�
( )
( )( ) ( )x n
xx E G
. Òîãäà � �x x V, ~ � �( ) (~ )x x� .
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì äëÿ îïðåäåëåííîñòè � �( ) (~ )x x� . Ïîñêîëü-
êó V — íåêîìáèíàòîðíûé � k -êëàññ, äëÿ ëþáîãî x V� �( )x k� . Åñëè �( )x �1 , òî
èç ïðåäïîëîæåíèÿ òàêæå �(~ )x �1 .
Ïóñòü òåïåðü �( )x �1 . Îáîçíà÷èì l x� ��( ) 1 , òîãäà � �l n
lx E G( ) ( )� ; ïóñòü
òàêæå s — ïåðâàÿ ðàçëè÷íàÿ êîîðäèíàòà òî÷åê x è ~x , ò.å. x xs s� ~ , è åñëè s�1 , òî
� �s sx x� ��1 1( ) (~ ) . Ïðåäïîëîæèì, ÷òî s l� . Ïîñêîëüêó x xs s� ~ , èìååò ìåñòî îäíî
èç äâóõ íåðàâåíñòâ: x xs s� ~ èëè x xs s� ~ .
Ðàññìîòðèì ñëó÷àé, êîãäà x xs s� ~ . Èç ñâîéñòâ ìíîæåñòâà E Gn
k
� ( ) ñëåäóåò,
÷òî ñóùåñòâóåò òàêàÿ òî÷êà
�x E Gn
k
� ( ) , ÷òî �k x x( ) �
è � �l lx x( ) ( )�
. Òàê êàê
s l� , òî
� �x x xs s s
~ , ïðè÷åì s — ïåðâàÿ ðàçëè÷íàÿ êîîðäèíàòà òî÷åê
x è ~x . Òà-
êèì îáðàçîì,
x xk� � (~ ) . Ó÷èòûâàÿ òàêæå �k x x(~ ) �
, èìååì, ÷òî òî÷êà
�x E Gn
k
� ( ) óäîâëåòâîðÿåò ñîîòíîøåíèþ � �k kx x x( ) (~ )� �
, ÷òî ïðîòèâîðå÷èò
� k -ýêâèâàëåíòíîñòè òî÷åê x è ~x .
 ñëó÷àå, êîãäà x xs s� ~ , èìååì
� �x x xs s x
~ , ãäå òî÷êà x E Gn
k
� � ( ) òàêîâà, ÷òî
x xk� � ( ) , � �s sx x( ) ( )�
. Çíà÷èò, x xk
� � (~ ) è èìååò ìåñòî ñîîòíîøåíèå
� �k kx x x(~ ) ( )� �
, ÷òî ïðîòèâîðå÷èò x x~ ~ .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 139
Òàêèì îáðàçîì, ïðåäïîëîæåíèå íåïðàâèëüíî, ò.å. s l� , à çíà÷èò,
� �l lx x( ) (~ )� . Ñëåäîâàòåëüíî, � � �l l n
lx x E G(~ ) ( ) ( )� � , ò.å. � �(~ ) ( )x x� . Ó÷èòû-
âàÿ, ÷òî ïî ïðåäïîëîæåíèþ � �( ) (~ )x x� , èìååì � �( ) (~ )x x� . Óòâåðæäåíèå
äîêàçàíî.
Èç óòâåðæäåíèÿ ñëåäóåò, ÷òî íàèìåíüøåå ÷èñëî � òàêîå, ÷òî
� � �
�( ) ( )x E Gn
, ÿâëÿåòñÿ õàðàêòåðèñòèêîé íåêîìáèíàòîðíîãî � k -êëàññà. Î÷å-
âèäíî òàêæå, ÷òî åñëè V — êîìáèíàòîðíûé � k -êëàññ, òî äëÿ ëþáîãî � � Jk êîð-
òåæ � � ( )x — ýëåìåíò ìíîæåñòâà E Gn�
� ( ) .
Îïðåäåëåíèå 5. Ðàíãîì íåêîìáèíàòîðíîãî � k -êëàññà V ñ ïðåäñòàâèòåëåì x
åñòü íàèìåíüøåå ÷èñëî � òàêîå, ÷òî êîðòåæ � � ( )x íå ÿâëÿåòñÿ ýëåìåíòîì ìíî-
æåñòâà E Gn�
� ( ) ; ðàíã êîìáèíàòîðíîãî � k -êëàññà ðàâåí k 1 .
ÏÎÈÑÊ ÊÎÌÁÈÍÀÒÎÐÍÛÕ �k -ÊËÀÑÑÎÂ
 àëãîðèòìàõ ìåòîäà ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè â êà-
÷åñòâå âñïîìîãàòåëüíûõ èñïîëüçóþòñÿ çàäà÷è ïîèñêà êîìáèíàòîðíûõ � k -êëàñ-
ñîâ, áëèæàéøèõ ê çàäàííîìó êëàññó V â ïîðÿäêå (1) ñëåâà è ñïðàâà, ò.å.
� k -êëàññîâ � �V è � �V , óäîâëåòâîðÿþùèõ ñîîòâåòñòâåííî óñëîâèÿì:
V V� � � �
�
� � �
V F V V V VE ( )� � ;
V V� � � �
�
� � �
V F V V V VE ( )� � .
 ïðèâåäåííûõ íèæå àëãîðèòìàõ ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ íåîáõî-
äèìî òàêæå ó÷èòûâàòü äîïîëíèòåëüíûå îãðàíè÷åíèÿ, âîçíèêàþùèå â ïðîöåññå
ðåøåíèÿ çàäà÷è è ôîðìèðóþùèå íåêîòîðîå âûïóêëîå ïîäìíîæåñòâî Q M� .
 ñâÿçè ñ ýòèì öåëåñîîáðàçíî ñôîðìóëèðîâàòü çàäà÷è ïîèñêà � k -êëàññîâ � �V Q è
� �V Q , êîòîðûå ÿâëÿþòñÿ áëèæàéøèìè ñëåâà è ñïðàâà ê V â ïîðÿäêå (1) ñðåäè
âñåõ êîìáèíàòîðíûõ � k -êëàññîâ, èìåþùèõ íåïóñòîå ïåðåñå÷åíèå ñ ìíîæåñòâîì
Q. Îáîçíà÷èì F QE ( ) ìíîæåñòâî êîìáèíàòîðíûõ � k -êëàññîâ, êîòîðûå èìåþò íå-
ïóñòîå ïåðåñå÷åíèå ñ ìíîæåñòâîì Q . Ñ ó÷åòîì ââåäåííîãî îáîçíà÷åíèÿ îïðåäå-
ëåíèÿ êëàññîâ � �V Q è � �V Q çàïèøóòñÿ ñëåäóþùèì îáðàçîì:
� � �V F QQ E ( ) , V V Q� � � �
�
� � �
V F Q V V V VE Q( )( )� � ;
� � �V F QQ E ( ) , V V Q� � � �
�
� � �
V F Q V V V VE Q( )( )� � .
Ïî àíàëîãèè ñ � �V -çàäà÷åé [8] � �V Q -çàäà÷åé íàçîâåì çàäà÷ó ïîèñêà ëåêñè-
êîãðàôè÷åñêè ìàêñèìàëüíîé òî÷êè ìíîæåñòâà � � �V QQ , à � �V Q -çàäà÷åé áóäåì
íàçûâàòü çàäà÷ó ïîèñêà ëåêñèêîãðàôè÷åñêè ìèíèìàëüíîé òî÷êè ìíîæåñòâà
� � �V QQ .
Ðàññìîòðèì ðåøåíèå � �V Q -çàäà÷è, ãäå � k -êëàññ V îïðåäåëåí òî÷êîé x M� .
Ïóñòü � � Jk . Îáîçíà÷èì
S x e S G x x x e E G e xL i i n
k
i( , ) { ( )| ( , , ..., , ) ( ),� � � �� � � ��1 2 1 } ,
S x e S G x x x e E G e xR i i n
k
i( , ) { ( )| ( , , ..., , ) ( ),� � � �� � � ��1 2 1 } .
140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
Î÷åâèäíî, ÷òî S x S xL R( , ) ( , )� �� � � ïðè � �� ( )V . Åñëè V ÿâëÿåòñÿ íå-
êîìáèíàòîðíûì � k -êëàññîì, òî S xL ( , )� � � è S xR ( , )� � � ïðè � �� ( )V . Äåé-
ñòâèòåëüíî, äëÿ x V� ñóùåñòâóþò x x E Gn
k
�, ( )� òàêèå, ÷òî x x xk
� �� ( ) è
� � �� � �� � �
� �
1 1 1( ) ( ) ( )x x x , åñëè � �1. Òîãäà
� �
x x x� � � . À ïîñêîëüêó
� �� � �( ), ( ) ( )x x E Gn
k
� , � �
�( )x E
, íè îäíîãî èç ðàâåíñòâ íå ñóùåñòâóåò. Ñëå-
äîâàòåëüíî,
�x S xL� �( , ) ,
�x S xL� �( , ) . Îòìåòèì, ÷òî ïðè � �� ( )V ìíîæåñòâà
S xL ( , )� è S xR ( , )� íåîáÿçàòåëüíî ÿâëÿþòñÿ íåïóñòûìè.
Óòâåðæäåíèå 4. Åñëè äëÿ âñåõ � � Jk ìíîæåñòâî S xL ( , )� � � , òî V — ïåð-
âûé â ïîðÿäêå (1) êîìáèíàòîðíûé � k -êëàññ.
Äîêàçàòåëüñòâî. Ïîñêîëüêó äëÿ íåêîìáèíàòîðíîãî � k -êëàññà ìíîæåñòâà
S xL ( , )� è S xR ( , )� ÿâëÿþòñÿ íåïóñòûìè ïðè � �� �( )V Jk , òî V FE� .
Ïóñòü � k -êëàññV
òàêîé, ÷òîV V
� ; x V
�
, l — èíäåêñ ïåðâîé ðàçëè÷íîé êî-
îðäèíàòû òî÷åê x
è x . Òàê êàê V FE� , òî � �l n
lx E G�
��1
1( ) ( ) � �l k{ , ..., }2 , à òîã-
äà òàêæå � �l n
lx E G�
�
�1
1( ) ( ) . Ñëåäîâàòåëüíî, l V�
�( ) .
Åñëè �( )V l
� , òî � �l n
lx E G( ) ( )
� . Ó÷èòûâàÿ, ÷òî òàêæå
�x xl l , èìååì
�x S x ll L ( , ) , ÷òî ïðîòèâîðå÷èò S xL ( , )� � � .
Ïóñòü òåïåðü �( )V l
� . Òîãäà �( )V k
� , ò.å. V FE
. Ñëåäîâàòåëüíî, ñóùåñ-
òâóåò ýëåìåíò ei ìóëüòèìíîæåñòâà òàêîé, ÷òî e S x li L�
( , ) . Òàê êàê e x xi l l�
� ,
òî òàêæå e S x li L� ( , ) , ò.å. S xL ( , )� � � ïðè � � l . Óòâåðæäåíèå äîêàçàíî.
Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî èç S xR ( , )� � � � �� Jk ñëåäóåò, ÷òîV — ïî-
ñëåäíèé â ïîðÿäêå (1) êîìáèíàòîðíûé � k -êëàññ.
Ïóñòü ìíîæåñòâî Q M� ÿâëÿåòñÿ âûïóêëûì, òî÷êà x Q� , êàê è ðàíüøå, îïðå-
äåëÿåò � k -êëàññV , ÷èñëî � � Jk òàêîå, ÷òî S xL ( , )� � � , e e e S x pi L� �max{ | ( , )} .
Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó:
�
x x
x Q
� �= lex max , x x
x Q
�
= arglex max � , (2)
x xt t� � � �t J � 1, (3)
x ei� � . (4)
Î÷åâèäíî, ÷òî çàäà÷à (2)–(4) èìååò ðåøåíèå, åñëè òîëüêî åå äîïóñòèìîå
ìíîæåñòâî íåïóñòî, òàê êàê ïî êðàéíåé ìåðå x en� � .
Óòâåðæäåíèå 5. Ðåøåíèå x
çàäà÷è (2)–(4) îïðåäåëÿåò � k -êëàññ V
, ëåêñèêî-
ãðàôè÷åñêè ìåíüøèé � k -êëàññàV , ïðè÷åì x
ÿâëÿåòñÿ ëåêñèêîãðàôè÷åñêè ìàêñè-
ìàëüíîé òî÷êîé ìíîæåñòâà V Q
� .
Äîêàçàòåëüñòâî. Î÷åâèäíî, ÷òî ðåøåíèå x
çàäà÷è (2)–(4), åñëè îíî ñóùåñò-
âóåò, èìååò âèä ( , , )x x e x xi u1 1 1� �
� �
� � �� � , ïðè÷åì òî÷êà x
ÿâëÿåòñÿ ëåêñèêî-
ãðàôè÷åñêè ìàêñèìàëüíîé èç âñåõ òî÷åê òàêîãî âèäà. Òàê êàê e S xi L� ( , )� , òî
( , ) ( )x x e E Gi n1 1� � ��� � �
� . Ó÷èòûâàÿ òàêæå, ÷òî âñëåäñòâèå óòâåðæäåíèÿ 3
� �
x V � �� �( ) ( )x x�
, ïîëó÷àåì, ÷òî x
— ëåêñèêîãðàôè÷åñêè ìàêñèìàëüíàÿ
òî÷êà ìíîæåñòâà V Q
� .
Èç e S xi L� ( , )� òàêæå ñëåäóåò, ÷òî x ei� � . Ïîñêîëüêó ïðè ýòîì
� �� �� ��
1 1( ) ( )x x , èìååì x x�
. Êðîìå òîãî, òî÷êè x è x
íå ÿâëÿþòñÿ � k -ýêâè-
âàëåíòíûìè (â ïðîòèâíîì ñëó÷àå èìåëî áû ìåñòî ñîîòíîøåíèå x x ei� ��
� ),
çíà÷èò, V V�
. Òàêèì îáðàçîì, ðåøåíèå çàäà÷è (2)–(4) îïðåäåëÿåò � k -êëàññ, ëåê-
ñèêîãðàôè÷åñêè ìåíüøèé äàííîãî. Óòâåðæäåíèå äîêàçàíî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 141
Òåîðåìà 1. Åñëè � � Jk — íàèáîëüøåå ÷èñëî, äëÿ êîòîðîãî çàäà÷à (2)–(4)
èìååò ðåøåíèå, ïðè÷åì ýòî ðåøåíèå x
îïðåäåëÿåò � k -êëàññ V
, òî íå ñóùåñòâóåò
� k -êëàññà èç ìíîæåñòâà F QE ( ) , êîòîðûé áû ðàñïîëàãàëñÿ â ïîðÿäêå (1) ìåæäó
� k -êëàññàìè V è V
.
Äîêàçàòåëüòñâî òåîðåìû ïðîâåäåì îò ïðîòèâíîãî. Ïðåäïîëîæèì, ÷òî ñó-
ùåñòâóåò � k -êëàññ V F QE� ( ) òàêîé, ÷òî V V V� �
. Ïóñòü x V Q� � , òîãäà òàê-
æå èìååò ìåñòî ñîîòíîøåíèå x x x� �
. Ó÷èòûâàÿ, ÷òî � �� �� ��
1 1( ) ( )x x , èìå-
åì � �� �� ��
1 1( ) ( )x x , à çíà÷èò, x x x ei� � �� �
� . Íî òàê êàê
x — ðåøåíèå çà-
äà÷è (2)–(4) è x x�
, òî x íå óäîâëåòâîðÿåò (4), ò.å. x ei� � .
Îäíàêî èç V FE� ñëåäóåò, ÷òî � �k n
kx E G( ) ( )� , à çíà÷èò, � � �
�( ) ( )x E Gn� .
Ïðè x x� �� ïîëó÷èì x S xL� �� ( , ) , ÷òî âñëåäñòâèå x ei� � ïðîòèâîðå÷èò òîìó,
÷òî ei — ìàêñèìàëüíûé ýëåìåíò ìíîæåñòâà S xL ( , )� .
Òàêèì îáðàçîì, x x ei� �� � . Ýòî îçíà÷àåò, ÷òî èíäåêñ l ïåðâîé ðàçëè÷íîé
êîîðäèíàòû òî÷åê x è x áîëüøå � . Òîãäà èç x xl l� (âñëåäñòâèå x x� ) è
� �l n
lx E G( ) ( )� ñëåäóåò, ÷òî x S x ll L� ( , ) . Ó÷èòûâàÿ, ÷òî â (4) ei — ìàêñèìàëü-
íûé ýëåìåíò ìíîæåñòâà S xL ( , )� , ïîëó÷àåì, ÷òî x óäîâëåòâîðÿåò (3), (4) ïðè
� � l . Ïîñêîëüêó òàêæå x Q� , çàäà÷à âèäà (2)–(4) èìååò ðåøåíèå ïðè l � � , ÷òî
ïðîòèâîðå÷èò ôàêòó, ÷òî � — íàèáîëüøåå ÷èñëî, ïðè êîòîðîì çàäà÷à (2)–(4)
èìååò ðåøåíèå. Òåîðåìà äîêàçàíà.
Èç òåîðåìû 1 ñëåäóåò, ÷òî ðåøåíèå çàäà÷è (2)–(4) ìîæíî ïîëîæèòü â îñíîâó
ðåøåíèÿ � �V Q -çàäà÷è. Äåéñòâèòåëüíî, ïóñòü � � Jk — íàèáîëüøåå ÷èñëî, äëÿ
êîòîðîãî çàäà÷à (2)–(4) èìååò ðåøåíèå x
; åñëè � �k n
kx E G( ) ( )
� , òî ñîãëàñíî òåî-
ðåìå 1 òàêæå x V Q
�� � . Åñëè � �k n
kx E G( ) ( )
, ò.å. � k -êëàññ V
, îïðåäåëåííûé
òî÷êîé x
, ÿâëÿåòñÿ íåêîìáèíàòîðíûì, òî ïîëîæèì x x�
è ñíîâà ðåøèì çàäà÷ó
âèäà (2)–(4). Ïðîöåññ çàâåðøàåòñÿ â îäíîì èç äâóõ ñëó÷àåâ:
1) êîìáèíàòîðíûì ÿâëÿåòñÿ � k -êëàññ, îïðåäåëåííûé ðåøåíèåì x
çàäà÷è
âèäà (2)–(4);
2) ïðè � �1 çàäà÷à (2)–(4) íå èìååò ðåøåíèÿ.
 ïåðâîì ñëó÷àå x
åñòü ðåøåíèå � �V Q -çàäà÷è, òàê êàê êàæäûé ñëåäóþùèé
� k -êëàññ ëåêñèêîãðàôè÷åñêè ìåíüøå ïðåäûäóùåãî, ïðè÷åì ìåæäó � k -êëàññàìè,
îïðåäåëåííûìè ðåøåíèÿìè ëþáûõ äâóõ ïîñëåäîâàòåëüíûõ çàäà÷, â ïîðÿäêå (1)
íå ñîäåðæèòñÿ � k -êëàññîâ èç F QE ( ) .
Âî âòîðîì ñëó÷àå, î÷åâèäíî, çàäà÷à âèäà (2)–(4) íå èìååò ðåøåíèÿ íè ïðè
êàêîì çíà÷åíèè � . Òîãäà íå ñóùåñòâóåò � k -êëàññîâ èç F QE ( ) , ëåêñèêîãðàôè÷åñ-
êè ìåíüøèõ äàííîãî. Äåéñòâèòåëüíî, åñëè áû ñóùåñòâîâàë � k -êëàññ V F QE� ( ) ,
ëåêñèêîãðàôè÷åñêè ìåíüøèé V , òî åãî ïðåäñòàâèòåëü x óäîâëåòâîðÿë áû óñëî-
âèþ (3) ïðè � , ðàâíîì èíäåêñó ïåðâîé ðàçëè÷íîé êîîðäèíàòû òî÷åê x è x . Êðî-
ìå òîãî, ïîñêîëüêó x x� , èìåëè áû ìåñòî ñîîòíîøåíèÿ x x� �� è � � �
�( ) ( )x E Gn� ,
òàê êàê V FE
� , âñëåäñòâèå ÷åãî ÷èñëî x � ÿâëÿëîñü áû ýëåìåíòîì ìíîæåñòâà
S x( , )� . Òàêèì îáðàçîì, ìíîæåñòâî S x( , )� áûëî áû íåïóñòûì è ñ ó÷åòîì ïðàâè-
ëà âûáîðà ýëåìåíòà ei â (4) ÷èñëî x � óäîâëåòâîðÿëî áû (4) è òî÷êà x ÿâëÿëàñü áû
äîïóñòèìîé òî÷êîé çàäà÷è (2)–(4). Ñëåäîâàòåëüíî, ñóùåñòâîâàëî áû è ðåøåíèå
çàäà÷ (2)–(4).
Òàêèì îáðàçîì, àëãîðèòì ðåøåíèÿ � �V Q -çàäà÷è èìååò ñëåäóþùèé âèä.
Øàã 1. Ïîëàãàåì íîìåð èòåðàöèè h � 0, ÷èñëî � �� ( )V , åñëè V FE
, èíà÷å
� � k .
142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
Øàã 2. Ôîðìèðóåì ìíîæåñòâî S xL ( , )� .
Øàã 3. Åñëè S xL ( , )� � �, òî ïåðåõîäèì ê øàãó 4, èíà÷å ê øàãó 5.
Øàã 4. Åñëè � �1 , òî óìåíüøàåì � íà åäèíèöó è âîçâðàùàåìñÿ ê øàãó 2,
èíà÷å çàäà÷à íå èìååò ðåøåíèÿ.
Øàã 5. Ðåøàåì çàäà÷ó (2)–(4). Åñëè îíà íå èìååò ðåøåíèÿ, òî ïåðåõîäèì
ê øàãó 4, èíà÷å îáîçíà÷èì ðåøåíèå x h è ïîëîæèì � �� ( )V h , ãäå � k -êëàññ V h
îïðåäåëÿåòñÿ òî÷êîé x h .
Øàã 6. Åñëè � � k 1 , òî x h — èñêîìàÿ òî÷êà, èíà÷å ïîëàãàåì x x h� è, óâå-
ëè÷èâ h íà åäèíèöó, ïåðåõîäèì ê øàãó 2.
Àíàëîãè÷íî îáîñíîâàí è ñôîðìóëèðîâàí àëãîðèòì ðåøåíèÿ � �V Q -çàäà÷è.
ÐÅØÅÍÈÅ ×ÀÑÒÈ×ÍÎ ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÇÀÄÀ× ÎÏÒÈÌÈÇÀÖÈÈ
ÍÀ ÐÀÇÌÅÙÅÍÈßÕ
Ðàññìîòðèì òåïåðü ðåøåíèå ëèíåéíîé óñëîâíîé ÷àñòè÷íî êîìáèíàòîðíîé åâ-
êëèäîâîé çàäà÷è ëåêñèêîãðàôè÷åñêîé ìàêñèìèçàöèè íà ðàçìåùåíèÿõ, ïîä êî-
òîðîé áóäåì ïîíèìàòü çàäà÷ó íàõîæäåíèÿ òàêîé ïàðû � �C x x( ),* * , ÷òî
C x c x
x R
j j
j
u
u
( )* �
� �
�lexmax
1
; x c x
x R
j j
j
u
u
* �
� �
�arglexmax
1
(5)
ïðè êîìáèíàòîðíîì óñëîâèè
( , ) ( )x x x E Gk n
k
1 2 � � �� � (6)
è äîïîëíèòåëüíûõ îãðàíè÷åíèÿõ
a x bij j
j
u
i
�
� �
1
, i Jm� , (7)
x j � 0 � �j Ju . (8)
Çäåñü c j , aij , bi — çàäàííûå äåéñòâèòåëüíûå ÷èñëà � �j Ju è � �i Jm .
Äëÿ ðåøåíèÿ çàäà÷è (5)–(8) ìîæíî èñïîëüçîâàòü ñ íåçíà÷èòåëüíûìè âèäîèç-
ìåíåíèÿìè àëãîðèòìû ìåòîäà ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè,
ïðåäëîæåííûå è îáîñíîâàííûå â [8, 9].
Ïóñòü ìíîãîãðàííèê M îïðåäåëÿåòñÿ äîïîëíèòåëüíûìè îãðàíè÷åíèÿ-
ìè (7), (8) ðàññìàòðèâàåìîé çàäà÷è è ñèñòåìîé íåðàâåíñòâ, êîòîðàÿ îïèñûâàåò
âûïóêëóþ îáîëî÷êó ìíîæåñòâà ðàçìåùåíèé — îáùèé ìíîãîãðàííèê ðàçìåùå-
íèé [1]:
g x gj
j
t
t
j
j� �
�
�
� � �� �
1
1
1
| | | |�
�
�
�
� �� Jk . (9)
Ïåðâûé àëãîðèòì ìåòîäà ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè
èñïîëüçóåòñÿ äëÿ ðåøåíèÿ ëèíåéíûõ óñëîâíûõ çàäà÷ îïòèìèçàöèè íà ðàçìåùå-
íèÿõ ïðè óñëîâèè ïðèíàäëåæíîñòè çíà÷åíèé öåëåâîé ôóíêöèè íåêîòîðîìó äèñ-
êðåòíîìó ìíîæåñòâó A (ýëåìåíòû ìíîæåñòâà áóäåì ñ÷èòàòü óïîðÿäî÷åííûìè ïî
âîçðàñòàíèþ).  ýòîì ñëó÷àå ýêñòðåìàëü çàäà÷è (5)–(8) ìîæåò íàõîäèòüñÿ òîëüêî
íà îäíîé ãèïåðïëîñêîñòè âèäà
c xj j
j
u
�
� �
1
� , (10)
ãäå � � A .
Ïóñòü � �C x x(~ ), ~ — ðåøåíèå çàäà÷è (5), (7)–(9), � h — íàèáîëüøèé ýëåìåíò
ìíîæåñòâà A òàêîé, ÷òî C x h(~ ) � � . Ðàññìîòðèì çàäà÷ó ïîèñêà ïàðû (5) ïðè óñëî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 143
âèÿõ (7)–(9):
c xj j
j
u
h
�
� �
1
� . (11)
Êàê ïîêàçàíî â [8], ýêñòðåìàëü x * ÿâëÿåòñÿ ëåêñèêîãðàôè÷åñêè ìàêñèìàëü-
íîé òî÷êîé ìíîãîãðàííèêà M h( )� , êîòîðûé îïðåäåëÿåòñÿ óñëîâèÿìè (7)–(10).
Åñëè ïðè ýòîì � �k n
kx E G( ) ( )* � , òî ïîëó÷åíî ðåøåíèå èñõîäíîé çàäà÷è (5)–(7).
 ïðîòèâíîì ñëó÷àå ðåøèì � �V
M h( )�
-çàäà÷ó, ãäå � k -êëàññ V îïðåäåëÿåòñÿ òî÷-
êîé x * . Åñëè çàäà÷à íå èìååò ðåøåíèÿ, òî ôàêòîð-ìíîæåñòâî M h
k( ) /� � íå ñî-
äåðæèò êîìáèíàòîðíûõ � k -êëàññîâ. Ýòî îçíà÷àåò, ÷òî íå ñóùåñòâóåò äîïóñòè-
ìûõ òî÷åê çàäà÷è (5)–(8), äîñòàâëÿþùèõ öåëåâîé ôóíêöèè çíà÷åíèå � h .  ýòîì
ñëó÷àå çàìåíèì � h ïðåäûäóùèì çíà÷åíèåì èç ìíîæåñòâà A è ïîâòîðèì ðåøåíèå
çàäà÷è âèäà (7)–(9), (11).
Ïóñòü x
— ðåøåíèå � �V
M h( )�
-çàäà÷è. Òîãäà äëÿ ëþáîé äîïóñòèìîé òî÷êè x
çàäà÷è (5)–(8), äëÿ êîòîðîé C x h( )
� � , èìååò ìåñòî ñîîòíîøåíèå x x�
. Ó÷èòûâàÿ
òàêæå, ÷òî íå ñóùåñòâóåò äîïóñòèìûõ òî÷åê, äëÿ êîòîðûõ çíà÷åíèå öåëåâîé
ôóíêöèè áîëüøå � h , ïîëó÷àåì, ÷òî �
�C x x( ), ÿâëÿåòñÿ ðåøåíèåì çàäà÷è (5)–(8).
Åñëè â ïðîöåññå óìåíüøåíèÿ � h çàäà÷à (5), (7)–(9), (11) îêàæåòñÿ íåðàçðåøè-
ìîé, òî, î÷åâèäíî, èñõîäíàÿ çàäà÷à (5)–(8) òàêæå íå èìååò ðåøåíèÿ.
Äàëåå ïðèâåäåí ïåðâûé àëãîðèòì ðåøåíèÿ ëèíåéíîé óñëîâíîé ÷àñòè÷íî
êîìáèíàòîðíîé åâêëèäîâîé çàäà÷è ëåêñèêîãðàôè÷åñêîé ìàêñèìèçàöèè íà ðàçìå-
ùåíèÿõ.
Àëãîðèòì 1
Øàã 1. Ïîëàãàåì íîìåð èòåðàöèè h � 0 .
Øàã 2. Ðåøàåì çàäà÷ó ïîèñêà ïàðû (5) ïðè óñëîâèÿõ (7)–(9). Åñëè îíà íå
èìååò ðåøåíèÿ, òî íå èìååò ðåøåíèÿ è èñõîäíàÿ çàäà÷à (5)–(8), èíà÷å îáîçíà÷èì
ðåøåíèå � �� h hx, .
Øàã 3. Åñëè � h A� , òî ïåðåõîäèì ê øàãó 6, èíà÷å ê øàãó 4.
Øàã 4. Óâåëè÷èâàÿ íîìåð h èòåðàöèè íà åäèíèöó, ïîëàãàåì � h ðàâíûì áëè-
æàéøåìó ñëåâà ýëåìåíòó ìíîæåñòâà A .
Øàã 5. Ðåøàåì çàäà÷ó ïîèñêà ïàðû (5) ïðè óñëîâèÿõ (7)–(9), (11). Åñëè îíà
íå èìååò ðåøåíèÿ, òî òàêæå íå èìååò ðåøåíèÿ èñõîäíàÿ çàäà÷à, èíà÷å ïóñòü
� �� h hx, – ðåøåíèå.
Øàã 6. Åñëè x h óäîâëåòâîðÿåò óñëîâèþ (6), òî � �� h hx, – ðåøåíèå èñõîäíîé
çàäà÷è.
Øàã 7. Ðåøàåì � �V h
M h( )�
-çàäà÷ó, ãäå M h( )� — ìíîãîãðàííèê, êîòîðûé
îïðåäåëÿåòñÿ óñëîâèÿìè (7)–(10), � k -êëàññ V h èìååò ñâîèì ïðåäñòàâèòåëåì òî÷-
êó x h .
Øàã 8. Åñëè � �V h
M h( )�
-çàäà÷à íå èìååò ðåøåíèÿ, òî ïîëàãàåì � h ðàâíûì
ïðåäûäóùåìó çíà÷åíèþ ìíîæåñòâà A è ïåðåõîäèì ê øàãó 4, èíà÷å èñõîäíàÿ çà-
äà÷à ðåøåíà è åå ðåøåíèåì ÿâëÿåòñÿ ïàðà �
�� h x, , ãäå x
– ðåøåíèå
� �V h
M h( )�
-çàäà÷è.
Âòîðîé àëãîðèòì ìåòîäà ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè
èñïîëüçóåò íàïðàâëåííûé ïåðåáîð êîìáèíàòîðíûõ � k -êëàññîâ â ïîðÿäêå ëåêñè-
144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
êîãðàôè÷åñêîãî âîçðàñòàíèÿ è ëåêñèêîãðàôè÷åñêîãî óáûâàíèÿ, êîòîðûé ïðåäó-
ñìàòðèâàåò ðåøåíèå ïîñëåäîâàòåëüíîñòè ñîîòâåòñòâåííî � �V Q - è � �V Q -çàäà÷.
Ïðè ýòîì èç ðàññìîòðåíèÿ ñëåäóåò èñêëþ÷èòü òå � k -êëàññû, ïðåäñòàâèòåëè êîòî-
ðûõ äîñòàâëÿþò öåëåâîé ôóíêöèè çíà÷åíèÿ ìåíüøèå, ÷åì ïîëó÷åííûå íà
ïðåäûäóùèõ èòåðàöèÿõ, ò.å. íå óäîâëåòâîðÿþò óñëîâèþ
c xj j
j
u
h
�
� �
1
� , (12)
ãäå � h — íàèáîëüøåå çíà÷åíèå öåëåâîé ôóíêöèè, ïîëó÷åííîå íà ïðåäûäóùèõ
èòåðàöèÿõ.
Îòìåòèì, ÷òî ïðè ðåøåíèè ïîëíîñòüþ êîìáèíàòîðíûõ çàäà÷ çíà÷åíèå öåëå-
âîé ôóíêöèè äëÿ êîìáèíàòîðíîãî � k -êëàññà îïðåäåëÿåòñÿ îäíîçíà÷íî, òàê êàê
òàêîé êëàññ ñîñòîèò èç îäíîé òî÷êè.  ñëó÷àå îáîáùåííîãî îòíîøåíèÿ � k -ýêâè-
âàëåíòíîñòè êîìáèíàòîðíûé êëàññ ñîäåðæèò ìíîæåñòâî òî÷åê, ïðè÷åì çíà÷åíèÿ
öåëåâîé ôóíêöèè â ýòèõ òî÷êàõ ìîãóò áûòü ðàçëè÷íûìè. Ïîýòîìó äëÿ íàõîæäå-
íèÿ ìàêñèìàëüíîãî çíà÷åíèÿ öåëåâîé ôóíêöèè äëÿ � k -êëàññà V ñ èçâåñòíûì
ïðåäñòàâèòåëåì x ðåøèì çàäà÷ó íàõîæäåíèÿ ïàðû (5) ïðè óñëîâèè (7) è
x xt t� � �t Jk . (13)
Åñëè öåëåâàÿ ôóíêöèÿ C x( ) îãðàíè÷åíà ñâåðõó íà ìíîæåñòâå M , òî òàêæå
ñóùåñòâóåò ìàêñèìóì C x( )* ýòîé ôóíêöèè íà íåïóñòîì ìíîæåñòâå (7)–(9), (13),
ïðè÷åì C x C x h( ) ( )* � � � , ò.å. ìàêñèìàëü óäîâëåòâîðÿåò óñëîâèþ (12).
Ïåðåáîð êîìáèíàòîðíûõ � k -êëàññîâ â ïîðÿäêå ëåêñèêîãðàôè÷åñêîãî âîçðàñ-
òàíèÿ ñ ó÷åòîì îïèñàííûõ çàìå÷àíèé íàçîâåì l -ïåðåáîðîì, à ïåðåáîð â ïîðÿäêå
ëåêñèêîãðàôè÷åñêîãî óáûâàíèÿ — l � -ïåðåáîðîì.
Ðàññìîòðèì ñíà÷àëà l -ïåðåáîð. Ïóñòü òî÷êà x Mh � îïðåäåëÿåò êîìáèíà-
òîðíûé � k -êëàññ V h , ïðè÷åì x h ÿâëÿåòñÿ ëåêñèêîãðàôè÷åñêîé ìàêñèìàëüþ
ôóíêöèè C x( ) íà ìíîæåñòâå V h . Ïóñòü òàêæå ìíîæåñòâî Q M� îïðåäåëÿåòñÿ
óñëîâèÿìè (7)–(9), (12), ãäå � h hC x� ( ) . Ðåøèì � �V h
Q -çàäà÷ó è, èñïîëüçóÿ åå
ðåøåíèå x h , íàéäåì ïàðó (5) ïðè óñëîâèÿõ (7)–(9), (13). Ïîñêîëüêó x V h
Q
* �� � ,
òî x * óäîâëåòâîðÿåò (12) è äëÿ ëþáîé òî÷êè x V h� èìååò ìåñòî x x*
� . Ó÷èòû-
âàÿ, ÷òî x h — ëåêñèêîãðàôè÷åñêàÿ ìàêñèìàëü ôóíêöèè C x( ) íà ìíîæåñòâå V h ,
èìååì, ÷òî äëÿ ëþáîãî x V h� ëèáî C x C x( ) ( )* � , ëèáî C x C x( ) ( )* � , íî ïðè
ýòîì x x*
� . Êàê è â [8], áóäåì â òàêîì ñëó÷àå ãîâîðèòü, ÷òî x * ÿâëÿåòñÿ ëó÷øèì
äîïóñòèìûì ðåøåíèåì çàäà÷è (5)–(7), ÷åì x , è îáîçíà÷àòü ýòîò ôàêò x x* . Òà-
êèì îáðàçîì, x x* äëÿ ëþáîãî x V h� .
Òî÷êà x * êàê ðåøåíèå çàäà÷è (5), (7)–(9), (13) òàêæå ÿâëÿåòñÿ ëó÷øèì äîïóñ-
òèìûì ðåøåíèåì, ÷åì ëþáîé ïðåäñòàâèòåëü � k -êëàññà � �V h
Q . Êðîìå òîãî, íå
ñóùåñòâóåò òàêèõ êîìáèíàòîðíûõ � k -êëàññîâ, ðàñïîëàãàþùèõñÿ ìåæäó V h è
� �V h
Q â ïîðÿäêå (1), ïðåäñòàâèòåëè êîòîðûõ äîñòàâëÿþò öåëåâîé ôóíêöèè çíà-
÷åíèå íå ìåíüøå C x( )* . Ïîñêîëüêó òàêæå x x* ~ äëÿ âñåõ ~x V h� , äëÿ ëþáîé òî÷-
êè x , óäîâëåòâîðÿþùåé ñîîòíîøåíèÿì (6), (7) è x x x h*
� � , èìååì x x* .
Ïðîäîëæàÿ l -ïåðåáîð, óâåëè÷èì h íà åäèíèöó è âíîâü ðåøèì � �V h
Q -çàäà-
÷ó, âçÿâ â êà÷åñòâå íà÷àëüíîãî � k -êëàññ, îïðåäåëåííûé òî÷êîé x * , � h C x� ( )* ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 145
çàòåì ðåøèì çàäà÷ó (5), (7)–(9), (13). Ïðîäîëæèì îïèñàííûé ïðîöåññ äî ìîìåí-
òà, êîãäà ïðè íåêîòîðîì �
� �V h
Q -çàäà÷à áóäåò íåðàçðåøèìà. Ýòî îçíà÷àåò, ÷òî
íå ñóùåñòâóåò êîìáèíàòîðíûõ � k -êëàññîâ, êîòîðûå ëåêñèêîãðàôè÷åñêè áîëüøå
V h è èìåþò ïðåäñòàâèòåëÿ, äîñòàâëÿþùåãî öåëåâîé ôóíêöèè çíà÷åíèå
áîëüøå �
.
Ïîñêîëüêó òàêæå íå ñóùåñòâóåò äîïóñòèìûõ òî÷åê çàäà÷è (5)–(7), êîòîðûå
ðàñïîëàãàþòñÿ â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå ìåæäó òî÷êàìè x h è x
(ëåêñèêî-
ãðàôè÷åñêèé ìàêñèìóì öåëåâîé ôóíêöèè íà V h ) è ïðè ýòîì ÿâëÿþòñÿ ëó÷øèì
äîïóñòèìûì ðåøåíèåì, ÷åì x
, òî÷êà x
— ëåêñèêîãðàôè÷åñêàÿ ìàêñèìàëü ôóíê-
öèè C x( ) ïðè óñëîâèÿõ (6), (7) è x x h
� .
Ïðèâåäåì ôîðìàëüíîå èçëîæåíèå àëãîðèòìà l -ïåðåáîðà, íà÷èíàÿ ñ òî÷êè
x V0 0� , ïðè÷åì x 0 — ëåêñèêîãðàôè÷åñêàÿ ìàêñèìàëü ôóíêöèè C x( ) íà ìíîæåñ-
òâå V 0 .
Àëãîðèòì l
-ïåðåáîðà
Øàã 1. Ïîëàãàåì íîìåð èòåðàöèè h � 0 .
Øàã 2. Ðåøàåì � �V h
Q -çàäà÷ó, ãäå ìíîæåñòâî Q M� îïðåäåëÿåòñÿ óñëîâèÿìè
(7)–(9), (12). Åñëè � �V h
Q -çàäà÷à íå èìååò ðåøåíèÿ, òî ïåðåáîð çàâåðøåí è ïàðà
� �� h hx, ÿâëÿåòñÿ åãî ðåçóëüòàòîì, èíà÷å ïóñòü x h — ðåøåíèå � �V h
Q -çàäà÷è.
Øàã 3. Ðåøàåì çàäà÷ó âèäà (5), (7)–(9), (13), ïóñòü � � � h hx1 1, — åå ðåøåíèå.
Øàã 4. Óâåëè÷èâ h íà åäèíèöó, ïåðåõîäèì ê øàãó 2.
 ñëó÷àå l� -ïåðåáîðà â ðåçóëüòàòå ðåøåíèÿ � �V Q -çàäà÷è áóäåò ïîëó÷åíà
òî÷êà x * , ëåêñèêîãðàôè÷åñêè ìåíüøàÿ äàííîé, ïîýòîìó äëÿ ïîëó÷åíèÿ ëó÷øåãî
äîïóñòèìîãî ðåøåíèÿ íåîáõîäèìî, ÷òîáû çíà÷åíèå öåëåâîé ôóíêöèè â òî÷êå x *
áûëî ñòðîãî áîëüøå � h . Ñ ó÷åòîì ýòîãî ïðèâåäåì àëãîðèòì l� -ïåðåáîðà.
Àëãîðèòì l
� -ïåðåáîðà
Øàã 1. Ïîëàãàåì íîìåð èòåðàöèè h � 0 .
Øàã 2. Ðåøàåì � �V h
Q -çàäà÷ó, ãäå ìíîæåñòâî Q M� îïðåäåëÿåòñÿ óñëîâèÿìè
(7)–(9), (12). Åñëè � �V h
Q -çàäà÷à íå èìååò ðåøåíèÿ, òî ïåðåáîð çàâåðøåí è ïàðà
� �� h hx, ÿâëÿåòñÿ åãî ðåçóëüòàòîì, èíà÷å ïóñòü x h — ðåøåíèå � �V h
Q -çàäà÷è.
Øàã 3. Ðåøàåì çàäà÷ó (5), (7)–(9), (13), ïóñòü � �~, ~� x — åå ðåøåíèå.
Øàã 4. Åñëè ~� �� h , òî ïîëîæèì � �h �1 ~, x xh �1 ~, èíà÷å � �h h �1 ,
x xh h �1 .
Øàã 5. Óâåëè÷èâ h íà åäèíèöó, ïåðåõîäèì ê øàãó 2.
Ðàññóæäåíèÿ, àíàëîãè÷íûå ïðîâåäåííûì äëÿ l -ïåðåáîðà, ïîêàçûâàþò, ÷òî
òî÷êà, ïîëó÷åííàÿ â ðåçóëüòàòå l� -ïåðåáîðà, ÿâëÿåòñÿ ëåêñèêîãðàôè÷åñêîé ìàê-
ñèìàëüþ ôóíêöèè C x( ) ïðè óñëîâèÿõ (6), (7) è x x�
0 .
Òàêèì îáðàçîì, ñ èñïîëüçîâàíèåì àëãîðèòìîâ l - è l� -ïåðåáîðà ìîæíî
ïðåäëîæèòü ñëåäóþùèé àëãîðèòì ðåøåíèÿ çàäà÷è (5)–(8).
Àëãîðèòì 2
Øàã 1. Ðåøàåì çàäà÷ó ïîèñêà ïàðû (5) ïðè óñëîâèÿõ (7)–(9). Åñëè îíà íå
èìååò ðåøåíèÿ, òî íå èìååò ðåøåíèÿ è èñõîäíàÿ çàäà÷à (5)–(8), èíà÷å ïóñòü ýêñ-
òðåìàëü x îïðåäåëÿåò � k -êëàññ V M k� / � .
146 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
Øàã 2. Åñëè � �k n
kx E G( ) ( )� , òî � �C x x( ), — ðåøåíèå çàäà÷è (5)–(8), èíà÷å
ïåðåõîäèì ê øàãó 3.
Øàã 3. Ðåøàåì � �V M - è � �V M -çàäà÷è.
Øàã 4. Åñëè íè îäíà èç çàäà÷ íå èìååò ðåøåíèÿ, òî íå èìååò ðåøåíèÿ è èñ-
õîäíàÿ çàäà÷à, èíà÷å ïåðåõîäèì ê øàãó 5.
Øàã 5. Åñëè � �V M -çàäà÷à íå èìååò ðåøåíèÿ, à � �V M -çàäà÷à èìååò ðåøåíèå
x , òî îñóùåñòâëÿåì l -ïåðåáîð, â êîòîðîì íà÷àëüíîé òî÷êîé x 0 ÿâëÿåòñÿ ðåøå-
íèå çàäà÷è (5), (7)–(9), (13), è ïåðåõîäèì ê øàãó 13.
Øàã 6. Åñëè � �V M -çàäà÷à íå èìååò ðåøåíèÿ, à � �V M -çàäà÷à èìååò ðåøåíèå
x , òî îñóùåñòâëÿåì l� -ïåðåáîð, â êîòîðîì íà÷àëüíîé òî÷êîé x 0 ÿâëÿåòñÿ ðåøå-
íèå çàäà÷è (5), (7)–(9), (13), è ïåðåõîäèì ê øàãó 13.
Øàã 7. Ïóñòü x 1 è x 2 — ðåøåíèÿ ñîîòâåòñòâåííî � �V M - è � �V M -çàäà÷. Ðå-
øèì çàäà÷è âèäà (5), (7)–(9), (13) äëÿ x x� 1 è x x� 2 . Ïóñòü x1 è x 2 ñîîòâåò-
ñòâåííî ðåøåíèÿ ýòèõ çàäà÷.
Øàã 8. Åñëè x1 ÿâëÿåòñÿ ëó÷øèì äîïóñòèìûì ðåøåíèåì, ÷åì x 2 , òî ïåðåõî-
äèì ê øàãó 9, èíà÷å ê øàãó 11.
Øàã 9. Ïîëàãàåì � 0 1� C x( ) è îñóùåñòâëÿåì l -ïåðåáîð, íà÷èíàÿ ñ òî÷êè
x1. Ïóñòü ïàðà �
�� , x ïîëó÷åíà â ðåçóëüòàòå ýòîãî ïåðåáîðà.
Øàã 10. Îñóùåñòâëÿåì l� -ïåðåáîð, íà÷èíàÿ ñ òî÷êè x 2 , ñ ó÷åòîì ïîëó÷åí-
íîãî íà ïðåäûäóùåé èòåðàöèè çíà÷åíèÿ �
, è ïåðåõîäèì ê øàãó 13.
Øàã 11. Ïîëàãàåì � 0 2� C x( ) è îñóùåñòâëÿåì l� -ïåðåáîð, íà÷èíàÿ ñ òî÷êè
x1. Ïóñòü ïàðà �
�� , x ïîëó÷åíà â ðåçóëüòàòå ýòîãî ïåðåáîðà.
Øàã 12. Îñóùåñòâëÿåì l -ïåðåáîð, íà÷èíàÿ ñ òî÷êè x1, ñ ó÷åòîì ïîëó÷åí-
íîãî íà ïðåäûäóùåé èòåðàöèè çíà÷åíèè �
, è ïåðåõîäèì ê øàãó 13.
Øàã 13. Ðåøåíèåì èñõîäíîé çàäà÷è (5)–(7) ÿâëÿåòñÿ ïàðà, ïîëó÷åííàÿ â ðå-
çóëüòàòå ïåðåáîðà.
Íåäîñòàòêîì ðàññìîòðåííûõ âûøå àëãîðèòìîâ ÿâëÿåòñÿ òî, ÷òî â ñëó÷àå èõ
îñòàíîâêè íà íåêîòîðîé èòåðàöèè íåâîçìîæíî îïðåäåëèòü, íàñêîëüêî áëèçêî ïî-
ëó÷åííîå ðåøåíèå ê îïòèìàëüíîìó. Äàëåå ïðåäëîæåí ïðèáëèæåííûé àëãîðèòì
ìåòîäà ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè, ïîçâîëÿþùèé ïîëó-
÷èòü äîïóñòèìîå ðåøåíèå, äëÿ êîòîðîãî çíà÷åíèå öåëåâîé ôóíêöèè îòëè÷àåòñÿ
îò îïòèìóìà íå áîëåå ÷åì íà çàäàííóþ âåëè÷èíó.
Ïóñòü ïàðà �
�C x x( ), ÿâëÿåòñÿ ðåøåíèåì çàäà÷è (5), (7)–(9). Î÷åâèäíî, ÷òî
âåëè÷èíà C x( )
äàåò âåðõíþþ îöåíêó �h (h �1) çíà÷åíèÿ öåëåâîé ôóíêöèè íà
ìíîæåñòâå (6), (7), (8). Ïóñòü òàêæå
x — íåêîòîðàÿ äîïóñòèìàÿ òî÷êà çàäà-
÷è (5)–(8). Çíà÷åíèå C x( )
áóäåì ñ÷èòàòü íèæíåé îöåíêîé
h ôóíêöèè C x( ) íà
ìíîæåñòâå (6), (7). Ïîëîæèì �
h
h h
�
�
2
è îñóùåñòâèì ïîèñê òåõ êîìáèíàòîð-
íûõ � k -êëàññîâ, ïðåäñòàâèòåëè êîòîðûõ óäîâëåòâîðÿþò óñëîâèÿì (11), (12).
Åñëè òàêèõ êîìáèíàòîðíûõ � k -êëàññîâ íå áóäåò íàéäåíî, òî îïòèìóì öåëå-
âîé ôóíêöèè íà ìíîæåñòâå (6)–(8), î÷åâèäíî, íå ïðåâûøàåò � h , ò.å. � �h h �1 .
 ïðîòèâíîì ñëó÷àå îïðåäåëèì íîâîå çíà÷åíèå íèæíåé îöåíêè
h 1 êàê ëåêñè-
êîãðàôè÷åñêèé ìàêñèìóì ôóíêöèè C x( ) íà ìíîæåñòâå V , ãäå V — íàéäåííûé
êîìáèíàòîðíûé � k -êëàññ ñ ïðåäñòàâèòåëåì x . Äëÿ ýòîãî ðåøèì çàäà-
÷ó (7)–(9), (11)–(13).
Ïîâòîðèì ïîèñê êîìáèíàòîðíûõ � k -êëàññîâ, ïðåäñòàâèòåëè êîòîðûõ
óäîâëåòâîðÿþò óñëîâèÿì (11), (12) äëÿ íîâûõ çíà÷åíèé îöåíîê. Ïðîöåññ çàâåðøèò-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 147
ñÿ, êîãäà áóäåò äîñòèãíóòà òðåáóåìàÿ òî÷íîñòü � , ò.å. âåëè÷èíà �
h h� íå ïðåâû-
ñèò � . Ïîñêîëüêó äëÿ çíà÷åíèÿ
h öåëåâîé ôóíêöèè èçâåñòíî ñîîòâåòñòâóþùåå
äîïóñòèìîå ðåøåíèå çàäà÷è (5)–(7), îíî ñ çàäàííîé òî÷íîñòüþ äàåò ðåøåíèå çà-
äà÷è ìàêñèìèçàöèè ôóíêöèè C x( ) ïðè óñëîâèÿõ (6), (7). Îäíàêî íåîáÿçàòåëüíî
ýòà òî÷êà ÿâëÿåòñÿ ëåêñèêîãðàôè÷åñêè ìàêñèìàëüíîé èç âñåõ ìàêñèìàëåé, òàê
êàê ìîãóò ñóùåñòâîâàòü êîìáèíàòîðíûå � k -êëàññû, ïðåäñòàâèòåëè êîòîðûõ äîñ-
òàâëÿþò öåëåâîé ôóíêöèè òî æå çíà÷åíèå
h . Ïîñêîëüêó çíà÷åíèå öåëåâîé ôóíê-
öèè èçâåñòíî, çàäà÷à ñâîäèòñÿ ê íàõîæäåíèþ ëåêñèêîãðàôè÷åñêè ìàêñèìàëüíîé
äîïóñòèìîé òî÷êè ìíîãîãðàííèêà M h( )
, îïðåäåëåííîãî óñëîâèÿìè (7)–(9)
è (10) ïðè �
� h . Êàê ïîêàçàíî âûøå, äëÿ ýòîãî íåîáõîäèìî ðåøèòü çàäà÷ó
âèäà (5), (7)–(9), (11) è, åñëè åå ðåøåíèå îïðåäåëÿåò íåêîìáèíàòîðíûé � k -êëàññ
V , ðåøèòü � �V
M h( )
-çàäà÷ó.
Çàìå÷àíèå. Åñëè èçâåñòíî äèñêðåòíîå ìíîæåñòâî, êîòîðîìó ïðèíàäëåæàò
çíà÷åíèÿ öåëåâîé ôóíêöèè, òî ìîæíî ïîëó÷èòü òî÷íîå ðåøåíèå èñõîäíîé çàäà-
÷è, îñòàíîâèâ ïðîöåññ, êîãäà âåëè÷èíà � �h h� ñòàíåò íå áîëüøå ðàçíîñòè äâóõ
ñîîòâåòñòâóþùèõ ñîñåäíèõ ýëåìåíòîâ ìíîæåñòâà.
Äëÿ ïîèñêà êîìáèíàòîðíûõ � k -êëàññîâ ìîæíî èñïîëüçîâàòü àëãîðèòìû ðå-
øåíèÿ � �V Q h( ) - è � �V Q h( ) -çàäà÷, ãäå ìíîãîãðàííèê Q h( ) çàäàåòñÿ óñëîâèÿ-
ìè (7)–(8), (11), (12); � k -êëàññ V îïðåäåëÿåòñÿ òî÷êîé x
. Ðåøèì ñíà÷àëà
� �V Q h( ) -çàäà÷ó. Åñëè îíà íå èìååò ðåøåíèÿ, òî ðåøèì � �V Q h( ) -çàäà÷ó. Åñëè ïî-
ñëåäíÿÿ òàêæå íå èìååò ðåøåíèÿ, òî ýòî îçíà÷àåò, ÷òî íå ñóùåñòâóåò êîìáèíà-
òîðíûõ � k -êëàññîâ, ïðåäñòàâèòåëè êîòîðûõ ïðèíàäëåæàò ìíîæåñòâó Q h( ) .
Îòìåòèì, ÷òî åñëè íà íåêîòîðîì ïîäìíîæåñòâå Q h( ) ìíîãîãðàííèêà M
� �V Q h( ) -çàäà÷à íå èìååò ðåøåíèÿ, òî îíà, î÷åâèäíî, íå èìååò ðåøåíèÿ è äëÿ ëþ-
áîãî Q Q h� ( ) . Ýòî îçíà÷àåò, ÷òî ïðè ïîèñêå êîìáèíàòîðíûõ � k -êëàññîâ íà
ìíîæåñòâå Q ìîæíî îñóùåñòâëÿòü ðåøåíèå òîëüêî � �V Q -çàäà÷è.
Íà îñíîâàíèè èçëîæåííûõ âûøå ðàññóæäåíèé ìîæíî ñôîðìóëèðîâàòü ñëå-
äóþùèé àëãîðèòì ðåøåíèÿ çàäà÷è (5)–(8) ñ òî÷íîñòüþ � .
Àëãîðèòì 3
Øàã 1. Ðåøàåì çàäà÷ó (5), (7)–(9). Åñëè îíà íå èìååò ðåøåíèÿ, òî íå èìååò
ðåøåíèÿ è èñõîäíàÿ çàäà÷à, èíà÷å ïóñòü �
�C x x( ), — ðåøåíèå, òî÷êà x
îïðåäå-
ëÿåò � k -êëàññ V M k� / � .
Øàã 2. Ïîëàãàåì íîìåð èòåðàöèè h �1 .
Øàã 3. Ðåøàåì � �V M -çàäà÷ó. Åñëè îíà èìååò ðåøåíèå x h , òî ïîëàãàåì lh �1
è ïåðåõîäèì ê øàãó 5, èíà÷å ïîëàãàåì lh � 0 .
Øàã 4. Ðåøàåì � �V M -çàäà÷ó. Åñëè îíà íå èìååò ðåøåíèÿ, òî òàêæå íå èìååò
ðåøåíèÿ è èñõîäíàÿ çàäà÷à, èíà÷å ïóñòü x h — ðåøåíèå.
Øàã 5. Ïîëàãàåì � h C x�
( ) ,
h hC x� ( ) .
Øàã 6. Åñëè �
�h h� � , òî ïåðåõîäèì ê øàãó 12.
Øàã 7. Ïîëàãàåì �
h
h h
�
�
2
.
Øàã 8. Åñëè lh �1 , òî ðåøàåì � �V Q h( ) -çàäà÷ó, ãäå ìíîãîãðàííèê Q h( ) îïðå-
äåëÿåòñÿ óñëîâèÿìè (7)–(9), (11), (12). Åñëè çàäà÷à èìååò ðåøåíèå x h , òî ïåðåõî-
äèì ê øàãó 10.
148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
Øàã 9. Ðåøàåì � �V Q h( ) -çàäà÷ó, ãäå ìíîãîãðàííèê Q h( ) îïðåäåëÿåòñÿ óñëîâè-
ÿìè (7)–(9), (11), (12). Åñëè îíà èìååò ðåøåíèå x h , òî ïîëàãàåì lh �1 0 è ïåðåõî-
äèì ê øàãó 10, èíà÷å ïîëàãàåì � �h h �1 ,
h h �1 , l lh h �1 è ïåðåõîäèì
ê øàãó 6.
Øàã 10. Ðåøàåì çàäà÷ó (5), (7)–(9), (11)–(13). Ïóñòü � �C x x(~ ), ~ — åå ðåøåíèå.
Øàã 11. Ïîëàãàåì
h C x �1 (~ ) , � �h h �1 , óâåëè÷èâàåì h íà åäèíèöó è ïå-
ðåõîäèì ê øàãó 6.
Øàã 12. Ðåøàåì çàäà÷ó ïîèñêà ïàðû (5) íà ìíîæåñòâå M h( )
, îïðåäåëÿåìî-
ãî óñëîâèÿìè (7)–(9), (11). Ïóñòü åå ðåøåíèå
x îïðåäåëÿåò � k -êëàññ
V .
Øàã 13. Åñëè � k -êëàññ
V ÿâëÿåòñÿ êîìáèíàòîðíûì, òî �
�C x x( ), — ðåøå-
íèå èñõîäíîé çàäà÷è (5)–(7), èíà÷å ðåøåíèå çàäà÷è (5)–(7) — ïàðà � �C x x( ),* * ,
ãäå òî÷êà x * — ðåøåíèå �
�V
M h( )
.
ÇÀÊËÞ×ÅÍÈÅ
Òàêèì îáðàçîì, â ñòàòüå ïðåäëîæåíî îáîáùåíèå ââåäåííîãî ðàíåå îòíîøåíèÿ
ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè îòíîñèòåëüíî ðàçìåùåíèé, îáîñíîâàíû
àëãîðèòìû ðåøåíèÿ ÷àñòè÷íî êîìáèíàòîðíûõ çàäà÷ îïòèìèçàöèè íà ðàçìåùå-
íèÿõ, êîòîðûå îñíîâàíû íà ñâîéñòâàõ ðàññìîòðåííîãî îòíîøåíèÿ. Îïèñàííûå
èäåè ìîæíî òàêæå èñïîëüçîâàòü ïðè ðåøåíèè èíûõ êëàññîâ åâêëèäîâûõ çàäà÷
êîìáèíàòîðíîé îïòèìèçàöèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. C ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Êè¿â:
²í-ò ñèñòåìíèõ äîñë³äæåíü îñâ³òè, 1993. — 188 ñ.
2. Ã ð å á å í í è ê È . Â . , Á à ð à í î â À . Â . Îöåíêè ìèíèìóìà âûïóêëûõ ôóíêöèé íà êëàññàõ
êîìáèíàòîðíûõ ìíîæåñòâ ïåðåñòàíîâîê // Ðàä³îåëåêòðîí³êà. ²íôîðìàòèêà. Óïðàâë³ííÿ. —
2009. — ¹ 1. — Ñ. 81–87.
3. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê ³ í à Ë . Ì . Çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³¿ ç äðîáîâî-ë³í³éíèìè
ôóíêö³ÿìè. — Ê.: Íàóê. äóìêà, 2005. — 117 ñ.
4. ß ê î â ë å â Ñ . Â . , Â à ë ó é ñ ê à ÿ Î . À . Îïòèìèçàöèÿ ëèíåéíûõ ôóíêöèé íà âåðøèíàõ
ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà ñ äîïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè // Óêð. ìàò.
æóðí. — 2001. — ¹ 9. — Ñ. 1278–1280.
5. Å ì å ö Î . À . , Å ì å ö Å . Ì . Ìîäèôèêàöèÿ ìåòîäà êîìáèíàòîðíîãî îòñå÷åíèÿ â çàäà÷àõ
îïòèìèçàöèè íà âåðøèííî ðàñïîëîæåííûõ ìíîæåñòâàõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç.
— 2009. — ¹ 5. — Ñ. 129–136.
6. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à Î .  . , Í å ä î á à ÷ ³ é Ñ . Ñ . Íåçâ³äíà ñèñòåìà îáìåæåíü äëÿ
çàãàëüíîãî ìíîãîãðàííèêà ðîçì³ùåíü // Óêð. ìàò. æóðí. — 2003. — 55, ¹ 1. — Ñ. 3–11.
7. ª ì å ö ü Î . Î . , × å ð í å í ê î Î . Î . Îïòèì³çàö³ÿ äðîáîâî-ë³í³éíî¿ ôóíêö³¿ íà ðîçì³ùåííÿõ:
âëàñòèâîñò³ äîïóñòèìî¿ îáëàñò³ // Íàóê. â³ñò³ ÍÒÓÓ «Êϲ». — 2006. — ¹ 5. — Ñ. 22–29.
8. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ. — Ê.: Íàóê.
äóìêà, 2008. — 159 ñ.
9. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . Ðåøåíèå çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè
ìåòîäîì ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2004. — ¹ 5. — Ñ. 115–125.
10. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . , × å ð í å í ê î Î . À . Ðåøåíèå çàäà÷ îïòèìèçàöèè ñ äðîáíî-
ëèíåéíûìè öåëåâûìè ôóíêöèÿìè è äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè íà ðàçìåùåíèÿõ // Òàì
æå. — 2006. — ¹ 5. — Ñ. 79–85.
11. Ê î ë î ê î ë î â À . À . , Ë å â à í î â à Ò . Â . Àëãîðèòìû äåêîìïîçèöèè è ïåðåáîðà L-êëàññîâ äëÿ
ðåøåíèÿ íåêîòîðûõ çàäà÷ ðàçìåùåíèÿ // Âåñòí. Îìñê. óí-òà. — 1996. — Âûï. 1. — Ñ. 21–23.
12. Ê î ð á ó ò À . À . , Ô è í ê å ë ü ø ò å é í Þ . Þ . Äèñêðåòíîå ïðîãðàììèðîâàíèå. — Ì.: Íàóêà,
1969. — 368 ñ.
Ïîñòóïèëà 06.12.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 149
|