Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ

Розглянуто точний комбінаторний метод розв’язання задачі дискретної оптимізації з дробово-лінійною функцією цілі. Побудовано алгоритм методу гілок та меж для розв’язання такої задачі....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автори:	Емец, О.А., Черненко, О.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 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

id	irk-123456789-207644
record_format	dspace
spelling	irk-123456789-2076442025-10-12T00:09:06Z Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ Розв’язання дискретних задач оптимізації з дробово-лінійною цільовою функцією методом гілок та меж Solving of discrete problems of optimization with linear-fractional objective function by branch and bound methods Емец, О.А. Черненко, О.А. Оптимальное управление и методы оптимизации Розглянуто точний комбінаторний метод розв’язання задачі дискретної оптимізації з дробово-лінійною функцією цілі. Побудовано алгоритм методу гілок та меж для розв’язання такої задачі. 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 Article Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ / О.А. Емец, О.А. Черненко // Проблемы управления и информатики. — 2013. — № 5. — С. 64-69. — Бібліогр.: 17 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207644 519.8 10.1615/JAutomatInfScien.v45.i9.70 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Емец, О.А. Черненко, О.А. Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ Проблемы управления и информатики
description	Розглянуто точний комбінаторний метод розв’язання задачі дискретної оптимізації з дробово-лінійною функцією цілі. Побудовано алгоритм методу гілок та меж для розв’язання такої задачі.
format	Article
author	Емец, О.А. Черненко, О.А.
author_facet	Емец, О.А. Черненко, О.А.
author_sort	Емец, О.А.
title	Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ
title_short	Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ
title_full	Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ
title_fullStr	Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ
title_full_unstemmed	Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ
title_sort	решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207644
citation_txt	Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ / О.А. Емец, О.А. Черненко // Проблемы управления и информатики. — 2013. — № 5. — С. 64-69. — Бібліогр.: 17 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT emecoa rešeniediskretnyhzadačoptimizaciisdrobnolinejnojcelevojfunkciejmetodomvetvejigranic AT černenkooa rešeniediskretnyhzadačoptimizaciisdrobnolinejnojcelevojfunkciejmetodomvetvejigranic AT emecoa rozvâzannâdiskretnihzadačoptimízacíízdrobovolíníjnoûcílʹovoûfunkcíêûmetodomgíloktamež AT černenkooa rozvâzannâdiskretnihzadačoptimízacíízdrobovolíníjnoûcílʹovoûfunkcíêûmetodomgíloktamež AT emecoa solvingofdiscreteproblemsofoptimizationwithlinearfractionalobjectivefunctionbybranchandboundmethods AT černenkooa solvingofdiscreteproblemsofoptimizationwithlinearfractionalobjectivefunctionbybranchandboundmethods
first_indexed	2025-10-12T01:13:10Z
last_indexed	2025-10-13T01:11:57Z
_version_	1845827120819863552
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  0jx ,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 0jy }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,1j Если значения целевых функций совпадают, перейти на шаг 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, т.е. .1j 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

Решение дискретных задач оптимизации с дробно-линейной целевой функцией методом ветвей и границ

Репозитарії

Схожі ресурси