ПРИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

Содержание

Введение

1 Обзор прикладных методов оптимизации

1.1 Нелинейная оптимизация

1.2 Линейное программирование

1.3 Теория двойственности в линейном программировании

1.4 Транспортная задача

1.5 Целочисленное линейное программирование

1.6 Динамическое программирование

2 Практическая задача на нахождение градиента функции

Заключение

Список использованной литературы

Введение

Оптимизация как раздел математики существует достаточно давно. Оптимизация – это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином «оптимизация» в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или «оптимального» решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры – способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.

Наиболее сложно обстоит дело с принятием решений, когда речь идет о мероприятиях, опыта в проведении которых еще не существует и, следовательно, здравому смыслу не на что опереться, а интуиция может обмануть. Пусть, например, составляется перспективный план развития вооружения на несколько лет вперед. Образцы вооружения, о которых может идти речь, еще не существуют, никакого опыта их применения нет. При планировании приходится опираться на большое количество данных, относящихся не столько к прошлому опыту, сколько к предвидимому будущему. Выбранное решение должно по возможности уберечь нас от ошибок, связанных с неточным прогнозированием, и быть достаточно эффективным для широкого круга условий. Для обоснования такого решения приводится в действие сложная система математических расчетов.

Вообще, чем сложнее организуемое мероприятие, чем больше вкладывается в него материальных средств, чем шире спектр его возможных последствий, тем менее допустимы так называемые «волевые» решения, не опирающиеся на научный расчет, и тем большее значение получает совокупность научных методов, позволяющих заранее оценить последствия каждого решения, заранее отбросить недопустимые варианты и рекомендовать те, которые представляются наиболее удачными.

Практика порождает все новые и новые задачи оптимизации причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.

Цель данной курсовой работы – рассмотреть и изучить классификацию прикладных методов оптимизации. Рассмотреть основные понятия, формулы, которые встречаются при решении задач. Также рассмотреть основные приемы решения задач нахождения градиента функции

Задачи данной курсовой работы:

1.                 Произвести обзор прикладных методов оптимизации.

2.                 Решить задачу нелинейного оптимизации на нахождение градиента функции.

1 Обзор прикладных методов оптимизации

1.1 Нелинейная оптимизация

Для постановки задачи оптимизации требуется:

1.      целевая функция f(x), где , определенную на пространстве Rn. Значения этой функции характеризуют степень достижения цели, ради которой решается задача;

2.      множество допустимых точек x ∈Rn, среди элементов которого осуществляется поиск.

Задача оптимизации ставится следующим образом: требуется найти такой вектор х* из множества X допустимых решений, которому соответствует минимальное (или максимальное) значение целевой функции на этом множестве, то есть:

Задача поиска минимума и максимума целевой функции f(x) называется задачей поиска экстремума:

Задача поиска максимума функции f(x) сводится к задаче поиска минимума путём замены знака перед функцией на противоположный:

Решить задачу нелинейной оптимизации означает:

      либо найти пару (x*,f (x*)), включающую точку x* и значение целевой функции в ней;

      либо показать, что целевая функция f(x) не ограничена на множестве допустимых значений, то есть inf f (x) = –∞ в случае задачи на минимум или sup f (x) = +∞ в случае задачи на максимум;

      либо показать, что множество допустимых значений пусто, то есть X = 0.

Множество точек минимума (максимума) целевой функции f(x) на множестве X обозначим x*.Оно может содержать конечное число точек (в частности, одну), бесконечное число точек или быть пустым.

Точка x* ∈ X называется точкой глобального (абсолютного) минимума функции f(x) на множестве X, если функция достигает в этой точке своего наименьшего значения, то есть f(x∗) ≤ f(x).

Точка x* ∈ X называется точкой локального (относительного) минимума функции f(x) на множестве X, если существует ε > 0, такое, что если x ∈ X,то f(x*) ≤ f(x).

Отличие глобального минимума от локального состоит в том, что в случае глобального минимума точка x* сравнивается со всеми точками из множества допустимых точек X, а в случае локального минимума – только с принадлежащими ε–окрестности.

Поверхностью уровня Sa, α ∈ R, функции f(x) называется множество точек x ∈ Rn, в которых функция принимает постоянное значение α, то есть f(x) = α. Если n = 2, поверхность уровня называется линией уровня на плоскости R2.

