Диссертация (1150576), страница 4

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

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

Будем считать, что уравнение = разрешимо для любых ∈ X и натуральных , то есть, что введенная операциявозведения в целую степень может быть распространена на случай рационального показателя степени.Далее будем опускать знак умножения для упрощения записи. Знаки отношений и оператор min будут пониматься в смысле порядка на X, описанноговыше.Примерами идемпотентных полуполей на множестве вещественных чиселявляютсяRmax ,+ = ⟨R ∪ {−∞}, max, +, −∞, 0⟩,Rmin ,+ = ⟨R ∪ {+∞}, min, +, +∞, 0⟩,Rmax,× = ⟨R+ ∪ {0}, max, ×, 0, 1⟩,Rmin,× = ⟨R+ ∪ {+∞}, min, ×, +∞, 1⟩,где R+ = { ∈ R| > 0}.

Дополнительные примеры могут быть найдены, вчастности, в [22, 70–74].Рассмотрим полуполе Rmax ,+ . В нем роль нуля играет −∞, а единицы – 0.Для любого ∈ R существует обратный по умножению −1 , который равенпротивоположному числу − в обычной арифметике.

Степень определенадля любых , ∈ R и соответствует арифметическому произведению . Порожденный сложением порядок на Rmax,+ совпадает с естественным линейнымпорядком на R.1.1.2Алгебра матрицОбозначим через X× множество матриц над X, состоящих из строк и столбцов. Матрица, все элементы которой равны 0, считается нулевой. Матри-18ца, у которой нет нулевых строк (столбцов) называется регулярной по строкам(столбцам).Операции сложения и умножения матриц вводятся аналогично операциям встандартной алгебре с заменой соответствующих покомпонентных операций на⊕ и ⊙. Пусть = ( ), = ( ) и = ( ) — матрицы подходящего размера,а — скаляр.

Тогда{ ⊕ } = ⊕ ,{} =⨁︁ ,{} = .=1Более подробную информацию о матрично-векторных операциях идемпотентной алгебры можно найти в работах [75–78].Транспонирование матрицы обозначается через .Мультипликативно сопряженным транспонированием матрицы = ( )будем называть преобразование, при котором она трансформируется в транс−−1понированную матрицу − = (− ) с элементами = , если ̸= 0 и− = 0 в противном случае.Рассмотрим квадратные матрицы из X× .

Обозначим через единичнуюматрицу, на главной диагонали которой стоят 1, а вне ее – 0. Для любой квадратной матрицы и натурального определим степень0 = , = −1 .След квадратной матрицы = ( ) вычисляется по формулеtr = 11 ⊕ · · · ⊕ .Для любых двух матриц и , а также скаляра из определения следавытекают равенстваtr( ⊕ ) = tr ⊕ tr ,tr() = tr(),tr() = tr .19Биномиальное тождество [52] для матриц и из X× , и натуральнойстепени имеет следующий вид( ⊕ ) =⨁︁⨁︁ 0 1 · · · ⊕ .=1 0 +···+ =−Для проверки этого утверждения достаточно заметить, что при раскрытиискобок будут получаться всевозможные произведения из сомножителей, изкоторых равны , − равны (при = получим ).Нетрудно проверить справедливость тождества [52]⨁︁( ⊕ ) ==1⨁︁⨁︁01 · · · ⊕=1 0≤0 +···+ ≤−⨁︁.(1.1)=1Здесь вначале были сгруппированы в одну сумму все слагаемые по степенямматрицы , а затем добавлена сумма степеней .Как обычно, матрица, состоящая из одного столбца или строки, образуетвектор.

