Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Содержание

Введение

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) делаются в зависимости от знаков коэффициентов и оценок замещения. Обязательно на каждой итерации выполняется одно из трех условий:

I. Для любого номера k = 1,n выполняется ∆k ≥ 0.

II. Существует номер s = 1,n такой, что ∆s < 0 и λjs ≤ 0 для всех i = 1, m.

III. Существует номер s = 1,n такой, что ∆s < 0 и λjs > 0 при некотором j = 1,m.

Организация вычислений по симплекс–методу осуществляется с помощью симплекс–таблицы Т, которая представляет собой матрицу размера (m+1)*(n+1):

В верхней части таблицы записываются столбцы матрицы А и очередного базисного плана. Слева–столбцы матрицы, образующей базис и вектор дельта ∆.

После заполнения таблицы Т проводится её анализ на основе правил симплекс–метода. Если выполняется условие I или II, то расчеты заканчиваются, если выполняется условие III, то осуществляется переход к следующей симплекс–таблице соответствующей новому базисному плану.

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

Рассмотрим задачу линейного программирования в произвольной форме:

(1.3.1)

где k ≤ m, l ≤ n.

Эту задачу будем называть прямой.
Двойственной к приведенной задаче называется следующая задача:

(1.3.2)

Таким образом, двойственная задача строится по следующим правилам:

1. если прямая задача – задача на максимум, то двойственная задача суть задача на минимум;

2. коэффициентами целевой функции w(u) двойственной задачи служат свободные члены bi ограничений прямой задачи (поэтому число переменных m в двойственной задаче равно числу ограничений прямой задачи);

3. свободными членами cj ограничений двойственной задачи служат коэффициенты целевой функции прямой задачи (поэтому число ограничений n в двойственной задаче равно числу переменных в прямой задаче);

4. матрицей условий двойственной задачи служит транспонированная матрица условий прямой задачи;

5. каждому ограничению-неравенству двойственной задачи соответствует неотрицательная переменная в прямой задаче, и каждому ограничению типа равенства двойственной задачи соответствует свободная переменная (переменная, на знак которой не наложено ограничение) прямой задачи;

6. каждой неотрицательной переменной двойственной задачи соответствует ограничение-неравенство прямой задачи, а каждой свободной переменной двойственной задачи соответствует ограничение-равенство прямой задачи.

Эти правила для каждой задачи (1.3.1) однозначно определяют двойственную задачу (1.3.2). Легко показать, что, если задачу (1.3.2) привести к виду (1.3.1), а затем найти двойственную, то получится задача (1.3.1). Это означает, что двойственная задача к двойственной есть исходная задача.
Соотношения двойственности.

Справедливы следующие утверждения:

1. Пусть x – произвольный план задачи (1.3.1), u* – произвольный план задачи (1.3.2). Тогда z(x) ≤ w(u).

2. Пусть план задачи (1.3.1), u* - план задачи (1.3.2) и z(x*) = w(u*). Тогда x* - оптимальный план задачи (1.3.1), u* - оптимальный план задачи (1.3.2).

3. Если задача (1.3.1) неограничена, т.е. max z(x) = +∞, то множество планов задачи (1.3.2) пусто. И наоборот, если задача (1.3.2) неограничена, т.е. min w(u) = −∞, то множество планов задачи (1.3.1) пусто.

4. Если множества планов обеих задач (1.3.1) и (1.3.2) не пусты, то эти задачи имеют решение.
Решение задачи (1.3.1) существует тогда и только тогда, когда существует решение задачи (1.3.2), причем, если x∗ – оптимальный план задачи (3.1), а u∗ – оптимальный план задачи (3.2), то z(x∗) = w(u∗).

Задача оптимального планирования производства.

Предположим, что предприятие выпускает n видов продукции, используя m видов сырьевых ресурсов. Пусть на изготовление единицы продукции i-го вида требуется aji единиц j-го ресурса и от ее реализации предприятие получает прибыль в размере ci рублей (i = 1, 2,...,n). На складе предприятия имеется bj единиц j-го ресурса (j = 1, 2,..., m). Задача оптимального планирования заключается в следующем: сколько надо изготовить продукции каждого вида из имеющихся запасов сырья, чтобы общая прибыль предприятия была максимально возможной? Переведем эту задачу на язык математики. Обозначим через xi количество изготовленной продукции i-го вида, а через z - прибыль предприятия от реализации всей продукции. В результате мы приходим к следующей задаче линейного программирования:

Мы получили не что иное, как задачу оптимального планирования производства. Это есть классическая интерпретация стандартной задачи линейного программирования в случае, когда ci > 0, aji > 0, bj > 0.

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

Предположим, что имеются m пунктов отправления Ai, A2,.., Am и в них хранится однородный груз в количестве ai ,a2,.. ,am единиц соответственно. Этот груз следует доставить в n пунктов назначения Bi,B2,..,Bn, причем в каждый из них требуется доставить соответственно bi,b2,..,bn единиц этого груза. Через cij обозначим стоимость перевозок единицы груза из пункта Ai в пункт Bj.

Требуется составить план перевозок, суммарная стоимость которых будет минимальной при условии выполнения всех заявок. Такая задача называется транспортной задачей. В такой постановке показателем эффективности транспортной задачи является суммарная стоимость перевозок, а сама транспортная задача называется транспортной задачей по критерию стоимости.

