Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах
Розглянуто модифікацію методу комбінаторного відсікання для оптимізації на вершинно розташованих множинах, який дозволяє працювати з виродженими рішеннями допоміжних задач.Обґрунтовано вигляд нерівності–відсікання. Наведено ілюстративний приклад застосування методу. A modification of the method comb...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44408 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах / О.А. Емец, Е.М. Емец // Кибернетика и системный анализ. — 2009. — № 5. — С. 129-136. — Бібліогр.: 28 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860234718360895488 |
|---|---|
| author | Емец, О.А. Емец, Е.М. |
| author_facet | Емец, О.А. Емец, Е.М. |
| citation_txt | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах / О.А. Емец, Е.М. Емец // Кибернетика и системный анализ. — 2009. — № 5. — С. 129-136. — Бібліогр.: 28 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто модифікацію методу комбінаторного відсікання для оптимізації на вершинно розташованих множинах, який дозволяє працювати з виродженими рішеннями допоміжних задач.Обґрунтовано вигляд нерівності–відсікання. Наведено ілюстративний приклад застосування методу.
A modification of the method combinatorial cutting for optimization over vertex-located sets is considered. The modification allows working with degenerated decisions of auxiliary problems. The type of an inequality-cutting is grounded. An illustrative example of application of the method is given.
|
| first_indexed | 2025-12-07T18:23:07Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Î.À. ÅÌÅÖ, Å.Ì. ÅÌÅÖ
ÌÎÄÈÔÈÊÀÖÈß ÌÅÒÎÄÀ ÊÎÌÁÈÍÀÒÎÐÍÎÃÎ ÎÒÑÅ×ÅÍÈß
 ÇÀÄÀ×ÀÕ ÎÏÒÈÌÈÇÀÖÈÈ ÍÀ ÂÅÐØÈÍÍÎ
ÐÀÑÏÎËÎÆÅÍÍÛÕ ÌÍÎÆÅÑÒÂÀÕ
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ìåòîä îòñå÷åíèÿ, âåðøèííî
ðàñïîëîæåííûå ìíîæåñòâà, ïåðåñòàíîâêè, âûðîæäåííûå ðåøåíèÿ çàäà÷ ëèíåé-
íîãî ïðîãðàììèðîâàíèÿ.
ÂÂÅÄÅÍÈÅ
Àêòóàëüíîñòü è âàæíîñòü çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè â ñîâðåìåííîé òåî-
ðèè îïòèìèçàöèè íå òðåáóåò îáîñíîâàíèÿ ââèäó ñâîåé î÷åâèäíîñòè [1–10].
Èíòåðåñíûì è âàæíûì ÿâëÿåòñÿ êëàññ çàäà÷ îïòèìèçàöèè ëèíåéíîé ôóíêöèè
ñ äîïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè íà âåðøèííî ðàñïîëîæåííîì êîì-
áèíàòîðíîì ìíîæåñòâå. Ïðèìåðàìè òàêèõ âåðøèííî ðàñïîëîæåííûõ ìíîæåñòâ ÿâ-
ëÿþòñÿ ìíîæåñòâà ïåðåñòàíîâîê, ïîëèïåðåñòàíîâîê, íåêîòîðûå ìíîæåñòâà ðàçìå-
ùåíèé è ìíîãèå åâêëèäîâû êîìáèíàòîðíûå ìíîæåñòâà. Äëÿ òàêèõ çàäà÷ ðàçðàáîòàí
ìåòîä êîìáèíàòîðíîãî îòñå÷åíèÿ [11–18]. Âìåñòå ñ òåì âîçíèêàþò íåêîòîðûå
ñëîæíîñòè â åãî ðåàëèçàöèè, êîãäà âî âñïîìîãàòåëüíûõ çàäà÷àõ ëèíåéíîãî
ïðîãðàììèðîâàíèÿ (ÇËÏ) ðåøåíèÿ ÿâëÿþòñÿ âûðîæäåííûìè.
 íàcòîÿùåé ñòàòüå ïðåäëàãàåòñÿ ìîäèôèêàöèÿ ìåòîäà êîìáèíàòîðíîãî îòñå÷å-
íèÿ äëÿ çàäà÷ îïòèìèçàöèè íà âåðøèííî ðàñïîëîæåííûõ êîìáèíàòîðíûõ ìíîæåñòâàõ,
êîòîðàÿ ïîçâîëÿåò èñïîëüçîâàòü âûðîæäåííûå ðåøåíèÿ âñïîìîãàòåëüíûõ ÇËÏ.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ðàññìîòðèì çàäà÷ó ìàêñèìèçàöèè ëèíåéíîé ôóíêöèè ïðè äîïîëíèòåëüíûõ ëè-
íåéíûõ îãðàíè÷åíèÿõ íà âåðøèííî ðàñïîëîæåííîì ìíîæåñòâå. Íàéòè
C y c y
y R
j j
j
n
n
( *) max�
� �
�
1
, (1)
y y y c yn
y R
j j
j
n
n
* ( , , ) max* *� �
� �
�1
1
� arg (2)
ïðè äîïîëíèòåëüíûõ ëèíåéíûõ óñëîâèÿõ
a y b i Jij j
j
n
i r
�
� � � �
1
; (3)
y j Jj n� � �0 (4)
ñ ó÷åòîì êîìáèíàòîðíîãî îãðàíè÷åíèÿ
x x x y y E Rk k
k� � � �( , , ) ( , , )1 1� � , (5)
â êîòîðîì êîìáèíàòîðíîå ìíîæåñòâî E ÿâëÿåòñÿ âåðøèííî ðàñïîëîæåííûì, ò.å.
ïðè îáðàçîâàíèè åãî âûïóêëîé îáîëî÷êè convE ñîâïàäàåò ñ ìíîæåñòâîì åå âåð-
øèí vert(convE ) :
E E� vert conv( ) . (6)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 129
© Î.À. Åìåö, Å.Ì. Åìåö, 2009
 çàäà÷å (1)–(6) n r k, , — çàäàííûå íàòóðàëüíûå êîíñòàíòû ( )k n� ; R n —
