Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения
Запропоновано правила галуження та оцінку допустимих підмножин для задач мінімізації на множині розміщень з одиничною їх сумою лінійної цільової функції для методу гілок та меж. Доведено дві властивості оцінок, що дозволяють значно зменшувати кількість допустимих підмножин, що аналізуються. Branchin...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2012 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84126 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения / О.А. Емец, А.О. Емец // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 83-94. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859584294627835904 |
|---|---|
| author | Емец, О.А. Емец, А.О. |
| author_facet | Емец, О.А. Емец, А.О. |
| citation_txt | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения / О.А. Емец, А.О. Емец // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 83-94. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано правила галуження та оцінку допустимих підмножин для задач мінімізації на множині розміщень з одиничною їх сумою лінійної цільової функції для методу гілок та меж. Доведено дві властивості оцінок, що дозволяють значно зменшувати кількість допустимих підмножин, що аналізуються.
Branching rules and the estimation of admissible subsets for minimization problems on the set of arrangements with a constant sum of a linear objective function for the branch and bound method are proposed in the paper. Two properties of the estimates are proved. These properties allow reducing the number of the admissible subsets being analyzed.
|
| first_indexed | 2025-11-27T09:14:02Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Î.À. ÅÌÅÖ, À.Î. ÅÌÅÖ
ÐÅØÅÍÈÅ ËÈÍÅÉÍÎÉ ÇÀÄÀ×È ÅÂÊËÈÄÎÂÎÉ ÊÎÌÁÈÍÀÒÎÐÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÈ ÍÀ ÐÀÇÌÅÙÅÍÈßÕ Ñ ÓÑËÎÂÈÅÌ ÏÎÑÒÎßÍÑÒÂÀ
ÑÓÌÌÛ ÝËÅÌÅÍÒÎÂ ÐÀÇÌÅÙÅÍÈß
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ðàçìåùåíèÿ, ìåòîä âåò-
âåé è ãðàíèö.
Êîìáèíàòîðíàÿ îïòèìèçàöèÿ â ñâîåì ðàçâèòèè [1–4] ñîçäàåò àïïàðàò äëÿ ìî-
äåëèðîâàíèÿ è ðåøåíèÿ âñå áîëåå øèðîêîãî êëàññà çàäà÷. Ïðè ðåøåíèè çàäà÷
êîìáèíàòîðíîé îïòèìèçàöèè èãðîâîãî òèïà [5–7] íà ðàçìåùåíèÿõ èòåðàöèîí-
íûì ìåòîäîì âîçíèêàåò çàäà÷à ìèíèìèçàöèè ëèíåéíîé ôóíêöèè íà ìíîæåñòâå
ðàçìåùåíèé, êîãäà ñóììà ýëåìåíòîâ ðàçìåùåíèé — ïîñòîÿííàÿ âåëè÷èíà.
 çàäà÷àõ èç ðàáîòû [7] ýòîé ñóììîé ÿâëÿåòñÿ åäèíèöà, ñîäåðæàòåëüíàÿ èí-
