Автореферат (1150699), страница 3
Текст из файла (страница 3)
Л. Овсиевича. Экономико-математические исследования: математические моде8ли и информационные технологии» (Санкт-Петербург, Россия – 2017); на семинарах кафедры статистического моделирования и кафедры системного программирования СанктПетербургского государственного университета и семинаре Санкт-Петербургского государственного университета и Санкт-Петербургского экономико-математического института РАН по тропической математике и смежным вопросам.Результаты диссертационной работы были получены при поддержке грантов №1302-00338 – «Модели и методы тропической математики в прикладных задачах экономикии управления» и №16-02-00059 – «Развитие моделей и методов тропической математики вприкладных задачах экономики и управления» Российского гуманитарного научного фонда, а также №18-010-00723А – «Разработка моделей и методов тропической математикидля прикладных задач экономики и управления» Российского фонда фундаментальныхисследований.Публикации.
Основные результаты диссертации представлены в восьми печатныхработах [1–3, 6–10]. Три из них [1–3] изданы в журналах из "Перечня рецензируемых научных изданий, в которых должны быть опубликованы основные научные результатыдиссертаций на соискание учёной степени кандидата наук, на соискание ученой степенидоктора наук”, а переводы двух из них опубликованы в журналах, индексируемых в международных библиографических базах Scopus и Web of Science [4, 5].В совместных работах с Кривулиным Н. К. [1, 2, 8–10] соискателю принадлежит формулировка и доказательства теорем о решении задачи размещения на плоскости точечногообъекта с прямоугольной метрикой и ограничениями на область размещения, разработкаалгоритмов и программных средств, а также проведение вычислительных экспериментов для верификации полученных результатов, соавтору принадлежат постановки задачи разработка общих методов решения.Объем и структура диссертации.
Диссертационная работа состоит из введения,трех глав, разбитых на параграфы, заключения и одного приложения. Полный объем диссертации составляет122 страницы машинописного текста. Список литературы содержит116 наименований.ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫВовведении обосновывается актуальность и научная новизна темы исследования,описана степень ее разработанности, а также формулируются цели и задачи диссертационной работы, показывается практическая значимость полученных результатов и представляются выносимые на защиту научные положения, приведены сведения об апробациипредлагаемых моделей и методов.Впервой главе систематизированы основные сведения об идемпотентной алгебре,на которые опираются дальнейшие исследования.
Сформулированы основные определения и введены используемые обозначения.Рассматривается числовое множествокоммутативные операции сложениязаданное наX⊕X,на котором определены ассоциативные ии умножения⊗.Через⟨X, ⊕, ⊗, 0, 1⟩обозначаетсяпри помощи этих операций коммутативное полукольцо с нулем0и еди-1. Сложение считается идемпотентным (т.е. для любого числа ∈ X выполняется ⊕ = ), а умножение – обратимым (т.е.
для каждого ̸= 0 существует обратный эле−1 такой, что ⊗ −1 = 1). Далее для упрощения математических выкладок знакмент умножения ⊗ в алгебраических выражениях, как обычно, опускается. В качестве примераницейалгебраической структуры рассматриваемого типа приведено вещественное идемпотентное полуполеRmax ,+ = ⟨R ∪ {−∞}, max, +, −∞, 0⟩.9Проведен обзор алгебры векторов и матриц над идемпотентными полуполями.
Сформулирована минимаксная задача в терминах идемпотентной алгебры в матричной форме,на основе которой в последующих материалах диссертации предложено решение оптимизационной задачи.Вторая глава посвящена изучению класса задач тропической оптимизации с одной,двумя и тремя переменными.Для некоторого набор чисел,,, ∈ X сформулирована задача тропической опти, ∈ X, на которых целевая функция принимаетмизации. Необходимо найти пару чиселнаименьшее значениеmin,∈X−1 −1 ⊕ −1 ⊕ −1 ⊕ .(1)Для решения задачи предложен матричный подход на основе экстремального свойства идемпотентного спектрального радиуса.
Задача записывается в расширенной векторной форме. При этом на введенный вектор-решение накладывается дополнительноеограничение, заключающееся в том, что первая и последняя координаты вектора считаются взаимно обратными. Из этого условия получается система неравенств, в которой покрайней мере одно неравенство является равенством.
Результаты анализа задачи (1) длявсех рассмотренных случаев записываются в виде Теоремы 1, которая уточняет известные решения. В результате решения задачи предложена явная формула для вычисленияминимума целевой функции и координат вектора оптимального решения.Теорема 1.когдаМинимум = ( ⊕ )1/2 в задаче(︂)︂(︂=(1)достигается тогда и только тогда,2−1 (1− − 1− − )1/2(1− −1 − )1/2)︂,0 ≤ ≤ 1.Затем предложено решение для ряда задач тропической оптимизации с ограничениями. Сначала изучено решение задачи с одной переменной и ограничениями в виде двойногонеравенства. Заданы числаненулевые решения∈X,,,,, ∈ X, а также вещественное число . Требуется найтизадачиmin −1 ⊕ −(−1) ⊕ −(+1) ⊕ +1 ,∈X(2) ≤ ≤ .Для решения применяется метод, заключающийся в сведении задачи оптимизациик системе параметризованных неравенств.
Сначала вводится параметр для обозначенияминимума целевой функции, а затем задача сводится к решению параметризованной системы неравенств. Условие существования решений системы используются для определения величины параметра, а все решения системы при найденном значении параметраберутся в качестве решений исходной задачи оптимизации. Вариант решения предложенв Теореме 2.Пусть ,,,,, ∈ X и – вещественное число. Тогда справедливы следующие утверждения:1) если < −1 или > 1, то минимум в задаче (2) равенТеорема 2. = 1/2 1/2 ⊕ (+1)/2 (−1)/2 ⊕ (+1)/2 (−1)/2 ⊕ 1/2 1/2 ⊕⊕ ( −(−1) ⊕ −(−1) )−1 ⊕ ( −1 ⊕ −1 )−1 ⊕⊕ ( +1 ⊕ +1 )−1 ⊕ ( −(+1) ⊕ −(+1) )−110и достигается тогда и только тогда, когда = (((−1 )−1/(−1) ⊕ (−1 )−1/(−1) )−1 ⊕⊕ ((−1 )−1/(+1) ⊕ (−1 )−1/(+1) )−1 ⊕ )1− (((−1 )−1/(−1) ⊕ (−1 )1/(−1) )−1 ⊕⊕ ((−1 )1/(+1) ⊕ (−1 )−1/(+1) )−1 ⊕ −1 )− ,2)если −1 ≤ ≤ 1, то минимум равен = 1/2 1/2 ⊕ (+1)/2 −(−1)/2 ⊕ (+1)/2 −(−1)/2 ⊕ 1/2 1/2 ⊕⊕ −1 ⊕ −(−1) ⊕ −(+1) ⊕ +1и достигается тогда и только тогда, когда = ((−1 )1/(−1) ⊕ (−1 )1/(+1) ⊕ )1− ((−1 )1/(−1) ⊕ (−1 )1/(+1) ⊕ −1 )− ,где – любое число, удовлетворяющее условию 0 ≤ ≤ 1.Также в диссертационной работе рассмотрено решение оптимизационной задачи сдвумя переменными и ограничениями в виде двойных неравенств.Для заданных чиселзадачи,,,,,,, ∈ Xтребуется найти ненулевые решения, ∈ Xmin −1 −1 ⊕ −1 ⊕ −1 ⊕ ,,∈X(3) ≤ ≤ , ≤ ≤ .Результат решения задачи может быть представлен в виде теоремы 3.Теорема 3.Введем обозначения = 1/2 1/2 ⊕ −1 ⊕ ,Тогда минимум в задаче(3) = 1/2 1/2 ⊕ −1 ⊕ , = 1/2 1/2 ⊕ 1/2 1/2 .равен = 1/2 1/2 ⊕ −1 ⊕ ⊕ и достигается тогда и только тогда, когда = (−1 ⊕ )1− (−1 ⊕ −1 )− , = (−1 −1 ⊕ −1 ⊕ )1− (−1 −1 ⊕ −1 ⊕ −1 )− ,где – вещественное число, удовлетворяющее условию 0 ≤ ≤ 1.В заключении третьей главы рассмотрена оптимизационная задача с тремя переменными без ограничений на допустимую область размещения.
Пусть заданы числа,,,,,,,ℎ ∈ X.Требуется найти ненулевые решения, , ∈ Xзадачи поиска миниму-ма функции−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ⊕⊕ −1 −1 ⊕ −1 ⊕ −1 ⊕ ℎ.(4)Результат, сформулированный в диссертационной работе, предложен в Теореме 4.11Теорема 4.Введем обозначения1 = 1/2 1/2 ⊕ 1/2 1/2 ,1 = 1/2 1/2 ⊕ 1/2 1/2 ,1 = 1/2 ℎ1/2 ⊕ 1/2 1/2 ,1 = 1/2 1/2 ,ℎ1 = 1/2 ℎ1/2 ,1 = 1/2 1/2 ,1 = 1/2 1/2 ,1 = 1/2 ℎ1/2 ⊕ 1/2 1/2 ⊕ 1/2 1/2 ⊕ 1/2 1/2 ,1/2 1/2⊕ 1 1 ,2 = 1 ℎ11/2 1/2⊕ 1 ,1/2 1/2⊕ 1 12/3 1/3⊕ 2 22 = 1 12 = 1 ℎ11 = 1/2 ℎ1/2 ⊕ 1/2 1/2 ,1/2 1/2Тогда минимум в задаче1/2 1/2 2 = 1 1(4)1/2 1/2⊕ 1 1 ,1/2 1/2⊕ 1 ℎ12/3 1/3⊕ 2 21/2 1/22 = 1 11/2 1/2⊕ 1 .1/2 1/2⊕ 2⊕ 1 ,равен1/2 1/2 = 2 2⊕ 2 2и справедливы следующие утверждения:1/2 1/2−11) если = 1 1 , то = 2 2 ,{︃3/4 −1/4 −1/22 , если 2−3/4 1/4 1/21 1 2 ,если 2−1 −1 −1−1 −11 1= = (⊕1/2 1/2= 1 1 ,1/2 1/2= 1 1 , ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;2)2/3 −2/32/3 1/3если = 2 2 , то = 2 2,{︃2/3 −1/3 −1/32 , если−2/3 1/3 1/31 1 2 ,если−1 −1 −1−1 −11 1= = (⊕1/2 1/22 = 1 1 ,1/2 1/22 = 1 1 , ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;3)−2/3 2/32 ,2/3 1/3если = 2 2 , то = 2{︃=2/3 −1/3 −1/32 , если 2−2/3 1/3 1/3 1 1 2 ,если 2−1 −1 −1−1 −11 ℎ1 = (⊕1/2 1/2= 1 ℎ1 ,1/2 1/2= 1 1 , ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;4)1/2 −1/21/2 1/2если = 2 2 , то = 2 2=,⎧ 1/2 −1/2 1 1,⎪⎪⎪⎨ 1/2 ℎ−1/2 ,1/2 1/2если 2 = 1 1 ,1/2 1/21−1/2 −1/2−11− ⊗⎪(1 1 1 ⊕ −1⎪1 1 ⊕ 1 1 )⎪⎩−1/2 −1/2−1− ,⊗(1 1 1 ⊕ −11 1 ⊕ 1 ℎ1 )−1 −1 −1−1 −1−1−1 = (1⊕⊕если 2 = 1 ℎ1 ,если 2 = 1 , 2 = 1 ,⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;125)−1 1− 2 −2− ,если = 2 , то = (22 −2(2 2 ⊕ 2 −12 ⊕ 2 2 )2 )=⎧ 1/2 −1/2⎪⎨1 1 ,1/2 1/2если 2 = 1 1 ,−1/2 1/21 ,если 21/2 −1/21 ℎ1 −1 , если 2−1 −1 −1−1 −11⎪⎩ = (⊕1/2 1/2= 1 1 ,1/2 1/2= 1 ℎ1 , ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;6)если = 1 , то = (22 1−2 ⊕ 2 1−1 )1− (22 1−2 ⊕ 2 1−1 )− , = (1 1−1 ⊕ 1−1 1 −1 ⊕ 1−1 1 )1− (1−1 1 ⊕ 1−1 1 −1 ⊕ 1−1 ℎ1 )− ,⎧1/2 ℎ−1/2 −1 −1 , если 1 = 1/2 ℎ1/2 ,⎪⎪⎪⎨1/2 −1/2 −1 ,если 1 = 1/2 1/2 ,=⎪−1/2 1/2 −1 ,если 1 = 1/2 1/2 ,⎪⎪⎩ −1/2 1/21/2 1/2,если 1 = ,где , – вещественные числа, удовлетворяющие условиям 0 ≤ ≤ 1, 0 ≤ ≤ 1.Втретьей главе предложены приложения теорем, сформулированных и доказан-ных во второй главе диссертационной работы, к исследованию реальных ситуаций оптимизации структурного построения информационных систем.
Рассмотрены задачи размещения на плоскости с прямоугольной метрикой точечного объекта без ограничений наобласть размещения, с ограничениями в виде прямой линии, отрезка прямой, полосы ипрямоугольника. Завершается глава постановкой и решением задачи размещения в трехмерном пространстве.Рассматривается задача, появляющаяся при размещении аппаратного комплекса обработки интернет-трафика (центрального сервера управления сетью локальных коммуникаций), в условиях городской инфраструктуры (рис. 1).Пусть необходимо собирать, обрабатывать и хранить информацию, поступающую клиентов(1 ,2 ) ∈ R2 ,отлокальной сети. Координаты этих клиентов задаются векторамигде = 1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
