Об одном алгоритме отыскания решений системы линейных неравенств

An efficient algorithm for finding a solution to system of linear inequalities is proposed. It is based on the procedure of cutting a simplex by a plane and of embedding an obtained “semisimplex ” into a new simplex of minimal volume. The computational experiment results are provided.

Gespeichert in:

Bibliographische Detailangaben
Datum:	2005
1. Verfasser:	Ненахов, Э.И.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2005
Schriftenreihe:	Теорія оптимальних рішень
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/84923
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:	Об одном алгоритме отыскания решений системы линейных неравенств / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 42-48. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-84923
record_format	dspace
spelling	irk-123456789-849232015-07-18T03:01:32Z Об одном алгоритме отыскания решений системы линейных неравенств Ненахов, Э.И. An efficient algorithm for finding a solution to system of linear inequalities is proposed. It is based on the procedure of cutting a simplex by a plane and of embedding an obtained “semisimplex ” into a new simplex of minimal volume. The computational experiment results are provided. 2005 Article Об одном алгоритме отыскания решений системы линейных неравенств / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 42-48. — Бібліогр.: 4 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84923 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	An efficient algorithm for finding a solution to system of linear inequalities is proposed. It is based on the procedure of cutting a simplex by a plane and of embedding an obtained “semisimplex ” into a new simplex of minimal volume. The computational experiment results are provided.
format	Article
author	Ненахов, Э.И.
spellingShingle	Ненахов, Э.И. Об одном алгоритме отыскания решений системы линейных неравенств Теорія оптимальних рішень
author_facet	Ненахов, Э.И.
author_sort	Ненахов, Э.И.
title	Об одном алгоритме отыскания решений системы линейных неравенств
title_short	Об одном алгоритме отыскания решений системы линейных неравенств
title_full	Об одном алгоритме отыскания решений системы линейных неравенств
title_fullStr	Об одном алгоритме отыскания решений системы линейных неравенств
title_full_unstemmed	Об одном алгоритме отыскания решений системы линейных неравенств
title_sort	об одном алгоритме отыскания решений системы линейных неравенств
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2005
url	http://dspace.nbuv.gov.ua/handle/123456789/84923
citation_txt	Об одном алгоритме отыскания решений системы линейных неравенств / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 42-48. — Бібліогр.: 4 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT nenahovéi obodnomalgoritmeotyskaniârešenijsistemylinejnyhneravenstv
first_indexed	2025-07-06T12:02:44Z
last_indexed	2025-07-06T12:02:44Z
_version_	1836898964969881600
fulltext	42 Теорія оптимальних рішень. 2005, № 4 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Предлагается эффективный ал- горитм для решения системы ли- нейных неравенств. В основе ал- горитма лежит процедура сече- ния симплекса плоскостью и по- гружения полученного “полусимп- лекса” в новый симплекс мини- мального объема. Представлены результаты численного экспери- мента.  Э.И. Ненахов, 2005 ÓÄÊ 519.8 Ý.È. ÍÅÍÀÕÎÂ ÎÁ ÎÄÍÎÌ ÀËÃÎÐÈÒÌÅ ÎÒÛÑÊÀÍÈß ÐÅØÅÍÈÉ ÑÈÑÒÅÌÛ ËÈÍÅÉÍÛÕ ÍÅÐÀÂÅÍÑÒÂ Введение. Для минимизации ограниченной снизу выпуклой функции в пространстве n R разработан метод центрированных сечений [1], который основан на том, что используя информацию о локализации минимума в не- котором выпуклом замкнутом многогранни- ке, находить на каждой итерации алгоритма центр тяжести данного многогранника и вы- числять субградиент функции в данной точ- ке. Минимум функции будет находиться в одном из полупространств, определяемых опорной гиперплоскостью. Часть многогран- ника, лежащую в другом полупространстве, можно отсечь. С полученным новым много- гранником поступаем аналогично. Метод центрированных сечений практиче- ски непригоден, поскольку вычисление цен- тра тяжести многомерного многогранника является неконструктивной процедурой. Весьма эффективной оказалась идея замены многогранника на эллипсоид [2]. В работе [3] была осуществлена замена многогранни- ка симплексом и получен метод центров тя- жести симплексов для решения экстремаль- ной задачи. Для быстрой сходимости указан- ного метода необходимо простым способом вычислять последовательность симплексов, содержащих очередную неотсеченную об- ласть – «полусимплекс». Кроме того отно- шение объемов двух последовательных сим- плексов должно быть меньше единицы. Известно, что центр тяжести позволяет осуществлять гарантированное уменьшение объема симплекса [4]. Однако, в качестве ОБ ОДНОМ АЛГОРИТМЕ ОТЫСКАНИЯ РЕШЕНИЙ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ Теорія оптимальних рішень. 2005, № 4 43 очередного приближения наряду с центром тяжести может быть выбран центр шара максимального радиуса, вписанного в симплекс. Рассмотрению способов эффективного управления уменьшением объемов симплексов и выбора некото- рых характерных точек симплексов в качестве приближений решения системы линейных неравенств посвящена данная работа. Рассмотрим систему линейных неравенств mixa ii ,...,1,0),( =≤α+ , (1) определяющую многогранник ΩΩΩΩ с непустой внутренностью. Требуется найти точку ΩΩΩΩ∈∈∈∈x~ . Предполагаем, что существует произвольный n –мерный симплекс 1−−−−S , натянутый на вершины n xxx ,...,, 10 и содержащий ΩΩΩΩ . Пусть x − центр тяжести симплекса 1−−−−S и задана некоторая плоскость 0),( =α+xa , такая, что 0),( >α+xa . Далее рассмотрим процедуру ),;( αaxV , ставящую в соответствие симплексу 1−−−−S симплекс 1S минимального объема, содержащий “полусимплекс” { }0),(:10 ≤α+∈= − xaSxS . Пусть 0),( =β+ jj xb , nj ,...,1,0==== , нормальное уравнение плоскости, со- держащей грань симплекса 1−−−−S , противолежащую вершине j x данного сим- плекса. Тогда 0S можно представить так: { }0),(,,...,1,0,0),(:0 ≤α+=≤β+= xanjxbxS jj . Погружение “полусимплекса” 0S в симплекс осуществляется следующим образом. Вначале определяем все вершины исходного симплекса, удовлетво- ряющие отсекающему неравенству. Пусть для определенности 0),( ≤α+j xa , kj ,...,1,0= , и вершина 0 x наиболее удалена от отсекающей плоскости. Для ]1,0[∈θ построим гиперплоскость 0]),[(]),][(),)[(1(]),[( 0 0 000 0 =β+β+α+θ−+α+θ xbxbxaxa . Вычисляем координаты точек пересечения )(θj y , nj ,...,1==== , с этой гипер- плоскостью ребер симплекса 1−−−−S , исходящих из вершины 0 x , т.е. находим вер- шины симплекса, определяемого неравенствами 0),( ≤β+ jj xb , nj ,...,1==== , и неравенством 0]),[(]),][(),)[(1(]),[( 0 0 000 0 ≤β+β+α+θ−+α+θ xbxbxaxa , содержащего 0S . Нетрудно проверить, что njxaxaxxxy j jj jj ,...,1],),[(]),[(,)1()()( 000 =α+α+=δθδ−−+=θ . Э.И. НЕНАХОВ 44 Теорія оптимальних рішень. 2005, № 4 Процедура (((( ))))α,; axV , завершается вычислением на отрезке [[[[ ]]]]1,0 минимума функции ( ) 0, 1 1 1 > θδ− ⋅=θϕ ∏ = cc n j j . Оценка сверху для минимума )(θϕ зависит от величины ∑∑∑∑ ==== ====∆∆∆∆ k j j 1 δ . Ска- занное следует понимать так: если имеется несколько плоскостей, отделяющих центр тяжести x , то для сечения симплекса следует выбрать ту, которой соот- ветствует меньшая величина ∆∆∆∆ . Процедуру построения гиперплоскости 0),( =α+xa в соответствии с описанным правилом обозначим )(1 xH . Для описания следующей процедуры )(2 xH построения отсекающей ги- перплоскости предположим, что 0),( >α+ ii xa , 0,...,1 mi ==== . На первом шаге вначале полагаем 11 ac ==== , 11 αγ ==== , 22 ac ==== , 22 αγ ==== и рассматриваем отсекаю- щее неравенство как выпуклую комбинацию первых двух нарушенных нера- венств ,0]),)[(1(]),[( 2211 ≤γ+θ−+γ+θ xcxc ]1,0[∈θ . Далее строим функцию ( ) ,]),)[(1(]),[(max ]),)[(1(]),[()( 2211 0 0 2211 γ+θ−+γ+θ−         −γ+θ−+γ+θ=θ∆ ≤≤ = ∑ jj nj n j jj xcxc gxcxc где ( )]),)[(1(]),[( 2211 0 γ+θ−+γ+θ= ∑ = jj n j xcxcg . Определяем параметр ( ){ }]1,0[minarg * ∈θθ∆=θ и полагаем направ- ляющий вектор 2 * 1 ** )1( cca θ−+θ= и свободный член уравнения отсекающей гиперплоскости 2 * 1 ** )1( γθ−+γθ=α . Несмотря на сложный вид функции )(θ∆ , значение параметра θ легко вы- числяется. Оно совпадает или с одним из концов указанного отрезка, или с кор- нем одного из слагаемых, стоящих под знаком модуля в числителе этого выражения. На втором шаге полагаем 1 ac ==== , * 1 αγ ==== , 32 ac ==== , 32 αγ ==== и повторяем все описанные действия. Процедура )(2 xH продолжается до тех пор, пока не будут перебраны все 0m нарушенные неравенства. Последняя выпуклая комби- нация даст искомую отсекающую гиперплоскость. ОБ ОДНОМ АЛГОРИТМЕ ОТЫСКАНИЯ РЕШЕНИЙ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ Теорія оптимальних рішень. 2005, № 4 45 Для описания процедуры )(3 xH также будем предполагать, что в точке x нарушены первые 0m неравенств. Полагаем 0 1 ,...,1],),[(]),[( 0 mixaxa m k kkiii =α+α+=λ ∑ = . Тогда для нормали a и свободного члена α отсекающей гиперплоскости получаем следующие выражения: ∑∑∑∑∑∑∑∑ ======== ======== 00 11 , m i iii m i ii aa αλαλ . Рассмотрим три процедуры отыскания очередного приближения. Процедура )(1 SP ставит в соответствие симплексу S его центр тяжести x . Процедура )(2 SP ставит в соответствие симплексу S его чебышевский центр       ∈−= ∈ n Sz Rxzxx maxminarg€ . Для отыскания чебышевского центра x€ исходного симплекса 1−−−−S достаточ- но решить соответствующую систему уравнений. На всех последующих шагах расчеты значительно проще. Действительно, центр шара, вписанного в 1S , сле- дует искать на луче τ−+ )€( 00 xxx , 0≥≥≥≥τ . Поэтому достаточно найти решение 0τ уравнения ( ) ( ) 0 00 01 00 1 )€(,)€(, β+τ−+=β+τ−+ xxxbxxxb , где 0),( 00 =β+xb – нормальное уравнение плоскости, содержащей грань сим- плекса 1S , противолежащей вершине 0 x , а затем положить 0 00 )€(:€ τ−+= xxxx . Процедура )(3 SP состоит из n шагов. На первом шаге полагаем xz ====:€ , 1: xz ==== и находим ( )       ∈θα+θ−+θ=θ ]1,0[])1(€,[maxminarg* ii i zza . (2) Далее полагаем zzz )1(€:€ ** θ−+θ= , 2: xz ==== и решаем вновь задачу (2). Заверша- ется процедура )(3 SP построением некоторой точки z€ на n -й итерации. Перейдем теперь к непосредственной формулировке алгоритма для решения системы (1). Пусть точки )(1 1−= SPx , )(2€ 1−= SPx и )(3€ 1−= SPz не принадле- жат Ω (иначе, система (1) решена). Применяя процедуру )(1 xH , либо (((( ))))xH 2 , либо )(3 xH находим отсекающую гиперплоскость 0),( =α+xa . Осуществляем процедуру ),;( αaxV , т.е. находим новый симплекс ΩΩΩΩ⊃⊃⊃⊃1S , объем которого меньше объема исходного симплекса 1−−−−S . Описанные шаги повторяются. По- скольку ∅∅∅∅≠≠≠≠ΩΩΩΩint , то за конечное число итераций модифицированный метод решит систему (1). Э.И. НЕНАХОВ 46 Теорія оптимальних рішень. 2005, № 4 Если ∅∅∅∅====ΩΩΩΩint , то на некоторой итерации может быть получен симплекс нулевого объема, но не получено решение задачи, т. е. вычислительный процесс завершается безрезультатно. Требуется найти некоторую точку в многограннике {{{{ }}}} 2 21121 01;01;012: Rx ∈∈∈∈≤≤≤≤−−−−++++−−−−≤≤≤≤++++≤≤≤≤−−−−−−−−−−−−====ΩΩΩΩ ξξξξξ . В качестве исходного берем симплекс 0S с вершинами )10;0( , )20;10( −− , )20;10( − . Тогда ΩΩΩΩ⊃⊃⊃⊃0S , ∅∅∅∅====ΩΩΩΩint . На первой итерации центр симплекса 0S не удовлетворяет неравенствам с номерами 11 ====i , 22 ====i и 1552,0* ====λ . Выпуклая комбинация первых двух плос- костей, определяющих ΩΩΩΩ , с использованием найденного значения λ дает отсе- кающую плоскость 0145005,0 21 ====++++−−−− ξξ . Таким образом будет построен сим- плекс 1S с вершинами )10;0( , )20;10( −− , )5319,5;4894,1( , причем 1489,0)()( 01 =SvolSvol . На второй итерации 31 ====i , 12 ====i , 81660 ,====λ . Выпук- лая комбинация с данным *λ третьей и первой плоскости, определяющих ΩΩΩΩ , дает отсекающую плоскость 0145005,0 21 ====−−−−++++−−−− ξξ . В качестве симплекса 2S получаем отрезок с концами )20;10( −− , )5319,5;4894,1( , то есть 0)( 2 =Svol . Алгоритм закончил работу, однако, единственная точка Ω∈− )0;1( не найдена. Заметим, что в качестве исходного симплекса 1−−−−S можно брать симплекс, удовлетворяющий более слабому требованию ∅∅∅∅≠≠≠≠ΩΩΩΩ−−−− I1S . Пример. Требуется найти решение системы неравенств (1) с числовыми дан- ными, представленными в таблице. Здесь 15 Rx ∈∈∈∈ , число неравенств 14====m . В качестве исходного симплекса берем         ≤≤≤≤≥≥≥≥==== ∑∑∑∑ ==== −−−− 3,0: 15 1 1 q qxxS ξ . На оче- редной итерации построение отсекающей гиперплоскости производилось с по- мощью процедур )(1 xH или )(2 xH . В первом случае решение получено при 86====k , === xxSvolSvol ~,99774,0)(/)( 8586 (–0,76881; 0,29741; 0,85762; 0,09701; 0,04513; 0,05111; 0,10333; 0,15089; 0,13279; 0,34197; 0,02528; 0,71540; 0,06160; 0,54511; 0,25700), во втором − при 34====k , === xxSvolSvol ~,99579,0)(/)( 3334 (0,79970; 0,15279; 0,61331; –0,06312; 0,21261; 0,06889; 0,05470; 0,09169; 0,01581; 0,43580; 0,03071; 0,02301; 0,04400; 0,15569; 0,25390). Замечание. Если на каждом шаге итерационного процесса с использо- ванием процедуры )(1 SP отсекаются все вершины, кроме одной, то объем сим- плексов, в которых локализована точка x~ , уменьшается в два раза, т.е. осущест- вляется процесс дихотомии. ОБ ОДНОМ АЛГОРИТМЕ ОТЫСКАНИЯ РЕШЕНИЙ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ Теорія оптимальних рішень. 2005, № 4 47 ТАБЛИЦА ia i 1ξ 2ξ 3ξ 4ξ 5ξ 6ξ 7ξ 8ξ 9ξ 10ξ 11ξ 12ξ 13ξ 14ξ 15ξ iα 1 1 -1 2 -3 0 2 -1 3 -1 -2 -5 1 1 2 -3 1 2 -1 -2 3 -5 2 -1 2 -4 6 -7 0 -5 4 3 2 -0,7 3 0 3 -1 2 -3 0 5 -5 6 8 1 0 -1 -2 4 3,3 4 2 1 -3 4 0 0 -2 0 0 2 -3 2 0 5 8 3,2 5 1 2 3 -1 -3 -5 6 0 0 0 0 0 0 0 1 2,8 6 0 0 -1 -2 -3 3 2 1 0 0 -1 1 2 -2 1 -0,5 7 -1 -1 -2 -3 2 3 0 0 0 -1 2 -4 5 6 -4 -1,5 8 -1 1 -2 3 0 -2 1 -3 1 2 5 -1 -1 -2 3 -0,8 9 1 2 -3 5 -2 1 -2 4 -6 7 0 5 -4 -3 -2 0,9 10 0 -3 1 -2 3 0 -5 5 -6 -8 -1 0 1 2 -4 -3,1 11 -2 -1 3 -4 0 0 2 0 0 -2 3 -2 0 -5 -8 -3,0 12 -1 -2 -3 1 3 5 -6 0 0 0 0 0 0 0 -1 -2,6 13 0 0 1 2 3 -3 -2 -1 0 0 1 -1 -2 2 -1 0,7 14 1 1 2 3 -2 -3 0 0 0 1 -2 4 -5 -6 4 1,9 Заключение. Исследуемый алгоритм, вообще говоря, не улучшает теорети- ческую оценку скорости сходимости метода центров тяжести симплексов. Од- нако при решении конкретных задач предложенные варианты алгоритма суще- ственно уменьшают число итераций. Е.І. Ненахов ПРО ОДИН АЛГОРИТМ ПОШУКУ РІШЕНЬ СИСТЕМИ ЛІНІЙНИХ НЕРІВНОСТЕЙ Пропонується ефективний алгоритм для розв′язування системи лінійних нерівностей. У осно- ві алгоритму лежить процедура відтинання симплексу площиною та занурення отриманого “напівсимплексу” в новий симплекс мінімалного об′єму. Наведені результати обчислюваль- ного експерименту. Э.И. НЕНАХОВ 48 Теорія оптимальних рішень. 2005, № 4 E.I. Nenakhov AN ONE ALGORITHM FOR FINDING SOLUTION TO A LINEAR INEQUALITY SYSTEM An efficient algorithm for finding a solution to system of linear inequalities is proposed. It is based on the procedure of cutting a simplex by a plane and of embedding an obtained “semisimplex ” into a new simplex of minimal volume. The computational experiment results are provided. 1. Левин А.Ю. Об одном алгоритме минимизации выпуклых функций // Докл. АН СССР. − 1965. − 160, № 6. − С. 1244 −1247. 2. Шор Н.З. Методы минимизации недифференцируемых функций и их применение. − Киев: Наук. думка, 1979. − 200 с. 3. Александров И.А., Анциферов Е.Г., Булатов В.П. Методы центрированных сечений в выпуклом программировании. − Иркутск, 1983. − 33 с. − (Препр. / АН СССР, Сиб. отд. − ние. Сиб. энергетический ин−т; № 5). 4. Митягин Б.С. Два неравенства для объемов выпуклых тел // Математические замет- ки. − 1969. − 5, вып. 1. − С. 99 − 106. Получено 25.02.2005

Об одном алгоритме отыскания решений системы линейных неравенств

Institution

Ähnliche Einträge