Метод ветвей и границ для задач оптимизации на нечётких множествах
Запропоновано алгоритм методу гілок та меж для задачі мінімізації в нечіткій постановці. Проілюстровано застосування методу гілок та меж до комбінаторної транспортної задачі на переставленнях з нечіткими даними. The algorithm of branch and bound method for the minimization problem in the fuzzy setti...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2013 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/207600 |
| 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: | Метод ветвей и границ для задач оптимизации на нечётких множествах / О.А. Емец, А.О. Емец, Т.А. Парфенова // Проблемы управления и информатики. — 2013. — № 2. — С. 55–60. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860119584728678400 |
|---|---|
| author | Емец, О.А. Емец, А.О. Парфенова, Т.А. |
| author_facet | Емец, О.А. Емец, А.О. Парфенова, Т.А. |
| citation_txt | Метод ветвей и границ для задач оптимизации на нечётких множествах / О.А. Емец, А.О. Емец, Т.А. Парфенова // Проблемы управления и информатики. — 2013. — № 2. — С. 55–60. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Запропоновано алгоритм методу гілок та меж для задачі мінімізації в нечіткій постановці. Проілюстровано застосування методу гілок та меж до комбінаторної транспортної задачі на переставленнях з нечіткими даними.
The algorithm of branch and bound method for the minimization problem in the fuzzy setting is proposed. The use of branch and bound method for combinatorial transportation problem on permutations with fuzzy data is shown.
|
| first_indexed | 2025-12-07T17:38:46Z |
| format | Article |
| fulltext |
© О.А. ЕМЕЦ, А.О. ЕМЕЦ, Т.А. ПАРФЕНОВА, 2013
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 2 55
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
И МЕТОДЫ ОПТИМИЗАЦИИ
УДК 519.85
О.А. Емец, А.О. Емец, Т.А. Парфенова
МЕТОД ВЕТВЕЙ И ГРАНИЦ ДЛЯ ЗАДАЧ
ОПТИМИЗАЦИИ НА НЕЧЕТКИХ МНОЖЕСТВАХ
Введение
Задачи комбинаторной оптимизации на нечетких множествах все еще недоста-
точно исследованы. Количество работ в этом направлении весьма ограничено [1–12].
Практически нет методов, учитывающих специфику таких задач. В настоящей работе
обосновывается общий подход в рамках метода ветвей и границ (МВГ) к решению
задачи минимизации в нечеткой постановке, который иллюстрируется комбинатор-
ной транспортной задачей на перестановках с нечеткими данными.
Постановка задачи
Пусть )(xF — функция, определенная на множестве X )( Xx нечетких чи-
сел; ,)( XxF т.е. значение, которое она принимает, — также нечеткое число;
XD — множество допустимых нечетких чисел.
Используя операции из [5–12] (в том числе нахождение минимума и максимума),
задачу оптимизации на множестве нечетких чисел можно сформулировать так: найти
).(min xF
Dx
(1)
МВГ при оптимизации на нечетких множествах
Пусть S — некоторый список (массив), recn — переменная, обозначающая
номер рассмотренного МВГ допустимого решения. Алгоритм МВГ для (1) изло-
жен в следующих шагах.
Шаг 0. ;S .0recn Задание допустимой области D )( D и целевой
функции F на D.
Шаг 1. Разбиение множества D на подмножества nDD ...,,1 со свойствами
;iD ji DD },...,,2,1{, nJji n ....1 nDDD Множества nDD ...,,1
считаем неразветвленными и неотсеченными. Назовем такое множество «поч-
кой», а свойства таких множеств — «свойствами почек».
Каждому множеству, которое не принадлежит S и является почкой, припи-
шем оценку XD iii )( — нечеткое число со свойством )(xFi ,iDx
где — знак линейного порядка на множестве нечетких чисел X [5–12]. Допишем
их в список S почек с оценками. Обозначим n количество S почек.
Шаг 2. Проверка: ?S Если «да» — на шаг 16. Если «нет» — на шаг 3.
Шаг 3. Выбираем произвольную почку .iD
Шаг 4. Проверяем: количество элементов iD во множестве iD равняется
единице, ?1iD Если «да» — на шаг 5. Если «нет» — на шаг 6.
Шаг 5. Имеем 1iD (точнее, это означает ),1iD разбиваем (разветвля-
ем) iD как D, переходя на шаг 1.
56 ISSN 0572-2691
Шаг 6. Одноэлементную почку назовем «листом», т.е. },{
recni xD .
rec
Dxn
Лист iD исключаем из S. Вычисляем ),(
recrec nn xFF используя операции из [5–12]
для нечетких чисел.
Шаг 7. Проверяем: ?0rec n Если «нет» (т.е. ),0rec n то переход на шаг 8,
иначе (т.е. )0rec n — на шаг 14.
Шаг 8. Присваиваем точке, которая дает рекордное значение целевой функ-
ции, точку ;0x .1rec n
Шаг 9. Задаем 1i (организовываем начало цикла перебора почек).
Шаг 10. Проверка: ?0Fi Если «да» — на шаг 12, если «нет» — на шаг 11.
Шаг 11. Почку iD исключаем из списка S. (Заметим, что при этом n не изме-
няется, оно изменяется только на шаге 1.) Это означает отсечение почки .iD
Шаг 12. Увеличиваем i на единицу, т.е. .1: ii
Шаг 13. Проверка: ?ni Если «да» — переход на шаг 2, если «нет» — пе-
реход на шаг 10.
Шаг 14. Проверка: ?0rec
FFn Если «да» — переход на шаг 2, если «нет» —
переход на шаг 15.
Шаг 15. Присваиваем текущему минимуму 0F целевой функции значение
,
recnF т.е. ,:
rec0 nFF дальше ;:
recrec nxx .1recrec nn Переход на шаг 9.
Шаг 16. Вывод результата: минимальное значение 0F целевой функции и
точка ,recx которая его доставляет. Останов.
Схема алгоритма приведена на рисунке.
Начало
0rec
n
S
Разбиение D
на почки Di
Приписывание
новым почкам Di
оценки vi
Дописывание
почки в S ,
|S |n
?S
Выбор
номера i
почки Di
|Di | 1?
in Dx :
rec
)(:
recrec nn xFF
Исключение
листа Di из S
Рассмотрение
Di как D
Останов
rec0, xF
0
1
Да
16
Нет 2
3 4 5
Да
Нет
0rec
rec
:
1:
xx
n
?0rec n
1:i
?0Fvi
Исключение
почки Di из S
(отсечение)
1: ii
?ni
rec
:0 nFF
rec
:rec nxx
1: recrec nn
6
14 7 Да Да
Да
Нет
Нет
8
9
10
11
12
13 Да
Нет
15
Нет
?0
rec
nF
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 2 57
Замечание 1. Этот алгоритм является алгоритмом МВГ вообще (т.е. для чет-
кой или нечеткой постановки задачи (1)), если определен линейный порядок
во множестве значений целевой функции (в связи с этим в действительных числах
в алгоритме имеются такие конкретизации: на шаге 14 это , на шаге 10 — <).
На эффективность МВГ существенно влияет способ ветвления допустимого
множества (шаг 1 (разбиение D на почки );iD шаг 3 — выбор )iD и оценивание
iD (определение оценки на шаге 1). В силу общности задачи нет рецептов, кото-
рые действовали бы эффективно во всех случаях. Способы ветвления, отсечения,
оценивания определяются спецификой класса задач, который рассматривается.
Отсечение происходит, как видно по алгоритму, по аналогии с классическим для
МВГ условием: если 0)( FDii не выполняется, то iD отсекается.
Решение МВГ комбинаторной транспортной задачи на перестановках
(КТЗП) в нечеткой постановке
Как известно [10, 11], КТЗП в нечеткой постановке имеет вид: найти минимум
ijij
n
j
m
i
xc
11
(2)
при следующих условиях:
iij
n
j
ax
1
,mJi (3)
jij
m
i
bx
1
,nJj (4)
).()...,,( 11 GExxx kmn (5)
Здесь ,ijc ,ia ,jb ijx — нечеткие числа [5–12], их минимум, сумма, произведение,
линейный порядок определены в [5–12], m, n, k — натуральные постоянные,
а )(GEk — множество нечетких перестановок, ,knm }...,,{ 1 kggG — муль-
тимножество возможных объемов перевозок, },...,,2,1{ mJm как и раньше, —
множество первых m натуральных чисел.
Заметим, что по экономическому содержанию задачи элементы носителей
чисел ,ijc ,ia ,jb tg положительные.
Рассмотрим способ разбиения D на почки .iD Упорядочим тарифы ijc ,
,mJi :mJj
kkiii ccc ...
2211
; (6)
переобозначив их:
**
2
*
1 ... kccc . (7)
Здесь li — номер строки, l — номер столбца транспортной таблицы, в которой
находится тариф ,*
lji cc
ll
что в упорядочении (7) расположен на l-м месте.
Пусть объемы перевозок ,jg которые составляют мультимножество
}...,,{ 1 kggG , пронумерованы согласно порядку
....21 kggg (8)
Для удобства дальнейшего изложения переобозначим это так: ,... 00
2
0
1 kggg
.0 GG
Почки образуем в таком порядке. Множество D разбивается на подмножества
согласно порядку
58 ISSN 0572-2691
1D — это подмножество D, где ;0
11 kji gx
:2D ;0
111 kji gx
…
:iD ;0
111 ikji gx
…
:kD .0
111
gx ji
Выбор номера i почек первого уровня kDD ...,,1 на шаге 3 МВГ происходит
последовательно: от 1-й до k-й.
Если выбрана почка первого уровня ,
1
DDi то на шаге 5 она рассмат-
ривается как D. Это означает следующее. Образуется разность мультимноже-
ства G и },{ 1ikg которая используется в качестве },{ 0
1
01
1
k
gGG где
}...,,{ 1
1
1
1
1
kggG , и элементы в 1G пронумерованы так: .... 1
1
1
1 kgg Образо-
вание почек второго уровня упорядочено следующим образом:
11 11
)( DD — подмножество множества ,
1
D в котором ;1
122 kji gx
22 11
)( DD — подмножество множества ,
1
D в котором ;1
222 kji gx
…
21D — подмножество множества ,
1
D в котором ;1
222
kji gx
…
:)1(1 kD .1
122
gx ji
Выбор номера 2 почек второго уровня
21D на шаге 3 МВГ осуществляет-
ся последовательно: от 12 до .12 k
Если на шаге 1 выбрана почка r-го уровня ,...21 r
D которая на шаге 5 рас-
сматривается как D, то это означает следующее. Образуется разность rG муль-
тимножеств 1rG и },{ 1
1
r
kg т.е. },{ 1
1
1
r
k
rr gGG где },...,,{ 1
r
rk
rr ggG
и элементы τG упорядочены так: ....1
r
rk
r gg
Образование почек )1( r -го уровня упорядочено следующим образом:
1...1... 2121
)(
rr
DD — подмножество ,...1 r
D когда ;r
rkji gx
rr
:)( 2...2... 2121 rr
DD ;1
r
rkji gx
rr
…
:
121 ... rr
D ;
11
r
rkji
rrr
gx
…
:)(...21 rkr
D .1
r
ji gx
rr
Ясно, что уровней почек не больше, чем k, а некоторые почки будут пусты-
ми, поскольку для них может не выполняться одно из ограничений в (3).
Замечание 2. Вместо (6)–(8) можно использовать любой линейный порядок
на множестве тарифов объемов перевозок.
Замечание 3. Легко видеть, что для нечетких чисел с дискретным носите-
лем [5–9, 12] и суммой из [5–9, 12] пустую почку можно отсекать, т.е. если
,)()( cbaba и если )}|(...,),|{( 11 ttddd tJi ,0id то
.)()( dcbaba (9)
Другими словами, если условие (3) на некотором уровне для почки не вы-
полнилось, то оно не выполнится для почек, которые образованы разбиением этой
почки (на дальнейших уровнях).
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 2 59
Оценивание допустимых подмножеств в МВГ
Опишем вычисление оценки подмножества
r
D ...21
— почки r-го уровня.
Если данные — действительные числа, свойством оценки )(D подмножества D,
которая обеспечивает работу МВГ, является следующее: если ,DDi то
).()( DDi
Теорема 1. Если },{...
21
xDDD
niii т.е. ,1
ni
D а функционал ,
который задан на множествах ,...,,
1 nii DD такой, что ),()()( xFxD
ni
),()(
1
jj ii DD ,1 nJj то значение функционала )(D может быть оценкой
допустимого подмножества в МВГ.
Доказательство. Из того, что )()(
1
jj ii DD 1 nJj и ),()()( xFxD
ni
следует )()( xFD
ji
jiDx ,nJj что и нужно доказать.
Теорема 2. Если )},|(...,),|{( 11
c
kk
c
ccc )},|(...,),|{( 11
tt g
l
t
l
gt
t ggg
где 0ic ;nJi 0t
jg ,lJj то оценкой )(D множества D в МВГ может
служить число )(CH — характеристический сравнитель [7] нечеткого числа С, где
BGx
B
jj xcC (10)
— значение части целевой функции, т.е. тех ее слагаемых, в которых определены
переменные.
Доказательство. В соответствии с формулировкой теоремы в доказательстве
нечеткие числа считаются нечеткими числами с дискретным носителем. Пусть a,
b — два таких нечетких числа (с дискретным носителем). Если ,ba то
)()( bHaH (см. утверждение 7 из [7]).
Если ,ba то cba при )}|(...,),|{( 11 kkccc и 0ic kJi
(см. теорему 2 из [12]).
Докажем, что за оценку можно взять характеристический сравнитель ).(CH
Подмножество следующего уровня в МВГ дает еще одно слагаемое в опреде-
лившуюся часть целевой функции — пусть это tgcC (заметим, что
)},|(...,),|{( 11
c
kk
c
ccc )},|(...,),|{( 11
tt g
l
t
l
gt
t ggg где 0ic ;nJi
0t
jg ).lJj
Докажем, что ).()( CCHCH Очевидно, .CCC Доказано такое
свойство характеристического сравнителя (см. утверждение 7 из [7]): если ,ba
то ),()( BHAH т.е. ),(CH где C — это (10) — «частичное» значение целевой
функции, которое определяет подмножество D, имеет свойство функционала
)()( CHD и согласно теореме 1 является оценкой подмножества D, что и нуж-
но было доказать.
Замечание 4. Рассмотренное оценивание допустимых множеств может исполь-
зоваться как при решении КТЗП, так и в общей задаче (1), поскольку не использует
конкретной постановки задачи, в частности, что D — подмножество нечетких пере-
становок [5], как в КТЗП.
Обоснование МВГ для задачи (1)
Теорема 3. Изложенный МВГ применительно к задаче (1) дает ее решение,
которым выступает 0F — значение целевой функции и recx — точка, в которой
оно достигается.
Доказательство. Согласно шагу 11 из рассмотрения исключают только поч-
ки ,iD в которых не выполняется условие .)( 0FDii
60 ISSN 0572-2691
Если ,0rec
FFn то на шаге 15 0F обновляется и стает равным ,
recnF что до-
стигается в точке .recx
Следовательно, в силу свойства оценки )()( xFD ,Dx цепочки
rec
...1 nFF и правила отсечения 0)( FDii имеем: )(
rec
xFFn ,Dx что
и нужно было доказать.
Заключение
Предложен алгоритм МВГ для задачи минимизации в нечеткой постановке.
Проиллюстрировано применение МВГ к КТЗП с нечеткими данными.
В дальнейших исследованиях целесообразно провести числовые эксперимен-
ты по этому методу для определения рамок его практического применения.
О.О. Ємець, Ол-ра О. Ємець, Т.О. Парфьонова
МЕТОД ГІЛОК ТА МЕЖ ДЛЯ ЗАДАЧ ОПТИМІЗАЦІЇ
НА НЕЧІТКИХ МНОЖИНАХ
Запропоновано алгоритм методу гілок та меж для задачі мінімізації в нечіткій
постановці. Проілюстровано застосування методу гілок та меж до комбінатор-
ної транспортної задачі на переставленнях з нечіткими даними.
O.A. Iemets, A.О. Yemets, T.A. Parfonova
BRANCH AND BOUND METHOD
FOR OPTIMIZATION PROBLEMS ON FUZZY SETS
The algorithm of branch and bound method for the minimization problem in the
fuzzy setting is proposed. The use of branch and bound method for combinatorial
transportation problem on permutations with fuzzy data is shown.
1. Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. Об одной нечеткой задаче многопара-
метрического выбора оптимальных решений // Кибернетика и системный анализ. — 2003.
— № 2. — С. 3–15.
2. Сергиенко И.В., Каспшицкая М.Ф. Применение понятий размытой математики для формализации
и решения комбинаторных оптимизационных задач // Там же. — 1995. — № 2. — С. 158–162.
3. Серая О.В. Нечеткая задача коммивояжера // Математическое моделирование. — 2007. —
№ 2 (17). — С. 13–15.
4. Роскладка А.А., Емец А.О. Решение одной комбинаторной задачи упаковки с учетом не-
определенности данных, описанной нечеткими числами // Радиоэлектроника и информати-
ка. — 2007. — № 2. — С. 132–141.
5. Ємець Ол-ра О. Одна задача упакування як комбінаторна оптимізація на нечіткій множині
розбиттів і її розв’язування // Там же. — 2007. — № 4. — С. 150–160.
6. Емец О.А., Роскладка А.А. О комбинаторной оптимизации в условиях неопределенности //
Кибернетика и системный анализ. — 2008. — № 5. — С. 35–44.
7. Ємець О.О., Ємець Ол-ра О. Операції та відношення над нечіткими числами // Наукові вісті
НТУУ «КПІ». — 2008 — № 5. — С. 39–46.
8. Ємець О.О., Ємець Ол-ра О. Побудова математичної моделі однієї комбінаторної задачі
упакування прямокутників з нечіткими розмірами // Там же. — 2008 — № 6. — С. 25–33.
9. Донец Г.А., Емец А.О. Постановка и решение задачи о рюкзаке с нечеткими данными //
Проблемы управления и информатики — 2009. — № 5. — С. 65–76.
10. Ємець О.О., Парфьонова Т.О. Транспортна задача на переставленнях та її розв’язування:
чітка та нечітка постановки. — http://www.imath.kiev.ua/~congress2009/Abstracts/Yemets.pdf.
11. Емец О.А., Парфенова Т.А. Операции над нечеткими числами с носителем мощности кон-
тинуум для моделирования в комбинаторной оптимизации // Международный научно-
технический журнал «Проблемы управления и информатики». — 2010 — № 2. — С. 86–101.
12. Ємець Ол-ра О. Деякі властивості операції суми та лінійного порядку для нечітких чисел з
дискретним носієм // Праці міжнародної молодіжної математичної школи «Питання оп-
тимізації обчислень (ПОО-XXXVII)». — Київ : ІК НАНУ, 2011. — С. 62–63.
Получено 18.10.2011
http://www.imath.kiev.ua/~congress2009/Abstracts/Yemets.pdf
|
| id | nasplib_isofts_kiev_ua-123456789-207600 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T17:38:46Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Емец, А.О. Парфенова, Т.А. 2025-10-10T10:31:51Z 2013 Метод ветвей и границ для задач оптимизации на нечётких множествах / О.А. Емец, А.О. Емец, Т.А. Парфенова // Проблемы управления и информатики. — 2013. — № 2. — С. 55–60. — Бібліогр.: 12 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207600 519.85 10.1615/JAutomatInfScien.v45.i4.30 Запропоновано алгоритм методу гілок та меж для задачі мінімізації в нечіткій постановці. Проілюстровано застосування методу гілок та меж до комбінаторної транспортної задачі на переставленнях з нечіткими даними. The algorithm of branch and bound method for the minimization problem in the fuzzy setting is proposed. The use of branch and bound method for combinatorial transportation problem on permutations with fuzzy data is shown. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Метод ветвей и границ для задач оптимизации на нечётких множествах Метод гілок та меж для задач оптимізації на нечітких множинах Branch and Bound Method for Optimization Problems on Fuzzy Sets Article published earlier |
| spellingShingle | Метод ветвей и границ для задач оптимизации на нечётких множествах Емец, О.А. Емец, А.О. Парфенова, Т.А. Оптимальное управление и методы оптимизации |
| title | Метод ветвей и границ для задач оптимизации на нечётких множествах |
| title_alt | Метод гілок та меж для задач оптимізації на нечітких множинах Branch and Bound Method for Optimization Problems on Fuzzy Sets |
| title_full | Метод ветвей и границ для задач оптимизации на нечётких множествах |
| title_fullStr | Метод ветвей и границ для задач оптимизации на нечётких множествах |
| title_full_unstemmed | Метод ветвей и границ для задач оптимизации на нечётких множествах |
| title_short | Метод ветвей и границ для задач оптимизации на нечётких множествах |
| title_sort | метод ветвей и границ для задач оптимизации на нечётких множествах |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207600 |
| work_keys_str_mv | AT emecoa metodvetveiigranicdlâzadačoptimizaciinanečetkihmnožestvah AT emecao metodvetveiigranicdlâzadačoptimizaciinanečetkihmnožestvah AT parfenovata metodvetveiigranicdlâzadačoptimizaciinanečetkihmnožestvah AT emecoa metodgíloktameždlâzadačoptimízacíínanečítkihmnožinah AT emecao metodgíloktameždlâzadačoptimízacíínanečítkihmnožinah AT parfenovata metodgíloktameždlâzadačoptimízacíínanečítkihmnožinah AT emecoa branchandboundmethodforoptimizationproblemsonfuzzysets AT emecao branchandboundmethodforoptimizationproblemsonfuzzysets AT parfenovata branchandboundmethodforoptimizationproblemsonfuzzysets |