Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ
Розглянуто точний комбінаторний метод розв’язування задачі оптимізації на розміщеннях з дробово-лінійною функцією цілі та додатковими лінійними обмеженнями. Побудований алгоритм гілок та меж для розв’язування такої задачі ґрунтується на ідеях А. Ленд та A. Дойг. Наведено приклад розв’язування оптимі...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84157 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ / И.В. Сергиенко, О.А. Емец, О.А. Черненко // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 30-35. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859909576943468544 |
|---|---|
| author | Сергиенко, И.В. Емец, О.А. Черненко, О.А. |
| author_facet | Сергиенко, И.В. Емец, О.А. Черненко, О.А. |
| citation_txt | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ / И.В. Сергиенко, О.А. Емец, О.А. Черненко // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 30-35. — Бібліогр.: 18 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто точний комбінаторний метод розв’язування задачі оптимізації на розміщеннях з дробово-лінійною функцією цілі та додатковими лінійними обмеженнями. Побудований алгоритм гілок та меж для розв’язування такої задачі ґрунтується на ідеях А. Ленд та A. Дойг. Наведено приклад розв’язування оптимізаційної задачі з дробово-лінійною цільовою функцією на розміщеннях запропонованим алгоритмом.
The exact combinatorial method of solving the problem of optimization on arrangements with a linear-fractional objective function and additional linear constraints is considerd. The branch and bound algorithm constructed is based on the ideas of Land and Doig. An illustrative example of solving the optimization problem with a linear-fractional objective function on arrangements with the algorithm is presented.
|
| first_indexed | 2025-12-07T16:01:45Z |
| format | Article |
| fulltext |
È.Â. ÑÅÐÃÈÅÍÊÎ, Î.À. ÅÌÅÖ, Î.À. ×ÅÐÍÅÍÊÎ
ÓÄÊ 519.85 ÐÅØÅÍÈÅ ÓÑËÎÂÍÎÉ ÇÀÄÀ×È ÎÏÒÈÌÈÇÀÖÈÈ
ÄÐÎÁÍÎ-ËÈÍÅÉÍÎÉ ÖÅËÅÂÎÉ ÔÓÍÊÖÈÈ
ÍÀ ÌÍÎÆÅÑÒÂÅ ÐÀÇÌÅÙÅÍÈÉ
ÌÅÒÎÄÎÌ ÂÅÒÂÅÉ È ÃÐÀÍÈÖ
Êëþ÷åâûå ñëîâà: ìåòîä âåòâåé è ãðàíèö, îïòèìèçàöèÿ, äðîáíî-ëèíåéíàÿ
ôóíêöèÿ öåëè, ðàçìåùåíèå.
Èññëåäîâàíèþ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè è ìåòîäîâ èõ ðåøåíèÿ ïî-
ñâÿùåíî ìíîãî ðàáîò (íàïðèìåð, [1–15]), ïîñêîëüêó áîëüøèíñòâî ïðàêòè÷åñ-
êèõ çàäà÷ îïèñûâàþòñÿ ñ ïîìîùüþ êîìáèíàòîðíûõ îïòèìèçàöèîííûõ ìîäå-
ëåé. Àêòóàëüíûìè îñòàþòñÿ ðàçðàáîòêà ìåòîäîâ è àëãîðèòìîâ ðåøåíèÿ çàäà÷
íà îòäåëüíûõ êîìáèíàòîðíûõ ìíîæåñòâàõ, â ÷àñòíîñòè, íà ìíîæåñòâå ðàçìå-
ùåíèé, è ïðîáëåìà ïîèñêà áîëåå ýôôåêòèâíûõ àëãîðèòìîâ.
 ðàáîòàõ [2, 3, 5, 6–8, 10–15] îïèñàíû ìåòîäû è àëãîðèòìû ðåøåíèÿ ëèíåé-
