Диссертация (1150701), страница 4
Текст из файла (страница 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× .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