n-ìåðíîå åâêëèäîâî àðèôìåòè÷åñêîå ïðîñòðàíñòâî; J r — ìíîæåñòâî ïåðâûõ r íàòó-
ðàëüíûõ ÷èñåë ( , , , )J rr � { }1 2 � ; c a bj ij i, , — çàäàííûå äåéñòâèòåëüíûå ÷èñëà
� � � �i J j Jr n, .
Îòìåòèì, ÷òî ïðè k n çàäà÷ó íàçûâàþò ÷àñòè÷íî êîìáèíàòîðíîé, à ïðè k n� —
ïîëíîñòüþ êîìáèíàòîðíîé.
ÌÎÄÈÔÈÊÀÖÈß ÌÅÒÎÄÀ ÊÎÌÁÈÍÀÒÎÐÍÎÃÎ ÎÒÑÅ×ÅÍÈß È ÅÅ ÎÁÎÑÍÎÂÀÍÈÅ
Ìåòîä îòñå÷åíèÿ äëÿ êîìáèíàòîðíîé çàäà÷è ñîñòîèò â ñëåäóþùåì (ñõåìà ìåòîäà
îòñå÷åíèÿ èçëîæåíà â [5]).
1. Ðåøàåì âñïîìîãàòåëüíóþ ÇËÏ, êîòîðàÿ ïîëó÷åíà èç çàäà÷è (1)–(5) ïðè óñëîâèè
(6) çàìåíîé (5) íà ïðèíàäëåæíîñòü òî÷êè x âûïóêëîé îáîëî÷êå ìíîæåñòâà E:
x E�conv . (7)
Çàìåòèì, ÷òî âûïóêëûå îáîëî÷êè ìíîãèõ âåðøèííî ðàñïîëîæåííûõ ìíîæåñòâ
èçâåñòíû (íàïðèìåð, [4, 19–26]). Áóäåì ñ÷èòàòü, ÷òî ñèñòåìà ëèíåéíûõ îãðàíè÷å-
íèé, îïèñûâàþùàÿ óñëîâèå (7), ïðåäñòàâëåíà â âèäå ðàâåíñòâ (êàê è ïðè ñâåäå-
íèè ÇËÏ ê êàíîíè÷åñêîìó âèäó)
a y b i J Jij j i
j
n
s r� � �
�
�
1
\ , (8)
ãäå s — íàòóðàëüíàÿ êîíñòàíòà, s r
; aij , bi — îïðåäåëåííûå â (7) äåéñòâèòåëü-
íûå ÷èñëà � �i J Js r\ , � �j J n .
Îáúåäèíÿÿ (3) è (8), ïîëó÷àåì
a y bij j i
j
n
�
�
�
1
� �i J s. (9)
Òàêèì îáðàçîì, âñïîìîãàòåëüíàÿ ÇËÏ (ÂÇËÏ) èìååò âèä: íàéòè (1), (2) ïðè
îãðàíè÷åíèÿõ (4), (9). Íà ýòîì ýòàïå çàäà÷à ðåøàåòñÿ ìåòîäîì ëèíåéíîãî ïðîãðàì-
ìèðîâàíèÿ (ñèìïëåêñ-ìåòîäîì, ìåòîäîì èñêóññòâåííîãî áàçèñà, äâîéñòâåííûì
ñèìïëåêñ-ìåòîäîì — â çàâèñèìîñòè îò âèäà ÇËÏ), â ðåçóëüòàòå ïîëó÷åíà âåðøèíà
äîïóñòèìîé îáëàñòè.
2. Îáîçíà÷èì y* ðåøåíèå ÂÇËÏ (1), (2), (4), (9). Íà îñíîâàíèè y* îáðàçóåì
x x x y yk k
* * * * *( , , ) ( , , )� �1 1� � , äëÿ êîòîðîãî ïðîâåðÿåì óñëîâèå (5):
x E* � . (10)
Åñëè (10) âûïîëíÿåòñÿ, òî çàäà÷à (1)–(5) ðåøåíà. Èíà÷å ïåðåõîäèì ê ï. 3.
3. Íàõîäèì ñìåæíûå ñ òî÷êîé y* âåðøèíû ìíîãîãðàííèêà (9). Îïðåäåëÿåì ïî-
ëóïðîñòðàíñòâî, ãðàíèöà êîòîðîãî ïðîõîäèò ÷åðåç ñìåæíûå ñ òî÷êîé y* âåðøèíû
ìíîãîãðàííèêà (9), êîòîðîìó òî÷êà y* íå ïðèíàäëåæèò:
a y br j j
j
n
r�
�
�� �1
1
1, . (11)
Ýòî íåðàâåíñòâî â âèäå ðàâåíñòâà (äîáàâèâ â åãî ëåâóþ ÷àñòü íîâóþ íåîòðèöàòåëü-
íóþ ïåðåìåííóþ) äîáàâëÿåì â ñèñòåìó (9) (ñîîòâåòñòâåííî óâåëè÷èâ çíà÷åíèå s ).
Ïîñëå ýòîãî ïåðåõîäèì ê ï. 1.
Îòëè÷èòåëüíûì â ïðåäëàãàåìîé ìîäèôèêàöèè ìåòîäà ÿâëÿåòñÿ ñïîñîá ïîñòðî-
åíèÿ íåðàâåíñòâà (11). Êàê èçâåñòíî èç [5, 11–18], îòñå÷åíèå (11) ïðåäëàãàåòñÿ
ñòðîèòü â âèäå íåðàâåíñòâà
130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
y j
jj J
i
ii
��
� � 1, (12)
ãäå J — ìíîæåñòâî íåáàçèñíûõ ïåðåìåííûõ â òî÷êå y* — ðåøåíèè ÂÇËÏ,
�
�
�
�
��
j
i
i
ij
t
tjij
� �
min
: 0
.
(13)
Çäåñü � ij ; � i — ýëåìåíòû ïîñëåäíåé ñèìïëåêñ-òàáëèöû ÂÇËÏ (i — íîìåð åå
ñòðîêè, j — íîìåð ñòîëáöà íåáàçèñíîé ïåðåìåííîé), êîòîðàÿ äàåò ðåøåíèå y* .
Ôîðìóëû (12), (13) ïðèåìëåìû, êîãäà � ji
0 � �j Ji . Èíà÷å (ïðè � j � 0 ) ïðåä-
ëàãàåòñÿ [5, 11, 12, 15] èñïîëüçîâàòü ìåòîäû âîçìóùåíèÿ (×àðíñà è äðóãèå).
 ñòàòüå äàíà ìîäèôèêàöèÿ ìåòîäà êîìáèíàòîðíîãî îòñå÷åíèÿ, ïîçâîëÿþùàÿ
