Решение методом ветвей и границ одной задачи минимизации взвешенной длины связующей сети
Запропоновано і реалізовано метод гілок та меж для задачі мінімізації зваженої довжини зв’язуючої сітки при лінійному розташуванні прямокутних елементів. Розглянуто правило галуження допустимої множини на підмножини, а також обґрунтовано оцінку допустимої підмножини. Розглянуто ілюстративний приклад...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/207513 |
| 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: | Решение методом ветвей и границ одной задачи минимизации взвешенной длины связующей сети / Емец О.А., Емец А.О. // Проблемы управления и информатики. — 2012. — № 4. — С. 44–54. — Бібліогр.: 16 назв. - рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859614231274455040 |
|---|---|
| author | Емец, О.А. Емец, А.О. |
| author_facet | Емец, О.А. Емец, А.О. |
| citation_txt | Решение методом ветвей и границ одной задачи минимизации взвешенной длины связующей сети / Емец О.А., Емец А.О. // Проблемы управления и информатики. — 2012. — № 4. — С. 44–54. — Бібліогр.: 16 назв. - рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Запропоновано і реалізовано метод гілок та меж для задачі мінімізації зваженої довжини зв’язуючої сітки при лінійному розташуванні прямокутних елементів. Розглянуто правило галуження допустимої множини на підмножини, а також обґрунтовано оцінку допустимої підмножини. Розглянуто ілюстративний приклад.
The branch and bound method is offered and realized for a minimization problem of the weighted length of a connecting grid at linear placing of rectangular elements. The rule of branching of admissible set on subsets is considered. The estimation of an admissible subset is offered and proved. The illustrative example is given
|
| first_indexed | 2025-11-28T16:34:23Z |
| format | Article |
| fulltext |
© О.А. ЕМЕЦ, А.О. ЕМЕЦ , 2012
44 ISSN 0572-2691
УДК 519.8
О.А. Емец, А.О. Емец
РЕШЕНИЕ МЕТОДОМ ВЕТВЕЙ
И ГРАНИЦ ОДНОЙ ЗАДАЧИ
МИНИМИЗАЦИИ ВЗВЕШЕННОЙ
ДЛИНЫ СВЯЗУЮЩЕЙ СЕТИ
Введение
Задачи комбинаторной оптимизации (см., например, [1–12]) позволяют все
более адекватно моделировать объекты, процессы, явления и системы. Одна из
таких задач — задача минимизации взвешенной длины связующей сети при ли-
нейном размещении элементов — рассматривалась в [2, 4, 6], где предложены ал-
горитмы переборного типа для ее решения. В работах [13–15] для решения задач
евклидовой комбинаторной оптимизации на перестановках предложен подход
в рамках метода ветвей и границ (МВГ) с эффективной процедурой оценивания
допустимых подмножеств. Авторам не известны работы, в которых МВГ приме-
няется к задаче минимизации взвешенной длины связующей сети при линейном
размещении прямоугольных элементов. В настоящей статье предлагается рас-
смотреть применение МВГ к этой задаче с использованием результатов, изложен-
ных в [13–15].
Постановка задачи
Пусть имеется n прямоугольников одинаковых размеров: ,1a которые распо-
ложены на декартовой плоскости вдоль оси абсцисс в линию так, что стороны
длины a соседних прямоугольников совпадают, а центр симметрии первого слева
прямоугольника находится в начале координат. Центры симметрии прямоугольников
соединены между собой связями с весом 0pqc ,qp }....,,2,1{, nJqp n
Необходимо определить такое размещение прямоугольников, чтобы взве-
шенная длина сети, которая связывает центры симметрии прямоугольников, име-
ла наименьшее значение.
Обозначим параметры размещения прямоугольников. Пусть nxx ...,,1 — абс-
циссы центров симметрии прямоугольников с номерами n...,,1 соответственно.
Очевидно, их ординаты .0...1 nyy Легко видеть, что взвешенная длина сети,
которая связывает центры симметрии прямоугольников, полностью определяется
порядком размещения прямоугольников в линии, т.е. некоторой перестановкой
)()...,,( 1 nnn JEiii из множества перестановок )( nn JE первых n натуральных
чисел },...,,2,1{ nJn где ti — номер прямоугольника, который стоит на месте t;
,ti .nJt Рассмотрим две равные подстановки: .
...21
...
...
...21 21
21
n
jjj
iii
n n
n
В первой строке стоят номера мест, в линии слева направо, а во второй — номера
прямоугольников, которые стоят на этих местах, т.е. tj — номер места, на кото-
ром стоит прямоугольник с номером ;t ,tj .nJt Тогда, очевидно, взвешенная
длина сети будет определяться функционалом ),( jf который зависит от переста-
новки ),()...,,( 1 nnn JEjjj а именно .)(
1
1
qp jjpq
n
qpq
n
p
xxcjf
Парамет-
ры размещения прямоугольников ,tx ,nJt очевидно, могут принимать только
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 4 45
значения .1,2...,,2,1,0 nn Это позволяет с учетом соотношения 1 tj jx
t
за-
писать )( jf в виде
.)(
1
1
1
qppq
n
pq
n
p
jjcjf
(1)
Математическая модель задачи принимает вид полностью комбинаторной
безусловной е-задачи [2, 4] на перестановках с выпуклой целевой функцией ),( jf
а именно: найти
),(min)(
)(
** jfjff
nn JEj
(2)
),(minarg
)(
* jfj
nn JEj
(3)
где )( jf определяется соотношением (1).
Применяя МВГ к задаче (1)–(3), легко видеть, что выражения qp jj в форму-
ле (1) принимают значение 1 1( n раз). Значение 2 принимается этим выражением
2n раза и т.д., значение 1n принимается модулем из (1) один раз. Объединим все
значения в мультимножество G с основой )1...,,2,1()( nGS и первичной специ-
фикацией ),1...;;2;1(][ nnG т.е. }.)1(....,,...,,2,1{ 111 njG jnnn
Очевид-
но, что количество Gk элементов в G как количество элементов арифметической
прогрессии такое: ).1(5,02/)1(]1)1[( nnnnG Значит, ).1(5,0 nnk
В G имеется 1 n разных элементов.
Рассмотрим множество )(GEk перестановок элементов мультимножества G.
Очевидно, что )( nn JEj )()...,,( 1 GExxx kk такое, что ),()( xFjf где
,)(
1
tt
k
t
xdxF
(4)
nJqp , ;kJt ;pqt cd .qpt jjx (5)
Легко видеть, что противоположное неверно, т.е. не для каждой перестановки
)(GEx k существует перестановка ),( nn JEj для которой выполняется (4), (5).
Обозначим )(GED k множество всех таких перестановок ),(GEx k для
которых существует перестановка )( nn JEj такая, что выполняется (4), (5). То-
гда задачу (1)–(3) запишем в виде эквивалентной задачи: найти
),(min)(
)(
** xFxFF
GEx k
(6)
)(minarg
)(
* xFx
GEx k
(7)
при условии
,Dx (8)
где )(xF — линейная функция (4), а значит, задача (4), (6)–(8) — это полностью
комбинаторная условная е-задача на перестановках с линейной целевой функ-
цией (4) и нелинейными дополнительными ограничениями (8). Применим к ней
МВГ на основе подходов, рассмотренных в [13–15].
46 ISSN 0572-2691
Применение метода ветвей и границ
Как известно, для организации МВГ необходимо определить следующие
правила: 1) ветвление допустимого множества на подмножества; 2) оценивание
допустимых подмножеств; 3) отсечение бесперспективных подмножеств допу-
стимых решений.
1. Ветвление допустимого подмножества. Дерево ветвления будет иметь от
корня 1n уровень с возрастанием номеров от корня (уровень 0) по ветвям до
листьев. Ветвление будет происходить «в глубину» с уровня l на уровень .1l А
если это невозможно, то «в ширину» — до нового множества текущего l уровня
или вершины )1( l -го уровня. Для иллюстрации удобно использовать пример,
условие которого приведено ниже.
Пример. Пусть ;5n наддиагональная матрица связей (вес связей) приведе-
на на рис. 1, а.
Для выбора порядка переменных при ветвлении множества допустимых реше-
ний упорядочим коэффициенты pqc (то же самое )td целевых функций (1), (4):
,...
21 k
ddd (9)
а элементы ,tg ,kJt мультимножества G считаем упорядоченными так:
....21 kggg (10)
Допустимые подмножества первого уровня определяются заданием перемен-
ной
1
x первого подходящего в порядке (10) значения: ;1
1
ngt .1 kJt При
этом образуется мультимножество }.{
~
1t
gGG Допустимое подмножество, ко-
торое образовалось, обозначим .1
1
t
D
Для примера учтем .10...321
10321
dddd Понятно, что
;41 g ;332 gg ;2654 ggg .110987 gggg Имеем ,4
1
x
;1
1
d ,11 t и это условие определяет множество .1
1
t
D
Удобно интерпретировать допустимое подмножество 1
1
D в терминах исход-
ной задачи. Рассмотрим матрицу, в которой над главной диагональю стоят воз-
можные значения модулей qp jj для ),...,,2,1( nj т.е. ,pjp qjq
nJqp , (рис. 1, б).
qj 1 2 3 4 5
q
p
1 2 3 4 5
pj q
p
1 2 3 4 5
1 1 5 4 7 1 1 1 2 3 4
2 2 9 3 2 2 1 2 3
3 8 6 3 3 1 2
4 10 4 4 1
5 5 5
а б
Рис. 1
Выбор 41 g означает выбор для
1
1 dcpq ;1pj 5qj и определение
1
1
D (рис. 2, а), т.е. выбор 1 означает выбор 112 c и .421 jj (Из рис. 1, а
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 4 47
и рис. 2, а видно, что в строке 1pj могут стоять только 2, 9, 3 (см. строку 2 на
рис. 1, а)). При этом множество 1
1
D можно определять условием ;12 j ,51 j
введя для этого множества более удобное обозначение — 15
21Q (верхние индексы —
значения ,pj ,qj а нижние — соответствующие им значения p и q).
Следующий уровень ветвления соответствует
2
d (9). При возможности из 1
1
D
образуется 21
12
D (а вообще 21
21
ii
D ) 2
22
ngx i (для 1
1
D имеем ).22
gx
Третий уровень ветвления соответствует
3
d из (9), для которого можно назна-
чить ,3
33
ngx i и т. д. Для примера имеем: :21
12
D 3
2
x
2
d ;2p
3q 223 c ;4pj 1qj ;4( 3 j ).12 j Это также означает 531 c при
;4pj 5pj 154
21312
21( QD
(рис. 2, б).
Затем для 321
123
D определяются 23
3
nx в строке 2q ).1( qj Судя
по рис. 1, а, возможно 3
3
3
3
dd (рис. 3, а), т.е. на первом уровне определяется
одно слагаемое в (1) и (4), на втором — 2, на третьем — 3, на четвертом — 4, …,
на )1( n -м уровне 1n слагаемое. Последний )1( n -й уровень однозначно
определяется на )2( n -м уровне. Поэтому фактически уровней ветвления :2n
для первой ветви — это ;15
211
1 QD
;154
21312
21 QD
1543
21351234123
4321321 QDD
).3,2,4,1,5(015432
21354 jQ
qj 1 2 3 4 5 qj 1 2 3 4 5
pj q
p
2 1
pj q
p
2 3 1
1 2 1 1 2 2 1
2 2
3 3
4 4 3 5
5 1 5 1
а б
Рис. 2
qj 1 2 3 4 5 qj 1 2 3 4 5
pj q
p
2 4 5 3 1
pj q
p
2 5 4 3 1
1 2 9 3 2 1 1 2 3 9 2 1
2 4 10 8 4 2 5 10 6 7
3 5 6 7 3 4 8 4
4 3 5 4 3 5
5 1 5 1
а б
Рис. 3
Множество 4321321
1234123
DD — это одноэлементное множество-перестановка
).3,2,4,1,5()4,3,5,4,2(0 j Из рис. 1, б и рис. 3, а (заполнение для )321
123
D лег-
ко видеть, что .8841)42(3)783(2)56109(1)( 0
0 Fjf Та-
ким образом,
0j — допустимое решение, а 0F — значение целевой функции на нем.
48 ISSN 0572-2691
При ветвлении «в ширину» на третьем уровне )3( l имеем
1543
213421
321
3
QD
i
)2,3,4,1,5(115432
21345 jQ (рис. 3, б, заполнение для )),2,3,4,1,5(1 j )( 1
1 jfF
).95)58103(1)469(2)72(314 На рис. 4 показан фрагмент
дерева. Ветви А, B будут продлены.
15
21Q 154
213Q
154
215Q
154
214Q
15
23Q 15432
21435Q
15432
21435Q
15432
21543Q
15432
21534Q
)2,3,4,1,5(1
15432
21345
1543
2134
j
QQ
)3,2,4,1,5(0
15432
21354
1543
2135
j
QQ
A
B 1045 F
1074 F
933 F
892 F
951 F
880 F
)( 55 JE
83
83
94
84
85
⊝
⊝
Рис. 4
При возвращении на верхний уровень )2( l имеем ,154
2151
3
321
32
QD
ii
по-
скольку ,3pqc элемент исходной матрицы связей — это .253
cd Его ставим в
клеточку с ,2
3
x это клетка в столбце ,4qj где 5q в строке ,1pj 2p
(рис. 5, а). Получаем );4,2,3,1,5(215432
21534 jQ )43(314)( 2
2 jfF
.89)7689(1)5102(2 Далее используем только вторые обозначения
допустимых множеств (как более удобные):
)4,3,2,1,5(15432
21543
3 Qj (рис. 5, б),
,93)71082(1)469(2)53(341)( 3
3 jfF
)2,4,3,1,5(4 j (рис. 6, а) )3,4,2,1,5(5 j (рис. 6, б),
,107)4863(1)5102(2)79(341)( 4
4 jfF
104)1062(1)783(2)59(341)( 5
5 jfF (см. рис. 4).
qj 1 2 3 4 5 qj 1 2 3 4 5
pj q
p
2 4 3 5 1 pj q
p
2 3 4 5 1
1 2 9 2 3 1 1 2 2 9 3 1
2 4 8 10 4 2 3 8 6 5
3 3 6 5 3 4 10 4
4 5 7 4 5 7
5 1 5 1
а б
Рис. 5
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 4 49
Все возможные ветвления множества 15
21Q осуществлены, на уровне 1l
разветвляем «в ширину», т.е., рассматриваем все решения, в которых в (4) есть
слагаемое .4212
gd Эти решения образуют множество, которое определя-
ется ,2 23ccpq т.е. (рис. 7, а) имеем множество .15
21Q
2. Оценивание допустимых подмножеств. Как известно, число )(D может
служить оценкой допустимого подмножества D в задаче минимизации ),(xF если
)()( DxF .Dx
При нахождении определенного подмножества Q согласно правилам ветвле-
ния определяется некоторое множество переменных DXxx Bt
,,
1
в за-
даче (4)–(8), которые, приобретая значения ,,,
1
GGgg Bt
т.е.
gx
,tJ имеют коэффициенты ....,,
1 t
dd Обозначим },~...,,~{
~
1 rB ggGGG
};~...,,~{}...,,{}...,,{
~
11 1 ccddddC
tk пусть , tk очевидно .
~~
CG
Пронумеруем элементы C
~
и G
~
:
,~...~
1 cc (11)
.~...~
1 gg (12)
Теорема 1. Оценкой )(D некоторого подмножества Q допустимых реше-
ний, полученного согласно описанным правилам ветвления в задаче (4)–(8), мо-
жет быть величина
,)( cQ (13)
,
1
t
p
pp
gd (14)
1
~~
q
qq gcc (15)
при выполнении условий (11), (12).
Доказательство. Обозначим },~...,,~{}...,,{
~
11 xxXxxX Bk пусть нуме-
рация переменных во множестве X
~
без ограничений общности такая, что пере-
менная qx~ имеет коэффициент qc~ в (4). Тогда Qx согласно (4)
.~~)(
111
qq
q
t
p
pp
k
p
xcxdxdxF
pp
(16)
Первая сумма в (16) постоянная согласно (14): const,
1
pp
k
p
xd а по-
следняя сумма в (16) qq
q
xc ~~
1
— это значение линейной функции на некоторой
перестановке )
~
()~,...,~(~ ~1 GExxx из элементов мультимножества ,
~
G среди
которых v~ разных элементов.
Согласно следствию теоремы 3.1. из [2] (которое совпадает с теоремой 368
из [16]) при условиях (11), (12) имеем
.~~~~min~~
11)
~
(~
1
cgcxcxc qq
q
qq
qGEx
qq
q
(17)
Таким образом, из (16), (17) следует
,)( cxF (18)
50 ISSN 0572-2691
т.е. число , которое стоит в правой части неравенства (18): , c можно ис-
пользовать как оценку )(Q допустимого подмножества Q в задаче (1)–(4) при
решении ее МВГ, поскольку Qx ),()( xFQ что и нужно было доказать.
Подсчитаем оценки для подмножества, показанные на рис. 4. При этом оцен-
ки «листов» дерева совпадают со значением целевой функции для листа. Оценку
множества )(Q на рисунке обозначим возле изображения множества.
Найдем ;)( 15
21
15
21
*15
21 ccQ ;4115
21 vv ),~,~(15
21 gccc где
)1,2,3,4,5,6,7,8,9,10(~ c ),3,3,2,2,2,1,1,1,1(~ g т.е. ,79c .83)( 15
21 Q
Здесь и далее )~,~( gc обозначает скалярное произведение векторов ,~c .~g
Вычислим .)( 154
213
154
213
154
213 ccQ Как видно из рис. 2, б, 14154
231
;151532 ),~,~( gcc
где );3,4,5,6,7,8,9,10(~ c );3,2,2,2,1,1,1(~ g
,70c .85)( *154
213 cQ
Подсчитаем .)( 154
215
154
215
154
215 cQ Из рис. 5, а следует, что 154
215
;20173314 для ;)~,~(154
215
cgcc где );2,4,5,6,8,9,10(~ c
);3,2,2,2,1,1,1(~ g ;63* c .83)( 154
215 Q
Определим .)( 154
214
154
214
154
214 cQ Как видно из рис. 6, а 41154
213
,352781439 ),~,~(154
214 gccc где );2,3,5,6,7,8,10(~ c ,1,1,1(~ g
);3,2,2,2 ;59c .94)( 154
214 cQ
Вставим .)( 15
23
15
23
15
23 cQ Из рис. 7, а следует, что ;84215
23
),~,~(15
23
* gccc где );1,3,4,5,6,7,8,9,10(~ c );3,3,2,2,2,1,1,1,1(~ g ;76* c
таким образом, .84)( *15
23 cQ
qj 1 2 3 4 5 qj 1 2 3 4 5
pj q
p
2 5 3 4 1
pj q
p
2 3 5 4 1
1 2 3 2 9 1 1 2 2 3 9 1
2 5 6 10 7 2 3 6 8 5
3 3 8 5 3 5 10 7
4 4 4 4 4 4
5 1 5 1
а б
Рис. 6
qj 1 2 3 4 5 qj 1 2 3 4 5
pj
q
p
2 4 5 1 3
pj
q
p
2 5 4 1 3
1 2 9 3 1 2 1 2 3 9 1 2
2 4 10 4 8 2 5 10 7 6
3 5 7 6 3 4 4 8
4 1 5 4 1 5
5 3 5 3
а б
Рис. 7
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 4 51
3. Отсечение бесперспективных подмножеств допустимых решений. Пред-
лагается использовать классическое правило отсечения МВГ: если ,)( 0FQ где
0F — текущее рекордное значение целевой функции (рекорд), то Q — бесперспек-
тивная вершина, и она отсекается. Если ,0FFt то рекорд обновляется и становит-
ся равным .:: 0 tt FFF После этого проверяется правило отсечения для всех не-
разветвленных вершин («почек» дерева).
Таким образом, из рис. 4 видно, что множество 154
214Q не надо разветвлять
(отметим это знаком возле оценки), а надо отсекать как бесперспективное, по-
скольку его оценка .8894 0 F Знаки ⊝ возле его подмножеств означают,
что в МВГ 4F и 5F не вычисляются.
Продолжим рассмотрение иллюстративного примера. Разветвляя ,15
23Q обра-
зуем .154
231Q Считаем . c Из рис. 7, а видно, что ;16153142
),~,~( gcc где ),3,4,6,7,8,9,10(~ c );3,2,2,2,1,1,1(~ g ;70c 86
.880 F Разветвляя множество дальше «в глубину», получаем ;615432
23514 jQ
.92)57109(1)643(2)81(342 06 FF Рекорд не обновляется.
На этом уровне образуем
715432
23145 jQ (рис. 7, б). )61(3247F
099)54103(1)879(2 F . Рекорд не обновляется. Дерево МВГ по-
казано на рис. 8, который является продолжением рис. 4.
Из рис. 9, а видно, что для ,)( 154
235
154
235
154
235 cQ величина 24154
235v
;236133 ),~,~(154
235 gccc
где ),1,4,5,7,8,9,10(~ c );3,2,2,2,1,1,1(~ g
;62c .85 0Fc
Множество разветвляем дальше («в глубину»). Обра-
зуем ;815432
23514 jQ )6749(1)5101(2)83(3248F .99 0F Ре-
корд не обновляется. Образуем
915432
23541 jQ (рис. 9, б); )53(3429F
;101)61041(1)879(2 0F рекорд не обновляется. Возвращаемся на
уровень .2l Образуем 154
234Q (см. рис. 8): ; c ;432716186342
),~,~( gcc ),1,3,4,5,6,7,10(~ c );3,2,2,2,1,1,1(~ g ;50c .93 0F Вер-
шина отсекается как неперспективная (знак на рис. 8). Аналогично образуется
остальная часть дерева в МВГ. На рис. 8 и на рис. 10 — окончание решения
примера.
Решением является рекорд минимального значения целевой функции .0F
Заметим, что в примере рекорд не улучшился, а как был, так и остался первым
допустимым решением при указанном ветвлении: .880 F Это значение дости-
гается при )3,2,4,1,5(0 j (что соответствует размещению )1,3,5,4,2(0 i и сим-
метричному )).2,4,5,3,1(11 i
Замечание. Для уменьшения перебора вдвое в МВГ можно отслеживать рас-
смотрение симметричных относительно центра комбинаций, т.е. 54321 и
12345 дают симметричные размещения с одинаковым значением целевой
функции. Это можно рассматривать как еще одно правило отсечения.
52 ISSN 0572-2691
154
321Q
154
234Q
15
25Q
15432
23154Q
A
C
926 F
85
85
86
B
15432
23145Q 997 F
15432
23514Q 998 F
15432
23541Q 1019 F
15
24Q
0100 F
093 F
154
251Q
091 F
154
253Q
094 F
154
254Q
095 F
154
235Q
154
124Q
154
123Q
15432
12435Q 8910 F
84
091 F
15
24Q
83
15432
12453Q 011 88 FF
154
125Q
088 F
15
14Q
87
154
142Q
094 F
154
143Q
090 F
154
145Q
093 F
15
13Q
089 F
15
15Q
094 F
15
32Q
84
154
321Q
094 F
154
325Q
091 F
091 F
154
324Q
15
31Q
15
35Q
15
34Q
089 F
091 F
097 F
Рис. 8
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 4 53
154
523Q
094 F
15
52Q
85
154
521Q
097 F
154
524Q
15
43Q
097 F
15
42Q
0100 F
15
45Q
0103 F
15
41Q
87
154
413Q
096 F
154
412Q
0103 F
154
415Q
99
15
53Q
091 F
15
51Q
094 F
15
54Q
0103 F
С
097 F
Рис. 10
Заключение
В настоящей работе задача минимизации взвешенной длины связующей сети
при линейном размещении прямоугольных элементов сведена к линейной задаче
на специальном множестве перестановок, для которой предложен и реализован
МВГ. Обосновано правило ветвления допустимого множества на подмножества,
предложена и обоснована оценка допустимых множеств.
При дальнейших исследованиях интересно было бы установить условия, при
которых первое допустимое решение (как в приведенном иллюстративном приме-
ре) является решением задачи.
О.О. Ємець, О.О. Ємець
РОЗВ’ЯЗУВАННЯ МЕТОДОМ ГІЛОК ТА МЕЖ
ОДНІЄЇ ЗАДАЧІ МІНІМІЗАЦІЇ ЗВАЖЕНОЇ
ДОВЖИНИ ЗВ’ЯЗУЮЧОЇ СІТКИ
Запропоновано і реалізовано метод гілок та меж для задачі мінімізації зваженої
довжини зв’язуючої сітки при лінійному розташуванні прямокутних еле-
ментів. Розглянуто правило галуження допустимої множини на підмножини,
а також обґрунтовано оцінку допустимої підмножини. Розглянуто ілюстратив-
ний приклад.
O.A. Iemets, A.О. Yemets
THE SOLUTION OF A MINIMIZATION PROBLEM
OF THE WEIGHTED LENGTH OF A CONNECTING
GRID BY BRANCH AND BOUND METHOD
The branch and bound method is offered and realized for a minimization problem of
the weighted length of a connecting grid at linear placing of rectangular elements.
qj 1 2 3 4 5
pj q
p
2 4 1 5 3
1 2 9 1 3 2
2 4 4 10 8
3 1 7 5
4 5 6
5 3
а
qj 1 2 3 4 5
pj
q
p
2 1 4 5 3
1 2 1 9 3 2
2 1 4 7 5
3 4 10 8
4 5 6
5 3
б
Рис. 9
54 ISSN 0572-2691
The rule of branching of admissible set on subsets is considered. The estimation of an
admissible subset is offered and proved. The illustrative example is given.
1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных за-
дач оптимизации. — Киев : Наук. думка, 1981. — 288 с.
2. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Київ :
ІСДО, 1993. — 188 с.
3. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимізація на полірозміщеннях: теорія та методи.
— Полтава : РВЦ ПУСКУ, 2005. — 103 с.
4. Емец О.А. Евклидовы комбинаторные множества и оптимизация на них. Новое в матема-
тическом программировании. — Киев : УМК ВО, 1992. — 92 с.
5. Ємець О.О., Колєчкіна Л.М., Недобачій С.І. Дослідження областей визначення задач евклі-
дової комбінаторної оптимізації на переставних множинах. Частина 1. — Полтава : ПДТУ,
ЧПКП «Легат», 1999. — 64 с.
6. Ємець О.О., Колєчкіна Л.М., Недобачій С.І. Дослідження областей визначення задач евклі-
дової комбінаторної оптимізації на переставних множинах. Частина 2. — Полтава: ПДТУ,
ЧПКП «Легат», 1999. — 32 с.
7. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільо-
вими функціями, — Київ : Наук. думка, 2005. — 117 с.
8. Ємець О.О., Роскладка О.В. Задачі оптимізації на полікомбінаторних множинах: властиво-
сті та розв’язування. — Полтава : РВЦ ПУСКУ, 2006. — 114 с.
9. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. — Киев : Наук.
думка, 2008. — 159 с.
10. Емец О.А., Романова Н.Г. Оптимизация на полиперестановках. — Киев : Наук. думка, 2010.
— 105 с.
11. Гуляницький Л.Ф. Розробка моделей і наближених методів комбінаторної оптимізації та їх
застосування в інформаційних технологіях: Автореф. дис. … д-ра техн. наук. — Київ : ІК
НАНУ, 2005. — 32 с.
12. Гребеннік І.В. Математичні моделі та методи комбінаторної оптимізації в геометричному
проектуванні: Автореф. дис. … д-ра техн. наук. — Харків : ІПМаш НАНУ, 2006. — 34 с.
13. Ємець О.О., Парфьонова Т.О. Оцінювання допустимих множин розв’язків комбінаторної
транспортної задачі на переставленнях, що розв’язується методом гілок та меж // Наукові
вісті НТУУ «КПІ». — 2010. — № 1. — С. 21–27.
14. Емец О.А., Парфенова Т.А. Транспортные задачи на перестановках: свойства оценок в ме-
тоде ветвей и границ // Кибернетика и системный анализ. — 2010. — № 6. — С. 106–112.
15. Чілікіна Т.В., Ємець О.О., Ємець Є.М., Парфьонова Т.О. Оцінки в методі гілок та меж для
лінійної умовної задачі комбінаторної оптимізації на переставленнях // Інформатика та си-
стемні науки (ІСН-2011): Матеріали ІІ Всеукр. наук.-практ. конф. (17–19 березня 2011 р.,
Полтава). — Полтава: РВВ ПУЕТ. — С. 328–331.
16. Харди Г.Г., Литтльвуд Дж.Е., Полиа Г. Неравенства. — М. : Гос. изд-во иностр. лит., 1948.
— 455 с.
Получено 01.09.2011
|
| id | nasplib_isofts_kiev_ua-123456789-207513 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-11-28T16:34:23Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Емец, А.О. 2025-10-08T17:14:49Z 2012 Решение методом ветвей и границ одной задачи минимизации взвешенной длины связующей сети / Емец О.А., Емец А.О. // Проблемы управления и информатики. — 2012. — № 4. — С. 44–54. — Бібліогр.: 16 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207513 519.8 10.1615/JAutomatInfScien.v44.i7.30 Запропоновано і реалізовано метод гілок та меж для задачі мінімізації зваженої довжини зв’язуючої сітки при лінійному розташуванні прямокутних елементів. Розглянуто правило галуження допустимої множини на підмножини, а також обґрунтовано оцінку допустимої підмножини. Розглянуто ілюстративний приклад. The branch and bound method is offered and realized for a minimization problem of the weighted length of a connecting grid at linear placing of rectangular elements. The rule of branching of admissible set on subsets is considered. The estimation of an admissible subset is offered and proved. The illustrative example is given ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Решение методом ветвей и границ одной задачи минимизации взвешенной длины связующей сети Розв’язання методом гілок та меж однієї задачі мінімізації зваженої довжини зв’язуючої сітки The Solution of a Minimization Problem of the Weighted Length of a Connecting Grid by Branch and Bound Method Article published earlier |
| spellingShingle | Решение методом ветвей и границ одной задачи минимизации взвешенной длины связующей сети Емец, О.А. Емец, А.О. Оптимальное управление и методы оптимизации |
| title | Решение методом ветвей и границ одной задачи минимизации взвешенной длины связующей сети |
| title_alt | Розв’язання методом гілок та меж однієї задачі мінімізації зваженої довжини зв’язуючої сітки The Solution of a Minimization Problem of the Weighted Length of a Connecting Grid by 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/207513 |
| work_keys_str_mv | AT emecoa rešeniemetodomvetveiigranicodnoizadačiminimizaciivzvešennoidlinysvâzuûŝeiseti AT emecao rešeniemetodomvetveiigranicodnoizadačiminimizaciivzvešennoidlinysvâzuûŝeiseti AT emecoa rozvâzannâmetodomgíloktamežodníêízadačímínímízacíízvaženoídovžinizvâzuûčoísítki AT emecao rozvâzannâmetodomgíloktamežodníêízadačímínímízacíízvaženoídovžinizvâzuûčoísítki AT emecoa thesolutionofaminimizationproblemoftheweightedlengthofaconnectinggridbybranchandboundmethod AT emecao thesolutionofaminimizationproblemoftheweightedlengthofaconnectinggridbybranchandboundmethod |