Автореферат (1150574), страница 3
Текст из файла (страница 3)
. . , 1) .Далее в главе рассматривается задача оптимизации с нелинейной (псевдоквадратичной) целевой функцией и ограничениями в форме линейногонеравенства.Пусть заданы матрицы , ∈ X× , векторы , ∈ X и скаляр ∈ X.Требуется найти все регулярные векторы ∈ X , которые решают задачуmin − ⊕ − ⊕ − ⊕ , ≤ .Полное решение задачи получено в следующей форме.9(1)Пусть – матрица со спектральным радиусом > 0, а – матрица, для которой Tr() ≤ 1. Для любого натурального и =1, . . .
, введем обозначенияТеорема 1.0 =⨁︁ ,⨁︁ = 0 1 · · · .0≤0 +···+ ≤−=0Тогда минимум в задаче (1) равен=⊕⨁︁1/tr( ) ⊕−1⨁︁( − ,−1 )1/(+2) ,=0=1а все регулярные решения имеют вид = (−1 ⊕ )* ,−1 ≤ ≤ ( − (−1 ⊕ )* )− .Для доказательства теоремы применяется подход, при котором вводится дополнительная переменная, описывающая минимальное значение целевойфункции. Затем задача сводится к решению неравенства, в котором эта переменная выступает в роли параметра. Необходимые и достаточные условиясуществования решений неравенства используются для вычисления параметра, а общее решение неравенства берется в качестве решения исходной задачиоптимизации.Предлагается метод, позволяющий существенно уменьшить количествонеобходимых арифметических операций и производится оценка вычислительной сложности решения задачи (1), которая оказывается полиномиальной.Полученное решение является полным и представлено в простой аналитической форме в матрично-векторном виде.
Это дает возможность проводить дальнейшее аналитическое исследование задачи, а также обеспечиваетвозможность эффективной программной реализации и распараллеливаниявычислений.Результаты главы опубликованы в работах [1, 5].Вторая глава посвящена применению результатов первой главы длярешения задачи разработки плана мероприятий по ликвидации аварии на радиационно опасном объекте с радиоактивным загрязнением местности, которая представляет собой задачу сетевого планирования. Для решения такихзадач применяются детерминированные методы, такие как метод критического пути (CPM) и диаграммы Ганта, либо вероятностные, например, методоценки и пересмотра планов (PERT) и метод графической оценки и анализа(GERT).
Задачи сетевого планирования можно сформулировать в виде задачоптимизации. Для их решения используются различные методы линейного инелинейного программирования. При этом зачастую подобное решение является алгоритмическим и не предоставляет полного решения задачи.10Одним из способов решения некоторых задач планирования производства и сетевого планирования является применение методов тропической математики. По сравнению с методами математического программирования, которые зачастую предоставляют лишь алгоритмическое решение, для некоторых классов задач сетевого планирования применение методов тропическойоптимизации дает возможность получить в явном виде полное решение.Предположим, что на некоторой территории произошла авария с радиоактивным загрязнением местности.
Необходимо провести обследование местности, выработать план первоочередных работ и осуществить его.Для этого в район загрязнения будут отправлены несколько групп исполнителей работ. Перед началом работы каждой группы осуществляется еедоставка к месту аварии, а после завершения работы – ее эвакуация с местааварии, при этом имеются ограничения на наиболее позднюю дату высадки, а также на наиболее раннюю возможную дату эвакуации групп послезавершения задания. Для каждой группы известна продолжительность работ, которые она должна выполнить, а также зависимости между срокамивыполнения этих работ и сроками выполнения работ других групп.Необходимо запланировать операцию таким образом, чтобы минимизировать максимальное время пребывания (промежуток между высадкой и эвакуацией) всех групп в опасной зоне с учетом всех ограничений.Пусть имеется проект, состоящий из операций.
Для каждой операциис номером = 1, . . . , обозначим время начала через , а время окончаниячерез . Каждая операция завершается сразу, как только заданные условия для ее выполнения оказываются выполненными. Введем следующие обозначения: — минимально возможная задержка между началом операции = 1, .
. . , и окончанием операции , – наименьший допустимый интервал времени между началом операции = 1, . . . , и началом операции , – конечная дата высадки и – начальная дата эвакуации -й группы.Запишем задачу планирования в виде задачи нахождения времени начала и времени завершения операций для каждой из групп, которыеминимизируют максимальное время нахождения групп в районе заражения,представленное как разность между датами эвакуации и переброски :minmax ( − ),1≤≤ = − max(− , − ),(︁)︁ = max max ( + ), ,(2)1≤≤ ≥ max ( + ),1≤≤ = 1, .
. . , .Применим результат теоремы 1 для решения задачи ликвидатора, приведенной к форме (2), представив задачу в терминах полуполя Rmax,+ .Задача планирования сроков выполнения проекта принимает форму за11дачи тропической оптимизации:min − ⊕ − ⊕ − ⊕ − , ≤ .Заменив − на − , − на и применив теорему 1, получаем решениезадачи над полуполем Rmax,+ .В третьей главе рассматривается задача, связанная с нахождениемнаилучшего приближенного решения в смысле метрики Чебышева векторного уравнения = , где и обозначают заданные матрицу и вектор, –неизвестный вектор, а произведение матрицы на вектор понимается в смыслетропического полуполя Rmax,+ .Проблема чебышевской аппроксимации сводится к задаче тропическойоптимизации по нахождению векторов , на которых достигается минимумmin ()− ⊕ − .(3)В дальнейшем при рассмотрении этой задачи не будем ограничиватьсятолько полуполем Rmax,+ , поэтому далее будем называть подобную задачузадачей псевдочебышевской аппроксимации.Рассмотрим задачу (3) в следующем более общем виде.
Пусть заданыматрица ∈ X× и векторы , ∈ X . Требуется найти все регулярныевекторы ∈ X , на которых достигается минимумmin ()− ⊕ − .(4)Сначала находится минимальное значение целевой функции задачи, предлагается описание множества решений в форме системы неравенств и приводится одно из решений.Пусть – регулярная по строкам матрица, а и – регулярные векторы. Тогда минимум в задаче (4) равен ∆ = (()− )1/2 , а всерегулярные решения определяются системой неравенствЛемма 1. ≥ ∆−1 , ≤ ∆.В частности, минимум достигается при = ∆ .Далее вводится понятие разреженной матрицы задачи = ( ), которая получается из исходной матрицы путём обнуления всех элементов, которые меньше порогового значения по следующему правилу:{︃ , если ≥ ∆−2 −1 ;̂︀ =0,в противном случае.12Показывается, что замена матрицы задачи на разреженную не изменяетминимальное значение целевой функции и множество решений.
С помощьюразрежения матрицы задачи находится расширенное множество решений, азатем полное решение расширенной задачи аппроксимации в виде семействарешений. Это семейство задается множеством матриц, полученных из разреженной матрицы задачи путем дальнейшего обнуления ее элементов. Общеерешение представлено в следующем виде.Пусть – регулярная по строкам разреженная матрица задачи (4), где и – регулярные векторы, и ∆ = (()− )1/2 .
Обозначимчерез множество матриц, полученных из путем сохранения по одномуненулевому элементу в каждой строке и обнулением остальных, а через – матрицу, столбцами которой являются векторы 1 = ∆−1 −1 для всехматриц 1 ∈ .Тогда минимум в задаче (4) равен ∆, а все регулярные решения имеют вид = ⊕ , ≤ ∆,1 = 1.Теорема 2.В качестве следствия этого результата получаем решение задачи (3),которая является частным случаем задачи (4). Таким образом, для задачипсевдочебышевской аппроксимации было представлено множество всех решений, которое в дальнейшем может быть сокращено с учетом дополнительныхтребований или ограничений.Перебор всевозможных матриц 1 ∈ для построения подмножеств семейства решений задачи в соответствии с результатом теоремы 2 может представлять определенные трудности.
Поэтому предлагаются процедуры, позволяющие сократить число подмножеств, которые необходимо исследовать припостроении полного решения.Кроме того, некоторые подмножества семейства решений могут содержаться в других подмножествах и поэтому могут не учитываться. В работепостроен формальный критерий для определения подмножеств, отбрасывание которых не меняет общего решения задачи.Приводится алгоритм нахождения всех подмножеств решения для задачи псевдочебышевской аппроксимации, необходимых для получения полногомножества решений задачи (4), в котором используются предложенные процедуры.Точная оценка вычислительной сложности алгоритма затруднена из-затого, что в зависимости от структуры разреженной матрицы задачи и выбранного порядка обхода ее строк, число матриц, которые необходимо рассмотреть, может сильно отличаться.
Поэтому была проведена статистическаяоценка количества рассматриваемых матриц 1 ∈ , для чего для каждойразмерности от 3 до 10 были сгенерировано по 100000 случайных матриц состандартным нормальным распределением элементов. Для каждой такой матрицы алгоритм находил полное решение, а число рассмотренных в процессе13Размерность Среднее Дисперсия Медиана31.20.4141.60.9152.31.8263.73.5276.27.44810.915.86920.035.191037.473.214Таб. 1.
Число рассмотренных вариантов в зависимости от размерности задачи.матриц 1 ∈ фиксировалось. После этого было вычислено среднее, дисперсия и медиана полученного распределения числа рассмотренных матриц,результаты приведены в таблице 1.Случай, когда в большинстве строк разреженной матрицы значительнаячасть элементов ненулевые и при этом все строки равнозначны в том смысле,что в каждой из них присутствуют как элементы, позволяющие значительносократить перебор вариантов в своем столбце, так и те, которые этому неспособствуют, является наихудшим.
Тогда количество рассматриваемых матриц может быть экспоненциальным по размерности задачи, но в тестовыхзадачах, как видно из таблицы, подобные случаи обычно не встречаются.Завершается глава примером численного решения задачи на множестветрехмерных векторов. Результаты этой главы опубликованы в работах [2, 6].В четвёртой главе рассматривается неравенство ≥ ,(5)решение которого представляет большой интерес для многих приложений.Рассмотрим произвольный ненулевой вектор ∈ X . Будем называтьтропическим выпуклым конусом множество всех векторов ∈ X , таких,что ≥ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