òåðïðåòàöèÿ êîòîðîé — ñóììà âåðîÿòíîñòåé â ïîëíîé ãðóïïå ñîáûòèé.
Çàäà÷è íà ðàçìåùåíèÿõ ñ ëèíåéíûìè öåëåâûìè ôóíêöèÿìè ðàññìàòðèâàëèñü
â [3], íî ñïåöèôèêà îãðàíè÷åíèÿ ïîáóæäàåò èñêàòü áîëåå ýôôåêòèâíûå ìåòîäû
çà ñ÷åò ó÷åòà ïðèñóòñòâóþùèõ ñâîéñòâ çàäà÷è.
Ðàññìîòðèì ëèíåéíóþ óñëîâíóþ ïîëíîñòüþ êîìáèíàòîðíóþ çàäà÷ó åâêëè-
äîâîé êîìáèíàòîðíîé îïòèìèçàöèè íà ðàçìåùåíèÿõ [2]
c yj j
j
k
�
� �
1
min; (1)
y y y E Gk
k y
� �( , , ) ( )1 � �� ; (2)
y Cj
j
k
�
� �
1
, (3)
ãäå c Rj �
1
� � �j k Jk{ }1, ,� , C R� �const 1, G g gy y y
� { }
1
, ,� � — ìóëüòèìíî-
æåñòâî [2], g R J
t
y
� �
1
� , ìíîæåñòâî E Gk
�� ( ) — îáùåå ìíîæåñòâî k-ðàçìåùå-
íèé [2] èç � ýëåìåíòîâ ìóëüòèìíîæåñòâà G y , ñðåäè êîòîðûõ v ðàçíûõ.
Íå íàðóøàÿ îáùíîñòè ðàññóæäåíèé, ðàññìîòðèì çàäà÷ó, êîòîðàÿ ïîëó÷åíà
èç çàäà÷è (1)–(3) ïóòåì äåëåíèÿ âñåõ ïåðåìåííûõ y j , j Jk� , è âñåõ ýëåìåíòîâ
gt
y , t J� � , íà êîíñòàíòó C. Çàäà÷à (1)–(3) ïðèìåò âèä
c xj j
j
k
�
� �
1
min; (4)
x x x E Gk
k
� �( , , ) ( )1 � �� ; (5)
x j
j
k
�
� �
1
1 , (6)
ãäå G g g� { }1, ,� � — èçâåñòíîå ìóëüòèìíîæåñòâî, g Rj �
1. Ñâÿçü ìåæäó ýê-
âèâàëåíòíûìè çàäà÷àìè (1)–(3) è (4)–(6) óñòàíàâëèâàþò ñîîòíîøåíèÿ x C yj j�
� �j Jk ; g C gt t
y
� � �t J� .
Äàëåå èçëîæèì çàäà÷ó (4)–(6), äëÿ ðåøåíèÿ êîòîðîé èñïîëüçóåì ìåòîäîëî-
ãèþ ìåòîäà âåòâåé è ãðàíèö (ÌÂÃ). Ðàññìîòðèì îïòèìèçàöèþ ëèíåéíîé ôóíê-
öèè íà ðàçìåùåíèÿõ ïðè óñëîâèÿõ åäèíè÷íîñòè ñóììû èõ ýëåìåíòîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 83
© Î.À. Åìåö, À.Î. Åìåö, 2012
Ïðè ðåàëèçàöèè ìåòîäà âåòâåé è ãðàíèö äëÿ çàäà÷è èëè îïðåäåëåííîãî êëàññà
çàäà÷ íåîáõîäèìî îïðåäåëèòü: 1) ñïîñîá âåòâëåíèÿ ìíîæåñòâà äîïóñòèìûõ ðåøå-
íèé íà ïîäìíîæåñòâà; 2) ñïîñîá îöåíèâàíèÿ äîïóñòèìûõ ïîäìíîæåñòâ; 3) ïðàâèëà
îòñå÷åíèÿ áåñïåðñïåêòèâíûõ (èëè ïóñòûõ) ïîäìíîæåñòâ äîïóñòèìûõ ðåøåíèé.
Ðàññìîòðèì ñïîñîá âåòâëåíèÿ ìíîæåñòâà äîïóñòèìûõ ðåøåíèé íà ïîäìíî-
æåñòâà. Äëÿ ýòîãî óïîðÿäî÷èì êîýôôèöèåíòû öåëåâîé ôóíêöèè ñîãëàñíî òàêèõ
íåðàâåíñòâ:
c c c c c
l l k� � � � �1 2 1
0� � � � � � �
� � , (7)
à ýëåìåíòû ìóëüòèìíîæåñòâà G áóäåì ñ÷èòàòü (áåç îãðàíè÷åíèÿ îáùíîñòè
ðàññóæäåíèé) ïðîíóìåðîâàííûìè òàêèì îáðàçîì, ÷òîáû âûïîëíÿëèñü ñîîòíî-
øåíèÿ
g g g g gk k1 2 1
� � � . (8)
Âåòâëåíèÿ ïðåäëàãàåòñÿ âûïîëíÿòü «â ãëóáèíó», ïîñëåäîâàòåëüíî îïðåäåëÿÿ
ïåðåìåííûå â âåêòîðå x E k
� �� â ïîðÿäêå íîìåðîâ � � � �1 2 1, , , ,� l l� , à çàòåì íî-
ìåðîâ � � � �k k l l, , , ,� 1 2 1� , ãäå ïîðÿäîê îïðåäåëÿåòñÿ óñëîâèÿìè (7), ïîñëå-
äîâàòåëüíî ïðèäàâàÿ ïåðåìåííûì ñ íîìåðàìè � � �1 2, , ,� l çíà÷åíèÿ g g1 2, , ... ,
à ïåðåìåííûì ñ íîìåðàìè � � �k k l, , ,� 1 1� — ïîñëåäîâàòåëüíî ïðèäàâàÿ çíà÷å-
íèÿ g g� �, ,�1 � Åñëè äàëüíåéøåå âåòâëåíèå «â ãëóáèíó» íåâîçìîæíî (ìíîæåñòâî
ïóñòîå èëè îäíîýëåìåíòíîå), ïðîèñõîäèò âîçâðàò íà ïðåäûäóùèé óðîâåíü äåðåâà
âåòâëåíèé ñ ïðèñâîåíèåì ðàíåå îïðåäåëåííîé ïåðåìåííîé ñëåäóþùåãî çíà÷åíèÿ.
Ðàññìîòðèì ñïîñîá îöåíèâàíèÿ äîïóñòèìûõ ïîäìíîæåñòâ ðåøåíèé. Ïóñòü
â îïèñàííîì ñïîñîáå âåòâëåíèÿ ïðè îáðàçîâàíèè ïîäìíîæåñòâà Q ìíîæåñòâà äî-
ïóñòèìûõ ðåøåíèé çàäà÷è (4)–(6) óæå îïðåäåëèëèñü ïåðåìåííûå x x x
t� � �1 2
, , ,� ,
êîòîðûå áåç íàðóøåíèÿ îáùíîñòè ðàññóæäåíèé ïðîíóìåðóåì òàêèì îáðàçîì,
÷òîáû âûïîëíÿëèñü ñîîòíîøåíèÿ
c c c
t� � �1 2
� � �� . (9)
Ïåðåìåííûå, êîòîðûå îñòàëèñü íåîïðåäåëåííûìè, îáîçíà÷èì ~ , , ~x x1 � � , ãäå
t k �� . Íóìåðàöèþ ýòèõ íåîïðåäåëåííûõ ïåðåìåííûõ îñóùåñòâèì òàê, ÷òîáû
âûïîëíÿëèñü ñëåäóþùèå ñîîòíîøåíèÿ äëÿ êîýôôèöèåíòîâ ~c j öåëåâîé ôóíêöèè
ïðè ïåðåìåííûõ ~x j � �j J� :
~ ~ ~ ~ ~c c c c c1 2 10� � � � � � � � �� . (10)
Çíà÷åíèÿ t ïåðåìåííûõ
x g x gi it t� �1 1
� �, ,� , (11)
êîòîðûå îïðåäåëåíû ñîãëàñíî îïèñàííûì ïðàâèëàì âåòâëåíèÿ ïðè îáðàçîâà-
íèè ïîäìíîæåñòâà Q, îáúåäèíèì â ìóëüòèìíîæåñòâî G g gB i it
� { }
1
, ,� . Òîãäà
çíà÷åíèÿ íåîïðåäåëåííûõ ïåðåìåííûõ ìîæíî âûáèðàòü èç ìóëüòèìíîæå-
ñòâà
~
G , êîòîðîå ÿâëÿåòñÿ ðàçíîñòüþ ìóëüòèìíîæåñòâ G è GB :
~
G G GB� � �
= { }~ , , ~g g1 � � , ãäå � � �t . Ïóñòü ýëåìåíòû ìóëüòèìíîæåñòâà
~
G ïðîíóìåðîâà-
íû òàê, ÷òî
~ ~ ~g g g1 2
� � . (12)
Ïîäñòàâëÿÿ çíà÷åíèÿ ïåðåìåííûõ x x
t� �1
, ,� â öåëåâóþ ôóíêöèþ (4), ïîëó-
÷àåì ñëàãàåìîå
� ��
�
� c g
p pi
p
t
1
. (13)
Êàê èçâåñòíî, ÷èñëî â çàäà÷å ìèíèìèçàöèè ôóíêöèé F x( ) íà ìíîæåñòâå
x D� â ÌÂÃ ÿâëÿåòñÿ îöåíêîé ïîäìíîæåñòâà D Di � , åñëè
F x( ) � �x Di .
84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Òåîðåìà 1. Îöåíêîé ïîäìíîæåñòâà Q ìíîæåñòâà äîïóñòèìûõ ðåøåíèé çàäà-
÷è (4)–(6) ÿâëÿåòñÿ âåëè÷èíà
�� c* , (14)
ãäå � âû÷èñëÿåòñÿ ïî ôîðìóëå (13), à
c c g c gj
j
j j
j
j
* ~ ~ ~ ~�
�
�
�
� � �
1 1
�
�
� �
� � � (15)
ñîãëàñíî óñëîâèÿì (10), (12).
Äîêàçàòåëüñòâî. Äëÿ ïðîèçâîëüíîé òî÷êè x èç ïîäìíîæåñòâà Q çíà÷åíèå
öåëåâîé ôóíêöèè ïðèíèìàåò âèä
F x c xj j
j
( ) ~ ~�
�
��
�
1
,
(16)
ãäå ~ (~ , , ~ ) (
~
)x x x E G� �1 � � �
� , E G
�
� (
~
) — îáùåå ìíîæåñòâî �-ðàçìåùåíèé èç
ìóëüòèìíîæåñòâà
~
G . Ïîñëåäíåå èìååò � ýëåìåíòîâ, ñðåäè êîòîðûõ êîëè÷åñòâî
ðàçíûõ ýëåìåíòîâ ñîñòàâëÿåò
.
Î÷åâèäíî, ÷òî � �x Q çíà÷åíèå F x( ) íå ìåíüøå ìèíèìàëüíîãî çíà÷åíèÿ ~c
ïðàâîé ÷àñòè ôîðìóëû (16), ò.å. � �x Q ñ ó÷åòîì, ÷òî ñîãëàñíî (13) � � const,
èìååì
F x c( ) ~� � . (17)
Íàéäåì
~ min ~ ~
~ (
~
)
c c x
x E G
j j
j
�
� �
�
�
�
�
1
, (18)
âîñïîëüçîâàâøèñü òåîðåìîé 3.1 èç [2]. Ïîëó÷àåì
~ ~ ~ ~ ~c c g c gj j
j
j j
j
�
�
�
�
�
� �
1 1
�
� � � �
� �
.
(19)
Èç ñðàâíåíèÿ (19) è (15) ñëåäóåò, ÷òî ~ *c c� . Îòñþäà ñ èñïîëüçîâàíèåì íåðà-
âåíñòâà (17) èìååì ��
c F x* ( ) � �x Q, ÷òî è òðåáîâàëîñü äîêàçàòü.
Ðàññìîòðèì ïðàâèëà îòñå÷åíèÿ áåñïåðñïåêòèâíûõ èëè ïóñòûõ ïîäìíîæåñòâ
(âåðøèí äåðåâà âåòâëåíèé). Èñïîëüçóåì ñòàíäàðòíîå ïðàâèëî îòñå÷åíèÿ: åñëè
äëÿ ïîäìíîæåñòâà Q îöåíêà � �F F x0 0( ) — çíà÷åíèå öåëåâîé ôóíêöèè íà îä-
íîýëåìåíòíîì äîïóñòèìîì ìíîæåñòâå x0 , ò.å. íåêîòîðîå äîïóñòèìîå ðåøåíèå, òî
ïîäìíîæåñòâî Q îòñåêàåòñÿ (äàëüøå âåòâëåíèÿ íå ïðîèñõîäèò). Àíàëîãè÷íî åñëè
Q �
, òî íè îäíà òî÷êà â Q íå óäîâëåòâîðÿåò (6).
Åñëè F F F x0 1 1� � ( ), { }x Q1 � , ò.å. | |Q �1 , òî çíà÷åíèå F0 (òåêóùèé «ðå-
êîðä») îáíîâëÿåòñÿ (çàìåíÿåòñÿ çíà÷åíèåì F1): F F0 1:� . Íîâîå çíà÷åíèå F0 ñðàâ-
íèâàþò ñ îöåíêîé êàæäîãî äîïóñòèìîãî ìíîæåñòâà Q (êîòîðîå íå îòñå÷åíî).
Åñëè � F0 , òî ìíîæåñòâî Q îòñåêàþò.
Îáîçíà÷èì ïîäìíîæåñòâî Q äîïóñòèìûõ ðåøåíèé â ÌÂà îòíîñèòåëüíî çà-
äà÷è (4)–(6) êàê
D x x x R x g j J r J
i i k
k
i r n
r
r
j j1
1
1 1
�
�
�
� �
� �� � � � � � � �{ ( , , ) | , , ( , , ) ( );� � r k
r
kE J�
( , , ) ( )i i E Jr
r
1 � � � � },
ãäå E J
k
r
k( ) — ìíîæåñòâî r-ðàçìåùåíèé áåç ïîâòîðåíèé èç ìíîæåñòâà Jk
(ñì. [2]), � j , i j óäîâëåòâîðÿþò (9), (11) ïðè óñëîâèè r t� . Îöåíêó ýòîãî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 85
ìíîæåñòâà, îïðåäåëåííóþ ïî ôîðìóëàì (13)–(15) ïðè óñëîâèÿõ (9), (10), (12),
îáîçíà÷èì
� �
i ir
r
1
1
�
�
. Èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2. Äëÿ îöåíîê ïîäìíîæåñòâ D
i ir
r
1
1
�
�� �
è D
i i ir r
r r
1
1
� �
� �
�
�� � �
ñïðàâåäëèâî
ñîîòíîøåíèå
� � � �
�
�
i i i ir
r
r
r
1
1
1
1
�
�
�
�
, (20)
ãäå r k
� � � �r J k 1, � � � �
� �
� J J
k k1
0
1
0{ }, ( , , ) ( )� �1 � q k
q
kE J� ; ( , , )i iq1 � �
�E Jq
� �( ) , q r r� { }; � ; âåëè÷èíû i Jj � � è � � �1, ,� r óäîâëåòâîðÿþò óñëî-
âèÿì (9), (11).
Äîêàçàòåëüñòâî. Îöåíêà �
� �
i ir
r c
1
1
1 1
�
�
� ~ , ãäå ïðè óñëîâèè r t� âåëè÷èíà �1
ÿâëÿåòñÿ îöåíêîé ïîäìíîæåñòâà D
i ir
r
1
1
�
�� �
ñîãëàñíî (12), ~c1 — ýòî ~c äëÿ D
i ir
r
1
1
�
�� �
ïî ôîðìóëå (17). Îöåíêà �
�
�� �
i ir
r c
1
1
2 2
�
�
� ~ , ãäå � 2 è ~c2 äëÿ ïîäìíîæåñòâà
D
i i ir r
r r
1
1
� �
� �
�
�� � �
— ýòî ñîîòâåòñòâåííî îöåíêà ñîãëàñíî (12) è ~c — îöåíêà ñîãëàñ-
íî (17). Ïîñêîëüêó D D
i i i i ir r
r r
r
r
1
1
1
1
� �
� �
�
�
�
�
�� � � � �
, òî � � �2 1� � , à �� ~c2 — ýòî
çíà÷åíèÿ ïðè � � �k r ëèíåéíîé ôóíêöèè ~ ~c xj j
j�
�
1
�
èç ôîðìóëû (16) íà íåêîòîðîì
ðàçìåùåíèè ~ (
~
)x E G�
�
� , à ñîãëàñíî (18) ~ min ~ ~
~
c c x
x E
j j
j
1
1
�
� �
�
�
�
�
. Òîãäà èç îïðåäåëåíèÿ
ìèíèìóìà èìååì �� �~ ~c c2 1. Ïðèáàâèâ ê ïîñëåäíåìó íåðàâåíñòâó çíà÷åíèå �1
â ïðàâóþ è ëåâóþ ÷àñòè, ïîëó÷èì � � �
� � � �
�
�
i i i ir
r
r
rc c
1
1
1
1
1 1 1 2
�
�
�
�
�
�
~ ~� ,
÷òî òðàáîâàëîñü äîêàçàòü.
Äîêàæåì óòâåðæäåíèå, êîòîðîå âûðàæàåò åùå îäíî ñîîòíîøåíèå ìåæäó
îöåíêàìè äîïóñòèìûõ ïîäìíîæåñòâ. Äëÿ ýòîãî âíà÷àëå ââåäåì íåîáõîäèìûå
îáîçíà÷åíèÿ è èçëîæèì ïðåäâàðèòåëüíûå ðàññóæäåíèÿ.
Ðàññìîòðèì ñîîòíîøåíèÿ ìåæäó îöåíêàìè äîïóñòèìûõ ïîäìíîæåñòâ, êîòî-
ðûå ÿâëÿþòñÿ ïîäìíîæåñòâàìè îäíîãî äîïóñòèìîãî ïîäìíîæåñòâà è íå îäíî èç
íèõ íå ÿâëÿåòñÿ ïîäìíîæåñòâîì äðóãîãî (â îòëè÷èå îò òåîðåìû 2).
Îöåíêà ïîäìíîæåñòâà D
i i ir r
r r
1 1
1 1
�
�
� � �
ñîãëàñíî (14) èìååò âèä
�
� � �
1
1 1
1 1� �
i ir r
r r
�
�
� � r rc1 1
* , ãäå ïðè t � � ñîãëàñíî (13) � �� �r i
p
r
ic g c g
p p r r
�
� � � 1
1
1
0 1 1
,
à îöåíêà ïîäìíîæåñòâà D
i i ir r j
r r
1
1 1
�
�
� � �
ñîãëàñíî (14) �
�
� � �
j i i r j r j
r r j
r r c� �
1
1 1
�
� * ,
ãäå ïðè t � � ñîãëàñíî (13) � �� � �r j i
p
r
i ic g c g c g
p p r r j r r j
�
� � �
1
01 1
. Çäåñü
âåëè÷èíà � 0 — îäèíàêîâàÿ ÷àñòü âûðàæåíèé äëÿ � r 1 è � r j .
Ñîãëàñíî óñëîâèþ (8) èìååì ïîäìíîæåñòâà:
1) åñëè c
r�
�
1
0, òî g gi ir r j
1
, ñëåäîâàòåëüíî � � �r r j ic g
r r � � �
1 1 1
(
�
gir j
) 0 ;
� �r r j
1 ; (21)
2) åñëè c
r�
�
1
0 , òî g gi ir r j
�
1
, ñëåäîâàòåëüíî òàêæå èìååì
� �r r j �
1 0.
86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Ñðàâíèì êîýôôèöèåíòû cr 1
* è cr j
* , êîòîðûå âû÷èñëÿþòñÿ ñ ïîìîùüþ ôîð-
ìóë âèäà (14), (15), âìåñòå ñî ñëàãàåìûìè � �r �1 0 è � � �r j � ñîîòâåòñòâåííî,
÷òî íåîáõîäèìî äëÿ ñðàâíåíèÿ 1 è j . Ïóñòü G g g
B i ir
� { }
1
, ,� , G G GB0 � � è
ðàçíîñòè ìóëüòèìíîæåñòâ ïðåäñòàâèì â âèäå G G g g gir1 0 1
1 1
1
� � �
{ } { }~ , , ~
� � ,
G G g g gir j2 0 1
2 2
� � �
{ } { }~ , , ~
� � , äëÿ ýëåìåíòîâ G1, G2 âûïîëíÿåòñÿ óñëîâèå
âèäà (12). Ïóñòü � � �t , t r� 1 , t k �� , à òàêæå âûïîëíÿåòñÿ óñëîâèå (10).
Ñîãëàñíî ôîðìóëå (15) èìååì c c cr � 1 11 12
* * * , ãäå
c c gj j
j
11
1
1
* ~ ~�
�
�
�
; (22)
c c gj j
j
12
1
1
* ~ ~� �
�
�
� � � � �
� �
, (23)
à òàêæå c c cr j �
* * *
21 22 , ãäå
c c gj j
j
21
2
1
* ~ ~�
�
�
�
; (24)
c c gj j
j
22
2
1
* ~ ~� �
�
�
� � � � �
� �
. (25)
Ïðè íàõîæäåíèè cr 1
* , c11
* , c12
* ýëåìåíò gir j
ìîæåò íàõîäèòüñÿ â G1 ñðåäè
ïåðâûõ � ýëåìåíòîâ ìóëüòèìíîæåñòâà G1, ñðåäè ýëåìåíòîâ ñ íîìåðàìè � 1 ,
� 2,…, � � �� � �1 , � � �� � , ñðåäè ýëåìåíòîâ ñ íîìåðàìè � � �� � 1 ,
� � � �� � �2, , .
Îòìåòèì, ÷òî ýëåìåíòû G1 óïîðÿäî÷åíû ñîãëàñíî óñëîâèþ
~ ~ ~g g g
1
1
1
2 1
� � . (26)
Îáîçíà÷èì íàçâàííûå ïåðâîå, âòîðîå è òðåòüå ìóëüòèìíîæåñòâà ñîîòâåò-
ñòâåííî A1, B1, C1, êîòîðûå â ñóììå äàþò ìóëüòèìíîæåñòâî G1: A B1 1
�C G1 1. Àíàëîãè÷íî ïðè íàõîæäåíèè cr j
* , c21
* , c22
* ýëåìåíò gir 1
â G2 ìîæåò
íàõîäèòüñÿ â ïîäìóëüòèìíîæåñòâàõ A2 , B2 , C2 , êîòîðûå â ñóììå äàþò ìóëüòè-
ìíîæåñòâî G2 (G A B C2 2 2 2� ): A g g g2 1
2
2
2 2
� { }~ , ~ , , ~
�
�
; B g g2 1
2
2
2
�
{~ , ~ ,
� �
�
... , ~ , ~g g
� � � � � �� � � � �1
2 2 }; C g2 1
2
�
� �
{~ ,
� � �
~ , , ~g g
� � � �� � 2
2 2
� }. Ýëåìåíòû ìóëüòèìíî-
æåñòâà G2 óïîðÿäî÷åíû ñîãëàñíî óñëîâèþ
~ ~ ~g g g
1
2
2
2 2
� � . (27)
Òàêèì îáðàçîì, ïðè ñðàâíåíèè cr 1
* è cr j
* íåîáõîäèìî ðàññìîòðåòü äåâÿòü
âàðèàíòîâ îáðàçîâàíèÿ ýòèõ âûðàæåíèé, ÷òî ñîîòâåòñòâóåò äåâÿòè êîìáèíàöèÿì
ðàçìåùåíèÿ ðàçíûõ ýëåìåíòîâ gir j
è gir 1
â G1 è G2 ñîîòâåòñòâåííî. Îáîçíà÷èì
ýòè âàðèàíòû êàê A A1 2 ; A B1 2 ; A C1 2 ; B A1 2 ; B B1 2 ; B C1 2 ; C A1 2 ; C B1 2 ; C C1 2 . Ïðè
ýòîì äëÿ ñëó÷àåâ A A1 2 , B B1 2 , C C1 2 âîçìîæíû ïîäñëó÷àè, çàâèñèìûå îò òîãî,
âûïîëíÿåòñÿ óñëîâèå g gi ir r j
1
èëè óñëîâèå g gi ir r j
�
1
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 87
Òåîðåìà 3. Ìåæäó îöåíêàìè 1 è j ïîäìíîæåñòâ D
i i ir r
r r
1 1
1 1
�
�
� � �
è D
i i ir r j
r r
1
1 1
�
�
� � �
ñîîòâåòñòâåííî âî âñåõ ñëó÷àÿõ, êðîìå B C1 2 è C C1 2 , ñïðàâåäëèâî ñîîòíîøåíèå
� � � � � �
1
1 1
1 1
1
1 1�
�
i i i i i i j
r r
r r
r r j
r r
�
�
�
�
, ãäå ( , , ) ( )� �1 1
1
� r k
r
kE J
� , ( , , ,i ir1 �
i E Jr j
r
�) ( )� �
1 , ( , , ) ( )i i E Jr
r
1 1
1
�
� � � , r J
k
�
�1
0 , j � 1, j i ir k� { }2 , ,� , ÷èñëà
i Jj � � è � �1 1, ,� r óäîâëåòâîðÿþò (9), (11).  ñëó÷àå C C1 2 çíàê íåðàâåíñòâà
— ïðîòèâîïîëîæíûé: 1 � j .  ñëó÷àå B C1 2 ñïðàâåäëèâî íåðàâåíñòâî �
j ,
åñëè � � � � �
� c g g c g c g
r r j r ri i i� �
� � � �1 1 1 1 1 0( ) ~ ~ ~ , è â ïîñëåäíåì íåðà-
âåíñòâå ïðè �
0 èìååì 1 � j . Â ôîðìóëå äëÿ � ïàðàìåòð
îáîçíà÷àåò ìåñòî
ýëåìåíòà gir 1
â ìíîæåñòâå C2 (îò åãî íà÷àëà).
Äîêàçàòåëüñòâî. Ðàññìîòðèì ñîîòíîøåíèÿ ìåæäó 1 è j äëÿ âñåõ âîçìîæ-
íûõ ñëó÷àåâ.
Ïðè óñëîâèè A A1 2 , êîãäà g g
ir j ri�
�
1
, èìååì B B1 2� ; C C1 2� , à çíà÷èò
c c12 22
* *
� ,
� 1 11 21
1 2
1
1 2
1
� � � � �
� �
�c c c g g c g gj j j
j
j j j
j
* * ~ (~ ~ ) ~ (~ ~ )
�
�
�
�
�
1
2
21
1 2
1 �
� � �~ (~ ~ )c g gj j j
j
, (28)
ãäå �1 1 è � 2 îáîçíà÷àþò ìåñòà ýëåìåíòîâ gir 1
è gir j
â A1, A2 . Ñëåäîâà-
òåëüíî, ïåðâàÿ � � �1 11 12� � è òðåòüÿ � � �2 21 22� � ñóììû â (28) íóëåâûå,
ïîñêîëüêó ~ ~g gj j
1 2
� .
Çàìåòèì, ÷òî ïðè óñëîâèè A A1 2 , êîãäà g gi ir j r
�
1
, ñîãëàñíî ïðàâèëó âåò-
âëåíèÿ èìååì c
r�
�
1
0. Çàìåòèì, ÷òî ñîãëàñíî ïðàâèëó âåòâëåíèÿ è óñëîâèþ (7)
âñå ïåðåìåííûå, êîòîðûå íå îïðåäåëèëèñü, èìåþò êîýôôèöèåíòû, ìåíüøèå, ÷åì
c
r�
�
1
0, à ïðè óñëîâèè A A1 2 â (28) îíè íåîòðèöàòåëüíû, ò.å.
c c c c
r� � � �
� � � � � 1 1 1 21 2 0~ ~ ~
� . (29)
Çàìåòèì, ÷òî g gi ir r j
1
; ñëåäîâàòåëüíî,
� �� �
�
�
1 0
1
1
1
111 1 2
1
2
�
�
�
�c g c g c g
r r r ji j j i
j
~ ~ ~ � 21 12 c* ; (30)
� �� �
�
�
j i i j j
j
c g c g c g
r r j r
�
�
�0 1
2
2
121 1 1
1
2
~ ~ ~ � 22 22 c* . (31)
 ñèëó (26), (27) ýëåìåíòû G1 è G2 óïîðÿäî÷åíû. Òàê, â ðåçóëüòàòå óïîðÿäî-
