Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями
Запропоновано та обґрунтовано прямий метод відсікання для розв’язування комбінаторних задач оптимізації на полірозміщеннях з додатковими обмеженнями. Метод не дозволяє будувати лінійну оболонку множини полірозміщень і отримувати на кожному етапі допустимий розв’язок. A direct pruning method to solve...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84256 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями / О.А. Емец, Е.М. Емец, Ю.Ф. Олексийчук // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 116-124. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859901082069630976 |
|---|---|
| author | Емец, О.А. Емец, Е.М. Олексийчук, Ю.Ф. |
| author_facet | Емец, О.А. Емец, Е.М. Олексийчук, Ю.Ф. |
| citation_txt | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями / О.А. Емец, Е.М. Емец, Ю.Ф. Олексийчук // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 116-124. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано та обґрунтовано прямий метод відсікання для розв’язування комбінаторних задач оптимізації на полірозміщеннях з додатковими обмеженнями. Метод не дозволяє будувати лінійну оболонку множини полірозміщень і отримувати на кожному етапі допустимий розв’язок.
A direct pruning method to solve combinatorial optimization problems on polyarrangements with additional constraints is proposed and substantiated in the paper. The method allows obtaining a feasible solution at each stage without constructing the linear hull of the set of polyarrangements.
|
| first_indexed | 2025-12-07T15:57:53Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Î.À. ÅÌÅÖ, Å.Ì. ÅÌÅÖ, Þ.Ô. ÎËÅÊÑÈÉ×ÓÊ
ÏÐßÌÎÉ ÌÅÒÎÄ ÎÒÑÅ×ÅÍÈÉ ÄËß ÇÀÄÀ× ÊÎÌÁÈÍÀÒÎÐÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÈ Ñ ÄÎÏÎËÍÈÒÅËÜÍÛÌÈ ÎÃÐÀÍÈ×ÅÍÈßÌÈ
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ïîëèðàçìåùåíèå, êîìáèíà-
òîðíûé ìåòîä îòñå÷åíèé.
ÂÂÅÄÅÍÈÅ
Òî÷íûå ìåòîäû ðåøåíèÿ åâêëèäîâûõ êîìáèíàòîðíûõ çàäà÷ ìîæíî óñëîâíî
ðàçäåëèòü íà ìåòîäû îòñå÷åíèÿ è êîìáèíàòîðíûå.
Ðàçðàáîòêå ìåòîäîâ êîìáèíàòîðíîé îïòèìèçàöèè, èññëåäîâàíèþ ñâîéñòâ
âûïóêëûõ îáîëî÷åê êîìáèíàòîðíûõ ìíîæåñòâ ïîñâÿùåíî ìíîãî ïóáëèêàöèé
(â ÷àñòíîñòè, [1–12]).  [13] ðàññìîòðåí ïðÿìîé ìåòîä äëÿ ðåøåíèÿ ëèíåéíûõ öå-
ëî÷èñëåííûõ çàäà÷ îïòèìèçàöèè. Äëÿ ìåòîäîâ êîìáèíàòîðíîãî îòñå÷åíèÿ îäíîé
èç ïðîáëåì ÿâëÿåòñÿ èñïîëüçîâàíèå îïèñàíèÿ êîìáèíàòîðíûõ ìíîãîãðàííèêîâ â
âèäå ëèíåéíûõ îãðàíè÷åíèé, êîëè÷åñòâî êîòîðûõ óâåëè÷èâàåòñÿ ýêñïîíåíöèàëü-
íî ñ ðîñòîì êîëè÷åñòâà ýëåìåíòîâ êîìáèíàòîðíûõ ìíîæåñòâ. Ïîýòîìó ïåðñïåê-
òèâíûìè ñ÷èòàþòñÿ ìåòîäû, â êîòîðûõ íàäî ñòðîèòü ëèøü ÷àñòü êîìáèíàòîðíûõ
îãðàíè÷åíèé èëè íå ñòðîèòü èõ âîîáùå.
 äàííîé ðàáîòå ñ èñïîëüçîâàíèåì èäåé èç [13] ïðåäëîæåí è îáîñíîâàí ìå-
