Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1

Досліджено властивості точок переставного многогранника та поширено відомий метод розв’язування систем лінійних нерівностей для знаходження загальної формули точок переставного многогранника при додаткових обмеженнях....

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207291
record_format	dspace
spelling	irk-123456789-2072912025-10-06T00:02:19Z Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1 Дослідження розв’язків лінійних задач евклідової комбінаторної оптимізації на перестановках з додатковими обмеженнями. Частина 1 The investigation of the solutions oflinearproblems of Euclidean combinatorial optimization onrearrangements with additional restrictions. Part I Емец, О.А. Устьян, Н.Ю. Оптимальное управление и методы оптимизации Досліджено властивості точок переставного многогранника та поширено відомий метод розв’язування систем лінійних нерівностей для знаходження загальної формули точок переставного многогранника при додаткових обмеженнях. The properties of points of a permutable polyhedron are investigated and the known method of solution of systems of linear inequalities for finding a general formula of points of a permutable polyhedron at additional restrictions is extended. 2011 Article Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1 / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2011. — № 2. — С. 26–32. — Бібліогр.: 21 назва. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207291 519.85 10.1615/JAutomatInfScien.v43.i3.30 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Емец, О.А. Устьян, Н.Ю. Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1 Проблемы управления и информатики
description	Досліджено властивості точок переставного многогранника та поширено відомий метод розв’язування систем лінійних нерівностей для знаходження загальної формули точок переставного многогранника при додаткових обмеженнях.
format	Article
author	Емец, О.А. Устьян, Н.Ю.
author_facet	Емец, О.А. Устьян, Н.Ю.
author_sort	Емец, О.А.
title	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1
title_short	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1
title_full	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1
title_fullStr	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1
title_full_unstemmed	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1
title_sort	исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. часть 1
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207291
citation_txt	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1 / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2011. — № 2. — С. 26–32. — Бібліогр.: 21 назва. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT emecoa issledovanierešenijlinejnyhzadačevklidovojkombinatornojoptimizaciinaperestanovkahsdopolnitelʹnymiograničeniâmičastʹ1 AT ustʹânnû issledovanierešenijlinejnyhzadačevklidovojkombinatornojoptimizaciinaperestanovkahsdopolnitelʹnymiograničeniâmičastʹ1 AT emecoa doslídžennârozvâzkívlíníjnihzadačevklídovoíkombínatornoíoptimízacíínaperestanovkahzdodatkovimiobmežennâmičastina1 AT ustʹânnû doslídžennârozvâzkívlíníjnihzadačevklídovoíkombínatornoíoptimízacíínaperestanovkahzdodatkovimiobmežennâmičastina1 AT emecoa theinvestigationofthesolutionsoflinearproblemsofeuclideancombinatorialoptimizationonrearrangementswithadditionalrestrictionsparti AT ustʹânnû theinvestigationofthesolutionsoflinearproblemsofeuclideancombinatorialoptimizationonrearrangementswithadditionalrestrictionsparti
first_indexed	2025-10-07T01:06:58Z
last_indexed	2025-10-07T01:06:58Z
_version_	1845283225559105536
fulltext	© О.А. ЕМЕЦ, Н.Ю. УСТЬЯН, 2011 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 2 26 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.85 О.А. Емец, Н.Ю. Устьян ИССЛЕДОВАНИЕ РЕШЕНИЙ ЛИНЕЙНЫХ ЗАДАЧ ЕВКЛИДОВОЙ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ НА ПЕРЕСТАНОВКАХ С ДОПОЛНИТЕЛЬНЫМИ ОГРАНИЧЕНИЯМИ. Часть 1 Введение. В последнее время активно развивается дискретная (в том числе и комбинаторная) оптимизация [1–14]. Исследуются новые классы задач с раз- личной спецификой, например такие, которые имеют игровые и комбинаторные черты. Исследуются возможности использования разных методов для решения таких задач, разрабатываются новые методы. Так, в комбинаторной оптимизации одним из объектов исследования являют- ся задачи оптимизации на перестановках [1, 3–7, 15–17]. Для решения линейных условных задач евклидовой комбинаторной оптимизации на перестановках разра- ботан, в частности, метод комбинаторного отсечения (для полностью и частично комбинаторных задач) [18–20]. Исследуются свойства перестановочного много- гранника, его вершин. Несмотря на большое количество исследований линейных условных задач евклидовой комбинаторной оптимизации на перестановках и свойств перестано- вочного многогранника, использование новых подходов и методов из других раз- делов математики может помочь найти новые свойства этих объектов. Постановка задачи. Исследуются линейные условные задачи евклидовой комбинаторной оптимизации на перестановках, свойства вершин перестановочно- го многогранника используя подходы, изложенные в [21]. В первой части публи- кации ставится задача — изучить свойства вершин перестановочного многогран- ника и представить произвольную точку многогранника через линейную комби- нацию его вершин. Задача исследования фундаментальной системы решений неравенств, которая описывает перестановочный многогранник, с дополнитель- ными ограничениями изучается во второй части данной статьи. Опираясь на ре- зультаты исследований первых двух частей статьи, в третьей части исследуется возможность применения метода решения систем неравенств, рассмотренного в [21], для нахождения общей формулы точек перестановочного многогранника при дополнительных ограничениях. Рассмотрим сначала, согласно работам [4] и [21] термины и обозначения, необходимые для изложения результатов исследования. Рассмотрим следующую систему однородных неравенств: 0...11  njnj xaxa ).,1( mj  (1) Некоторое решение системы (1) отличного от нуля ранга r называется суще- ственным решением, если оно не превращает в равенство все неравенства этой Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 2 27 системы. Существенное решение, для которого обращаются в равенство 1r лю- бых ее неравенств с линейно независимыми левыми частями (линейно независимые неравенства), называется фундаментальным решением. Два фундаментальных ре- шения считаются существенно различными, если в системе (1) не существует 1r таких линейно независимых неравенств, которые обращаются в равенства для каж- дого из них. Максимальная система существенно различных фундаментальных ре- шений системы (1) называется фундаментальной системой ее решений. Пусть элементы мультимножества }...,,{ 1 kggG  упорядочены по невозрас- танию: ,11   kii Jigg (2) }...,,{)( 1 neeGS  — основание мультимножества G (множество всех разных эле- ментов G). Согласно [4] рассмотрим многогранное множество ),(П Gkn которое является выпуклой оболочкой перестановок элементов мультимножества G и определяется следующей системой неравенств:               ; ; 11 11 k j j k j j i j j i j gx gx j ,,,, kirjkj JiJrjrjJ  (3) при условии (2). Далее будем рассматривать систему (3) для определения многогранного мно- жества ),(П Gkn которую согласно [4] назовем перестановочным многогранником. Совокупность неравенств системы (3) с одинаковым значением величины i называют i-й группой неравенств этой системы, а нижнее неравенство системы (3) — нулевой группой. Если )...,,,( 21 kxxxx  — вершина ),(П Gkn то справедливо ,},...,{}...,,{...},{ 1 1 1 1 1 2 2 2 1 1 1 k k k kk k k J    (4) , 11 kt i t i t Jigx i t     (5) и наоборот, если выполняются условия (4), (5), то x — вершина перестановочного многогранника ).(П Gkn Известно [4], что множество вершин )(П Gkn совпадает с множеством пере- становок из элементов G. Исследуем свойства точек перестановочного многогранника (в частности, вершин) и системы неравенств, которая описывает этот многогранник, используя подход, изложенный в [21]. Исследование свойств вершин перестановочного многогранника Рассмотрим систему неравенств , 11     i j j i j gx j (6) 11 ,,,   kirjkj JiJrjrjJ , 28 ISSN 0572-2691 при условии (2), которая в совокупности с равенством      k i k i ii gx 1 1 (или неравен- ствами    k j j k j j gx 11 и    k j j k j j gx 11 ) эквивалентна системе (3) и описывает перестановочный многогранник ).(П Gkn Проверять, чтобы точки удовлетворяли этому равенству, будем отдельно. Докажем следующую теорему. Теорема 1. Вершины перестановочного многогранника являются фундамен- тальными решениями системы неравенств (6). Доказательство. Ранг системы неравенств (6) равен ,kr  т.е. для того что- бы существенное решение этой системы неравенств было фундаментальным ре- шением, оно должно обращать в равенства 11  kr неравенств этой системы с линейно независимыми левыми частями. Рассмотрим вершины ).(П Gkn Как упоминалось выше, для вершин этого перестановочного многогранника справедливо (5). Последнее равенство     k t t k t gx k t 11 не рассматриваем (оно равно , 1 1      k i k i ii gx и вершины многогран- ника )(П Gkn удовлетворяют этому равенству). Значит, каждая вершина обращает в равенства 1k неравенств системы (6), левые части которых линейно незави- симы: ,1 11     k i t t i t Jigx i t причем выполняется (4). Поэтому вершины )(П Gkn — фундаментальные решения системы неравенств (6). Теорема 1 доказана. Имеет место следующее утверждение. Теорема 2. Фундаментальные решения системы (6) (вершины перестановоч- ного многогранника) существенно различны. Доказательство. Введем новые обозначения для j i из (4): пусть ,1 11 l тогда поскольку },,{ 2 2 2 1 1 1  одно из чисел 2 2 2 1 , равно ,1l второе обозна- чим ,2l а поскольку },,,{},{ 3 3 3 2 3 1 2 2 2 1  то среди чисел },,{ 3 3 3 2 3 1  есть 21, ll , третье обозначим 3l и т.д. до .1kl Итак, для вершин )(П Gkn выполняются следующие равенства:            ....... ... , , 11 21 1 11 21 1 kll ll l ggxx ggxx gx k (7) Значит, il — порядковый номер в векторе ),...,,( 1 kxxx  на котором нахо- дится .ig Допустим, что среди фундаментальных решений системы (6) имеются реше- ния, несущественно различные. Это означает, что они одновременно обращают в равенства (7) неравенства системы (6). Тогда в координатах этих вершин ig находится на месте il ,( 1 kJi но, учитывая, что это вершины и что они удовле- творяют равенству , 1 1      k i k i ii gx следовательно, и kg находится на месте ),kl т.е. эти две вершины совпадают. Поэтому не может быть несущественно различных фундаментальных решений-вершин. Теорема 2 доказана. Докажем следующее. Теорема 3. Система неравенств (6), кроме вершин перестановочного много- гранника, других фундаментальных решений не имеет. Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 2 29 Доказательство. Допустим противное: пусть существует хотя бы одно фун- даментальное решение системы (6), не являющееся вершиной перестановочного многогранника (точка, принадлежащая ),(П Gkn которая обращает в равенства 1k неравенств системы и удовлетворяет равенству ). 1 1      k i k i ii gx Пусть из первой группы неравенств системы неравенств (6) (i-й группой бу- дем считать неравенства системы с одинаковым значением i) в равенство обраща- ется неравенство .11 gxt  Больше неравенств, обращающихся в равенства, в пер- вой группе быть не может (если существует еще такое ,: 11 1 gxs s  то  11 st xx ).2111 gggg  Равенство достигается только в частном случае, когда ,21 gg  а для всех остальных ,2111 ggxx st  что противоречит одному из неравенств второй группы. Дальше будем рассматривать только строгие неравен- ства, исключая частный случай равенства ji gg  и даже нескольких ),ig поэто- му .11 gxt  Докажем, что из второй группы в равенство может обращаться только одно из неравенств вида :2121 ggxx tt  если будем иметь равенство  2 tt xx i ,1,,21  jigg то 321212 21 gggggxxx ttt i  — противоречие; а если обращаются в равенства два неравенства второй группы 2121 ggxx tt  и ,211 ggxx rtt  то  121112121 )()( gggxxxxxxxx tttttttt rr 3212112 2 ggggggg  — противоречие. Поэтому из второй группы в равенство обращается только неравенство ,2121 ggxx tt  тогда ,11 gxt  .22 gxt  Процесс можно продолжить. Пусть на этапе i получили ....,,11 itt gxgx i  Тогда на следующем этапе для группы 1i в равенство будет обращаться неравенство вида  11 ... ii ttt xxx 11 ...  ii ggg и только одно. Действительно: а) если в таком неравенстве не будет хотя бы одной из координат }...,,{ 1 im ttt xxx  (неравенство ......... 11111   gxxxxxx piimm tttttt ),... 1 ii gg то, прибавляя mt x к этому равенству, получим  11 ... mtt xx ,...... 1111 mmpiim tiittttt ggggxxxxx   где , 2  im tt gg т.е. ... 1 tx 2111 ............ 111    itiitttttt ggggggxxxxxx mmpiimm — противоречие (не выполняется одно из неравенств следующей группы); б) если в равенства превращаются два неравенства, то получаем такие равенства: ,...... 1111   iittt gggxxx ii ....... 111  iittt gggxxx mi Следовательно, 11   it gx i и .1 it gx m Тогда   mii tttt xxxx 11 ... 211111 ......   iiiiii gggggggg — противоречие (не выполня- ется одно из неравенств следующей группы). Аналогично для последней 1k группы в равенство превращается только одно неравенство вида ....... 1111   ktt ggxx k Два неравенства в равенства обращаться не могут, так как из 1k равенств 2k уже есть. Если допустить, что неравенство, которое обращается в равенство, не содержит хотя бы одну ко- ординату }...,,{ 21   km ttt xxx (вида   piimm tttttt xxxxxx 1111 ...... ),... 11   kt gg то   11111 ......... 1 kmpiimm tttttttt ggxxxxxxx km tt ggg  ...1 — противоречие (равенство      k i k i ii gx 1 1 не выполняется). 30 ISSN 0572-2691 Итак, в равенства обращаются 1k неравенств, по одному из каждой группы и 121 121 ...,,,   kttt gxgxgx k (а из равенства      k i k i ii gx 1 1 следует, что и ),kt gx k  т.е. это фундаментальное решение — вершина перестановочного мно- гогранника. Теорема доказана. Таким образом, вершины перестановочного многогранника — существенно различные фундаментальные решения системы неравенств (6), других фундамен- тальных решений система (6) не имеет, поэтому вершины составляют максималь- ную систему существенно различных фундаментальных решений системы, а сле- довательно, ее фундаментальную систему решений. Кроме того, вершины перестановочного многогранника удовлетворяют ра- венству . 1 1      k i k i ii gx Добавим к системе неравенств (6) поочередно неравенства      k i k i ii gx 1 1 и , 1 1      k i k i ii gx к которым сводится равенство . 1 1      k i k i ii gx Все фундаментальные решения (вершины перестановочного многогранника) удовле- творяют обоим неравенствам, поэтому согласно теореме 3.2 из [24] они, и только они, войдут в фундаментальную систему решений системы неравенств (3), кото- рая описывает перестановочный многогранник ).(П Gkn Следовательно, вершины перестановочного многогранника — фундаментальная система решений системы неравенств (3), которая описывает этот перестановочный многогранник. Докажем следующее утверждение. Теорема 4. Произвольное решение системы (3) выражается формулой , 1 k k l k xpx    (8) где lpp ...,,1 — произвольные неотрицательные элементы поля P, а kx — вер- шины перестановочного многогранника (3). Доказательство. В [21] доказана следующая теорема. Если система не- равенств (1) имеет существенные решения, то она имеет хотя бы одно фунда- ментальное решение. Если lkxxx k n kk ,1)...,,( 1  — любая фундаменталь- ная система решений этой системы и x — ее произвольное несущественное решение, т.е. произвольное решение системы ее граничных уравнений 0...11  njnj xaxa ,,1 mj  то произвольное решение системы неравенств (1) выражается формулой , 1 k k l k xpxx    где lpp ...,,1 — произвольные неотрица- тельные элементы поля P. Следовательно, несущественное решение системы неравенств (1) должно об- ращать в равенства все его неравенства. Система неравенств (3) описывает пере- становочный многогранник ).(П Gkn Несущественное решение системы (3) долж- но обращать все неравенства в равенства, тогда из первой группы получим 1gxi  и      k i i k i k i i ggx 11 1 1 1(g — наибольший из элементов мультимноже- ства G), а это означает, что не будет выполняться равенство . 1 1      k i k i ii gx Следо- вательно, система (3) несущественных решений не имеет, и ее произвольное ре- Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 2 31 шение выражается формулой , 1 k k l k xpx    где lpp ...,,1 — произвольные неот- рицательные элементы поля P, а kx — фундаментальная система решений (3). Теорема доказана. Как было доказано выше, вершины перестановочного многогранника состав- ляют фундаментальную систему решений (3) и других фундаментальных решений система не имеет. Следовательно, в формуле (8) kx — вершины перестановочно- го многогранника, и любая точка перестановочного многогранника записывается в таком виде. Значит, при использовании метода Н.В. Черниковой для нахожде- ния общей формулы решений системы линейных неравенств для системы нера- венств (3) получим формула (8). Выводы. Теоремы о новых свойствах вершин перестановочного многогран- ника и представления произвольной точки многогранника через линейную ком- бинацию его вершин, доказанные в первой части статьи, дают возможность опре- делить структуру фундаментальной системы решений системы неравенств, кото- рая описывает перестановочный многогранник. Полученные результаты будут использоваться во второй и третьей частях статьи. Приложение 1 Приведем пример доказательства теоремы 3. Пусть },2,0,3,0,5,0{xP тогда система (11) имеет следующий вид:                 .8,0 8,0 8,0 5,0 5,0 5,0 32 31 21 3 2 1 xx xx xx x x x Пусть в равенство обращается неравенство 5,01 x (т.е. ).5,01 x Если к тому же, например, 2x обращает неравенство из первой группы в равенство, то 1x 5,02  x и ,8,0121  xx не удовлетворяется неравенство из второй группы. Покажем, что из второй группы в равенство может обращаться только одно из неравенств вида :211 2 ggxx t  если в равенство будет обращаться неравен- ство ,8,032  xx то ,13,18,05,0321  xxx равенство 1321  xxx не выполняется. Если же будем иметь два равенства из второй группы 8,021  xx и ,8,032  xx то ,11,15,08,08,0)()( 13121321  xxxxxxxx т.е. равенство 1321  xxx тоже не выполняется. О.О. Ємець, Н.Ю. Устьян ДОСЛІДЖЕННЯ РОЗВ’ЯЗКІВ ЛІНІЙНИХ ЗАДАЧ ЕВКЛІДОВОЇ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ НА ПЕРЕСТАВЛЕННЯХ З ДОДАТКОВИМИ ОБМЕЖЕННЯМИ. Частина 1 Досліджено властивості точок переставного многогранника та поширення відомого методу розв’язування систем лінійних нерівностей для знахо- дження загальної формули точок переставного многогранника при додатко- вих обмеженнях. 32 ISSN 0572-2691 O.A. Yemets, N.Yu. Ustian THE INVESTIGATION OF THE SOLUTIONS OF LINEAR PROBLEMS OF EUCLIDEAN COMBINATORIAL OPTIMIZATION ON REARRANGEMENTS WITH ADDITIONAL RESTRICTIONS. Part I The properties of points of a permutable polyhedron are investigated and the known method of solution of systems of linear inequalities for finding a general formula of points of a permutable polyhedron at additional restrictions is extended. 1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных за- дач оптимизации. — Киев : Наук. думка, 1981. — 288 с. 2. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы исследо- вания, решения. — Киев : Наук. думка, 2003. — 263 с. 3. Емец О.А. Евклидовы комбинаторные множества и оптимизация на них. Новое в матема- тическом программировании: Учеб. пособие. — Киев : УМК ВО, 1992. — 92 с. 4. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Київ : ІСДО, 1993. — 188 с. 5. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимізація на полірозміщеннях: теорія та методи. — Полтава : РВЦ ПУСКУ, 2005. — 103 с. 6. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільо- вими функціями. — Киев : Наук. думка, 2005. — 117 с. 7. Ємець О.О., Роскладка О.В. Задачі оптимізації на полікомбінаторних множинах: властиво- сті та розв’язування. — Полтава : РВЦ ПУСКУ, 2006. — 129 с. 8. Панішев А.В., Данильченко О.М., Скачков В.О. Вступ до теорії складності дискретних за- дач. — Житомир : ЖДТУ, 2004. — 236 с. 9. Панишев А.В., Плечистый Д.Д. Модели и методы оптимизации в проблеме коммивояжера. — Житомир: ЖГТУ, 2006. — 300 с. 10. Гуляницький Л.Ф. Розробка моделей і наближених методів комбінаторної оптимізації та їх застосування в інформаційних технологіях: Автореф. дис. ... докт. техн. наук (01.05.02) / НАН України. Ін-т кібернетики ім. В.М. Глушкова. — Київ, 2005. — 32 с. 11. Гребеннік І.В. Математичні моделі та методи комбінаторної оптимізації в геометричному проектуванні: Автореф. дис. ... докт. техн. наук (01.05.02) / Ін-т пробл. машинобудування ім. А.М. Підгорного. — Харків, 2006. — 34 с. 12. Ємець О.О., Роскладка А.А. Про оцінки мінімумів цільових функцій при оптимізації на сполученнях // Укр. мат. журн. — 1999. — № 8. — С. 1118–1121. 13. Ємець О.О., Роскладка О.В., Недобачій С.І. Незвідна система обмежень для загального многогранника розміщень // Там же. — 2003. — № 1. — С. 3–11. 14. Ємець О.О., Барболіна Т.М. Розв’язування задач нелінійної умовної оптимізації на розмі- щеннях методом відсікання // Там же. — 2003. — № 5. — С. 604–612. 15. Валуйская О.А., Яковлев С.В. О минимизации линейной функции на вершинах перестано- вочного многогранника с учетом линейных ограничений / Там же. — 2001 — № 9. — С. 89–101. 16. Ємець О.О., Колєчкіна Л.М. Задача оптимізації на переставленнях з дробово-лінійною ці- льовою функцією: властивості множини допустимих розв'язків // Там же. — 2000. — № 12. — С. 1630–1640. 17. Емец О.А., Устьян Н.Ю. Решение некоторых задач комбинаторной оптимизации на размеще- ниях и перестановках игрового типа // Проблемы управления и информатики. — 2006. — № 3. — С. 37–47. 18. Емец О.А. Об одном методе отсечения для задач комбинаторной оптимизации // Экономика и мат. методы. — 1997. — 33, вып. 4. — С. 120–129. 19. Ємець О.О., Ємець Є.М. Відсікання в лінійних частково комбінаторних задачах евклідової комбінаторної оптимізації // Доп. НАН України. — 2000. — № 9. — С. 105–109. 20. Емец О.А., Емец Е.М. Отсечения в линейных частично комбинаторных задачах оптимиза- ции на перестановках // Экономика и мат. методы. — 2001. — 37, № 1. — С. 118–121. 21. Черников С.Н. Линейные неравенства. — М. : Наука, 1968. — 488 с. Получено 13.01. 2010

Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 1

Репозитарії

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