Курс лекци Русакова по методам оптимизации (1083216), страница 12

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

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

Получаем последовательность функцийψ(x,β1),..., ψ(x,βk).Пусть для каждой функции этой последовательности может бытьрешена задача безусловной минимизации (одним из рассмотренных ранееметодов) :arg minψ ( x,β ) = x β *,x ∈ R n .Оказывается,чтопринекоторыхусловияхпоследовательностьоптимальных точек для задач без ограничений может сходиться коптимальнойточкедляисходнойзадачисограничениями:xβ * → x*, x* = arg min f ( x ) на Х.β →0Применяютсяразличныештрафныефункции.распространена следующая штрафная функция:mψ ( x ) = ∑ ( g i+ ( x )) 2 , где g i+ (x ) - «срезка» функции g i (x ) :i =1g i+ (x ) =0, если g i (x ) ≤0111Наиболееg i+ (x ) = gi (x ) , если g i (x ) >0или g i+ ( x ) = max{0, g i ( x )}3.07 Двойственность ЗВПВ формулировке теоремы Куна-Таккера прямые и двойственныепеременные входят симметричным образом.

Поэтому можно ожидать, чтоаналогичная симметрия существует и для задач оптимизации относительнопрямых и двойственных переменных.Введем функцию: g(x)=sup Ψ (x, λ ), при λ ≥ 0Тогда очевидно ,чтоg(x) = f(x), если gi(x) ≤ 0, i=1...mg(x) = ∞ , в противном случаеПонятно, что Ψ (x, λ ) = f(x)+( λ , g(x)), λ ≥ 0Поэтому исходная ЗВП может быть записана в виде:min g(x)-?, при x∈ RnЭту задачу принято называть прямой.Поступим аналогичным образом, поменяв роль переменных иопераций max и min.

Обозначим h( λ )= inf Ψ ( x, λ ) , при x∈RnЗадачу нахождения максимума функции h( λ )-? при λ ≥ 0 , называютдвойственной.Теорема двойственности:Справедливы следующие соотношения двойственности:1121) f(x) ≥ h( λ ) ∀ x∈ X, λ ≥ 02) Если выполнено условие теоремы Куна-Таккера, а пара (x*,λ*)является седловой точкой функции Лагранжа, то λ*-решение двойственнойзадачи.λ* = argmax h( λ ),при λ ≥ 0 и f(x* )=h(λ*)3)Если для допустимых x*, λ* : f(x*)=h(λ*), тоx* = argmin f(x), при x∈ X – решение прямой задачи,λ* = argmax h( λ ), при λ ≥ 0 – решение двойственной задачи.Доказательство:1) f(x) ≥ f(x)+( λ ,g(x))= Ψ (x, λ ) ≥ inf Ψ (x, λ ) = h( λ ), при x∈Rn2) Для всех λ ≥ 0 справедливо соотношение:h(λ*)= inf Ψ (x ,λ*) = Ψ (x* , λ*) ≥ Ψ (x* , λ ) ≥ inf Ψ (x, λ ) = h( λ ),приx∈RnОтсюда λ* - решение двойственной задачи.Но Ψ (x*, λ*) = f(x*) ⇒ h(λ*)=f(x*)3) На основании 1) f(x) ≥ h(λ*) = (на основании 2)) f(x*) ≥ h( λ )тогда x*- прямое решение, λ*- двойственное решениеПродемонстрируем двойственность ЗВП на примере задачи линейногопрограммирования (ЗЛП) , которая вкладывается в ЗВП.Напомним, что функция f называется вогнутой, если -f выпуклаяфункция.113Определение.

Функция, которая выпукла и вогнута одновременно,является афинной или линейной функцией.ИТОГО:МатематическоепрограммированиеЗНП(т. Кароша - Джона)ЗВП(т. Куна- Таккера)ЗЛП(симплекс -метод поискаопт. точки)Глава 4 Решение переборных задачДопустимое множество состоит из конечного числа элементов, поэтомурешение задачи всегда можно найти за конечное число шагов, но в рядеслучаев количество вариантов слишком велико, чтобы можно былоорганизовать их полный перебор, и приходится искать методыцеленаправленного перебора.4.01 Метод ветвей и границ114Пусть I 0 - все множество возможных вариантов.

На этом множествезадан функционал качества f(x). Надо найти min0 f(x)x∈IПусть мы можем оценить этот минимум на I 0 через параметр α:α ≤ minf(x)0IДелим множество I 0 на два множества. Для каждого из этих множестввыписываем оценку:f(x); α 11 , α 21 ≥ α 0α ij ≤ miniIjБудем постепенно получать дерево: (α -граница)I0ветвьI 11α 1122I 11α 11• • • •I 21α 2122I 12α 12• • • •Способ получения этого дерева описывается ниже:Выберем минимальный среди α ij .Пусть минимальный α 11 .Делим I 11 на два множества, вычисляем оценки и т.д.Пусть где-то получили множествоI ijk ...= { x * } с оценкой α ijk ...(которая меньше всех других)Тогда x * - оптимальный вариант.Если оценка не минимальная, то находим тот лист дерева, у которогооценка минимальная и соответственно I вновь разбиваем на два множества ит.д.Метод ветвей и границ (МВГ) дает экономию по сравнению сперебором всех вариантов.Рассмотрим пример.1154.02 Задача о коммивояжере.Есть n городов.

