Диссертация (1150701), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Прямоугольная метрика записывается следующим образом:−1−1−1(,) = (−11 1 ⊕ 1 1 )(2 2 ⊕ 2 2 ).(3.2)Целевая функция в задаче (3.1) может быть представлена в форме⨁︁−1−1−1 (−11 1 ⊕ 1 1 )(2 2 ⊕ 2 2 ) ==1−1−1−1= −11 2 ⊕ 1 2 ⊕ 1 2 ⊕ 1 2 , (3.3)79где после группировки членов использованы обозначения=⨁︁ 1 2 ,==1=⨁︁⨁︁−1 12 ,=1−1 1 2,=⨁︁=1−1 −1 12 .=1Тогда задача размещения (3.1) принимает вид−1−1−1−11 2 ⊕ 1 2 ⊕ 1 2 ⊕ 1 2 .min2∈R(3.4)Решение такой задачи предложено в теореме 2.Теорема 8.

Минимум в задаче (3.1) равен = ( ⊕ )1/2и достигается тогда и только тогда, когда(︃=2−1(1− − 1− − 1/2))︃где=⨁︁ 1 2 ,==1=⨁︁=1−1 1 2,0 ≤ ≤ 1,,(1− −1 − )1/2⨁︁−1 12 ,=1=⨁︁−1 −1 12 .=1Записывая общий результат в терминах обычных арифметических операций, получим полное решение исходной задачи размещения (3.1) в следующейформе.Следствие 11. Минимум в задаче (3.1) равен = max( + , + )/280и достигается тогда и только тогда, когда(︃=(2 − 1) + (1 − )( + )/2 − ( + )/2)︃(1 − )( − )/2 − ( − )/2,0 ≤ ≤ 1,где = max ( + 1 + 2 ), = max ( − 1 + 2 ), = max ( + 1 − 2 ), = max ( − 1 − 2 ).1≤≤1≤≤1≤≤1≤≤Рассмотрим пример, в котором описана задача размещения с числом заданных точек = 7.Пусть дан набор координат:1 = (1, 7), 2 = (3, 3), 3 = (4, 6), 4 = (5, 3), 5 = (7, 2), 6 = (9, 1), 7 = (9, 9).Воспользуемся теоремой и получим результат.Для начала вычислим = max(8; 6; 10; 8; 9; 10; 18) = 18, = max(6; 0; 2; −2; −5; −8; 0) = 6, = max(−6; 0; −2; 2; 5; 8; 0) = 8, = max(−8; −6; −10; −8; −9; −10; −18) = −6.Пользуясь формулой для получаем: = max(18 + (−6); 8 + 6)/2 = 7.Теперь осталось подставить полученные значения в итоговую формулу.(︃=7(2 − 1) + (1 − )(8 + 18)/2 − (6 + (−6))/2(1 − )(18 − 8)/2 − (−6 − 6)/2)︃=81(︃=14 − 7 + 13 − 13)︃(︃=5 − 5 + 6+6)︃.+5Для любого значения ∈ (0; 1).

Результаты вычислений предложены на рисунке 3.3.Если в качестве в задаче выбрать набор1 = 1, 2 = 3, 3 = 2, 4 = 2, 5 = 1, 6 = 1, 7 = 3,то результат с учетом изменений можно видеть на рисунке 3.4.212 6108r6r@4 @@r2@@@@@rr@@02 4@r@@6@r@br-8 10 12 10rb@b2 @4@@b@rb@Рисунок 3.3 - Случай = 03.6212 6108 br6 b@4@2 @b @@rbrbb@@@b@@brb-6 8 10 12 1@Рисунок 3.4 - Случай ̸= 0Решение задач размещения на плоскости с ограничениями3.6.1Размещение на отрезке прямойДля решения задачи при условии, что допустимое множество задаетсяна плоскости в виде отрезка прямой, применим разработанные выше методы.Для этого задачу размещения будем представлять в виде задачи тропическойоптимизации с ограничениями, а затем решать с использованием результатовпредыдущего раздела.Сначала запишем целевую функцию задачи (3.1) в терминах идемпотентного полуполя Rmax ,+ .

