1612726833-e6f68fc32d761b4e64266f5c195a8f96 (Лекции слайды)

МЕТОПТ. Лекция (1)2МЕТОПТ. Лекция (2)31МЕТОПТ. Лекция (3)54МЕТОПТ. Лекция (4)68МЕТОПТ. Лекция (5)78МЕТОПТ. Лекция (6)91МЕТОПТ. Лекция (7)107МЕТОПТ. Лекция (8)123МЕТОПТ. Лекция (9)144МЕТОПТ. Лекция (10)170МЕТОПТ. Лекция (11)211МЕТОПТ. Лекция (12)229МЕТОПТ. Лекция (13)251МЕТОПТ. Лекция (14)276ЛЕКЦИЯ № 1от 10.02.14Лектор:http://www.math.nsc.ru/LBRT/k5/mo.html1. Понятие экстремальной задачи2. Элементы алгоритмической теорииэкстремальных задач3.

Классификация задач-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛагранжева теория двойственности1. Определения2. Теорема о седловой точке3. Линейное программирование4. Теория двойственности линейного программирования-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛИТЕРАТУРА[1] Алексеева Е. В., Кутненко О. А., Плясунов А.

В.Численные методы оптимизации. Новосибирск: НГУ, 2008.[2] Болтянский В. Г. Математические методы оптимального управления. М.:Наука, 1969.[3] Васильев Ф. П. Методы оптимизации. М.: ФакториалПресс, 2002.[4] Глебов Н. И., Кочетов Ю. А., Плясунов А. В. Методы оптимизации. Новосибирск: НГУ, 2000.[5] Иоффе А. Д., Тихомиров В. М.

Теория экстремальныхзадач. М.: Наука, 1974.[6] Ларин Р. М., Плясунов А. В., Пяткин А. В. Методы оптимизации. Примеры и задачи. Новосибирск: НГУ, 2003, 2009.[7] Мину М. Математическое программирование. М.: Наука, 1990.-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛИТЕРАТУРА[8] Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. М.: Наука, 1978.[9] Понтрягин Л. С. и др.

Математическая теорияоптимальных процессов. М.: Наука, 1976.[10] Сухарев А. Г., Тимохов А. В., Федоров В.В. Курсметодов оптимизации. М.: Физматлит, 2005.[11] Схрейвер А. Теория линейного и целочисленногопрограммирования. М.: Мир, 1991.[12] Ху Т. Целочисленное программирование и потоки всетях. М.: Мир, 1974.[13] Юдин Д.Б., Гольштейн Е.Г. Линейное программирование.

Теория, методы и приложения. М.:Наука, 1969.-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЭКСТРЕМАЛЬНАЯ (ОПТИМИЗАЦИОННАЯ) ЗАДАЧА(P)Найти:min f (x)(1)при условии, чтоϕi(x) ≤ 0, i = 1, m,(2)x ∈ S ⊆ Rn или Z n или B n.(3)x = (x1, . . . , xn)– вектор переменных;f – целевая функция задачи;ϕi(x) ≤ 0, i = 1, m, x ∈ S – ограничениязадачи.-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетоды оптимизации ≡ Теория оптимизации ≡ Теория экстремальных задач ≡ Математическое программирование1. Теоретическое исследование вопросов существования оптимальных решений экстремальныхзадач.2.

Необходимые и/или достаточные условияэкстремума.3. Разработка численных методов решения.4. Исследование сложности задач (классы PO,FPTAS, PTAS, APX, poly-APX, exp-APX, NPO).-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИсточник экстремальных задач: – экономика, техника и т.д. (см. слайды).Цели лекционного курса:– Изучение ряда базовых алгоритмов, которыеиспользуются для решения конечномерных задач оптимизации.– Получение теоретических и концептуальныхпредставлений, достаточных для понимания, оценки этих алгоритмов и, если необходимо, созданияновых.-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitОСНОВНЫЕ ОПРЕДЕЛЕНИЯВектор x – допустимое решение задачи P , если выполняются ограничения (2),(3).Q(P ) = {x ∈ Rn|ϕi(x) ≤ 0, i = 1, m, x ∈ S} —множество допустимых решений задачи P .Оптимальное решение (глобальный минимум):любое допустимое решение задачи, на котором достигаетсяминимум целевой функции f на множестве Q(P ).1.

