Диссертация (1150701), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Матрица, диагональные элементы которой равны 1, а остальные элементы равны 0, называетсяединичной и обозначается . Для любой матрицы и целого числа > 0выполнены следующие соотношения:0 = , = −1 = −1 .След матрицы = ( ),=1 – это величина, вычисляемая по формуле:tr = 11 ⊕ . . . ⊕ .Матрицей Клини называется матрица* = ⊕ ⊕ · · · ⊕ −1 .24Под собственным числом матрицы ∈ X× будем понимать скалярнуювеличину , для которой существует вектор ∈ X ∖{0} такой, что выполняетсяравенство = .Собственным вектором матрицы будем называть любой вектор ̸= 0, удовлетворяющий этому равенству.Максимальное собственное число называется спектральным радиусом и вычисляется по формуле:=⨁︁tr1/ ( ).(1.1)=11.4Предварительные результатыВ работе [74] изучается минимаксная задача размещения одиночного объекта на плоскости с прямоугольной метрикой (задача Ролса), которая сводится втерминах тропической математики к задаче нахождения таких векторов , прикоторых достигается минимумmin − ,(1.2)где − обозначает мультипликативно сопряженный вектор и – некотораяматрица.Известно [101], что минимум в задаче (1.2) равен спектральному радиусу матрицы и достигается на любом собственном векторе, который отвечает .Для решения задачи размещения Ролса в работе [74] потребовалось показать,что на самом деле множество решений задачи (1.2) шире, чем множество собственных векторов матрицы .

Было построено решение задачи Ролса в явномвиде, однако проверить, что таким образом получены все решения и другихрешений нет, при этом не удалось.Новое общее решение задачи (1.2) при весьма общих условиях было затемнайдено в работах [49,102,103], что позволяет теперь уточнить полученные в [74]результаты.25В работах [49, 102] все вектора, на которых достигается минимум в задаче(1.2), представлены в замкнутой векторной форме.

Сформулируем следующуютеорему.Теорема 1. [103] Пусть — матрица со спектральным радиусом ̸= 0 и = −1 . Тогда минимум задачи (1.2) равен . Общее регулярное решениебудет иметь вид: = * , ∈ X26Глава 2РешениенекоторыхзадачтропическойоптимизацииВ этом разделе диссертации будет рассмотрено несколько задач тропической оптимизации с одной, двумя и тремя переменными. Будут предложеныдва подхода – матричный, основанный на использовании результатов, описанных в теореме 1, и скалярный, состоящий в преобразовании задачи к системепараметризованных неравенств, для получения аналитических решений в явном виде с использованием методов тропической математики.2.1Задача тропической оптимизации в матричной формеПусть задан набор чисел ,,, ∈ X, удовлетворяющих условию ,,, > 0.Сформулируем задачу тропической оптимизации. Необходимо найти ненулевые числа , ∈ X, на которых достигается минимум целевой функцииmin,∈X−1 −1 ⊕ −1 ⊕ −1 ⊕ .(2.1)Чтобы перейти к векторной форме записи задачи, введем вектор и матрицу⎛⎞⎜⎟⎟,=⎜⎝⎠−1⎛⎞0 0⎜⎟⎟.=⎜0⎝⎠0 027Теперь вместо исходной задачи можно решить расширенную задачуmin3 − ,(2.2)∈Xа затем выбрать из числа ее решений те векторы, у которых первый и последнийэлемент – взаимно-обратные в терминах тропической математики.2.1.1Анализ и решение задачиПусть – спектральный радиус матрицы и = −1 .По теореме 1, минимум в задаче (2.2) равен .