òîä ðåøåíèÿ åâêëèäîâûõ êîìáèíàòîðíûõ çàäà÷ íà ïîëèðàçìåùåíèÿõ ñ íåêîòîðû-
ìè äîïîëíèòåëüíûìè óñëîâèÿìè.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ðàññìîòðèì åâêëèäîâó çàäà÷ó êîìáèíàòîðíîé îïòèìèçàöèè íà ïîëèðàçìåùåíèÿõ:
íàéòè óïîðÿäî÷åííóþ ïàðó � �x f x* *, ( ) :
f f x f x
x E n
ks
* *( ) ( )� �
�
max
�
,
x f x
x E n
ks
* ( )�
�
arg max
�
(1)
ïðè ëèíåéíûõ îãðàíè÷åíèÿõ
a x aij j
j
k
i
�
� �
1
0 (i t�1 2, , ,� ) (2)
è íåêîòîðûõ äîïîëíèòåëüíûõ îãðàíè÷åíèÿõ
h xi ( ) � 0 (i q�1 2, , ,� ), (3)
ãäå E n
ks
� — åâêëèäîâî ìíîæåñòâî ïîëèðàçìåùåíèé [2, 3], ýëåìåíòû êîòîðî-
ãî — öåëûå ÷èñëà, f x( ) — ëèíåéíàÿ ôóíêöèÿ, h xi ( ) — íåêîòîðûå èçâåñòíûå
ôóíêöèè ëþáîãî êëàññà.
Ìíîæåñòâîì ïîëèðàçìåùåíèé ñîãëàñíî [2, 3] áóäåì ñ÷èòàòü ìíîæåñòâî,
îïðåäåëÿåìîå ñëåäóþùèì îáðàçîì.
Ïóñòü Jn — ìíîæåñòâî n ïåðâûõ íàòóðàëüíûõ ÷èñåë, ò.å. J nn � { }1 2, , ,� .
Ïîä ìóëüòèìíîæåñòâîì G g g g� { }1 2, , ,� � áóäåì ïîíèìàòü ñîâîêóïíîñòü ýëå-
ìåíòîâ, ñðåäè êîòîðûõ ìîãóò áûòü è îäèíàêîâûå (íåðàçëè÷èìûå) [2].
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
� Î.À. Åìåö, Å.Ì. Åìåö, Þ.Ô. Îëåêñèé÷óê, 2011
Ëþáîå ìóëüòèìíîæåñòâî A ìîæíî ïðåäñòàâèòü åãî îñíîâîé S A( ), ò.å. ìíî-
æåñòâîì âñåõ åãî ðàçíûõ ýëåìåíòîâ, è ïåðâè÷íîé ñïåöèôèêàöèåé [ ]A — ñïèñêîì
êðàòíîñòåé ýëåìåíòîâ îñíîâû ìóëüòèìíîæåñòâà. Ìóëüòèìíîæåñòâî B ñ îñíîâîé
S B( ) íàçûâàåòñÿ ïîäìóëüòèìíîæåñòâîì A, åñëè S B S A( ) ( ) è äëÿ êàæäîãî ýëå-
ìåíòà a S B� ( ) ñïðàâåäëèâî íåðàâåíñòâî k a k aB A( ) ( )� , ãäå k aX ( ) — êðàòíîñòü
ýëåìåíòà a â ìóëüòèìíîæåñòâå X . Ñóììîé A B
ìóëüòèìíîæåñòâ A è B íàçûâà-
þò ìóëüòèìíîæåñòâî ñ îñíîâîé S A B S A S B( ) ( ) ( )
� � è êðàòíîñòÿìè ýëåìåíòîâ,
ðàâíûìè ñóììå êðàòíîñòåé ñîîòâåòñòâóþùèõ ýëåìåíòîâ â ìóëüòèìíîæåñòâàõ A è B.
Ðàññìîòðèì óïîðÿäî÷åííîå ðàçáèåíèå ìóëüòèìíîæåñòâà G íà s íåïóñòûõ
ïîäìóëüòèìíîæåñòâ G G Gs1 2, , ,� , ò.å. G Gi
i
s
�
� �
1
, à òàêæå k-âûáîðêó èç ìóëüòè-
ìíîæåñòâà G âèäà
g g g g g g g g g g
p p
s s
p
s
s
� ( , , , , , , , , , , , , )
1
1
2
1 1
1
2
2
2 2
1 21 2
� � � � , (4)
ãäå g Gj
l
l� , j J pl
� , pl — êîëè÷åñòâî ýëåìåíòîâ â âûáîðêå èç ìóëüòèìíî-
æåñòâà Gl , l J s� , p kl� � .
Ìíîæåñòâî A Gn
ks
� ( ), ýëåìåíòû êîòîðîãî — ðàçíûå óïîðÿäî÷åííûå k-âûáîð-
êè âèäà (4) èç ìóëüòèìíîæåñòâà G, íàçûâàþò [2, 3] åâêëèäîâûì êîìáèíàòîðíûì
ìíîæåñòâîì ïîëèðàçìåùåíèé, à åãî ýëåìåíòû — ïîëèðàçìåùåíèÿìè.
Îòîáðàæåíèå
� � �: A E Rn
ks k� (5)
íàçûâàþò [2, 3] ïîãðóæåíèåì A n
ks
� â àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî,
åñëè ìåæäó A n
ks
� è E� ñóùåñòâóåò âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå, óñòàíîâ-
ëåííîå ïðàâèëîì: äëÿ
g g g g g g g g g g gk p p
� �( , , , ) ( , , , , , , , , ,1 2 1
1
2
1 1
1
2
2
2 2
11 2
� � � �
s s
p
s
n
ksg g A
s
, , , )
2
� � � ,
x g� �( ), x x x x Ek� �( , , , )1 2 � �
èìååì x gj j�
�j Jk .
Îáîçíà÷èì ïîãðóæåííîå åâêëèäîâî êîìáèíàòîðíîå ìíîæåñòâî íà ïîëèðàç-
ìåùåíèÿõ E Gn
ks
� ( ), èëè E n
ks
� . Íåíóëåâîé âåêòîð x R k� íàçûâàåòñÿ ëåêñèêîãðàôè-
÷åñêè ïîëîæèòåëüíûì (îáîçíà÷åíèå x � 0 ), åñëè ïîëîæèòåëüíà åãî ïåðâàÿ íåíó-
ëåâàÿ êîîðäèíàòà. Âåêòîð x R k� ëåêñèêîãðàôè÷åñêè áîëüøå âåêòîðà y R k�
(îáîçíà÷åíèå x y� ), åñëè x y� � 0.
Öåëîé ÷àñòüþ äåéñòâèòåëüíîãî ÷èñëà a (îáîçíà÷åíèå [ ]a ) íàçûâàåòñÿ ñàìîå
áîëüøîå öåëîå ÷èñëî, êîòîðîå íå áîëüøå a. Äðîáíîé ÷àñòüþ ÷èñëà a (îáîçíà÷å-
íèå { }a ) íàçûâàåòñÿ ðàçíîñòü a a� [ ] .
ÏÐßÌÎÉ ÌÅÒÎÄ ÎÒÑÅ×ÅÍÈÉ ÄËß ÇÀÄÀ× ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Ââåäåì äîïîëíèòåëüíûå óñëîâèÿ íà ìóëüòèìíîæåñòâî G.
Óñëîâèå 1. Ïóñòü â G ñîäåðæèòñÿ ìèíèìóì k íóëåé, ïðè÷åì ïîäìóëüòèìíî-
æåñòâà Gi ñîäåðæàò ìèíèìóì pi íóëåé, i J s� , à îñòàëüíûå ýëåìåíòû — öåëûå.
Ýòî óñëîâèå íàçîâåì óñëîâèåì äîñòàòî÷íîãî êîëè÷åñòâà íóëåé è öåëî÷èñëåííîñòè
(óñëîâèå ÄÊÍÖ).
Óñëîâèå 2. Íà÷àëüíîå íóëåâîå ðåøåíèå óäîâëåòâîðÿåò óñëîâèÿì (3).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 117
Ðàññìîòðèì àëãîðèòì ðåøåíèÿ çàäà÷è (1)–(3) ñ ýòèìè óñëîâèÿìè. Çäåñü èñ-
ïîëüçóþòñÿ ôîðìû ñèìïëåêñ-òàáëèö, êàê â [13], ñ îáîçíà÷åíèÿìè èç [14].  ïî-
ñëåäíåé ñòðîêå â ñòîëáöàõ Pj — îöåíêè � j , â P0 — çíà÷åíèå öåëåâîé ôóíêöèè.
Ïðîèçâîäÿùåé íàçîâåì ñòðîêó, ïî êîòîðîé ñòðîèòñÿ îòñå÷åíèå.
Øàã 0. Ïîñòðîèòü ñèìïëåêñ-òàáëèöó ñîîòâåòñòâåííîé çàäà÷è ëèíåéíîãî
ïðîãðàììèðîâàíèÿ (áåç ó÷åòà êîìáèíàòîðíûõ óñëîâèé): f x( ) max� ïðè óñëî-
âèè (2). Ê ñèìïëåêñ-òàáëèöå ïðèñîåäèíÿåòñÿ ñòðîêà (L-ñòðîêà), ñîîòâåòñòâóþùàÿ
îãðàíè÷åíèþ, êîòîðîå âûðàæàåò âåðõíþþ ãðàíèöó íåáàçèñíûõ ïåðåìåííûõ
x x aL j
j J
L
�
�
� 0 . (6)
Çäåñü J — ìíîæåñòâî íåáàçèñíûõ ïåðåìåííûõ, a xL i
i
k
0
1
�
�
� , ãäå xi — ìàêñè-
ìàëüíî âîçìîæíîå èëè áîëüøåå, ÷åì ìàêñèìàëüíî âîçìîæíîå, çíà÷åíèå ïåðå-
ìåííîé xi ïðè óñëîâèÿõ çàäà÷è (1)–(3), xL � 0 — áàçèñíàÿ ïåðåìåííàÿ, ââåäåí-
íàÿ äëÿ ïîëó÷åíèÿ ðàâåíñòâà èç ïðèñîåäèíåííîãî íåðàâåíñòâà.
Øàã 1. Ïðîâåðèòü óñëîâèå îïòèìàëüíîñòè äëÿ ðåøåíèÿ çàäà÷è ëèíåéíîãî
ïðîãðàììèðîâàíèÿ (ÇËÏ): åñëè îöåíêè � j � 0, òî ðåøåíèå îïòèìàëüíîå è îñòà-
íîâêà; èíà÷å — ïåðåõîä íà øàã 2.
Øàã 2. Âûáðàòü íàïðàâëÿþùèé ñòîëáåö ñ íîìåðîì � êàê ñòîëáåö, êîòîðûé
óäîâëåòâîðÿåò óñëîâèÿì aL� � 0 è r rj� � äëÿ âñåõ j � �, j J� ïðè aL� � 0, ãäå
r
a
a
a
a
a
j
j
Lj
j
Lj
nj
Lj
�
�
�
�
�
�
�
�
�
�
, , ,
1
� .
Øàã 3. Âûáðàòü íîìåð v ïðîèçâîäÿùåé ñòðîêè, íà îñíîâàíèè êîòîðîé áóäåò
ñòðîèòüñÿ îòñå÷åíèå, èç ìíîæåñòâà íîìåðîâ ñòðîê
V i
a
a
io
i
( )�
�
�� �
�
�
�
�
�
� �
�
!
"
#
$
0 % , (7)
ãäå %�
��
�
�
�
min
a
i J
i
ii
k t
a
a0
0 , ïî ñëåäóþùèì ïðàâèëàì.
1. Ïóñòü Vt ( )� — ìíîæåñòâî V ( )� , êîòîðîå ñîîòâåòñòâóåò t-é ñèìïëåêñ-òàá-
ëèöå. Åñëè Vt ( )� ñîäåðæèò áîëüøå îäíîãî ýëåìåíòà: V v v vt m( ) , , ,� � { }1 2 � , òî
âûáèðàåì ñòðîêó v� , êîòîðàÿ â ïîñëåäîâàòåëüíîñòè V1 ( )� , V Vt2 ( ), , ( )� �& ïîÿâè-
ëàñü ðàíüøå (íå ïîçæå) äðóãèõ v Vi t� ( )� è ñîõðàíÿëàñü äîVt ( )� . Ïåðåéòè ê ï. 2.
2. Ïîñëåäîâàòåëüíî âûáèðàòü ñòðîêó v èç ï. 1, ïîêà v V� ( )� . Åñëè v V' ( )� ,
ïåðåéòè ê ï. 1 [13].
Øàã 4. Äîáàâèòü â ñèìïëåêñ-òàáëèöó îòñå÷åíèå
x
a
a
a
a
xm
v
v
vj
v
j
j J
�
�
�
�
�
�
�
�
�
�
�
�
�
� ��1
0
� �
( ) (8)
è ïðîâåðèòü, óäîâëåòâîðÿåò ëè ñëåäóþùåå äîïóñòèìîå ðåøåíèå íîâîé ÇËÏ
êîìáèíàòîðíûì (x E n
ks� � ) è äîïîëíèòåëüíûì îãðàíè÷åíèÿì (3). Åñëè äà — ïå-
ðåéòè ê øàãó 7. Èíà÷å — d �1 , ïåðåéòè ê øàãó 5.
Øàã 5. Çàìåíèòü îòñå÷åíèå (8) îòñå÷åíèåì
x
a
a
d
a
a
d qm
v
v
vj
v
�
�
�
�
�
�
� �
�
�
��
�
�
��
�
�
�
�
�
� �
�
�
�
�
�
�
1
0
� �
�
�
�
�
� ( )x j
j J
, (9)
ãäå q �1, åñëè
a
a
a
a
v
v
vj
v
0
� �
�
!
"
#
$
(
�
!
"
#
$
, èíà÷å q � 0.
Ïåðåéòè ê øàãó 6.
118 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Øàã 6. Ïðîâåðèòü, óäîâëåòâîðÿåò ëè ñëåäóþùåå äîïóñòèìîå ðåøåíèå ÇËÏ
êîìáèíàòîðíûì è äîïîëíèòåëüíûì îãðàíè÷åíèÿì. Åñëè äà — ïåðåéòè ê øàãó 7.
Èíà÷å — óâåëè÷èòü d íà åäèíèöó, ïåðåéòè ê øàãó 5.
Øàã 7. Ïðîâåñòè ñèìïëåêñ-ïðåîáðàçîâàíèå, ãäå íàïðàâëÿþùèì âûñòóïàåò
ñòîëáåö ñ íîìåðîì �, à íàïðàâëÿþùåé ñòðîêîé — äîáàâëåííîå îòñå÷åíèå.
Øàã 8. Óäàëèòü ñòðîêó èç ñèìïëåêñ-òàáëèöû, êîòîðàÿ ñîîòâåòñòâóåò äîáàâ-
ëåííîìó îòñå÷åíèþ. Ïåðåéòè ê øàãó 1.
ÎÁÎÑÍÎÂÀÍÈÅ ÌÅÒÎÄÀ
Îòñå÷åíèå íàçûâàåòñÿ ïðàâèëüíûì, åñëè ïðè äîáàâëåíèè åãî â ñèñòåìó îãðà-
íè÷åíèé çàäà÷è (1)–(3) îáëàñòü äîïóñòèìûõ ðåøåíèé íå ìåíÿåòñÿ.
Äîêàæåì, ÷òî îòñå÷åíèÿ (8) è (9) ïðàâèëüíûå.
Ïóñòü íà íåêîòîðîì øàãå íàïðàâëÿþùèì ÿâëÿåòñÿ �-é ñòîëáåö, à ïðîèçâîäÿ-
ùåé ñòðîêîé — v-ÿ ñòðîêà. Ðàçäåëèâ ïðîèçâîäÿùóþ ñòðîêó íà av� , ïîëó÷àåì
ñòðîêó
a x a x x a x a x am m1 1 1 1 1 1 0
�� �
� �� � � � � . (10)
Ïóñòü, íå íàðóøàÿ îáùíîñòè, áóäåì ñ÷èòàòü { } { }a ai � 0 äëÿ
�i J l è
{ } { }a ai � 0 äëÿ âñåõ îñòàëüíûõ i.
Òåîðåìà 1. Îòñå÷åíèå (8), çàïèñàííîå â âèäå íåðàâåíñòâà
[ ] [ ] [ ] [ ] [ ]a x a x x a x a x am m1 1 1 1 1 1 0
�� �
� �� � � � � (11)
ÿâëÿåòñÿ ïðàâèëüíûì äëÿ çàäà÷è (1)–(3).
Äîêàçàòåëüñòâî. Äîêàæåì, ÷òî (8) íå îòñåêàåò îò äîïóñòèìîé îáëàñòè ñîîò-
âåòñòâóþùåé ÇËÏ íè îäíîé òî÷êè ñ öåëî÷èñëåííûìè êîîðäèíàòàìè, à çíà÷èò,
è äîïóñòèìîé òî÷êè èñõîäíîé çàäà÷è, ò.å. ÿâëÿåòñÿ ïðàâèëüíûì äëÿ çàäà÷è (1)–(3).
Äîïóñòèì ïðîòèâíîå, ò.å. ñóùåñòâóåò òàêàÿ òî÷êà ñ öåëî÷èñëåííûìè êîîð-
äèíàòàìè ) � ) )x x xm( , , )1 � , ÷òî
[ ] [ ] [ ] [ ] [a x a x x a x a x am m1 1 1 1 1 1)
)
)
)
) �� �
� �� � � � � 0 ] . (12)
Ó÷èòûâàÿ, ÷òî â (12) âñå ïåðåìåííûå öåëûå, èìååì
[ ] [ ] [ ] [ ]a x a x x a x a xm m1 1 1 1 1 1 1)
)
)
)
) � �� �
� �� � � � � [ ]a0 . (13)
Îòíèìåì èç (13) íåðàâåíñòâî (10) ñ ó÷åòîì, ÷òî a a a�
[ ] { }:
� ) � � ) � ) � � ) � � �� �
{ } { } { } { } {a x a x a x a x am m1 1 1 1 1 1 1� �� � � � 0 } (14)
èëè
{ } { } { } { } { }a x a x a x a x am m1 1 1 1 1 1 01)
)
)
)
�� �
� �� � � � , (15)
îòêóäà ñëåäóåò { }a0 1� , ÷òî ïðîòèâîðå÷èò òîìó, ÷òî { }a0 — äðîáíàÿ ÷àñòü ÷èñëà.
Ïîëó÷èëè ïðîòèâîðå÷èå; ñëåäîâàòåëüíî, ñäåëàííîå ïðåäïîëîæåíèå íåâåðíî,
÷òî äîêàçûâàåò òåîðåìó.
Òåîðåìà 2. Îòñå÷åíèå (9), çàïèñàííîå â âèäå íåðàâåíñòâà
([ ] ) ([ ] ) ([ ] ) ([a d x a d x a d x al l l l1 1 1 11 1�
�
�
�� � � 1 1] )�
�d x�
�
� � �
x a d x a d x a dm m� � �([ ] ) ([ ] ) [ ]1 1 0� , (16)
îòñåêàåò îò äîïóñòèìîé îáëàñòè ñîîòâåòñòâåííîé ÇËÏ òîëüêî òàêèå òî÷êè
ñ öåëî÷èñëåííûìè êîîðäèíàòàìè: x a� � [ ]0 , x a x a d� �� � & � �
[ ] , , [ ]0 01 1
(â ñîîòâåòñòâåííîì áàçèñå).
Äîêàçàòåëüñòâî. Ôàêò îòñå÷åíèÿ óêàçàííûõ òî÷åê ïîäòâåðæäàåòñÿ íå-
ïîñðåäñòâåííîé ïðîâåðêîé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 119
Äîêàæåì îò ïðîòèâíîãî, ÷òî íèêàêàÿ äðóãàÿ òî÷êà íå îòñåêàåòñÿ. Äîïóñòèì,
÷òî ñóùåñòâóåò òàêàÿ íåíóëåâàÿ öåëî÷èñëåííàÿ òî÷êà ) � ) )x x xm( , , )1 � , ÷òî
([ ] ) ([ ] ) ([ ] ) ([a d x a d x a d xl l l l1 1 1 11 1�
)
�
)
� )
� � a d x� �� �� )
1 1] )
)
� )
� ) � �
x a d x a d x a dm m� � �([ ] ) ([ ] ) [ ]1 1 0� . (17)
Ó÷èòûâàÿ, ÷òî â (17) âñå ïåðåìåííûå öåëûå, èìååì
([ ] ) ([ ] ) ([ ] ) ([a d x a d x a d xl l l l1 1 1 11 1�
)
�
)
� )
� � a d x� �� �� )
1 1] )
)
� )
� ) � � �
x a d x a d x a dm m� � �([ ] ) ([ ] ) [ ]1 1 01� . (18)
Îòíèìåì èç (18) íåðàâåíñòâî (10) ñ ó÷åòîì, ÷òî a a a�
[ ] { }:
( ) ( )
,
� �
)
� � ) � � �
� �
�
� �{ } { } {a d x a d x ai i
i
l
i i
i l i s
m
1 1
1 1
0 }� d . (19)
Äàëåå èìååì
( ) ( )
,
{ } { } { }a d x a d x d ai i
i
l
i i
i l i
m
� )
)
� �
� �
�
� �1 1
1 1
0
�
.
(20)
Âîçìîæíû âàðèàíòû:
1) cðåäè ÷èñåë x i li , , , ,�1 2 � , ñóùåñòâóåò õîòÿ áû îäíî íåíóëåâîå (íàïðè-
ìåð, xk ), òîãäà
( ) ( )
,
{ } { }a d x a d x di i
i
l
i i
i l i
m
� )
)
� �
� �
�
� �1 1
1 1 �
�
� )
� �
� )
� �
�
� ( ) ( ){ } { }a d x d a d x di i
i
l
k k1 1 1 1
1
�
�
� � �( ){ } { } { }a d d a ak k1 1 0 ; (21)
2) x x xl1 2 0� � � �� , òîãäà ñðåäè ÷èñåë x i l l mi , , , , , , ,�
�
1 1 1� �� � ,
ñóùåñòâóåò õîòÿ áû îäíî íåíóëåâîå (íàïðèìåð, xh ):
( ) ( )
,
{ } { }a d x a d x di i
i
l
i i
i l i
m
� )
)
� �
� �
�
� �1 1
1 1 �
�
)
� �
)
� �
�
�
� ( ) ( )
,
{ } { }a d x d a d x di i
i l i
m
h h
1
1 1
�
�
� �
�( ){ } { } { }a d d a ah h1 1 0 . (22)
Íåðàâåíñòâî (22) íåñïðàâåäëèâî. Ñëåäîâàòåëüíî, ñäåëàííîå ïðåäïîëîæåíèå
íåâåðíî, ÷òî äîêàçûâàåò òåîðåìó.
ÏÐÈÌÅÐ
Ðåøèòü çàäà÷ó
f x x x x( ) �
�3 21 2 3 max,
x x x
x x x
x x x
1 2 3
1 2 3
1 2 3
3 7
3 3
4 3 3 10
�
�
�
�
�
*
!
*
;
;
;
( )x x x1
2
2
2
3
23 1�
� ;
( , , ) ( )
.
x x x E G E1 2 3 10 6
32� � , G � { }0 1 2 3 4 53 3 2 2, , , , , ;
120 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
( , ) ( )x x E G1 2 1� , G1
2 2 20 1 3 4� { }, , , , E G( )1 — ìíîæåñòâî 2-ðàçìåùåíèé èç
ìóëüòèìíîæåñòâà G1; x E G3 2� ( ), G2 0 1 2 3 5� { }, , , , , E G( )2 — ìíîæåñòâî 1-ðàç-
ìåùåíèé èç ìóëüòèìíîæåñòâà G2 .
Ðåøåíèå. Çàïèøåì âñïîìîãàòåëüíóþ ÇËÏ (ÂÇËÏ) â êàíîíè÷åñêîì âèäå:
f x x x x( ) �
�3 21 2 3 max,
x x x x
x x x x
x x x x
1 2 3 4
1 2 3 5
1 2 3 6
3 7
3 3
4 3 3 10
�
�
�
�
�
,
,
,
*
!
*
x j � 0
�j J6 .
Øàã 0. Ñòðîèì ñèìïëåêñ-òàáëèöó ÂÇËÏ, ïðèñîåäèíÿåì L-ñòðîêó:
x x x xL1 2 3 14
� (òàáë. 1; áàçèñíûå ñòîëáöû äëÿ óäîáñòâà íå çàïèñûâàåì).
 ñèìïëåêñ-òàáëèöó äëÿ ïîñòðîåíèÿ îòñå÷åíèÿ äîáàâëåíû äâà äîïîëíèòåëüíûõ
