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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Емец, О.А., Устьян, Н.Ю.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Оптимальное управление и методы оптимизации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207447
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3 / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2012. — № 1. — С. 54–61. — Бібліогр.: 6 назв. - рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207447
record_format	dspace
spelling	irk-123456789-2074472025-10-08T00:02:13Z Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3 Дослідження розв’язків лінійних задач евклідової комбінаторної оптимізації на перестановках з додатковими обмеженнями. Частина 3 Investigation of the Solutions of Linear Problems of Euclidean Combinatorial Optimization on Arrangements with Additional Restrictions. Part III Емец, О.А. Устьян, Н.Ю. Оптимальное управление и методы оптимизации Досліджується поширення відомого методу розв’язування систем лінійних нерівностей для знаходження загальної формули точок переставного многогранника при додаткових обмеженнях. The known method of decision of systems of linear inequalities for finding a general formula of points of a permutable polyhedron at additional restrictions is investigated. 2012 Article Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3 / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2012. — № 1. — С. 54–61. — Бібліогр.: 6 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207447 519.85 10.1615/JAutomatInfScien.v44.i2.30 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Емец, О.А. Устьян, Н.Ю. Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3 Проблемы управления и информатики
description	Досліджується поширення відомого методу розв’язування систем лінійних нерівностей для знаходження загальної формули точок переставного многогранника при додаткових обмеженнях.
format	Article
author	Емец, О.А. Устьян, Н.Ю.
author_facet	Емец, О.А. Устьян, Н.Ю.
author_sort	Емец, О.А.
title	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3
title_short	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3
title_full	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3
title_fullStr	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3
title_full_unstemmed	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3
title_sort	исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. часть 3
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207447
citation_txt	Исследование решений линейных задач евклидовой комбинаторной оптимизации на перестановках с дополнительными ограничениями. Часть 3 / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2012. — № 1. — С. 54–61. — Бібліогр.: 6 назв. - рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT emecoa issledovanierešenijlinejnyhzadačevklidovojkombinatornojoptimizaciinaperestanovkahsdopolnitelʹnymiograničeniâmičastʹ3 AT ustʹânnû issledovanierešenijlinejnyhzadačevklidovojkombinatornojoptimizaciinaperestanovkahsdopolnitelʹnymiograničeniâmičastʹ3 AT emecoa doslídžennârozvâzkívlíníjnihzadačevklídovoíkombínatornoíoptimízacíínaperestanovkahzdodatkovimiobmežennâmičastina3 AT ustʹânnû doslídžennârozvâzkívlíníjnihzadačevklídovoíkombínatornoíoptimízacíínaperestanovkahzdodatkovimiobmežennâmičastina3 AT emecoa investigationofthesolutionsoflinearproblemsofeuclideancombinatorialoptimizationonarrangementswithadditionalrestrictionspartiii AT ustʹânnû investigationofthesolutionsoflinearproblemsofeuclideancombinatorialoptimizationonarrangementswithadditionalrestrictionspartiii
first_indexed	2025-10-08T01:09:56Z
last_indexed	2025-10-09T01:05:28Z
_version_	1845464325363335168
fulltext	© О.А. ЕМЕЦ, Н.Ю. УСТЬЯН, 2012 54 ISSN 0572-2691 УДК 519.85 О.А. Емец, Н.Ю. Устьян ИССЛЕДОВАНИЕ РЕШЕНИЙ ЛИНЕЙНЫХ ЗАДАЧ ЕВКЛИДОВОЙ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ НА ПЕРЕСТАНОВКАХ С ДОПОЛНИТЕЛЬНЫМИ ОГРАНИЧЕНИЯМИ. Часть 3 Введение. Используя исследование фундаментальной системы решений си- стемы неравенств, которая описывает перестановочный многогранник без ограни- чений и с дополнительными ограничениями [1, 2], в третьей части статьи исследу- ется возможность применения метода решения систем линейных неравенств [3, 4] для нахождения общей формулы точек перестановочного многогранника при до- полнительных ограничениях. Распространение метода решения систем линейных неравенств для нахождения общей формулы точек перестановочного многогранника при дополнительных ограничениях. Рассмотрим применение метода Н.В. Чернико- вой для нахождения общей формулы неотрицательных решений системы ли- нейных уравнений [3, с. 239–264], точнее, использование этого метода для нахождения общей формулы решений системы линейных неравенств (6) из [2]. Этот алгоритм из [3, с. 260, 261], разработанный Н.В. Черниковой на основе ме- тода Моцкина–Бургера [5, 6], заключается в следующем. Рассмотрим процесс нахождения общей формулы неотрицательных решений системы линейных уравнений 0...)( 11  njnjj xaxaxl ),1( mj  (1) согласно [3, с. 256]. Для системы (1) составляется таблица . ... ... ... 1...0 ... 0...1 )( 1 111 1 2 1 1 1            mnn m aa aa SSS Пусть по ней составлены таблицы ....,, 12 iSS Тогда для построения таблицы iS в правой части таблицы 1iS выделяется произвольный ненулевой столбец (если он имеется), например первый столбец; его называют основным столбцом таблицы .1iS В очередную таблицу )( 21 iii SSS  переносятся без изменений те строки таблицы ,1iS на пересечении которых с основным столбцом стоят нули (если такие строки имеются). Далее в таблице 1iS выделяется любая пара строк, на пересечении которых с основным столбцом находятся ненулевые элементы противоположных знаков. Такую пару строк называют допустимой парой. Если таблица 1iS содержит больше двух строк и существуют столбцы таблицы ,1 iS которые пересекают по нулевым элементам обе строки допустимой пары, но не существует никакой другой строки таблицы ,1iS пересекающейся по нулевым элементам со всеми столбцами такого рода, то при этом условии допустимая пара строк называется уравновешенной. Если таблица 1iS содержит только две стро- ки и они составляют допустимую пару, то последняя считается уравновешенной. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 55 Строкой равновесия уравновешенной пары строк называется такая их линейная комбинация с положительными коэффициентами из поля ,P которая пересекает- ся по нулевому элементу с основным столбцом. Строки равновесия всех уравно- вешенных пар строк таблицы 1iS переносятся в таблицу .iS На этом составле- ние таблицы iS заканчивается. Через конечное число шагов рассматриваемый процесс оканчивается, так как в правой части очередной таблицы либо не окажется ненулевых столбцов, либо столбец, который принят за основной, не содержит нулей и не определяет уравно- вешенных пар строк. В первом случае минимальную систему образующих конуса неотрицательных решений системы (1) составляют строки левой части последней из таблиц ,iS а во втором получается, что этот конус не содержит ненулевых элементов. К вопросу нахождения общей формулы неотрицательных решений системы линейных уравнений сводится вопрос получения общей формулы решений систе- мы линейных неравенств [3, c. 260, 261]. В случае системы (1) из [2] однородных линейных неравенств можно рассматривать равносильную ей систему линейных уравнений jnjnjj uxaxaxl  ...)( 11 ),1( mj  с неотрицательными пара- метрами .ju Считая ранг r системы (1) из [2] отличным от нуля, к написанной си- стеме линейных уравнений применяется алгоритм Гаусса для исключения неизвест- ных. При этом формулы для неизвестных уравнений и уравнения для параметров имеют следующий вид: nrnsrsrsrss xaxaububx   ...... 1111 rJs и ,...11 irrrii uucuc  ....,,2,1 rmi  Если ,rm  то уравнений здесь не будет, поэтому полученные формулы вы- разят общее решение системы (1) из [2]. При ,mr  пользуясь приведенной выше вычислительной схемой, можно получить формулу )...,,()...,,( 1 1 1 k m k k l k m uupuu    с произвольными неотрицательными параметрами lpp ...,,1 для неотрицательных решений записанной системы уравнений. Найдем из нее выражения для muu ...,,1 и подставим их в предыдущие формулы, в результате получим формулы sx irsi rn i k rsr k sk l k xaububp      1 11 1 )...( ,rJs определяющие все решения си- стемы (1) из [2] однородных линейных неравенств. Случай системы неоднород- ных линейных неравенств 0...11  jnjnj axaxa ),1( mj  сводится к рас- смотренному случаю следующим образом. Произвольному неотрицательному решению )...,,( 00 1 nxx этой системы отвечает неотрицательное решение )1,...,,( 00 1 nxx системы 0... 111  njnjnj xaxaxa ),1( mj  (2) однородных линейных уравнений, и наоборот. Поэтому нахождение общей фор- мулы неотрицательных решений системы неоднородных линейных неравенств сводится к отысканию всех неотрицательных решений системы (2), имеющих равную единице последнюю координату. Рассмотрим теперь распространение описанного выше метода Н.В. Чернико- вой [3, с. 260, 261] для нахождения общей формулы решений системы линейных неравенств (6) из [2]. 56 ISSN 0572-2691 При сведении неравенств системы линейных неравенств (6) из [2] к равен- ствам (вводя неотрицательные параметры )ju выбираем равенства для вычисле- ния значений переменных ix 1 kJi из равенств, соответствующих неравен- ствам, которые описывают перестановочный многогранник (пусть им соответ- ствуют ju ,rJj r — ранг системы неравенств (6) из [2]). Все остальные будут иметь вид 0...11  irrr uucuc ,rMJi  где M — количество неравенств системы неравенств (6) из [2]. Следовательно, в каждом из таких равенств при- сутствуют параметры ruu ...,,1 и один элемент iru  ,rMJi  который больше не присутствует ни в одном из таких равенств, а значит, в таблицах ,2 j S ...,,2,1j в строках rMr  ...,,1 в столбце i rMJi  будут стоять 1, а во всех других столбцах — 0. Назовем эти строки строками, дающими перестановки (смысл названия будет понятен позже). Учитывая правила переноса строк из 1jS в ,jS ...,,3,2j получается, что эти строки ( rMr  ...,,1 ) будут переноситься в следующую таблицу ,jS ...,,3,2j до тех пор, пока основным столбцом не будет выбран тот столбец ,i ,rMJi  в котором стоит 1. В процессе преобразования таблицы S сначала в качестве основных столбцов выбираем первые tM  столбцов, т.е. не выбираем столбцы, которые отвечают дополнительным t неравенствам-ограничениям. Поскольку для вычисления зна- чений переменных ix 1 kJi нужны только значения ,...,,1 ruu то значения остальных параметров iru  rMJi  можно не вычислять. Поэтому при пере- ходе от таблицы 1jS к ,jS ...,,3,2j в таблице j S1 в строках равновесия в столбцах, соответствующих ,iu ,...,,1 rMri  элементы будут равны 0, если оба соответствующих элемента допустимых строк равны 0; и 1 — в противопо- ложном случае (их реальные значения нам не нужны). Если бы дополнительных ограничений не было, то в последней таблице wS строки составляли бы минимальную систему образующих элементов конуса неот- рицательных решений системы уравнений для параметров iu .MJi Как было доказано в [1] (теорема 4), произвольное решение системы неравенств, описы- вающих перестановочный многогранник (3) из [1], выражается формулой , 1 k k l k xpx    где lpp ...,,1 — произвольные неотрицательных элементы поля P, а kx — вершины перестановочного многогранника (3) из [1]. Следовательно, число строк таблицы wS должно быть равно количеству параметров ,...,,1 lpp т.е. количеству вершин перестановочного многогранника ,l и каждая строка со- ответствует одной из вершин. Для каждого дополнительного ограничения в таб- лицу ,jS ...,,2,1j добавляется по одной строке, дающей перестановки, кото- рые будут переноситься в следующую таблицу ,jS ...,,3,2j до тех пор, пока основным столбцом не будет выбран тот столбец ,i ,rMJi  в котором стоит 1 в данной строке. После выбора основными столбцами первых tM  столбцов таблица 1tMS будет состоять из l строк, соответствующих вершинам переста- новочного многогранника и t строк, соответствующих перестановкам. В [3] сформулировано следующее свойство таблиц ,jS ....,2,1j Скалярное произведение любого вектора-строки левой части таблицы с ,}...,,,{ 21 iniii aaaa  Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 57 mJi (элементы i-го столбца таблицы ,2 j S ...),2,1j равно числу, стоящему на пересечении соответствующей строки этой таблицы с i-м столбцом правой ее части. Иными словами, если x — строка левой части таблицы ,jS ...,,2,1j то элемент i-го столбца таблицы j S2 равен ).(xli Учитывая теорему 3.2 из [3, с. 234], вопрос о включении каждого фундаментального решения в фундаментальную си- стему решений новой системы неравенств зависит от значения ),(l где  — фун- даментальное решение, а 0)( xl — добавляемое неравенство, поэтому если x — строка левой части таблицы ,jS ...,,2,1j соответствующая вершине ,l k Jkx  то элемент основного столбца таблицы j S2 этой строки равен ).( kxl Если же вершина перестановочного многогранника l k Jkx  удовлетворяет до- бавляемому ограничению ,0)( kxl то элемент основного столбца таблицы j S2 для строки, соответствующей данной вершине, будет отрицательным; а если вер- шина не удовлетворяет присоединяемому ограничению — положительным. Если вершина превращает дополнительное ограничение в 0, то в соответствующей ей строке в основном столбце будет стоять ноль, поэтому данная строка будет пере- несена в следующую таблицу ...,3,2, jS j (рассматриваемая вершина войдет в фундаментальную систему новой системы неравенств). Из всех строк, соответ- ствующих перестановкам, только у одной в основном столбце стоит 1 и она не переносится в следующую таблицу ...,3,2, jS j У остальных строк, соответ- ствующих перестановкам, в основном столбце стоит 0, поэтому они переносятся в следующую таблицу ...,3,2, jS j Итак, остаются для рассмотрения следую- щие строки: строка, соответствующая перестановкам, у которой в основном столбце стоит 1, а в остальных — нули; строки, соответствующие вершинам пере- становочного многогранника, у которых в основном столбце стоят положитель- ные и отрицательные значения. Строка, соответствующая перестановкам, будет составлять допустимую пару с каждой строкой, у которой в основном столбце стоит отрицательное значение. В левой части таблицы ...,,3,2, jS j в строках, соответствующих перестановкам, как и в правой части этой таблицы, в одном из столбцов с номером r стоит 1, а в остальных — 0. Следовательно, если в допу- стимой паре строк одной из допустимых строк является строка, соответствующая перестановкам, то она не влияет на значения ,...,,1 ruu которые будут использо- ваться при вычислении ;1 ki Jix и если второй допустимой строкой является строка, соответствующая вершине перестановочного многогранника, то в строке равновесия значения ruu ...,,1 не изменятся. Это соответствует случаю, когда вершина удовлетворяет дополнительному ограничению и переносится в фунда- ментальную систему новой системы неравенств. В строках, соответствующих вершинам перестановочного многогранника, которые не удовлетворяют допол- нительному ограничению, в основном столбце стоит положительное значение, поэтому они не образуют допустимых пар строк со строкой, дающей переста- новки и согласно теореме 3.2 [3] не войдут в фундаментальную систему новой системы неравенств. На основании этой же теоремы и теоремы 6 из [2] в фундаментальную систему новой системы неравенств должны войти элемен- ты , )()( )()( ),( qp qppq vlvl vlvvlv qp    причем точки pv и qv будут смежными вершинами перестановочного многогранника, одна из которых удовлетворяет до- 58 ISSN 0572-2691 полнительному ограничению, а вторая нет (только соседние вершины превраща- ют 2r неравенства в равенства). Для таблицы jS это означает, что уравнове- шенную пару строк составят строки, соответствующие смежным вершинам, если в основном столбце одной из строк стоит положительный элемент (вершина удо- влетворяет дополнительному ограничению), а во второй строке — отрицательное значение. Такая уравновешенная пара строк даст строку равновесия, соответ- ствующую элементу ),,( qp который не является вершиной перестановочного многогранника, поэтому такие строки равновесия включать в следующую табли- цу ...,,3,2, jS j не будем. Исходя из вышесказанного, сформулируем дополнительные правила по при- менению метода Н.В. Черниковой [3, с. 239–264] для получения общей формулы решений системы линейных неравенств (6) из [2]. Пусть M — количество неравенств системы неравенств (6) из [2], а t — ко- личество дополнительных ограничений, и в таблице 1 2S столбцы, соответствую- щие дополнительным t ограничениям, стоят в конце. Правило 1. В процессе преобразования таблицы S сначала в качестве ос- новных столбцов выбираем первые tM  столбцов. Правило 2. При переходе от таблицы 1jS к ...,,3,2, jS j в таблице j S1 в строках равновесия в столбцах, соответствующих rMriui  ...,,1, , элемен- ты будут равны 0, если оба соответствующих элемента допустимых строк равны 0; и 1 — в противном случае. Правило 3. При выборе основными столбцами последних t столбцов, со- ответствующих дополнительным ограничениям, в следующую таблицу ,jS ...,,3,2j переносятся только те строки равновесия, у которых одной из уравно- вешенных допустимых строк является строка, дающая перестановки, с 1 в основ- ном столбце. Это условие гарантирует, что в следующую таблицу будут перено- ситься только те строки, которые соответствуют вершинам перестановочного многогранника. Заключение. Доказанные в статье утверждения о новых свойствах вершин перестановочного многогранника, представлении произвольной точки многогран- ника через линейную комбинацию его вершин и о фундаментальных решениях системы линейных неравенств (6) из [2] дают возможность распространить метод нахождения общей формулы решений системы линейных неравенств из [3] для системы неравенств, которая описывает перестановочный многогранник, с до- полнительными ограничениями. Дальнейшие исследования могут быть направлены на установление времен- ных оценок работы данного метода и повышение его эффективности работы. Приложение. Иллюстрация распространения метода Н.В. Черниковой на числовом примере Пусть },4,0;6,0{G .0225)( 21  xxxl Тогда систему (6) из [2] за- пишем               .0225 ,1 ,1 ,6,0 ,6,0 21 21 21 2 1 xx xx xx x x Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 59 Найдем общую формулу решений системы . .0225 ,0 ,0 ,06,0 ,06,0 321 321 321 32 31               xxx xxx xxx xx xx Для этого составим систему уравнений                  63 5321 4321 3321 232 131 ,225 , , ,6,0 ,6,0 ux uxxx uxxx uxxx uxx uxx и применим к ней алгоритм Гаусса для исключения неизвестных. При этом она запишется в виде                  .60 ,5550 ,0 ,555 ,6,0 ,6,0 5321 6321 43 3213 232 131 uuuu uuuu uu uuux uxx uxx Отсюда получаем формулы         3213 3212 3211 555 ,323 ,332 uuux uuux uuux и систему уравнений         06 ,0555 ,0 5321 6321 43 uuuu uuuu uu для неотрицательных параметров .,,,,, 654321 uuuuuu Составим таблицу . 010 100 001 151 150 650 100000 010000 001000 000100 000010 000001 )( 1 2 1 1 1                         SSS 60 ISSN 0572-2691 Третий столбец таблицы 1 2S соответствует дополнительному ограничению, поэтому в качестве основных столбцов сначала выберем первые два столбца (со- гласно сформулированному правилу 1). Считая основным столбцом первый стол- бец таблицы ,1 2S в следующую таблицу 2S будем переносить строки 1, 2, 5 и 6 (поскольку элементы этих строк, которые стоят в основном столбце, равны 0). Получим таблицу . 010 100 150 650 100000 010000 000010 000001 )( 2 2 2 1 2                  SSS Считая второй столбец таблицы 2 2S основным столбцом, в следующую таб- лицу 3S будем переносить строку 3 и строки равновесия уравновешенных пар строк (1, 4) и (2, 4). Поскольку для вычисления переменных 321 ,, xxx использу- ются только параметры ,,, 321 uuu то согласно сформулированному правилу 2 элементы столбцов 4–6 таблиц ...,,3,2,1 jS j будут равны 0, если оба соответ- ствующих элемента допустимых строк равны 0; и 1 — в противном случае. Полу- чим таблицу . 2,000 2,100 100 10002,00 100002,0 010000 )( 3 2 3 1 3            SSS Основным столбцом будем считать третий столбец таблицы .3 2S Согласно сформулированному правилу 3 в следующую таблицу 4S будут переноситься только те строки равновесия, в которых одной из уравновешенных допустимых строк есть строка, дающая перестановки, у которой в основном столбце стоит 1. Для таблицы 3S такой строкой является первая строка, поэтому в следующую таблицу будет переноситься только строка равновесия уравновешенной пары строк (1, 2) (а строка равновесия уравновешенной пары строк (2, 3) переноситься не будет): ).000110002,0()( 4 2 4 1 4  SSS Строки таблицы 4 1S представляют собой минимальную систему образующих элементов конуса неотрицательных решений системы уравнений для параметров, поэтому получаем такие формулы для параметров :,, 321 uuu .0 ,2,0 32 11   uu pu Подставив эти выражения в полученные выше формулы для ,,, 321 xxx нахо- дим выражения ,4,0 11 px  ,6,0 12 px  ,113  px поэтому ,4,01 x .6,02 x Точка )6,0;4,0(X удовлетворяет неравенству .0)( xl Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 61 О.О. Ємець, Н.Ю. Устьян ДОСЛІДЖЕННЯ РОЗВ’ЯЗКІВ ЛІНІЙНИХ ЗАДАЧ ЕВКЛІДОВОЇ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ НА ПЕРЕСТАНОВКАХ З ДОДАТКОВИМИ ОБМЕЖЕННЯМИ. Частина 3 Досліджується поширення відомого методу розв’язування систем лінійних не- рівностей для знаходження загальної формули точок переставного многогран- ника при додаткових обмеженнях. O.А. Yemets, N.Yu. Ustian THE INVESTIGATION OF THE SOLUTIONS OF LINEAR PROBLEMS OF EUCLIDEAN COMBINATORIAL OPTIMIZATION ON ARRANGEMENTS WITH ADDITIONAL RESTRICTIONS. Part III The known method of decision of systems of linear inequalities for finding a general formula of points of a permutable polyhedron at additional restrictions is investigat- ed. 1. Емец О.А., Устьян Н.Ю. Исследование решений линейных задач евклидовой комбина- торной оптимизации на перестановках с дополнительными ограничениями. Часть 1 // Международный научно-технический журнал «Проблемы управления и информатики». — 2011. — № 2. — С. 26–32. 2. Емец О.А., Устьян Н.Ю. Исследование решений линейных задач евклидовой комбина- торной оптимизации на перестановках с дополнительными ограничениями. Часть 2 // Там же. — 2011. — № 5. — С. 44–51. 3. Черников С Н. Линейные неравенства. — М. : Наука, 1968. — 488 с. 4. Черникова Н.В. Алгоритм для нахождения общей формулы неотрицательных решений си- стемы линейных уравнений // Журн. вычисл. математики и мат. физики. — 1964. — 4, № 4. — С. 733–738. 5. Моцкин Т.С., Райфа Х., Томпсон Дж.Л., Тролл Р.М. Метод двойного описания // Матрич- ные игры / Под ред. Н.Н. Воробьева. — М. : Физматгиз, 1961. — С. 81–109. 6. Burger E. Uber homogene lineare Ungleichungssysteme // Z. Angew. Math. und Mech. — 1956. — 36, N 3/4. — P. 135–139. Получено 13.01.2010

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

Institution

Ähnliche Einträge