Все решения имеют вид = * ,(2.3) ∈ X3 ,и поэтому образуют линейную оболочку столбцов матрицы * .Для определения спектрального радиуса найдем степени матрицы ⎛⎞0⎜⎟⎟2 = ⎜⎝ 0 ⊕ 0 ⎠ ,0⎛2⎞0 ⊕ 0⎜⎟22 ⎟,3 = ⎜0 ⊕ ⎠⎝ ⊕ 0 ⊕ 20а затем вычислим = tr() ⊕ tr1/2 (2 ) ⊕ tr1/3 (3 ) = ( ⊕ )1/2 .После возведения в квадрат равенство принимает следующий вид:2 = ⊕ .Тогда после замены знака равенства на знак неравенства и применениясвойств введенного линейного порядка, получаем2 ≥ ,2 ≥ ,4 ≥ .28Чтобы записать решения расширенной задачи (2.2), необходимо вычислитьматрицу⎛*= ⊕ ⊕−1−2⎞1 ⎜⎟−1−1⎟.=⎜1⎝⎠−2−1 12Нетрудно проверить, что второй столбец матрицы * является линейнойкомбинацией двух других. Действительно,⎛⎞⎛−2⎞⎛−1⎞1 ⎜⎟⎜⎟⎜⎟−1⎟ ⊕ −1 ⎜ −1 ⎟ = ⎜ 1 ⎟ .−1 ⎜⎝⎠⎝⎠ ⎝⎠−2−1 1 Тогда для представления всех решений (2.3) достаточно построить линейную оболочку только первого и последнего столбцов * в форме⎛−2⎞1 ⎜⎟−1−1⎟=⎜⎝ ⎠ ,−2 1 ∈ R2 .Переходя к скалярной форме записи, получим три равенства1 = 1 ⊕ −2 2 ,2 = −1 1 ⊕ −1 2 ,3 = −2 1 ⊕ 2 .Для решения исходной задачи сначала нужно найти все векторы =(1 ,2 ,3 ) , которые удовлетворяют этим равенствам и условию для координат1 = −13 .После этого останется найти все векторы (,) , координаты которых определяются равенствами = 1 ⊕ −2 2 , = −1 1 ⊕ −1 2 .(2.4)29Условие для первой и третьей координаты записывается в виде1 ⊕ −2 2 = (−2 1 ⊕ 2 )−1 .После умножения на −2 1 ⊕ 2 имеем равенство−2 12 ⊕ 1 2 ⊕ −2 22 = 1.Полученное равенство равносильно системе неравенств1 ≤ −1/2 −1/2 ,1 2 ≤ 1,2 ≤ −1/2 −1/2 ,(2.5)в которой хотя бы одно неравенство должно выполняться как равенство.Рассмотрим три случая, в которых одно из неравенств заменяется равенством.Случай 1.

Первое неравенство выполняется как равенствоЗаменим первое неравенство в (2.5) равенством, которое будет однозначноопределять значение 1 . После подстановки этого значения во второе неравенство имеем систему1 = −1/2 −1/2 ,2 ≤ −1 1/2 1/2 ,2 ≤ −1/2 −1/2 .В силу условия ≤ 4 выполняется неравенство−1 1/2 1/2 ≤ −1/2 −1/2 ,а тогда система принимает вид1 = −1/2 −1/2 ,2 ≤ −1 1/2 1/2 .Подставим найденные значения в решение (2.4).

Применяя неравенства ≤ 2 , ≤ 2 ,30находим, что−2 2 ≤ −3 1/2 1/2 ≤ 1 ,−1 2 ≤ −2 1/2 1/2 ≤ −1 1 .Тогда решение (2.4) принимает вид = 1 = −1/2 −1/2 , = −1 1 = 1/2 −1/2 .Нетрудно проверить, что при условии = 1 решение можно записать вформе(︃)︃(︃=2−1 (1− − 1− − )1/2(1− −1 − )1/2)︃.(2.6)Случай 2. Второе неравенство выполняется как равенствоПредположим, что второе неравенство в системе (2.5) является равенством.В этом случае система принимает вид1 ≤ −1/2 −1/2 ,1 2 = 1,2 ≤ −1/2 −1/2 .Воспользуемся равенством 2 = 1−1 .

Первое и третье условия системы можно объединить в виде двойного неравенства−1 1/2 1/2 ≤ 1 ≤ −1/2 −1/2 .Чтобы записать решение исходной задачи в форме (2.4), сначала заметим,что−2 2 ≤ −1 1/2 1/2 ≤ 1 .При этом, если 2 = , то имеем неравенство−1 2 ≤ −1 1/2 1/2 ≤ −1 1 ,откуда следует, что решение можно записать в виде = 1 , = −1 1 ,−1 1/2 1/2 ≤ 1 ≤ −1/2 −1/2 .31Введем параметр 0 ≤ ≤ 1 и запишем решение в параметрической форме.Сначала заменим двойное неравенство для 1 выражением1 = (1−)/2 (−1)/2 /2 −/2 = 2−1 (1− − 1− − )1/2 .Заметим, что при = 0 это выражение совпадает с левой границей двойногонеравенства для 1 , а при = 1 оно равно правой границе.После подстановки приходим к результату, который обобщает решение (2.6)в форме(︃)︃(︃=2−1 (1− − 1− − )1/2(1− −1 − )1/2)︃0 ≤ ≤ 1.,(2.7)В случае, когда 2 = , справедливо неравенство−1 1 ≤ −1 1/2 1/2 ≤ −1 2 .С учетом этого неравенства, имеем = 1 , = −1 2 = 1/2 −1/2 1−1 ,−1 1/2 1/2 ≤ 1 ≤ −1/2 −1/2 .Записывая двойное неравенство для 1 в параметрическом виде1 = /2 −/2 (1−)/2 (−1)/2 = 2−1 (1− − 1− − )1/2 ,снова получаем решение задачи, представленное как (2.7).Случай 3.