Надо объехать все города с минимальной стоимостью(расстоянием) и вернутся в исходный город. При этом каждый городпосещается один раз (т.е. имеется Гамильтонов цикл, но с минимальнойстоимостью).Матрица стоимостей путей1......n1A=2∞a21a12∞......a1na2 n.................nan1 an 2...∞aij -стоимость пути от i до j.aij м.б.≠ a ji , aij ≥ 0 ,∀ i, jДопустимый маршрут содержит по одному элементу в каждой строке истолбце. Обратное неверно, так как возможны подциклыКоличество возможных вариантов n!.Составим математическую модель:Обозначим xij =  , причем01 - если дуга входит в маршрут0 - если дуга не входит в маршрут.min ∑∑ aij xij −? , причем1i116jn∑ xij= 1, j = 1, n , xij ∈{0,1}i =1* в каждом столбце содержится один элементn∑ xij= 1, i = 1, nj =1* в каждой строке содержится один элементЭти ограничения разрешают циклы, поэтому эти условия являютсянеобходимыми, но не достаточными.Требование непрерывности маршрута обеспечиваются введениемдополнительных N ограничений, где N = (n − 1)2 − (n − 1) , каждое ограничениеимеет вид:y i − y j − n⋅ xij ≤ n − 1i = 2, n , j = 2, nТаким образом, матрица сильно разрежена, симплекс-метод применятьне выгодно.Используем МВГ.Предположим, что мы выбирали некоторый путь S, его длинаl S = ∑ aij , причем каждый из индексов используется один и только один раз.ijТак как в путь S входит только один элемент из каждой строки истолбца, то можно проделать операцию нормализации матрицы A.

Выберемпроизвольную строку i .λi - наименьший элемент i -й строки и построим матрицу A / сэлементамиaij/ = aij − λi (изменена каждая строка)Матрица A / определяет новую задачу коммивояжера, которая вкачестве оптимальной будет иметь ту же последовательность городов.nl S = l /S + ∑ λii =1В каждой строке A / будет теперь, по крайней мере, один нулевойэлемент.Обозначим g j - минимальный элемент j-го столбца A / .117Построим матрицу A // с элементами aij// = aij/ − g jnni =1j =1Оптимальный путь тот же, а длина l S = l //S + d 0 , где d 0 = ∑ λi + ∑ g jОбозначим l * - решение задачи коммивояжера (ЗК).l * = min l Ss∈SТогда величина d 0 - простейшая нижняя оценка решения l * :*d0 ≤ l(*)d 0 − это α 0 для МВГ.Рассмотрим ЗК с матрицей A // .Рассмотрим путь S, содержащий переход i→ j.Тогда нижняя оценка пути:l S ≥ d 0 + a ij//Следовательно, для тех переходов, у которых aij// = 0 будем иметь сноваоценку (*).

Естественно ожидать, что кратчайший путь содержит один изтаких переходов.Рассмотрим один из переходов i→ j, для которого aij// = 0.Обозначим (i →/ j) -множество всех тех путей, которые не содержатпереход i→ j.Так как из города i надо куда-то идти, то множество (i →/ j) содержитодин из переходов i→ k, k ≠ j.Так как в город j надо прийти, то множество (i →/ j)содержит переходm→ j, где m ≠ i.Следовательно, некоторый путь l S из множества (i →/ j), содержащегопереходыi→ k , m→ j, будет иметь следующую нижнюю оценку://l S ≥ d 0 + a ik// + a mjОбозначим://Θ ij = min a ik// + min a mjm≠ik≠ jДля любого из множества путей (i →/ j) мы будем иметь оценку:l S ≥ d 0 + Θ ij118(**)Мы хотим исключить некоторое множество вариантов (i →/ j).Поэтомунадо выбрать такой переход i→ j, для которого оценка (**) была бымаксимальной.Θ* =max//{ aij/ : aij/ = 0 }a // )( min aik// + minm≠i mjk≠ jТаким образом, все множество возможных вариантов мы разбили надва множества: I 1 , I 2 .Для путей из множества I 1 - оценка (*).Для путей их множества I 2 - оценка l S ≥ d 0 + Θ* .Для I 2 матрица A2 будет отличаться от матрицы A // тем, что aij := ∞(переход i→ j запрещен , кот.

выбран).Рассмотрим множество I 1 и матрицу A // .Так как все пути, принадлежащие этому множеству, содержат переходi→ j, то для его исследования достаточно рассмотреть ЗК, в которой города iи j совпадают(из A // вычеркивается i -ая строка и j -й столбец).Размерность этой задачи n - 1.Так как переход j→ i невозможен, то элементы матрицы A1 : a ji := ∞ .Точнее, так как элемента aji может не быть, маршрут, определяемыйдугой( i, j ) содержит сколько-то (может быть ни одного) из ранеевыбранных ребер помимо ребра ( i, j ).Ребро ( i, j ) будет или изолировано от этих других ребер, или будетчастью пути, включающего некоторые или все эти ребра.Пусть p и q - начальный и конечный города этого пути.

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

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