ó÷èòûâàòü ñèòóàöèþ ñ âûðîæäåííûì ðåøåíèåì ÂÇËÏ. Èçëîæèì ìîäèôèöèðîâàí-
íûé ìåòîä êîìáèíàòîðíîãî îòñå÷åíèÿ äëÿ çàäà÷è îïòèìèçàöèè (1)–(5) íà âåðøèííî
ðàñïîëîæåííîì êîìáèíàòîðíîì ìíîæåñòâå.
Øàã 0. Çàäàåì öåëî÷èñëåííóþ ïåðåìåííóþ q � 0 .
Øàã 1. Ðåøàåì ÂÇËÏ (1), (2), (4), (9) ïðÿìûì ëèáî äâîéñòâåííûì ñèì-
ïëåêñ-ìåòîäîì èëè ìåòîäîì èñêóññòâåííîãî áàçèñà. Åñëè ýòà çàäà÷à íå èìååò ðåøå-
íèÿ, òî è èñõîäíàÿ çàäà÷à (1)–(5) íå èìååò ðåøåíèÿ. Íà ýòîì àëãîðèòì îêàí÷èâàåò
ðàáîòó. Èíà÷å — ïåðåõîä íà øàã 2.
Øàã 2. Ïðîâåðÿåì óñëîâèå x y y Ek
* * *( , , )� �1 � (ò.å. âûïîëíåíèå óñëîâèÿ (5)).
Åñëè (5) äëÿ x* âûïîëíÿåòñÿ, òî çàäà÷à (1)–(5) ðåøåíà. Àëãîðèòì îêàí÷èâàåò ðàáî-
òó. Èíà÷å — ïåðåõîä íà øàã 3.
Øàã 3. Óâåëè÷èâàåì çíà÷åíèå q íà åäèíèöó.
Øàã 4. Äîáàâëÿåì ê ñèñòåìå (9) (óâåëè÷èâàÿ s íà åäèíèöó) îòñå÷åíèå òî÷êè y*
â âèäå ðàâåíñòâà
� � � ��
�
�
y
y
j
j
n q
j J
t
t
t
jt
�
�
1
0
, (14)
ââåäÿ äîïîëíèòåëüíóþ ïåðåìåííóþ yn q� � 0 . Â ôîðìóëå (14) j j1 , ,� � — íîìå-
ðà íåáàçèñíûõ ïåðåìåííûõ â ïîñëåäíåé òî÷êå y* (ïîëó÷åííîé êàê ðåøåíèå
ÂÇËÏ íà øàãå 1), � — èõ êîëè÷åñòâî, J j j� { }1 , ,� � ; � jt
� �t J � íàõîäèòñÿ ïî
ôîðìóëå (13), ò.å.
�
�
�
�
�
�
j
i s
i
ij
t
tj
ij
� �
� �
min
1
0
,
ãäå � ij , � i — ýëåìåíòû ïîñëåäíåé ñèìïëåêñ-òàáëèöû ÂÇËÏ, êîòîðàÿ ñîîòâåòñòâóåò
ðåøåíèþ y* ýòîé âñïîìîãàòåëüíîé çàäà÷è, i — íîìåð ñòðîêè òàáëèöû, j — íîìåð
ñòîëáöà íåáàçèñíîé ïåðåìåííîé. Äàëåå ïåðåõîäèì íà øàã 1 ìåòîäà.
Çàìå÷àíèå 1. Ïðîöåññ ïîñòðîåíèÿ îòñå÷åíèé è ðåøåíèå çàâåðøàåòñÿ ëèáî ïî-
ëó÷åíèåì òî÷êè, êîòîðàÿ óäîâëåòâîðÿåò óñëîâèþ (5), ëèáî ïåðåõîäîì íà ãðàíü
ìåíüøåé ðàçìåðíîñòè ìíîãîãðàííèêà äîïóñòèìîé îáëàñòè òåêóùåé ÂÇËÏ. Ðàçðå-
øèòü ïîñëåäíþþ ñèòóàöèþ ïîçâîëÿåò ñëåäóþùåå äîñòàòî÷íî î÷åâèäíîå óòâåðæäå-
íèå: åñëè ïîñëå îòñå÷åíèÿ ñ ïîìîùüþ ðàâåíñòâà (14) èëè (÷òî òî æå ñàìîå) ñ ïî-
ìîùüþ íåðàâåíñòâà y j
jj J
t
tt
jt
�
�
�
�
� 1
0
(15)
è äàëüíåéøåãî íàõîæäåíèÿ òî÷êè y* â íàéäåííûõ ñ íåé ñìåæíûõ âåðøèíàõ íå-
ðàâåíñòâî (15) âûïîëíÿåòñÿ êàê ðàâåíñòâî, òî ðåøåíèå â äàëüíåéøåì íàõîäèòñÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 131
íà ãðàíè îáëàñòè (ò.å. íåðàâåíñòâî (15) îáðàùàþò â ðàâåíñòâî), ïðèñîåäèíÿåòñÿ
ê òåêóùåé ñèñòåìå îãðàíè÷åíèé è ïðîöåññ ðåøåíèÿ ïðîäîëæàåòñÿ. Òàêèì îáðà-
çîì, êîëè÷åñòâî âîçìîæíûõ ñîñåäíèõ âåðøèí óìåíüøàåòñÿ íà åäèíèöó.  èòîãå
ìîæåò îñòàòüñÿ îäíà âåðøèíà. Åñëè äëÿ íåå âûïîëíÿåòñÿ óñëîâèå (5), òî ýòà
âåðøèíà äàåò ðåøåíèå çàäà÷è (1)–(5), â ïðîòèâíîì ñëó÷àå èñõîäíàÿ çàäà÷à
(1)–(5) íå èìååò ðåøåíèÿ.
Îáîñíîâûâàåò îòñå÷åíèå ñëåäóþùàÿ òåîðåìà, àíàëîãè÷íàÿ òåîðåìå 4.1 èç [5]
äëÿ íåðàâåíñòâà (12).
Òåîðåìà 1. Ïóñòü â íåðàâåíñòâå (15), ãäå jt ( j Jt � � �t J � , � �| |J ) — íîìåðà
íåáàçèñíûõ ïåðåìåííûõ â ðåøåíèè y y yn q
* * *( , , )� �1 � ÂÇËÏ, âåëè÷èíà � jt
âû-
÷èñëÿåòñÿ ïî ôîðìóëå (13). Òîãäà íåðàâåíñòâó (15) âñå ñìåæíûå ñ y* âåðøèíû äî-
ïóñòèìîé îáëàñòè ÂÇËÏ óäîâëåòâîðÿþò êàê ðàâåíñòâó, à òî÷êà y* íåðàâåíñòâî (15)
íå óäîâëåòâîðÿåò.
Äîêàçàòåëüñòâî. Ïîñêîëüêó y yj j1
, ,�
�
— íåáàçèñíûå ïåðåìåííûå â òî÷êå
y* , òî â íåé îíè ðàâíû íóëþ. Òàêèì îáðàçîì, î÷åâèäíî, ÷òî òî÷êà y* íå óäîâëåòâî-
ðÿåò íåðàâåíñòâî (15). Ïî àëãîðèòìó ïîñòðîåíèÿ ñìåæíîé âåðøèíû äîïóñòèìîãî
ìíîãîãðàííèêà â ñèìïëåêñ-ìåòîäå (íàïðèìåð, [27, 28]) ó âåðøèíû ~y, êîòîðàÿ ñìåæ-
íà ñ âåðøèíîé y* , êîîðäèíàòà y j jt t
� � � �t J � , à äðóãèå êîîðäèíàòû èç íàáîðà
( , , )y yj j1
�
�
ðàâíû íóëþ, ò.å. â ëþáîé òî÷êå ~y íåðàâåíñòâî (15) âûïîëíÿåòñÿ êàê
ðàâåíñòâî. Òåîðåìà äîêàçàíà.
Êîíå÷íîñòü ïðåäëàãàåìîãî ìîäèôèöèðîâàííîãî ìåòîäà êîìáèíàòîðíîãî îòñå-
÷åíèÿ îñíîâûâàåòñÿ íà ñëåäóþùåì. Óñëîâèå (5) îçíà÷àåò îãðàíè÷åííîñòü îáëàñòè
äîïóñòèìûõ ðåøåíèé çàäà÷è (1)–(5). Äëÿ äîêàçàòåëüñòâà êîíå÷íîñòè ìåòîäà ìîæíî
ïðåäïîëîæèòü, ÷òî êàæäûé áàçèñ, ðàññìàòðèâàåìûé ïðè ðåøåíèè ÂÇËÏ, ÿâëÿåòñÿ
íåâûðîæäåííûì. Èíà÷å åñëè â ñòîëáöå ñâîáîäíûõ ÷ëåíîâ ñèìïëåêñ-òàáëèöû â
ñòðîêå i ïîÿâëÿåòñÿ íóëü, òî óðàâíåíèå
y yi ij j
j J
� �
�
� � 0 ,
ñîîòâåòñòâóþùåå ýòîé ñòðîêå ñèìïëåêñ-òàáëèöû, èñêëþ÷àåòñÿ èç íåå ñ ïîäñòà-
íîâêîé â öåëåâóþ ôóíêöèþ
y yi ij j
j J
� �
�
� � .
Íà îñíîâàíèè ñäåëàííûõ çàìå÷àíèé î÷åâèäíà êîíå÷íîñòü ìåòîäà. Äåéñòâè-
òåëüíî, ïåðåìåííàÿ yn q� (èç (14)) ïîñëå ïðèìåíåíèÿ äâîéñòâåííîãî ñèìïëåêñ-ìå-
òîäà âûâîäèòñÿ èç áàçèñà (ñòàíîâèòñÿ ðàâíîé íóëþ), ò.å. ãèïåðïëîñêîñòü (14) â ïå-
ðåñå÷åíèè ñ ðåáðàìè äîïóñòèìîé îáëàñòè ÂÇËÏ íîâûõ âåðøèí íå îáðàçóåò. Ïî-
ñêîëüêó ïðè yn q� � 0 ãèïåðïëîñêîñòü (14) ïðîõîäèò ÷åðåç ñìåæíûå âåðøèíû ê
òî÷êå y* , êîòîðàÿ îòñåêàåòñÿ, à âåðøèíó y* ìîæíî ñ÷èòàòü íåâûðîæäåííîé, òî ïî-
ñòðîåííàÿ ãèïåðïëîñêîñòü ïåðåñåêàåòñÿ ñ ðåáðàìè äîïóñòèìîé îáëàñòè òîëüêî ïî
âåðøèíàì îáëàñòè, ò.å. íîâûõ âåðøèí íå îáðàçóåòñÿ.
Ïðè ðåøåíèè îäíîé ÂÇËÏ îòñåêàåòñÿ (ïî ñìåæíûì âåðøèíàì) îäíà âåðøèíà
èëè ïðîèñõîäèò ïåðåõîä â ïðîñòðàíñòâî íà åäèíèöó ìåíüøåé ðàçìåðíîñòè (ñì. çà-
ìå÷àíèå 1). Êîíå÷íîñòü äîïóñòèìîé îáëàñòè çàäà÷è (1)–(5) è êîíå÷íîñòü ðàçìåð-
íîñòè îáåñïå÷èâàþò êîíå÷íîñòü ìåòîäà.
Çàìå÷àíèå 2. Îòìåòèì, ÷òî â äîïîëíèòåëüíîì èññëåäîâàíèè ýôôåêòèâíîñòè
ìîäèôèöèðîâàííîãî ìåòîäà êîìáèíàòîðíîãî îòñå÷åíèÿ íåò íåîáõîäèìîñòè, ïî-
ñêîëüêó îí èìååò îáùåå ñâîéñòâî ñ õîðîøî èçâåñòíûì ñèìïëåêñ-ìåòîäîì äëÿ
ÇËÏ — ïåðåáîð ñìåæíûõ âåðøèí (â ñèìïëåêñ-ìåòîäå — ïîñëå àíàëèçà âåðøèíû
íà îïòèìàëüíîñòü è íåîãðàíè÷åííîñòü öåëåâîé ôóíêöèè äëÿ ïåðåõîäà ê âåðøèíå ñ
132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
áîëüøèì (â íåâûðîæäåííîé çàäà÷å íà ìàêñèìóì) çíà÷åíèåì öåëåâîé ôóíêöèè,
à â ìîäèôèöèðîâàííîì ìåòîäå êîìáèíàòîðíîãî îòñå÷åíèÿ — ïîñëå àíàëèçà âåðøè-
íû íà óäîâëåòâîðåíèå óñëîâèÿ (5) è åå îòñå÷åíèÿ äëÿ ïåðåõîäà ê ñìåæíîé âåðøèíå
ñ ìåíüøèì çíà÷åíèåì öåëåâîé ôóíêöèè).
Ýôôåêòèâíîñòü ìîäèôèöèðîâàííîãî ìåòîäà êîìáèíàòîðíîãî îòñå÷åíèÿ ñðàâ-
íèìà ñ ýôôåêòèâíîñòüþ ñèìïëåêñ-ìåòîäà, ïîñêîëüêó îïðåäåëÿåòñÿ â îñíîâíîì
ýòèì ïåðåáîðîì âåðøèí, ò.å. àíàëîãè÷íî ñèìïëåêñ-ìåòîäó ìîæíî ïîñòðîèòü «ïàòî-
ëîãè÷åñêèå» ïðèìåðû, â êîòîðûõ ïåðåáèðàþòñÿ âñå âåðøèíû äîïóñòèìîé îáëàñòè.
Èñõîäÿ èç ýòîãî ìîæíî ñäåëàòü âûâîä, ÷òî ïðè ïðàêòè÷åñêîì ïðèìåíåíèè ìåòîä
îòñå÷åíèÿ áóäåò òàêèì æå ýôôåêòèâíûì, êàê è ñèìïëåêñ-ìåòîä.
ÈËËÞÑÒÐÀÒÈÂÍÛÉ ÏÐÈÌÅÐ
Ðàññìîòðèì ïðèìåð ïðèìåíåíèÿ ìîäèôèöèðîâàííîãî ìåòîäà êîìáèíàòîðíîãî îò-
ñå÷åíèÿ, êîòîðûé â [15] ðåøåí ñ èñïîëüçîâàíèåì ìåòîäà âîçìóùåíèÿ ×àðíñà.
Íàéòè
� �x4 max (16)
ïðè äîïîëíèòåëüíûõ îãðàíè÷åíèÿõ
x x x
x x
x x
1 2 4
3 4
1 2
0
0
0
� � �
� �
� �
�
�
�
�
�
;
;
;
(17)
x j � 0 , j � 1 2 3 4, , , , (18)
è ïðè êîìáèíàòîðíîì îãðàíè÷åíèè
x x x x E G� �( , , ) ( )1 2 3 , (19)
ãäå E G( ) — ìíîæåñòâî ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè èç ìóëüòèìíîæåñòâà
G � { }1 1 3, , .
Êàê èçâåñòíî [4, 20, 23–25], ìíîæåñòâà ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè ÿâëÿþòñÿ
âåðøèííî ðàñïîëîæåííûìè. Äëÿ ôîðìèðîâàíèÿ ïåðâîé ÂÇËÏ óñëîâèå (19) (x E� ) çà-
ìåíèì óñëîâèåì x E�conv , ò.å. çàïèøåì ñèñòåìó, êîòîðàÿ äàåò âûïóêëóþ îáîëî÷êó çà-
äàííîãî â (19) ìíîæåñòâà ïåðåñòàíîâîê E G( ) (íàïðèìåð, [4, 20, 23–25]), ïðè ýòîì ñâå-
äåì ñèñòåìó ê ôîðìå, íåîáõîäèìîé äëÿ êàíîíè÷åñêîãî âèäà ÇËÏ:
x x
x x
x x
x x x
x x x
x x
1 5
2 6
3 7
1 2 8
1 3 9
2
3
3
3
4
4
� �
� �
� �
� � �
� � �
�
;
;
;
;
;
3 10
1 2 3
4
5
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
x
x x x
;
,
(20)
x j � 0 , j � 1 2 10, , ,� .
 ñâÿçè ñ ýòèì ñèñòåìó (17) çàïèøåì â âèäå