÷åííîñòè G1 èìååì
~ ~ ~g g g gir j� � �1 1 21
1
2
1
1
1
�
� . (32)
Èç óïîðÿäî÷åííîñòè G2 ñëåäóåò
g g g g g
ir
� �1 1 1 2 22
2
3
2
2
2
1
2~ ~ ~ ~
� � � �
� .
(33)
Ïðè ýòîì â (32), (33) äëÿ âñåõ âîçìîæíûõ ïàð èíäåêñîâ j, j 1 èìååì ðàâåí-
ñòâî (~g j îáîçíà÷àþò îäèíàêîâûå â G1 è G2 ýëåìåíòû):
~ ~ ~g g gj j j
1
1
2
� �
. (34)
Ñëåäîâàòåëüíî, èç (32)–(34) âûòåêàåò
g g g g gi ir r j
�1 1 1 21 2 1
~ ~ ~
� � �� . (35)
88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Îòìåòèì, ÷òî ñîãëàñíî òåîðåìå 3.1 èç [2] âûðàæåíèå � � �1 0 11 21 12� � � � c*
ñîãëàñíî (30) ÿâëÿåòñÿ ìèíèìàëüíûì çíà÷åíèåì ëèíåéíîé öåëåâîé ôóíêöèè
ñ êîýôôèöèåíòàìè, óïîðÿäî÷åííûìè ñîãëàñíî (20) íà ìíîæåñòâå ïåðåñòàíîâîê
ýëåìåíòîâ â íåðàâåíñòâàõ (35). Òîãäà âûðàæåíèå � � �j c� � � �0 12 22 22
* , êîòî-
ðîå ìîæíî ðàññìàòðèâàòü êàê çíà÷åíèå òàêîé æå öåëåâîé ôóíêöèè, íî â äðóãîé
ïåðåñòàíîâêå ýëåìåíòîâ (35), ñîãëàñíî îïðåäåëåíèþ ìèíèìóìà íå ìîæåò áûòü
ìåíüøå � � �1 0 11 21 12� � � � c* ; çíà÷èò, � � �j c� � � �0 12 22 22
* �1 0� �
� � �� �11 21 12c* .
Ñëåäîâàòåëüíî, ñ ó÷åòîì � �11 12� ; � �21 22� ; c c12 22
* *
� ïîëó÷àåì j � 1
â ñëó÷àå A A1 2 ïðè g gi ir r j
1
.
Ðàññìîòðèì ñëó÷àé g gi ir j r
1
, òîãäà ñîãëàñíî ïðàâèëó âåòâëåíèÿ èìååì
c
r�
�
1
0. Çàìåòèì, ÷òî ñîãëàñíî ýòîìó ïðàâèëó åñëè îïðåäåëåíà ïåðåìåííàÿ ïðè
îòðèöàòåëüíîì êîýôôèöèåíòå öåëåâîé ôóíêöèè c
r
�
�
1
0, òî íåîïðåäåëåííûìè
îñòàëèñü òîëüêî ïåðåìåííûå ïðè îòðèöàòåëüíûõ êîýôôèöèåíòàõ öåëåâîé ôóíê-
öèè. Ñëåäîâàòåëüíî, ñèòóàöèÿ A A1 2 , ñîãëàñíî êîòîðîé èìåþòñÿ íåîïðåäåëåííûå
ïåðåìåííûå ñ ïîëîæèòåëüíûìè êîýôôèöèåíòàìè öåëåâîé ôóíêöèè, ïðè óñëîâèè
c
r
�
�
1
0 íåâîçìîæíà. Ðàññìîòðåíèå ñëó÷àÿ A A1 2 çàâåðøåíî.
Ðàññìîòðèì ñëó÷àé A B1 2 , ò.å. êîãäà g Air j
� 1; g Bir
�
1 2 , à çíà÷èò
g gi ir j r
1
. Ýòî îçíà÷àåò ïî ïðàâèëó âåòâëåíèÿ, ÷òî c
r
�
�
1
0. Ñëåäîâàòåëüíî, íå
îïðåäåëåíû òîëüêî ïåðåìåííûå ïðè ìåíüøèõ c
r
�
1
â (7) îòðèöàòåëüíûõ êîýôôè-
öèåíòàõ öåëåâîé ôóíêöèè. Çíà÷èò, ñèòóàöèÿ A B1 2 ïðè ýòîì íåâîçìîæíà, òàê êàê
ñóùåñòâóåò ïðîòèâîðå÷èå ýòîìó (A1 îçíà÷àåò íàëè÷èå íåîïðåäåëåííûõ ïåðåìåí-
íûõ ñ ïîëîæèòåëüíûìè êîýôôèöèåíòàìè â öåëåâîé ôóíêöèè).
Ðàññìîòðèì ñëó÷àé A C1 2 , ò.å. êîãäà g Air j
� 1; g Bir
�
1 2 , à ñëåäîâàòåëüíî
g gi ir j r
1
. À ýòî ñîãëàñíî ñïîñîáó âåòâëåíèÿ ìîæåò áûòü òîëüêî ïðè c
r�
�
1
0.
Ïîñëåäíåå îçíà÷àåò, ÷òî íåîïðåäåëåííûìè ÿâëÿþòñÿ òîëüêî ïåðåìåííûå ïðè îò-
ðèöàòåëüíûõ êîýôôèöèåíòàõ, ò.å. êîãäà g Air j
� 1, ÷òî ÿâëÿåòñÿ ïðîòèâîðå÷èåì
äëÿ ñëó÷àÿ A C1 2 .
Ðàññìîòðèì ñëó÷àé B A1 2 , êîãäà g Bir j
� 1; g Air
�
1 2 . Îòñþäà ñîãëàñíî ñïî-
ñîáó âåòâëåíèÿ (ïîñêîëüêó g gi ir r j
1
) ñëåäóåò íåðàâåíñòâî c
r�
�
1
0.
Äàëåå çàïèøåì 1 â âèäå
� �1 0 11 1
�
c g c
r ri r
* , (36)
à j â âèäå
� �j i r jc g c
r r j
�
0 1
* , (37)
ãäå
c c cr � 1 11 12
* * * , (38)
c c cr j �
* * *
21 22 , (39)
à ñîñòàâëÿþùèå (38), (39) âû÷èñëÿþòñÿ ñîãëàñíî (22)–(25). Î÷åâèäíî, ÷òî
c c12 22
* *
� (C C1 2� ),
c c gj j
j
11 11
1
1
* ~ ~�
�
��
�
�
; (40)
c c g c gi j j
j
r21 21
2
1
1 1
1
* ~ ~ ~�
�
�� �
�
�
, (41)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 89
ãäå
� �
�
11 21
1
11
� �
�
�
� ~ ~c gj j
j
, ~ ~ ~g g gj j j� �
1 2
� � �j J �1 1; (42)
~ ~ ~g g g
j j j
� �
1
2 1
� � �j J J� �\
1 1. (43)
Îïðåäåëèì ðàçíîñòü j � 1:
� � � �j i i ic g c g c g g
r r j r r r
� � � �
1
1
1 1 1 1 1 1
( ) ~ ( ~ ) �
�
� ~ (~ ~ )c g gj j j
j
2 1
11�
�
. (44)
Çàìåòèì, ÷òî â ñèëó ñïîñîáà âåòâëåíèÿ
c c c c
r� � � �
� � � � � 1 1 1 1 0~ ~ ~
� . (45)
 ñèëó (26), (27) è (43) èìååì