íûõ óñëîâíûõ çàäà÷ íà ïåðåñòàíîâêàõ, ïîëèïåðåñòàíîâêàõ, ðàçìåùåíèÿõ è ïîëè-
ðàçìåùåíèÿõ. Ðàçðàáîòàíû ìåòîäû ðåøåíèÿ äðîáíî-ëèíåéíûõ óñëîâíûõ çàäà÷
íà ìíîæåñòâàõ ïåðåñòàíîâîê [4, 15] è ðàçìåùåíèé [7].
Ïðåäëîæåííûé â [9] ìåòîä ðåøåíèÿ óñëîâíûõ çàäà÷ ñ äðîáíî-ëèíåéíîé öå-
ëåâîé ôóíêöèåé íà ðàçìåùåíèÿõ îñíîâàí íà ðàçáèåíèè ïðîñòðàíñòâà íà êëàññû
ýêâèâàëåíòíîñòè è ïîñëåäóþùåì íàïðàâëåííîì ïðîñìîòðå ýòèõ êëàññîâ. Ýòî
îäèí èç íåìíîãèõ òî÷íûõ ìåòîäîâ äëÿ äàííîãî êëàññà çàäà÷, êîòîðûé ó÷èòûâàåò
ñâîéñòâà ìíîæåñòâà ðàçìåùåíèé. Ïðèìåíåíèå èäåé ìåòîäîâ äèñêðåòíîé îïòèìè-
çàöèè [16–18] ê çàäà÷àì íà êîìáèíàòîðíûõ ìíîæåñòâàõ öåëåñîîáðàçíî âñëåä-
ñòâèå îïðåäåëåííîé ñõîæåñòè îòäåëüíûõ ñâîéñòâ äîïóñòèìûõ ìíîæåñòâ äèñ-
êðåòíîé è êîìáèíàòîðíîé îïòèìèçàöèé. Ïîýòîìó, ó÷èòûâàÿ ñïåöèôèêó êîìáèíà-
òîðíûõ îãðàíè÷åíèé, ïðèìåíèì íåêîòîðûå ìåòîäû ðåøåíèÿ äèñêðåòíûõ çàäà÷
äëÿ çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè.
Öåëü äàííîé ñòàòüè — ðàñïðîñòðàíèòü ìåòîä âåòâåé è ãðàíèö äëÿ ðåøåíèÿ
çàäà÷ îïòèìèçàöèè íà ðàçìåùåíèÿõ ñ äðîáíî-ëèíåéíîé öåëåâîé ôóíêöèåé è äî-
ïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè, à òàêæå îáîñíîâàòü àëãîðèòì ýòîãî
ìåòîäà.
Èçëîæèì ïîëó÷åííûå ðåçóëüòàòû. Ìíîæåñòâî k ïåðâûõ íàòóðàëüíûõ ÷èñåë
îáîçíà÷èì J
k
, ò.å. J k
k
� { }1 2, , ..., , à J J
k
k
0
0� �{ }. Ïóñòü äàíî ìóëüòèìíîæåñòâî
G g g g� � �{ }
1 2
, � � ñ îñíîâîé S G e e e
n
( ) ( , , ..., )�
1 2
, ãäå e R
i
�
1
� �i J
n
, è êðàò-
íîñòÿìè ýëåìåíòîâ k e
G i i
( ) � � , i J
n
� . Î÷åâèäíî, ÷òî � �
i
i
n
�
�
�
1
[2].
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
© È.Â. Ñåðãèåíêî, Î.À. Åìåö, Î.À. ×åðíåíêî, 2012
Âûáåðåì ïðîèçâîëüíîå k J� � . Ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ k-âûáîðîê
èç ìóëüòèìíîæåñòâà G âèäà ( , )g g g
i i i
k1 2
� �� , ãäå g G
i
j
� , i i
j t
� � �i i J
j t
, �
� �j t J
k
, , îáðàçóåò îáùåå ìíîæåñòâî ðàçìåùåíèé E G
n
k
� ( ) . Ïóñòü ýëåìåíòû
ìóëüòèìíîæåñòâà G óïîðÿäî÷åíû ïî íåóáûâàíèþ, à ýëåìåíòû ( , )e e e
n1 2
� �� åãî
îñíîâû — ïî âîçðàñòàíèþ.
Âûïóêëîé îáîëî÷êîé ìíîæåñòâà E G
n
k
� ( ) ÿâëÿåòñÿ îáùèé ìíîãîãðàííèê ðàç-
ìåùåíèé �n
k
G( ) , êîòîðûé îïèñàí â [2] ñèñòåìîé íåðàâåíñòâ
g x g J
j
j
i j
j
k
i�
�
��
� ��
� � �
1
1
1
| | | |�
�
�
�
� , (1)
ãäå g G
j
� , | |� — êîëè÷åñòâî ýëåìåíòîâ âo ìíîæåñòâå � .
Ïóñòü k n m p, , , ,� — íàòóðàëüíûå êîíñòàíòû, c d R
j j
, � � �j J
m
0
, a b R
ij i
, �
� �j J
m
, � �i J
p
, à òàêæå t t t t t t R
k k m
m
� �
�
( , , ..., , , ..., )
1 2 1
, ãäå x t
j j
� � �j J
k
,
ò.å. ïåðåìåííûå t t
k m�
� �
1
� ÿâëÿþòñÿ íåïðåðûâíûìè, à x x
k1
, ..., — êîìáèíà-
òîðíûìè.
Ðàññìîòðèì çàäà÷ó ñëåäóþùåãî âèäà: íàéòè óïîðÿäî÷åííóþ ïàðó � �f t t( )
* *
,
òàêóþ, ÷òî
f t f t
c t c
d t d
t R t R
j
m
j j
j
m
j j
m m
( ) max ( ) max
*
� �
�
�
� �
�
�
�
�
1
0
1
0
, t f t
t R
m
*
max ( )�
�
arg , (2)
ïðè êîìáèíàòîðíîì óñëîâèè
x x x E G R
k n
k m
� � � �
( ) ( )
1
� � , k m� , (3)
è äîïîëíèòåëüíûõ ëèíåéíûõ îãðàíè÷åíèÿõ
a t b
ij j
j
m
i
�
�
�
1
, I J
p
� . (4)
Çàäà÷ó (2)–(4) ðåøèì ïóòåì ïåðåõîäà ê ðåëàêñèðîâàííîé çàäà÷å: óñëîâèå (3)
îñëàáèì, çàìåíèâ åãî (1). Ïðèìåíÿÿ ê çàäà÷å (1), (2), (4) îòîáðàæåíèå � , êîòîðîå
ïðåäñòàâèì ñîîòíîøåíèÿìè
y
d t d
j
m
j j
0
1
0
1
�
�
�
�
, z t y
j j
�
0
� � �j J t R
m
m
, , (5)
ãäå çíàìåíàòåëü áîëüøå íóëÿ, ïåðåéäåì ê çàäà÷å ñ ëèíåéíîé ôóíêöèåé öåëè è
äîïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè
F z F z c z c y
z R z R
j
m
j j
m m
( ) max ( ) max ( )
*
� � �
� �
�
� �
�
1 1
1
0 0
, z F z
z R
m
*
max ( )�
�
�
arg
1
, (6)
ïðè óñëîâèÿõ
j
m
ij j i
a z b y
�
�
�
1
0
0 , i J
p
� , (7)
g y y g y J
j
j
i
i
j
j
k0
1
1 0
1� �
�
�
� � �
� � �
| | | |�
�
�
�
� , (8)
d z d y
j j
j
m
�
�
� �
1
0 0
1, y
0
0� , z j J
j m
� � �0 , (9)
ãäå z y z z z z R
k k m
m
� �
�
�
( , , ..., , , ..., )
0 1 1
1
, y z j J
j j k
� � � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 31
Êîìáèíàòîðíîå óñëîâèå (3) ïîñëå ïðèìåíåíèÿ îòîáðàæåíèÿ (5) çàïèøåòñÿ â âèäå
y y y y E R
k
m
� �
�
( , , ..., )
0 1
1
.
(10)
Ìíîæåñòâî, çàäàííîå ñèñòåìîé (8), îáîçíà÷èì Q G
n
k
� ( ). Çàäà÷è (1), (2), (4) è (6)–(9)
ýêâèâàëåíòíû, ò.å. åñëè z y z z
m
*
( , , ..., )�
0 1
, ãäå y z
j j
� � �j J
k
, — îïòèìàëü-
íîå ðåøåíèå çàäà÷è (6)–(9), òî t t t t
m
*
( , )� � �
1 2
� , ãäå t z y
j j
�
( )
0
1
, t x
j j
�
� �j J
k
, — îïòèìàëüíîå ðåøåíèå (1), (2), (4). Àíàëîãè÷íîå óòâåðæäåíèå èìååò
ìåñòî è äëÿ çàäà÷ (2)–(4) è (6), (7), (9), (10).
Ñðåäè êîìáèíàòîðíûõ ìåòîäîâ âàæíîå çíà÷åíèå êàê â ïðàêòè÷åñêîì, òàê
è òåîðåòè÷åñêîì ïëàíå èìååò ìåòîä âåòâåé è ãðàíèö.  íàñòîÿùåå âðåìÿ ñóùåñò-
âóåò ìíîãî îáùèõ ñõåì ìåòîäîâ âåòâåé è ãðàíèö, êîòîðûå îòëè÷àþòñÿ ãëàâíûì
îáðàçîì ñïîñîáàìè âåòâëåíèÿ, îòñå÷åíèÿ è îöåíèâàíèÿ. Èìåííî ýòè õàðàêòåðèñ-
òèêè îïðåäåëÿþò ýôôåêòèâíîñòü ìåòîäà ïðè ðåøåíèè êîíêðåòíîé çàäà÷è.
Äàëåå ïðèâåäåí àëãîðèòì ìåòîäà âåòâåé è ãðàíèö äëÿ ðåøåíèÿ çàäà÷è
(2)–(4), îñíîâàííûé íà èäåÿõ Ëýíä è Äîéã [18]. Îáîçíà÷èì � íîìåð èòåðàöèè
(îäèí ïîëíûé öèêë àëãîðèòìà).
Øàã 1. Ïåðåéòè ê ðåëàêñèðîâàííîé çàäà÷å: óñëîâèå (3) îñëàáëÿåòñÿ è çàìå-
íÿåòñÿ íà (1). Ïðèìåíèòü ïðåîáðàçîâàíèå (5) ê çàäà÷å (1), (2), (4).
Øàã 2. Ðåøèòü ëèíåéíóþ çàäà÷ó (6)–(9).
Øàã 3. Åñëè (6)–(9) íå èìååò ðåøåíèÿ, òî íå èìååò ðåøåíèÿ (2)–(4), èíà÷å
ïóñòü t z y�
( )
0
1
— ýêñòðåìàëü çàäà÷è (1), (2), (4).
Øàã 4. Åñëè x E G
n
k
� � ( ) , ãäå x t j J
j j k
� � � , òî F x x( ),
* *
— ðåøåíèå çà-
äà÷è (2)–(4), èíà÷å ïåðåéòè ê øàãó 5.
Øàã 5. Îïðåäåëèòü èíäåêñ � êîìïîíåíòà t � òî÷êè t òàêîãî, ÷òî t G� � , èëè
k t k t
t G
( ) ( )� �� .
Øàã 6. Çàïèñàòü äâà îãðàíè÷åíèÿ, êîòîðûå â îáëàñòè (3), (4) îòñåêàþò t :
t e
i� �
1
,
(11)
t e
i� �
2
, (12)
ãäå
e e e S G e t t t t e E G
i i i i i n
1
1 2 1
� � � � � �
max { | ( ), , ( , , ) ( )� � �
�
� },
e e e S G e t t t t e E
i i i i i n
2
1 2 1
� � � �
min | ( ), , ( , , ..., , ) ({ � � �
�
G)} .
Øàã 7. Ïðèìåíèòü ê (11), (12) ïðåîáðàçîâàíèå (5):
z e y
i� �
1
0
,
(13)
z e y
i� �
2
0
. (14)
Øàã 8. Ïðèñîåäèíèòü ê ðåøåííîé íà ïðåäûäóùåé èòåðàöèè çàäà÷å âèäà
(6)–(9) îãðàíè÷åíèå (13) è ðåøèòü çàäà÷ó (6)–(9), (13). Åñëè îíà íå èìååò ðåøåíèÿ,
òî ïåðåéòè ê øàãó 9, èíà÷å åå ðåøåíèåì áóäåò � �F z z( ),
1 1
.
Øàã 9. Ïðèñîåäèíèòü ê ðåøåííîé íà ïðåäûäóùåé èòåðàöèè çàäà÷å âèäà
(6)–(9) îãðàíè÷åíèå (14) è ðåøèòü çàäà÷ó (6)–(9), (14). Åñëè îíà íå èìååò ðåøå-
íèÿ, òî ïåðåéòè ê øàãó 10, èíà÷å åå ðåøåíèåì áóäåò � �F z z( ),
2 2
.
Øàã 10. Åñëè íè îäíà èç çàäà÷ âèäà (6)–(9), (13) è (6)–(9), (14) íå èìååò ðå-
øåíèÿ, òî çàäà÷à (2)–(4) òàêæå íå èìååò ðåøåíèÿ â ñëó÷àå � �1. Äëÿ � �1 âûáðàòü
äëÿ äàëüíåéøåãî âåòâëåíèÿ äðóãóþ îáëàñòü ñ òî÷êîé, íàéäåííîé íà øàãå 12
( )�
1 -é èòåðàöèè, è ïåðåéòè ê øàãó 4.
Øàã 11. Åñëè îäíà èç çàäà÷ âèäà (6)–(9), (13) èëè (6)–(9), (14) íå èìååò ðå-
øåíèÿ, òî ïåðåéòè ê øàãó 4, ñ÷èòàÿ x z y
i
�
( )
0
1
, ãäå i — íîìåð òî÷êè z
i
, êîòîðàÿ
ïðåäîñòàâëÿåò öåëåâîé ôóíêöèè çíà÷åíèå, íàèáîëüøåå â îáëàñòè D
i
.
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
Øàã 12. Åñëè îáå çàäà÷è âèäà (6)–(9), (13) è (6)–(9), (14) èìåþò ðåøåíèÿ, òî
ïðè � �1 äëÿ äàëüíåéøåãî âåòâëåíèÿ âûáðàòü òó îáëàñòü, êîòîðàÿ ïðåäîñòàâëÿåò
öåëåâîé ôóíêöèè áîëüøåå çíà÷åíèå, è ïåðåéòè ê øàãó 4, ñ÷èòàÿ x z y
i
�
( )
0
1
, ãäå
i — íîìåð òî÷êè z
i
, ïðåäîñòàâëÿþùåé öåëåâîé ôóíêöèè áîëüøåå èç äâóõ çíà÷å-
íèé F z j
j
( ), ,�1 2 .  ñëó÷àå, åñëè çíà÷åíèÿ öåëåâûõ ôóíêöèé ñîâïàäàþò, ïåðåé-
òè ê øàãó 4 è ïðîàíàëèçèðîâàòü ðåøåíèå êàæäîé çàäà÷è. Äëÿ � � 1 ñðàâíèòü çíà-
÷åíèÿ öåëåâûõ ôóíêöèé äëÿ âñåõ íåâåòâëåííûõ îáëàñòåé è äëÿ äàëüíåéøåãî âåò-
âëåíèÿ âûáðàòü òó îáëàñòü, êîòîðàÿ ïðåäîñòàâëÿåò öåëåâîé ôóíêöèè áîëüøåå
çíà÷åíèå, äàëåå ïåðåéòè ê øàãó 4.
Àëãîðèòì îñíîâàí íà ñëåäóþùèõ ïðåäïîëîæåíèÿõ. Îáîçíà÷èì D äîïóñòè-
ìóþ îáëàñòü èñõîäíîé çàäà÷è, ò.å. ìíîæåñòâî òî÷åê, óäîâëåòâîðÿþùèõ óñëîâèÿì
(2)–(4). Ñîãëàñíî ìåòîäó âåòâåé è ãðàíèö ìíîæåñòâî D ðàçîáüåì íà ÷àñòè, êîòî-
ðûå íå èìåþò îáùèõ òî÷åê, ò.å. D D D D� � �
1 2
*
, D D
1 2
� � � , ãäå D
1
— ìíî-
æåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è (2)–(4) ïðè äîáàâëåíèè îãðàíè÷åíèÿ (11);
D
2
— ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è (2)–(4) ïðè äîáàâëåíèè îãðàíè÷å-
íèÿ (12). Î÷åâèäíî, ÷òî ìíîæåñòâî äîïóñòèìûõ ðåøåíèé D
*
çàäà÷è (2)–(4) ïðè
äîáàâëåíèè îãðàíè÷åíèÿ e t e
i i
2 1
� �� ïóñòîå äëÿ çàäà÷è (2)–(4), ïîýòîìó èç äàëü-
íåéøåãî âåòâëåíèÿ åãî ìîæíî èñêëþ÷èòü.
Ïðèìåíèâ ê ñèñòåìå íåðàâåíñòâ, êîòîðûå îïèñûâàþò ìíîæåñòâà D
1
,
D D
*
,
2
, ïðåîáðàçîâàíèå (5), ïîëó÷èì Q Q Q
1 2
, ,
*
.
Óòâåðæäåíèå 1. Îãðàíè÷åíèÿ (13), (14) íå îòñåêàþò íè îäíîé òî÷êè
z y z z
m
� ( , , ..., )
0 1
òàêîé, ÷òî y E� , ãäå y z j J
j j k
� � � .
Äîêàçàòåëüñòâî. Ïóñòü ñóùåñòâóåò z Q
* *
� òàêàÿ, ÷òî z
*
— ðåøåíèå çàäà-
÷è (6), (7), (9), (10). Ïðèìåíÿÿ ê z
*
ïðåîáðàçîâàíèå, îáðàòíîå (5), ïîëó÷èì òî÷êó
t
*
, t z y
* *
( )�
0
1
. Ó÷èòûâàÿ, ÷òî çàäà÷è (6), (7), (9), (10) è (2)–(4) ýêâèâàëåíòíû,
ïîëó÷àåì t
*
— ðåøåíèå çàäà÷è (2)–(4). Èç ðåçóëüòàòîâ ðàáîòû [7] ñëåäóåò, ÷òî
îòîáðàæåíèå � çàäàåò âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ìíîæåñòâîì òî-
÷åê D , êîòîðûå óäîâëåòâîðÿþò (2)–(4), è ìíîæåñòâîì òî÷åê Q , êîòîðûå óäîâëåò-
âîðÿþò (6), (7), (9), (10), à ñëåäîâàòåëüíî, t D
* *
� . Îäíàêî ïî ïîñòðîåíèþ ìíîæå-
ñòâî D
*
ïóñòîå äëÿ çàäà÷è (2)–(4). Èìååì ïðîòèâîðå÷èå. Òàêèì îáðàçîì, ìíîæå-
ñòâî Q
*
íå ñîäåðæèò ðåøåíèé çàäà÷è (6), (7), (9), (10).
Óòâåðæäåíèå äîêàçàíî.
Ñ ó÷åòîì òîãî, ÷òî çàäà÷è (1), (2), (4) è (6)–(9) ýêâèâàëåíòíû, ñïðàâåäëèâî
ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 2. Îöåíêàìè äîïóñòèìûõ îáëàñòåé D
i
çàäà÷ (2)–(4), (11) èëè
(2)–(4), (12) ÿâëÿþòñÿ çíà÷åíèÿ öåëåâûõ ôóíêöèé ñîîòâåòñòâóþùèõ çàäà÷ (1), (2),
(4), (11) èëè (1), (2), (4), (12).
Êàæäîìó èç ìíîæåñòâ îáëàñòåé D
i
äîïóñòèìûõ ðåøåíèé ñîîòâåòñòâóþùåé
çàäà÷è âèäà: íàéòè (2) ïðè îãðàíè÷åíèÿõ (1), (4) è ïðè äîïîëíèòåëüíûõ îãðàíè÷å-
íèÿõ (11) èëè (12), ïðèïèñûâàþò îöåíêó �( ) max ( )D f x
i
x D
i
�
�
. Åñëè îïòèìàëüíûå ðå-
øåíèÿ ïîëó÷åííûõ çàäà÷ óäîâëåòâîðÿþò êîìáèíàòîðíîìó óñëîâèþ (3), òî ðåøå-
íèå ñ ìàêñèìàëüíîé îöåíêîé áóäåò îïòèìàëüíûì äëÿ èñõîäíîé çàäà÷è. Èíà÷å ïðî-
äîëæàåì ïðîöåññ âåòâëåíèÿ, âûáèðàÿ ìíîæåñòâî D
i
ñ íàèáîëüøåé îöåíêîé. Äëÿ
èòåðàöèé � �1 â ñëó÷àå, åñëè âûáðàííàÿ îáëàñòü D
i
íå ñîäåðæèò òî÷åê, êîòîðûå
ÿâëÿþòñÿ ðàçìåùåíèÿìè, èñïîëüçóåì äëÿ äàëüíåéøåãî âåòâëåíèÿ âòîðóþ îáëàñòü,
íàéäåííóþ íà ïðåäûäóùåé èòåðàöèè (øàã 10 ïðèâåäåííîãî âûøå àëãîðèòìà).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 33
Ðàçáèâàÿ â ïðîöåññå ðåøåíèÿ ìíîæåñòâî D íà ïîäìíîæåñòâà D
i
, �
�
�
i
i
D D ,
èìååì, ÷òî îöåíêà äëÿ ëþáîãî èç íèõ íå áîëüøå ÷åì îöåíêà äëÿ èñõîäíîãî ìíî-
æåñòâà D, ò.å. äëÿ âñåõ D
i
èìååò ìåñòî íåðàâåíñòâî � �( ) ( )D D
i
� .
Ñîãëàñíî ïðàâèëàì îòñå÷åíèÿ îòñåêàþòñÿ òîëüêî òå îáëàñòè D
i
, êîòîðûå íå
ñîäåðæàò òî÷åê, óäîâëåòâîðÿþùèõ óñëîâèþ (3) (øàã 6 àëãîðèòìà), è òå, äëÿ êîòî-
ðûõ �( ) ( )D f x
i
�
0
, ãäå f x( )
0
— äîïóñòèìîå ðåøåíèå èñõîäíîé çàäà÷è.
Èç èçëîæåííûõ ñïîñîáîâ âåòâëåíèÿ, îòñå÷åíèÿ è îöåíèâàíèÿ ñëåäóåò ñïðà-
âåäëèâîñòü ñëåäóþùåãî óòâåðæäåíèÿ îòíîñèòåëüíî ïðåäëîæåííîãî àëãîðèòìà.
Óòâåðæäåíèå 3. Àëãîðèòì ìåòîäà âåòâåé è ãðàíèö, ïðèìåíåííûé ê çàäà÷å
(2)–(4), íàõîäèò åå îïòèìàëüíîå ðåøåíèå.
Ðàññìîòðèì ïðèìåð. Íàéòè ìàêñèìóì ôóíêöèè
x x
x x
1 2
1 2
2
�
�
� max ïðè êîìáè-
íàòîðíîì óñëîâèè ïðèíàäëåæíîñòè ìíîæåñòâó k-ðàçìåùåíèé ( )k � 2 èç ýëåìåí-
òîâ ìóëüòèìíîæåñòâà G x x x E G: ( , ) ( )
,
� �
1 2
5 4
2
, ãäå G � { }1 2 2 4 5, , , , , ïðè äîïîë-
íèòåëüíûõ ëèíåéíûõ îãðàíè÷åíèÿõ x x
1 2
4� � ,
� �2 3 7
1 2
x x .
Ðåøåíèå.
Øàã 1. Çàìåíèâ êîìáèíàòîðíîå óñëîâèå ñèñòåìîé îãðàíè÷åíèé, îïèñûâàþ-
ùèõ ìíîãîãðàííèê ðàçìåùåíèé èñõîäíîé çàäà÷è, ïîëó÷èì çàäà÷ó
x x
x x
1 2
1 2
2
�
�
� max
ïðè ëèíåéíûõ îãðàíè÷åíèÿõ x x
1 2
4� � ,
� �2 3 7
1 2
x x , 1 5
1
� �x , 1 5
2
� �x ,
3 9
1 2
� � �x x . Ïðèìåíèâ ïðåîáðàçîâàíèå (5) ê ïîëó÷åííîé çàäà÷å, èìååì
y y
1 2
� � max ïðè îãðàíè÷åíèÿõ
�y y y
1 2 0
4 0 ,
�
�2 3 7 0
1 2 0
y y y ,
�y y
1 0
5 0,
� �y y
1 0
0 , y y
2 0
5 0
� ,
� �y y
2 0
0,
� �y y y
1 2 0
3 0 ,
y y y
1 2 0
9 0�
� , 2 1
1 2
y y� � .
Øàãè 2–3. Ðåøèâ ïîëó÷åííóþ çàäà÷ó, èìååì y � ( / , / , / )1 5 1 5 3 5 , îòêóäà
x � ( , ).1 3
Øàã 4. Ó÷èòûâàÿ, ÷òî ( , ) ( )
,
1 3
5 4
2
�E G , ïåðåõîäèì ê øàãó 5.
Øàã 5. Îïðåäåëèì èíäåêñ � � 2 , ïîñêîëüêó 3 �G .
Øàã 6. Çàïèøåì äâà îãðàíè÷åíèÿ, êîòîðûå îòñåêàþò x : x
2
2� , x
2
4� , ó÷è-
òûâàÿ, ÷òî
e e e S G e e E G
i i i i i
1
54
2
3 1 2� � � � �max | ( ), , ( , ) ( ){ } ,
e e e S G e e E G
i i i i i
2
54
2
3 1 4� � � � �min { | ( ), , ( , ) ( )} .
Øàã 7. Ïðèìåíèâ ê îãðàíè÷åíèÿì x
2
2� , x
2
4� ïðåîáðàçîâàíèå (5), ïîëó-
÷èì y y
2 0
2 0
� ,
� �y y
2 0
4 0 .
Øàã 8. Ê ëèíåéíîé çàäà÷å øàãà 1 äîáàâèì îãðàíè÷åíèå y y
2 0
2 0
� è ðå-
øèì åå: F y f x x( ) ( ) / , ( , )
1 1 1
2 3 2 2� � � .
Øàã 9. Ê ëèíåéíîé çàäà÷å øàãà 1 äîáàâèì îãðàíè÷åíèå
� �y y
2 0
4 0 è ðå-
øèì åå: F y f x x( ) ( ) / , ( / , )
2 2 2
13 18 5 2 4� � � .
Øàã 10. Ó÷èòûâàÿ, ÷òî
2
3
13
18
� , äëÿ äàëüíåéøåãî âåòâëåíèÿ âûáåðåì çàäà÷ó
øàãà 9. Äàëåå, ïðèìåíèâ àëãîðèòì ê çàäà÷å, ðåøåííîé íà øàãå 9, ïîëó÷èì äâå çà-
äà÷è: ê îäíîé äîáàâëÿåòñÿ îãðàíè÷åíèå âèäà y y
1 0
2 0
� , ê äðóãîé — îãðàíè÷å-
íèå âèäà
� �y y
1 0
4 0. Ïåðâàÿ çàäà÷à íå èìååò ðåøåíèÿ, à âòîðàÿ ïðåäîñòàâëÿåò
öåëåâîé ôóíêöèè çíà÷åíèå F y( ) /
4
9 13� , îòêóäà F x( ) /
4
9 13� , x
4
4 5� ( , ) . Ïàðà
� �9 13 4 5/ , ( , ) — îïòèìàëüíîå ðåøåíèå èñõîäíîé çàäà÷è.
Òàêèì îáðàçîì, ïðåäëîæåí è îáîñíîâàí àëãîðèòì ìåòîäà âåòâåé è ãðàíèö
äëÿ ðåøåíèÿ çàäà÷ îïòèìèçàöèè íà êîìáèíàòîðíîì ìíîæåñòâå ðàçìåùåíèé
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
â ñëó÷àå äðîáíî-ëèíåéíîé öåëåâîé ôóíêöèè è äîïîëíèòåëüíûõ ëèíåéíûõ îãðà-
íè÷åíèÿõ. Öåëåñîîáðàçíî â äàëüíåéøåì ïðîâåñòè òåîðåòè÷åñêóþ îöåíêó åãî
ñëîæíîñòè, à òàêæå íàéòè ãðàíèöû åãî ïðèìåíåíèÿ íà ïðàêòèêå.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ
êîìáèíàòîðíûõ çàäà÷ îïòèìèçàöèè. — Ê.: Íàóê. äóìêà, 1981. — 288 ñ.
2. C ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Ê.:
²í-ò ñèñòåìíèõ äîñë³äæåíü îñâ³òè, 1993. — 188 ñ.
3. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Îïòèì³çàö³ÿ íà ïîë³ðîçì³ùåííÿõ: òåîð³ÿ òà
ìåòîäè. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ.
4. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê ³ í à Ë . Ì . Çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³¿ ç äðîáîâî-ë³í³éíèìè
ö³ëüîâèìè ôóíêö³ÿìè / Çà ðåä. ².Â. Ñåð㳺íêà. — Ê.: Íàóê. äóìêà, 2005. — 117 ñ.
5. Å ì å ö Î . À . , Á à ð à á î ë è í à Ò . Í . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ / Ïîä
ðåä. È.Â. Ñåðãèåíêî. — Ê.: Íàóê. äóìêà, 2008. — 159 ñ.
6. ª ì å ö ü Î . Î . , ª ì å ö ü Î ë - ð à Î . Ðîçâ’ÿçóâàííÿ çàäà÷ êîìá³íàòîðíî¿ îïòèì³çàö³¿ íà
íå÷³òêèõ ìíîæèíàõ. — Ïîëòàâà: ÏÓÅÒ, 2011. — 239 ñ.
7. Å ì å ö Î . À . , × å ð í å í ê î Î . À . Îïòèìèçàöèÿ äðîáíî-ëèíåéíûõ ôóíêöèé íà ðàçìåùåíèÿõ
/ Ïîä ðåä. È.Â. Ñåðãèåíêî. — Ê.: Íàóê. äóìêà, 2011. — 139 ñ.
8. Å ì å ö Î . À . , Ð î ì à í î â à Í . Ã . Îïòèìèçàöèÿ íà ïîëèïåðåñòàíîâêàõ / Ïîä ðåä.
È.Â. Ñåðãèåíêî. — Ê.: Íàóê. äóìêà, 2010. — 105 ñ.
9. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . , × å ð í å í ê î Î . À . Ðåøåíèå çàäà÷ îïòèìèçàöèè
ñ äðîáíî-ëèíåéíûìè öåëåâûìè ôóíêöèÿìè è äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè íà ðàçìåùå-
íèÿõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 5. — Ñ. 79–85.
10. Å ì å ö Î . À . , Ï à ð ô ¸ í î â à Ò . À . Òðàíñïîðòíûå çàäà÷è íà ïåðåñòàíîâêàõ: ñâîéñòâà îöå-
íîê â ìåòîäå âåòâåé è ãðàíèö // Òàì æå. — 2010. — ¹ 6. — Ñ. 106–112.
11. ª ì å ö ü Î . Î . , Ï à ð ô ü î í î â à Ò . Î . Òðàíñïîðòí³ çàäà÷³ êîìá³íàòîðíîãî òèïó: âëàñòè-
âîñò³, ðîçâ’ÿçóâàííÿ, óçàãàëüíåííÿ. — Ïîëòàâà: ÏÓÅÒ, 2011. — 174 ñ.
12. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à Î .  . Çàäà÷³ îïòèì³çàö³¿ íà ïîë³êîìá³íàòîðíèõ ìíîæèíàõ:
âëàñòèâîñò³ òà ðîçâ’ÿçóâàííÿ. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2006. — 144 ñ.
13. ª ì å ö ü Î . Î . , × å ð í å í ê î Î . Î . Ìîäåë³ åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Ïîë-
òàâà: ÏÓÅÒ, 2011. — 204 ñ.
14. à ó ë ÿ í è ö ü ê è é Ë . Ô . Ðîçðîáêà ìîäåëåé ³ íàáëèæåíèõ ìåòîä³â êîìá³íàòîðíî¿ îïòèì³çàö³¿
òà ¿õ çàñòîñóâàííÿ â ³íôîðìàö³éíèõ òåõíîëîã³ÿõ: Àâòîðåô. äèñ. … ä-ðà òåõí. íàóê:. — Ê.,
2005. — 32 ñ.
15. Ä î í å ö ü à . Ï . , Ê î ë º ÷ ê ³ í à Ë . Ì . Åêñòðåìàëüí³ çàäà÷³ íà êîìá³íàòîðíèõ êîíô³ãóðàö³ÿõ.
— Ïîëòàâà: ÐÂÂ ÏÓÅÒ, 2011. — 309 ñ.
16. Ê î ð á ó ò À . À . , Ñ è ã à ë È . Õ . , Ô è í ê å ë ü ø ò å é í Þ . Þ . Ìåòîä âåòâåé è ãðàíèö:
îáçîð òåîðèè, àëãîðèòìîâ, ïðîãðàìì è ïðèëîæåíèé // Math. Operationsch und Statist., Ser.
Optimiz. — 1977. — N 2. — P. 253–280.
17. Ê î ð á ó ò À . À . , Ô è í ê å ë ü ø ò å é í Þ . Þ . Äèñêðåòíîå ïðîãðàììèðîâàíèå. — Ì.: Íàóêà,
1969. — 368 ñ.
18. L a n d A . H . , D o i g A . G . An automatic method of solving discrete programming problems //
Econometrica. — 1960. — 28. — Ð. 497–520.
Ïîñòóïèëà 23.03.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 35
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.3
/CompressObjects /Off
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages false
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /LeaveColorUnchanged
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams true
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts false
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile (Color Management Off)
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 290
/ColorImageMinResolutionPolicy /Warning
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 600
/ColorImageDepth 8
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.01667
/EncodeColorImages true
/ColorImageFilter /FlateEncode
/AutoFilterColorImages false
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 290
/GrayImageMinResolutionPolicy /Warning
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 600
/GrayImageDepth 8
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 2.03333
/EncodeGrayImages true
/GrayImageFilter /FlateEncode
/AutoFilterGrayImages false
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 800
/MonoImageMinResolutionPolicy /Warning
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 2400
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/PDFX3:2003
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError false
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox false
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000500044004600206587686353ef901a8fc7684c976262535370673a548c002000700072006f006f00660065007200208fdb884c9ad88d2891cf62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef653ef5728684c9762537088686a5f548c002000700072006f006f00660065007200204e0a73725f979ad854c18cea7684521753706548679c300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002000740069006c0020006b00760061006c00690074006500740073007500640073006b007200690076006e0069006e006700200065006c006c006500720020006b006f007200720065006b007400750072006c00e60073006e0069006e0067002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f0062006500200050004400460020007000610072006100200063006f006e00730065006700750069007200200069006d0070007200650073006900f3006e002000640065002000630061006c006900640061006400200065006e00200069006d0070007200650073006f0072006100730020006400650020006500730063007200690074006f00720069006f00200079002000680065007200720061006d00690065006e00740061007300200064006500200063006f00720072006500630063006900f3006e002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f007500720020006400650073002000e90070007200650075007600650073002000650074002000640065007300200069006d007000720065007300730069006f006e00730020006400650020006800610075007400650020007100750061006c0069007400e90020007300750072002000640065007300200069006d007000720069006d0061006e0074006500730020006400650020006200750072006500610075002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f006200650020005000440046002000700065007200200075006e00610020007300740061006d007000610020006400690020007100750061006c0069007400e00020007300750020007300740061006d00700061006e0074006900200065002000700072006f006f0066006500720020006400650073006b0074006f0070002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea51fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e3059300230c730b930af30c830c330d730d730ea30f330bf3067306e53705237307e305f306f30d730eb30fc30d57528306b9069305730663044307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e30593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020b370c2a4d06cd0d10020d504b9b0d1300020bc0f0020ad50c815ae30c5d0c11c0020ace0d488c9c8b85c0020c778c1c4d560002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken voor kwaliteitsafdrukken op desktopprinters en proofers. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200066006f00720020007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c00690074006500740020007000e500200062006f007200640073006b0072006900760065007200200065006c006c00650072002000700072006f006f006600650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020007000610072006100200069006d0070007200650073007300f5006500730020006400650020007100750061006c0069006400610064006500200065006d00200069006d00700072006500730073006f0072006100730020006400650073006b0074006f00700020006500200064006900730070006f00730069007400690076006f0073002000640065002000700072006f00760061002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a00610020006c0061006100640075006b006100730074006100200074007900f6007000f60079007400e400740075006c006f0073007400750073007400610020006a00610020007600650064006f007300740075007300740061002000760061007200740065006e002e00200020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740020006600f600720020006b00760061006c00690074006500740073007500740073006b0072006900660074006500720020007000e5002000760061006e006c00690067006100200073006b0072006900760061007200650020006f006300680020006600f600720020006b006f007200720065006b007400750072002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/DEU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200037002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300031003000200053007000720069006e006700650072002d005600650072006c0061006700200047006d006200480020>
/ENU (Use these settings to create Adobe PDF documents for quality printing on desktop printers and proofers. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /NoConversion
/DestinationProfileName ()
/DestinationProfileSelector /NA
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure true
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles true
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /NA
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /LeaveUntagged
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [2834.646 2834.646]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-84157 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:01:45Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Сергиенко, И.В. Емец, О.А. Черненко, О.А. 2015-07-03T10:49:55Z 2015-07-03T10:49:55Z 2012 Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ / И.В. Сергиенко, О.А. Емец, О.А. Черненко // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 30-35. — Бібліогр.: 18 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84157 519.85 Розглянуто точний комбінаторний метод розв’язування задачі оптимізації на розміщеннях з дробово-лінійною функцією цілі та додатковими лінійними обмеженнями. Побудований алгоритм гілок та меж для розв’язування такої задачі ґрунтується на ідеях А. Ленд та A. Дойг. Наведено приклад розв’язування оптимізаційної задачі з дробово-лінійною цільовою функцією на розміщеннях запропонованим алгоритмом. The exact combinatorial method of solving the problem of optimization on arrangements with a linear-fractional objective function and additional linear constraints is considerd. The branch and bound algorithm constructed is based on the ideas of Land and Doig. An illustrative example of solving the optimization problem with a linear-fractional objective function on arrangements with the algorithm is presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ Розв’язування умовної задачі оптимізації дробово-лінійної цільової функції на множині розміщень методом гілок та меж Solving a conditional problem of optimization of a linear-fractional objective function on arrangements by the branch and bound method Article published earlier |
| spellingShingle | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ Сергиенко, И.В. Емец, О.А. Черненко, О.А. Системный анализ |
| title | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ |
| title_alt | Розв’язування умовної задачі оптимізації дробово-лінійної цільової функції на множині розміщень методом гілок та меж Solving a conditional problem of optimization of a linear-fractional objective function on arrangements by the branch and bound method |
| title_full | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ |
| title_fullStr | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ |
| title_full_unstemmed | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ |
| title_short | Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ |
| title_sort | решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84157 |
| work_keys_str_mv | AT sergienkoiv rešenieuslovnoizadačioptimizaciidrobnolineinoicelevoifunkciinamnožestverazmeŝeniimetodomvetveiigranic AT emecoa rešenieuslovnoizadačioptimizaciidrobnolineinoicelevoifunkciinamnožestverazmeŝeniimetodomvetveiigranic AT černenkooa rešenieuslovnoizadačioptimizaciidrobnolineinoicelevoifunkciinamnožestverazmeŝeniimetodomvetveiigranic AT sergienkoiv rozvâzuvannâumovnoízadačíoptimízacíídrobovolíníinoícílʹovoífunkcíínamnožinírozmíŝenʹmetodomgíloktamež AT emecoa rozvâzuvannâumovnoízadačíoptimízacíídrobovolíníinoícílʹovoífunkcíínamnožinírozmíŝenʹmetodomgíloktamež AT černenkooa rozvâzuvannâumovnoízadačíoptimízacíídrobovolíníinoícílʹovoífunkcíínamnožinírozmíŝenʹmetodomgíloktamež AT sergienkoiv solvingaconditionalproblemofoptimizationofalinearfractionalobjectivefunctiononarrangementsbythebranchandboundmethod AT emecoa solvingaconditionalproblemofoptimizationofalinearfractionalobjectivefunctiononarrangementsbythebranchandboundmethod AT černenkooa solvingaconditionalproblemofoptimizationofalinearfractionalobjectivefunctiononarrangementsbythebranchandboundmethod |