g(x) = 0 ≡ g(x) ≤ 0, −g(x) ≤ 0.g(x) ≤ 0 ≡ g(x) + y = 0, где y ≥ 0.2. max g(x) ≡ min −g(x)x∈Qx∈Q-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitОСНОВНЫЕ ОПРЕДЕЛЕНИЯЗадача оптимизации решена, если– либо найдено её оптимальное решение,– либо найден конечный инфинум целевой функции на множестве Q(P ), в случае, когда оптимального решения не существует,– либо доказано, что целевая функция неограничена снизу на множестве допустимых решений,– либо установлено, что множество допустимыхрешений задачи P пусто.-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitКЛАССИФИКАЦИЯ ЗАДАЧВ зависимости от природы множества S задачи оптимизацииклассифицируются как:– дискретные (комбинаторные) — S конечно или счетно,– целочисленные — x ∈ S ⊆ Z n,– булевы — x ∈ S ⊆ B n,– вещественные (непрерывные) — x ∈ S ⊆ Rn,– бесконечномерные — S подмножество гильбертова пространства.-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitКЛАССИФИКАЦИЯ ЗАДАЧЕсли S = Rn или Z n или B n, (m = 0), то задача P– задача безусловной оптимизации.

В противном случае говорят о задаче условной оптимизации.Подробности в пособии (изучить самостоятельно)Алексеева Е. В., Кутненко О. А., Плясунов А. В.Численные методы оптимизации. Новосибирск: НГУ,2008.-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitОСНОВЫ АЛГОРИТМИЧЕСКОЙ ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧВычислимость ≡ Тип вычислительных устройств ≡ Программы ≡ Конечные наборы инструкцийПример невычислимого вещественного числаИдея: использовать 10 проблему Гильберта ≡ разрешимыили нет диофантовы уравнения в целых числах?P −nd =4 , где D – гёделевские номера разрешимыхn∈Dдиофантовых уравнений.Иерархия сложностных классов экстремальных задач.-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitВЫЧИСЛИМОСТЬ ВЕЩЕСТВЕННЫХ ФУНКЦИЙАлгебраическая вычислимость:Данные представляются (аргумент x) точно и любая операция (+, -, *, /) выполняется точно за один шаг при вычислении f (x)Битовая вычислимость:По заданному "хорошему"рациональному приближению xможно получить "хорошее"рациональное приближение f (x)-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitВЫЧИСЛИМОСТЬ ВЕЩЕСТВЕННЫХ ФУНКЦИЙ:ПРОБЛЕМЫАлгебраическая вычислимость:Функции константы вычислимы (сравнить с примером)xНевычислимытрансцендентныефункции.Например:eи√x.Битовая вычислимость:Все вычислимые функции должны быть непрерывны-14•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitБИТОВАЯ ВЫЧИСЛИМОСТЬ: УТОЧНЕНИЕФункция ϕ(n) ∈ { 2mk | m ∈ Z, k ∈ N } такая, чтоkϕ(l) − xk < 2−lназывается представлением числа x ∈ RЧисло x вычислимо тогда и только тогда, когда вычислимоего представлениеПиксель – шар радиуса ε > 0Пиксель вычислим, если вычислимы координаты его центраи радиус.

Например, B( 2mk , 2−l )Образ – набор пикселей заданного размера (разрешение)Соответственно, образ вычислим, если он состоит из вычислимых пикселей-15•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitБИТОВАЯ ВЫЧИСЛИМОСТЬ: УТОЧНЕНИЕОграниченное множество S ⊆ Rn вычислимо, если вычислима следующая функцияT−kf (d, k) = 1, если B(d, 2 ) S 6= ∅T−kf (d, k) = 0, если B(d, 2 ∗ 2 ) S = ∅f (d, k) = 0 или 1, иначеd ∈ { 2mk | m ∈ Z, k ∈ N }Ограниченная функция определённая на ограниченном множестве вычислима, если вычислим её график-16•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛагранжева теория двойственностиРассмотрим задачу P с произвольными функциями f и ϕi:f (x) −→ min(1)ϕi(x) ≤ 0, i = 1, m.(2)Определение 1. ФункциюL(x, λ) = f (x) +mXλiϕi(x),i=1определенную при всех x и λ, назовем функцией Лагранжадля задачи (1), (2).-17•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛагранжева теория двойственностиОпределение 2.

Пара (x∗, λ∗) называется седловой точкойфункции Лагранжа, если∗(3)∗∗(4)L(x , λ) ≤ L(x , λ ) ≤ L(x, λ∗) ∀x ∈ Rn, ∀λ ≥ 0.Пустьg(x) = sup L(x, λ)λ≥0Тогдаg(x) =f (x), x ∈ Q,=⇒+∞, x ∈6 Q.-18•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛагранжева теория двойственностиЗадача P эквивалентна следующей:g(x) −→ minПустьh(λ) = infn L(x, λ).x∈RРассмотрим задачу (D):h(λ) −→ max .λ≥0(D) – задача двойственная к прямой (или исходной) задаче P .λ1, . . . , λm – двойственные переменные, а x1, . .