Третье неравенство выполняется как равенствоЗаменив третье неравенства в системе (2.5) на равенство, получаем1 ≤ −1/2 −1/2 ,1 ≤ −1 1/2 1/2 ,2 = −1/2 −1/2 .В силу неравенства −1/2 −1/2 ≥ −1 1/2 1/2 , система принимает вид1 ≤ −1 1/2 1/2 ,2 = −1/2 −1/2 .32Учитывая, что1 ≤ −1 1/2 1/2 = −2 2 ,−1 1 ≤ −2 1/2 1/2 ≤ −1 2 ,имеем = −2 2 = −1 1/2 1/2 , = −1 2 = 1/2 −1/2 .Осталось проверить, что это решение совпадает с (2.6) при = 0.2.1.2Формулировка основного результатаРезультаты анализа задачи (2.1) для всех рассмотренных случаев можнообъединить в виде следующего утверждения, которое уточняет решение, полученное в [74].Теорема 2. Минимум в задаче (2.1) равен = ( ⊕ )1/2и достигается тогда и только тогда, когда(︃)︃(︃=2−1(1− − 1− − 1/2))︃(1− −1 − )1/2,0 ≤ ≤ 1.Запишем общий результат в терминах обычных арифметических операций.В качестве примера, рассмотрим полученный результат в контексте (max ,+)алгебры. Для другого полуполя запись будет иной.

Полное решение исходнойзадачи (2.1) представим в следующей форме.Следствие 1. Минимум в задаче (2.1) равен = max( + , + )/2и достигается тогда и только тогда, когда(︃)︃(︃=(2 − 1) + (1 − )( + )/2 − ( + )/2(1 − )( − )/2 − ( − )/2)︃,0≤≤133Заметим, что последнее решение по форме соответствует результатам [62,63].2.2Решение задач оптимизации в скалярной формеВ этом разделе для решения задач тропической оптимизации с ограничениями применим подход, развитый в работе [49], который заключается в заменеисходной задачи оптимизации на параметризованную систему неравенств.2.2.1Решение задачи с одной переменнойПусть заданы числа ,,,,, ∈ X, удовлетворяющие условию ,,,,, >0, а также вещественное число . Требуется найти ненулевые решения ∈ Xзадачиmin −1 ⊕ −(−1) ⊕ −(+1) ⊕ +1 ,∈X(2.8) ≤ ≤ .Следующий результат описывает все решения рассматриваемой задачи.Теорема 3.

Пусть ,,,,, > 0 и – вещественное число. Справедливыследующие утверждения:1) если < −1, то минимум в задаче (2.8) равен = 1/2 1/2 ⊕ (+1)/2 (−1)/2 ⊕ (+1)/2 (−1)/2 ⊕ 1/2 1/2 ⊕⊕ −1 ⊕ −(−1) ⊕ −(+1) ⊕ +1и достигается тогда и только тогда, когда = ((−1 )1/(−1) ⊕(−1 )1/(+1) ⊕ )1− ((−1 )1/(−1) ⊕(−1 )1/(+1) ⊕ −1 )− ;2) если −1 ≤ ≤ 1, то минимум равен = 1/2 1/2 ⊕ (+1)/2 −(−1)/2 ⊕ (+1)/2 −(−1)/2 ⊕ 1/2 1/2 ⊕⊕ −1 ⊕ −(−1) ⊕ −(+1) ⊕ +134и достигается тогда и только тогда, когда = ((−1 )1/(−1) ⊕(−1 )1/(+1) ⊕ )1− ((−1 )1/(−1) ⊕(−1 )1/(+1) ⊕ −1 )− ;3) если > 1, то минимум равен = 1/2 1/2 ⊕ (+1)/2 (−1)/2 ⊕ (+1)/2 (−1)/2 ⊕ 1/2 1/2 ⊕⊕ −1 ⊕ −(−1) ⊕ −(+1) ⊕ +1и достигается тогда и только тогда, когда = ((−1 )1/(−1) ⊕(−1 )1/(+1) ⊕ )1− ((−1 )1/(−1) ⊕(−1 )1/(+1) ⊕ −1 )− ,где – любое вещественное число, удовлетворяющее условию 0 ≤ ≤ 1.Доказательство.

Характеристики

Список файлов диссертации