Диссертация (Решение минимаксных задач размещения на плоскости с прямоугольной метрикой на основе методов идемпотентной алгебры), страница 4

Использование таких полуколец объясняется тем, что они естественным образом появляются при решении задач, возникающих на практике. Некоторые множества обладают структурой полукольца. Примерами могут служить натуральные, целые и рациональные числа относительно заданных на них операций сложения и умножения. Повидимому, как отмечается в работе Д. Голана [84], впервые понятие полукольцабыло использовано в работах Ф. Макалая [85] и Е. Нетера [86], опубликованныхв начале двадцатого века, в контексте изучения идеалов некоторых колец.

В явном виде понятие полукольца появляется в работе Х. Вандивера [87], связаннойс аксиоматизацией натуральных чисел. Изучение тропической математики, какотдельной ветви прикладной математики, началось в 1950-х годах. Многие авторы связывают начало развития полуколец с идемпотентным сложением и ихприложений с публикацией работы С. К. Клини [88] в 1956 году.Идемпотентная алгебра оказалась достаточно удобным инструментом прирешении широкого круга задач, возникающих в таких областях, как комбинаторика, теория оптимизации, дискретная математика и алгебраическая геометрия. Также методы тропической математики можно эффективно использоватьпри решении задач имитационного моделирования и теории управления, а также при анализе производственных систем [89–91].19Дальнейшее развитие тропической математики (раздел прикладной математики, включающий в себя идемпотентную алгебру) можно связать с публикациями Н.

Н. Воробьева [11–13], в работах которого рассматривалась теорияидемпотентных полумодулей. В его статьях для обозначения идемпотентныхполуколец использовались термины экстремальная алгебра и экстремальнаяматематика. «К сожалению, идеи Н. Н. Воробьева в свое время не получилиширокой известности, поэтому его терминология не прижилась и сейчас почтине используется,» – отмечает в своей работе Г. Л. Литвинов [92].Большое влияние на развитие методов тропической математики оказали работы Р. А. Кунингхайм-Грина [20, 90], в которых описан ряд подходов к решению различных задач в терминах тропической математики. Отметим монографию [90].

В ней рассматриваются схожие вопросы с теми, что ранее изучалисьН. Н. Воробьевым, но используется несколько иная алгебраическая техника.При этом решения представлены в удобной и компактной матричной форме.Значительный вклад в развитие идемпотентной математики внесли представители научной школы, возглавляемой академиком В. П. Масловым, разработавшие теорию идемпотентного функционального анализа (области исследования полумодулей функций со значением в полукольце с идемпотентным сложением) [14, 22, 93, 94]. Работы представителей этой научной школы заложилитеоретические и методологические основы идемпотентной математики, котораявключает в себя идемпотентную алгебру, идемпотентный анализ и идемпотентный функциональный анализ.В работах [21, 72, 73] изучен класс задач оптимизации с ограничениями сцелевой функцией, зависящей от переменных, для которой существует представление в виде максимума функций, каждая из которых зависит от однойсобственной переменной.

Такой класс функций называется max-сепарабельным.Подробный обзор моделей, методов и приложений тропической математикипредставлен в работах [14, 28, 40, 43, 47]. Важным объектом изучения тропической математики, активно использующимся при решении практических задач,является (max ,+)-алгебра. Множество вещественных чисел, дополненное минус бесконечностью, с заданными на нем операциями взятия максимума из пары чисел (операция тропического сложения) и обычного сложения (операция20тропического умножения) образует тропическое полукольцо, которое обычноназывают (max ,+)-алгеброй.Развитие методов тропической математики во многом обусловлено тем, чторяд задач, которые являются нелинейными в обычной алгебре, может бытьсведен к линейным.

Отметим, что многие понятия линейной алгебры, а такжевычислительные процедуры, такие как решение систем линейных уравнений,проблема поиска собственного значения и собственного вектора, метод Якоби иГауса-Зейделя имеют собственные аналоги в тропической алгебре [47]. Следуетожидать, что использование общих методов и результатов линейной алгебры внекоторых случаях позволит получать решения в более удобной форме и прощеинтерпретировать результат. Часто решение в терминах тропической математики позволяет найти полные решения некоторых задач в ситуациях, где этоиначе было бы непросто или невозможно.Пример применения методов тропической математики при решении задачна сетях Петри и на графах, предложен в работе [43], где рассматривается железнодорожная сеть между двумя городами, представленная в терминах тропической математики.Подходы к решению прикладных производственных задач при помощи методов (max ,+)-алгебры приведены в работе П. Бутковича [29].

Исследованиюсистем с очередями посвящены работы [48, 95], исследование задачи принятиярешений для анализа результатов оценки альтернатив на основе парных сравнений проведено в [96]. Большой класс задач тропической оптимизации изученв работах Н. К. Кривулина [1, 97–99]. Полные решения в явном виде некоторыхзадач математического программирования с использованием методов тропической оптимизации получены в работе [100].1.2Идемпотентное полуполеПриведем обзор основных понятий и результатов тропической математики,на которые опирается последующее исследование и решение задач размещения.Более детальное рассмотрение вопросов, связанных с идемпотентной алгебройпредставлено в работах [21, 47, 90].21Введем в рассмотрение числовое множество X, на котором определены ассоциативные и коммутативные операции сложения ⊕ и умножения ⊗. Обозначимчерез ⟨X, ⊕, ⊗, 0, 1⟩ заданное на X при помощи этих операций коммутативноеполукольцо с нулем 0 и единицей 1.