(ïîñëåäíèõ) ñòîëáöà.
Øàã 1. Åñòü îòðèöàòåëüíûå îöåíêè � j , ïåðåõîäèì ê ñëåäóþùåìó øàãó.
Øàã 2. Íàïðàâëÿþùèé ñòîëáåö — ïåðâûé (P1), ïîñêîëüêó âåêòîð
r1
3
1
1
1
1
1
4
1
1
1
0
1
0
1
�
� ��
�
�
�
�
�, , , , , , ëåêñèêîãðàôè÷åñêè ìåíüøå, ÷åì r2
2
1
�
��
�
�
�
�
�, ... è
r3
1
1
�
��
�
�
�
�
�, ... .
Øàã 3. Âû÷èñëèì %1
0
0
11
7
2 5� �
�
�
min
a
i J
i
ii
a
a
, , V1 1 3( ) � { }. Ïðîèçâîäÿùàÿ ñòðîêà —
òðåòüÿ.
Øàã 4. Ñîãëàñíî (8) ïîëó÷àåì îòñå÷åíèå x x1 7 2
� . Ïîñëå ñèìïëåêñ-ïðåîá-
ðàçîâàíèÿ ñòîëáöà P0 ïîëó÷àåì òî÷êó x * ( , , )� 2 0 0 , êîòîðàÿ íå óäîâëåòâîðÿåò
êîìáèíàòîðíûì è äîïîëíèòåëüíîìó (íåëèíåéíîìó) îãðàíè÷åíèÿì. Ïîëîæèì
d �1, ïåðåõîäèì íà øàã 5.
Øàã 5. Ñîãëàñíî (9) ïîëó÷àåì îòñå÷åíèå x x1 7 1
� .
Øàã 6. Ïîñëå ñèìïëåêñ-ïðåîáðàçîâàíèÿ ñòîëáöà P0 ïîëó÷àåì òî÷êó
x * ( , , )� 1 0 0 , êîòîðàÿ óäîâëåòâîðÿåò êîìáèíàòîðíûì îãðàíè÷åíèÿì x E*� è äî-
ïîëíèòåëüíîìó íåëèíåéíîìó. Ïåðåõîäèì íà øàã 7.
Øàã 7. Ïðîâîäèì ñèìïëåêñ-ïðåîáðàçîâàíèÿ, íàïðàâëÿþùàÿ ñòðîêà — îòñå-
÷åíèå, íàïðàâëÿþùèé ñòîëáåö — ïåðâûé (P1) (òàáë. 2).
Øàã 8. Óäàëÿåì ñòðîêó-îòñå÷åíèå èç òàáë. 3, ïåðåõîäèì íà øàã 1.
 ïåðâîì øàãå èìåþòñÿ îòðèöàòåëüíûå îöåíêè. Àíàëîãè÷íî ïîëó÷àåì âòî-