Если не оговорено иначе, будем рассматривать векторы как векторстолбцы. Множество вектор-столбцов размерности с элементами из X обозначается X . Вектор считается регулярным, если у него отсутствуют нулевыекомпоненты.Мультипликативно сопряженным транспонированием вектора = ( ) называется преобразование, при котором трансформируется в вектор-строку−−1−− = (− ) с элементами = , если ̸= 0 и = 0 в противном случае.Для регулярных векторов и выполняется следующее соотношение [32]: − ≥ (− )−1 .(1.2)Отсюда следует, что если вектор является регулярным, то верно следующее неравенство:− ≥ .Для ненулевого вектора справедливо равенство [52, 79, 80]− = 1.(1.3)20Для любых регулярных векторов , ∈ X определим функцию расстоянияследующим образом:(,) = − ⊕ − .В дальнейшем будем называть такое расстояние псевдочебышевской метрикой.Заметим, что в рамках полуполя Rmax ,+ это выражение принимает вид(,) = max | − |,1≤≤что соответствует метрике Чебышева.Скаляр является собственным числом матрицы , если существует ненулевой вектор такой, что = .Максимальное собственное число называется спектральным радиусом матрицы и вычисляется по формуле=⨁︁tr1/ ( ).=1Вектор, все компоненты которого равны 1, обозначается как 1 = (1, .

. . ,1) .Выпуклой линейной комбинацией векторов 1 , . . . , называется выражение вида1 1 ⊕ · · · ⊕ ,где числа 1 , . . . , удовлетворяют условию1 ⊕ · · · ⊕ = 1.Это условие означает, что ≤ 1 для всех индексов = 1, . . . , , и по крайнеймере для одного выполняется равенство = 1.211.2Линейные неравенства и их решенияПриведем решения некоторых линейных неравенств, которые будут использованы ниже. Сначала предположим, что заданы матрица ∈ X× и регулярный вектор ∈ X . Требуется найти все векторы ∈ X , удовлетворяющиенеравенству ≤ .(1.4)Решение задачи обеспечивается следующим утверждением, доказательствокоторого приводится, например, в работах [32, 59].Лемма 1. Для любой регулярной по столбцам матрицы и регулярного вектора , все решения неравенства (1.4) имеют вид ≤ (− )− .Пусть теперь заданы матрица ∈ X× и вектор ∈ X . Необходимо найтивсе регулярные векторы , для которых выполняется неравенство ⊕ ≤ .(1.5)Чтобы записать решение задачи, сначала введем функцию, которая ставитв соответствие любой матрице ∈ X× скаляр по правилуTr() = tr ⊕ · · · ⊕ tr .При условии, что Tr() ≤ 1, введем оператор, известный также как «звездаКлини», который сопоставляет матрице матрицу* = ⊕ ⊕ · · · ⊕ −1 .Решение неравенства (1.5) получено в [31] в следующей форме.Теорема 1.

Для любой матрицы и вектора справедливы следующиеутверждения:1. Если Tr() ≤ 1, то все регулярные решения неравенства (1.5) имеютвид = * , где – регулярный вектор такой, что ≥ .222. Если Tr() > 1, то регулярных решений не существует.1.3Задачи тропической оптимизацииТеперь рассмотрим ряд задач оптимизации, которые формулируются в терминах тропической математики, состоят в минимизации нелинейных функционалов, и могут иметь ограничения в виде линейных векторных неравенств [30].Решение многих таких задач опирается на экстремальное свойство спектрального радиуса матрицы и связано с его вычислением [31, 52, 54, 59]. Это свойствосостоит в том, что спектральный радиус матрицы определяет минимум функции, которая задается этой матрицей с использованием оператора мультипликативно сопряженного транспонирования следующим образом.Пусть спектральный радиус матрицы ∈ X× равен .

Рассмотрим задачуmin− ,(1.6)где минимум берется на множестве всех регулярных векторов ∈ X . Такаязадача имеет приложения, например, в сетевом планирование [40,59], оптимальном размещении объектов [40, 54, 81], принятии решений [55, 82] и в других областях.Полное решение этой задачи приводится в [31, 52, 59] в следующем виде.Лемма 2. Пусть – матрица со спектральным радиусом > 0. Тогда минимум в задаче (1.6) равен , а все регулярные решения задачи имеют вид = (−1 )* , ∈ X .Известны решения для вариантов задачи (1.6) с целевой функцией более общего вида.