x x x x
x x x
x x x
1 2 4 11
3 4 12
1 2 13
0
0
0
� � � �
� � �
� � �
�
�
�
�
�
;
;
,
(21)
x j � 0 � j.
Îòìåòèì, ÷òî äëÿ ÇËÏ èñïîëüçóåòñÿ òåðìèíîëîãèÿ, îáîçíà÷åíèÿ è ôîðìû ñèì-
ïëåêñ-òàáëèö èç [27], ïðè÷åì áàçèñíûå ñòîëáöû è íóëè, êàê ïðàâèëî, îïóñêàþòñÿ è
â òàáëèöå íå ïèøóòñÿ (ñîîòâåòñòâóþùèå êëåòî÷êè îñòàþòñÿ íåçàïîëíåííûìè).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 133
Òàêèì îáðàçîì, ïåðâàÿ ÂÇËÏ èìååò âèä (16), (20), (21) ïðè âñåõ íåîòðèöàòåëü-
íûõ ïåðåìåííûõ. Â ñèëó îòñóòñòâèÿ áàçèñà ââåäåì èñêóññòâåííóþ íåîòðèöàòåëü-
íóþ ïåðåìåííóþ x14 â ñåäüìîå óðàâíåíèå ñèñòåìû (20) è ïðèìåíèì M-ìåòîä
[27, 28]. Öåëåâàÿ ôóíêöèÿ ðàñøèðåííîé ÇËÏ äëÿ ïåðâîé ÂÇËÏ áóäåò èìåòü âèä
� � �x Mx4 14 max ,
ãäå M
0 — äîñòàòî÷íî áîëüøîå ÷èñëî.
 òàáë. 1 ïðèâåäåíû ðåçóëüòèðóþùàÿ ñèìïëåêñ-òàáëèöà ïåðâîé ÂÇËÏ è ñòîë-