Сложение будем считать идемпотентным(т.е. для любого числа ∈ X выполняется ⊕ = ), а умножение – обратимым (т.е. для каждого ̸= 0 существует обратный элемент −1 такой, что⊗−1 = 1). Так как ⟨X∖{0}, ⊗, 1⟩ образует коммутативную группу по умножению, то описанную структуру ⟨X, ⊕, ⊗, 0, 1⟩ принято называть идемпотентнымполуполем.Операция возведения в степень с целым показателем вводится стандартнымобразом. Для любого ненулевого числа ∈ X и натурального числа определим0 = 1, = ⊗ −1 , − = (−1 ) и 0 = 0. Будем считать, что операция возведения в целую степень ненулевого числа может быть естественным образомраспространена в полуполе на случай рационального показателя степени.Далее для упрощения математических выкладок знак умножения ⊗ в алгебраических выражениях, как обычно, будет опускаться.В силу того, что сложение идемпотентно, можно определить отношение частичного порядка ≤ так: ≤ тогда и только тогда, когда ⊕ = .

Изэтого определения следует пара неравенств ≤ ⊕ и ≤ ⊕ , а такжеравносильность неравенства ⊕ ≤ и системы неравенств ≤ и ≤ для любых ,, ∈ X. Кроме того, нетрудно проверить свойства монотонностиопераций сложения и умножения, по которым при условии ≤ для любого выполняются неравенства ⊕ ≤ ⊕ и ≤ . Наконец, для любых, ̸= 0 из неравенства ≤ следует −1 ≥ −1 . В дальнейшем будем дополнительно предполагать, что введенный частичный порядок является линейным.Кроме того, несложно проверить неравенство 1/2 1/2 ≤ ⊕ , которое являетсятропическим аналогом неравенства между геометрическим и арифметическимсредними.В качестве примеров алгебраических структур рассматриваемого типа можно привести вещественные идемпотентные полуполяRmax ,+ = ⟨R ∪ {−∞}, max, +, −∞, 0⟩, Rmin ,+ = ⟨R ∪ {+∞}, min, +, +∞, 0⟩,Rmax ,× = ⟨R+ ∪ {0}, max, ×, 0, 1⟩,Rmin ,× = ⟨R+ ∪ {+∞}, min, ×, +∞, 1⟩,22где R – множество вещественных чисел и R+ = { ∈ R| > 0}.Нулевым элементом для полуполя Rmax ,+ , которое обычно называют(max ,+)-алгеброй, является −∞, единичным – число 0.

В этом полуполе любому числу ∈ R можно сопоставить обратный −1 , который совпадает с противоположным числом − в обычной алгебре. Для любой пары чисел , ∈ Rможно определить степень , значение которой равно арифметическому произведению . Порядок, порожденный операцией идемпотентного сложения,совпадает с обычным линейным порядком на множестве R.1.3Идемпотентная алгебра векторов и матрицМножество вектор-столбцов размерности , с элементами из X будем обозначать через X .

Для любой пары векторов = ( ) и = ( ) из X , скаляра ∈ X верны следующие покомпонентные равенства:{ ⊕ } = ⊕ , {} = .После ввода этих операций, множество X оказывается конечномерным полумодулем над идемпотентным полукольцом X.Операции сложения векторов и умножение вектора на скаляр являются монотонными, то есть для любых , , ∈ X и числа ∈ X из покоординатногонеравенства ≤ следует ⊕ ≤ ⊕ , ≤ .Регулярным вектором назовем вектор = ( ) ∈ X , все элементы которого ненулевые, то есть ̸= 0 для всех = 1, . .

. ,. Нулевым назовем вектор0 = (0, . . . , 0) ∈ X .Вектор линейно зависит от набора векторов 1 , . . . , , если верно равенство = 1 1 ⊕ . . . ⊕ для некоторых скаляров 1 , . . . , ∈ X.Для любого ненулевого вектора определена операция мультипликативно сопряженного транспонирования, которая каждому вектор-столбцу ∈ X ставит−1в соответствие вектор-строку − ∈ X с элементами − = , если ̸= 0, и− = 0 в противном случае.23Обозначим через X× множество матриц из строк и столбцов, состоящих из элементов множества X.Матрицу, все элементы которой равны 0, будем называть нулевой.

Регулярной по строкам (по столбцам) является матрица без нулевых строк (столбцов).Матрица, регулярная по строкам и по столбцам, называется регулярной.Сложение и умножение матриц, а также умножение матрицы на скалярпроизводится по тем же правилам, что и в обычной математике, в которыхскалярные операции имеют иной смысл. Так, если = ( ), = ( ) и =( ) матрицы, состоящие из элементов полукольца X, подходящего размера дляосуществления операций сложения и вычитания, а ∈ X скаляр, то верныследующие выражения:{ ⊕ } = ⊕ ,{} =⨁︁ ,{} = .Описанные матричные операции обладают свойством монотонности, то естьдля любых подходящих по размеру матриц , , , и числа ∈ X из покоординатного неравенства ≤ следует ⊕ ≤ ⊕ , ≤ , ≤ .Рассмотрим квадратные матрицы из множества X× .