Обозначим через xij ,i = 1,m,j = 1,n, количество груза, перевозимого из i-го пункта отправления Ai в j-й пункт назначения Bj. Величины xij называются перевозками, а совокупность перевозок {xij} называется планом перевозок, или просто планом. Будем обозначать, для краткости }.

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

так как количество перевозимого груза не может быть отрицательным.

Кроме того, на перевозки xij накладываются ограничения, обусловленные количеством перевозимого груза.

Количество груза, вывозимого из i-го пункта отправления Ai во все пункты назначения, должно быть не больше запаса груза в ai единиц в этом пункте:

Количество груза, ввозимого в j-й пункт назначения Bj из всех пунктов отправления, должно быть не больше заявки на груз в bj единиц в этом пункте:

Суммарная стоимость всех перевозок определяется формулой

и должна быть минимальной, то есть f (x)→min.

Очевидно, что транспортная задача является задачей ЛП. Поэтому вся теория таких задач применима и к рассматриваемой задаче. В частности, как и в задаче ЛП, план перевозок будем называть допустимым, если он удовлетворяет ограничениям. Допустимый план перевозок называется базисным планом, если в нем отличны от нуля только базисные перевозки. План перевозок называется оптимальным, если соответствующая ему стоимость перевозок минимальна среди всех допустимых планов, то есть оптимальный план - решение задачи (4.1)-(4.5). Как и в любой ЗЛП, оптимальный план является базисным.

Транспортную задачу, как задачу ЛП, можно решить, например, симплекс-методом. Но ввиду специфики ограничений (коэффициенты при переменных равны единице), транспортная задача может быть решена более простым способом.

Для решения транспортной задачи составляется транспортная таблица (таблица 1.4) первая строка и столбец таблицы соответствуют пунктам назначения Bj и пунктам отправления Ai. Последняя строка и столбец -заявкам bj и запасам ai в пунктах отправления. Нижняя правая клетка таблицы содержит суммарную заявку ∑j bj и суммарный запас ∑i ai.

Таблица 1.4

В левые верхние углы внутренних клеток записываются стоимости соответствующих перевозок cij, а в их правые нижние углы заносятся значения конкретных перевозок xij, удовлетворяющие поставленным ограничениям.

Клетки таблицы, соответствующие отличным от нуля перевозкам, называются базисными клетками, а остальные клетки – свободными.

В зависимости от соотношения между запасами (количеством вывозимого груза) и заявками (количеством ввозимого груза) транспортная задача называется либо сбалансированной, либо несбалансированной.

Если сумма всех заявок равна сумме всех запасов, то есть
,

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

Если сумма всех заявок не равна сумме всех запасов, то есть

то транспортная задача называется несбалансированной или открытой.

Допустимый план сбалансированной транспортной задачи, то есть решение, удовлетворяющее ограничениям, может быть получен, если заполнить клетки транспортной таблицы перевозками xij следующим образом:

 сумма перевозок в каждой строке ∑nxij равняется запасам в ai единиц соответствующего пункта отправления;

 сумма перевозок в каждом столбце ∑mxij равняется заявке в bj единиц соответствующего пункта назначения.

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

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

Далее рассматриваем сбалансированную транспортную задачу:
, где

Для определения начального допустимого плана сбалансированной транспортной задачи наиболее часто применяют метод северо-западного угла и метод минимального элемента.

Метод северо–западного угла подразумевает начало вычислений с элемента x11 ,стоящего в северо-западном углу транспортной таблицы.

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

В этом методе последовательно заполняются клетки с наименьшей стоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью, то из них выбирается любая.

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

Во многих задачах линейного программирования, возникающих на практике, переменные могут принимать только целые значения 0,1, 2,..., так как по своей природе выражают количество физически неделимых объектов, например, количество автомобилей, станков, единиц штучной продукции и т.п. Такие задачи называются задачами целочисленного линейного программирования (ЦЛП).

Важным классом задач ЦЛП являются экстремальные комбинаторные задачи, переменные которых носят логический характер и принимают только два значения 0 и 1. Такие переменные называются булевыми.

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

Классической задачей ЦЛП является следующая «задача о рюкзаке».

Турист, собираясь в поход, должен решить, какие предметы ему взять из имеющихся n типов предметов. Введем обозначения: aj - вес одного предмета j-го типа; Cj - ценность одного предмета j-го типа; xj - число предметов j-го типа, которые турист берет с собой; b - величина, ограничивающая вес рюкзака. Туристу надо решать следующую задачу:

Как же решать задачи ЦЛП? Кажется вполне естественным решить вначале задачу, отбросив требование целочисленности, и полученное решение округлить до целых значений переменных. Однако данный способ далеко не всегда приводит к цели. Во-первых, округленный вектор может оказаться недопустимым в смысле ограничений, а, во-вторых, он может сильно отличаться от точного целочисленного решения.

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

Метод Гомори.

Рассмотрим следующую задачу ЦЛП

(1.5.1)

(1.5.2)

(1.5.3)

(1.5.4)

Изложим сначала алгоритм метода Гомори в целом.

1. Решаем исходную задачу (1.5.1)–(1.5.3) без условия (1.5.4) симплекс-методом. Если эта задача имеет целочисленное решение, то оно будет и решением задачи (1.5.1)– (1.5.4). В противном случае переходим к следующему пункту.

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