áöû äëÿ ïîñòðîåíèÿ îòñå÷åíèÿ. Çäåñü P — ñòîëáåö íàçâàíèé áàçèñíûõ âåêòîðîâ,
â 11-é ñòðîêå — çíà÷åíèå öåëåâîé ôóíêöèè; Cá — êîýôôèöèåíòû öåëåâîé ôóíê-
öèè ïðè áàçèñíûõ ïåðåìåííûõ; P0 — ñòîëáåö ïðàâûõ ÷àñòåé îãðàíè÷åíèé;
P P P10 11 12, , — íåáàçèñíûå ñòîëáöû; � � �10 11 12, , — îïðåäåëÿþùèå êàê ìèíèìóì
ýëåìåíòîâ ýòèõ ñòîëáöîâ.
Èç òàáë. 1 âèäíî, ÷òî x1 1� (ñòðîêà 7); x2 3 2� / (ñòðîêà 8), x3 5 2� / (ñòðîêà 9),
ò.å. (1, 3/2, 5/2) íå ÿâëÿåòñÿ ïåðåñòàíîâêîé ÷èñåë (1, 1, 3); òàêèì îáðàçîì, êîìáèíà-
òîðíîå óñëîâèå (19) íå âûïîëíèëîñü. Ñòðîèì îòñå÷åíèå ïîëó÷åííîé òî÷êè.
 òàáë. 1 (â òðåõ ïîñëåäíèõ ñòîëáöàõ) ïî ôîðìóëå (13) íàéäåíû � j äëÿ íåáàçèñíûõ
