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

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

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

Проведем аналогичные рассуждения иполучим = 1/2 ℎ−1/2 .Пусть 1 = , 1 = .Двойное неравенство для в этом случае преобразуется к следующему виду,записанному в параметрической форме: = (−1/2 −1/2 ⊕ −1 ⊕ −1 )1− (−1/2 −1/2 ⊕ −1 ⊕ −1 ℎ)− 0 ≤ ≤ 1.Случай = 1Пусть сначала = 1/2 1/2 . Тогда двойное неравенство (2.29) для можнозаписать следующим образом:−1/2 −1/2 ( ⊕ −1 ⊕ ) ≤ ≤ 1/2 1/2 ( ⊕ −1 ⊕ ℎ)−1При этом для выражений слева и справа выполняются неравенства1/2 −1/2 ≤ −1/2 −1/2 ⊕ −1/2 −1/2 −1 ⊕ −1/2 −1/2 ,(−1/2 −1/2 ⊕ −1/2 −1/2 −1 ⊕ −1/2 −1/2 ℎ)−1 ≤ 1/2 −1/2 .Отсюда можно сделать вывод, что если = 1/2 1/2 , то выполняется равенство = 1/2 −1/2 .63Теперь пусть = 1/2 1/2 , тогда проводя аналогичные рассуждения получим = −1/2 1/2 , где = (21 −1 −1 ⊕ 1 −1/2 −1/2 )1− (21 −1 −1 ⊕ 1 −1/2 −1/2 )− ,0 ≤ ≤ 1.Если в качестве выбрать = 1/2 ℎ1/2 , то, повторяя рассуждения выше,можно получить равенство = 1/2 ℎ−1/2 −1 , где = (21 −1 ℎ−1 ⊕ 1 −1/2 ℎ−1/2 )1− (21 −1 ℎ−1 ⊕ 1 −1/2 ℎ−1/2 )− ,0 ≤ ≤ 1.Пусть = .

Тогда двойные неравенства (2.29) для и (2.15) для можно записать следующим образом с использованием параметров 0 ≤ ≤1, 0 ≤ ≤ 1 в параметрической форме: = (21 −2 ⊕ 1 −1 )1− (21 −2 ⊕ 1 −1 )− , = ( −1 ⊕ −1 −1 ⊕ −1 )1− ( −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;Исследование этого случая завершает доказательство теоремы.2.2.5Решение задачи с тремя переменнымиПусть заданы числа ,,,,,,,ℎ > 0.

Требуется найти ненулевые решения, , ∈ X задачиmin−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ⊕⊕ −1 −1 ⊕ −1 ⊕ −1 ⊕ ℎ. (2.31)Следующий результат описывает все решения рассматриваемой задачи.Теорема 7. Введем обозначения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 = 1/2 ℎ1/2 ⊕ 1/2 1/2 ⊕ 1/2 1/2 ⊕ 1/2 1/2 ,(2.32)641/2 1/2⊕ 1 1 ,1/2 1/2⊕ 1 ,2 = 1 12 = 1 11/2 1/21/2 1/21/2 1/21/2 1/21/2 1/22 = 1 ℎ1 ⊕ 1 1 ,1/2 1/2 2 = 1 ℎ1 ⊕ 1 ,1/2 1/22 = 1 1 ⊕ 1 1 ⊕ 1 ℎ1 ⊕ 1 .Тогда минимум в задаче (2.31) равен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 , то = 2 −12 ,⎧⎨3/4 −1/4 −1/2 , если 2 = 1/2 1/2 ,11211=1/2 1/2⎩−3/4 1/4 1/2 ,если 2 = 1 1 ,112 = (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;2/3 1/32) если = 2 2 , то2/3 −2/3 = 2 2 ,⎧⎨2/3 −1/3 −1/3 , если 2 = 1/2 1/2 ,11211=1/2 1/2⎩−2/3 1/3 1/3 ,если 2 = 1 1 ,112 = (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;(2.33)652/3 1/33) если = 2 2 , то−2/3 2/3 = 2 2 ,⎧⎨2/3 ℎ−1/3 −1/3 , если 2 = 1/2 ℎ1/2 ,11211=⎩−2/3 1/3 1/3 , если = 1/2 1/2 ,211211 = (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;1/2 1/24) если = 2 2 , то1/2 −1/2 = 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 ,11=−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 ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;5) если = 2 , то−1 1− 2 −2− = (22 −2(2 2 ⊕ 2 −12 ⊕ 2 2 )2 ) ,⎧1/2 −1/21/2 1/2⎪⎪1 1 ,если 2 = 1 1 ,⎪⎨1/2 1/2 = 1−1/2 11/2 ,если 2 = 1 1 ,⎪⎪⎪⎩1/2 ℎ−1/2 −1 , если = 1/2 ℎ1/2 ,11211 = (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− ;666) если = 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/2 ,если = 1/2 1/2 ,1где , – вещественные числа, удовлетворяющие условиям 0 ≤ ≤ 1, 0 ≤ ≤ 1.Доказательство.

Обозначим минимум целевой функции в задаче (2.31) через . Тогда все решения задачи определяются неравенством−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/2 > 0.67Решим систему относительно , считая и параметрами. ≥ −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.34)Множество значений , удовлетворяющих этому неравенству, непусто, есливыполняется условие(−1 −1 ⊕ −1 ⊕ −1 ⊕ )(−1 −1 ⊕ −1 ⊕ −1 ⊕ ℎ) ≤ 2 .Раскроем скобки слева и извлечем квадратный корень из обоих частей неравенства.