ðîå îòñå÷åíèå �
�2 17 2 8x x x .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 121
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ xi
P0 P1 P2 P3
a
a
i
i
0
�
a
a
i
i
0
�
�
�
�
�
�
�
1 x4 0 7 1 3 1 7 5
2 x5 0 3 1 –1 3 3 3
3 x6 0 10 4 3 3 2,5 2
4 x1 3 0 –1 0 0 – –
5 x2 2 0 0 –1 0 – –
6 x3 1 0 0 0 –1 – –
7 xL 0 14 1 1 1
Îöåíêà, � 0 –3 –2 –1
Ò à á ë è ö à 1
 òàáë. 4–7 ïîëó÷åíî åùå ÷åòûðå îòñå÷åíèÿ äëÿ ðàçëè÷íûõ ýòàïîâ.
 òàáë. 8 âñå îöåíêè � j íå ìåíüøå íóëÿ. Îïòèìàëüíîå ðåøåíèå èñõîäíîé
çàäà÷è íàéäåíî: f x( )* � 6, x E* ( , , )� �1 1 1 .
Îòìåòèì, ÷òî íà ðàçíûõ ýòàïàõ ïîëó÷åíû òàêèå äîïóñòèìûå ðåøåíèÿ çàäà÷è
(1)–(3): ( , , )0 0 0 , ( , , )1 0 0 , ( , , )1 1 0 , ( , , )1 1 1 .
122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ,
xi
P0 P1 P2 P3
1 x4 0 7 1 3 1
2 x5 0 3 1 –1 3
3 x6 0 10 4 3 3
4 x1 3 0 –1 0 0
5 x2 2 0 0 –1 0
6 x3 1 0 0 0 –1
7 xL 0 14 1 1 1
8 x7 1 1 0 0
Îöåíêà, � 0 –3 –2 –1
Ò à á ë è ö à 2
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ,
xi
P0 P7 P2 P3
a
a
i
i
0
�
a
a
i
i
0
�
�
�
�
�
�
�
1 x4 0 6 –1 3 1 2 2
2 x5 0 2 –1 –1 3 – –
3 x6 0 6 –4 3 3 2 2
4 x1 3 1 1 0 0 – –
5 x2 2 0 0 –1 0 – –
6 x3 1 0 0 0 –1 – –
7 xL 0 13 –1 1 1
8 x8 1 –2 1 0
Îöåíêà, � 3 3 –2 –1
Ò à á ë è ö à 3
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ, xi
P0 P7 P8 P3
a
a
i
i
0
�
a
a
i
i
0
�
�
�
�
�
�
�
1 x4 0 3 5 –3 1 3 3
2 x5 0 3 –3 1 3 1 1
3 x6 0 3 2 –3 3 1 1
4 x1 3 1 1 0 0 – –
5 x2 2 1 –2 1 0 – –
6 x3 1 0 0 0 –1 – –
7 xL 0 12 1 –1 1
8 x9 1 0 –1 1
Îöåíêà, � 5 –1 2 –1
Ò à á ë è ö à 4
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 123
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ, xi
P0 P7 P8 P9
a
a
i
i
0
�
a
a
i
i
0
�
�
�
�
�
�
�
1 x4 0 2 5 –2 –1 0,4 0
2 x5 0 0 –3 4 –3 – –
3 x6 0 0 2 0 –3 0 0
4 x1 3 1 1 0 0 1 1
5 x2 2 1 –2 1 0 – –
6 x3 1 1 0 –1 1 – –
7 xL 0 11 1 0 –1
8 x10 0 1 0 –2
Îöåíêà, � 6 –1 1 1
Ò à á ë è ö à 5
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ, xi
P0 P10 P8 P9
a
a
i
i
0
�
a
a
i
i
0
�
�
�
�
�
�
�
1 x4 0 2 –5 –2 9 0,22222 0
2 x5 0 0 3 4 –9
3 x6 0 0 –2 0 1 0 0
4 x1 3 1 –1 0 2 0,5 0
5 x2 2 1 2 1 –4 – –
6 x3 1 1 0 –1 1 1 1
7 xL 0 11 –1 0 1
8 x11 0 –2 0 1
Îöåíêà, � 6 1 1 –1
Ò à á ë è ö à 6
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ, xi
P0 P10 P8 P11
a
a
i
i
0
�
a
a
i
i
0
�
�
�
�
�
�
�
1 x4 0 2 13 –2 –9 0,15385 0
2 x5 0 0 –15 4 9 – –
3 x6 0 0 0 0 –1 – –
4 x1 3 1 3 0 –2 0,33333 0
5 x2 2 1 –6 1 4 – –
6 x3 1 1 2 –1 –1 0,5 0
7 xL 0 11 1 0 –1
8 x12 0 1 –1 –1
Îöåíêà, � 6 –1 1 1
Ò à á ë è ö à 7
Íîìåð
ñòðîêè
Ïåðåìåííûå
Çíà÷åíèÿ
ïåðåìåííûõ, xi
P0 P12 P8 P11
1 x4 0 2 –13 11 4
2 x5 0 0 15 –11 –6
3 x6 0 0 0 0 –1
4 x1 3 1 –3 3 1
5 x2 2 1 6 –5 –2
6 x3 1 1 –2 1 1
7 xL 0 11 –1 1 0
Îöåíêà, � 6 1 0 0
Ò à á ë è ö à 8
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåí è îáîñíîâàí ïðÿìîé ìåòîä îòñå÷åíèé äëÿ ðåøåíèÿ óñëîâíûõ êîì-
áèíàòîðíûõ çàäà÷ íà ïîëèðàçìåùåíèÿõ ïðè óñëîâèè ÄÊÍÖ. Çàìåòèì, ÷òî îá-
ëàñòü, êîòîðóþ îáðàçóþò âñå îãðàíè÷åíèÿ èñõîäíîé çàäà÷è (êðîìå êîìáèíà-
òîðíûõ), íå îáÿçàòåëüíî äîëæíà áûòü âûïóêëîé.
Ñðåäè äîñòîèíñòâ ìåòîäà îòìåòèì òî, ÷òî íà êàæäîì ýòàïå èìååòñÿ äîïóñòè-
ìîå ðåøåíèå èñõîäíîé çàäà÷è (1)–(3).
Íàïðàâëåíèåì äàëüíåéøèõ èññëåäîâàíèé ìîæåò áûòü ïîëó÷åíèå òåîðåòè-
÷åñêîé îöåíêè ñëîæíîñòè àëãîðèòìà. Öåëåñîîáðàçíî ðàññìîòðåòü âîçìîæíîñòü
ðàñïðîñòðàíåíèÿ äàííîãî ìåòîäà íà äðóãèå òèïû êîìáèíàòîðíûõ îïòèìèçàöèîí-
íûõ çàäà÷.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ
êîìáèíàòîðíûõ çàäà÷ îïòèìèçàöèè. — Ê.: Íàóê. äóìêà, 1981. — 288 ñ.
2. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. —
Ê.: ²ÑÄÎ, 1993. — 188 ñ. (http://informatics.org.ua/uploads/books/stoyan sub emets sub eko.pdf)
3. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Îïòèì³çàö³ÿ íà ïîë³ðîçì³ùåííÿõ: òåîð³ÿ òà
ìåòîäè. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ.
4. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Ìíîæèíè ïîë³ðîçì³ùåíü â êîìá³íàòîðí³é
îïòèì³çàö³¿ // Äîï. ÍÀÍ Óêðà¿íè. — 1999. — ¹ 8. — Ñ. 37–41.
5. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ:
Ìîíîãðàôèÿ. — Ê.: Íàóê. äóìêà, 2008. — 159 ñ.
6. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê ³ í à Ë . Ì . Çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³¿ ç äðîáîâî-ë³í³éíèìè
ö³ëüîâèìè ôóíêö³ÿìè. — Ê.: Íàóê. äóìêà, 2005. — 117 ñ.
7. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à Î .  . Çàäà÷³ îïòèì³çàö³¿ íà ïîë³êîìá³íàòîðíèõ ìíîæèíàõ:
âëàñòèâîñò³ òà ðîçâ’ÿçóâàííÿ. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2006. — 129 ñ.
8. ª ì å ö ü Î . Î . , Á à ð á î ë ³ í à Ò . Ì . Ðîçâ’ÿçóâàííÿ çàäà÷ íåë³í³éíî¿ óìîâíî¿ îïòèì³çàö³¿ íà
ðîçì³ùåííÿõ ìåòîäîì â³äñ³êàííÿ // Óêð. ìàò. æóðí. — 2003. — 55, ¹ 5. — Ñ. 604–611.
9. Ä î í å ö à . À . , Ê î ë å ÷ ê è í à Ë . Í . Ìåòîä óïîðÿäî÷åíèÿ çíà÷åíèé ëèíåéíîé ôóíêöèè íà
ìíîæåñòâå ïåðåñòàíîâîê // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 2. — Ñ. 50–61.
10. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à À . À . Ïðî îö³íêè ì³í³ìóì³â ö³ëüîâèõ ôóíêö³é ïðè
îïòèì³çàö³¿ íà ñïîëó÷åííÿõ // Óêð. ìàò. æóðí. — 1999. — 51, ¹ 8. — Ñ. 1118–1121.
11. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Ì . Ðåøåíèå ëèíåéíûõ çàäà÷ îïòèìèçàöèè íà ðàçìåùåíèÿõ
ìåòîäîì îòñå÷åíèÿ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2003. — ¹ 6. — Ñ. 131–141.
12. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Ì . Ðåøåíèå çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòèìè-
çàöèè ìåòîäîì ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêîé ýêâèâàëåíòíîñòè // Òàì æå. — 2004. — ¹ 5.
— Ñ. 115–125.
13. Õ ó Ò . Öåëî÷èñëåííîå ïðîãðàììèðîâàíèå è ïîòîêè â ñåòÿõ. — Ì.: Ìèð, 1974. — 519 ñ.
14. À ê ó ë è ÷ È . Ë . Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå â ïðèìåðàõ è çàäà÷àõ: Ó÷åá. ïîñîáèå
äëÿ ñòóäåíòîâ ýêîíîì. ñïåö. âóçîâ. — Ì.: Âûñø. øê., 1986. — 319 ñ.
Ïîñòóïèëà 27.12.2010
124 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
|
| id | nasplib_isofts_kiev_ua-123456789-84256 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:57:53Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Емец, Е.М. Олексийчук, Ю.Ф. 2015-07-04T14:51:55Z 2015-07-04T14:51:55Z 2011 Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями / О.А. Емец, Е.М. Емец, Ю.Ф. Олексийчук // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 116-124. — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84256 519.85 Запропоновано та обґрунтовано прямий метод відсікання для розв’язування комбінаторних задач оптимізації на полірозміщеннях з додатковими обмеженнями. Метод не дозволяє будувати лінійну оболонку множини полірозміщень і отримувати на кожному етапі допустимий розв’язок. A direct pruning method to solve combinatorial optimization problems on polyarrangements with additional constraints is proposed and substantiated in the paper. The method allows obtaining a feasible solution at each stage without constructing the linear hull of the set of polyarrangements. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями Прямий метод відсікання для задач комбінаторної оптимізації з додатковими обмеженнями Direct pruning method for combinatorial optimization problems with additional constraints Article published earlier |
| spellingShingle | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями Емец, О.А. Емец, Е.М. Олексийчук, Ю.Ф. Системный анализ |
| title | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями |
| title_alt | Прямий метод відсікання для задач комбінаторної оптимізації з додатковими обмеженнями Direct pruning method for combinatorial optimization problems with additional constraints |
| title_full | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями |
| title_fullStr | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями |
| title_full_unstemmed | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями |
| title_short | Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями |
| title_sort | прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84256 |
| work_keys_str_mv | AT emecoa prâmoimetodotsečeniidlâzadačkombinatornoioptimizaciisdopolnitelʹnymiograničeniâmi AT emecem prâmoimetodotsečeniidlâzadačkombinatornoioptimizaciisdopolnitelʹnymiograničeniâmi AT oleksiičukûf prâmoimetodotsečeniidlâzadačkombinatornoioptimizaciisdopolnitelʹnymiograničeniâmi AT emecoa prâmiimetodvídsíkannâdlâzadačkombínatornoíoptimízacíízdodatkovimiobmežennâmi AT emecem prâmiimetodvídsíkannâdlâzadačkombínatornoíoptimízacíízdodatkovimiobmežennâmi AT oleksiičukûf prâmiimetodvídsíkannâdlâzadačkombínatornoíoptimízacíízdodatkovimiobmežennâmi AT emecoa directpruningmethodforcombinatorialoptimizationproblemswithadditionalconstraints AT emecem directpruningmethodforcombinatorialoptimizationproblemswithadditionalconstraints AT oleksiičukûf directpruningmethodforcombinatorialoptimizationproblemswithadditionalconstraints |