Градиентом (обозначается f'(x)) непрерывно дифференцируемой функции f(x) в точке x называется вектор–столбец, элементами которого являются частные производные первого порядка, вычисленные в данной точке:

Важное свойство градиента состоит в том, что градиент функции в точке x направлен по нормали к поверхности уровня, проходящей через точку x, то есть перпендикулярно к касательной плоскости, проведенной в точке x, в сторону наибольшего возрастания функции в данной точке.

Вместе с градиентом можно определить вектор антиградиента, равный по модулю вектору градиента, но противоположный по направлению. Он указывает сторону наибольшего убывания функции в данной точке.

Используя понятие поверхности уровня целевой функции и градиента (антиградиента) этой функции, можно дать геометрическую интерпретацию решения задачи нелинейной оптимизации, если задача поставлена в пространстве R2. Эта интерпретация для задачи минимума состоит в следующем. Строим множество допустимых точек X. Через некоторую точку    x ∈ X проводим линию уровня Sa. Антиградиент –f'(x) в этой точке x показывает направление наибольшего убывания функции f(x) в данной точке. Сдвигая точку x ∈ X в сторону антиградиента, находим крайнее положение линии уровня Sa*, если оно существует, такое, что Sa * ∩X ≠∅, а при а > а* будет Sa ∩ X =∅. Тогда множество X* = {x ∈ X ∣f (x) = а*} и будет множеством решений задачи оптимизации. Если же такого положения линии уровня не существует, то целевая функция не ограничена на множестве допустимых точек, то есть inf f(x) =–∞.

Матрицей Гессе H(x) дважды непрерывно дифференцируемой в точке x функции f (x) называется симметричная n х n матрица частных производных второго порядка, вычисленных в данной точке:

Пусть

есть симметричная n х n матрица, то есть матрица, у которой aij = аji,

Квадратичная форма xTAx (а также соответствующая n х n симметричная матрица A) называется:

       положительно определенной (A > 0), если для любого ненулевого x выполняется неравенство xTAx >0;

       отрицательно определенной (A < 0), если для любого ненулевого x выполняется неравенство xTAx < 0;

       положительно полуопределенной (A ≥ 0), если для любого x выполняется неравенство xTAx > 0 и существует вектор x = 0, для которого xTAx = 0;

       отрицательно полуопределенной (A ≤ 0), если для любого x выполняется неравенство xTAx < 0 и существует вектор x = 0, для которого xTAx = 0;

       неопределенной (A <> 0), если существуют такие векторы х и x, что выполняются неравенства xTAx > 0 и xTAx < 0 ;

       тождественно равной нулю (A = 0), если для любого x будет xTAx =0.

Для симметричной матрицы A определители:

,

называются угловыми минорами. Определители m-ого порядка (m ≤ n), получающиеся из определителя матрицы A вычеркиванием каких-либо (n−m) строк и (n−m) столбцов с одними и теми же номерами, называются главными минорами.

Критерии Сильвестра:

1.      Для того чтобы матрица A была положительно определенной, необходимо и достаточно, чтобы знаки угловых миноров были строго положительны:

2.      Для того чтобы матрица A была отрицательно определенной, необходимо и достаточно, чтобы знаки угловых миноров чередовались, начиная с отрицательного:

3.      Для того чтобы матрица A была положительно полуопределенной, необходимо и достаточно, чтобы все главные миноры матрицы A были неотрицательны;

4.      Для того чтобы матрица A была отрицательно полуопределенной, необходимо и достаточно, чтобы все главные миноры матрицы A четного порядка были неотрицательны, а все главные миноры нечетного порядка - неположительны.

1.2 Линейное программирование

Задачей линейного программирования (ЛП) называется задача максимизации или минимизации линейной функции f(x) = (c,x) при x ∈ Ω.

Функцию (c,x) будем далее называть целевой функцией. Ясно, что если умножить целевую функцию на −1, то задача на максимум перейдет в задачу на минимум и наоборот.

Задачу линейного программирования на максимум запишем так

(c,x) → max, Ax ≤ b

Задачу ЛП  такого вида называют основной задачей ЛП. Возможны другие распространенные записи задачи ЛП на максимум, различающиеся способами представления допустимого множества Ω:

      стандартная задача ЛП: (c,x) → max,   Ax < b, x > On;

       каноническая задача ЛП: (c, x)→max,   Ax = b, x > On;

      общая задача ЛП: (c, x)→max,

Геометрическая интерпретация задачи ЛП.

Рассмотрим задачу ЛП в основной форме. Уравнение есть уравнение гиперплоскости в Rn.

Следовательно, ограничение вида  означает, что вектор x принадлежит полупространству, лежащему по одну сторону от гиперплоскости. Множество Ω является, таким образом, многогранным множеством, то есть пересечением конечного числа полупространств.

Множества уровня целевой функции (c, x) образуют семейство параллельных гиперплоскостей

Вектор c является вектором нормали к этим гиперплоскостям и направлен

в сторону возрастания ( c, x) .

Будем перемещаться по гиперплоскостям в направлении вектора c до тех пор, пока множество Ω окажется в одном из полупространств, порожденных некоторой гиперплоскостью и хотя бы одна точка из Ω будет принадлежать этой гиперплоскости. Такая гиперплоскость является опорной для Ω. Ясно, что точки из Ω, лежащие на опорной гиперплоскости, и будут решениями задачи. Если же при сколь угодно больших а пересечение гиперплоскости π(ά) со множеством Ω не пусто, то значение целевой функции на ά может быть сколь угодно большим и, следовательно, задача ЛП в этом случае не имеет решения. Ясно также, что если решение задачи существует, а у множества Ω есть вершины, то, по крайней мере, одна из них является решением задачи.

Симплекс-метод.

Симплекс метод является основным численным методом решения задачи линейного программирования, который представляет собой вычислительную процедуру генерирующую по исходному базисному плану х последовательность базисных планов  х1, х2, ... , хр вместе с их базисами. На очередной итерации в зависимости от текущего значения параметров делается один из выводов:

1.      хр есть решение задачи;

2.      Задача не имеет решения;

3.      Строится следующий базисный план хр+1

Перебор базисов может продолжаться несколько итераций.

Допустимыми планами общей задачи ЛП называется вектор х.

Оптимальными планами задачи называются допустимые планы, на которых целевая функция принимает max значение.

Базисным планом задачи ЛП называется допустимый план х = (х1, х2, ... , хр)T, если у него найдется (n-m) нулевых компонент и при этом остальным компонентам будут соответствовать линейно–независимые столбцы матрицы А. Набор этих векторов называется базисом этого базисного плана.

Описание итераций симплекс–метода.

Допустим получен следующий базисный план хр и его базис. Разложим столбцы матрицы А по этому базису, используя формулу:

И вычилим величны:

Параметры λjk называются коэффициентами замещения, а параметры ∆k– оценками замещения. Выводы 1)–3) делаются в зависимости от знаков коэффициентов и оценок замещения. Обязательно на каждой итерации выполняется одно из трех условий: