Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ
Розглянуто точний комбінаторний метод розв’язання задачі дискретної оптимізації з дробово-лінійною функцією цілі. Побудовано алгоритм методу гілок та меж для розв’язання такої задачі. The exact combinatorical method of solving discrete optimization problem with a linear-fractional objective function...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207644 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ / О.А. Емец, О.А. Черненко // Проблемы управления и информатики. — 2013. — № 5. — С. 64-69. — Бібліогр.: 17 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859705821274832896 |
|---|---|
| author | Емец, О.А. Черненко, О.А. |
| author_facet | Емец, О.А. Черненко, О.А. |
| citation_txt | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ / О.А. Емец, О.А. Черненко // Проблемы управления и информатики. — 2013. — № 5. — С. 64-69. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розглянуто точний комбінаторний метод розв’язання задачі дискретної оптимізації з дробово-лінійною функцією цілі. Побудовано алгоритм методу гілок та меж для розв’язання такої задачі.
The exact combinatorical method of solving discrete optimization problem with a linear-fractional objective function and additional linear limitations is considered. The algorithm of branch and bound method is built for the solving of such task.
|
| first_indexed | 2025-12-01T02:49:44Z |
| format | Article |
| fulltext |
© О.А. ЕМЕЦ, О.А. ЧЕРНЕНКО, 2013
64 ISSN 0572-2691
УДК 519.8
О.А. Емец, О.А. Черненко
РЕШЕНИЕ ДИСКРЕТНЫХ ЗАДАЧ ОПТИМИЗАЦИИ
С ДРОБНО-ЛИНЕЙНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ
МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ
Введение. Большинство задач, которые исследуются в теории оптимиза-
ции [1–14], обусловлены практическими потребностями. В частности, анализируя
экономическую эффективность деятельности производства, наряду с абсолютны-
ми показателями (прибылью, валовым выпуском продукции и др.) используют
относительные, которые записываются как отношения двух других величин. В та-
ком случае в модели оптимизируется дробно-линейная функция. Некоторые зада-
чи многокритериальной оптимизации также могут быть сведены к задачам опти-
мизации с дробно-линейной целевой функцией. В связи с этим актуальными
остаются разработка методов и алгоритмов решения задач с дробно-линейной це-
левой функцией и проблема поиска более эффективных алгоритмов.
В [1, 2, 14–17] описаны методы и алгоритмы решения линейных задач опти-
мизации на дискретных множествах. Разработаны методы решения задач с дроб-
но-линейной целевой функцией, в том числе на комбинаторных множествах [5, 8, 9].
Среди большого количества разных классов оптимизационных задач задачи
дискретной оптимизации с дробно-линейной целевой функцией остаются недо-
статочно исследованными. Учитывая, что задача дробно-линейного программи-
рования отличается от задачи линейного программирования видом целевой функ-
ции, это дает возможность при сведении целевой функции к линейной использо-
вать для ее решения известные методы линейного программирования при
определенной их модификации.
Цель данной статьи — распространить метод ветвей и границ (точнее, перво-
начальный его вириант Лэнд и Дойг [16]) для решения задач дискретной оптими-
зации с дробно-линейной целевой функцией с необходимым обоснованием алго-
ритма этого метода.
Рассмотрим задачу: найти упорядоченную пару ** ,)( xxf такую, что
,max=)(max)(
0
1
0
1*
gxg
cxc
xfxf
jj
n
j
jj
n
j
RxRx nn
),(maxarg* xfx
nRx
(1)
при ограничениях
n
j
ijij bхa
1
mJi ; (2)
,}...,,,{ 21 njmjj
j
j JjdddDx
j
(3)
где ),...,,,( 21 nxxxx 0jx ,nJj iijjj bagc ,,, — действительные числа
,mJi ,nJj kJ обозначает множество первых k натуральных чисел
}....,,2,1{ k
Пусть элементы множества jD упорядочены по возрастанию:
....21 jjmjj ddd
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 5 65
Задача (1)–(3) может быть решена путем перехода к релаксированной задаче:
условие (3) ослабим, заменив его
jjmjj dxd 1 nJj . (4)
Применяя к задаче (1), (2), (4) отображение , которое зададим соотношени-
ями
,1 0
1
0 /
gxgy jj
n
j
0yxy jj ,nJj ,nRx (5)
где знаменатель не равен нулю и ,00 y перейдем к задаче с линейной функцией
цели и дополнительными линейными ограничениями: найти
,max=)(max)( 00
1
*
11
ycycyFyF jj
n
jRyRy nn
),(maxarg
1
* yFy
nRy
(6)
при условиях
00
1
ybya ijij
n
j
,mJi (7)
,100
1
ygyg jj
n
j
(8)
001 ydyyd
jjmjj ,nJj (9)
где ,)...,,,...,,,( 1
110
n
nkk Ryyyyyy 0jy }0{0 nn JJj .
Заметим, что ),(=)( ** yFxf где )( *xf — оптимальное решение зада-
чи (1)−(3), а )( *yF — задачи (6)–(9).
Как и в известных алгоритмах Гомори или Дальтона–Ллевелина, для реше-
ния задачи (1)–(3) на первом шаге предлагается не учитывать условие дискретно-
сти (3), а далее все шаги алгоритма выполнять для задачи (1), (2) и для эквива-
лентной ей линейной задачи (6)–(8).
Основная идея комбинаторных методов решения задач дискретной оптими-
зации состоит в целенаправленном переборе допустимых решений. Наиболее рас-
пространенный среди комбинаторных методов — метод ветвей и границ (МВГ).
Учитывая всеобщность МВГ, нет одного общего подхода к решению разных задач
этим методом. Способы ветвления, отсечения, оценивания определяются специ-
фикой класса задач, который рассматривается.
Способы ветвления. Пусть задано множество D — допустимая область ис-
ходной задачи (1)–(3), т.е. множество точек, которые удовлетворяют
условиям (2), (3). Обозначим )( iD оценку области .DDi Разбиение множе-
ства D на iD в процессе решения задачи осуществляется так, что выполняется
правило: ),()( DDi а именно, оценка для любого подмножества iD множе-
ства D не больше оценки для исходного множества D.
Вычисление оценок. Оценкой )( iD является значение целевой функции
в точке ,ii Dx где ix — оптимальное решение задачи (1)–(3) на множестве .iD
Заметим, что если ,12 DD то ).(max)(max
12
xfxf
DD
66 ISSN 0572-2691
Отсечение. Из рассмотрения исключаются те области ,iD для которых не
выполняется условие (3), а также для которых ,)( 0fDi где 0f — допустимое
решение исходной задачи (1)–(3).
Поиск решений. Для задачи оптимизации дробно-линейной целевой функ-
ции с дискретной областью допустимых точек используется переход к задаче ли-
нейного программирования.
Для решения задачи (1)–(3) предлагается следующий алгоритм МВГ, в осно-
ве которого лежит алгоритм Лэнд и Дойг [16]. Пусть — номер итерации. Под
итерацией будем понимать один полный цикл алгоритма.
Шаг 1. Задачу (1)–(3) свести к непрерывной: ослабить условие (3), заменив
его (4). Применить преобразование (5) к задаче (1), (2), (4), результат — зада-
ча (6)–(9).
Шаг 2. Решить линейную задачу (6)–(9).
Шаг 3. Если (6)–(9) не имеет решения, то не имеет решения и (1)–(3), иначе
пусть
1
0 )( yyx — экстремаль задачи (1), (2), (4).
Шаг 4. Если )...,,,( 21 nxxxx удовлетворяет (3), то xxf ),( — решение
задачи (1)–(3), иначе перейти на шаг 5.
Шаг 5. Определить наименьший индекс j компоненты jx точки ,x такой что
.jj Dx
Шаг 6. Записать два ограничения, которые отсекают точку :x
,1
jjmj dx (10)
,2
jjmj dx (11)
где
},),...,,,(,,{max 121
1 j
jmjjjm
j
jmjmjm
DdxxxxdDddd
jjjjj
}.),...,,,(,,min{ 121
2 j
jmjjjm
j
jmjmjm
DdxxxxdDddd
jjjjj
Шаг 7. Применить к (10), (11) преобразование (5):
,0
1 ydy
jjmj (12)
.0
2 ydy
jjmj (13)
Шаг 8. Присоединить к последней задаче вида (6)–(9) ограничение (12) и при-
менить шаги 2–4 к решению (6)–(9), (12). Если задача (6)–(9), (12) не имеет реше-
ния, перейти на шаг 9, иначе 11),( yyF — решение задачи (6)–(9), (12).
Шаг 9. Присоединить к последней задаче вида (6)–(9) ограничение (13)
и применить шаги 2–4 к решению (6)–(9), (13). Если задача (6)–(9), (13) не имеет
решения, перейти на шаг 10, иначе 22),( yyF — решение задачи (6)–(9), (13).
Шаг 10. Если никакая из задач вида (6)–(9), (12) и (6)–(9), (13) решения не
имеет, то задача (1)–(3) тоже решения не имеет в случае .1 При 1 выбрать
для дальнейшего ветвления другую область с вершиной, найденной на шаге 12
)1( -й итерации, и перейти на шаг 4.
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 5 67
Шаг 11. Если одна из задач вида (6)–(9), (12) или (6)–(9), (13) решения не
имеет, то перейти на шаг 4, считая ,)( 1
0
yyx i где i — номер точки, которая
предоставляет целевой функции наибольшее в области iD значение.
Шаг 12. Если обе задачи вида (6)–(9), (12) и (6)–(9), (13) имеют решение, то
для дальнейшего ветвления выбрать ту, которая предоставляет целевой функции
большее значение, и перейти на шаг 4, считая ,)( 1
0
yyx i где i — номер точ-
ки ,iy который предоставляет целевой функции большее с двух значений ),( jyF
.2,1j Если значения целевых функций совпадают, перейти на шаг 4 и проана-
лизировать решение каждой из задач.
Теорема 1. Алгоритм МВГ, применяемый к задаче (1)–(3), находит ее опти-
мальное решение.
Доказательство. Учитывая способы ветвления, для дальнейшего разбиения
выбирают множество iD с наибольшей оценкой, т.е. с наибольшим значением
целевой функции )(max xfD
iDx
i
, и правила отсечения (на шаге 6 алгоритма от-
секаются только те области ,iD которые не содержат точек, удовлетворяющих
условию (4)), имеем, что ).()}(max{max *xfxf
iDx
Для итераций 1 в случае,
если выбранная область iD не содержит точек с заданными дискретными коор-
динатами, используем для дальнейшего ветвления область с меньшей оценкой,
найденной на предыдущей итерации (шаг 10 алгоритма).
Теорема доказана.
Описанный алгоритм основывается на таких утверждениях. Задача (1)–(3)
является задачей дробно-линейной оптимизации, метод «линеаризации» позволя-
ет свести (1), (2), (4) к линейной задаче (6)–(9), эквивалентной ей.
Ограничения вида (12), (13), добавляемые к задаче (6)–(9), являются обра-
зами (10), (11) при применении отображения (5), которое имеет свойство инъектив-
ности и суръективности [8]. Применив к условию (3) отображение (5), получим
},...,,,{ 00201 ydydydEy
jjmjj
j
j ,
1nJj .1 nn (14)
Таким образом, учитывая, что (10), (11) по построению не отсекают никакое
допустимое решение задачи (1)–(3), их образы — ограничения (12), (13) — также
не отсекают никакой точки множества решений задачи (6)–(9), (14), которая явля-
ется образом (1)–(3).
Теорема 2. Ограничения (12), (13) не отсекают никакой точки
)...,,,( 10 nyyyy , для которой
1nJj jy удовлетворяет (14).
Рассмотрим илюстративный пример.
Пример. Оптимизировать функцию max
2
25
21
21
xx
xx
при линейных ограни-
чениях ,1232 21 xx ,62 21 xx 822 21 xx и при условиях дискретности,
а именно: ,}12,9,8,5,4,2{1
1 Dx }.10,6,4,2,1{2
2 Dx
Решение.
1. Не учитывая условия дискретности, «линеаризируем» исходную задачу,
используя преобразование (5), получим: max25 21 yy при ограничениях
,01232 021 yyy ,062 021 yyy ,0822 021 yyy .12 21 yy
2, 3. Решая линейную задачу, получим ,
13
1
,
13
6
,
52
5
y откуда .
5
4
,
5
24
x
4. Учитывая, что
1
1 Dx и ,2
2 Dx переходим на шаг 5.
68 ISSN 0572-2691
5. Наименьший индекс точки ,x такой что ,jj Dx равен 1, т.е. .1j
6. Записываем два ограничения, которые отсекают точку :x ,41 x ,51 x
учитывая, что
44,
5
24
,max 1
1
1
11
1
1 1111
DdDddd mmmm
,
.55,
5
24
,min 1
1
1
11
2
1 1111
DdDddd mmmm
Применяя к ограничениям ,41 x 51 x преобразование (5), получаем ,04 01 yy
.05 01 yy
7. К линейной задаче шага 1 добавляем ограничение 04 01 yy и решаем
ее: ,
7
13
)( 1 yF .
3
4
,41
x
8. К линейной задаче шага 1 добавляем ограничение 05 01 yy и решаем
ее: ,
11
23
)( 2 yF ).1,5(2 x
9. Учитывая, что ,
11
23
7
13
для дальнейшего ветвления выбираем вторую за-
дачу и переходим на шаг 4 алгоритма.
Поскольку )1,5(2 x удовлетворяет условиям дискретности, точка )1,5(2 x
и будет оптимальным решением исходной задачи. Таким образом, )1,5(,
11
23
—
решение.
Заключение. В настоящей работе предложен и обоснован метод в рамках
схемы метода ветвей и границ для решения задач оптимизации дробно-линейной
целевой функции с дискретными параметрами и линейными ограничениями.
В дальнейшем представляется целесообразным применить данный подход
к решению задач оптимизации с дробно-линейной функцией цели на других мно-
жествах, в частности комбинаторных.
О.О. Ємець, О.О. Черненко
РОЗВ’ЯЗАННЯ ДИСКРЕТНИХ ЗАДАЧ
ОПТИМІЗАЦІЇ З ДРОБОВО-ЛІНІЙНОЮ ЦІЛЬОВОЮ
ФУНКЦІЄЮ МЕТОДОМ ГІЛОК ТА МЕЖ
Розглянуто точний комбінаторний метод розв’язання задачі дискретної оптимі-
зації з дробово-лінійною функцією цілі. Побудовано алгоритм методу гілок та
меж для розв’язання такої задачі.
O.A. Iemets, O.A. Chernenko
THE SOLVING OF DISCRETE OPTIMIZATION
PROBLEMS WITH LINEAR-FRACTIONAL OBJECTIVE
FUNCTION BY BRANCH AND BOUND METHOD
The exact combinatorical method of solving discrete optimization problem with
a linear-fractional objective function and additional linear limitations is considered.
The algorithm of branch and bound method is built for the solving of such task.
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 5 69
1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных за-
дач оптимизации. — Киев : Наук. думка, 1981. — 288 с.
2. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных
задач оптимизации. — Киев : Наук. думка, 1980. — 266 с.
3. Cтоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Київ :
Інститут системних досліджень освіти, 1993. — 188 с.
4. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимізація на полірозміщеннях: теорія та методи.
— Полтава : РВЦ ПУСКУ, 2005. — 103 с.
5. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними
цільовими функціями. — Київ : Наук. думка, 2005. — 117 с.
6. Ємець О.О., Роскладка О.В. Задачі оптимізації на полікомбінаторних множинах: власти-
вості та розв’язування. — Полтава : РВЦ ПУСКУ, 2006. — 144 с.
7. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. — Киев : Наук.
думка, 2008. — 159 с.
8. Емец О.А., Черненко О.А. Оптимизация дробно-линейных функций на размещениях. —
Киев : Наук. думка, 2011. — 154 с.
9. Емец О.А., Романова Н.Г. Оптимизация на полиперестановках. — Киев : Наук. думка,
2010. — 105 с.
10. Ємець О.О., Ємець Ол-ра О. Розв’язування задач комбінаторної оптимізації на нечітких
множинах: — Полтава : ПУЕТ, 2011. — 239 с.
11. Емец О.А., Парфёнова Т.А. Транспортные задачи на перестановках: свойства оценок в ме-
тоде ветвей и границ // Кибернетика и системный анализ. — 2010. —№ 6. — С. 106–112.
12. Ємець О.О., Ємець Є.М., Парфьонова Т.О., Чілікіна Т.В. Лінійні умовні задачі комбінатор-
ної оптимізації на переставленнях та їх розв’язування // Штучний інтелект. — 2011. — №
2. — С. 131–135.
13. Ємець О.О., Парфьонова Т.О. Транспортні задачі комбінаторного типу: властивості,
розв’язування, узагальнення: монографія. — Полтава : ПУЕТ, 2011. — 174 с.
14. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. — М. : Наука, 1969. —
368 с.
15. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Метод ветвей и границ: обзор теории, алго-
ритмов, программ и приложений // Math. Operationsch und Statist., Ser. Optimiz. — 1977. —
N 2. — P. 253–280.
16. Land A.H., Doig A.G. An autmatic method of solving discrete programming problems // Econo-
metrica. — 1960. — 28. — Р. 497–520.
17. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное про-
граммирование. — Киев : Вища шк., 1975. — 372 с.
Получено 27.03.2012
|
| id | nasplib_isofts_kiev_ua-123456789-207644 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-01T02:49:44Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Черненко, О.А. 2025-10-11T10:40:22Z 2013 Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ / О.А. Емец, О.А. Черненко // Проблемы управления и информатики. — 2013. — № 5. — С. 64-69. — Бібліогр.: 17 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207644 519.8 10.1615/JAutomatInfScien.v45.i9.70 Розглянуто точний комбінаторний метод розв’язання задачі дискретної оптимізації з дробово-лінійною функцією цілі. Побудовано алгоритм методу гілок та меж для розв’язання такої задачі. The exact combinatorical method of solving discrete optimization problem with a linear-fractional objective function and additional linear limitations is considered. The algorithm of branch and bound method is built for the solving of such task. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ Розв’язання дискретних задач оптимізації з дробово-лінійною цільовою функцією методом гілок та меж Solving of discrete problems of optimization with linear-fractional objective function by branch and bound methods Article published earlier |
| spellingShingle | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ Емец, О.А. Черненко, О.А. Оптимальное управление и методы оптимизации |
| title | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ |
| title_alt | Розв’язання дискретних задач оптимізації з дробово-лінійною цільовою функцією методом гілок та меж Solving of discrete problems of optimization with linear-fractional objective function by branch and bound methods |
| title_full | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ |
| title_fullStr | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ |
| title_full_unstemmed | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ |
| title_short | Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ |
| title_sort | решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207644 |
| work_keys_str_mv | AT emecoa rešeniediskretnyhzadačoptimizaciisdrobnolineinoicelevoifunkcieimetodomvetveiigranic AT černenkooa rešeniediskretnyhzadačoptimizaciisdrobnolineinoicelevoifunkcieimetodomvetveiigranic AT emecoa rozvâzannâdiskretnihzadačoptimízacíízdrobovolíníinoûcílʹovoûfunkcíêûmetodomgíloktamež AT černenkooa rozvâzannâdiskretnihzadačoptimízacíízdrobovolíníinoûcílʹovoûfunkcíêûmetodomgíloktamež AT emecoa solvingofdiscreteproblemsofoptimizationwithlinearfractionalobjectivefunctionbybranchandboundmethods AT černenkooa solvingofdiscreteproblemsofoptimizationwithlinearfractionalobjectivefunctionbybranchandboundmethods |