ïåðåìåííûõ j � 10 11 12, , .
Çàïèñûâàåì îòñå÷åíèå (15), êîòîðîå â ýòîì ñëó÷àå (îòñóòñòâóþò íóëåâûå � j )
ñîâïàäàåò ñ (12):
x x x10 11 12
0 25 1 3
1
,
� � � .
Ïîñëåäíåå íåðàâåíñòâî çàïèñûâàåì â âèäå (14)
� � � � � �4
1
3
110 11 12 15x x x x ,
(23)
óäîáíîì ïðè èñïîëüçîâàíèè äâîéñòâåííîãî ñèìïëåêñ-ìåòîäà.
Äîáàâèâ (23) ê îãðàíè÷åíèÿì ïåðâîé ÂÇËÏ, ïîëó÷èì âòîðóþ ÂÇËÏ. Ïðàêòè-
÷åñêè ýòî îçíà÷àåò ââåäåíèå â ñèìïëåêñ-òàáëèöó (òàáë. 1) ñòðîêè, ñîîòâåòñòâóþùåé
(23), è ñòîëáöà P15 . Ïîëó÷àåì ïåðâóþ ñèìïëåêñ-òàáëèöó âòîðîé ÂÇËÏ, ïðè ïåðå-
ñ÷åòå êîòîðîé ïî ïðàâèëàì äâîéñòâåííîãî ñèìïëåêñ-ìåòîäà ïîëó÷àåì ðåøåíèå âòî-
ðîé ÂÇËÏ (òàáë. 2).
Îïòèìàëüíàÿ òî÷êà âòîðîé ÂÇËÏ èç òàáë. 2 îïðåäåëÿåò x1 5 4� / ; x2 5 4� / ,
x3 5 2� / . Ýòî íå ñîîòâåòñòâóåò ïåðåñòàíîâêå ÷èñåë 1, 1, 3, ò.å. óñëîâèå (19) íå âû-
ïîëíÿåòñÿ, ñòðîèì îòñå÷åíèå. Ïîñêîëüêó �15 0� , òî â ñîîòâåòñòâèè ñ (14) ïîëó÷èì
� � � � �
x x
x11 12
16
1 3
1.
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Ò à á ë è ö à 1
Íîìåð
ñòðîêè,
i
Áàçèñíûé
ñòîëáåö,
P
Cá P0 P10 P11 P12
� �i ij/
j � 10 j � 11 j � 12
1 P5 0 2 1 2 – –
2 P6 0 3/2 –1 –1/2 1/2 – – 3
3 P7 0 1/2 1/2 –1/2 – 1 –
4 P8 0 3/2 –1/2 1/2 – – 3
5 P9 0 1/2 1 1/2 –1/2 1/2 1 –
6 P4 –1 5/2 –1/2 –1/2 – – –
7 P1 0 1 –1 – – –
8 P2 0 3/2 1 1/2 –1/2 3/2 3 –
9 P3 0 5/2 –1/2 1/2 – – 5
10 P13 0 1/2 2 1/2 –1/2 1/4 1 –
11 –5/2 1/2 1/2 �10 1 4� / �11 1� �12 3�
Ïðèñîåäèíåíèå ýòîãî óñëîâèÿ ê ñèìïëåêñ-òàáëèöå èç òàáë. 2 äàåò ïåðâóþ ñèì-
ïëåêñ-òàáëèöó òðåòüåé ÂÇËÏ. Ïåðåñ÷åò ïîñëåäíåé äâîéñòâåííûì ñèìïëåêñ-ìåòî-
äîì äàåò òî÷êó x x x x� ( , , )1 2 3 ñ êîîðäèíàòàìè x1 1� ; x2 1� , x3 3� . Çíà÷åíèå öåëå-
âîé ôóíêöèè x4 ðàâíî –3. Òàêèì îáðàçîì, óñëîâèå (19) âèäà ( , , ) ( )1 1 3 �E G âûïîëíå-
íî. Èñõîäíàÿ çàäà÷à êîìáèíàòîðíîé îïòèìèçàöèè íà âåðøèííî ðàñïîëîæåííîì
ìíîæåñòâå ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè ðåøåíà.
 òàáë. 2. ïðèâåäåíû ðåçóëüòèðóþùàÿ ñèìïëåêñ-òàáëèöà âòîðîé ÂÇËÏ è ñòîë-
