Теормин (1125514), страница 2
Текст из файла (страница 2)
В результате все неравенстваограничивают некоторый многогранник (возможно, бесконечный), называемый такжеполиэдральным конусом. Уравнение W(x) = c, где W(x) — максимизируемый (илиминимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимостьот c порождает семейство параллельных гиперплоскостей. Тогда экстремальнаязадача приобретает следующую формулировку — требуется найти такое наибольшееc, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке.
Заметим,что пересечение оптимальной гиперплоскости и многогранника будет содержать хотябы одну вершину. Принцип симплекс-метода состоит в том, что выбирается одна извершин многогранника, после чего начинается движение по его ребрам от вершины квершине в сторону увеличения значения функционала. Когда переход по ребру изтекущей вершины в другую вершину с более высоким значением функционаланевозможен, считается, что оптимальное значение c найдено.Теорема о границах решений задач ЛП с целымикоэффициентамиМетодичка, стр.
28-29Δ(D) = max | det(D1) | , где D1 — квадратная подматрица D.Теорема (о границах решений). Если задача озЛПразмерности (n, m) с целымикоэффициентами разрешима, то у нее существует рациональное рашение x * в шаре:иТеорема о мере несовместности систем линейных неравенствс целыми коэффициентамиМетодичка, стр. 29-▪-приближенное решение системы ЛН, еслив строчной записи:▪ в матричной записи:, где e -- вектор-столбец из единицТеорема. Если система линейных неравенств имеетприближенное решение(), то эта система разрешима, то есть имеет точное решение.Описание метода эллипсоидов▪ Методичка, стр. (30-32) 32-33▪ вики:Метод эллипсоидовРешает задачу линейного программирования за полиномиальное число шагов.Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затемпостепенно сжимать этот эллипсоид; оказывается, на каждом этапе объемэллипсоида уменьшается в константное число раз.Лемма1. Если системасовместна, то в шаренайдется ее решение.Таким образом получаем, что если система совместна, то эта лемма позволяетлокализовать хотбы бы 1 из ее решенийВведем функцию невязки в точке x -- t(x) = maxi((Ax)i − bi).
Точкашара E0. Если-- это центр, то x0 -- решение. Если это не так, то возьмем s:, значит x0 не удовлетворяет s-ому неравенству системы.Всякий вектор x, удовлетворяющий неравенству s, должен лежать вполупространстве. Пересечение этого полупространства с нашейсферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новуюсферу и повторяем алгоритм заново.Теория двойственности ЛП▪ Методичка, стр.
35-36▪ http://www.mathelp.spb.ru/book1/lprog5.htmКаждой задаче линейного программирования можно определенным образомсопоставить некоторую другую задачу (линейного программирования), называемуюдвойственной или сопряженной по отношению к исходной или прямой задаче.Двойственной задачей к задаче линейного программированиямаксимум(в форме ОЗЛП можно записать:на) называетсязадача линейного программирования на минимум:Утверждение Двойственная задача к двойственной задаче совпадает с прямойзадачей линейного программирования.Теорема (двойственности ЛП). Задача ЛП разрешима тогда и только тогда, когдаразрешима двойственная к ней.
При этом в случае разрешимости оптимальныезначения целевых функций совпадают:Сведение озЛП к однородной системе уравнений согрничением x>0Методичка, стр 36-37Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейныхнеравенств.Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейныхуравнений в неотрицательных переменных.Утверждение. Задача ЛП эквивалентна поиску неотрицательного ненулевого решенияоднородной системы линейных уравнений.Идея метода Кармаркара▪ Методичка, стр 37-38▪ http://logic.pdmi.ras.ru/~yura/modern/02seminar.pdfМетод Кармаркара.1.На основании предыдущего утверждения (см.
вопрос о сведении озЛП коднородной системе), есть возможность свести задачу ЛПк поиску решения СЛАУ2., которая, в свою очередь, сводитсяк однородной СЛАУ:Введем функцию Кармаркара:, где▪▪3.N -- число столбцов в PK -- число строк в P▪-- строки матрицы Pприменяя теорему о мере несовместимости и алгоритм округления можнопоказать, что для решения достаточно найти такой, для которого4.при этом можно так же показать полиномиальный алгоритм поиска данногоприближения, который в курсе не рассматривается.Следствия систем линейных неравенств. Афинная леммаФаркаша (без доказательства)▪▪Методичка, стр. 34-35http://imcs.dvgu.ru/lib/nurmi/finmath/node41.htmlСистема линейных неравенствназывается разрешимой, еслиЛинейное неравенствоЛНявляется следствием разрешимой системы, если для всех x, для которых выполняется сама система, выполняетсяи следствие:Афинная лемма Фаракша.
Линейное неравентсвоследствием разрешимой в вещественный переменных ЛНтогда, когда существуютявляется, тогда и только:▪▪▪Лемма Фаркаша о неразрешимостиМетодичка, стр. 35Лемма. Система линейных неравенствкогда разрешима система:▪неразрешима тогда и только тогда,(нулевой вектор)▪▪Элементы математического программированияКлассификация задач математического программирования.Преимущества выпуклого случаяМетодичка.
стр 39-41Задача математического программирования (ЗМП) -- по заданной f(x) найти, то есть:▪найти*-- решение*▪ f = f(x ) -- (оптимальное) значение целевой функции f(x)▪ где X -- допустимое множество (множество ограничений)Классификация проводится по типу допустимого множества X:▪дискретные (комбинаторные) -- множество X конечно или счётно▪целочисленные --▪булевы --▪ непрерывные -▪ бесконечномерные▪ функциональныеЗадачи оптимизации бывают:▪условные --▪ безусловные -Классификация по свойствам целевой функции: выпуклость, гладкость и т.п.Классификация по результату:▪ локальная оптимизация▪ глобальная оптимизацияВыпуклое множество (вики) -- такое множество, которое содержит вместе с любымидвумя своими точками еще и отрезок, их соединяющий.Функция f называется выпуклой, если её надграфик (множество точек над графиком:) является выпуклым множеством.Утверждение.
Любая точка локального минимума выпуклой функции является точкойеё глобального минимума.Преимущества выпуклых задач:▪▪применим метод эллипсоидов, причем сложность - полиномиальнадля острых задач (целевая функция убывает в окрестности минимума немедленнее некоторой линейной функции) можно получить точное решениеФормула градиентного метода в задаче безусловнойминимизацииМетодичка.
стр 41-42Основная идея:▪▪▪▪берем некоторое начальное значениеитеративно вычисляем градиент целевой функциидвигаемся в обратном направлениии так постепенно приходим к (локальному) минимуму функцииФормула градиентного метода -- xt + 1 = xt − αtgradf(xt), где αt -- шаговый множитель:▪▪пассивный способ: {αt} выбирается заранееадаптивный способ: {αt} выбирается в зависимости от реализующейся xt▪метод скорейшего спуска --▪метод дробления (деления пополам) -- если f(xt + 1) > f(xt), то возвращаемсяк шагу t с новым значением αt = αt / 2Идея метода НьютонаМетодичка, стр. 43Метод ньютона -- это фактически градиентный спуск с адаптивынымкоэффициентом, который берется, как 2 производная целевой функции.Реально можно вывести формулу Ньютона из разложения по Тейлору до 2производной в окрестности точки минимума.Формула метода Ньютона в задаче безусловной минимизацииМетодичка.
стр 43Формула Ньютона -, при этом начальноеприближение должно находиться достаточно близко к искомой точке минимума.Метод ньютона имеет квадратичную скорость сходимости:, где Q - некоторая константаОграничения:▪невырожденность матрицы 2 производных (гессиана)▪близость начального приближения к точке минимума ()Идея метода штрафовМетодичка. стр 44Смысл метода в том, чтобы свести задачу условной оптимизации к задачебезусловной оптимизации, то есть избавится от ограничения на область, в которойищем минимум.Для этого вводится так называемая функция штрафа, которая равна нулю в тойобласти, в которой мы "условно оптимизируем" целевую функцию, а в остальныхточках добавляет к значению целевой функции некоторое значение (собственно,штраф).Пример. Пусть область задаётся следующим образом:, гдеg(x) -- некоторая функция.
Тогда рассмотрим задачу безусловной минимизациицелевой функции f(x) со штрафом:константа [??], а-- параметр штрафа, где C -- некотораяСпособы решения переборных задачМетоды глобальной минимизацииМетодичка. стр. 52 (52-55)Метод ветвей и границ для глобальной минимизацииЛипшицевых функцийМетодичка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