g g g g gi ir r j
1 1 1 1
~ ~ ~
� � �� . (46)
Çàìåòèì, ÷òî j � 1 — ýòî ðàçíîñòü çíà÷åíèé ëèíåéíîé öåëåâîé ôóíêöèè ñ
êîýôôèöèåíòàìè èç (45) äëÿ äâóõ âåêòîðîâ: g1 è g j . Âåêòîð g1 ñîñòîèò èç ïîñëå-
äîâàòåëüíûõ � �� 1 2 çíà÷åíèé ýëåìåíòîâ â ñëåäóþùåì ïîðÿäêå: ïåðâûé ñëå-
âà — ýòî gir j
, à äàëåå � �� 1 1 ýëåìåíòîâ, âçÿòûõ ñëåâà â (46). Âåêòîð g j ñîñòî-
èò èç ïîñëåäîâàòåëüíûõ � �� 1 2 çíà÷åíèé ýëåìåíòîâ, âçÿòûõ ñëåâà â (46). Ââå-
äåì îáîçíà÷åíèÿ: c c c� � ( , , )1 21
� � � ; x x x x� � ( , , , )1 2 21
� � � ; � �� �1 2 L .
Ïåðåîáîçíà÷èì ñîîòâåòñòâåííî ÷èñëà èç (45): c c cL1 2� � �� . Ïóñòü G0 —
ìóëüòèìíîæåñòâî ëåâûõ L ýëåìåíòîâ èç (46), ò.å. äî ~g � âêëþ÷èòåëüíî;
E G E GL� � � �( ) ( ),0 2 01
� � — ìíîæåñòâî ïåðåñòàíîâîê èç ýòèõ ýëåìåíòîâ. (Çäåñü
� — êîëè÷åñòâî ðàçíûõ ýëåìåíòîâ â G0 .) Âåëè÷èíà
�
1
1
�
�
�
�min
x E
j j
j
L
L
c x ñîãëàñíî
[2, òåîðåìà 3.1]. Òîãäà âåêòîð, íà êîòîðîì äîñòèãàåòñÿ 1, ÿâëÿåòñÿ âåêòîðîì
g g g g g gir
1
1 11 1 1
�
�( ; ~ , ~ , , ~ ; ~ )� � � �� , ýëåìåíòû êîòîðîãî óäîâëåòâîðÿþò (46). Ïî-
ñêîëüêó g1 — ýòî ìèíèìàëü, òî íà äðóãîì âåêòîðå g g g E G
L L
0
1
0 0
0� �( , , ) ( )� �
çíà÷åíèÿ ëèíåéíîé ôóíêöèè 0
0
1
1
� �
�
� c gj j
j
L
. Âîçüìåì â êà÷åñòâå g 0 âåêòîð
(~ , , ~ ; ~ , , ~ )g g g g gir� � � � �1 1 1 1 1� . Çàìåòèì, ÷òî âñå c j � �j JL ñîãëàñíî (45) íåîòðè-
öàòåëüíû. Ñëåäîâàòåëüíî, èìåÿ 0 1� , èçìåíèì â g 0 ïåðâûé ýëåìåíò íà gir j
,
ïîëó÷èì g j , ò.å. èçìåíèì â 0 îäíî ñëàãàåìîå c g c g
r1 1
0
1
�
� �
~ íà
c g c g
r r ji
j
�
�
1 1 1
. Ñîãëàñíî (46) è óñëîâèþ c
r�
�
1
0 èìååì c g c g
r r j ri� � �
�
1 1
~ .
 ðåçóëüòàòå çàìåíû â 0 ïîëó÷èì j � 0 , ò.å. j � �0 1. Òàêèì îáðàçîì,