áöû äëÿ ïîñòðîåíèÿ îòñå÷åíèÿ.
Òàêèì îáðàçîì, ïðåäëîæåíà è îáîñíîâàíà ìîäèôèêàöèÿ ìåòîäà îòñå÷åíèÿ â
óñëîâíûõ ëèíåéíûõ çàäà÷àõ îïòèìèçàöèè íà âåðøèííî ðàñïîëîæåííûõ êîìáèíà-
òîðíûõ ìíîæåñòâàõ ïðè íàëè÷èè âûðîæäåííûõ áàçèñîâ âî âñïîìîãàòåëüíûõ ÇËÏ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È .  . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè.
— Êèåâ: Íàóê. äóìêà, 1988. — 472 ñ.
2. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíàòîðíûõ
çàäà÷ îïòèìèçàöèè. — Ê.: Íàóê. äóìêà, 1981.— 288 ñ.
3. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: Ïðîáëåìû, ìåòîäû
ðåøåíèÿ, èññëåäîâàíèÿ. — Ê.: Íàóê. äóìêà, 2003. — 265 ñ.
4. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Êè¿â: ²í-ò
ñèñòåì. äîñë³äæåíü îñâ³òè, 1993. — 188 ñ.
5. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Îïòèì³çàö³ÿ íà ïîë³ðîçì³ùåííÿõ: òåîð³ÿ òà
ìåòîäè. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ.
6. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê ³ í à Ë . Ì . Çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³ÿ ç äðîáîâî-ë³í³éíèìè
ôóíêö³ÿìè. — Ê.: Íàóê. äóìêà, 2005. — 117 ñ.
7. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à Î .  . Çàäà÷³ îïòèì³çàö³¿ íà ïîë³êîìá³íàòîðíèõ ìíîæèíàõ:
âëàñòèâîñò³ òà ðîçâ’ÿçóâàííÿ. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2006. — 129 ñ.
8. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ. — Ê.: Íàóê.
äóìêà, 2008. — 159 ñ.
9. à ó ë ÿ í è ö ü ê è é Ë . Ô . Ðîçðîáêà ìîäåëåé ³ íàáëèæåíèõ ìåòîä³â êîìá³íàòîðíî¿ îïòèì³çàö³¿ òà ¿õ
çàñòîñóâàííÿ â ³íôîðìàö³éíèõ òåõíîëîã³ÿõ: Àâòîðåô. äèñ. ... ä-ðà òåõí. íàóê: 01.05.02 / ÍÀÍ
Óêðà¿íè. ²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà. — Ê., 2005. — 32 ñ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 135
Ò à á ë è ö à 2
Íîìåð
ñòðîêè,
i
Áàçèñíûé
ñòîëáåö,
P
Cá P0 P11 P12 P15
� �i ij/
j � 11 j � 12 j � 15
1 P5 0 7/4 –1/4 –1/12 1/4 – – 7
2 P6 0 7/4 –1/4 7/12 –1/4 – 3 –
3 P7 0 1/2 1/2 –1/2 1 – –
4 P8 0 3/2 –1/2 1/2 – 3 –
5 P9 0 1/4 1/4 –7/12 1/4 1 – 1
6 P4 –1 5/2 –1/2 –1/2 – – –
7 P1 0 5/4 1/4 1/12 –1/4 5 15 –
8 P2 0 5/4 1/4 –7/12 1/4 5 – 5
9 P3 0 5/2 –1/2 1/2 – 5 –
10 P13 0 0 0 –3/2 1/2 – – 0
11 P10 0 1/4 1/4 1/12 –1/4 1 3 –
12 –5/2 1/2 1/2 �11 1� �12 3� �15 0�
10. à ð å á å í í ³ ê ² .  . Ìàòåìàòè÷í³ ìîäåë³ òà ìåòîäè êîìá³íàòîðíî¿ îïòèì³çàö³¿ â ãåîìåòðè÷íîìó
ïðîåêòóâàíí³. Àâòîðåô. äèñ. ... ä-ð. òåõí. íàóê: 01.05.02 / ²í-ò ïðîáë. ìàøèíîáóäóâàííÿ
³ì. À.Ì. ϳäãîðíîãî. — Õàðê³â, 2006. — 34 ñ.
11. Å ì å ö Î . À . Ìåòîä îòñå÷åíèÿ ïðè ðåøåíèè îäíîãî êëàññà ëèíåéíûõ åâêëèäîâûõ êîìáèíàòîðíûõ
çàäà÷ îïòèìèçàöèè / Ïîëò. òåõí. óí-ò. — Ïîëòàâà, 1995. — 20 ñ. — Äåï. â ÃÍÒÁ Óêðàèíû 02.06.95,
¹ 1408-Óê95.
12. Å ì å ö Î . À . Îá îäíîì ìåòîäå îòñå÷åíèÿ äëÿ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè // Ýêîíîìèêà è
ìàò. ìåòîäû. — 1997. — 33, âûï. 4. — Ñ. 120–129.
13. Å ì å ö Î . À . , Å ì å ö Å . Ì . Îòñå÷åíèÿ â ëèíåéíûõ ÷àñòè÷íî êîìáèíàòîðíûõ çàäà÷àõ åâêëèäîâîé
êîìáèíàòîðíîé îïòèìèçàöèè / Ïîëò. òåõí. óí-ò. — Ïîëòàâà, 1995. — 21 ñ. — Äåï. â ÃÍÒÁ Óêðàèíû
01.12.95, ¹2562-Óê95.
14. ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . ³äñ³êàííÿ â ë³í³éíèõ ÷àñòêîâî êîìá³íàòîðíèõ çàäà÷àõ åâêë³äîâî¿
êîìá³íàòîðíî¿ îïòèì³çàö³¿ // Äîï. ÍÀÍÓ. — 2000. — ¹ 9. — Ñ. 105–109.
15. ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Ìåòîä â³äñ³êàííÿ â åâêë³äîâ³é êîìá³íàòîðí³é îïòèì³çàö³¿.: Íàâ÷.
ïîñ³áíèê. — Ïîëòàâà, 1997. — 30 ñ.
16. Å ì å ö Î . À . , Å ì å ö Å . Ì . Îòñå÷åíèÿ â ëèíåéíûõ ÷àñòè÷íî êîìáèíàòîðíûõ çàäà÷àõ îïòè-
ìèçàöèè íà ïåðåñòàíîâêàõ // Ýêîíîìèêà è ìàò. ìåòîäû. — 2001. — 37, ¹ 1. — Ñ. 118–121.
17. ª ì å ö ü Î . Î . , × ³ ë ³ ê ³ í à Ò .  . Íåë³í³éí³ çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³¿ íà âåðøèííî
ðîçòàøîâàíèõ ìíîæèíàõ òà ¿õ ðîçâ’ÿçóâàííÿ // Äèíàìè÷åñêèå ñèñòåìû (Ìåæâåä. íàó÷. ñá.). — 2004.
Âûï. 17. — Ñèìôåðîïîëü: Òàâðè÷. íàö. óí-ò. — Ñ. 160–165.
18. Å ì å ö Î . À . , Ê î ë å ÷ ê è í à Ë . Í . Ðåøåíèå çàäà÷ îïòèìèçàöèè ñ äðîáíî-ëèíåéíûìè öåëåâûìè
ôóíêöèÿìè è äîïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè íà ïåðåñòàíîâêàõ // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2004. — ¹ 3. — Ñ. 30–43.
19. Å ì å ë è ÷ å â Â . À . , Ê î â à ë å â Ì . Ì . , Ê ð à â ö î â Ì . Ê . Ìíîãîãðàííèêè, ãðàôû, îïòèìèçàöèÿ.
— Ì.: Íàóêà, 1981. — 344 ñ.
20. Å ì å ö Î . À . Åâêëèäîâû êîìáèíàòîðíûå ìíîæåñòâà è îïòèìèçàöèÿ íà íèõ. Íîâîå â ìàòåìàòè-
÷åñêîì ïðîãðàììèðîâàíèè.: Ó÷åáíîå ïîñîáèå. — Ê.: ÓÌÊ ÂÎ, 1992. — 92 ñ.
21. Å ì å ö Î . À . Çàäà÷è îïòèìèçàöèè íà åâêëèäîâîì ïîëèïåðåñòàíîâî÷íîì ìíîæåñòâå ñ ïîâòî-
ðåíèÿìè: ñâîéñòâà äîïóñòèìîãî ìíîæåñòâà // Â êí.: Ìåòîäû è ïðîãðàììíûå ñðåäñòâà îïòèìèçàöèè,
ìîäåëèðîâàíèÿ è ñîçäàíèÿ âû÷èñëèòåëüíûõ ñèñòåì: Ñá. íàó÷. òð. /ÀÍ ÓÑÑÐ. Èí-ò êèáåðíåòèêè ÀÍ
ÓÑÑÐ. — Êèåâ, 1990. — Ñ. 22–24.
22. Å ì å ö Î . À . Êîìáèíàòîðíàÿ ìîäåëü è ïðèáëèæåííûé ìåòîä ñ àïðèîðíîé îöåíêîé ðåøåíèÿ
îïòèìèçàöèîííîé çàäà÷è ðàçìåùåíèÿ ðàçíîöâåòíûõ ïðÿìîóãîëüíèêîâ // Ýêîíîìèêà è ìàò. ìåòîäû.
— 1993. — 29, âûï. 2. — Ñ. 294–304.
23. Å ì å ö Î . À . Îá îáùåì ïîëèïåðåñòàíîâî÷íîì ìíîãîãðàííèêå è íåêîòîðûõ åãî ñâîéñòâàõ / Ïîëò.
èíæ.-ñòðîèò. èí-ò. — Ïîëòàâà, 1989. — 11 ñ. — Äåï. â ÓêðÍÈÈÍÒÈ 31.10.89, ¹ 2362Óê-89.
24. Å ì å ö Î . À . Îáùèé ïåðåñòàíîâî÷íûé ìíîãîãðàííèê è íåêîòîðûå åãî ñâîéñòâà / Ïîëò. èíæ.-
ñòðîèò. èí-ò. — Ïîëòàâà, 1983. — 20 ñ. — Äåï. â ÓêðÍÈÈÍÒÈ 28.06.83, ¹ 616 — ÓêÄ83.
25. Ñ ò î ÿ í Þ . à . , Å ì å ö Î . À . Î êîìáèíàòîðíûõ çàäà÷àõ ðàçìåùåíèÿ ïðÿìîóãîëüíèêîâ //
Ýêîíîìèêà è ìàò. ìåòîäû. — 1985. — 21, âûï. 5. — Ñ. 868–881.
26. Ñ ò î ÿ í Þ . à . , ß ê î â ë å â Ñ .  . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåî-
ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Ê.: Íàóê. äóìêà, 1986. — 268 ñ.
27. À ê ó ë è ÷ È . Ë . Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå â ïðèìåðàõ è çàäà÷àõ. — Ì.: Âûñø. øê., 1986.
— 319 ñ.
28. Å ð ì î ë ü å â Þ . Ì . , Ë ÿ ø ê î È . È . , Ì è õ à ë å â è ÷  . Ñ . , Ò þ ï ò ÿ  . È . Ìàòåìàòè÷åñêèå
ìåòîäû èññëåäîâàíèÿ îïåðàöèé. — Êèåâ: Âèùà øê., 1979. — 312 ñ.
Ïîñòóïèëà 28.10.2008
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-44408 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:23:07Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Емец, Е.М. 2013-06-01T08:36:50Z 2013-06-01T08:36:50Z 2009 Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах / О.А. Емец, Е.М. Емец // Кибернетика и системный анализ. — 2009. — № 5. — С. 129-136. — Бібліогр.: 28 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44408 519.85 Розглянуто модифікацію методу комбінаторного відсікання для оптимізації на вершинно розташованих множинах, який дозволяє працювати з виродженими рішеннями допоміжних задач.Обґрунтовано вигляд нерівності–відсікання. Наведено ілюстративний приклад застосування методу. A modification of the method combinatorial cutting for optimization over vertex-located sets is considered. The modification allows working with degenerated decisions of auxiliary problems. The type of an inequality-cutting is grounded. An illustrative example of application of the method is given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах Модифікація методу комбінаторного відсікання в задачах оптимізації на вершинно розташованих множинах A modification of the method of combinatorial cutting in optimization problems over vertex-located sets Article published earlier |
| spellingShingle | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах Емец, О.А. Емец, Е.М. Системный анализ |
| title | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах |
| title_alt | Модифікація методу комбінаторного відсікання в задачах оптимізації на вершинно розташованих множинах A modification of the method of combinatorial cutting in optimization problems over vertex-located sets |
| title_full | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах |
| title_fullStr | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах |
| title_full_unstemmed | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах |
| title_short | Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах |
| title_sort | модификация метода комбинаторного отсечения в задачах оптимизации на вершинно расположенных множествах |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44408 |
| work_keys_str_mv | AT emecoa modifikaciâmetodakombinatornogootsečeniâvzadačahoptimizaciinaveršinnoraspoložennyhmnožestvah AT emecem modifikaciâmetodakombinatornogootsečeniâvzadačahoptimizaciinaveršinnoraspoložennyhmnožestvah AT emecoa modifíkacíâmetodukombínatornogovídsíkannâvzadačahoptimízacíínaveršinnoroztašovanihmnožinah AT emecem modifíkacíâmetodukombínatornogovídsíkannâvzadačahoptimízacíínaveršinnoroztašovanihmnožinah AT emecoa amodificationofthemethodofcombinatorialcuttinginoptimizationproblemsoververtexlocatedsets AT emecem amodificationofthemethodofcombinatorialcuttinginoptimizationproblemsoververtexlocatedsets |