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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2017
Автори:	Емец, О.А., Барболина, Т.Н.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/208369
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Свойства комбинаторных оптимизационных безусловных задач на размещениях с линейной и дробно-линейной целевыми функциями / О.А. Емец, Т.Н. Барболина // Проблемы управления и информатики. — 2017. — № 1. — С. 66-76. — Бібліогр.: 15 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208369
record_format	dspace
spelling	irk-123456789-2083692025-10-27T01:06:35Z Свойства комбинаторных оптимизационных безусловных задач на размещениях с линейной и дробно-линейной целевыми функциями Властивості комбінаторних оптимізаційних безумовних задач на розміщеннях з лінійною і дробово-лінійною цільовими функціями Properties of combinatorial optimization unconditional problems on arrangements with linear and linear-fractional objective functions Емец, О.А. Барболина, Т.Н. Оптимальное управление и методы оптимизации Розглянуто властивості безумовних евклідових задач комбінаторної оптимізації на розміщеннях з лінійною і дробово-лінійною цільовими функціями. Показано, що будь-яка екстремаль у лінійній задачі є елементом певної множини полірозміщень. Для задач із дробово-лінійною цільовою функцією обгрунтовано спосіб формування множини всіх екстремалей, якщо відома одна з них. The properties of unconditional combinatorial optimization problems on a set of arrangements with linear and linear-fractional objective functions are considered. We prove that in linear problem any extremal is an element of certain set of polyarrangements. Also we substantiate how to construct the set of extremals in a problem with linear-fractional objective function when one of extremals is know. 2017 Article Свойства комбинаторных оптимизационных безусловных задач на размещениях с линейной и дробно-линейной целевыми функциями / О.А. Емец, Т.Н. Барболина // Проблемы управления и информатики. — 2017. — № 1. — С. 66-76. — Бібліогр.: 15 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208369 519.85 10.1615/JAutomatInfScien.v49.i1.40 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	2017
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/208369
citation_txt	Свойства комбинаторных оптимизационных безусловных задач на размещениях с линейной и дробно-линейной целевыми функциями / О.А. Емец, Т.Н. Барболина // Проблемы управления и информатики. — 2017. — № 1. — С. 66-76. — Бібліогр.: 15 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT emecoa svojstvakombinatornyhoptimizacionnyhbezuslovnyhzadačnarazmeŝeniâhslinejnojidrobnolinejnojcelevymifunkciâmi AT barbolinatn svojstvakombinatornyhoptimizacionnyhbezuslovnyhzadačnarazmeŝeniâhslinejnojidrobnolinejnojcelevymifunkciâmi AT emecoa vlastivostíkombínatornihoptimízacíjnihbezumovnihzadačnarozmíŝennâhzlíníjnoûídrobovolíníjnoûcílʹovimifunkcíâmi AT barbolinatn vlastivostíkombínatornihoptimízacíjnihbezumovnihzadačnarozmíŝennâhzlíníjnoûídrobovolíníjnoûcílʹovimifunkcíâmi AT emecoa propertiesofcombinatorialoptimizationunconditionalproblemsonarrangementswithlinearandlinearfractionalobjectivefunctions AT barbolinatn propertiesofcombinatorialoptimizationunconditionalproblemsonarrangementswithlinearandlinearfractionalobjectivefunctions
first_indexed	2025-10-27T02:08:58Z
last_indexed	2025-10-28T02:28:18Z
_version_	1847370604930400256
fulltext	© О.А. ЕМЕЦ, Т.Н. БАРБОЛИНА, 2017 66 ISSN 0572-2691 УДК 519.85 О.А. Емец, Т.Н. Барболина СВОЙСТВА КОМБИНАТОРНЫХ ОПТИМИЗАЦИОННЫХ БЕЗУСЛОВНЫХ ЗАДАЧ НА РАЗМЕЩЕНИЯХ С ЛИНЕЙНОЙ И ДРОБНО-ЛИНЕЙНОЙ ЦЕЛЕВЫМИ ФУНКЦИЯМИ Введение Среди задач комбинаторной оптимизации, которые привлекают внимание исследователей (см., например, [1–14]), важный класс составляют задачи на евклидовых комбинаторных множествах. В [5–14] и других работах исследова- ны свойства комбинаторных и поликомбинаторных множеств, а также различных классов оптимизационных задач на таких множествах. В частности, для общего множества размещений получена несводимая система ограничений его выпуклой оболочки [13], предложены методы решения линейных и некоторых классов нели- нейных задач [6–8], сформулировано достаточное условие решения линейной безус- ловной задачи [6]. Исследование безусловных задач продолжено в [14], где получен критерий экстремали линейной безусловной задачи оптимизации на размещениях для положительных коэффициентов целевой функции. Данная статья посвящена обосно- ванию такого критерия в общем случае, а также исследованию безусловных задач оптимизации дробно-линейной функции. Критерий экстремали линейной безусловной задачи оптимизации на размещениях Введем необходимую терминологию и обозначения относительно общего множества размещений [6]. Под мультимножеством понимаем совокупность эле- ментов, среди которых могут быть и одинаковые. Любое мультимножество }...,,{ 1  ggG можно задать его основой ),(GS т.е. кортежем всех его различ- ных элементов, и кратностью — числом повторов каждого элемента основы. Кор- теж кратностей называют первичной спецификацией и обозначают G. Упорядо- ченной k -выборкой из мультимножества }...,,{ 1  ggG называется набор, ),...,,( 1 kii gg где ,Gg ji  ,,  Jiiii tjtj kJtj  , (здесь и далее nJ обозна- чает множество n первых натуральных чисел). Множество всех упорядоченных k - выборок из мультимножества G называют общим множеством размещений ).(GEk  Рассмотрим сначала решение линейной безусловной задачи комбинаторной оптимизации на размещениях в следующей постановке: найти пару  *),( xxL такую, что ,extr)( 1)(     k j jj GEx xcxL k ,extrarg 1)( *     k j jj GEx xcx k (1) где k k Rxxx  )...,,( 1 , 1Rc j  ,kJj )(GEk  — общее множество размеще- ний из элементов мультимножества },...,,{ 1  ggG причем элементы мульти- множества удовлетворяют условию ....1  gg (2) Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 1 67 Также будем полагать, что коэффициенты целевой функции    k j jj xcxL 1 )( упорядочены по невозрастанию, причем мультимножество }...,,,{ 21 kccc имеет основу )...,,( 1 scc и первичную спецификацию )....,,( 1 stt Обозначим ,11 t     i j jiii tttt 1 1 1 для ,sJi тогда выполняются соотношения ............. 11 3221 kttttt cccccc s   (3) Как известно [6], множество вершин выпуклой оболочки множества )(GEk  — общего многогранника размещений )(Gk  — является подмножест- вом множества )(GEk  . При этом точка )(Gx k  будет вершиной общего мно- гогранника размещений тогда и только тогда, когда ее компоненты являются пе- рестановками чисел ,...,,,...,, 11  gggg rp где ,, 0 kJrp  krp  (здесь и далее для целых n и k })....,,1,{ knnJ n k  Согласно критерию смежности вершин общего многогранника размещений [6] вершина x смежна с вершиной ,x если она получена из вершины x перестановкой компонент, равных элементам 1, tt gg 1(  tt gg ,1 pJt ), 1 1   r Jt или заменой pg (или )1 rg на rg  (или 1pg соответственно) при условии rp gg  ),( 11   pr gg ,, 0 kJrp  .krp  Теорема 1. Пусть для смежных вершин x и x общего многогранника раз- мещений выполняются соотношения )()( xLxL  и .ii xx  Тогда выполняется по крайней мере одно из двух условий: 1) ;0jc 2) вершина x получена из x перестановкой компонент ti gx  и 1 tq gx ),( 1 tt gg причем qi cc  ,,( kJqi  ).1 Jt Доказательство. Пусть для смежных вершин x и x общего многогранника размещений выполняются условия )()( xLxL  и .ii xx  Если вершина x получена из x заменой pi gx  на ri gx  ),( rp gg  то ),()()()()()( 11 rpirpi k ij j jjj k j jjj ggcggcxxcxxcxLxL      так как jj xx  ij  .kJj Следовательно, в этом случае (замены координат) )()( xLxL  только при .0ic Такой же результат получается, если 1 ri gx заменяется на .11   rpi ggx Если вершина x получена из x перестановкой компонент ti gx  и 1 tq gx ),( 1 tt gg то ).()()()()()()( ; 1 qqqiiiqqqiii k qjij j jjj xxcxxcxxcxxcxxcxLxL     68 ISSN 0572-2691 Поскольку ,qi xx  ,iq xx  то равенство )()( xLxL  равносильно .0))((  qiii ccxx Учитывая, что ,ii xx  получаем .qi cc  Теорема доказана. Отметим, что если для смежных вершин x и x общего многогранника размещений выполняются соотношения ),()( xLxL  ii xx  и ,0ic то в соответствии с теоремой 1 вершина x получена из x перестановкой компонент ti gx  и 1 tq gx ).( 1 tt gg Обозначим }.0\|{  wts cJwW Следствие 1. Если для смежных вершин x и x общего многогранника размещений выполняется условие ),()( xLxL  то для всех Ww мультимножества }...,,{ 11  ww tt xx и },...,{ 11ww tt xx равны между собой. Пусть точки x и x — минимали (максимали) в задаче (1). Это означает, что найдется последовательность вершин 21 ...,, xxxxx r  таких, что 1, ii xx )( 1 rJi — смежные вершины и ).(...)( 1 rxLxL  Согласно следствию 1 из теоремы 1 для всех ,Ww 1 rJi имеют место равенства мультимножеств }...,,{ 11 i t i t ww xx  и }....,,{ 1 1 1 1     i t i t ww xx Следовательно,   }...,,{ 11ww tt xx }...,,{ * 1 * 1  ww tt xx для всех .Ww Иными словами, ),()...,,( 11 w ttt GExx www   где },,...,{ * 1 * 1  ww tt w xxG ,\|\| 1 www w tttG   а )( w t GE w — множество перестановок элементов мультимножества .wG Поскольку ),(GEx k  то для sJv такого, что 0 vt c )...,,( 11  vv tt xx является vt -выборкой из мультимножества    Ww wv GGG (операции над мультимножествами рассмотрены, например, в [15]). Таким образом, ),()...,,( 11 vt ntt GExx v vvv   где . 1 vv s w w Ww w v v tktttGn    Полученный результат целесообразно сформулировать с использованием понятия полиразмещения, которое определим в соответствии с [9]. Пусть }...,,{ 1  ggG — мультимножество, содержащее n различных элементов. Рассмотрим упорядоченное разбиение J на s множеств ,...,,1 sNN удовлетворяющее условиям ,,  iji NNN  ,jN ,, sJji  а также упорядоченное разбиение числа k на s слагаемых ,...,,1 skk удовлетворяющее условиям ii nk 1 ,pJi где .\|\| ii Nn  Очевидно, что  21 nn ,... sn ....21 skkkk  Пусть H — множество всех k -выборок из множества J вида ),...,,()...,,...,,...,,())(...,),1(( 1 1111 1 s sksk s k  (4) где )...,,( 1 iiki i  — произвольная ik -выборка из множества si JiN  . Множество }\|)...,,{(),( )()1( HggHGЕ k ks n   называют общим множеством полиразмещений. Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 1 69 Вернемся к рассмотрению свойств экстремалей линейной безусловной задачи комбинаторной оптимизации на размещениях. Пусть )...,,( 1 kll ggx  — экстремаль (для определенности — минималь) в задаче (1). Рассмотрим разбиение множества J на s множеств sNN ...,,1 таким образом:            .0 если ,\ ; если },,...,{ 11 w ww tv Wv tt w cNJ Wwll N  (5) Легко видеть, что ,,  iji NNN  ,jN ., sJji  Рассмотрим также разбиение числа k на s слагаемых: ....1 sttk  С учетом введенных обозначений }\|{ wj w NjGgG  для всех .sJw Следовательно, любая ми- нималь в задаче (1) удовлетворяет условию ),,(* HGEx ks n где H — множество всех k -выборок из J вида (4), множества wN определяются согласно (5). Пусть теперь для точки )(* GEx k  выполняется условие ),(* HGEx ks n . Тогда ),( )( 1 1 11 * 1 1 * 1 ** 1 111 xLxc xcxcxcxcxL s w t tj jt Ww t tj jt Ww t tj jt s w t tj jt k j jj w w w w w w w w w w w w                                                         т. е. x — минималь в задаче (1). Таким образом, доказана следующая теорема. Теорема 2. Пусть точка )...,,( 1 kll ggx  — минималь (максималь) в за- даче (1), множества wN sJw определяются согласно (5), разбиение числа k на слагаемые имеет вид ....1 sttk  Точка x также является минималью (максималью) в задаче (1) тогда и только тогда, когда ),,(* HGEx ks n где H — множество выборок вида (4). Пример 1. Пусть },9,8,7,7,7,3,3,2{G 754321 233)( xxxxxxxL  . Одной из минималей функции )(xL на множестве )(7 8 GE является точка x ).9;8;7;7;3;3;2( Используя теорему 2, найдем остальные минимали. Сначала сформируем множества (5). Так как ,7654321 ccccccc  то ,21 t ,32 t ,143  tt ,11 t ,3112  ttt ,63 t ,74 t .85 t Поскольку также ,063  cct то }.4,2,1{W Учитывая, что ;;;;;( 54321 gggggx  ),; 87 gg получаем },2,1{1 N },5,4,3{2 N },8{4 N }.7,6{}8,5,4,3,2,1{\83  JN Поскольку разбиение числа k на слагаемые имеет вид ,1132 k то множество H формируется в виде ),8;7;3;4;5;2;1(),8;6;3;4;5;2;1(),8;7;4;3;5;2;1(),8;6;4;3;5;2;1( ),8;7;3;5;4;2;1(),8;6;3;5;4;2;1(),8;7;5;3;4;2;1(),8;6;5;3;4;2;1( ),8;7;4;5;3;2;1(),8;6;4;5;3;2;1(),8;7;5;4;3;2;1(),8;6;5;4;3;2;1{(H 70 ISSN 0572-2691 )}.8;7;3;4;5;1;2(),8;6;3;4;5;1;2(),8;7;4;3;5;1;2(),8;6;4;3;5;1;2( ),8;7;3;5;4;1;2(),8;6;3;5;4;1;2(),8;7;5;3;4;1;2(),8;6;5;3;4;1;2( ),8;7;4;5;3;1;2(),8;6;4;5;3;1;2(),8;7;5;4;3;1;2(),8;6;5;4;3;1;2( Учитывая, что для некоторых элементов множества H соответствующие элементы )...,,( )()1( kgg  множества полиразмещений равны (например, ;;( 21 gg ),9;7;7;7;3;3;2();;;;;;();;;; 864532186543  gggggggggggg получаем следую- щее множество полиразмещений :),( 4,7 5,8 HGE )}.9;8;3;7;7;2;3(),9;7;3;7;7;2;3(),9;8;7;3;7;2;3(),9;7;7;3;7;2;3( ),9;8;7;7;3;2;3(),9;7;7;7;3;2;3(),9;8;3;7;7;3;2(),9;7;3;7;7;3;2( ),9;8;7;3;7;3;2(),9;7;7;3;7;3;2(),9;8;7;7;3;3;2(),9;7;7;7;3;3;2{( ),( 4,7 5,8  HGE В соответствии с теоремой 2 это множество является множеством минималей функции )(xL на множестве ).(7 8 GE Если среди коэффициентов целевой функции нет равных, то 1jt ,sJj а значит, каждая координата экстремали определяется однозначно и имеет место следствие из теоремы 2. Следствие 1. Если для коэффициентов целевой функции в задаче (1) выполняется условие ,...21 kccc  то задача (1) имеет единственное решение. Отметим, что если 0jc ,kJj то sJW  и ww tN \|\| ,sJw поэтому множество ),( HGEks n является множеством полиперестановок [6, 9] ),,( 1 1 HGE s kn где },...,,{ 11 kll ggG  .11 Gn  Пусть для элементов мультимножества и коэффициентов целевой функции выполняются неравенства (2) и (3) соответственно, причем .0kc Тогда, как показано в [14], одной из минималей в задаче (1) является точка ),...,,,( 21 kggg а одной из максималей — точка )....,,,( 11  kggg Следовательно, для минимали )...,,( 1 * kll ggx  имеем jl j  kJj и, учитывая, что ,sJW  вследствие 0jc kJj получаем следующий вид множеств (5): wN }1...,,{ 1  ww tt .sJw Для максимали имеем 1 jl j ,kJj в частности ,1 wt tl w .2111   wt tl w Следовательно, множества (5) запишем ...,2{ 1  ww tN }1...,  wt .sJw Таким образом, справедлива следующая лемма. Лемма 1. Пусть для элементов мультимножества G и коэффициентов целевой функции в задаче (1) выполняются условия (2) и (3) соответственно, причем .0kc Точка x является экстремалью в задаче (1) тогда и только тогда, когда ),,( 1 1 HGEx s kn  где:  H — множество перестановок из множества kJ вида (4), ;...1 sttk   }1,...,{ 1  www ttN ,sJw }...,,{ 11 kggG  в задачах минимизации; Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 1 71  }1...,,2{ 1   www ttN ,sJw },...,{ 11  ggG k в задачах максимизации. Рассмотрим теперь решение задачи (1), если .01 c Лемма 2. Пусть для элементов мультимножества и коэффициентов целевой функции в задаче (1) выполняются условия (2) и (3) соответственно, причем .01 c Точка x является экстремалью в задаче (1), если и только если ),( 1 1 HGEx s kn  :  H — множество перестановок из множества kJ вида (4), ;...1 sttk   }1,...,{ 1  www tktkN ,sJw }...,,{ 11  ggG k в задачах минимизации;  }1,...,2{ 1   www tktkN ,sJw }...,,{ 11 kggG  в задачах макси- мизации. Доказательство. Рассмотрим сначала задачу в случае минимизации целевой функции. Она эквивалентна задаче поиска пары  ** ~),~( ~ xxL такой, что ,~~max)~( ~ 1)(~ *     k j jj GEx xcxL k .~~maxarg~ 1)(~ *     k j jj GEx xcx k (6) Зеcь ,~ 1 jkj xx а коэффициенты функции    k j jj xcxL 1 ~~)~( ~ определяются так: .~ 1 jkj cc Поскольку коэффициенты функции )(xL удовлетворяют условию (3), то 1... cck  и коэффициенты функции )~( ~ xL упорядочены по невозрастанию. Значит, одна из максималей функции )~( ~ xL на )(GEk  определяется соотношениями .~ 1 *  jj gx Тогда одна из минималей в задаче (1) удовлетворяет условиям .~* 1 jkjkj gxx   Таким образом, множества (5) принимают вид }1...,,{ 1  www tktkN Ww sJW ( вследствие ,01 c т.е. 0jc ),kJj }....,,{ 11  ggG k Из теоремы 2 следует, что любая минималь в задаче (1) удовлетворяет условию ),,( 1 * 1 HGEx s kn  где }1...,,{ 1  www tktkN ,sJw }....,,{ 11  ggG k В случае задачи максимизации целевой функции аналогично получаем, что одна из экстремалей удовлетворяет условию ,1 jkj gx а значит, }1...,,2{ 1   www tktkN ,sJw }....,,{ 11 kggG  Лемма доказана. Теорема 3. Пусть элементы мультимножества G в задаче (1) удовлетворяют условию (2), а коэффициенты целевой функции — условию (3). Точка x является минималью в задаче (1) тогда и только тогда, когда она удовлетворяет условию ),,( HGEx ks n где H — множество k -выборок из множества J вида (4), при формировании которых ,...1 sttk  а множества wN определяются следующим образом: 72 ISSN 0572-2691                  w t tww tww w w w w cNJ ctktk сtt N .0если,\ ,0если},1....,,{ 0если},1...,,{ 1 ,1 (7) Доказательство. Пусть r — наибольший индекс такой, что ,0 rt c а q — наименьший индекс такой, что .0 qt c В соответствии с леммами 1 и 2 для любой точки )()...,,( 1 GExxx k k  выполняются условия        1 1 1 1 11 rr t j jj t j jj gcxc и ,     k tj jkj k tj jj qq gcxc отсюда        1 1 1 11 11 r q r t j jj k tj jj t j jj k j jj gcxcxcxc .   k tj jkj q gc Таким образом, точка ,x удовлетворяющая условиям jj gx  ,11  rt Jj jkj gx  ,qt k Jj является минималью в задаче (1). Тогда в соответствии с теоремой 1 точка x является минималью в задаче (1), если и только если ),,( HGEx ks n где H — множество k -выборок из множества sJ вида (4), wN определяются согласно (7). Пример 2. Рассмотрим задачу минимизации функции  21 33)( xxxC 8763 2xxxx  на множестве ),(GEk  где }.10,10,10,5,5,5,5,2,2,2,1{G Так как мультимножество коэффициентов функции )(xC имеет вид ,1,3,3{ },2,1,1,0,0  то ,11 t ,32 t ,43 t ,64 t ,85 t .96 t Учитывая, что ,0 1 tc ,0 2 tc ,0 3 tc ,0 4 tc сформируем множества (7): },2,1{1 N },3{2 N },10,9{4 N },11{5 N }.8,7,6,5,4{}11,10,9,3,2,1{\113  JN Поскольку 2g ,243  gg ,8765 gggg  ,1011109  ggg то множество полиразмещений )}.10;10;10;2;5;2;1;2(),10;10;10;5;2;2;1;2( ),10;10;10;2;5;2;2;1(),10;10;10;5;2;2;2;1{(),( 5,8 4,11  HGE На основе теоремы 3 получаем, что минималями функции )(xL на множестве )(GEk  являютя точки ),10;10;10;5;2;2;2;1( ),10;10;10;2;5;2;2;1( ;2;1;2(  ),10;10;10;5;2 ).10;10;10;2;5;2;1;2(  Соответствующее значение целевой функ- ции равно –35. Аналогичная теорема имеет место и в случае максимизации. Теорема 4. Пусть элементы мультимножества в задаче (1) удовлетворяют условию (2), а коэффициенты целевой функции — условию (3). Точка x является максималью в задаче (1), если и только если она удовлетворяет условию ),,( HGEx ks n где H — множество k -выборок из множества J вида (4), при формировании которых ,...1 sttk  а множества wN определяются следующим образом: Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 1 73                   w t tww tww w w w w cNJ сtktk сtt N .0если,\ ,0если},1,...,2{ ,0если},1,...,2{ 1 1 Пример 3. Рассмотрим задачу максимизации функции  21)( xxxL 7654 4222 xxxx  на множестве ),(GEk  где }.10,10,8,5,5,2,2,2,3{G Учитывая, что ,11 t ,32 t ,43 t ,74 t ,85 t причем ,0 2 tc имеем, что }9,8{1 N ),91,82( 12  tt }4,3,2{3 N ),41,22( 34  tktk },1{4 N }.7,6,5{}9,8,4,3,2,1{\92  JN Так как множество полиразмещений )},3;2;2;2;8;10;10(),3;2;2;2;5;10;10{(),( 4,7 5,9 HGE то согласно теореме 4 максималями функции )(xL на множестве )(GEk  являются точки ;5;10;10( )3;2;2;2  и ).3;2;2;2;8;10;10(  Соответствующее значение целевой функции равно 20. Свойства безусловной задачи оптимизации дробно-линейной функции на размещениях Используя критерий экстремали в линейной безусловной задаче оптимизации на размещениях, рассмотрим возможность получения всех экстремалей для дробно-линейных задач. Для нахождения одной из таких экстремалей x может использоваться аналитический метод, предложенный в [8]. Он позволяет также определить экстремали, являющиеся смежными вершинами с ,x однако не дает ответа на вопрос о существовании иных экстремалей. Рассмотрим безусловную задачу комбинаторной оптимизации на разме- щениях с дробно-линейной целевой функцией ,)( 0 1 0 1 dxd cxc x k j jj k j jj        т.е. задачу поиска пары  *),( xx такой, что ;extr)( 0 1 0 1 )( dxd cxc x k j jj k j jj GEx k          .extrarg 0 1 0 1 )( * dxd cxc x k j jj k j jj GEx k          (8) Будем считать, что для любой точки )(GEx k  справедливо неравенство .00 1   dxd k j jj Пусть  *, x — решение задачи (8). Для определенности рассмотрим случай минимизации. Тогда для любой точки )(GEx k  имеет место неравенство 74 ISSN 0572-2691 . 0 1 0 1        dxd cxc k j jj k j jj (9) Вместе с функцией )(x рассмотрим функцию .)()( 1 *    k j jjj xdcx Так как при условии 00 1   dxd k j jj неравенство (9) равносильно нера- венству ,)( 00 * 1 * cdxdc k j jjj   то для любой точки )(GEx k  имеем ,)( 00 * cdx  т.е. величина 00 ** cd  — минимум линейной функции )(x на множестве ).(GEk  Из эквивалентности условий )(  x и )(  x также следует, что точка x — минималь функции )(x на множестве ),(GEk  если и только если она — минималь задачи (8). Перенумеруем переменные таким образом, чтобы коэффициенты функции )(x были упорядочены по невозрастанию: ,... *** 2211 kk uuuuuu dcdcdc  (10) и обозначим ,* jj uuj dcc  juj xy  для всех .kJj Пусть )...,,( 1 mpp — первичная спецификация мультимножества },...,,{ 1 kcc  элементы которой упорядочены согласно порядку возрастания элементов основы; ,11 p 1ip ii pp  .mJi Пусть ),...,,( 1 * kll ggx  тогда соответствующая точка  )...,,( 1 * kuu xxy ),...,,( 1 krr gg где . juj lr  Обозначим }0\|{  ipm cJiI и рассмотрим разбиение числа k на m слагаемых )...( 1 mppk  и разбиение множества J на m подмножеств iN  по правилу            .0 если,\ , если},...,,{ где ,}\|{ 11 i ii pj Ij ppiij i cNJ IiuuNNjl N  (11) Из теоремы 2 следует, что точка )...,,( 1 kyyy  — минималь функции ,)( 1    k j jj ycy если и только если ),,( HGEy ks n где H — множество выборок вида (4), где )...,,( 1 iiki i  — произвольная ik -выборка из множества iN  ,mJi определенного согласно (11). Так как аналогичные рассуждения справедливы и в случае максимизации, то имеет место следующая теорема. Теорема 5. Пусть x — минималь (максималь) в задаче (8), ),( * x индексы ju kJj таковы, что выполняется условие (10), H — множество вы- борок вида (4), где )...,,( 1 iiki i  — произвольная ik -выборка из множества Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 1 75 iN  ,mJi определенного согласно (11), ....1 mppk  Точка x — также минималь (максималь) в задаче (8), если и только если для всех kJj выпол- няются равенства ,ju yx j  где ).,()...,,( 1 HGEyy ks nk  Пример 4. Рассмотрим решение задачи минимизации функции  )(x 4 2445 21 321    xx xxx на множестве )(3 5 GE размещений из элементов мультимно- жества }.7,5,5,3,2{G С помощью аналитического метода из [7], начиная про- цесс с точки ),5;3;2(0 x получим минималь ).;;()3;5;2( 231 * gggx  Соот- ветствующее значение целевой функции равно .1)( **  x В этом случае функция )(x принимает вид  1321 4)104()111()115()( xxxxx .4 3x Тогда ,11 u ,32 u ;23 u ,421  cc ,03 c ,11 p ,32 p .43 p Сформируем множества (11):  поскольку ,0 1 pс то },3,1{},{ 211  uuN };2,1{},{ 311  llN  поскольку ,0 2 pс то }.5,4,3{\ 162  NJN Тогда )},5;1;2(),4;1;2(),3;1;2(),5;2;1(),4;2;1(),3;2;1{(H ),5;3;2{(),( 2,3 4,5 HGE )}.7;2;3(),5;2;3(),7;3;2( В соответствии с теоремой 5 любая минималь в рассматриваемой задаче удо- влетворяет условиям ,11 yx  ,23 yx  ,32 yx  где ).,(),,( 2,3 4,5321 HGEyyy  Таким образом, минималями являются точки ),3;5;2(1 x ),3;7;2(2 x 3x ),2;5;3( ).2;7;3(4 x Заключение В настоящей статье сформулирован и обоснован критерий экстремали линейной безусловной задачи комбинаторной оптимизации на размещениях. Показано, что любая экстремаль является элементом определенного множества полиразмещений. Предложен и обоснован способ получения всех экстремалей, если известна одна из них, в безусловной задаче с дробно-линейной целевой функцией на размещениях. Полученные результаты могут использоваться при изучении свойств других классов задач евклидовой комбинаторной оптимизации, в первую очередь — услов- ных на размещениях, в том числе и с неопределенностью, а также для разработки методов решения таких задач. О.О. Ємець, Т.М. Барболіна ВЛАСТИВОСТІ КОМБІНАТОРНИХ ОПТИМІЗАЦІЙНИХ БЕЗУМОВНИХ ЗАДАЧ НА РОЗМІЩЕННЯХ З ЛІНІЙНОЮ І ДРОБОВО-ЛІНІЙНОЮ ЦІЛЬОВИМИ ФУНКЦІЯМИ Розглянуто властивості безумовних евклідових задач комбінаторної оптимізації на розміщеннях з лінійною і дробово-лінійною цільовими функціями. Показано, 76 ISSN 0572-2691 що будь-яка екстремаль у лінійній задачі є елементом певної множини полі- розміщень. Для задач із дробово-лінійною цільовою функцією обгрунтовано спосіб формування множини всіх екстремалей, якщо відома одна з них. O.A. Iemets, T.N. Barbolina PROPERTIES OF COMBINATORIAL OPTIMIZATION UNCONDITIONAL PROBLEMS ON ARRANGEMENTS WITH LINEAR AND LINEAR-FRACTIONAL OBJECTIVE FUNCTIONS The properties of unconditional combinatorial optimization problems on a set of ar- rangements with linear and linear-fractional objective functions are considered. We prove that in linear problem any extremal is an element of certain set of poly- arrangements. Also we substantiate how to construct the set of extremals in a prob- lem with linear-fractional objective function when one of extremals is known. 1. Сергиенко И.В. Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. — Киев : Наук. думка, 1981. — 288 с. 2. Згуровский М.З., Павлов А.А. Принятие решений в сетевых системах с ограниченными ре- сурсами. — Киев : Наук. думка, 2010. — 573 с. 3. Панишев А.В., Плечистый Д.Д. Модели и методы оптимизации в проблеме коммивояжера. — Житомир : ЖГТУ, 2006. — 300 c. 4. Гуляницкий Л.Ф., Сиренко С.И. Метаэвристический метод комбинаторной оптимизации ОМК-Н // Международный научно-технический журнал «Проблемы управления и инфор- матики». — 2010. — № 4. — С. 31–42. 5. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри- ческого проектирования. — Киев : Наук. думка, 1986. — 268 с. 6. Cтоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — http:// dspace.puet.edu.ua/handle/123456789/487. 7. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. — http://dspace.puet.edu.ua/handle/123456789/473. 8. Емец О.А., Черненко О.А. Оптимизация дробно-линейных функций на размещениях. — http://dspace.puet.edu.ua/handle/123456789/467. 9. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимізація на полірозміщеннях: теорія та методи. — http://dspace.puet.edu.ua/handle/123456789/376. 10. Гребенник И.В., Баранов А.В. Оценки минимума выпуклых функций на классах комбина- торных множеств перестановок // Радіоелектроніка. Інформатика. Управління. — 2009. — № 1. — С. 81–87. 11. Донець Г.П., Колєчкіна Л.М. Екстремальні задачі на комбінаторних конфігураціях. — http://dspace.puet.edu.ua/handle/123456789/560. 12. Емец О.А., Устьян Н.Ю. Исследование задач комбинаторной оптимизации игрового типа на размещениях // Проблемы управления и информатики. — 2007. — № 1. — С. 26–36. 13. Ємець О.О., Роскладка О.В., Недобачій С.С. Незвідна система обмежень для загального многогранника розміщень // Укр. мат. журн. — 2003. — 55, № 1. — С. 3–11. 14. Емец О.А., Барболина Т.Н. О свойствах линейной безусловной задачи комбинаторной оптимизации на размещениях с вероятностной неопределенностью // Кибернетика и системный анализ. — 2016. — № 2. — С. 127–139. 15. Ємець О.О., Парфьонова Т.О. Дискретна математика. — http://dspace.puet.edu.ua/handle/ 123456789/552 Получено 22.03.2016 http://dspace.puet.edu.ua/handle/%0b123456789/552 http://dspace.puet.edu.ua/handle/%0b123456789/552

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

Репозитарії

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