Теормин (Esyr) (1125519), страница 2

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

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

Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.14)Теорема о границах решений задач ЛП с целыми коэффициентамиМетодичка, стр. 28-29Δ(D) = max | det(D1) | , где D1 — квадратная подматрица D.Теорема (о границах решений). Если задача озЛПm) с целыми коэффициентами разрешима, то у нее существует рациональное рашение x * в шаре:иразмерности (n, 15)Теорема о мере несовместности систем линейных неравенств с целыми коэффициентамиМетодичка, стр. 29---приближенное решение системы ЛН, еслив строчной записи:в матричной записи:, где e -- вектор-столбец из единицТеорема.

Если система линейных неравенств имеетприближенное решение (эта система разрешима, то есть имеет точное решение.), то 16)Описание метода эллипсоидов Методичка, стр. (30-32) 32-33 вики:Метод эллипсоидовРешает задачу линейного программирования за полиномиальное число шагов.Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид;; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.Лемма1. Если системасовместна, то в шаренайдется ее решение.Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решенийВведем функцию невязки в точке x -- t(x) = maxi((Ax)i − bi).

Точка-- это центр шара E0. Если, то x0 -- решение. Если это не так, то возьмем s:, значит x0 не удовлетворяет s-ому неравенству системы. Всякий вектор x, удовлетворяющий неравенству s, должен лежать в полупространстве. Пересечение этого полупространства с нашей сферой дают полуэлипсоид.

Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново.17)Теория двойственности ЛП Методичка, стр. 35-36 http://www.mathelp.spb.ru/book1/lprog5.htmКаждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче.Двойственной задачей к задаче линейного программированияОЗЛП можно записать:на максимум(в форме ) называется задача линейного программирования на минимум:Утверждение Двойственная задача к двойственной задаче совпадает с прямой задачей линейного программирования.Теорема (двойственности ЛП). Задача ЛП разрешима тогда и только тогда, когда разрешима двойственная к ней.

При этом в случае разрешимости оптимальные значения целевых функций совпадают:18)Сведение озЛП к однородной системе уравнений с огрничением x>0Методичка, стр 36-37Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейных неравенств.Утверждение.

Задача ЛП оптимизации эквивалентна решению системы линейных уравнений в неотрицательных переменных.Утверждение. Задача ЛП эквивалентна поиску неотрицательного ненулевого решения однородной системы линейных уравнений.19)Идея метода Кармаркара Методичка, стр 37-38 http://logic.pdmi.ras.ru/~yura/modern/02seminar.pdfМетод Кармаркара.1. На основании предыдущего утверждения (см.

вопрос о сведении озЛП к однородной системе), есть возможность свести задачу ЛПк поиску решения СЛАУ,которая, в свою очередь, сводится к однородной СЛАУ:2. Введем функцию Кармаркара: N -- число столбцов в P K -- число строк в P, где-- строки матрицы P3. применяя теорему о мере несовместимости и алгоритм округления можно показать, что для решения достаточно найти такой, для которого4. при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается.20)Следствия систем линейных неравенств. Афинная лемма Фаркаша (без доказательства)Методичка, стр. 34-35http://imcs.dvgu.ru/lib/nurmi/finmath/node41.htmlСистема линейных неравенствназывается разрешимой, еслиЛинейное неравенствоявляется следствием разрешимой системы ЛНвсех x, для которых выполняется сама система, выполняется и , если для следствие:Афинная лемма Фаракша.

Линейное неравентсвовещественный переменных ЛНявляется следствием разрешимой в , тогда и только тогда, когда существует:21)Лемма Фаркаша о неразрешимостиМетодичка, стр. 35Лемма. Система линейных неравенствсистема:(нулевой вектор)неразрешима тогда и только тогда, когда разрешима Элементы математического программирования22)Классификация задач математического программирования.

