Диссертация (1150576), страница 5
Текст из файла (страница 5)
Учитывая четвертое неравенство и то, что ≥ − ≥ ,находим нижнюю границу для в форме ≥ ⊕ ( − )1/2 ⊕ .Применив лемму 1 к первым трем неравенствам рассматриваемой системы,а затем умножая первые два из полученных неравенств на −1 , получаем−1 ≤ ,−1 ≤ , ≤ .26Наконец, объединяя эти неравенства с неравенством ≤ , запишем систему (1.14) в виде двойного неравенства(−1 ⊕ ) ⊕ −1 ≤ ≤ .(1.15)По теореме 1 существование регулярных решений для левой части неравенства (1.15) равносильно выполнению условияTr(−1 ⊕ ) ≤ 1.Рассмотрим выражениеTr(−1 ⊕ ) =⨁︁tr(−1 ⊕ ) = tr=1(︃ ⨁︁)︃(−1 ⊕ ).=1Сначала, применяя тождество (1.1) при = , запишем⨁︁=1−1( ⊕ ) =⨁︁⨁︁−01 ( · · · ) ⊕=1 0≤0 +···+ ≤−⨁︁.=1Теперь с учетом обозначения получим−1Tr( ⊕ ) =⨁︁− tr ⊕ Tr().=1Заметим, что неравенство Tr() ≤ 1 выполнено по условиям теоремы, поэтому требуется обеспечить выполнение неравенства⨁︁− tr ≤ 1.=1Последнее неравенство эквивалентно системе неравенств− tr ≤ 1, = 1, .
. . ,.27Решение неравенств системы приводит к системеtr1/ ( ) ≤ , = 1, . . . ,,которая, в свою очередь, равносильна одному неравенству≥⨁︁tr1/ ( ).=1Нетрудно заметить, что ≥ для всех = 1, . . . ,, откуда следует⨁︁1/tr( ) ≥⨁︁tr1/ ( ) = .=1=1Тогда можно уточнить установленную ранее нижнюю границу для так−1/2 ≥ ⊕ ( )⊕⨁︁tr1/ ( ).=1Теперь необходимо получить решение неравенства (1.15). Применяя теорему1, находим решение левой части неравенства в виде = (−1 ⊕ )* ,где – любой регулярный вектор такой, что ≥ −1 .С учетом полученного решения правое неравенство в (1.15) принимает форму(−1 ⊕ )* ≤ .По лемме 1 решение этого неравенства записывается в виде ≤ ( − (−1 ⊕ )* )− .Объединив оба неравенства для , имеем−1 ≤ ≤ ( − (−1 ⊕ )* )− .28Выясним, для каких значений множество регулярных решений полученного неравенства не пусто. Необходимо решить относительно неравенство−1 ≤ ( − (−1 ⊕ )* )− .(1.16)Умножая неравенство (1.16) слева на−1 − (−1 ⊕ )* ,приходим к неравенству−2 − (−1 ⊕ )* ≤ 1.(1.17)Теперь покажем, что неравенство (1.16) в свою очередь тоже является следствием (1.17).
Для этого умножим неравенство (1.17) слева на( − (−1 ⊕ )* )− ,а затем применим неравенство (1.3). В результате получим−1 ≤ −1 ( − (−1 ⊕ )* )− − (−1 ⊕ )* ≤ ( − (−1 ⊕ )* )− ,откуда следует, что оба неравенства эквивалентны.Рассмотрим неравенство (1.17). Учитывая, что Tr(−1 ⊕ ) ≤ 1, можнозаписать−1−1⨁︁⨁︁−1( ⊕ ) =( ⊕ ) = ⊕(−1 ⊕ ) .−1*=0=1Также, как и в первой части доказательства, применим тождество (1.1) при = − 1. Используя обозначение ,−1 , запишем−1*( ⊕ ) = ⊕−1⨁︁=1− ,−1 ⊕−1⨁︁=1.29Учитывая условия теоремы Tr() ≤ 1, имеем⊕−1⨁︁ =−1⨁︁ = 0,−1 = * ,=0=1откуда следует, что−1−1⨁︁*( ⊕ ) =− ,−1 .=0Подставляя полученное выражение в неравенство (1.17), приходим к неравенству−1⨁︁−−2 − ,−1 ≤ 1.=0Решая это неравенство относительно тем же путем, что и выше, получим−1⨁︁≥( − ,−1 )1/(+2) .=0Заметим, что при = 0 правая часть неравенства равна(︀− *)︀1/2≥ ( − )1/2 .Объединив все нижние границы, установленные для , можем записать неравенство≥⊕⨁︁1/tr=1( ) ⊕−1⨁︁( − ,−1 )1/(+2) .=0Чтобы получить минимум целевой функции, заменим в этом соотношениизнак неравенства на знак равенства.
Осталось записать общее решение в форме = (−1 ⊕ )* ,−1 ≤ ≤ ( − (−1 ⊕ )* )− ,и тем самым завершить доказательство теоремы.Таким образом, было получено все множество решений задачи (1.11), чтопозволяет проводить фильтрацию найденных решений по различным критериях, а также дает возможность добавлять дополнительные ограничения илииспользовать задачу (1.11) в композиции с другими задачами.
Заметим, что30в терминах полуполя Rmax ,+ рассматриваемая задача может быть записана,как задача линейного программирования. Однако решение задачи методамилинейного программирования (например, симплекс-методом) приводит к итеративной процедуре нахождения решения, а не к прямым расчетным формулам для непосредственного нахождения решения. Кроме того, явные формулыпозволяют точно определить количество операций, необходимых для получения результата, в то время как итеративные подходы допускают только оценкувычислительной сложности.1.5Оценка вычислительной сложностиВ этом разделе производится оценка вычислительной сложности решениязадачи (1.11), а также предлагается метод, позволяющий существенно уменьшить количество необходимых арифметических операций.Основная сложность при решении задачи (1.11) состоит в необходимостивычисления слагаемых по формулам0 =⨁︁ ,⨁︁ = 0 1 · · · ,0≤0 +···+ ≤−=0для всех = 1, .
. . ,. При этом общее количество слагаемых, входящих в указанные суммы составляет величину порядка 2 .Таким образом, при прямом подсчете вычислительная сложность оказывается экспоненциальной. Далее представлена схема вычислений, которая позволяет существенно снизить количество операций по сравнению с прямым подходом.Обозначим через сумму всевозможных произведений, состоящих из матриц и − матриц . При этом 0 = , = , 00 = . С учетомэтих обозначений можно выразить суммы в виде0 =⨁︁=00 , =⨁︁= , = 1, . .
. ,.(1.18)31{#0111{#02. .z .{0{%. %.y .#11222. %. x.z. $.z ..%. .&y−1,$Рисунок 1.1: Схема подсчета слагаемых .Заметим, что матрицу (при 1 ≤ ≤ − 1), можно получить с помощьюследующей рекуррентной формулы: = ,−1 ⊕ −1,−1 = ,−1 ⊕ −1,−1 .На основе этой формулы предлагается метод для подсчета слагаемых: поочередно вычисляются слагаемые , после чего по формулам (1.18) находятсявсе необходимые суммы , и, соответственно, минимум целевой функции.Наглядная иллюстрация подобной схемы изображена на рис. 1.1.Общее количество матриц , необходимых для вычисления , составляетвеличину 1 + · · · + ( + 1) = ( + 1)( + 2)/2. Сложность нахождения слагаемых не превосходит (2 ) операций с матрицами, а итоговая сложностьнахождения всех регулярных решений задачи (1.11) оказывается полиномиальной. При использовании прямого метода перемножения матриц (сложность неболее (3 )), общая вычислительная сложность решения задачи не превосходит(5 ).Отсюда следует, что полученное решение не только является полным, но ктому же может быть представлено в простой аналитической форме в матричновекторном виде.
Это дает возможность проводить дальнейшее аналитическоеисследование задачи, а также обеспечивает естественность программной реализации и распараллеливания вычислений.321.6Численные примерыЧтобы проиллюстрировать полученные результаты, приведем примеры ихиспользования в терминах полуполя Rmax ,+ . Сначала рассмотрим задачу безограничений, решение которой затем распространим на случай задачи с ограничениями.1.6.1Задача без ограниченийПусть в задаче (1.11) отсутствуют ограничения и тогда она принимает форму (1.7). Предположим, что = 2, а матрица , векторы и − , а такжескаляр заданы в виде(︃=1 0)︃− =,3 4(︁1 −1)︁(︃,=1)︃,1 = 2.Для решения задачи применим теорему 2.
Сначала по формуле (1.8) найдемминимум целевой функции(︀)︀1/2 (︀ −)︀1/3 = ⊕ −⊕ ⊕ .Для этого вычислим(︃1 02 = − =1 03 4− =(︁)︃ (︃(︁1 −1(︃=3 41 −1)︁)︃(︃)︁(︃1 01)︃,7 8 = 4,)︃1)︃ (︃3 43 4(︀= 2,11−)︀1/2= 1,)︃(︀= 4, − )︀1/3= 4/3.Отсюда получаем = 4. Также подсчитаем(︃−1 =−3 −4−10)︃,(︀−1 )︀*(︃=0 −4−10)︃,33(︃−1 =−3)︃(︃( − (−1 )* )− =,−33)︃.5Применяя формулу (1.9), находим решение в виде(︃=0 −4−1)︃0(︃,−3)︃(︃≤≤−33)︃5.Переходя к обычной записи, положив = (1 , 2 ) , = (1 ,2 ) ,получаем следующие равенства:1 = max(1 , 2 − 4),2 = max(1 − 1, 2 ),где компоненты вектора ограничены неравенствами−3 ≤ 1 ≤ 3,−3 ≤ 2 ≤ 5.Графическая иллюстрация решения в декартовой системе координат данана рис. 1.2. Множество решений образует многоугольную область со штрихованными границами, которая получена пересечением полосы между двумя сплошными прямыми линиями, проведенными под углом 45∘ к координатным осям ипрямоугольника, границы которого изображены пунктиром.1.6.2Задачи с ограничениямиНайдем решение задачи с ограничениями в виде (1.11).
В качестве примерарассмотрим предыдущую задачу, в которой добавлено ограничение ≤ сматрицей ограничений(︃=0 −1−20)︃.346r r r r r r r r r rrrrrrrrrruI@r@@@urrrrrrr0rrrrrr r r r r r r r r r r r rruРисунок 1.2: Пример множества решений задачи без ограничений.Чтобы применить теорему 4, сначала вычислим 2 = = *,Tr() = 0 = 1,условие Tr() ≤ 1 выполнено.Найдем матрицы(︃ =1 00 −1−23 4(︃ =)︃ (︃0 −1−20)︃ (︃)︃01 03 4(︃=1 0)︃3 4)︃(︃=2 33 4= ,)︃.Применение формулы (1.12) для вычисления минимума целевой функциидает выражение(︀)︀1/2 (︀ −)︀1/3 = ⊕ tr(12 ) ⊕ tr1/2 (22 ) ⊕ − 01 ⊕ 11 ,356r r r r r r r r r r r r r r rrrrrrrrrurr*r1rrr0rrr?r*2rur r r r r r r r r r r r r r rrrrurrrrrrrrrrrrrrrrrrРисунок 1.3: Пример множества решений задачи с ограничениями (множествапересекаются).для которого находим01 = ⊕ ,(︃12 = ⊕ ⊕ =11 = ,2 3)︃(︃22 = 2 =,3 43 47 8)︃.Затем подсчитаем значения − 01 =(︁ − 11 =(︁(︃1 −1)︁1 −1)︁0 −1−2(︃1 03 4tr 12 = 4,)︃ (︃0)︃ (︃1111)︃(︀= 2, − 01 )︀1/2= 1,)︃= 4,(︀ − 11 tr1/2 (22 ) = 8/2 = 4.)︀1/3= 4/3,36После подстановки получаем, что минимум = 4 не изменился.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