â ñëó÷àå B A1 2 èìååì j � 1.
Ðàññìîòðèì ñëó÷àé B B1 2 . Î÷åâèäíî, ÷òî çäåñü 1, j ïðåäñòàâëÿþòñÿ êàê
(36), (37), cr 1
* , cr j
* ïðåäñòàâëÿþòñÿ êàê (38), (39) ïðè óñëîâèÿõ (22)–(25) è
c c11 21
* *
� ; c c12 22
* *
� . Ñëåäîâàòåëüíî, c cr r j �1
* * , ò.å. ðàçíîñòü j � 1 ïðåäñòàâëÿ-
åòñÿ â âèäå � ��j i i r j rc g g
r r j r
� � � � � �
1 11 1
0( ) , êàê áûëî ïîêàçàíî
â (21) (ýòîò ðåçóëüòàò íå çàâèñèò îò ïîäñëó÷àåâ B B1 2).
Ðàññìîòðèì ñëó÷àé C B1 2 , ò.å. èìååì g gi ir r j
1
; ýòî çíà÷èò, ÷òî ñîãëàñíî
ïðàâèëàì âåòâëåíèÿ c
r�
�
1
0 . Ñëåäóåò ó÷èòûâàòü, ÷òî 1, j âû÷èñëÿþòñÿ ñ ïî-
90 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
ìîùüþ ôîðìóë (36)–(39) ïðè óñëîâèÿõ (22)–(25). Ïðè ýòîì â ñëó÷àå C B1 2 â ñèëó
A A1 2� î÷åâèäíî, ÷òî c c11 21
* *
� . Ïðîàíàëèçèðóåì c12
* è c22
* , êîòîðûå îïðåäåëÿþò-
ñÿ â (23), (25) ñîîòâåòñòâåííî. Ýòè ñóììû èìåþò îäèíàêîâûå ñîñòàâëÿþùèå
� � � � �
� �
1
1
1
� �
�
�
� ~ ~c gj j
j
, � � � � �
� �
2
2
1
� �
�
�
� ~ ~c gj j
j
, ïîñêîëüêó ~ ~g gj j
1 2
� � �j J � \
\ J � � �
� . Çäåñü
îáîçíà÷àåò ìåñòî ýëåìåíòà gir j
â ìíîæåñòâå C
1
îò íà÷àëà
ñ ó÷åòîì ïîðÿäêà (26), ò.å. � � �1 2� � . Òîãäà èç (23) è (25) èìååì
c c gj j
j
12
1
1
* ~ ~� � �
�
�� � � � �
; (47)
c c gj j
j
22
2
1
* ~ ~� � �
�
�� � � � �
. (48)
Ïðè ýòîì ~ ~ ~g g g
j j j� � � � � � � � �� � � � �
1
1
2
� � � �
� �j J J
1
0
1 0{ }. Çàìåòèì,
÷òî
g g g g gi ir r j
� � � �1 1 1
~ ~ ~
� � � � � � � � �
� , (49)
c
r�
� �
1
0 ~ ~ ~c c c� � �
� � �1 2 � . (50)
Èñõîäÿ èç (36)–(39) ñîãëàñíî óñëîâèÿì (22)–(25) è ïðåäñòàâëåíèÿì (47),
(48), íåðàâåíñòâàì (49), (50), èìååì
� � �
� � �j i i j
j
jc g c g c g
r r j r r
� � � �
�
� ��1
1
11 1 1
~ ~
� � �
�
�
� �
~ ~ ~c g c gj
j
j ir j�
� � � �
1
1
� � �
�
�
� � ��c g g c g g
r r j ri i j
j
j� �
� � � � �1 1
1
1
1( ) ~ (~ ~
� j )
� �
~ (~ )c g gir j�
� � �
. (51)
 ñèëó òîãî, ÷òî c
