Диссертация (1150576), страница 7
Текст из файла (страница 7)
. ,.(2.5)44Эту задачу можно решать методами линейного программирования, при этомрешение будет алгоритмическим, и не гарантируется получение полного решения или решения в явном виде.Далее будет представлено полное решение задачи ликвидатора при помощиметодов тропической математики.2.2Решение задачи ликвидатораПрименим результат теоремы 4 для решения задачи ликвидатора, приведенной к форме (2.5).Так как в формулировке задачи присутствуют только операции взятия максимума, сложения и вычисления противоположного (обратного по сложению),то задачу можно представить в терминах полуполя Rmax ,+ . Для этого сначалавведем следующие обозначения для матриц: = ( ), = ( ),и для векторов = ( ), = ( ), = ( ), = ( ), = ( ).При этом матрицы ограничений вида «старт-финиш» и «старт-старт» обозначаются и соответственно, – искомый вектор сроков начала работ, авекторы и определяют конечные даты высадки и начальные даты эвакуациидля групп.
Пользуясь матричной алгеброй над Rmax,+ , запишем по формулам(2.3) и (2.1) скорректированное время начала и окончания работ: = (− ⊕ − )− , = ⊕ .Тогда по формуле (2.4) целевая функция приобретает форму− = (− ⊕ − )( ⊕ ) = − ⊕ − ⊕ − ⊕ − .(2.6)45Если перевести ограничения «старт-старт» в формуле (2.2) на язык идемпотентной математики, то задача планирования сроков выполнения проектапринимает форму задачи тропической оптимизации:min − ⊕ − ⊕ − ⊕ − ,(2.7) ≤ .Нетрудно видеть из постановки задачи, что векторы , и являются конечными, что обеспечивает их регулярность в тропическом смысле. Заменив− на − , − на и, применив теорему 4, получаем решение задачи надполуполем Rmax,+ в следующем виде.Лемма 3.
Пусть – матрица, > 0 – спектральный радиус , а –матрица такая, что Tr() ≤ 0. Для любого натурального и = 1, . . . ,введем обозначения0 =⨁︁ ,⨁︁ = 0 1 · · · .0≤0 +···+ ≤−=0Тогда минимум в задаче (2.6) равен− = ⊕⨁︁1/tr( ) ⊕=1−1⨁︁(− ,−1 )1/(+2) ,=0а все решения имеют вид = (−1 ⊕ )* ,2.3−1 ≤ ≤ (− (−1 ⊕ )* )− .Численный примерПрименим следствие 3 для решения задачи ликвидатора.Пусть заданы следующие матрицы ограничений:⎛⎞10 3 0⎜⎟⎟,=⎜072⎝⎠0 0 10⎛⎞0 0 0⎜⎟⎟,=⎜30−3⎝⎠7 2 046где — матрица ограничений вида «старт-финиш», — «старт-старт». Помимо этого заданы конечные даты высадки групп — вектор и начальные датыэвакуации — вектор :=(︁2 2 2)︁T,=(︁7 5 10)︁T.При этом столбцы (строки) идут в следующем порядке: исследователи, проектировщики и исполнители работ.Для того, чтобы применить следствие 2.6, необходимо проверить условиясуществования регулярных решений.
Вычислим матрицы⎛⎞⎛⎞⎛⎞0 0 00 0 00 0 0⎜⎟⎜⎟⎜⎟⎟ ⎜ 3 0 −3 ⎟ = ⎜ 4 0 −3 ⎟ ,2 = ⎜30−3⎝⎠⎝⎠ ⎝⎠7 2 07 2 07 2 0⎞⎛⎛⎞⎛⎞0 0 00 0 00 0 0⎟⎜⎟⎜⎟⎜⎟ ⎜ 3 0 −3 ⎟ = ⎜ 4 0 −3 ⎟ = 2 .3 = ⎜40−3⎠⎠⎝⎠ ⎝⎝7 2 07 2 07 2 0После чего получаем, чтоTr() = tr ⊕ tr 2 ⊕ tr 3 = 0 = 1,условие выполнено. Заметим, что * = 2 .Также подсчитаем⎛⎞⎛⎞⎛⎞10 3 010 3 020 13 5⎟⎜⎟ ⎜⎟⎜⎟ ⎜ 0 7 2 ⎟ = ⎜ 0 14 12 ⎟ , =⎜072⎝⎠⎝⎠ ⎝⎠0 0 100 0 200 0 102⎛⎞⎛⎞⎛⎞10 3 020 13 530 23 15⎜⎟⎜⎟ ⎜⎟⎟ ⎜ 0 14 12 ⎟ = ⎜ 0 21 22 ⎟ , =⎜072⎝⎠⎝⎠ ⎝⎠0 0 100 0 200 0 303По формуле (2.6) находим минимум целевой функции = 10.47 = − ⊕ tr(13 ) ⊕ tr1/2 (23 ) ⊕ tr1/3 (33 )⊕(︀)︀1/2 (︀ −)︀1/3 (︀ −)︀1/4⊕ − 02 ⊕ 12 ⊕ 22 .Вычислим матрицы , чтобы найти слагаемые по формулам (1.18).При этом значения матриц 01 = , 02 = 2 , 03 = 3 , 11 = ,22 = 2 и 33 = 3 были найдены ранее.
Получим матрицы12 = 01 ⊕ 11 ,13 = 02 ⊕ 12 ,23 = 12 ⊕ 22 .Вычислим матрицы, используемые в 12 :0111⎛⎞⎛⎞⎛⎞⎛⎞⎛⎞⎛⎞0 0 010 3 010 3 0⎟ ⎜⎟⎜⎟⎜⎟ ⎜ 3 0 −3 ⎟ = ⎜ 10 7 4 ⎟ ,= = ⎜072⎠ ⎝⎠⎝⎠⎝7 2 017 12 100 0 100 0 010 3 010 3 0⎜⎟⎜⎟ ⎜⎟⎟ ⎜ 0 7 2 ⎟ = ⎜ 13 7 7 ⎟ ,= = ⎜30−3⎝⎠⎝⎠ ⎝⎠7 2 00 0 1017 10 10откуда выводим 12 равным⎛12⎞⎛⎞⎛⎞10 3 010 3 010 3 0⎜⎟ ⎜⎟ ⎜⎟⎟ ⊕ ⎜ 13 7 7 ⎟ = ⎜ 13 7 7 ⎟ .=⎜1074⎝⎠ ⎝⎠ ⎝⎠17 12 1017 10 1017 12 10После этого вычислим матрицы, необходимые для 13 :⎛02⎞⎛⎞⎞⎛⎞10 3 00 0 010 3 0⎜⎟⎜⎟ ⎜⎟⎟ ⎜ 4 0 −3 ⎟ = ⎜ 11 7 4 ⎟ ,=⎜072⎝⎠⎝⎠ ⎝⎠0 0 107 2 017 12 10⎛12⎞⎛⎞⎛0 0 010 3 010 3 0⎜⎟⎜⎟ ⎜⎟⎟ ⎜ 13 7 7 ⎟ = ⎜ 14 9 7 ⎟ ,=⎜30−3⎝⎠⎝⎠ ⎝⎠17 12 107 2 017 12 1048⎛13⎞⎛⎞⎛⎞10 3 010 3 010 3 0⎜⎟ ⎜⎟ ⎜⎟⎟ ⊕ ⎜ 14 9 7 ⎟ = ⎜ 14 9 7 ⎟=⎜1174⎝⎠ ⎝⎠ ⎝⎠17 12 1017 12 1017 12 10Осталось найти матрицы для 23 :12⎛⎞⎛⎞⎛⎞⎛⎞⎛⎞⎛⎞10 3 010 3 020 13 10⎜⎟⎜⎟ ⎜⎟⎟ ⎜ 13 7 7 ⎟ = ⎜ 20 14 14 ⎟ ,=⎜072⎝⎠⎝⎠ ⎝⎠0 0 1017 12 1027 22 200 0 020 13⎜⎟⎜⎟⎜22 = ⎜⎝ 3 0 −3 ⎠ ⎝ 0 147 2 00 0⎛⎞ ⎛20 13 1020 13⎜⎟ ⎜⎟ ⎜23 = ⎜⎝ 20 14 14 ⎠ ⊕ ⎝ 23 1627 22 2027 20520⎟ ⎜⎜12 ⎟⎠ = ⎝ 232027⎞ ⎛520⎟ ⎜⎜17 ⎟⎠ = ⎝ 23135⎟16 17 ⎟⎠,20 20⎞13 10⎟16 17 ⎟⎠.27 22 2020Для каждого слагаемого , необходимого для вычисления , рассмотримего составные части.
Некоторые из них уже известны:02 = ⊕ ⊕ 2 = * ,22 = 22 = 2 ,33 = 33 = 3 .Получаем tr1/3 (33 ) = 30/3 = 10.Найдем оставшиеся слагаемые:12 = 12 ⊕ 1123 = 23 ⊕ 22⎛⎞⎛⎞⎛⎞⎛⎞⎛⎞⎛⎞10 3 010 3 010 3 0⎜⎟ ⎜⎟ ⎜⎟⎟ ⊕ ⎜ 0 7 2 ⎟ = ⎜ 13 7 7 ⎟ ,=⎜1377⎝⎠ ⎝⎠ ⎝⎠17 12 100 0 1017 12 1020 13 520 13 1020 13 10⎜⎟ ⎜⎟ ⎜⎟⎟ ⊕ ⎜ 0 14 12 ⎟ = ⎜ 23 16 17 ⎟ ,=⎜231617⎝⎠ ⎝⎠ ⎝⎠27 22 200 0 2027 22 20tr(23 ) = 20,tr1/2 (23 ) = 10.49⎛13⎞⎛10 3 0⎜⎟ ⎜⎟⊕⎜= 13 ⊕ 12 ⊕ 11 = ⎜1497⎝⎠ ⎝17 12 10⎛⎞ ⎛10 3 010⎜⎟ ⎜⎟ ⎜⊕⎜⎝ 0 7 2 ⎠ = ⎝ 140 0 10171030⎞⎟7⎟⎠⊕17 12 10⎞3 0⎟tr(13 ) = 10.9 4⎟⎠,13712 10Найдем вектор⎛− =(︁⎞)︁ ⎜ 10 3 0 ⎟ (︁)︁⎜⎟−2 −2 −2 ⎝ 0 7 2 ⎠ = 8 5 8 ,0 0 10а затем подсчитаем⎛− 02 =− 12 =− 12 =(︀(︁⎞⎛⎞)︁ ⎜ 0 0 0 ⎟ ⎜ 7 ⎟ (︁)︁ ⎜ 7 ⎟⎟⎜⎟⎜⎟8 5 8 ⎜⎝ 4 0 −3 ⎠ ⎝ 5 ⎠ = 8 5 8 ⎝ 11 ⎠ = 22,7 2 01014⎛⎞⎛⎞⎛⎞⎛⎞ ⎛⎞⎛⎞)︁ ⎜ 10 3 0 ⎟ ⎜ 7 ⎟ (︁)︁ ⎜ 17 ⎟⎟⎜⎟⎜⎟8 5 8 ⎜⎝ 13 7 7 ⎠ ⎝ 5 ⎠ = 8 5 8 ⎝ 20 ⎠ = 32,17 12 101024(︁(︁⎞⎛)︁ ⎜ 20 13 5 ⎟ ⎜ 7 ⎟ (︁)︁ ⎜ 27 ⎟⎟ ⎜⎟⎜⎟8 5 8 ⎜⎝ 0 14 12 ⎠ , ⎝ 5 ⎠ = 8 5 8 ⎝ 22 ⎠ = 34,0 0 201030− 02 )︀1/2= 11,(︀− 12 )︀1/3= 32/3,(︀− 22 )︀1/4= 19/2.50Вычислив значение⎛− =(︁⎞)︁ ⎜ 7 ⎟⎟8 5 8 ⎜⎝ 5 ⎠ = 8,10получаем минимум целевой функции = max(8, 10, 10, 10, 11, 32/3, 19/2) = 11.Найдем матрицы, необходимые для записи полного решения:⎞⎛⎞⎛−1 −8 010 3 0⎟⎟⎜⎜⎟ = ⎜ 0 −4 −9 ⎟ ,−1 = −11 ⎜072⎠⎠ ⎝⎝0 0 −10 0 10⎛−1 −8⎜−1 ⊕ = ⎜⎝0 −400⎛0 −8⎜( ⊕ ) = ⎜⎝3 07 2−12⎞⎛⎞⎛⎞0 −8 00 0 0⎟⎟ ⎜⎟ ⎜⎜ 3 0 −3 ⎟ = ⎜ 3 0 −3 ⎟ ,⊕−9 ⎟⎠⎠ ⎝⎠ ⎝7 2 07 2 0−1⎞⎛⎞ ⎛⎞00 −8 00 −8 −11⎟⎜⎟ ⎜⎟⎜ 3 0 −3 ⎟ = ⎜ 4 0 −3 ⎟ .−3 ⎟⎠⎝⎠ ⎝⎠07 2 07 200Заметим, что(−1 ⊕ )2 = (−1 ⊕ )* .Вычислим вектор⎛−−1* ( ⊕ ) =(︁⎞)︁ ⎜ 0 −8 −11 ⎟ (︁)︁⎜⎟8 5 8 ⎝ 4 0 −3 ⎠ = 15 10 8 .7 2051Левую и правую границы для вектора находим по формуле (2.6):⎛⎞−4⎜⎟⎟,−1 = ⎜−6⎝⎠−1⎛⎞⎛⎞−15−4⎜⎟⎜⎟⎟ = ⎜ 1 ⎟.(− (−1 ⊕ )* )− = 11 ⎜−10⎝⎠ ⎝⎠−83Получаем, что множество всех регулярных решений задачи (2.7) состоит извекторов вида⎛⎞0 −8 −11⎜⎟⎟ ,=⎜40−3⎝⎠7 20⎛⎞⎛⎞−4−4⎜⎟⎜⎟⎜ −6 ⎟ ≤ ≤ ⎜ 1 ⎟ .⎝⎠⎝⎠−13В терминах обычных операций решение принимает вид1 = max(1 , 2 − 8, 3 − 11),2 = max(1 + 4, 2 , 3 − 3),3 = max(1 + 7, 2 + 2, 3 ),при условии, что1 = −4,−6 ≤2 ≤ 1,−1 ≤3 ≤ 3.Так как 1 = −4, с учетом максимальных значений 2 и 3 , имеем 1 =max(1 ) = −4, 2 = max(0, 2 ).
Кроме того, так как 1 + 7 = 3, а значения2 + 2 и 3 в свою очередь также не превосходят 3, то 3 = 3. Общее решениеполучаем в виде1 = −4,0 ≤2 ≤ 1,3 = 3.Все вычисления в примерах настоящей главы были выполнены с использованием программ, реализованных на языке R, исходный код которых приводитсяв приложении А.52Глава 3Задача псевдочебышевской аппроксимации в тропическом векторном пространствеИмеется целый ряд практических задач (см., например, [8, 44, 60–62]), которые сводятся к наилучшему приближенному решению в смысле метрики Чебышева векторного уравнения = , где и обозначают заданные матрицу ивектор, – неизвестный вектор, а произведение матрицы на вектор понимаетсяв смысле тропической математики над полуполем Rmax ,+ .Рассмотрим, например, задачу оптимального планирования времени началаработ некоторого проекта с целью обеспечения заданных директивных сроковзавершения работ.
В этой задаче берется идемпотентное полуполе с операциейmax в роли сложения и арифметического сложения в роли умножения, координаты вектора имеют смысл времени начала выполнения для каждой работы,которое требуется определить, вектор задает директивные сроки завершенияработ, матрица – ограничения снизу на величину интервалов времени междуначалом и завершением работ.Проблема чебышевской аппроксимации сводится к задаче тропической математики по нахождению векторов , на которых достигается минимум в задачеmin ()− ⊕ − .В дальнейшем при рассмотрении этой задачи не будем ограничиваться только полуполем Rmax ,+ , для которого расстояние между векторами в точности53соответствует метрике Чебышева.
Поэтому далее будем называть подобную задачу задачей псевдочебышевской аппроксимации.Для решения задачи в статьях [101, 102] предлагается подход, при котором вводится дополнительный параметр для обозначения минимума целевойфункции, а затем задача сводится к решению параметризованных неравенств.С помощью такого подхода были получены решения в компактной векторнойформе для рассматриваемой задачи, а также некоторых ее вариантов, включаязадачи с ограничениями.Цель настоящей главы состоит в исследовании и решении задачи тропической оптимизации с целевой функцией более общего вида.
На основе применения методов решения с использованием разреженных матриц, разработанногов [103], находится полное решение задачи и его представление в компактнойвекторной форме [64, 66, 69].Глава построена следующим образом. Сначала находится минимальное значение целевой функции задачи, предлагается описание множества решений вформе системы неравенств и приводится одно из решений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