Учитывая, что с помощью операций этого полуполя прямоугольную метрику для векторов = (1 ,2 ) и = (1 ,2 ) можно представитьв форме (3.2), а целевая функция задачи принимает вид (3.3).82Ниже решение задачи (3.1) будет получено для различных случаев расположения на плоскости прямой, на которой выполняется размещение.Размещение на горизонтальной и вертикальной прямойПредположим, что заданы числа ,, ∈ R при условии ≤ . Рассмотримзадачу размещения на отрезке горизонтальной прямой, для которой определиммножество = {(1 ,2 ) | ≤ 1 ≤ , 2 = }.(3.5)Решение задачи приводит к следующему результату.Лемма 1. Минимум в задаче (3.1) при условии (3.5) равен = 1/2 1/2 ⊕ −1 ⊕ и достигается тогда и только тогда, когда1 = (−1 ⊕ )1− (−1 ⊕ −1 )− ,2 = ,где – любое число, удовлетворяющее условию 0 ≤ ≤ 1,=⨁︁−1 1 ( 2 ⊕−12),==1⨁︁−1 −1−1 1( 2 ⊕ 2).=1Доказательство.

Запишем целевую функцию (3.1), используя введенныевыше обозначения и , в следующем виде:(1 ,2 ) =⨁︁−1−1 −1−1−1( 1 ( −1 2 ⊕ 2)−11 ⊕ 1 ( 2 ⊕ 2 )1 ) = 1 ⊕ 1 .=1Теперь рассматриваемая задача сводится к задаче (2.12), в которой заменяется на 1 . После применения следствия 4 получаем необходимое решение.Представление решения в обычных обозначениях дает следующий результат.83Следствие 12. Минимум в задаче (3.1) при условии (3.5) равен = max(( + )/2, − , + )и достигается тогда и только тогда, когда1 = (1 − ) max(− + , ) − max(− − , − ),2 = ,где – любое число, удовлетворяющее условию 0 ≤ ≤ 1, = max ( + 1 + 2 − , + 1 − 2 + ),1≤≤ = max ( − 1 + 2 − , − 1 − 2 + ).1≤≤Заметим, что решение задачи размещения на отрезке вертикальной прямойпри условии = {(1 ,2 ) |1 = , ≤ 2 ≤ }, где ,, ∈ R – заданные числа,прямо получается из решения предыдущей путем замены 1 на 2 , 2 на 1 , атакже на .Размещение на прямой, наклоненной под углом 45∘Перейдем к решению задачи размещения на отрезке прямой, наклоненнойк горизонтальной оси координат под углом 45 градусов.

Пусть заданы числа,,, ∈ R, где ≤ . Тогда отрезок прямой можно определить при помощипараметра в виде = {(1 ,2 ) |1 = + , 2 = + , ≤ ≤ }.Справедливо следующее утверждение.Лемма 2. Минимум в задаче (3.1) при условии (3.6) равен = 1/2 1/2 ⊕ −2 ⊕ 2 ⊕ и достигается тогда и только тогда, когда1 = (−1/2 1/2 ⊕ )1− (−1/2 1/2 ⊕ −1 )− ,(3.6)842 = (−1/2 1/2 ⊕ )1− (−1/2 1/2 ⊕ −1 )− ,где – любое число, удовлетворяющее условию 0 ≤ ≤ 1,=⨁︁−1 −1 1 2 ,==1=⨁︁−1 −1 12 ,=1⨁︁−1−1 (−1 1 2⊕ −1 12 ).=1Доказательство. Записывая равенства 1 = + и 2 = + в терминахтропических операций, имеем 1 = и 2 = . После подстановки в целевуюфункцию (3.3) с учетом введенных обозначений , и получим(1 ,2 ) =⨁︁−1−1 (−1 1 −1 ⊕ 1)( −1 2 −1 ⊕ 2) = −2 ⊕ 2 ⊕ .=1Рассматриваемая задача принимает вид (2.11), решение которой дает следствие 3.С использованием обычных обозначений полученный результате можнопредставить следующей форме.Следствие 13.

Минимум в задаче (3.1) при условии (3.6) равен = max(( + )/2,, − 2, + 2 )и достигается тогда и только тогда, когда1 = (1 − ) max(( − )/2, ) − max(( − )/2, − ) + ,2 = (1 − ) max(( − )/2, ) − max(( − )/2, − ) + ,где – любое число, удовлетворяющее условию 0 ≤ ≤ 1, = max ( + 1 + 2 − − ),1≤≤ = max ( − 1 − 2 + + ),1≤≤ = max ( + 1 − 2 − + , − 1 + 2 + − ).1≤≤85Нетрудно видеть, что допустимое множество для задачи размещения на отрезке прямой, наклоненной под углом 135∘ к горизонтальной оси, может бытьпредставлено в виде = {(1 ,2 ) |1 = − , 2 = + , ≤ ≤ }.Решение такой задачи не имеет существенных отличий от решения предыдущейи находится аналогичным путем.Размещение на произвольной прямойРассмотрим задачу размещения на отрезке произвольной прямой, которыйдля фиксированных чисел ,,, ∈ R, где ≤ , описывается при помощимножества = {(1 ,2 ) | ≤ 1 ≤ , 2 = 1 + }.(3.7)Следующий результат обеспечивает полное решение задачи в явном виде.Лемма 3.