r�
�
1
0, à g gi ir r j
1
, à òàêæå íåðàâåíñòâ (49) è (50), ãäå
� �j J
èìååì ~c j� � 0, ïîëó÷èì èç (51) j � �1 0, ïîñêîëüêó ýòà ðàçíîñòü
ïðåäñòàâëÿåò ñóììó âñåõ íåîòðèöàòåëüíûõ ñëàãàåìûõ. Òàêèì îáðàçîì, j � 1
â ñëó÷àå C B1 2 .
Ðàññìîòðèì ñëó÷àé B C1 2 , ò.å. èìååì g gi ir j r
1
, ñîãëàñíî ïðàâèëó âåòâëå-
íèÿ c
r�
�
1
0. Êàê è ðàíåå, ïðîàíàëèçèðóåì � è j , êîòîðûå âû÷èñëÿþòñÿ ñîãëàñ-
íî (36)–(39) ïðè óñëîâèÿõ (22)–(25). Èç ýòèõ ôîðìóë äëÿ ñëó÷àÿ B C1 2 â ñèëó
A A1 2� î÷åâèäíî, ÷òî c c11 21
* *
� . Ïðîàíàëèçèðóåì c12
* è c22
* íà îñíîâàíèè èõ âûðà-
æåíèé (23), (25) ñîîòâåòñòâåííî. Åñëè
îáîçíà÷èòü ìåñòî ýëåìåíòà gir 1
â C2
(îò íà÷àëà C2 ñ ó÷åòîì ïîðÿäêà (27)), òî ìîæíî çàïèñàòü îäèíàêîâûå ÷àñòè ñóìì
(23) è (25):
� � � � �
� �
1
1
1
� �
�
�
� ~ ~c gj j
j
, (52)
� � � � �
� �
2
2
1
� �
�
�
� ~ ~c gj j
j
. (53)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 91
Äåéñòâèòåëüíî, (52) è (53) îäèíàêîâû, ïîñêîëüêó ~ ~g g
j j� � � � � �� �
�
1 2
� � �j J J� �
\ . Îáîçíà÷èì � � �1 2� � è ðàññìîòðèì c12
*
� � è c22
*
� �, êîòîðûå
ôîðìàëüíî îïðåäåëÿþòñÿ â (47), (48), ãäå
îáîçíà÷àåò ìåñòî ýëåìåíòà gir 1
â C2 (îò íà÷àëà C2). Çàìåòèì, ÷òî ~ ~ ~g g g
j j j� � � � � � � � �� � � � � �
1
1
2
� �j J
,
à òàêæå, ÷òî
g g g g gi ir j r
� � �
~ ~ ~
� � � � � � � � �
1 2 1
� , (54)
0
1 1 2� � � � �
c c c c
r� � � �
~ ~ ~
� . (55)
Èñõîäÿ èç (36)–(39) ïðè óñëîâèÿõ (22)–(25), ôîðìóë (47), (48), (52), (53) è íå-
ðàâåíñòâ (54), (55), èìååì
� �
� � �j i i j
j
jc g g c g
r r j r
� � � �
�
�
� �1
1
1
11 1
( ) ~ (~ ~ )g j� � ��
� �
~ ( ~ )c g gir�
� � �
1
. (56)
Îäíàêî ïåðåãðóïïèðîâàâ ñëàãàåìûå â (56), ñ ó÷åòîì ïîïàðíîãî ðàâåíñòâà ýëå-
ìåíòîâ èç G1 è G2 , ïðè êîòîðîì îáíóëÿþòñÿ ñîîòâåòñòâóþùèå ðàçíîñòè, èìå-
åì � �
� � � �j i i ic g g c g c g
r r j r r
� � � � �
� 1 1 11 1 1
( ) ~ ~ � .
Íåñëîæíî óâèäåòü, ÷òî ýòî âûðàæåíèå äëÿ j � �1 � ìîæåò áûòü êàê íåîò-
ðèöàòåëüíûì, òàê è íåïîëîæèòåëüíûì â ñëó÷àå B C1 2 . Ýòî è òðåáîâàëîñü äîêà-
çàòü äëÿ B C1 2 .
Ðàññìîòðèì ñëó÷àé C A1 2 , ò.å. g gi ir r j
1
. Ýòî îçíà÷àåò, ÷òî c
r�
�
1
0.
Ïóñòü �1 îáîçíà÷àåò ìåñòî ýëåìåíòà gir 1
â A2
, à
— ìåñòî ýëåìåíòà gir j
îò íà-
÷àëà â C1 (ó÷èòûâàÿ ïîðÿäêè (26), (27)). Íàéäåì
� � �j j j i ic c c g g
r r j r
� � � � � �
1 1 1 1 1
* * ( )
� �
�
�
�
�
�
� � �~ ~ ~ ~ ~ ~c g c g c gj j
j
j j
j
j j
j
2
1
2
1
1
1
�
� � � �
� � �
� � � �
�
�
�
~ ~ ( ) ~c g c g g c gj j
j
i i ir r j r r� � � �
� �
� �
1
1
1 1 1
1
�
�
�
�
� �~ ~ ~ ~c g c gj j
j
j j
j
2
1
2
11�
�
� � � �
� � �
�
�
�
�
� � �~ ~ ~ ~ ~ ~c g c g c gj j
j
j j
j
1 1
1
1
1�
�
� � � �
�
� � �
1 . (57)
 ïîñëåäíåé ñóììå