Тогда полученная система равносильна неравенству ≥ (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/2 ℎ1/2 ⊕ 1/2 1/2 )⊕⊕ 1/2 1/2 −1 −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 ).Заметим, что переход от исходной задачи к этому неравенству, в котором обозначает минимум целевой функции, включал только эквивалентные преобразования. Из этого следует, что полученное неравенство задает точную нижнюю границу для , выраженную через и , а потому необходимо решитьзадачу оптимизации следующего вида.min (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/2 ℎ1/2 ⊕ 1/2 1/2 )⊕68⊕ 1/2 1/2 −1 −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 ).

(2.35)С учетом обозначений (2.32) задача (2.35) может быть записана в болеекороткой формеmin 1 −1 ⊕ 1 −1 ⊕ 1 ⊕ 1 ⊕ 1 −1 −1 ⊕ 1 −1 ⊕ 1 −1 ⊕ ℎ1 ⊕ 1 .Решение такой задачи предложено в теореме 6. Если воспользоваться усло1/2 1/22/3 1/32/3 1/3вием (2.33), то минимум в задаче (2.31) равен = 2 2 ⊕ 2 2 ⊕ 2 2 ⊕1/2 1/2⊕2 2 ⊕ 2 , и справедливы следующие утверждения:1/2 1/21) если = 2 2 , то = 2 −12 и⎧⎨3/4 −1/4 −1/2 , если 2 = 1/2 1/2 ,11211=1/2 1/2⎩−3/4 1/4 1/2 ,если 2 = 1 1 ;1122/3 −2/32/3 1/32) если = 2 2 , то = 2 2и⎧⎨2/3 −1/3 −1/3 , если 2 = 1/2 1/2 ,11211=1/2 1/2⎩−2/3 1/3 1/3 ,если 2 = 1 1 ;112−2/3 2/322/3 1/33) если = 2 2 , то = 2и⎧⎨2/3 ℎ−1/3 −1/3 , если 2 = 1/2 ℎ1/2 ,11211=−2/31/31/31/21/2⎩1 2 , если 2 = 1 1 ;11/2 1/21/2 −1/24) если = 2 2 , то = 2 2=⎧1/2 −1/2⎪⎪1 1 ,⎪⎪⎪⎪⎨ 1/2 ℎ−1/2 ,11и1/2 1/2если 2 = 1 1 ,1/2 1/2если 2 = 1 ℎ1 ,−1/2 −1/2⎪⎪(1 1 1 ⊕ −11 ⊕ −11 )1− ⊗⎪11⎪⎪⎪⎩⊗(−1/2 −1/2 ⊕ −1 ⊕ −1 ℎ )− , если = , = ;11121 21111169−1 1− 2 −2−и(2 2 ⊕ 2 −15) если = 2 , то = (22 −22 )2 ⊕ 2 2 )⎧1/2 −1/2⎪1 1 ,⎪⎪⎪⎪⎪−1/2 1/2⎪⎪1 1 ,⎪⎨−1/2 −1 = 1/2 ,1 ℎ1⎪⎪⎪⎪⎪(1 1−1 ⊕ 1−1 1 −1 ⊕ 1−1 1 )1− ⊗⎪⎪⎪⎪⎩⊗( −1 ⊕ −1 −1 ⊕ −1 ℎ )− ,1111111/2 1/2если 2 = 1 1 ,1/2 1/2если 2 = 1 1 ,1/2 1/2если 2 = 1 ℎ1 ,если 2 = 1 ,где , – вещественные числа, удовлетворяющие условиям 0 ≤ ≤ 1, 0 ≤ ≤ 1.

Во всех случаях кроме последнего формулу для в виде двойногонеравенства (2.34) запишем с использованием параметра 0 ≤ ≤ 1 следующимобразом: = (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 )1− ⊗⊗ (−1 −1 −1 ⊕ −1 −1 ⊕ −1 −1 ⊕ −1 ℎ)− .Покажем, что в последнем случае может быть записано без использованиядополнительного параметра.Пусть = 1 = 1/2 ℎ1/2 . Тогда двойные неравенства (2.34) для можнозаписать следующим образом:1/2 ℎ−1/2 −1 −1 ≤ −1/2 ℎ−1/2 −1 −1 ⊕ −1/2 ℎ−1/2 −1 ⊕⊕ −1/2 ℎ−1/2 −1 ⊕ −1/2 ℎ−1/2 ≤ ≤ (−1/2 ℎ−1/2 −1 −1 ⊕ −1/2 ℎ−1/2 −1 ⊕⊕ −1/2 ℎ−1/2 −1 ⊕ −1/2 ℎ−1/2 ℎ)−1 ≤ 1/2 ℎ−1/2 −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/2 .Рассмотрение этих случаев завершает доказательство.В главе был рассмотрен ряд задач тропической оптимизации без ограничений и с ограничениями на допустимое решение.

Предложены два подхода:70матричный, основная идея которого состоит в записи расширенной задачи оптимизации в векторной форме, а затем применения экстремальных свойств идемпотентного спектрального радиуса матрицы, а также скалярный, при которомзадача оптимизации сводится к системе параметризованных неравенств и последующего нахождения всех ее решений. Практическое применение результатов, полученных в главе будет изучено в следующем разделе диссертационнойработы.71Глава 3Решениезадачразмещенияточечногообъекта на плоскости с прямоугольнойметрикой и ее приложения3.1История развития задачиНа практике большое значение имеет решение задач выбора мест размещения объектов пространственно распределенных информационных, социальных, экономических и иных систем. В качестве примеров можно привести такиезадачи, как выбор мест размещения маршрутизаторов сети передачи данных,центров обработки информации в распределенных вычислительных сетях, перегрузочных узлов на транспортной сети, обоснование распределения на некоторой территории элементов производственного комплекса, расчет оптимальногоразмещения в городе магазинов шаговой доступности и др.

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

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