Введем обозначения==⨁︁=1⨁︁−1 1 2, 1 2 −1 ,=⨁︁−1 12 −1 ,=1⨁︁==1−1 −1 12 .=1Тогда справедливы следующие утверждения:1) если < −1 или > 1, то минимум в задаче (3.1) при условии (3.7)равен = 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/(−1) )−1 ⊕86⊕ ((−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/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) ⊕ −1 )− ,2 = 1 ,где – любое число, удовлетворяющее условию 0 ≤ ≤ 1.Доказательство.

Заменим равенство 2 = 1 + на эквивалентное емуравенство в терминах тропических операций в виде 2 = 1 . В результатеподстановки в целевую функцию и использования введенных обозначений , , и получим(1 ,2 ) =⨁︁−1−1 −−1 (−11 1 ⊕ 1 1 )( 1 2 ⊕ 2 1 ) ==1−(−1)= −1⊕ 11−(+1)⊕ 1⊕ +11 .Записывая целевую функцию вместе с ограничением, приходим к задачеоптимизации относительно 1 в виде (2.8).

Решение полученной задачи с помощью следствия 2 дает оптимальные значения для 1 . Вычисление 2 = 1завершает доказательство.При использовании обычных обозначений найденное решение описываетсятак:87Следствие 14. Введем обозначения = max ( − 1 + 2 + ), = max ( + 1 − 2 − ), = max ( + 1 + 2 − ), = max ( − 1 − 2 + ).1≤≤1≤≤1≤≤1≤≤Тогда справедливы следующие утверждения:1) если < −1 или > 1, то минимум в задаче (3.1) при условии (3.7)равен(︂ = max + ( + 1) + ( − 1) ( + 1) + ( − 1) + ,,,,2222 + min(( − 1),( − 1)), − max(( − 1),( − 1)),)︂ − max(( + 1),( + 1)), + min(( + 1),( + 1))и достигается тогда и только тогда, когда(︂(︂)︂(︂)︂ )︂− −− −1 = (1 − ) max min,, min,,−1 −1+1 +1)︂(︂)︂)︂(︂(︂− −− −, min,− ,− max min,,−1 −1+1 +12 = 1 + ;2) если −1 ≤ ≤ 1, то минимум равен(︂ = max + ( + 1) − ( − 1) ( + 1) − ( − 1) + ,,,,2222)︂ + ( − 1), − ( − 1), − ( + 1), + ( + 1)и достигается тогда и только тогда, когда(︂− −1 = (1 − ) max,,−1 +1)︂)︂− −− max,,− ,−1 +12 = 1 + ,(︂88где – любое число, удовлетворяющее условию 0 ≤ ≤ 1.Рассмотрим числовой пример.

Пусть задано множество точек1 = (1, 7) ,2 = (3, 3) ,5 = (7, 2) ,3 = (4, 6) ,6 = (9, 1) ,4 = (5, 3) ,7 = (9, 9) .Сначала рассмотрим решение задачи размещения (3.1), в которой допустимое множество представляет собой отрезок, заданный в виде1 = {(1 ,2 ) | 5 ≤ 1 ≤ 8, 2 = −21 + 19}.Решение такой задачи приведено на рисунке 3.5, где выделенный жирным отрезок прямой представляет множество решений задачи без ограничений, отрезокобычной толщины – допустимое множество размещения, а точка на пересечении– решение задачи с ограничениями.Перейдем к рассмотрению случая, в котором допустимая область размещения задана следующим образом:2 = {(1 ,2 ) | 4 ≤ 1 ≤ 7, 2 = 21 − 6}.В этом случае, как показано на рисунке 3.6, допустимая область размещения не пересекается с множеством решений задачи без ограничений. Решениеисходной задачи изображено точкой, лежащей на отрезке 2 .212 6108r6420212 6108r642rrrAArAcAArAr-2 4 6 8 10 12 1Рисунок 3.5 - Размещение на 10rcr rrrr-2 4 6 8 10 12 1Рисунок 3.6 - Размещение на 2893.6.2Размещение в прямоугольникеПредположим также, что заданы числа ,,, ∈ R такие, что ≤ и ≤ .Определим допустимую область размещения в виде прямоугольника(3.8) = {(1 ,2 ) | ≤ 1 ≤ , ≤ 2 ≤ }.Рассматриваемая минимаксная задача размещения точечного объекта сограничениями (3.1) в виде прямоугольника .С учетом ограничений (3.8) задача (3.1) принимает форму задачи (2.18), где = 1 и = 2 .

Характеристики

Список файлов диссертации