Диссертация (1150701), страница 12
Текст из файла (страница 12)
Применение теоремы 5 дает следующий результат.Теорема 9. Введем обозначения = 1/2 1/2 ⊕ −1 ⊕ ,==⨁︁ = 1/2 1/2 ⊕ −1 ⊕ , 1 2 ,=1⨁︁−1 1 2,===1⨁︁=1⨁︁−1 12 ,−1 −1 12 .=1Тогда минимум в задаче (3.1) равен = 1/2 1/2 ⊕ −1 ⊕ ⊕ 1/2 1/2 ⊕ 1/2 1/2 ,и справедливы следующие утверждения:1) если = 1/2 1/2 при = 1/2 1/2 и = −1 или = −1 , то1 = (1/4 1/4 ⊕ 1/2 −1/2 )(1/2 −1/2 ⊕ 1/2 )−1 ,2 = ;2) если = 1/2 1/2 при = 1/2 1/2 и = или = , то1 = (1/4 1/4 ⊕ 1/2 1/2 )(1/2 1/2 ⊕ 1/2 )−1 ,2 = ;903) если = −1 , то1 = ,2 = (−1/2 1/2 ⊕ −1 )−1 ⊕ ;1 = ,2 = (−1/2 1/2 ⊕ −1 )−1 ⊕ ;4) если = , то5) если = 1/2 1/2 , то1 = (−1/2 −1/2 ⊕ )1− (−1/2 −1/2 ⊕ −1 )− ,2 = 1/2 −1/2 −11 ;6) если = 1/2 1/2 , то1 = (−1/2 −1/2 ⊕ )1− (−1/2 −1/2 ⊕ −1 )− ,2 = 1/2 −1/2 1 ,где – вещественное число, удовлетворяющее условию 0 ≤ ≤ 1.При использовании обычных обозначений найденное решение описываетсятак:Следствие 15.
Введем обозначения = max ( + 1 + 2 ), = max ( − 1 + 2 ), = max ( + 1 − 2 ), = max ( − 1 − 2 ),1≤≤1≤≤1≤≤1≤≤а также = max(( + )/2, − , + ), = max(( + )/2, − , + ).Минимум в задаче (3.1) равен = max(( + )/2, − , + , ( + )/2, ( + )/2),и справедливы следующие утверждения:911) если = ( + )/2 при = ( + )/2 и = − или = − , то1 = max(( + )/4,( − )/2) − max(( − )/2,/2),2 = ;2) если = ( + )/2 при = ( + )/2 и = + или = + , то1 = max(( + )/4,( + )/2) − max(( + )/2,/2),2 = ;3) если = − , то1 = ,2 = max(− max((− + )/2, −), );4) если = + , то1 = ,2 = max(− max((− + )/2, −), );5) если = ( + )/2, то1 = (1 − ) max((− − )/2 + , ) − max((− − )/2 + , −),2 = ( − )/2 − 1 ;6) если = ( + )/2, то1 = (1 − ) max((− − )/2 + , ) − max((− − )/2 + , −),2 = ( − )/2 + 1 ,где – вещественное число, удовлетворяющее условию 0 ≤ ≤ 1.Замечание.
Заметим, что в случае, если требуется решить задачу размещения в полосе, а не в прямоугольнике, то достаточно убрать из условия (3.8)одно из ограничений и воспользоваться одним из двух следствий 9 или 10.Приведем примеры применения полученных результатов. Пусть имеется = 11 исходных точек на плоскости, имеющих координаты1 = (3, 7) ,2 = (4, 4) ,3 = (5, 3) ,4 = (5, 9) ,925 = (6, 6) ,6 = (7, 3) ,9 = (9, 2) ,7 = (7, 8) ,10 = (10, 7) ,8 = (8, 4) ,11 = (11, 4) .Для простоты будем считать, что = 0 для всех .
Зададим четыре различных области размещения1 = {(1 ,2 ) | 4 ≤ 1 ≤ 10, 3 ≤ 2 ≤ 9},2 = {(1 ,2 ) | 2 ≤ 1 ≤ 12, 1 ≤ 2 ≤ 5,5},3 = {(1 ,2 ) | 2 ≤ 1 ≤ 5, 1 ≤ 2 ≤ 11},4 = {(1 ,2 ) | 2 ≤ 1 ≤ 12, 8 ≤ 2 ≤ 11}.В результате применения расчетных формул из следствия 15 для задач собластями размещения 1 , 2 , 3 , 4 получены решения, в которых оптимальноеразмещение описывается следующими парами координат:1 = + 6,5,1 = 0,5 + 6,5,1 = 5,1 = 7,5,2 = + 5,2 = 0,5 + 7,2 = 5,2 = 8.Для записи первых двух решений используется числовой параметр 0 ≤ ≤ 1.На рисунках 3.7-3.10 представлены результаты применения теорем изпредыдущего раздела. Кружками выделено исходное множество объектов,пунктирным прямоугольником – область размещения, отрезком жирной линииили жирной точкой – искомое множество размещения.2266bbbbbbbb0bbbbbbb-1Рисунок 3.7 - Размещение на 10bbq qqbbbbb-1Рисунок 3.8 - Размещение на 2932266bbbtbbbbbbbbb-10Рисунок 3.9 - Размещение на 33.7bbbbbtbbbbb0-1Рисунок 3.10 - Размещение на 4Решение задачи размещения в трехмерном пространствеРассмотрим минимаксную задачу размещения точечного объекта в трехмерном пространстве с прямоугольной метрикой, которая заключается в поиске наоснове уже имеющегося набора объектов новой точки из R3 , расстояние от которой до самого дальнего объекта из набора с учетом некоторого дополнительногослагаемого было бы минимальным.Расстояние в прямоугольной метрике между двумя точками = (1 ,2 ,3 )и = (1 ,2 ,3 ) в пространстве R3 может быть вычисленно по формуле(,) = |1 − 1 | + |2 − 2 | + |3 − 3 |.(3.9)Пусть задан набор точек = (1 ,2 ,3 ) ∈ R3 и чисел ∈ R, для всех = 1, .
. . ,. Числа могут отражать дополнительные затраты, связанные сперемещением между объектами. Введем функцию (), которая определяетмаксимальное расстояние от точки = (1 ,2 ,3 ) до набора точек следующим образом:() = max (( ,) + ) =1≤≤= max (|1 − 1 | + |2 − 2 | + |3 − 3 | + ) = (1 ,2 ,3 ). (3.10)1≤≤94Рассматриваемая минимаксная задача размещения точечного объекта формулируется так:(3.11)min ().∈R3Рассмотрим задачу размещения (3.11) и представим ее в терминах тропической математики. Расстояние между двумя векторами в прямоугольной метрике (3.9) с использованием операций идемпотентного полуполя Rmax ,+ записывается так:−1−1−1−1−1(,) = (−11 1 ⊕ 1 1 )(2 2 ⊕ 2 2 )(3 3 ⊕ 3 3 ).Для заданного набора точек = (1 ,2 ,3 ) ∈ R3 и чисел ∈ R, где = 1, . . .
,, целевая функция (3.10) принимает вид(1 ,2 ,3 ) =⨁︁−1−1−1−1−1 (−11 1 ⊕ 1 1 )(2 2 ⊕ 2 2 )(3 3 ⊕ 3 3 ).=1Чтобы упростить выражение, введем дополнительные обозначения====⨁︁=1⨁︁=1⨁︁=1⨁︁=1 1 2 3 ,−1 1 23 ,−1 12 3 ,−1 −1 12 3 ,===ℎ=⨁︁=1⨁︁=1⨁︁=1⨁︁−1 1 2 3,−1 −1 1 23 ,−1−1 12 3,−1 −1 −1 12 3 .=1Раскрыв скобки и перегруппировав слагаемые, запишем целевую функцию:−1 −1−1 −1−1−1−1(1 ,2 ,3 ) = −11 2 3 ⊕ 1 2 3 ⊕ 1 2 3 ⊕ 1 2 3 ⊕−1−1−1⊕ 1 −12 3 ⊕ 1 2 3 ⊕ 1 2 3 ⊕ ℎ1 2 3 .Задача (3.11) принимает форму задачи (2.31), где = 1 , = 2 и = 2 .Применение теоремы 7 дает следующий результат.95Теорема 10.
Введем обозначения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/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 ,1/2 1/21/2 1/2⊕ 1 ,2 = 1 12 = 1 11/2 1/21/2 1/21 = 1/2 1/2 ,1/2 1/21/2 1/22 = 1 ℎ1 ⊕ 1 1 ,1/2 1/22 = 1 ℎ1 ⊕ 1 ,1/2 1/22 = 1 1 ⊕ 1 1 ⊕ 1 ℎ1 ⊕ 1 .Тогда минимум в задаче (3.11) равен1/2 1/22/3 1/32/3 1/31/2 1/2 = 2 2 ⊕ 2 2 ⊕ 2 2 ⊕ 2 2 ⊕ 2 ,и справедливы следующие утверждения:1/2 1/21) если = 1 1 , то1 = 2 2−1 ,⎧⎨3/4 −1/4 −1/2 , если 2 = 1/2 1/2 ,112112 =1/2 1/2⎩−3/4 1/4 1/2 ,если 2 = 1 1 ,112−1−1 −1−1−1−11−3 = (−1 −1⊗1 2 ⊕ 1 2 ⊕ 1 2 ⊕ 1 2 )−1−1−1−1−1−1−⊗ (−1 −11 2 ⊕ 1 2 ⊕ 1 2 ⊕ ℎ1 2 ) ;2/3 1/32) если = 2 2 , то2/3 −2/31 = 2 2 ,⎧⎨2/3 −1/3 −1/3 , если 2 = 1/2 1/2 ,112112 =1/2 1/2⎩−2/3 1/3 1/3 ,если 2 = 1 1 ,112−1−1 −1−1−1−11−3 = (−1 −1⊗1 2 ⊕ 1 2 ⊕ 1 2 ⊕ 1 2 )−1−1−1−1−1−1−⊗ (−1 −11 2 ⊕ 1 2 ⊕ 1 2 ⊕ ℎ1 2 )962/3 1/33) если = 2 2 , то−2/3 2/31 = 2 2 ,⎧⎨2/3 ℎ−1/3 −1/3 , если 2 = 1/2 ℎ1/2 ,112112 =⎩−2/3 1/3 1/3 , если = 1/2 1/2 ,211211−1−1 −1−1−1−11−3 = (−1 −1⊗1 2 ⊕ 1 2 ⊕ 1 2 ⊕ 1 2 )−1−1−1−1−1−1−⊗ (−1 −11 2 ⊕ 1 2 ⊕ 1 2 ⊕ ℎ1 2 ) ;1/2 1/24) если = 2 2 , то1/2 −1/21 = 2 2 ,⎧1/2 −1/21/2 1/2⎪⎪ 1 1 ,если 2 = 1 1 ,⎪⎪⎪⎪1/2 1/2⎨ 1/2 ℎ−1/2 ,если 2 = 1 ℎ1 ,112 =−1/2 −1/2⎪1−⎪(1 1 1 ⊕ 1−1 1 ⊕ −1⊗⎪1 1 )⎪⎪⎪⎩⊗(−1/2 −1/2 ⊕ −1 ⊕ −1 ℎ )− , если = , = ,11121 211111−1−1 −1−1−1−11−3 = (−1 −1⊗1 2 ⊕ 1 2 ⊕ 1 2 ⊕ 1 2 )−1−1−1−1−1−1−⊗ (−1 −11 2 ⊕ 1 2 ⊕ 1 2 ⊕ ℎ1 2 ) ;5) если = 2 , то−1 1− 2 −2−1 = (22 −2(2 2 ⊕ 2 −12 ⊕ 2 2 )2 ) ,⎧1/2 −1/21/2 1/2⎪⎪1 1 ,если 2 = 1 1 ,⎪⎨2 = 1−1/2 11/2 1 , если 2 = 11/2 11/2 ,⎪⎪⎪⎩1/2 ℎ−1/2 −1 , если = 1/2 ℎ1/2 ,111211−1−1 −1−1−1−11−3 = (−1 −1⊗1 2 ⊕ 1 2 ⊕ 1 2 ⊕ 1 2 )−1−1−1−1−1−1−⊗ (−1 −11 2 ⊕ 1 2 ⊕ 1 2 ⊕ ℎ1 2 ) ;976) если = 2 = 1 , то1 = (22 1−2 ⊕ 2 1−1 )1− (22 1−2 ⊕ 2 1−1 )− ,−11− −1−1−2 = (1 1−1 ⊕ 1−1 1 −1(1 1 ⊕ 1−1 1 −11 ⊕ 1 1 1 )1 ⊕ 1 ℎ1 1 ) ,⎧−11/2 1/2⎪⎪1/2 ℎ−1/2 −1ℎ ,1 2 , если 1 = ⎪⎪⎪⎪⎨1/2 −1/2 −1 2 ,если 1 = 1/2 1/2 ,13 =⎪⎪−1/2 1/2 1 −1если 1 = 1/2 1/2 ,⎪2 ,⎪⎪⎪⎩−1/2 1/2 ,если = 1/2 1/2 ,1 21где , – вещественные числа, удовлетворяющие условиям 0 ≤ ≤ 1, 0 ≤ ≤ 1.Сформулируем результат в в терминах обычной математики в виде следствия.Следствие 16.
Введем обозначения1 = max( + , + )/2,1 = max( + , + )/2,1 = max( + ℎ, + )/2,1 = max( + ℎ, + )/2,1 = ( + )/2,1 = ( + )/2,ℎ1 = ( + ℎ)/2,1 = max( + ℎ, + , + , + )/2,2 = max(1 + 1 , 1 + 1 )/2,2 = max((1 + 1 )/2, 1 ),1 = ( + )/2,2 = max(1 + ℎ1 , 1 + 1 )/2,2 = max((1 + ℎ1 )/2, 1 ),2 = max(1 + 1 , 1 + 1 , 1 + ℎ1 , 21 )/2.Тогда минимум в задаче (3.11) равен = max((2 + 2 )/2, (22 + 2 )/3, (22 + 2 )/3, (2 + 2 )/2, 2 ),и справедливы следующие утверждения:981) если = (2 + 2 )/2, то1 = 2 − 2 ,⎧⎨(31 − 1 )/4 − 2 /2,если 2 = (1 + 1 )/2,2 =⎩(−3 + )/4 + /2, если = ( + )/2,1122113 = (1 − ) max(− + − 1 − 2 , − + − 1 + 2 ,− + + 1 − 2 , − + + 1 + 2 ) − max(− + − 1 − 2 ,− + − 1 + 2 , − + + 1 − 2 , − + ℎ + 1 + 2 );2) если = (22 + 2 )/3, то1 = (22 − 22 )/3,⎧⎨(21 − 1 − 2 )/3,если 2 = (1 + 1 )/2,2 =⎩(−2 + + )/3, если = ( + )/2,1122113 = (1 − ) max(− + − 1 − 2 , − + − 1 + 2 ,− + + 1 − 2 , − + + 1 + 2 ) − max(− + − 1 − 2 ,− + − 1 + 2 , − + + 1 − 2 , − + ℎ + 1 + 2 );3) если = (22 + 2 )/3, то1 = (−22 + 2 )/3,⎧1/2 1/2⎨(21 − ℎ1 − 2 )/3,если 2 = 1 ℎ1 ,2 =⎩(−2 + + )/3, если = ( + )/2,1122113 = (1 − ) max(− + − 1 − 2 , − + − 1 + 2 ,− + + 1 − 2 , − + + 1 + 2 ) − max(− + − 1 − 2 ,− + − 1 + 2 , − + + 1 − 2 , − + ℎ + 1 + 2 );994) если = (2 + 2 )/2, то1 = (2 − 2 )/2,⎧⎪(1 − 1 )/2,если 2 = (1 + 1 )/2,⎪⎪⎪⎪⎪⎪⎪(1 − ℎ1 )/2,если 2 = (1 + ℎ1 )/2,⎪⎪⎪⎪⎨(1 − ) max((−1 − 1 )/2 + 1 ,2 =⎪⎪−1 + 1 , −1 + 1 )−⎪⎪⎪⎪⎪⎪− max((−1 − 1 )/2 + 1 ,⎪⎪⎪⎪⎩− + , − + ℎ ),если 2 = 1 , 2 = 1 ,11113 = (1 − ) max(− + − 1 − 2 , − + − 1 + 2 ,− + + 1 − 2 , − + + 1 + 2 ) − max(− + − 1 − 2 ,− + − 1 + 2 , − + + 1 − 2 , − + ℎ + 1 + 2 );5) если = 2 , то1 = (1 − ) max(22 − 22 , 2 − 2 ) − max(22 − 22 , 2 − 2 ),⎧⎪⎪( − 1 )/2,если 2 = (1 + 1 )/2,⎪⎨ 12 = (−1 + 1 )/2 + 1 , если 2 = (1 + 1 )/2,⎪⎪⎪⎩( − ℎ )/2 − ,если 2 = (1 + ℎ1 )/2,1113 = (1 − ) max(− + − 1 − 2 , − + − 1 + 2 ,− + + 1 − 2 , − + + 1 + 2 ) − max(− + − 1 − 2 ,− + − 1 + 2 , − + + 1 − 2 , − + ℎ + 1 + 2 );1006) если = 2 = 1 , то1 = (1 − ) max(22 − 21 , 2 − 1 ) − max(22 − 21 , 2 − 1 ),2 = (1 − ) max(1 − 1 , −1 + 1 − 1 , −1 + 1 + 1 )−− max(−1 + 1 , −1 + 1 − 1 , −1 + ℎ1 + 1 ),⎧⎪⎪( − ℎ)/2 − 1 − 2 ,если 1 = ( + ℎ)/2,⎪⎪⎪⎪⎨( − )/2 − 1 + 2 ,если 1 = ( + )/2,3 =⎪⎪(− + )/2 + 1 − 2 , если 1 = ( + )/2,⎪⎪⎪⎪⎩(− + )/2 + + , если = ( + )/2,121где , – вещественные числа, удовлетворяющие условиям 0 ≤ ≤ 1,0 ≤ ≤ 1.Таким образом, приложения, разработанные в главе могут быть примененынапример– для решения задач оптимального размещения центрального серверауправления в сети локальных коммуникаций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
