Диссертация (1150701), страница 6
Текст из файла (страница 6)
Обозначим минимум целевой функции в задаче (2.8) через. Тогда все решения задачи определяются системой, состоящей из уравненияи неравенства,−1 ⊕ −(−1) ⊕ −(+1) ⊕ +1 = , ≤ ≤ .В силу того, что – минимальное значение целевой функции, равенство всистеме можно заменить на неравенство, что приводит к системе−1 ⊕ −(−1) ⊕ −(+1) ⊕ +1 ≤ , ≤ ≤ .Полученная система неравенств эквивалентна системе−1 ≤ ,−(−1) ≤ ,−(+1) ≤ ,+1 ≤ , ≤ , ≤ .(2.9)Заметим, что перемножение соответствующих частей первых двух неравенств дает неравенство ≤ 2 , откуда с учетом условия леммы следует, что ≥ 1/2 1/2 > 0.Теперь рассмотрим различные условия, которым может удовлетворять значение .35Сначала предположим, что выполняется условие < −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 )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) ⊕ ≤ ≤≤ ≤ ((−1 )1/(−1) ⊕ (−1 )1/(+1) ⊕ −1 )−1 .
(2.10)Это двойное неравенство задает непустое множество, если выполняется очевидное условие(−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) ⊕ −1 ) ≤ 1.Раскроем скобки в левой части, а затем заменим полученное неравенствоэквивалентной системой неравенств, включая неравенство −1 ≤ 1, котороепрямо следует из условия ≤ . Решение остальных неравенств системы отно-36сительно дает ≥ 1/2 1/2 , ≥ (+1)/2 (−1)/2 , ≥ (+1)/2 (−1)/2 , ≥ 1/2 1/2 , ≥ −1 , ≥ −(−1) , ≥ −(+1) , ≥ +1 .Полученная система эквивалентна одному неравенству ≥ 1/2 1/2 ⊕ (+1)/2 (−1)/2 ⊕ (+1)/2 (−1)/2 ⊕ 1/2 1/2 ⊕⊕ −1 ⊕ −(−1) ⊕ −(+1) ⊕ +1 .Учитывая, что обозначает минимальное значение целевой функции, в последнем неравенстве знак неравенства можно заменить на знак равенства.
Осталось представить двойное неравенство (2.10) для в параметрической форме = ((−1 )1/(−1) ⊕ (−1 )1/(+1) ⊕ )1− ((−1 )1/(−1) ⊕ (−1 )1/(+1) ⊕ −1 )− ,где вещественный параметр в показателе степени удовлетворяет условию0 ≤ ≤ 1.Перейдем к исследованию задачи в случае, когда выполняется условие−1 ≤ ≤ 1.Пусть сначала величина удовлетворяет строгому неравенству −1 < < 1,при котором значение − 1 является отрицательным, а + 1 – положительным.Тогда решение неравенств −1 ≤ и −(+1) ≤ системы (2.9) приводитк неравенствам ≥ (−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 ≤ 1, откуда следует, что при = −1 выполняются формальные равенства (−1 )1/(+1) = 0 и (−1 )1/(+1) = 0, а потому очевидно, что ≥ (−1 )1/(+1) и −1 ≥ (−1 )1/(+1) .37В результате объединения полученных неравенств, к которым добавляютсянеравенства ≥ и −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 )1/(+1) ⊕ −1 )−1 .После выполнения необходимых алгебраических преобразований, получаемнеравенство для , которое для минимума целевой функции принимает формуравенства = 1/2 1/2 ⊕ (+1)/2 −(−1)/2 ⊕ (+1)/2 −(−1)/2 ⊕ 1/2 1/2 ⊕⊕ −1 ⊕ −(−1) ⊕ −(+1) ⊕ +1 .С помощью параметра такого, что 0 ≤ ≤ 1, множество решений задачизаписывается в виде = ((−1 )1/(−1) ⊕ (−1 )1/(+1) ⊕ )1− ((−1 )1/(−1) ⊕ (−1 )1/(+1) ⊕ −1 )− .Это утверждение завершает доказательство теоремы.Построение решения задачи для случая, когда > 1, осуществляется такимже образом как в случае < −1 и здесь для краткости опускается.Нетрудно проверить, что формулировку доказанной теоремы можно записать в более компактном виде, объединив результаты для < −1 и > 1 водну общую формулу.Следствие 2.
Пусть ,,,,, > 0 и – вещественное число. Тогда справедливы следующие утверждения:1) если < −1 или > 1, то минимум в задаче (2.8) равен = 1/2 1/2 ⊕ (+1)/2 (−1)/2 ⊕ (+1)/2 (−1)/2 ⊕ 1/2 1/2 ⊕38⊕ ( −(−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 ⊕ )1−(((−1 )−1/(−1) ⊕ (−1 )1/(−1) )−1 ⊕⊕ ((−1 )1/(+1) ⊕ (−1 )−1/(+1) )−1 ⊕ −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 )− ,где – любое число, удовлетворяющее условию 0 ≤ ≤ 1.Теперь рассмотрим два следствия из полученного результата, которые будутиспользованы в примерах приложений в следующей главе.Предположим, что заданы числа ,,,, ∈ X и необходимо найти ненулевыезначения неизвестного ∈ X, которые решают задачуmin −2 ⊕ 2 ⊕ ,∈X(2.11) ≤ ≤ .Нетрудно видеть, что эта задача имеет форму задачи (2.8), в которой необходимо положить = −1 и = .
Тогда применение теоремы 3 дает следующееутверждение.39Следствие 3. Пусть ,,,, > 0. Минимум в задаче (2.11) равен = 1/2 1/2 ⊕ −2 ⊕ 2 ⊕ и достигается тогда и только тогда, когда = (−1/2 1/2 ⊕ )1− (−1/2 1/2 ⊕ −1 )− ,0 ≤ ≤ 1.Теперь получим решение задачи, которая формулируется так:min −1 ⊕ ,(2.12)∈X ≤ ≤ .Ясно, что эта задача сводится к задаче (2.8) при условии, что = 0, = и = . Решение задачи (2.12) находится как следствие из теоремы 3 в следующемвиде.Следствие 4.
Пусть ,,, > 0. Минимум в задаче (2.12) равен = 1/2 1/2 ⊕ −1 ⊕ и достигается тогда и только тогда, когда = (−1 ⊕ )1− (−1 ⊕ −1 )− ,0 ≤ ≤ 1.Заметим, что если добавить числовое значение ∈ X в целевой функциизадачи, то задача оптимизации будет выглядеть следующим образом:min −1 ⊕ ⊕ ,∈X(2.13) ≤ ≤ .Нетрудно проверить, что множество значений , на которых достигаетсяминимум целевой функции, будет иметь то же формульное представление, чтои в следствии 3, а к значению минимума добавится .
Решение задачи (2.13)можно записать в виде следствия.40Следствие 5. Пусть ,,,, > 0. Минимум в задаче (2.13) равен = 1/2 1/2 ⊕ −1 ⊕ ⊕ и достигается тогда и только тогда, когда = (−1 ⊕ )1− (−1 ⊕ −1 )− ,0 ≤ ≤ 1.Преобразуем утверждение следствия 5 к другому, более удобному для дальнейшего использования виду.Следствие 6. Пусть ,,,, > 0. Минимум в задаче (2.13) равен = 1/2 1/2 ⊕ −1 ⊕ ⊕ и справедливы следующие утверждения:1) если = 1/2 1/2 , то = 1/2 −1/2 ;2) если = −1 , то = ;3) если = , то = ;4) если = , то = (−1 ⊕ )1− (−1 ⊕ −1 )− , для любого 0 ≤ ≤ 1.Доказательство.
Представим из формулы (2.10) в виде двойного неравенства−1 ⊕ ≤ ≤ (−1 ⊕ −1 )−1 .Рассмотрим возможные значения . Пусть = 1/2 1/2 . После подстановкив предыдущую формулу и применения свойств монотонности идемпотентногосложения получим1/2 −1/2 ≤ 1/2 −1/2 ⊕ ≤ ≤ (−1/2 1/2 ⊕ −1 )−1 ≤ 1/2 −1/2 ,откуда можно заключить, что = 1/2 −1/2 .Аналогично проверяется, что при = −1 получим = , а при = значение будет равно .41Если = , то используем представление для в параметрической форме.Полученные выражения для решения представим в более компактной форме.Следствие 7. Пусть ,,,, > 0.
Минимум в задаче (2.13) равен = 1/2 1/2 ⊕ −1 ⊕ ⊕ и справедливы следующие утверждения:1) если = 1/2 1/2 ⊕ −1 ⊕ , то = (−1/2 1/2 ⊕ −1 )−1 ⊕ ;2) если = , то = (−1 ⊕ )1− (−1 ⊕ −1 )− ,0 ≤ ≤ 1.Доказательство. Объединим результаты первых трех пунктов в формулировке следствия 6 в один. Заметим, что общее значение может быть записано,как сумма = 1/2 1/2 ⊕ −1 ⊕ .Покажем, что в этом случае все значения, при которых достигается минимумвычисляются по формуле = (−1/2 1/2 ⊕ −1 )−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 ⊕ = 1/2 −1/2 ,что соответствует результату первого пункта следствия 6.Аналогичным образом проверяется, что при = −1 выполняется равенство = (−1/2 1/2 ⊕ −1 )−1 ⊕ = ,а при = – равенство = (−1/2 1/2 ⊕ −1 )−1 ⊕ = .42.2.2.2Решение второй задачи с одной переменнойПредположим, что необходимо найти ненулевые решения ∈ X задачиmin −1/2 ⊕ 1/2 ⊕ −1 ⊕ ⊕ ,∈X(2.14)где ,,,, – числа из X, удовлетворяющие условию ,,,, > 0.Решение этой задачи дает следующий результат.Теорема 4. Минимум в задаче (2.14) равен = 1/2 1/2 ⊕ 2/3 1/3 ⊕ 2/3 1/3 ⊕ ⊕1/2 1/2 ⊕ и достигается тогда и только тогда, когда = (−2 2 ⊕ −1 )1− (−2 2 ⊕ −1 )− ,0 ≤ ≤ 1.(2.15)При этом,1) если = 1/2 1/2 , то = −1 ;2) если = 2/3 1/3 , то = 2/3 −2/3 ;3) если = 2/3 1/3 , то = −2/3 2/3 ;4) если = 1/2 1/2 , то = 1/2 −1/2 ;5) если = , то = (2 −2 ⊕−1 )1− (2 −2 ⊕−1 )− , для любого 0 ≤ ≤ 1.Доказательство.
Обозначим минимум целевой функции в задаче (2.14) через . Тогда все решения задачи определяются уравнением−1/2 ⊕ 1/2 ⊕ −1 ⊕ ⊕ = .В силу того, что – минимальное значение целевой функции, равенство всистеме можно заменить на неравенство, что приводит к неравенству−1/2 ⊕ 1/2 ⊕ −1 ⊕ ⊕ ≤ .43Полученное неравенство эквивалентно системе−1/2 ≤ , 1/2 ≤ , −1 ≤ , ≤ , ≤ .(2.16)Заметим, что перемножение соответствующих частей, например, первого ивторого неравенств дает неравенство ≤ 2 , откуда с учетом условия леммыследует, что ≥ 1/2 1/2 > 0.Решение относительно первых четырех неравенств (2.16) дает ≥ −2 2 , ≤ 2 −2 , ≥ −1 , ≤ −1 .Двойное неравенство для можно записать следующим образом:(2.17)−2 2 ⊕ −1 ≤ ≤ (−2 2 ⊕ −1 )−1 .Множество значений , удовлетворяющих этому неравенству, непусто, есливыполняется условие(−2 2 ⊕ −1 )(−2 2 ⊕ −1 ) ≤ 1.Раскроем скобки в левой части, а затем заменим полученное неравенствоэквивалентной системой неравенств−4 2 2 ≤ 1,−3 2 ≤ 1,−3 2 ≤ 1,−2 ≤ 1.Решая неравенства системы относительно , получим ≥ 1/2 1/2 , ≥ 2/3 1/3 , ≥ 2/3 1/3 , ≥ 1/2 1/2 .Эта система, с учетом последнего неравенства из (2.16), равносильна неравенству ≥ 1/2 1/2 ⊕ 2/3 1/3 ⊕ 2/3 1/3 ⊕ 1/2 1/2 ⊕ .Заметим, что переход от исходной задачи к этому неравенству, в котором обозначает минимум целевой функции, включал только эквивалентные преобразования.
Из этого следует, что полученное неравенство задает точную ниж-44нюю границу для , а значит знак неравенства можно заменить на знак равенства = 1/2 1/2 ⊕ 2/3 1/3 ⊕ 2/3 1/3 ⊕ 1/2 1/2 ⊕ .Двойное неравенство для (2.17) можно записать с помощью параметра0 ≤ ≤ 1, представив его в виде (2.15).Рассмотрим возможные значения .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
