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

Досліджується фундаментальна система розв’язків системи нерівностей, яка описує переставний многогранник з додатковими обмеженнями, та властивості сусідніх вершин переставного многогранника. The fundamental system of solutions of the system of linear inequalities which describes the permutable polyh...

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859605154470297600
author	Емец, О.А. Устьян, Н.Ю.
author_facet	Емец, О.А. Устьян, Н.Ю.
citation_txt	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2 / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2011. — № 5. — С. 44–51. — Бібліогр.: 5 назв. — рос.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Досліджується фундаментальна система розв’язків системи нерівностей, яка описує переставний многогранник з додатковими обмеженнями, та властивості сусідніх вершин переставного многогранника. The fundamental system of solutions of the system of linear inequalities which describes the permutable polyhedron at additional restrictions; and the properties of the neighbour vertices of the permutable polyhedron are investigated.
first_indexed	2025-11-28T02:52:47Z
format	Article
fulltext	© О.А. ЕМЕЦ, Н.Ю. УСТЬЯН, 2011 44 ISSN 0572-2691 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.85 О.А. Емец, Н.Ю. Устьян ИССЛЕДОВАНИЕ РЕШЕНИЙ ЛИНЕЙНЫХ ЗАДАЧ ЕВКЛИДОВОЙ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ НА ПЕРЕСТАНОВКАХ С ДОПОЛНИТЕЛЬНЫМИ ОГРАНИЧЕНИЯМИ. Часть 2 Введение. В первой части статьи [1] изучены новые свойства вершин пере- становочного многогранника и установлено, что фундаментальную систему реше- ний системы неравенств, которая описывает перестановочный многогранник, об- разуют вершины этого многогранника. Во второй части статьи ставится задача ис- следовать фундаментальную систему решений системы неравенств, которая описывает перестановочный многогранник, с дополнительными ограничениями. Исследование системы неравенств, которая описывает перестановочный многогранник, с дополнительными ограничениями. Рассмотрим определение соседних вершин перестановочного многогранника [2]. Вершинами общего пере- становочного многогранника ),(GПkn соседними с вершиной },...,,{ 1 k ggg  являются все вершины [3], которые получены из g перестановкой компонент, рав- ных 1, ii ee ),(,, 11 GSeeJi iin   и только они (или же в другой записи: 1, ii gg ).,,, 111   iiiik ggGggJi Докажем следующую теорему. Теорема 1. Соседние вершины перестановочного многогранника превраща- ют в равенства 2k неравенства системы (6) из [1] с линейно независимыми ле- выми частями, и никакие другие фундаментальные решения этой системы не пре- вращают в равенства эти 2k неравенства. Любые несоседние вершины превра- щают в равенства не более чем 3k неравенства системы (6) из [1] с линейно независимыми левыми частями. Доказательство. Докажем сначала, что соседние вершины перестановочного многогранника превращают в равенства 2k неравенства системы (6) из [1] с ли- нейно независимыми левыми частями. Для этого исследуем неравенства, обращае- мые в равенства смежными вершинами перестановочного многогранника. Пусть одна из вершин превращает неравенства системы (6) из [1] в равенства (7) из [1]:           ....... ... , , 11 21 1 11 21 1 kll ll l ggxx ggxx gx k Вершины, смежные с этой вершиной, получаются перестановкой компонент 1, ii gg ., 11   iik ggJi Координата, соответствующая ,ig — , il x а 1ig — . 1il x Все первые 1i равенства системы (7) из [1] справедливы и для соседней вер- шины, а i-е равенство выполняться не будет (вместо il x будет :) 1il x  11 ... ill xx Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 45 ,...... 111111 iiiil ggggggx i   1i -е равенство, как и все после- дующие, будут удовлетворяться, так как в них входят одновременно il x и , 1il x а сумма 11   iill ggxx ii меняться не будет. Итак, для смежной вершины, по- лучающейся перестановкой компонент 1, ii gg ,1 kJi ,1 ii gg не будет удовлетворяться i-е равенство из 1k равенств (7) из [1], т.е. соседние вершины одновременно превращают в равенства 2k неравенства системы (6) из [1]. Докажем, что никакое другое фундаментальное решение системы нера- венств (6) из [1] (а это, как было доказано в [1], — одна из вершин перестановочно- го многогранника) не превращает эти же 2k неравенства в равенства. Если это решение удовлетворяет всем первым 1i равенствам, то ,11 gxt  ...,22 gxt  ,, 11   it gx i  и равенствам с 2i по последнее ,1k тогда ...,22   it gx i ., 11   kt gx k  Это фундаментальное решение должно удовлетворять и равен- ству ,1i поэтому .11   iill ggxx ii Учитывая, что фундаментальными реше- ниями системы (6) из [1] являются только вершины перестановочного многогранни- ка, одна из координат 1 , ii ll xx должна быть ,ig а вторая — .1ig Если ,il gx i  ,11   il gx i то это фундаментальное решение совпадает с первой рассматривае- мой вершиной, а если ,, 11 ilil gxgx ii   — то с ее смежной, следовательно, не может быть другого фундаментального решения системы (6) из [1], обращающего эти же 2k неравенства в равенства. Итак, смежные вершины перестановочного многогранника превращают в ра- венства 2k неравенства системы (6) из [1] с линейно независимыми левыми ча- стями, и никакие другие фундаментальные решения этой системы не превращают в равенства эти 2k неравенства. Докажем вторую часть теоремы, заключающуюся в том, что любые несмеж- ные вершины превращают в равенства не более чем 3k неравенств системы (6) из [1] с линейно независимыми левыми частями. Доказывать будем от противно- го. Пусть две несмежные вершины превращают в равенство более чем 3k нера- венств системы (6) из [1] с линейно независимыми левыми частями, т.е. хотя бы 2k неравенства, исключая i-е неравенство. Тогда эти решения удовлетворяют всем первым 1i равенствам, поэтому их элементы ,11 gxt  ,22 gxt  ,, 11   it gx i  и равенствам с 1i по последнее ,1k поэтому элементы 12 12 ...,,    ktit gxgx ki (и равенство , 1 1      k i k i ii gx поэтому ).kt gx k  Учиты- вая 1i и 1i равенства: 11 ...... 11   ill ggxx i и  11 ... ill xx ,... 11  igg получаем, что ,11   iill ggxx ii а поскольку это вершины, то мо- жет быть только два варианта решений: 11 ,   itit gxgx ii и ., 11 itit gxgx ii   Это означает, что рассматриваемые вершины смежные. Получено противоречие, следовательно, несмежные вершины обращать в равенство 2k неравенства си- стемы (6) из [1] не могут. Каждая вершина превращает в равенства 1k нера- венств системы (6) из [1], являясь фундаментальным решением этой системы. Все вершины существенно различны, поэтому в системе (6) из [1] не существует 1r таких линейно независимых неравенств, которые превращаются в равенства для каждого из них. Поэтому любые две вершины не могут обращать в равенства 1k неравенств системы (6) из [1], а значит, любые несмежные вершины пре- вращают в равенство не более 3k неравенств системы (6) из [1] с линейно неза- висимыми левыми частями. Теорема доказана. 46 ISSN 0572-2691 В [4] на основании алгоритма Моцкина–Бургера [3, 5] сформулирована тео- рема 3.2. Если lvv ...,,1 )1( l — фундаментальная система )(CV решений си- стемы линейных неравенств 0...)( 11  njnjj xaxaxl ),1( mj  (1) ранга n над пространством nP и 0...)( 11  nnxaxaxl — произвольное ли- нейное неравенство над ,nP то те элементы ,iv для которых ,0)( ivl и те эле- менты )()(),( qppq vlvvlvqpv  (2) с 0)(/)( qp vlvl (отличающиеся один от другого хотя бы одним из индексов ,p q), для каждого из которых существуют 2n линейно независимых неравенств ,0)( xl j обращающихся в равенства как для ,pv так и для ,qv составляют фун- даментальную систему решений системы      .0)( ,,1,0)( xl mjxl j (3) Если таких элементов не существует, то система (3) не имеет фундаменталь- ных решений. Среди неравенств системы (1), обращаемых в равенство как элементом ,pv так и элементом qv системы ),(CV тогда и только тогда существует 2n линей- но независимых неравенств, когда ни один из других элементов системы )(CV не превращает все их в равенства. В работе [3, с. 92] в лемме приводится немного другая формула, которая является основной в предложенном в этой работе графическом методе: , )()( )()( k j k i j k ii k j dd PdPd P    где ji PP , — две точки (в наших обозначениях — pv и ).qv В доказательстве леммы сказано, что отрезок ,)1( ji PttP  который соединяет точки iP и ,jP пересекает гиперплоскость только тогда, когда в интервале ]1,0[ существует такое t: .0)1( )()(  k j k i dttd В наших обозначениях  ))1(( ji PttPl ,0)()1()(  ji PltPtl т.е. )( )( pk i vld  и ).( )( qk j vld  Тогда формула приобре- тет такой вид: , )()( )()( ),( qp pqqp vlvl vlvvlv qp    .0)(/)( qp vlvl Если ,0)(,0)(  qp vlvl то . )()( )()( )()( )()( )()( )()( ),( qp qppq qp pqqp qp pqqp vlvl vlvvlv vlvl vlvvlv vlvl vlvvlv qp          Если ,0)(,0)(  qp vlvl то . )()( )()( )()( )()( )()( )()( ),( qp qppq qp pqqp qp pqqp vlvl vlvvlv vlvl vlvvlv vlvl vlvvlv qp          Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 47 Итак, в обоих возможных случаях значений )( pvl и )( qvl формула , )()( )()( k j k i j k ii k j dd PdPd P    приведенная в [3], в наших обозначениях имеет вид , )()( )()( ),( qp qppq vlvl vlvvlv qp    (4) причем этот элемент ),( qp является точкой пересечения отрезка, который со- единяет точки pv и ,qv и гиперплоскости .0...)( 11  nnxaxaxl Докажем следующее утверждение. Теорема 2. Элементы ),( qp (4) будут фундаментальными решениями си- стемы неравенств (3), несущественно различными для ),( qp (2), поэтому при переходе от системы неравенств (1) к (3) вместо элементов ),( qp в фундамен- тальную систему новой системы неравенств (3) можно включать ).,( qp Доказательство будем проводить аналогично доказательству п. 2а теоре- мы 3.1 из [4, с. 225–231]. Приведем вначале необходимые обозначения из [4]. Пусть C — конус решений системы (1) однородных линейных неравенств ранга 0r над пространством ,nP )(CH — его максимальное линейное подпростран- ство, C — конус решений системы (3) [4, с. 223]. Рассмотрим лемму 3.1 из [4, с. 226]. Пусть 1x и 2x — два существенно раз- личные фундаментальные решения системы (1) ранга r ).1( r Тогда справедли- вы следующие утверждения: а) если хотя бы один из коэффициентов комбинации 2 2 1 1 xpxp  ),( 21 Ppp  отличен от нуля, то );(2 2 1 1 CHxpxp  б) если элементы 1x и 2x превращают в равенства некоторые 2r линейно независимых неравенства системы (1), то для произвольного элемента ,0 nPx  обращающего в равенства те же неравенства, существуют такие элементы 1p и 2p поля ,P что )(2 2 1 1 0 CHxpxpx  (при 2r 0x — произвольный эле- мент из );nP в) если при условиях предыдущего пункта элементы ,0x 1x и 2x входят в одну и ту же фундаментальную систему решений системы (1), то элемент 0x совпадает либо с ,1x либо с .2x Рассмотрим следствие 2.13 из [4, с. 166]. Для того чтобы два фундаменталь- ные решения x( и )x  системы (9) были несущественно различными, необходи- мо и достаточно, чтобы существовал такой положительный элемент ,Pp для которого разность xxp  была бы ее несущественным решением. Вернемся к доказательству теоремы 2. Отметим вначале, что поскольку эле- мент ),( )()( 1 )()( )()( ),( qp vlvlvlvl vlvvlv qp qpqp qppq       и неравенства си- стем (1) и (3) линейные, то если элемент ),( qp удовлетворяет какому-либо не- равенству систем неравенств (1) и (3), то и элемент ),( qp тоже будет удовле- творять этому неравенству, а если элемент ),( qp превращает какое-либо неравенство систем неравенств (1) и (3) в равенство, то и элемент ),( qp тоже будет обращать это неравенство в равенство. 48 ISSN 0572-2691 В доказательстве п. 2а теоремы 3.1 из [4, с. 225–231] сказано, что все элемен- ты, рассматриваемые в п. 2а теоремы, очевидно, содержатся в конусе .C Итак, если элементы ),( qp удовлетворяют всем неравенствам системы (3), то и ),( qp тоже будут удовлетворять всем неравенствам системы (3), а значит, бу- дут содержаться в конусе .C Покажем, что элементы ),( qp — фундаментальные решения системы (3). Из п. а) леммы 3.1 из [4, с. 226] вытекает, что ).()(),( CHCHqp  В доказательстве п. 2а теоремы 3.1 из [4, с. 225–231] сказано, что из определения элемента ),( qp вытекает, что он является решением системы (3) и превращает в равенства 2r ли- нейно независимых неравенств, общих с системой (1), и ее неравенство .0)( xl По- следнее не может линейно выражаться (над P) этими 2r неравенствами, так как вопреки предположению, оно обращалось бы в равенство для элементов pv и .qv Следовательно, элемент ),( qp превращает в равенство 1r линейно независимых неравенств системы (3). Отсюда следует, что и элемент ),( qp превращает в равен- ство 1r линейно независимых неравенств системы (3). В том же доказательстве говорится, что в рассматриваемом случае ранг последней [системы (3)] совпадает с r, тем самым доказана фундаментальность решений ).,( qp А в нашем случае из этого следует фундаментальность ).,( qp Кроме того, фундаментальные решения ),( qp и ),( qp превращают в равен- ства одинаковые 1r линейно независимые неравенства системы (3), поэтому они являются несущественно различными фундаментальными решениями си- стемы (3). Итак, доказано, что ),( qp — фундаментальные решения системы (3), не- существенно различные для ).,( qp Докажем теперь, что все фундаментальные решения iv и ),( qp системы (3) существенно различны. Обратимся опять к теореме 3.1, где утверждается, что по- скольку ),()( CHCH  то для любых двух элементов iv это не требует доказа- тельства. Если несущественно различны какие-нибудь два элемента: iv и ),,( qp то в силу следствия 2.13 из [4, с. 166] существует такой положительный элемент ,Pt что ).()(),( CHCHqpvtvi  Отсюда вытекает, что элемент iv превращает в равенства те и только те неравенства системы (1), которые превра- щаются в равенства для обоих элементов: pv и .qv Поэтому существует 1r линейно независимых неравенств системы (1), обращающихся в равенства как для ,pv так и для ,qv что невозможно, так как элементы pv и qv содержатся в одной и той же фундаментальной системе решений системы (1) и, значит, существенно различны. Следовательно, любые два фундаментальных решения iv( и )),( qp существенно различны. Если несущественно различны фундаментальные решения ),( 11 qp и ),( 22 qp системы (3), отличающиеся своими индексами, но не их порядком, то в силу следствия 2.13 из [4, с. 166] существует такой положительный элемент ,Pd  что ).()(),(),( 2211 CHCHqpdqp  Отсюда вытекает, что элемент ),( 11 qp (элемент ),( 22 qp ) превращает в равенства те и только те неравен- ства системы (1), которые превращаются в равенства для обоих элементов: 2p  и 2q  1( p  и ).1q  Но тогда существует 2r таких линейно независимых нера- венств системы (1), которые превращаются в равенства для всех элементов ,1p  Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 49 ,1q  ,2p  .2q  На основании п. в) леммы 3.1 из [4, с. 226] вытекает, что обе па- ры ),( 11 qp  и ),( 22 qp  составлены из одних и тех же элементов. Поэтому, вопреки предположению, рассматриваемые фундаментальные решения ),( 11 qp и ),( 22 qp не отличаются своими индексами. Следовательно, существенно раз- личны и все фундаментальные решения ),( qp системы (1). Докажем, что произвольное фундаментальное решение  системы (3) несу- щественно отличается хотя бы от одного из рассматриваемых фундаментальных решений системы (3). Это означает, что они составляют фундаментальную систему решений последней. В теореме 3.1 из [4, с. 225–231] доказано, что hqq jj  21 21 ))()(( CHCHh  и ,0, 21 qq а также, что 0)( 1  j l и .0)( 2  j l Поскольку из 0)( l и 0, 21 qq вытекает, что ,0)(/)( 21  jj ll то вместе с этим доказано, что элемент )()( )()( )()( )( )()( )( 21 1221 21 1 2 21 2 1 jj jjjj jj j j jj j j ll ll ll l ll l          является одним из элементов ),( qp теоремы, которая доказывается. В теореме 3.1 из [4, с. 225–231] говорится, что из отношения 0)( l вы- текает также, что .0)()()( 21 21  jj lqlql Но тогда )( )( 2 1 1 2 j j l lq q    и раз- ложение  1 1 j q hq j  2 2 сведется к виду     h l lq qhqq j j j jjj 2 2 1 121 )( )(1 121    hll l q jjjj j ))()(( )( 1221 2 1 ,),( )()( )()( )( ))()(( 21 1 21 1221 2 21 hjjqh ll ll l llq jj jjjj j jj               где . )( ))()(( 2 21 1 j jj l llq q    Поскольку ),(CHh  то это означает, что фунда- ментальное решение  системы (3) несущественно отличается от ее фундамен- тального решения ).,( 21 jj Теорема 2 доказана. Основываясь на теореме 3.2 из [4, с. 234] и теоремах 1 и 2, получаем, что при до- бавлении неравенства-ограничения 0)( xl к системе неравенств (6) из [1] с )(CV (фундаментальной системой решений системы (6) из [1] являются вершины переста- новочного многогранника), те ),(CVvi  для которых ,0)( ivl будут присутство- вать в новой фундаментальной системе )(CV системы неравенств, состоящей из си- стемы (6) из [1] и неравенства .0)( xl Те ),(CVvi  которые не удовлетворяют не- равенству ,0)( xl не войдут в новую ).(CV Если, например, вершина qv  не удовлетворяет ограничению ,0)( xl то для нее .0)( qvl Тогда хотя бы одна из вер- 50 ISSN 0572-2691 шин, смежных с ней, удовлетворяет неравенству 0)( pvl и .0)(/)( pq vlvl Вер- шины qv и pv смежные, поэтому они будут обращать в равенства 2k неравенств системы (6) из [1] с линейно независимыми левыми частями, и никакие другие фун- даментальные решения этой системы не превращают в равенства эти 2k неравен- ства. Поэтому в новую )(CV войдет элемент , )()( )()( ),( qp qppq vlvl vlvvlv qp    кото- рый является точкой пересечения отрезка, соединяющего смежные вершины переста- новочного многогранника pv и ,qv и гиперплоскости ,0...)( 11  nnxaxaxl и, следовательно, не будет являться вершиной перестановочного многогранника, по- этому такие элементы нас не интересуют. Следовательно, после включения последо- вательно всех дополнительных ограничений к системе неравенств (6) из [1], в конеч- ную фундаментальную систему решений полученной системы неравенств , 11 j i j i j gx j      ,,,, 11   kirjkj JiJrjrjJ (5) ,0)( th Jhxl  войдут только те вершины перестановочного многогранника, которые удовлетво- ряют всем включаемым ограничениям .0)( th Jhxl  Кроме того, вершины перестановочного многогранника удовлетворяют ра- венству . 11 i k i i k i gx    Добавив к системе неравенств (5) поочередно неравенства i k i i k i gx    11 и i k i i k i gx    11 (к которым сводится равенство ), 11 i k i i k i gx    получим систему , 11 j i j i j gx j      ,,,, kirjkj JiJrjrjJ  , 1 1      k i k i ii gx (6) .0)( th Jhxl  Фундаментальные решения (вершины перестановочного многогранника), которые удовлетворяют всем дополнительным ограничениям в системе (5), удовлетворяют также и обоим неравенствам      k i k i ii gx 1 1 и , 1 1      k i k i ii gx поэтому согласно приведенной выше теореме 3.2 из [4, с. 234], они, и только они, войдут в фундаментальную систему решений системы неравенств (6). Заключение. Исследование фундаментальной системы решений системы ли- нейных неравенств, которая описывает перестановочный многогранник, с дополни- тельными ограничениями дает возможность распространить метод выведения об- щей формулы решений системы линейных неравенств из [4] для определения этой фундаментальной системы, что и будет сделано в третьей части настоящей статьи. Приложение 1. Пример доказательства теоремы 1 Пусть ,4k }.1,0;2,0;3,0;4,0{xP Вершина }1,0;2,0;3,0;4,0{1 X пре- вращает в равенства 31k неравенства системы (3): Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 51 .9,02,03,04,0 7,03,04,0 4,0 321 21 1    xxx xx x Рассмотрим смежную с вершиной 1X вершину },1,0;3,0;2,0;4,0{2 X для ко- торой переставлены элементы 3,02 g и ,2,03 g тогда .2i Все 11i равен- ства выполняются (первое равенство справедливо, так как ),4,01 x i-е равенство не справедливо (в нашем случае второе), так как 6,02,04,021  xx для .2X Остальные равенства, начиная с ,31i выполняются (у нас третье). Итак, смежная вершина 2X удовлетворяет двум равенствам ).2242( k О.О. Ємець, Н.Ю. Устьян ДОСЛІДЖЕННЯ РОЗВ’ЯЗКІВ ЛІНІЙНИХ ЗАДАЧ ЕВКЛІДОВОЇ КОМБІНАТОРНОЇ ОПТИМІЗАЦІІ НА ПЕРЕСТАНОВКАХ З ДОДАТКОВИМИ ОБМЕЖЕННЯМИ. Частина 2 Досліджується фундаментальна система розв’язків системи нерівностей, яка описує переставний многогранник з додатковими обмеженнями та властивості сусідніх вершин переставного многогранника. O.A. Yemets, N.Yu. Ustian THE INVESTIGATION OF THE SOLUTIONS OF LINEAR PROBLEMS OF EUCLIDEAN COMBINATORIAL OPTIMIZATION ON ARRANGEMENTS WITH ADDITIONAL RESTRICTIONS. Part II The fundamental system of solutions of the system of linear inequalities which describes the permutable polyhedron at additional restrictions; and the properties of the neighbour verteces of the permutable polyhedron are investigated. 1. Емец О.А., Устьян Н.Ю. Исследование решений линейных задач евклидовой комбинатор- ной оптимизации на перестановках с дополнительными ограничениями. Часть 1 // Между- народный научно-технический журнал «Проблемы управления и информатики». — 2011. — № 2. — С. 26–32. 2. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Киев : ІСДО, 1993. — 188 с. 3. Метод двойного описания / Т.С. Моцкин, Х. Райфа, Дж.Л. Томпсон, Р.М. Тролл // Сб. пере- водов «Матричные игры» / Под ред. Н.Н. Воробьева. — М. : Физматгиз, 1961. — С. 81–109. 4. Черников С.Н. Линейные неравенства. — М. : Наука, 1968. — 488 с. 5. Burger E. Über homogene lineare Ungleichungssysteme // Zeitschrift für Angewandte Mathemat- ik und Mechanik. — 1956. — 36, N 3/4. — P. 135–139. Получено 13.01. 2010
id	nasplib_isofts_kiev_ua-123456789-207337
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Russian
last_indexed	2025-11-28T02:52:47Z
publishDate	2011
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Емец, О.А. Устьян, Н.Ю. 2025-10-06T15:38:53Z 2011 Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2 / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2011. — № 5. — С. 44–51. — Бібліогр.: 5 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207337 519.85 10.1615/JAutomatInfScien.v43.i10.60 Досліджується фундаментальна система розв’язків системи нерівностей, яка описує переставний многогранник з додатковими обмеженнями, та властивості сусідніх вершин переставного многогранника. The fundamental system of solutions of the system of linear inequalities which describes the permutable polyhedron at additional restrictions; and the properties of the neighbour vertices of the permutable polyhedron are investigated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2 Дослідження розв’язків лінійних задач евклідової комбінаторної оптимізації на перестановках з додатковими обмеженнями. Частина 2 The Investigation of the Solutions of Linear Problems of Euclidean Combinatorial Optimization on Arrangements with Additional Restrictions. Part II Article published earlier
spellingShingle	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2 Емец, О.А. Устьян, Н.Ю. Оптимальное управление и методы оптимизации
title	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2
title_alt	Дослідження розв’язків лінійних задач евклідової комбінаторної оптимізації на перестановках з додатковими обмеженнями. Частина 2 The Investigation of the Solutions of Linear Problems of Euclidean Combinatorial Optimization on Arrangements with Additional Restrictions. Part II
title_full	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2
title_fullStr	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2
title_full_unstemmed	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2
title_short	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 2
title_sort	исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. часть 2
topic	Оптимальное управление и методы оптимизации
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207337
work_keys_str_mv	AT emecoa issledovanierešeniilineinyhzadačevklidovoikombinatornoioptimizaciinaperestanovkahsdopolnitelʹnymiograničeniâmičastʹ2 AT ustʹânnû issledovanierešeniilineinyhzadačevklidovoikombinatornoioptimizaciinaperestanovkahsdopolnitelʹnymiograničeniâmičastʹ2 AT emecoa doslídžennârozvâzkívlíníinihzadačevklídovoíkombínatornoíoptimízacíínaperestanovkahzdodatkovimiobmežennâmičastina2 AT ustʹânnû doslídžennârozvâzkívlíníinihzadačevklídovoíkombínatornoíoptimízacíínaperestanovkahzdodatkovimiobmežennâmičastina2 AT emecoa theinvestigationofthesolutionsoflinearproblemsofeuclideancombinatorialoptimizationonarrangementswithadditionalrestrictionspartii AT ustʹânnû theinvestigationofthesolutionsoflinearproblemsofeuclideancombinatorialoptimizationonarrangementswithadditionalrestrictionspartii

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

Репозитарії

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