Пусть, например, в дополнение к матрице ∈ X× заданы векторы, ∈ X и скаляр ∈ X. Требуется найти все регулярные векторы ∈ X ,обеспечивающиеmin− ⊕ − ⊕ − ⊕ .Справедливо следующее утверждение, которое было получено в [59].(1.7)23Теорема 2. Пусть – матрица со спектральным радиусом > 0, а –регулярный вектор. Тогда минимум в задаче (1.7) равен=⊕⨁︁( − −1 )1/(+1) ⊕ ,(1.8)=1а все регулярные решения задачи имеют вид = (−1 )* ,−1 ≤ ≤ ( − (−1 )* )− .(1.9)Другой вариант расширения задачи на экстремальное свойство спектрального радиуса – добавление ограничений на множество допустимых значений.Пусть заданы матрицы , ∈ X× и вектор ∈ X . Необходимо определить множество всех регулярных векторов ∈ X , на которых достигаетсяминимум в задачеmin − ⊕ − , ≤ .(1.10)Теорема 3. Пусть – матрица со спектральным радиусом > 0, а –матрица, для которой Tr() ≤ 1.

Тогда минимум в задаче (1.10) равен =⊕−1⨁︁⨁︁tr1/ ( 1 · · · ),=1 1≤1 +···+ ≤−а все регулярные решения имеют вид = (−1 ⊕ )* , ≥ −1 .Ниже будет предложено решение задачи, которая является дальнейшимобобщением задачи (1.10) с целевой функцией, которая определена также, какв задаче (1.7).1.4Задача оптимизации с ограничениямиВ этом разделе изучается новая задача оптимизации с нелинейной целевойфункцией и ограничениями в форме линейного неравенства [63, 65, 67]. Приме-24няется подход, развитый в [31,52,53,59], при котором вводится дополнительнаяпеременная, описывающая минимальное значение целевой функции.

Затем задача сводится к решению неравенства, в котором эта переменная выступает вроли параметра. Необходимые и достаточные условия существования решенийнеравенства используются для вычисления параметра, а общее решение неравенства берется в качестве решения исходной задачи оптимизации.Пусть заданы матрицы , ∈ X× , векторы , ∈ X и скаляр ∈ X.Требуется найти все регулярные векторы ∈ X , которые решают задачуmin − ⊕ − ⊕ − ⊕ , ≤ .(1.11)Теорема 4.

Пусть – матрица со спектральным радиусом > 0, а –матрица, для которой Tr() ≤ 1. Для любого натурального и = 1, . . . ,введем обозначения0 =⨁︁,⨁︁ = 0 1 · · · .0≤0 +···+ ≤−=0Тогда минимум в задаче (1.11) равен=⊕⨁︁1/tr( ) ⊕=1−1⨁︁( − ,−1 )1/(+2) ,(1.12)=0а все регулярные решения имеют вид = (−1 ⊕ )* ,−1 ≤ ≤ ( − (−1 ⊕ )* )− .(1.13)Доказательство. Сначала заметим (по лемме 2), что− ⊕ − ⊕ − ⊕ ≥ − ≥ > 0,откуда следует, что целевая функция в (1.11) ограничена снизу. Обозначимминимум целевой функции на множестве всех регулярных векторов через .25Тогда все регулярные решения задачи (1.11) получаются из системы− ⊕ − ⊕ − ⊕ = , ≤ .Так как по предположения – минимум целевой функции, то можно заменить равенство на неравенство− ⊕ − ⊕ − ⊕ ≤ , ≤ .(1.14)Первое неравенство в (1.14) равносильно системе неравенств− ≤ ,− ≤ , − ≤ , ≤ .Перемножив соответствующие части второго и третьего неравенств, получим соотношение − ≤ − − ≤ 2 .Следовательно, ≥ ( − )1/2 .

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

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