Диссертация (1150576), страница 11
Текст из файла (страница 11)
В дальнейшем будемвенство к виду считать, что неравенство сведено к данному виду.4.1.2Общая идеяДля начала рассмотрим случай, когда у матрицы = ( ), где = ( )– столбцы матрицы , отсутствуют нулевые компоненты. Если 11 1 ≥ 1, чторавносильно тому, что 1 ≥ −111 , то неравенство будет выполнено для первойкомпоненты вектора (= 1) вне зависимости от остальных векторов и прочих компонент вектора .
Изобразим координатные оси 1 , 2 , . . . , одну поддругой (каждую будем рассматривать отдельно от остальных). Отметим и подпишем на всех осях точки по следующему правилу: на -ой оси отмечаем точки−1 , указывая для каждой такой точки индекс . Если в какой-то точке оказывается несколько индексов, следует записать их всех.Если выбрана какая-либо точка из отмеченных на какой-либо оси в качестве соответствующего этой оси , то неравенство автоматически выполняетсядля , соответствующих индексу (или индексам) выбранной точки, а такжевсех, что находятся слева от нее. Получается, для решения задачи необходимои достаточно выбрать точки таким образом, чтобы в множество индексов,находящихся слева от выбранных, попадали все индексы 1, .
. . , вектора . Вчастности, понятно, что при отсутствии в матрице нулевых компонентов,неравенство будет выполняться в случае, если будет взята любая из крайнихправых отмеченных точек, при этом оставшиеся компоненты вектора можнобрать произвольно.Данная схема показывает и то, каким образом выглядит общее решениенеравенства: это объединение всевозможных наборов из точек, индексы кото-78рых покрывают числа 1, . . . , , вместе со всеми точками, находящимися правееэтих наборов (объединение -мерных конусов).
Примечательно, что нам не важно, что происходит между отмеченными точками: так как новые индексы прирассмотрении промежуточной точки не добавляются (фактически движемся по«грани» одного из конусов, при этом до пересечения с другим ничего нового неполучаем). То есть из абстрактного неравенства можно перейти к рассмотрениюдискретной модели (с узлами).В случае, когда в матрице есть нулевые компоненты, все остается попрежнему. Отличие только в том, что не для каждой оси самая правая точка будет давать решение неравенства при произвольных остальных (для этогонеобходимо и достаточно отсутствие нулевых компонент в соответствующемвекторе ), соответственно и число узлов в дискретной модели уменьшится наколичество нулевых компонент в матрице .
Иногда бывает удобно выписывать нулевые компоненты отдельно для каждой оси. Заметим, что с помощьюалгоритма можно наглядно увидеть, что у исходного неравенство всегда существует решение, если каждый из индексов 1, . . . , вектора встречается хотябы один раз на осях (это равносильно отсутствию нулевых строк матрицы ).Метод можно оптимизировать, если есть какая-либо априорная информацияо векторах или же присутствуют дополнительные ограничения.Пример реализации схемы приведен в приложении В.4.2Применение в задачах оптимизацииЧасто в задаче требуется найти не просто решение неравенства ≥ ,но и выбрать наиболее оптимальное по каким-нибудь параметрам.
Одной изсамых простых, но при этом достаточно важных, является задача линейнойоптимизации.794.2.1Линейная задача оптимизацииПусть заданы матрица ∈ X× и вектор ∈ X . Необходимо найти всевекторы ∈ X , которые решают задачуmin , ≥ .˜ (см. (4.1.1)). Так же можно считать, чтоБудем считать, что = 1 и = ̸= 0 для любой компоненты вектора (в противном случае, если = 0, тосоответствующая компонента не будет учитываться и можно взять ее максимальной, получив автоматическое выполнение неравенства для всех ненулевыхиндексов вектора , т.е.
сможем рассмотреть неравенство с меньшим количеством компонент).Для начала, отметим на осях точки по принципу, описанному в (4.1.2). Таккак компонента действует только на , а та, в свою очередь, только на вектор , то можем считать «весом» (или «стоимостью») -ой координатнойоси, и соответственно появляется возможность «склеить» все оси в одну результирующую, отмечая поочередно на ней все точки с осей, умноженные насоответствующие этим осям «веса». Так как информация о том, к какому вектору принадлежит конкретная точка не сохраняется, то помимо индекса нампридется указывать и номер вектора (оси), к которому она относится.После того, как на ось нанесены все узлы, простейшее решение получаетсяавтоматически в первой точке, на левом луче от которой будут встречаться всеиндексы 1, . .
. , (назовем ее критической). При этом все множество решенийбудет состоять из всех совокупностей точек, соответствующих наборам векторов, лежащих левее критической точки, при которых все индексы 1, . . . , всееще встречаются.4.2.2Варианты работы с нелинейными задачамиПо аналогии с линейной задачей оптимизации решается и нелинейная, гденужно минимизировать величину1 (1 ) ⊕ 2 (2 ) ⊕ · · · ⊕ ( )80в случае, если все – монотонно возрастающие функции. При нанесении точек на результирующую ось, для вычисления «веса» каждой точки необходимобрать значение соответствующей ей функции , примененной к этой точке. Приэтом, если ≡ на всем промежутке между двумя точками -ой оси, тона результирующей оси эти точки «склеятся».В случае произвольной функции помимо узловых точек придется такжерассматривать (соответственно отмечать и пересчитывать) и точки локальныхэкстремумов функций.
Так как это достаточно специфическая задача, то ееподробное рассмотрение не проводилось.4.3Пример использования методаПриведем пример поиска граничных решений неравенства (4.1).Рассмотрим следующее неравенство:⎛7 −6 −4⎜⎜ −7 −5⎜⎜ 0 −8⎝−3 46⎞⎛1⎞⎛−7⎟ ⎜⎟⎜⎜ 2 ⎟ ⎜1⎟⎟ ⎜⎟⎜⎜ ⎟≥⎜3 −9 ⎟⎠⎝ 3 ⎠ ⎝5 −248⎞⎟4⎟⎟1⎟⎠3Умножим каждую строку матрицы на соответствующий ей , переходя к неравенству:⎛141 313⎞⎛1⎞⎛0⎞⎜⎟ ⎜ ⎟⎟⎜⎜ −11 −9 4 −3 ⎟ ⎜ 2 ⎟ ⎜ 0 ⎟⎟ ⎜ ⎟⎜⎟⎜⎜ −1 −9 2 −10 ⎟ ⎜ ⎟ ≥ ⎜ 0 ⎟⎝⎠⎝ 3 ⎠ ⎝ ⎠40−6 1 2 −5Отметим «узлы» на координатных осях (Рис.
4.1). Получаем на первой оситочки (-14;1), (11;2), (1;3), (6;4), после упорядочивания получаем (-14;1), (1;3),(6;4), (11;2).На второй координатной оси в узле -1 получаем выполнение неравенствадля двух компонент: первой и четвертой, а в узле 9 для оставшихся: второй итретьей.На третьей оси отмечаем три узловые точки: -3 для первой компоненты, -4для второй, а также -2 для третьей и четвертой.811342-1416111,42,3-19213,4-4-3-21231243-1335104Рисунок 4.1: Узлы неравенстваНа последней оси получаем 4 узла: -13 для первой компоненты, 3 для второй,10 для третьей и 4 для четвертой.Для всех осей соответственно после упорядочивания:1.
(-14;1), (1;3), (6;4), (11;2)2. (-1;1,4), (9;2,3)3. (-4;2), (-3;1), (-2;3,4)4. (-13;1), (3;2), (4;4), (10;3)Так как нулевых компонент (−∞ для Rmax ,+ ) нет ни в одном из векторов, тоавтоматически получаются 4 «грани»: (−∞,−∞,−∞,10), (−∞,−∞,−2,−∞),(−∞,9, − ∞, − ∞) и (11, − ∞, − ∞, − ∞) (под знаком «−∞» понимаем, чтоданную компоненту можно брать произвольно). Оставшиеся грани получаемперебором: (1, − ∞, − ∞,5), (1, − 1, − ∞,3), (1, − 1, − 4, − ∞), (6, − ∞, − ∞,3),(6, − ∞, − 4, − ∞).
Перебор граней существенно сократило то, что выполнение82неравенства по третьей компоненте вектора на векторах 2 , 3 , 4 происходит только в крайних правых узлах (которые были автоматически включеныв самом начале). Поэтому можно не рассматривать дополнительные наборы, вкоторых 1 < 1 (при этом автоматически выполняется неравенство для 1 и 3компонент, остается обеспечить выполнение для 2 и 4).Других «граней» в неравенстве нет. Всякое решение получается прибавлением произвольного вектора к любому вектору из найденных наборов.83ЗаключениеИтоги выполненного исследования.
Разработаны новые методы и алгоритмы численного решения многомерных минимаксных задач тропическойоптимизации, а также программно-алгоритмическое обеспечение для их реализации в решении прикладных задач, возникающих при математическом моделировании естественнонаучных и научно-технических проблем.Получены следующие результаты:– Была полностью решена вычислительная задача с псевдоквадратичнойцелевой функцией и линейными ограничениями. В явном виде найдено еерешение, сформулированное в виде теоремы. Это решение представляетсобой точный численный метод с конечным количеством шагов. Был проведен анализ вычислительной сложности разработанного метода и предложена схема вычислений, трудоемкость которой не превосходит (5 ),где означает размерность задачи.– В работе была сформулирована и решена задача ликвидатора, котораязаключается в составлении плана работ по ликвидации последствий радиационной аварии.
Она была представлена в форме задачи сетевого планирования при наличии ограничений вида «старт-старт» и «старт-финиш»на порядок работ, а также дополнительных ограничений на сроки их выполнения. Далее задача сетевого планирования была переформулированав терминах идемпотентной математики как вычислительная задача тропической оптимизации, после чего было получено решение задачи в явномвиде в компактной векторной форме. Такое решение обеспечивает естественную алгоритмическую реализацию, а также позволяет модифицировать задачу, в том числе путем добавления дополнительных ограничений.84– Полученный результат использован для полного решения задачи ликвидатора.
Стоит отметить, что, хотя в работе рассматривалась задача составления плана мероприятий по ликвидации чрезвычайной ситуации толькос радиоактивным загрязнением территории, аналогичный подход можетбыть применен для планирования операции в случае химического и/илибактериологического (биологического) загрязнения.– Была полностью решена расширенная задача псевдочебышевской аппроксимации в тропическом векторном пространстве. В отличие от известныхранее результатов, которые позволяют получить одно из решений задачи, в диссертационной работе получено множество всех решений задачи ввиде семейства решений, которое задается множеством матриц, полученных из матрицы задачи путем оставления по одному элементу в каждойстроке и обнулением остальных. Предложены процедуры для упрощениявычислений, а также разработан алгоритм, реализующий эти процедуры.– Получены результаты исследования тропического векторного неравенстваи предложен вычислительный метод, позволяющий найти все множестворешений этого неравенства.Рекомендации.– Разработанные методы рекомендуются к применению в области созданияалгоритмов численного решения задач тропической алгебры, связанныхс задачами сетевого планирования, а также для решения прикладных задач, возникающих при математическом моделировании естественнонаучных и научно-технических проблем, таких, как, например, проблема ликвидации аварии антропогенной природы.– На основании предложенных диссертантом методов и их программнойреализации может быть разработано программное обеспечение для решения задач оптимизации.
Помимо этого, представленные реализации могутиспользоваться для последующих исследований рассмотренных задач, вчастности, с целью дальнейшего сокращения трудоемкости вычислений.Перспективы дальнейшей разработки темы. Возможные направленияисследовательской работы по теме диссертации:85– Добавление дополнительных ограничений к задаче с псевдоквадратичнойцелевой функцией и исследование возможностей ее применения для решения других вычислительных задач тропической оптимизации.– Использование задачи с псевдоквадратичной целевой функцией совместно с расширенной задачей псевдочебышевской аппроксимации, например,для нахождения численного решения в задаче оценки альтернатив на основе парных сравнений.– Улучшение численного алгоритма в расширенной задаче псевдочебышевской аппроксимации, необходимого для получения расчетной формулы, сцелью дальнейшего сокращения вычислительной сложности.86Список литературы1. Golan, J.
S. Semirings and their applications. / J. S. Golan. — Dordrecht:Kluwer Academic Publishers, 1999. — 381 p.2. Glazek, K. A guide to the literature on semirings and their applicationsin mathematics and information sciences. With complete bibliography. /K. Glazek. — Dordrecht: Kluwer Academic Publishers, 2002. — 392 p.3. Vandiver, H. S. Note on a simple type of algebra in which the cancellationlaw of addition does not hold. / H. S. Vandiver // Bulletin of the AmericanMathematical Society. — 1934.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
