1612726833-e6f68fc32d761b4e64266f5c195a8f96 (828578), страница 5
Текст из файла (страница 5)
f = −∞, S = S 0.Шаг 2. Решить задачу PS (релаксированная). Если она неразрешима, то конец, так как исходная задача неразрешима. Иначе пусть xS– оптимальное решение. Если ϕi(xS ) ≤ 0, i 6∈ S, то конец и xS –оптимальное решение. Иначе на шаг 3.Шаг 3. Пусть V – некоторое множество номеров ограничений и существует i ∈ V такой, что ϕi(xS ) > 0.Если f (xS ) > f , то f = f (xS ), S = E ∪ V , где E ={i|ϕi(xS ) = 0}, иначе S = S ∪ V . На шаг 2.-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДекомпозиция БендерсаДекомпозиция Бендерса == (Проекция, внешняя аппроксимация / релаксация)Рассмотрим следующую задачуmax {(c, x) + f (y)}x≥0,y∈YAx + F (y) ≤ b, гдеF : Rp → Rm, f : Rp → R.Предположим, что данная задача разрешима.
Т.е. существует допустимое решение (x∗, y ∗), на котором достигается максимальное значение целевой функции на множестве допустимых решений задачи.-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДекомпозиция БендерсаСпроектируем задачу на пространство переменных y и получим следующее её эквивалентное представление:max {f (y) + sup[(c, x)|Ax ≤ b − F (y)]}y∈Y ∩Vx≥0Рассмотрим задачу линейного программирования P (y):max{(c, x)|Ax ≤ b − F (y)}x≥0Она разрешима для y ∗.
Следовательно, двойственная к ней задачаD(y) допустима для любого y:min{(b − F (y), u)|uA ≥ c}u≥0-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДекомпозиция БендерсаПусть u1, . . . , up – вершины, up+1, . . . , up+q – направляющие вектора бесконечных рёбер задачи D(y).Задача P (y) допустима ⇔ задача D(y) разрешима ⇔(b − F (y), uj ) ≥ 0, j = p + 1, .
. . , p + q.Т.е. проекция представима в следующем виде:maxy∈Y:(b−F (y),uj )≥0,j=p+1,...,p+q{f (y) + max[(c, x)|Ax ≤ b − F (y)]}x≥0Применяем внешнюю аппроксимацию:maxy∈Y :(b−F (y),uj )≥0,j=p+1,...,p+q{f (y) + min (b − F (y), uj )}j=1,...,p-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДекомпозиция БендерсаИтак, исходная задача оказалась эквивалентной следующей координирующей задаче:max {f (y) + y0}y∈Y,y0y0 ≤ (b − F (y), uj ), j = 1, . . . , p(b − F (y), uj ) ≥ 0, j = p + 1, .
. . , p + q.Проблема: количество вершин и бесконечных рёбер может оказатьсяэкспоненциально большим. Следовательно задача перечисления такихобъектов является вычислительно сложной. Неудивительно, что в качестве стратегии решения необходимо использовать стратегию релаксации.-14•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДекомпозиция для максиминной задачиz = max min R(x, y).x∈X y∈YȲ ⊆ Y .Шаг 1: Решить релаксированную задачуz̄ = max γ;γ,x∈Xγ ≤ R(x, y),y ∈ Ȳ .Пусть x∗ – её оптимальное решение.Шаг 2: Решить подзадачуz = min R(x∗, y).y∈YПусть y ∗ – её оптимальное решение.Шаг 3: Если z̄ = z, то стоп.
Иначе Ȳ := Ȳ ∪ y ∗ и вернуться наШаг 1.-15•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСвойства методаЛемма 11.1. Если на шагах 1 и 2 существуют оптимальные решенияx∗ и y ∗, то z ≤ z ≤ z̄.2. Метод конечен, если на одном из шагов 1 или 2 повторяется оптимальное решение.-16•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 81. Алгоритм решения задачи о (r|p)-центроиде2.
Метод Такахаши3. Метод Келли-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПостановка задачи о (r|p)-центроидеДанные задачи:I = {1, . . . , n} — множество пунктов для размещения предприятий;J = {1, . . . , m} — множество потребителей;dj ≥ 0 — доход за обслуживание j-го потребителя;gij ≥ 0 — матрица транспортных затрат.Переменные задачи:(1, если Лидер в пункте i открывает предприятие,xi =0, в противном случае.(1, если Конкурент в пункте i открывает предприятие,yi =0, в противном случае.-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЗадача о (r|p)-центроиде (задача Лидера)(1, если клиент j обслуживается из предприятия Лидера,uj =0, если клиент j обслуживается из предприятия Конкурента.maxx,y,uXXdj u jj∈Jxi = p,i∈I(y, u) ∈ F ∗(x),xi ∈ {0, 1}, i ∈ I.-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЗадача КонкурентаIj (x) = {i ∈ I|gij < min(gij |xl = 1}, j ∈ Ji∈Imaxy,uXXdj (1 − uj )j∈Jyi = r, 1 − uj ≤i∈IXyi, j ∈ J,i∈Ij (x)yi + xi ≤ 1, i ∈ I,yi, uj ∈ {0, 1}, i ∈ I, j ∈ J.-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitАлгоритм решенияТочный алгоритм решения для задачи о (r|p)-центроиде == (проекция/декомпозиция)Проектируем задачу на пространство переменных x:nXo∗ρ(x) = maxdj uj |(y, u) ∈ F (x) =y,u= minj∈JnXy,uodj uj |(y, u) ∈ F (x)∗j∈JV = {x : F ∗(x) 6= ∅} = B n, X = {x : |x| = p}.Координирующая задача:max ρ(x) = max min R(x, y),x∈X∩Vx:|x|=p y:|y|=rгде-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitАлгоритм решенияR(x, y) = minu1 − uj ≤XXd j ujj∈Jyi, j ∈ J,i∈Ij (x)uj ∈ {0, 1}, j ∈ J.-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ТАКАХАШИ = (ДУАЛИЗАЦИЯ/СПУСК)Рассмотрим задачу P:f (x) −→ maxxH(x) = 0, G(x) = 0.f – строго вогнутая функция, ограничения линейны.Пусть ограничения G(x) = 0 делают задачу сложной.Применяем дуализацию (преобразование).
Получим задачу D:h(λ) −→ minλгдеh(λ) =sup {f (x) + λtG(x)}.x:H(x)=0-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ТАКАХАШИШаг 1: Выбрать начальное значение λ0.Шаг 2: Для λ = λ0 решить подзадачуsup{f (x) + λtG(x)}.x:H(x)=0Пусть x0 – её оптимальное решение. Если G(x0) =0, то x0 – оптимальное решение задачи P.
Иначевыполнить шаг 3.0Шаг 3: Положить λ = λ0 − αG(x0), α > 00– длина шага.Вернуться на Шаг 2 с новым λ .-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИ = (ВНЕШНЯЯ ЛИНЕАРИЗАЦИЯ/РЕЛАКСАЦИЯ)(c, x) =nXcj xj −→ minx≥0j=1Ax = b, ϕi(x) ≤ 0, i = 1, m.Применяем внешнюю линеаризацию(c, x) =nXcj xj −→ minx≥0j=1ϕi(x) + ∇ϕi(x)(x − x) ≤ 0, ∀xAx = b.-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИ ИЛИ МЕТОД СЕКУЩИХ ПЛОСКОСТЕЙДанный метод используется для решения задач выпуклого программирования вида:min f (x)при условии, чтоϕi(x) ≤ 0, i = 1, m.Здесь f, ϕi : Rn −→ R – выпуклые функции иf, ϕi ∈ C 1.-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИ ИЛИ МЕТОД СЕКУЩИХ ПЛОСКОСТЕЙВводя дополнительные переменную и ограничение,сделаем функционал задачи линейным:min yf (x) ≤ yϕi(x) ≤ 0, i = 1, ..., m,=⇒ без ограничения общности считаем, что f (x) == hc, xi и ограничимся изучением выпуклых задач вида:-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИnX(c, x) =cj xj −→ minj=1при условии, чтоϕi(x) ≤ 0, i = 1, m.Пусть в задаче существует оптимальное решениеx∗, которое содержится в многогранном множестве Q0 = {x ∈ Rn|Ax = b, x ≥ 0}, а такжеQ ⊆ Q0.-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИ = (ВНЕШНЯЯ ЛИНЕАРИЗАЦИЯ/РЕЛАКСАЦИЯ)Итерация k.Шаг 1.
Решаем задачу ЛП(c, x) −→ minx ∈ Qk ,где Qk – текущее многогранное приближение множества Q, Q ⊆ Qk .Пусть xk – оптимальное решение этой задачи.-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИЕсли xk – допустимое решение исходной задачи,то оно его оптимальное решение. Конец работы алгоритма. Иначе переходим к следующему шагу.Шаг 2. Найдём номер ik ограничения, для которого величина ϕik (xk ) > 0 максимальна.
Перейдём к выполнению следующей итерации с0k+1kkQ= Q ∩{x|ϕik (x )+(ϕi (xk ), x−xk ) ≤k≤ 0.}-14•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИКорректность определения множества Qk+1.0k1. Т.к. ограничение ϕik (x ) + (ϕi (xk ), x −kxk ) ≤ 0 линейно, то множество Qk+1 являетсямногогранным.2. Т.к. множество Qk и функция ϕik выпуклые,то0kϕik (x ) + (ϕi (xk ), x − xk ) ≤ ϕik (x)kдля всех x ∈ Qk (Лемма 8, лек.
№ 7)=⇒ Q ⊆Qk+1.-15•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИ(Другими словами ограничение0kϕik (x ) + (ϕi (xk ), x − xk ) = 0kявляется отсечением, которое отсекает точку xk .)Если алгоритм останавливается через конечноечисло шагов, то текущее приближение – оптимальное решение задачи. Рассмотрим случай, когда последовательность {xk } бесконечна.-16•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИТеорема 15.
Любая предельная точка последовательности {xk }, порождённая методом секущихплоскостей, есть оптимальное решение задачи.Доказательство. Последовательность {(c, xk )}монотонно неубывающая и ограничена сверху (т.к.существует оптимальное решение). Поэтому без ограничения общности считаем, что последовательность{xk } ограничена. Тогда считаем, что последовательность {xk }k∈N сходится и x – её предел.-17•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИВыберем произвольное ограничение с номером i.Пусть {xk }k∈T , где T ⊆ N, — подпоследовательность элементов, для которых секущая плоскость порождалась с помощью i-го ограничения.Возможны два случая.-18•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИ1.
Найдётся номер k0 такой, что ϕi(xk ) ≤ 0 длявсех k ≥ k0. Тогдаϕi(xk ) −→ ϕi(x) ≤ 0.Либо2. Подпоследовательность {xk }k∈T бесконечна.Тогда для любого k0 > k00kkkϕi(x ) + (ϕi(x ), x − xk ) ≤ 0.-19•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИСледовательно,00kkkϕi(x ) ≤ kϕi(x )kkx − xk k.0kТ.к. kx − xk k −→ 0 (из-за сходимости после00kдовательности), kϕi(x )k −→ kϕi(x)k (ϕi ∈C 1(Rn)).Получимϕi(xk ) −→ ϕi(x) ≤ 0.-20•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД КЕЛЛИСледовательно, x – допустимое решение задачи (всилу произвольного выбора i). Но для любого kимеем (c, xk ) ≤ (c, x∗) =⇒ (c, x) ≤ (c, x∗).Т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
