Диссертация (1150576), страница 3
Текст из файла (страница 3)
Основные результаты работы представлены в 2 печатныхработах [63,64], опубликованных в рецензируемых научных изданиях, рекомендованных ВАК при Минобрнауки России, переводы которых [65,66] индексируются в международных библиографических базах Scopus и Web Of Science.Всего по результатам диссертации автором опубликовано 5 печатных работ[63, 64, 67–69].В совместных работах с Кривулиным Н. К. [63, 64, 67, 69] соискателю принадлежит формулировка и доказательства теорем о решении задачи с псевдоквадратичной целевой функцией и линейными ограничениями, а также расширенной задачи псевдочебышевской аппроксимации в тропическом векторномпространстве, разработка алгоритмов и программных средств, проведение вычислительных экспериментов для верификации полученных результатов, соавтору принадлежат постановки задач и выбор методов решения.Cтруктура работы.
Диссертационная работа состоит из введения, четырех глав, заключения и трех приложений. Полный объем диссертации составляет 123 страницы машинописного текста. Список литературы содержит 103наименования.Во введении обосновывается актуальность темы диссертации, приводитсяобзор соответствующей литературы, определены цели и задачи работы, аргументируется их научная ценность.В главе 1 рассматривается задача с псевдоквадратичной целевой функциейи линейными ограничениями и разработан метод ее решения. В § 1.1 описываются основные понятия и результаты тропической математики, на которыеопираются решения, представленные в остальной части работы.
В § 1.2 приведены решения базовых векторных неравенств идемпотентной алгебры. В § 1.3приведены известные задачи тропической математики, решение которых опирается на экстремальное свойство спектрального радиуса матрицы и связано с13его вычислением. В § 1.4 формулируется и решается обобщенная задача с псевдоквадратичной целевой функцией и линейными ограничениями, решение которой формулируется в виде теоремы и является основным результатом даннойглавы. Это решение представляет собой точный численный метод с конечнымколичеством шагов. В § 1.5 проводится оценка вычислительной сложности представленного численного метода и приводится схема вычислений, при которойрешение находится за полиномиальное по размерности задачи время. В § 1.6 демонстрируются численные примеры решения вариантов задачи с различнымиограничениями и приводится наглядная графическая иллюстрация.В главе 2 рассматривается решение задачи планирования операции по ликвидации последствий радиационной аварии с помощью методов идемпотентнойалгебры, которое получено путем применения теоремы, сформулированной идоказанной в предыдущей главе.
В § 2.1 формулируется задача ликвидатора,которая заключается в составлении плана работ по ликвидации последствийаварии. Далее строится математическая модель, которая может быть использована для решения задачи различными способами, например, методами линейного программирования. Затем в § 2.2 задача формулируется в терминахидемпотентной математики, что позволяет применить для ее решения разработанный в главе 1 точный численный метод и получить решение в явном виде.В § 2.3 подробно рассматривается наглядный численный пример.В главе 3 приводится решение расширенной задачи псевдочебышевской аппроксимации в тропическом векторном пространстве.
В § 3.1 проводится обзоризвестных результатов в данной области, из которого, в частности, следует, чтов имеющихся исследованиях было получено только частичное решение задачиаппроксимации. В § 3.2 проводится анализ расширенной задачи псевдочебышевской аппроксимации, вычисляется минимум целевой функции, предъявляетсяодно из решений и строится система неравенств, которая определяет множествовсех решений.
Далее в § 3.3 вводится понятие разреженной матрицы задачи, которая получается из исходной матрицы путём обнуления всех элементов, которые меньше некоторого порогового значения. Показывается, что замена матрицы задачи на разреженную не изменяет минимальное значение целевой функции и множество решений. В § 3.4 представлено полное решение расширеннойзадачи аппроксимации в виде семейства решений, которое задается множеством14матриц, полученных из разреженной матрицы задачи.
Для этого сначала осуществляется расширение множества решений, а затем представляется полноерешение расширенной задачи аппроксимации в виде семейства решений, которое задается множеством матриц, полученных из разреженной матрицы задачипутем дальнейшего обнуления ее элементов. В качестве прямого следствия этого результата получено полное решение задачи чебышевской аппроксимации втропическом векторном пространстве. Перебор всевозможных матриц для построения подмножеств семейства решений задачи в соответствии с полученнымрезультатом (для получения расчетной формулы) может представлять определенные трудности.
Кроме того, некоторые семейства решений могут содержаться в других семействах и поэтому при записи общего решения могут бытьотброшены. В § 3.5 описываются процедуры, позволяющие во многих случаяхсократить число подмножеств, которые необходимо учесть при построении общего решения. В § 3.6 рассматривается алгоритм, необходимый для нахождениярасчетной формулы. Численный пример, демонстрирующий решение задачи сприменением описанных процедур, представлен в § 3.7.В главе 4 проведено исследование тропического линейного векторного неравенства.
Так как в явном виде множество всех решений для этой задачи получить не удается ввиду сложности данного множества, то в § 4.1 предлагаетсяметод, с помощью которого можно получить все решения алгоритмически. В§ 4.2 рассматриваются возможности применения предложенного метода в линейной и нелинейной задачах тропической оптимизации, а в § 4.3 демонстрируется численный пример использования метода.В заключении представлены основные результаты работы, а также рекомендации и предложения по дальнейшему проведению исследований по темеработы.В приложении А представлено описание процедур и компьютерный код методов, применявшихся для расчетов в главах 1 и 2.В приложении Б приводится компьютерный код методов, использованныйдля исследования расширенной задачи псевдочебышевской аппроксимации главы 3, а также для вычислений в примерах.В приложении В представлено описание предлагаемой схемы решения тропического линейного векторного неравенства главы 4.15Глава 1Задачаспсевдоквадратичнойцелевойфункцией и линейными ограничениямиОдна из задач оптимизации, которая рассматривалась еще в работе [6], связана с минимизацией функции, определенной на множестве вещественных векторов.
В терминах тропического полукольца Rmax,+ , где максимум выступаетв роли сложения, а арифметическое сложение в роли умножения, эта задачаприобретает формуmin− ,где – квадратная матрица, – неизвестный вектор, − – вектор, полученный при помощи мультипликативно сопряженного транспонирования , аматрично-векторные операции определены аналогично стандартным с заменойобычных покомпонентных операций сложения и умножения на тропические.Известно (см., например, [6]), что минимум в задаче совпадает с тропическим спектральным радиусом матрицы и достигается на любом собственном векторе, соответствующем этому радиусу. Полное решение задачи, котороеоказывается шире, чем множество собственных векторов , найдено в работах [31, 52, 59].В настоящей главе рассматривается дальнейшее обобщение задачи, в котором целевая функция имеет более сложную форму и введены дополнительныеограничения. Сначала представлен краткий обзор основных понятий и результатов тропической математики, необходимых для последующего анализа и решения задачи.
Затем формулируется новая задача оптимизации и находитсяее полное решение в явном виде в компактной векторной форме и проводит-16ся оценка вычислительной сложности. Приводятся числовые примеры решениязадач на множестве двумерных векторов, и представлена графическая иллюстрация решений на плоскости в декартовой системе координат.1.1Элементы тропической математикиВ этом разделе приводятся основные понятия и результаты тропическойматематики [32], на которые опираются решения, представленные в остальнойчасти работы.
Дополнительные детали и подробное изложение различных аспектов теории и методов тропической математики можно найти, например, вработах [22, 40, 50].1.1.1Идемпотентное полуполеРассмотрим набор ⟨X, ⊕, ⊙, 0, 1⟩, где X – непустое множество, на которомопределены операции сложения ⊕ и умножения ⊙. По сложению X являетсяидемпотентным коммутативным моноидом с нейтральным элементом 0 (нулем).По умножению множество X ∖ {0} образует коммутативную группу с нейтральным элементом 1 (единицей).Сложение идемпотентно: для любого ∈ X выполняется ⊕ = .
Идемпотентность сложения индуцирует частичный порядок на X так, что ≤ тогдаи только тогда, когда ⊕ = . Отсюда, в частности, следует, что неравенство ⊕ ≤ равносильно неравенствам ≤ и ≤ , а сумма ⊕ неменьше любого из слагаемых: ≤ ⊕ и ≤ ⊕ . Кроме того, операции ⊕и ⊙ монотонны в смысле указанного порядка по каждому аргументу, из чегоследует, что неравенство ≤ влечет за собой неравенства ⊕ ≤ ⊕ и ⊙ ≤ ⊙ для любых ∈ X.
Будем предполагать, что определенный такимобразом частичный порядок может быть продолжен до полного порядка на X.Умножение дистрибутивно относительно сложения и обратимо для всех элементов, кроме 0: для любого ∈ X ∖ {0} существует обратный −1 такой, что ⊙ −1 = 1. Операция обращения антитонна: это значит, что из неравенства ≤ вытекает неравенство −1 ≥ −1 для ненулевых и .17Естественным образом можно задать целые степени для любого ненулевого и натурального :0 = 1, = −1 ⊙ ,− = (−1 ) .Учитывая, что множество X не является группой по сложению, но его ненулевые элементы образуют группу по умножению, такая структура обычно называется идемпотентным полуполем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
