Оптимизация на размещениях: симплексная форма многогранника размещений

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

Full description

Saved in:

Bibliographic Details
Date:	2017
Main Authors:	Емец, О.А., Емец, А.О, Поляков, И.М.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Series:	Проблемы управления и информатики
Subjects:	Оптимальное управление и методы оптимизации
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/208607
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Оптимизация на размещениях: симплексная форма многогранника размещений / О.А. Емец, А.О Емец, И.М. Поляков // Проблемы управления и информатики. — 2017. — № 6. — С. 19-32. — Бібліогр.: 28 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208607
record_format	dspace
spelling	irk-123456789-2086072025-11-03T01:02:04Z Оптимизация на размещениях: симплексная форма многогранника размещений Оптимізація на розміщеннях: симплексна форма багатогранника розміщень Optimization on arrangements: the simplex shape of the polyhedron of arrangements Емец, О.А. Емец, А.О Поляков, И.М. Оптимальное управление и методы оптимизации Розглянуто знаходження симплексної форми загального багатогранника розміщень, яку необхідно використовувати при застосуванні АК при розв’язуванні допоміжних задач лінійного програмування в методах комбінаторного відсікання в евклідовій комбінаторній оптимізації. It is considered the finding of the simplex form of the general polyhedron of arrangements, which must be used for applying Karmarkar`s algorithm in solving auxiliary problems of the linear programming in combinatorial cutting methods in the Euclidean combinatorial optimization. 2017 Article Оптимизация на размещениях: симплексная форма многогранника размещений / О.А. Емец, А.О Емец, И.М. Поляков // Проблемы управления и информатики. — 2017. — № 6. — С. 19-32. — Бібліогр.: 28 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208607 519.8 10.1615/JAutomatInfScien.v49.i12.20 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/208607
citation_txt	Оптимизация на размещениях: симплексная форма многогранника размещений / О.А. Емец, А.О Емец, И.М. Поляков // Проблемы управления и информатики. — 2017. — № 6. — С. 19-32. — Бібліогр.: 28 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT emecoa optimizaciânarazmeŝeniâhsimpleksnaâformamnogogrannikarazmeŝenij AT emecao optimizaciânarazmeŝeniâhsimpleksnaâformamnogogrannikarazmeŝenij AT polâkovim optimizaciânarazmeŝeniâhsimpleksnaâformamnogogrannikarazmeŝenij AT emecoa optimízacíânarozmíŝennâhsimpleksnaformabagatogrannikarozmíŝenʹ AT emecao optimízacíânarozmíŝennâhsimpleksnaformabagatogrannikarozmíŝenʹ AT polâkovim optimízacíânarozmíŝennâhsimpleksnaformabagatogrannikarozmíŝenʹ AT emecoa optimizationonarrangementsthesimplexshapeofthepolyhedronofarrangements AT emecao optimizationonarrangementsthesimplexshapeofthepolyhedronofarrangements AT polâkovim optimizationonarrangementsthesimplexshapeofthepolyhedronofarrangements
first_indexed	2025-11-03T02:07:02Z
last_indexed	2025-11-04T02:05:54Z
_version_	1847823648368361472
fulltext	© О.А. ЕМЕЦ, А.О. ЕМЕЦ, И.М. ПОЛЯКОВ, 2017 Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 6 19 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.8 О.А. Емец, А.О Емец, И.М. Поляков ОПТИМИЗАЦИЯ НА РАЗМЕЩЕНИЯХ: СИМПЛЕКСНАЯ ФОРМА МНОГОГРАННИКА РАЗМЕЩЕНИЙ Введение В современной теории оптимизации комбинаторная оптимизация (см., в частности, [1–6]) является активно развивающейся частью, отражающей актуаль- ные проблемы исследования современного мира. Среди комбинаторных кон- фигураций одними из наиболее изучаемых в силу важности и употребляемости в оптимизационных проблемах являются размещения. Исследованию множества размещений и его обобщений в связи с задачами оптимизации на нем посвя- щено много публикаций, укажем, в частности, [1–24]. При построении методов решения задач оптимизации на евклидовых комбинаторных множествах, одним их которых есть множества размещений, нередко используются вспомогательные задачи линейного программирования, в которых частью ограничений являются комбинаторные многогранники — выпуклые оболочки евклидовых комбина- торных множеств. При решении таких вспомогательных задач на комбинатор- ных многогранниках методом Кармаркара необходимо знать так называемую симплексную форму этих многогранников. Для множеств перестановок такие формы исследованы в [25, 26]. Для многогранника размещений эта задача тре- бует решения. Получению симплексной формы многогранника размещений и посвящена настоящая публикация. Постановка задачи Поставим такую задачу: получить и исследовать общий многогранник раз- мещений [2], подвергнув его преобразованиям, необходимым, чтобы использо- вать алгоритм Кармаркара (АК) для решения задач, в которых этот многогран- ник — допустимая область. При этом будем использовать терминологию [2]. Рассмотрим решение линейной условной частично комбинаторной задачи на общем множестве размещений [2] вида: найти упорядоченную пару  *),( yyC такую, что ,max)( 1    m j jj Ry ycyC m (1)    m j jj Ry ycy m 1 maxarg* (2) 20 ISSN 0572-2691 при комбинаторных условиях kk nk RGExxx   )()...,,( 1 (3) и дополнительных условиях , 1 i m j jij bya   ;rJi , 1 i m j jij bya   .\ rs JJi (4) Здесь )(GEk n — общее множество k -размещений [2], заданных из элементов мультимножества },...,,{ 1  ggG среди которых n различных элементов: ,)...,,,...,,( 11 m mkk Ryyxxy   ii yx  ,kJi srnkm ,,,,,  — заданные натуральные числа ,( km  ;n ,k .rs  При этом sr, могут быть и нулями); ,jc ,ija ib — заданные действительные числа ,mJj ;sJi mR — m -мерное евклидово арифметическое пространство; kJ — множество первых k натураль- ных чисел: },...,,2,1{ kJk  а 0J . Один из методов решения линейных частично комбинаторных задач на ев- клидовых комбинаторных множествах, к которым относится и ),(GEk n — метод комбинаторного отсечения [5, 27]. При этом как вспомогательные используются задачи линейного программирования (ЗЛП), которые получают из задачи (1)–(4) заменой условия (3) на условие-релаксацию: ),()(conv GGEx k n k n   (5) где )(Gk n — выпуклая оболочка )(conv GEk n общего множества размеще- ний ).(GE k n Система ограничений, описывающая ),(Gk n известна [2], поэтому условие (5) записывается в виде                  , , \|\| 1 1 \|\| 1 k i i i i k i i i i Jgx Jgx (7) где элементы мультимножества G пронумерованы в соответствии с таким порядком: ,...21  ggg (8) \|\| — количество элементов множества . Алгоритм преобразования (АП) Для использования АК [28] применим алгоритм преобразования ЗЛП, кото- рая записана в стандартной форме, к необходимому виду. Форму получаемого многогранника будем называть симплексной. При этом используем подход, изло- женный в [26]. Рассмотрим матричную запись стандартной формы ЗЛП: maxcx при условиях      ,0 ; x bAx (9) (6) Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 6 21 где c — заданный вектор ),...,,( 1 kccc  x — вектор-столбец неизвестных, );...,,( 1 T kxxx  матрица A — заданная матрица коэффициентов при неизвест- ных с элементами :ija ,)( ,1 ,1 ri kjijaA    b — заданный вектор .)...,,( T 1 rbbb  Для вектора x запись 0x означает, что все его координаты неотрицательны. АП для ЗЛП, где допустимая область задана условием (9), представим такой последовательностью шагов. Шаг 1. Систему ограничений (9), ЗЛП запишем в каноническом виде:      ,0, ; yx byAx (10) где .)...,,( T 1 ryyy  Шаг 2. Вводим необходимое далее ограничение, которому удовлетворяют все допустимые решения ЗЛП из системы (9): , 1 1 Uyx k j r i ij     (11) U — достаточно большое число. Далее условие (11) удобно использовать как равенство , 1 1 Uuyx k j r i ij     (12) где вновь введенная переменная .0u Шаг 3. Умножим правую часть системы (10) на равное единице выражение .1 1 1              Uuyx k j r i ij Это позволяет получить из системы (10) однородную систему, эквивалент- ную ей. При этом уравнение системы (10) представим в виде ,0 buyAxA yx (13) где ,)( ,1 ,1 ri kj x ij x aA    1 Ubaa iij x ij ,kJj ;rJi ri kj y ij y aA ,1 ,1 )(    , 11  Uba i y ii ;rJi ,1 Uba i y ij ij  ,rJi ,kJj 0 — нулевой век- тор-столбец пространства ,rR т.е. .)0...,,0(0 T rR Шаг 4. Введем новые переменные: 1 UxX jj ;kJj 1 UyY ii ,rJi (14) а также .1 UuV (15) В этих переменных условие (12) определяет симплекс с вершиной в начале коор- динат, причем ребра симплекса, направленные по положительным направлениям координатных осей, имеют единичную длину. Используя в (13) замены (14), (15), можем записать ЗЛП так: maxUcx (16) 22 ISSN 0572-2691 с учетом ограничений ,0 bVYAXA YX (17) ;1 11   VYX r i i k j j (18) ;0)...,,( 1  T kXXX ;0)...,,( 1  T rYYY ,0V (19) где используемые в формуле (17) матрицы определены так: ,)( ,1 ,1 ri kj X ij X aA    iij X ij bUaa  ,rJi ;kJj ,)( ,1 ,1 ri kj Y ij Y aA    i Y ii bUa  ;rJi ,i Y ij ba  ,ji  ;rJi .kJj Шаг 5. На этом шаге обеспечивается условие, что бароцентр симплекса, т.е. точка, все координаты которой равны между собой и равны величине , об- ратной размерности пространства, удовлетворяет условиям , эквивалентным исходной ЗЛП. Это осуществляется за счет вычитания от левой части каждого уравнения в (17) неотрицательной переменной ,iZ ,rJi помноженной на сумму всех коэффици- ентов левой части этого уравнения. При этом в целевую функцию прибавляется слагаемое ,)( iZM выполняющее роль штрафа и при достаточно большом поло- жительном M обеспечивающее при максимизации измененной таким образом целевой функции нулевое значение переменной iZ с учетом выполнения условий трансформированной ЗЛП. Таким образом, из задачи (16)–(19) получаем эквивалентную ей ЗЛП: max, 1    r i iZMUcX (20) ,bVZAYAXA ZYX  (21) ,1 111    VZYX r i i r i i k j j (22) ;0X ;0Y ;0)...,,( T 1  rZZZ ,0V (23) где ,)( ,1 ,1 ri kj Z ij Z aA               k j iji Z ii aUbka 1 1)12( ;rJi 0Z ija ,ji  ;rJi .kJj Для системы (21), (22) точка nR nnn VZYX        1 ...,, 1 , 1 ),,,( ** допустима. Здесь ,12  rkn а n VZYX iij 1  rJi .kJj Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 6 23 Получение симплексной формы общего многогранника размещений Рассмотрим вид общего многогранника размещений (6), (7), в который он обратится после применения АП. Для этого обратимся к задаче max 1   jj k j xc при выполнении условий системы (6), (7). Напомним, что в этой системе элемен- ты мультимножества G удовлетворяют неравенствам (8). Применим шаг за ша- гом АП. Шаг 1. Введем в рассмотрение неотрицательные переменные ,y ,z ,kJ ,kJ с помощью которых систему (6), (7) запишем в виде равенств       \|\| 1i i i i gyx ,kJ (24)       \|\| 1 1 i i i i gzx .kJ (25) Шаг 2. Вводим новое ограничение вида (11): , 1 Uzyx kk J k j J j         (26) а при 0u имеем . 1 Uuzyx kk J k i J i         (27) Параметром U может выступать число ,2 11 1 11 1                       j i i j i i j k k j k i i ggCgU (28) что обосновывается в таком утверждении. Теорема 1. Для общего многогранника размещений (6), (7) при условиях (8), (24), (25) справедлива оценка .2 1 11 1 1 1 1                               k j j i i j i i j k k i i J k i J i ggCgzyx kk (29) Доказательство. Неравенства (6), (7) можно записать так:         \|\| 1 1 \|\| 1 i i i i i i gxg .kJ (30) Выразим из (24)      \|\| 1i i i i gxy ,kJ (31) 24 ISSN 0572-2691 а z из (25) —       i i i i xgz \|\| 1 1 .kJ (32) Правая часть (30) дает из (31)        \|\| 1 \|\| 1 1 i i i i ggy ,kJ (33) а левая часть (30) в виде     \|\| 1i i i i gx из (32) дает        \|\| 1 \|\| 1 1 i i i i ggz .kJ (34) При переходе к (34) использован тот факт, что и множество ,kJ и мно- жество .kJ Осталось оценить суммы переменных ,y ,z входящие в (27). Учтем, что количество подмножеств в kJ с одинаковым количеством j \|\|\|\| элементов равно количеству j k C сочетаний из k элементов по .j Тогда из (33) получаем , 11 1 1                       j i i j i i j k k jJ ggCy k (35) а из (34) имеем . 1 11 1                        k j j i i j i i j k J ggCz k (36) Из (7) при kJ (а значит, )\|\| k имеем . 1 1 1      k i i k i j gx (37) Сумма неравенств (35)–(37) дает (29), что и требовалось доказать. Шаг 3. Приводим систему (24), (25) к однородной. Для этого умножаем пра- вую часть уравнений системы на равное единице выражение , 1 1                 uzyxU kk JJ k i i где U вычисляется по формуле (28). В результате получаем такую систему: 01 \ \|\| 1 1 \|\| 1 1                                              uzyxgUyxgU kkk JJJi i i i i i i i ;kJ (38) Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 6 25 k JJ i Ji i i i i i i Juzyx gUzxgU kkk                                              0 1 \ \|\| 1 1 1 \|\| 1 1 1 (39) Шаг 4. Согласно (14), (15) вводим новые переменные и из (38), (39) и (27) имеем систему ограничений: ,0 \ \|\| 1 \|\| 1 \|\| 1 k JJJi i i i i i i i i i JVZYXgYgUXgU kkk                                             (40) 0 \ \|\| 1 1 \|\| 1 1                                             VZYXgZXgU kkk JJJi i i i i i i i ,kJ (41) .1 1        VZYX kk JJ k i i (42) При этом функция цели ЗЛП приобретает вид .max 1   jj k j XcU Шаг 5. В левой части каждого из уравнений (40), (41) отнимаем свою неот- рицательную переменную  W (для (40)) и  W (для (41)), ;kJ kJ с ко- эффициентами \|\| и \|\| соответственно, где ,)12()1\|(\| \|\| 1 1 \|\|       i i k gkU (43) .)12()1\|(\| \|\| 1 1 1 \|\|        i i k gkU (44) Утверждение 1. При фиксированном подмножестве kJ сумма коэффи- циентов при переменных в уравнении (40) равняется числу , которое задано в (43), а при выбранном подмножестве kJ сумма коэффициентов при пере- менных в уравнении (41) равна ,\|\| что задается формулой (44). Доказательство. Справедливость утверждения проверяется непосредствен- ными вычислениями. Сделаем это для . Первое слагаемое в (40) содержит \|\| переменных ,iX ,i с коэффициен- том при каждом . \|\| 1     i igU Второе слагаемое содержит множитель Y с коэффи- циентом . \|\| 1            i igU 26 ISSN 0572-2691 Третье алгебраическое слагаемое в (40) содержит \|\|\|\\|  kJk слагаемых вида iX ,\ kJi 22 k слагаемых ,Y где , ,kJ 12 k слагае- мое Z kJ и слагаемое .V Все эти слагаемые с сомножителем . \|\| 1     i ig Таким образом, U входит в сумму 1\|\|  раз, а слагаемое     \|\| 1i ig входит в общем такое количество раз: .1211222\|\|1\|\| 1   kk kkk Учитывая это, получаем формулу (43). Аналогично для (41) имеем: первое слагаемое содержит \|\| переменных ,iX ,i и одно слагаемое Z с коэффициентом при каждом . \|\| 1 1    i igU Второе алгебраическое слагаемое в (41) содержит \|\|\|\\|  kJk слагаемых вида ,iX ,\ kJi 12 k слагаемых ,Y ,kJ 22 k слагаемых ,Z где , kJ и слагаемое .V Все эти слагаемые имеют сомножитель . \|\| 1 1    i ig Таким образом, U входит в формулу 1\|\|  раз, а слагаемые     \|\| 1 1 i ig такое количество раз: .1212212\|\|1\|\| 1   kk kkk Это подтверждает справедливость формулы (44). Утверждение доказано. Выполнив пятый шаг АП, получим такую ЗЛП: max 1         WMWMXcU kk JJ jj k j (45) при ограничениях, которые из вида (40)–(42) трансформируются в                                           VZYXgYgUXgU kkk JJJi ii ii i i i i i \ \|\| 1 \|\| 1 \|\| 1 ,0\|\|   W ,kJ (46)                          ZXgU i i i i \|\| 1 1 ,0\|\| \ \|\| 1 1                         WVZYXg kkk JJJi i i i ,kJ (47) Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 6 27 ,1α ω 1           VWWZYX kkkk JJJJ k i i (48) ;0Y ;0Z ;0 W 0β ω W .kJ (49) Легко видеть, что точка ),,,,,,( ** VWWZYXT  имеющая все n ко- ординат, равных , 1 n удовлетворяет системе (46)–(48), где ,)...,,( 1 * k k RXXX  ,,,, **** qRWWZY  при ,12  kq ,1* RV  а также  1)12(4 kkn .32 2  kk Образ общего многогранника размещений, полученный в результате приме- нения АП, и называем, как сказано выше, симплексной формой многогранника размещений. Таким образом, доказана теорема о симплексной форме многогранника раз- мещений. Теорема 2. Общий многогранник размещений ),(Gk n задаваемый системой ограничений (6), (7) при условии (8), имеет симплексную форму, определяемую системой (46)–(49), параметры и переменные которой задаются условиями (14), (15), (24), (25), (27), (28), (43), (44). Иллюстративный пример Рассмотрим преобразование ЗЛП к виду, необходимому для применения АК, когда систему (9) определяет общий многогранник размещений, т.е. система (6), (7) при выполнении условий (8). Пусть выполняются такие условия в (1)–(4): ;3 mk 0 rs (т.е. условий вида (4) нет); },,,,,{ 33221 eeeeeG  т.е. ;5 ,3n ,11 eg  232 egg  , 354 egg  , ,321 eee  т.е. исходной является ЗЛП max332211  xcxcxcz при ограничениях ,11 gx  ,12 gx  ,13 gx  ,2121 ggxx  ,2131 ggxx  ,2132 ggxx  ,321321 gggxxx  ,51 gx  ,52 gx  ,53 gx  ,4521 ggxx  ,4531 ggxx  ,4532 ggxx  .345321 gggxxx  Найдем параметры симплексной формы для заданного многогранника раз- мещений: ,14724 123 eeeU  ;18 11 g ;3226915 123452 ggggg  ;4634161830 123453 ggggg  ;281621812 123451 ggggg  28 ISSN 0572-2691 ;42243927 123452 ggggg  .5632141842 123453 ggggg  Имеем (согласно теореме 2) такую симплексную форму многогранника раз- мещений:  123231312323211111 ()()( YYYYYYXXggUYgUX ,0) 11123231312321  WVZZZZZZZ  123231312313111212 ()()( YYYYYYXXggUYgUX ,0) 21123231312321  WVZZZZZZZ  123231312212111313 ()()( YYYYYYXXggUYgUX ,0) 31123231312321  WVZZZZZZZ  231332132121122121 )(()())()(( YYYYYXggggUYggUXX ,0) 122123231312321123  WVZZZZZZZY  231232122121132131 )(()())()(( YYYYYXggggUYggUXX ,0) 132123231312321123  WVZZZZZZZY  131232112121232132 )(()())()(( YYYYYXggggUYggUXX ,0) 232123231312321123  WVZZZZZZZY  1321321123321321 )(()())()(( YggggggUYgggUXXX ,0) 123312323131232123131232  WVZZZZZZZYYYYY  231312321325511 ())(( YYYYYYXXggUZX ,0) 1112323131232123   WVZZZZZZY  231312321315522 ())(( YYYYYYXXggUZX ,0) 2112323131231123   WVZZZZZZY  231312321215533 ())(( YYYYYYXXggUZX ,0) 3112323131221123   WVZZZZZZY  231312321345451221 )(())()(( YYYYYYXggggUZXX ,0) 1221232313321123   WVZZZZZZY Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 6 29  231312321245451331 )(())()(( YYYYYYXggggUZXX ,0) 1321232312321123   WVZZZZZZY  231312321145452332 )(())()(( YYYYYYXggggUZXX ,0) 2321231312321123   WVZZZZZZY  1312321345345123321 )(())()(( YYYYYggggggUZXXX ,0) 123323131232112323   WVZZZZZZYY  321123231312321321 ZZZYYYYYYYXXX   123231312321123231312 WWWWWWWVZZZZ .1123231312321   WWWWWWW При ;11 e ;22 e ,33 e поскольку ;2;1 321  ggg ;354  gg ;4U ;181  ;102  ;23  ;341  ;242  ,323  получаем такой общий многогранник размещений в симплексной форме:  123231312323211 (4543 YYYYYYXXYX ,018) 1123231312321  WVZZZZZZZ  123231312313122 (4543 YYYYYYXXYX ,018) 2123231312321  WVZZZZZZZ  123231312212133 (4543 YYYYYYXXYX ,018) 3123231312321  WVZZZZZZZ  231332131221 (347)(41 YYYYYXYXX ,010) 12123231312321123  WVZZZZZZZY  231232121331 (347)(41 YYYYYXYXX ,010) 13123231312321123  WVZZZZZZZY  131232112332 (347)(41 YYYYYXYXX ,010) 23123231312321123  WVZZZZZZZY  231312321123321 (549)(39 YYYYYYYXXX ,02) 123123231312321  WVZZZZZZZ  2313123213211 (3)(41 YYYYYYXXZX 30 ISSN 0572-2691 ,034) 112323131232123   WVZZZZZZY  2313123213122 (3)(41 YYYYYYXXZX ,034) 212323131231123   WVZZZZZZY  2313123212133 (3)(41 YYYYYYXXZX ,034) 312323131221123   WVZZZZZZY  23131232131221 (6)(38 YYYYYYXZXX ,024) 121232313321123   WVZZZZZZY  23131232121331 (6)(38 YYYYYYXZXX ,024) 131232312321123   WVZZZZZZY  23131232112332 (6)(38 YYYYYYXZXX ,024) 231231312321123   WVZZZZZZY  1312321123321 (8)(36 YYYYYZXXX ,032) 12323131232112323   WVZZZZZZYY  321123231312321321 ZZZYYYYYYYXXX   123231312321123231312 WWWWWWWVZZZZ .1123231312321   WWWWWWW 0,,,,     WWZYV .kJ Отметим, что точка T с координатами , 32 1 ,32RT  удовлетворяет полу- ченной симплексной форме многогранника размещений. Заключение В настоящей работе получена симплексная форма общего многогранника размещений. Она необходима для применения полиномиального АК при решении вспомогательных задач линейного программирования в методах комбинаторного отсечения. Вследствие использования этой формы следует ожидать повышения эффективности методов отсечения. Дальнейшие исследования целесообразно направить на изучение образов множеств вершин, смежных вершин, ребер, граней произвольной размерности, свойств многогранника размещений, проявившихся в результате трансформации его в симплексную форму, а также на изучение других свойств симплексной фор- мы многогранника размещений. Международный научно-технический журнал «Проблемы управления и информатики», 2017, № 6 31 О.О. Ємець, Ол-ра О. Ємець, І.М. Поляков ОПТИМІЗАЦІЯ НА РОЗМІЩЕННЯХ: СИМПЛЕКСНА ФОРМА БАГАТОГРАННИКА РОЗМІЩЕНЬ Розглянуто знаходження симплексної форми загального багатогранника розмі- щень, яку необхідно використовувати при застосуванні АК при розв’язуванні допоміжних задач лінійного програмування в методах комбінаторного відсі- кання в евклідовій комбінаторній оптимізації. O.A. Yemets, A.O. Yemets, I.M. Polyakov OPTIMIZATION ON ARRANGEMENTS: THE SIMPLEX SHAPE OF THE POLYHEDRON OF ARRANGEMENTS It is considered the finding of the simplex form of the general polyhedron of ar- rangements, which must be used for applying Karmarkar`s algorithm in solving aux- iliary problems of the linear programming in combinatorial cutting methods in the Euclidean combinatorial optimization. 1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. — Киев : Наук. думка, 1981. — 288 с. 2. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Київ : Ін-т системн. досліджень освіти, 1993. — 188 с. — http://dspace.uccu.org.ua/handle/123456789/487. 3. Донець Г.П., Колєчкіна Л.М. Екстремальні задачі на комбінаторних конфігураціях. — Пол- тава: РВВ ПУЕТ, 2011. — 309 с. 4. Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. — Київ : Видавничо-поліграфічний центр «Київський університет», 2016. — 142 с. 5. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. — Киев : Наук. думка, 2008. — 159 с. — http://dspace.uccu.org.ua/handle/123456789/473. 6. Емец О.А., Черненко О.А. Оптимизация дробно-линейных функций на размещениях. — Киев : Наук. думка, 2011. — 154 с. — http://dspace.uccu.org.ua/handle/123456789/467. 7. Emets' O.O., Roskladka O.V., Nedobachii S.I. Irreducible system of constraints for a general polyhedron of arrangements // Ukrainian Mathematical Journal. — 2003. — 55, N 1. — P. 1–12. 8. Emets' O., Barbolina T. On the solution of problems of nonlinear conditional optimization on arrangements by the cut-off method // Ibid. — 2003. — 55, N 5. — P. 729–738. 9. Emets O.A., Barbolina T.N. Solving linear optimization problems on arrangements by the truncation method // Cybernetics and systems analysis — 2003. — 39, N 6. — P. 889–896. 10. Yemets O.A., Barbolina T.N. Solution of Euclidean combinatorial optimization problems by the method of construction of a lexicographic equivalence // Ibid. — 2004 — 40, N 5. — P. 726–734. 11. Barbolina T.N., Emets O.A. An all-integer cutting method for linear constrained optimization problems on arrangements // Computational mathematics and mathematical physics. — 2005. — 45. — N 5. — P. 243–250. 12. Yemets O., Chernenko O.A. Nonreducible system of constraints of a combinatorial polyhedron in a linear-fractional optimization problem on arrangements // Cybernetics and systems analysis. — 2005. — 41, N 2. — P. 246–254. 13. Yemets O.A., Barbolina T.N., Chernenko O.A. Solving optimization problems with linear- fractional objective functions and additional constraints on arrangements // Ibid — 2006. — 42, N 5. — P. 680–685. 32 ISSN 0572-2691 14. Emets O.A., Ustian N. Yu. Solving of some problems of combinatorial optimizationon arrangements and permutations of game type // Journal of Automation and Information Scienc- es. — 2006. — 38, N 5. — Р. 34–45. 15. Emets O.A., Ustian N. Yu. Studies of problems of combinatorial optimization of game type on arrangements // Ibid. — 2007. — 39, N 1. — Р. 24–35. 16. Emets O.A., Barbolina T.N. Classes of lexicographic equivalence in Euclidean combinatorial optimization on arrangements // Discrete mathematics and applications. — 2007. — 17, N 1. — P. 77–86. 17. Iemets O.A., Olkhovskaja E.V. Iterative method for solving combinatorial optimization problems of the game-type on arrangements // Journal of Automation and Information Sciences. — 2011. — 43, N 5. — Р. 52–63. 18. Iemets O.O., Yemets Ye.M., Oleksiichuk Yu.F. Direct cut-off method for combinatorial optimization problems with additional constraints // Cybernetics and Systems Analysis. — 2011. — 47, N 6. — P. 932–940. 19. Iemets O.O., Yemets O.O. Solving a linear problem of Euclidean combinatorial optimization on arrangements with the constant sum of the elements // Ibid. — 2012. — 48, N 4. — P. 547–557. 20. Sergienko I.V., Iemets O.A., Chernenko O.A. Solving the conditional optimization problem for a fractional linear objective function on a set of arrangements by the branch and bound method // Ibid — 2012. — 48, N 6. — P. 832–836. 21. Iemets O. A., Olkhovskaja E. V. Proving the convergence of the iterative method for solving a game-type combinatorial optimization problem on arrangements // Ibid. — 2013. — 49, N 1. — Р. 86–97. 22. Iemets O. O., Barbolina T.M. Properties of the linear unconditional problem of combinatorial op- timization on arrangements under probabilistic uncertainty // Ibid. — 2016. — 52, N 2. — P. 285–295. 23. Iemets O.O., Barbolina T.M. Solving linear unconstrained problems of combinatorial optimiza- tion on arrangements under stochastic uncertainty // Ibid — 2016. — 52, N 3. — P. 457–466. 24. Iemets O.O., Barbolina T.M. Lexicographic equivalence in mixed combinatorial optimization of linear-fractional functions on arrangements // Ibid. — 2017. — 53, N 2. — P. 244–254. 25. Barbolina T.N. Solution of mixed combinatorial optimization problems on arrangements by the method of construction of lexicographic equivalence // Ibid — 2013. — 49, N 6. — P. 922–931. 26. Iemets O.A., Leonova M.V. Simplex shape of the general permutable polyhedron specified by irreducible system // Journal of Automation and Information Sciences. — 2014. — 46, N 2. — P. 42–55. 27. Yemets O.A., Yemets Ye. M. A modification of the method of combinatorial truncation in optimi- zation problems over vertex-located sets // Ibid. — 2009. — 45, N 5. — P. 785–791. 28. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. — 1984. — 4. — P. 373–395. Получено 15.05.2017 http://www.begellhouse.com/journals/2b6239406278e43e.html?vol=38 http://www.begellhouse.com/journals/2b6239406278e43e.html?vol=38 http://www.begellhouse.com/authors/27fe9d475366940b.html http://www.springerlink.com/content/?Author=O.+O.+Iemets http://www.springerlink.com/content/?Author=O.+O.+Iemets http://www.springerlink.com/content/?Author=O.+O.+Yemetsa http://link.springer.com/search?facet-author=%22E.+V.+Olkhovskaja%22 http://www.dl.begellhouse.com/ru/journals/2b6239406278e43e.html

Оптимизация на размещениях: симплексная форма многогранника размещений

Institution

Similar Items