. , xn — прямыепеременные.-19•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛагранжева теория двойственностиЕсли x ∈ Q, λ ≥ 0, то x — допустимое решение прямой задачи,а λ — допустимое решение двойственной задачи.Лемма 1. (Слабая теорема двойственности).∀x ∈ Q ∀λ ≥ 0 (h(λ) ≤ f (x)).Лемма 2. Если x ∈ Q и λ ≥ 0 и f (x) = h(λ), то x и λ —оптимальные решения задачи P и D, соответственно.-20•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛагранжева теория двойственностиТеорема 1. Вектора x, λ — оптимальные решения прямойи двойственной задачи и f (x) = h(λ) тогда и только тогда, когда пара (x, λ) — седловая точка функции Лагранжа.

При этом L(x, λ) = f (x) = h(λ).Следствие 1. Пусть x ∈ Q(P ), λ ≥ 0. Следующие утверждения эквивалентны:1. Пара (x, λ) — седловая точка функции Лагранжа.2. f (x) = h(λ).3. min sup L(x, λ) = max inf L(x, λ).xλ≥0λ≥0x-21•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛагранжева теория двойственностиСледствие 2. Пусть x∗, x ∈ Q, λ∗, λ ≥ 0.Если пары (x, λ) и (x∗, λ∗) — седловые точки функцииЛагранжа, то пары (x, λ∗) и (x∗, λ) — также седловые точкифункции Лагранжа, причемL(x∗, λ) = L(x, λ∗) = L(x, λ) = L(x∗, λ∗).-22•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛинейное программирование (ЛП)Задача линейного программирования (ЛП) в канонической форме:w(x) = (c, x) −→ min(5)Ax = b,(6)x ≥ 0,(7)где c = (cj ), x = (xj ) ∈ Rn, A = (aij ) — (m × n) матрица,b = (bi) ∈ Rm, m ≤ n, rang(A) = m.Ax = b ≡ (ai, x) = bi, i = 1, m,Ax = b ≡nXAj xj = bj=1-23•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: двойственная задачаЗадача (5) − (7) эквивалентна задаче(c, x) −→ min(ai, x) − bi ≤ 0,λ1i ≥ 0−(ai, x) + bi ≤ 0,λ2i ≥ 0−xj ≤ 0.µj ≥ 0Ее функция Лагранжа:L(x, λ1, λ2, µ) = (c, x)+(λ1, Ax−b)+(λ2, −Ax+b)+(µ, −x) =12= c + (λ − λ )A − µ, x − (λ1 − λ2, b).Следовательно, целевая функция двойственной задачи имеет вид:-24•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: двойственная задачаh(λ1, λ2, µ) = inf L(x, λ1, λ2, µ) =x−(b, λ1 − λ2), если c + (λ1 − λ2)A − µ = 0,==⇒−∞, иначе.Двойственная задачаh(λ1, λ2, µ) −→sup,λ1 ≥0,λ2 ≥0,µ≥0эквивалентна задаче ЛП:−(b, λ1 − λ2) −→ maxc + (λ1 − λ2)A − µ = 0 ≡ c + (λ1 − λ2)A ≥ 0.Умножим ограничения на −1, обозначим y = −(λ1 − λ2)-25•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: двойственная задачаПолучим(b, y) −→ max(8)yA ≤ c.(9)Замечание 1.

Для задач (5)-(7) и (8)-(9) выполняются всеутверждения: л. 1, л. 2, теор. 1, следствия 1 — 2.Теорема 2. Задача двойственная к задаче (8)-(9) совпадает с исходной задачей (5)-(7).Доказательство. Задача (8)-(9) эквивалентна задаче−(b, y) −→ minyA ≤ c.-26•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: двойственная задачаyA ≤ c ≡ системе неравенств (y, Aj ) − cj ≤ 0,xj ≥ 0(сопоставили каждому ограничению двойственную переменную (множитель Лагранжа))Функция Лагранжа:L(y, x) = −(b, y) + (x, yA − c) =−(b, y) + (Ax, y) − (x, c) = (Ax − b, y) − (c, x).Целевая функция двойственной задачиh(x) = inf L(y, x) =y−(c, x), если Ax = b,=⇒−∞, иначе.-27•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: двойственная задачаЗадачаmax h(x)x≥0эквивалентна задаче ЛП:−(c, x) −→ maxAx = b,x≥0илиmin(c, x)Ax = b,x ≥ 0.-28•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: двойственная задачаПрямая задачаnXw(x) =cj xj → minДвойственная задачаmXz(y) =biyi → maxj=1aix ≥ biaix = bixj ≥ 0xj − своб.i=1iijj∈∈∈∈I1I2J1J2yi ≥ 0yi − своб.yAj ≤ cjyAj = cj .Упражнение.Техника получения этой схемы: либо повторить выкладки, приведшие к задаче (8), (9), либо воспользоваться сводимостью общей задачиЛП к задаче ЛП в канонической форме и применить готовый рецепт(задача (8), (9)).-29•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 2Линейное программирование1.