Преимущества выпуклого случаяМетодичка. стр 39-41Задача математического программирования (ЗМП) -- по заданной f(x) найти, то есть: найти-- решение f * = f(x * ) -- (оптимальное) значение целевой функции f(x) где X -- допустимое множество (множество ограничений)Классификация проводится по типу допустимого множества X: дискретные (комбинаторные) -- множество X конечно или счётноцелочисленные --булевы -- непрерывные - бесконечномерные функциональныеЗадачи оптимизации бывают:условные -- безусловные -Классификация по свойствам целевой функции: выпуклость, гладкость и т.п.Классификация по результату: локальная оптимизация глобальная оптимизацияВыпуклое множество (вики) -- такое множество, которое содержит вместе с любыми двумя своими точками еще и отрезок, их соединяющий.Функция f называется выпуклой, если её надграфик (множество точек над графиком:) является выпуклым множеством.Утверждение.

Любая точка локального минимума выпуклой функции является точкой её глобального минимума.Преимущества выпуклых задач: применим метод эллипсоидов, причем сложность - полиномиальна для острых задач (целевая функция убывает в окрестности минимума не медленнее некоторой линейной функции) можно получить точное решение23)Формула градиентного метода в задаче безусловной минимизацииМетодичка. стр 41-42Основная идея: берем некоторое начальное значение итеративно вычисляем градиент целевой функции двигаемся в обратном направлении и так постепенно приходим к (локальному) минимуму функцииФормула градиентного метода -- xt + 1 = xt − αtgradf(xt), где αt -- шаговый множитель: пассивный способ: {αt} выбирается заранее адаптивный способ: {αt} выбирается в зависимости от реализующейся xtметод скорейшего спуска -метод дробления (деления пополам) -- если f(xt + 1) > f(xt), то возвращаемся к шагу t с новым значением αt = αt / 224)Идея метода НьютонаМетодичка, стр.

43Метод ньютона -- это фактически градиентный спуск с адаптивыным коэффициентом, который берется, как 2 производная целевой функции.Реально можно вывести формулу Ньютона из разложения по Тейлору до 2 производной в окрестности точкиминимума.25)Формула метода Ньютона в задаче безусловной минимизацииМетодичка. стр 43Формула Ньютона -находиться достаточно близко к искомой точке минимума., при этом начальное приближение должно Метод ньютона имеет квадратичную скорость сходимости:некоторая константаОграничения: невырожденность матрицы 2 производных (гессиана)близость начального приближения к точке минимума (, где Q -)26)Идея метода штрафовМетодичка.

стр 44Смысл метода в том, чтобы свести задачу условной оптимизации к задаче безусловной оптимизации, то есть избавится от ограничения на область, в которой ищем минимум.Для этого вводится так называемая функция штрафа, которая равна нулю в той области, в которой мы "условно оптимизируем" целевую функцию, а в остальных точках добавляет к значению целевой функции некоторое значение (собственно, штраф).Пример.

Пусть область задаётся следующим образом:Тогда рассмотрим задачу безусловной минимизации целевой функции f(x) со штрафом:, где C -- некоторая константа [??], а, где g(x) -- некоторая функция. -- параметр штрафаСпособы решения переборных задач27)Методы глобальной минимизацииМетодичка. стр. 52 (52-55)28)Метод ветвей и границ для глобальной минимизации Липшицевых функцийМетодичка. стр. 5429)Метод ветвей и границ для ЦЛП. Различные стратегии методаМетодичка. стр. 5730)Идея метода ветвей и границ.

Пример для задачи БЛПМетодичка. стр. 5931)Теорема оптимальности для разложимых функцийМетодичка. стр 60Опр. Функция f называется разделяемой на f1 и f2, если она представима в виде f(x,y) = f1(x,f2(y)).Опр. Функция f называется разложимой на f1 и f2, если: она разделяема на f1 и f2 f1 монотонно не убывает по последнему аргументуТеорема оптимальности для разложимых функций: minx,y(f(x,y)) = minx(f1(x,miny(f2(y)))).Указанная теорема используется для уменьшения размерности оптимизационных задач и в методе ДП.32)Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачиМетодичка.

стр. 6233)Метод динамического программирования для БЛП с неотрицательными коэффициентамиМетодичка. стр. 63-64Неотсортировано1.2.3.4.Полиномиальный алгоритм округления ε1-приближенного решения системы линейных неравенствПонятие о временной сложности алгоритмовПонятие о недетерминированно-полиномиальных задачахОценка сложности метода эллипсоидов ε2-приближенного решения озЛП.

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

Список файлов ответов (шпаргалок)