Диссертация (1150576), страница 10
Текст из файла (страница 10)
Это условие записываетсяв виде неравенства−1 (−1 ) ≥ 1,которое является условием отбрасывания границы 1 .683.6Алгоритм нахождения множества нижних границВ разделе будет предложен алгоритм нахождения всех нижних границ длязадачи псевдочебышевской аппроксимации, необходимых для получения полного множества решений задачи (3.3), в котором используются процедуры, предложенные в разделе 3.5.Пусть имеется разреженная матрица задачи = ( ), где = ( ) – строкиматрицы , а также регулярные векторы = ( ) и = ( ).
По формуле (3.4)−̂︀′ = (̂︀ ′ ), умножаянаходим Δ = (() )1/2 , после чего вычисляем матрицу ̂︀ ′ = −1каждую строку матрицы на элемент −1 : .Множество всех решений задачи получаем с помощью следующей процедуры, передав ей в качестве аргументов матрицу и векторы , .Algorithm 1 Алгоритм нахождения множества нижних границ.1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:function Nextmatr(, , , = ∅) ← ∅◁ – список найденных границ, изначально пуст′̂︀ ← Best( , )◁ индекс наилучшей строки из оставшихсяfor ← 1 to where ̸= 0 do ← {}◁ находим элементы -го столбца, которые можно зафиксироватьfor ← 1 to where ̸= 0 and ̸∈ doif ̂︀′ ≥ ̂︀′ then ← ⊎ {}◁ Добавляем их в список end ifend for̃︀ ← Fix(, , ) ◁ фиксируем их, обнуляя другие в их строках ← ⊎ if SizeOf( ) == then◁ если зафиксированы все строки̃︀− 1 ← Δ−1 ◁ то получаем новую нижнюю границу ← ⊎ 1◁ и добавляем ее в списокelse◁ рекурсивно вызываем процедуру для оставшихся строк̃︀, , , ) ← ⊎ Nextmatr(19:end ifend for20: ←18:21:22:FilterPoints()return end function◁ отбрасываем несущественные границы69Аргумент служебный и используется процедурой для передачи информации об обработанных строках.Для выбора наилучшей строки (процедура в строке 3 алгоритма 1)можно использовать различные подходы.
Рассмотрим следующий подход: для̂︀′ определяем количество элементовкаждого ненулевого элемента матрицы столбца, которые не меньше этого элемента (и которые, соответственно, будут тоже зафиксированы при выборе этого элемента), вычисляя тем самым его«вес». Приняв «вес» нулевых элементов за /2, находим общий «вес» каждойстроки как сумму «весов» ее элементов.
При этом больший «вес» строки соответствует большему приоритету для выбора.Точная оценка вычислительной сложности алгоритма 1 затруднена из-зарекурсивности процедуры, а также из-за сильных различий в зависимости отструктуры разреженной матрицы задачи. Поэтому была проведена статистическая оценка количества рассматриваемых матриц 1 ∈ , для чего для каждой размерности (от 3 до 10) были сгенерировано по 100000 матриц случайныхматриц со стандартным нормальным распределением элементов. Для каждойтакой матрицы алгоритм находил полное решение, а число рассмотренных впроцессе матриц 1 ∈ фиксировалось. После этого было вычислено среднее,дисперсия и медиана полученного распределения числа рассмотренных матриц,результаты приведены в таблице 3.1.В наихудшем случае, когда все строки разреженной матрицы равнозначны, количество рассматриваемых матриц может быть экспоненциальным поразмерности задачи, но в реальных задачах, как видно из таблицы, подобныеслучаи обычно не встречаются.3.7Численный примерРассмотрим задачу (3.3), заданную в полуполе Rmax ,+ при = 3.
Предположим, что имеются матрица и векторы и следующего вида:⎛⎞5 5 2⎜⎟⎟,=⎜−1−7−3⎝⎠−2 1 −6⎛⎞0⎜ ⎟⎟=⎜⎝ 4 ⎠,3⎛⎞1⎜ ⎟⎟=⎜⎝ 2 ⎠.370Размерность Среднее Дисперсия Медиана31.20.4141.60.9152.31.8263.73.5276.27.44810.915.86920.035.191037.473.214Таблица 3.1: Число рассмотренных процедурой вариантов в зависимости отразмерности задачиНайдем все регулярные векторы , которые решают задачу. Сначала поформуле (3.4) определим минимум Δ, для чего последовательно вычислим⎞⎛⎛⎞⎛⎞5 5 217⎟⎜ ⎟ ⎜ ⎟⎜⎟⎜ ⎟ ⎜ ⎟ = ⎜⎝ −1 −7 −3 ⎠ ⎝ 2 ⎠ = ⎝ 0 ⎠ ,−2 1 −633⎛Δ2 =(︁⎞)︁ ⎜ 0 ⎟−⎟−7 0 −3 ⎜⎝ 4 ⎠ = () = 4,3Δ = 2.Для нахождения разреженной матрицы задачи построим пороговую матрицу следующим образом:⎛⎞⎛⎞0 (︁)︁ ⎜ −5 −6 −7 ⎟⎜⎟⎟⎜⎟Δ−2 − = −4 ⎜⎝ 4 ⎠ −1 −2 −3 = ⎝ −1 −2 −3 ⎠ .3−2 −3 −4Заменяя нулем 0 = −∞ те элементы матрицы , которые строго меньше̂︀, а умножая каждую строкуэлементов матрицы Δ−2 − , находим матрицу ̂︀ на соответствующий элемент вектора − , получаем матрицу ̂︀′ .
Вматрицы 71результате получим⎛⎞⎛5 5 2⎜⎟̂︀ = ⎜ −1 0 −3 ⎟ ,⎝⎠−2 1 0⎞5 5 2⎜⎟⎟. =⎜−50−7⎝⎠−5 −2 0̂︀′Применим процедуру построения полного решения. Заметим, что в матрице̂︀′ во второй и в третьей строках все ненулевые элементы являются наименьшими ненулевыми элементами в своих столбцах. В силу этого следует начать̂︀, что позволит сократитьс выбора соответствующих элементов в матрице перебор разреженных матриц. Для определенности начнем со второй строки.̂︀′ элемент ̂︀Сначала зафиксируем элемент ̂︀21 .
Учитывая, что в матрице ′21не превосходит элементов ̂︀′11 и ̂︀′31 , то можно оставить без изменений соответ-̂︀, а остальные элементы этой матрицыствующие элементы ̂︀11 и ̂︀31 матрицы заменить нулями.В результате получаем матрицу 1 :⎛⎞5 0 0⎜⎟⎟1 = ⎜⎝ −1 0 0 ⎠ ,−2 0 0после чего находим нижнюю границу⎛⎜⎜1 = Δ−1 −=−21⎝−5 1 2⎞⎛⎞⎛⎞03⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟0 0 0⎟⎠⎝ 4 ⎠ = ⎝ 0 ⎠.0 0 030Матрица нижних границ 1 приобретает вид⎛⎞3⎜ ⎟⎟1 = ⎜⎝ 0 ⎠.0̂︀. В силу того,Теперь зафиксируем элемент ̂︀23 во второй строке матрицы ̂︀′ выполняется условие ̂︀̂︀что для элементов матрицы ′23 ≤ ̂︀′13 , в матрице 72можно оставить элемент ̂︀13 , а оставшиеся элементы первой строки этой матрицы заменить нулями.В оставшейся третьей строке следует по очереди фиксировать каждый еененулевой элемент.
Зафиксировав элемент ̂︀31 получаем матрицу⎛⎜2 = ⎜⎝0 02⎞⎟0 0 −3 ⎟⎠,−2 0 0и находим вторую нижнюю границу:⎛⎜⎜2 = Δ−1 −=−22⎝0 0 2⎞⎛⎞⎛⎞⎞⎛⎞03⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟0 0 0⎟⎠⎝ 4 ⎠ = ⎝ 0 ⎠−2 3 035После фиксации элемента ̂︀32 получаем границу⎛⎞0 0 2⎜⎟⎟3 = ⎜⎝ 0 0 −3 ⎠ ,0 1 0и вычисляем последнюю нижнюю границу⎛⎜−1 −3 = Δ 3 = −2 ⎜⎝0 00⎞⎛00⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟0 0 −1 ⎟⎠⎝ 4 ⎠ = ⎝ 0 ⎠.−2 3 035Выясним, являются ли полученные границы существенными. Проверкаусловия (3.11) приводит к следующим результатам:⎛−1 (−2 1 ) =(︁⎛⎞⎞−)︁ ⎜(︁)︁ ⎜ 3 ⎟⎟⎜ ⎟⎟0 ⎜⎝ −3 0 −5 ⎝ 0 ⎠⎠ = 0 = 1,073⎛−1 (−3 1 ) =(︁⎛⎞⎞−)︁ ⎜(︁)︁ ⎜ 3 ⎟⎟⎜ ⎟⎟0 ⎜⎝ 0 0 −5 ⎝ 0 ⎠⎠ = 0 < 1.0Для границы 2 условие оказывается выполненным, а потому ее можно неучитывать.
Заметим, что непосредственная проверка выполнения неравенства1 ≤ 2 подтверждает этот результат. Однако для границы 3 условие не выполняется и ее следует добавить к имеющейся границе 1 .В итоге получим матрицу границ⎛⎞3 0⎜⎟⎟. = (1 ,3 ) = ⎜00⎝⎠0 5Общее решение (3.9) задачи (3.3) записывается в форме⎛⎞3 0⎜⎟⎟=⎜⎝ 0 0 ⎠ ⊕ ,0 5⎛⎞3⎜ ⎟⎟≤⎜⎝ 4 ⎠,51 = 1.Представление решения в виде (3.8) дает два подмножества решений.
Первоев обычных терминах записывается в виде1 = 3,2 ≤ 4,3 ≤ 5,а второе представимо в форме1 ≤ 3,0 ≤ 2 ≤ 4,3 = 5.74Все вычисления в примерах настоящей главы были выполнены с использованием программ, реализованных на языке R, исходный код которых приводитсяв приложении Б.75Глава 4Метод построения множества всех решений тропического линейного векторногонеравенстваРазличные практические задачи (например, транспортная задача в сетевойпостановке, минимаксные задачи теории игр, см.
[7]) приводят к необходимостирешать тропические уравнения и неравенства вида ≤ , = , ≥ .Среди них неравенство ≤ решается в явном виде, и решение по лемме 1имеет вид ≤ (− )− . Уравнение = также может быть решено, однако его решение не всегда единственно, при этом, в случае единственности, ономожет быть получено в виде = (− )− [32], а в случае отсутствия единственности может быть построена процедура, перебирающая все решения.Если говорить о неравенстве ≥ , то, по-видимому, в литературе ему неуделяется достаточного внимания. Поэтому в настоящей главе было проведеноего исследование, и, так как в явном виде множество всех решений получить неудалось ввиду сложности данного множества, то предложен метод, с помощьюкоторого можно получить все решения [68].764.1Метод нахождения решений неравенстваМножество решений задачи ≥ представляет собой объединение некоторых простых подмножеств.
Далее будет описана конфигурация этих подмножеств и предложен метод, для нахождения решений.4.1.1Предварительная подготовкаРассмотрим произвольный ненулевой вектор ∈ X . Будем называть тропическим выпуклым конусом (далее конусом) множество всех векторов ∈ X ,таких, что ≥ , а «гранью» – множество граничных точек конуса, лежащихна одной гиперплоскости.Конус представляет собой многомерную фигуру, которая характеризуетсяколичеством ненулевых компонент вектора . Так, в случае, когда в векторе = ( ) присутствует только одна ненулевая координата, например, , соответствующий ему конус будет представлять собой полупространство пространства X , отделенное от оставшейся части пространства гиперплоскостью, длявсех точек которой -я компонента равна .
Эта гиперплоскость является единственной «гранью» рассматриваемого конуса.Если в векторе присутствует ненулевых компонент, то его конус представляет собой 1/2 часть пространства X с «гранями», каждая из которыхявляется 1/2−1 частью соответствующей ей гиперплоскости.Рассмотрим неравенство ≥ .(4.1)Множество всех решений неравенства (4.1) представляет собой сложную фигуру, которая образуется объединением многомерных конусов, поэтому в явномвиде решение получить трудно. Вместо этого предлагается метод, с помощьюкоторого можно получить все решения алгоритмически.Для начала заметим, что можно считать вектор = ( ), состоящим полностью из ненулевых компонент, т.к.
если = 0 для какого-либо , то для этойкомпоненты неравенство выполняется автоматически, вне зависимости от вектора , соответственно можно убрать из рассмотрения -ю строку матрицы и -ую компоненту вектора .77После того, как избавились от нулевых компонент в векторе , можно «отнормировать» по нему матрицу . Действительно, так как для выполнениянеравенства с конкретным :1 1 ⊕ 2 2 ⊕ · · · ⊕ ≥ рассматривается только -я строка матрицы (и в других неравенствах этастрока не используется), то можно умножить -ю строку на −1 , сведя нера-˜ ≥ 1, где ˜ – получившаяся матрица.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