~ ~ ~g g gj j j
1
1
2
� �
� � � j J J� � �
�\
1
; (58)
~g gir j� � �
�
�
1 ;
ïðè ýòîì
c c c c c c c
r� � � � � � �
� � � � � � � � � � 1 1 1 1 1 10~ ~ ~ ~ ~ ~
� � ; (59)
92 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
g g g g g gir
� � 1 1 1 1 1
~ ~ ~ ~ ~
� � � � � � �� �
... ~ ~
� � �
g g gir j� � � � � �
1 1� . (60)
Ïåðåïèøåì (57) â âèäå
� �
�
�
�j i i j j
j
j
j
c g c g c g c
r r j r
� �
�
�
�1 1
1
1 1 1
1
~ ~ ~ ~
�
�
� ��
1
1
1
� � �
~g j
(61)
� � � � �
�
~ ~ ~ ~ ~ ~c g c g c g c g
r ri j j
j
�
� � �
� � �
�
1
1
1 1 1 1
1
�
�
� � � �
� �� �
�
�
�
~ ~ ~ .c g c gj
j
j ir j
1
1
Ñîãëàñíî (59), (60) â ðàçíîñòè �j � â (61) îòíèìàåòñÿ ìèíèìàëüíîå çíà÷å-
íèå 1 ëèíåéíîé ôóíêöèè ñ êîýôôèöèåíòàìè èç ìíîæåñòâà ÷èñåë, óïîðÿäî÷åí-
íûõ ïî (59), ñ äîáàâëåíèåì îäíîãî íóëÿ ìåæäó ~c� � 0 è ~c� �1 0 íà ìíîæåñòâå ïå-
ðåñòàíîâîê èç � �
� 1 3 ýëåìåíòîâ â (60) [2, òåîðåìà 3.1]). Ïðè ýòîì îòíèìà-
åòñÿ � íå îò ìèíèìàëüíîãî çíà÷åíèÿ j ýòîé æå ôóíêöèè (ïîñêîëüêó âåêòîð
çíà÷åíèé ïåðåìåííûõ ýòîé ôóíêöèè, ÷òî äàåò j , íå óïîðÿäî÷åí ñîãëàñíî
(60)). Ñëåäîâàòåëüíî, j � �1 0, ÷òî è òðåáîâàëîñü äîêàçàòü â ñëó÷àå C A1 2 .
Íàêîíåö, ðàññìîòðèì ñëó÷àé C Ñ1 2 . Âîçìîæíû äâà âàðèàíòà ñîîòíîøå-
íèÿ: 1) g gi ir r j
1
; 2) g gi ir r j
�
1
. Ïîñêîëüêó g Cir j
� 1; g Cir
�
1 2 , òî ýòî çíà-
÷èò, ÷òî c
r�
�
1
0. Ñëåäîâàòåëüíî, ñîãëàñíî ïðàâèëó âåòâëåíèÿ g g
i i
r r j
�
1
, ò.å.
ïåðâûé âàðèàíò íåâîçìîæåí. Ðàññìîòðèì âòîðîé ñëó÷àé îòíîñèòåëüíî âûðàæå-
íèé 1, j :
� �
�
� � � �
�
1 0
1
1
1
1
1 1
�
�
�
�
�
�c g c g c g
r ri j j
j
j j
j
~ ~ ~ ~
1
�
~c gir j� �
�
�
�
� � ~ ~ ~ ~ ~ ~c g c g c gj j
j
j� � � �
�
�
� � �
� �
1
1
1
1
�
�
�
� � �
� �
j
j
1
1
;
(62)
� �
�
� � � �
�
j i j j
j
j j
j
c g c g c g
r r j
�
�
�
�
�
�0
2
1
1
1
1
~ ~ ~ ~
1
2
� �
~c g� � � � � �
�
�
�
� �
~ ~ ~ ~ ~c g c g c gj j
j
i jr� � � �
�
�
� � � �
2
1
1
1 j
j
2
1�
�
�
� �
,
(63)
ãäå
~ ~g gj j
1 2
� � �j J �; ~ ~g g
j j� � � � � �� �
�
1 2
� � �j J� 1, � � �j J J� �
\ ; (64)
� îáîçíà÷àåò ìåñòî ýëåìåíòà gir j
îò íà÷àëà C1;
îáîçíà÷àåò ìåñòî ýëåìåíòà
gir 1
îò íà÷àëà C2 ; ~ ~ ~g g g
j j j� � � � � � � � �� � � � �
1
1 2
� � � �j J J
�1 1\ . Ïðè
ýòîì èìååì
g g g g gi ir j r
� � � �
~ ~ ~
� � � � � � � � � � �
1 1 1
� ; (65)
0
1 1 1� � � � � �
� c c c c c
r� � � � � �
�
~ ~ ~ ~
� . (66)
Âû÷òåì èç ðàâåíñòâà (63) ðàâåíñòâî (62), ïðè ýòîì â ñèëó (64) òðåòüè, ÷åò-
âåðòûå è ïîñëåäíèå ñóììû âçàèìíî óíè÷òîæàþòñÿ (îíè ïîïàðíî îäèíàêîâû):
� � � � � � � �j i i ic g c g c g g
r r j r r r j
� � � �
� 1 1 1 1
~ (~ )
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 93
�
�
� � �� ~ (~ ~ )c g gj
j
j j�
�
� � � � �
1
1
1
~ ( ~ )c g gir�
� � �
� �
� �
1 1
�
� �
�
�
�c g c g c g
r r ji j j
j
� � � � � � � � � � �
�
1
1
1
~ ~ ~ ~ �
~c gir�
1
�
�
�
� ��[ ~ ~ ~c g c g c g
r r r ji i j
j
j� � � �
�
� � �1 1
1
1
1
~ ~ ]c g�
� � �
� �1 . (67)
Ïðàâàÿ ÷àñòü ðàâåíñòâà (67) — ýòî ðàçíîñòü äâóõ çíà÷åíèé ëèíåéíîé öåëåâîé
ôóíêöèè ñ êîýôôèöèåíòàìè èç (66) â ïåðåñòàíîâêå, êîòîðàÿ óïîðÿäî÷åíà ñîãëàñíî
(65) (÷òî ïî òåîðåìå 3.1 èç [2] ÿâëÿåòñÿ ìèíèìóìîì), è äðóãèì çíà÷åíèåì (ýòî ñóì-
ìà â êâàäðàòíûõ ñêîáêàõ), ÷òî ïî îïðåäåëåíèþ ìèíèìóìà íå ìåíüøå ïåðâîé ñóì-
ìû. Òàêèì îáðàçîì, â ñëó÷àå C C1 2 èìååì j
1, ÷òî è òðåáîâàëîñü äîêàçàòü äëÿ
ýòîãî ñëó÷àÿ. Äîêàçàòåëüñòâà çàâåðøåíû îòíîñèòåëüíî âñåõ ñëó÷àåâ.
Ðàññìîòðèì ïðèìåð ðåøåíèÿ èçëîæåííîé âûøå çàäà÷è.
Ðåøèòü çàäà÷ó: 5 41 2 3 4x x x x� � � min, x j
j�
� �
1
4
1 , x x xk� �( , , )1 �
�E Gk
�� ( ), G � {0 1 0 1 0 2 0 2 0 2 0 3 0 3 0 3 0 4 0 4, ; , ; , ; , ; , ; , ; , ; , ; , ; , ; 0 5 0 5, ; , ; 0 6 0 7 0 8 0 9 1, ; , ; , ; , ; }
(îòìåòèì, ÷òî k � 4, � �17, � �10).
Ïðè ðåøåíèè ñ ïîìîùüþ ÌÂà ýòîé çàäà÷è ñ ïðèìåíåíèåì îöåíèâàíèÿ, âåò-
âëåíèÿ è îòñå÷åíèÿ, ðàññìîòðåííûõ â òåîðåìàõ 1–3, ïîëó÷åíî 77 äîïóñòèìûõ ðå-
øåíèé, ïåðâîå èç êîòîðûõ îêàçàëîñü îïòèìàëüíûì: ñî çíà÷åíèåì öåëåâîé ôóíê-
öèè F0 2� � , äîñòèãàåìûì â òî÷êå x 0 0 1 0 2 0 1 0 6� ( , ; , ; , ; , ).
Òàêèì îáðàçîì, â íàñòîÿùåé ñòàòüå äëÿ çàäà÷ ìèíèìèçàöèè íà ìíîæåñòâå
ðàçìåùåíèé ñ åäèíè÷íîé èõ ñóììîé ëèíåéíîé öåëåâîé ôóíêöèè äëÿ ìåòîäà âåò-
âåé è ãðàíèö ïðåäëîæåíû ïðàâèëà âåòâëåíèÿ è îöåíêà äîïóñòèìûõ ïîäìíîæåñòâ.
Äîêàçàíû äâà ñâîéñòâà îöåíîê, êîòîðûå ïîçâîëÿþò çíà÷èòåëüíî óìåíüøàòü êî-
ëè÷åñòâî àíàëèçèðóåìûõ äîïóñòèìûõ ïîäìíîæåñòâ. Êàê íàïðàâëåíèå äàëüíåé-
øèõ èññëåäîâàíèé ìîæíî îïðåäåëèòü ïîèñê âîçìîæíîñòè òàê îðãàíèçîâàòü âåò-
âëåíèå â ÌÂà äëÿ ðàññìîòðåííîé çàäà÷è, ÷òîáû îöåíêè 1 è j èç òåîðåìû 3
âñåãäà èìåëè ñîîòíîøåíèå j � 1. Â ïåðñïåêòèâå öåëåñîîáðàçíî óñòàíîâèòü,
ïðè êàêèõ óñëîâèÿõ ïåðâîå äîïóñòèìîå ðåøåíèå F0 â ðàññìàòðèâàåìîé çàäà÷å
ÿâëÿåòñÿ è îïòèìàëüíûì.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíàòîðíûõ
çàäà÷ îïòèìèçàöèè — Ê.: Íàóê. äóìêà, 1981. — 288 ñ.
2. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Ê.: ²í-ò
ñèñòåì. äîñë³äæåíü îñâ³òè, 1993. — 188 ñ.
3. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ / Ïîä ðåä.
È.Â. Ñåðãèåíêî. — Ê.: Íàóê. äóìêà, 2008. — 159 ñ.
4. à ó ë ÿ í è ö ê è é Ë . Ô . Ðîçðîáêà ìîäåëåé ³ íàáëèæåíèõ ìåòîä³â êîìá³íàòîðíî¿ îïòèì³çàö³¿ òà ¿õ
çàñòîñóâàííÿ â ³íôîðìàö³éíèõ òåõíîëîã³ÿõ: Àâòîðåô. äèñ. ... ä-ðà òåõí. íàóê. — Ê., 2005. — 32 ñ.
5. Å ì å ö Î . À . , Ó ñ ò ü ÿ í Í . Þ . Ðåøåíèå íåêîòîðûõ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè íà
ðàçìåùåíèÿõ è ïåðåñòàíîâêàõ èãðîâîãî òèïà // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2006. —
¹ 3. — Ñ. 37–47.
6. Å ì å ö Î . À . , Ó ñ ò ü ÿ í Í . Þ . Èãðû ñ êîìáèíàòîðíûìè îãðàíè÷åíèÿìè // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2008. — ¹ 4. — Ñ. 134–141.
7. Å ì å ö Î . À . , Î ë ü õ î â ñ ê à ÿ Å . Â . Èòåðàöèîííûé ìåòîä ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷ èãðîâîãî
òèïà íà ðàçìåùåíèÿõ // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2011. — ¹ 3. — Ñ. 69–78.
Ïîñòóïèëà 21.07.2011
94 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
|
| id | nasplib_isofts_kiev_ua-123456789-84126 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-27T09:14:02Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Емец, А.О. 2015-07-03T09:10:32Z 2015-07-03T09:10:32Z 2012 Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения / О.А. Емец, А.О. Емец // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 83-94. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84126 519.85 Запропоновано правила галуження та оцінку допустимих підмножин для задач мінімізації на множині розміщень з одиничною їх сумою лінійної цільової функції для методу гілок та меж. Доведено дві властивості оцінок, що дозволяють значно зменшувати кількість допустимих підмножин, що аналізуються. Branching rules and the estimation of admissible subsets for minimization problems on the set of arrangements with a constant sum of a linear objective function for the branch and bound method are proposed in the paper. Two properties of the estimates are proved. These properties allow reducing the number of the admissible subsets being analyzed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения Розв’язування лінійної задачі евклідової комбінаторної оптимізації на розміщеннях з умовою сталості суми елементів розміщень Solving a linear problem of Euclidean combinatorial optimization on arrangements with a constant sum of the elements Article published earlier |
| spellingShingle | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения Емец, О.А. Емец, А.О. Системный анализ |
| title | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения |
| title_alt | Розв’язування лінійної задачі евклідової комбінаторної оптимізації на розміщеннях з умовою сталості суми елементів розміщень Solving a linear problem of Euclidean combinatorial optimization on arrangements with a constant sum of the elements |
| title_full | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения |
| title_fullStr | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения |
| title_full_unstemmed | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения |
| title_short | Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения |
| title_sort | решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства суммы элементов размещения |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84126 |
| work_keys_str_mv | AT emecoa rešenielineinoizadačievklidovoikombinatornoioptimizaciinarazmeŝeniâhsusloviempostoânstvasummyélementovrazmeŝeniâ AT emecao rešenielineinoizadačievklidovoikombinatornoioptimizaciinarazmeŝeniâhsusloviempostoânstvasummyélementovrazmeŝeniâ AT emecoa rozvâzuvannâlíníinoízadačíevklídovoíkombínatornoíoptimízacíínarozmíŝennâhzumovoûstalostísumielementívrozmíŝenʹ AT emecao rozvâzuvannâlíníinoízadačíevklídovoíkombínatornoíoptimízacíínarozmíŝennâhzumovoûstalostísumielementívrozmíŝenʹ AT emecoa solvingalinearproblemofeuclideancombinatorialoptimizationonarrangementswithaconstantsumoftheelements AT emecao solvingalinearproblemofeuclideancombinatorialoptimizationonarrangementswithaconstantsumoftheelements |