Численные методы решения задач

Содержание

 

Введение 2

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ 4

Метод перебора 6

Метод поразрядного поиска 7

Метод деления пополам 9

Метод золотого сечения 11

РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В СИСТЕМЕ MathCAD 13

Решение оптимизационных задач без ограничений 13

Решение оптимизационных задач с ограничениями 16

Заключение 21

Литература 22

 

Введение

 

Математическое  программирование – математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов  функции на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). В  зависимости от природы множеств задачи математического программирования классифицируются как:

• задачи дискретного программирования (или комбинаторной оптимизации) - если множество конечно и счетно;
• задачи целочисленного программирования – если множество является подмножеством множества целых чисел;
• задачи линейного программирования – если все ограничения и целевая функция содержат лишь линейные функции;
• задачи нелинейного программирования – если ограничения или целевая функция содержат нелинейные функции и множество является подмножеством конечномерного векторного пространства.

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

Математическое  программирование используется при  решении оптимизационных задач  исследования операций. Способ нахождения экстремума полностью определяется классом поставленной задачи.

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

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

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

Решение безусловной оптимизации является более простым и легко реализуется  в современных математических пакетах. Для решения поставленной задачи использовались средства программы  MathCAD. Данная программа позволяет выполнить как численные, так и аналитические вычисления, имеет удобный математически-ориентированный интерфейс и прекрасные средства графики. Система MathCAD изначально создавалась для численного решения математических задач, позже в нее были интегрированы инструменты символьной математики из системы Maple, что постепенно превратило MathCAD в универсальный инструмент решения математических задач. Поэтому выбор данного программного средства вполне обоснован.

 

 

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

 

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

f(x) -> min ,

x принадлежит  [a, b].

Максимизация целевой функции  эквивалента минимизации ( f(x) -> max ) эквивалентна минимизации противоположной величины ( -f(x) -> min ), поэтому, не умаляя общности можно рассматривать только задачи минимизации.

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

Для решения задачи минимизации  функции f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

Большим достоинством прямых методов  является то, что от целевой функции  не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность  определения значений f(x) в заданных точках.

Рассмотрим наиболее распространенные на практике прямые методы поиска точки  минимума. Самым слабым требованием  на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a, b].

 

Метод перебора

 

Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит  в следующем.

Разобьем отрезок [a,b] на n равных частей точками деления:

xi=a+i(b-a)/n, i=0,...n

Вычислив значения F(x) в  точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что

F(xm) = min F(xi) для всех i от 0 до n.

Погрешность определения  точки минимума xm функции F(x) методом  перебора не превосходит величены Eps=(b-a)/n.

 

Метод поразрядного поиска

 

Можно усовершенствовать метод  перебора с целью уменьшения количества значений F(x), которые необходимо находить в процессе минимизации. Во-превых, если оказывается, что F(xi)<= F(x[i+1]), то отпадает необходимость вычислять F(x) в точках x[i+2], x[i+3] и т.д.. Во-вторых, разумно  было бы сначала определить отрезок, содержащий оптимальную точку, грубо, т.е. найти точку xm с небольшой  точностью, а затем искать ее на этом отрезке с меньшим шагом дискретизации, повышая точность. Эти возможности  улучшения и реализованы в  методе поразрядного поиска. В этом методе перебор точек отрезка  происходит сначала с шагом sh=x[i+1]-xi > eps до тех пор, пока не выполнится условие F(xi) < F(x[i+1]) или пока очередная  из точек не совпадет с концом отрезка. После этого шаг уменьшается (обычно в 4 раза), и перебор точек с  новым шагом производится в противоположном  направлении до тех пор, пока значения F(x) снова не перестанут уменьшаться  или очередная точка не совпадет с другим концом отрезка и т.д. Описанный процесс завершается, когда перебор в данном направлении  закончен, а использованный при этом шаг дискретизации не превосходит eps. 
 
Алгоритм метода поразрядного поиска 
 
Шаг1. Выбрать начальный шаг sh=(b-a)/4. Положить x0=a. Вычислить F(x0). 
Шаг2. Положить x1=x0+sh. Вычислить F(x1). 
Шаг3. Сравнить F(x0) и F(x1). Если F(x0)>F(x1), то перейти к шагу 4, иначе -- к шагу 5. 
Шаг4. Положить x0=x1 и F(x0)=F(x1). Проверить условие принадлежности x0 интервалу [a,b]. Если a < x0 < b, то перейти к шагу 2, иначе -- к шагу 5. 
Шаг5. Проверка на окончание поиска: если |sh| <= eps, то вычисления завершить, полагая xm=x0, Fm=F(x0), иначе -- перейти к шагу 6. 
Шаг6. Изменить направление поиска: положить x0=x1, F(x0)=F(x1), sh=-sh/4. Перейти к шагу 2.

 

Метод деления  пополам

Рассмотрим функцию F, которую требуется  минимизировать на интервале [a1, b1]. Предположим, что F строго квазивыпукла. Очевидно, что  наименьшее число вычислений значений функции , которые необходимы для  сокращения интервала неопределенности, равно двум. Одной из стратегий  является выбор этих двух точек симметрично  на расстоянии eps>0 от середины интервала. Здесь число eps настолько мало, чтобы  длина нового интервала неопределенности eps+(b1-a1)/2 являлась достаточно близкой  к теоретическому значению (b1-a1)/2, и  в то же время такое, чтобы значение функции в этих двух точках были различимы.

 
Алгоритм дихотомического  поиска 
 
Алгоритм дихотомического метода для минимизации строго квазивыпуклой фунции на интервале [a1,b1].

 
Начальный этап. Выбрать константу различимости 2еps > 0 и допустимую конечную длину интервала неопределенности l > 0. Пусть [a1,b1] - начальный интервал неопределенности. Положить k=1 и перейти к основному этапу.

 
Основной этап.

Шаг 1. Если bk-ak < l, то остановиться; точка минимума принадлежит интервалу [ak,bk]. В противном случае вычислить pk=(ak+bk)/2-eps qk=(ak+bk)/2+eps и перейти к шагу 2.

 
Шаг2. Если F(pk) < F(qk), положить a[k+1]=ak и b[k+1]=qk. В противном случае положить a[k+1]=pk и b[k+1]=bk. Заменить k на k+1 и перейти к шагу 1.

 

Метод золотого сечения

 

Сравнение различных процедур линейного  поиска естественно производить  в соответствии со следующим коэффициентом  сжатия (длина интервала неопределенности после k выполненных наблюдений)/(длина  интервала неопределенности до выполнения наблюдений). 
Очевидно, что более эффективные схемы соответствуют меньшим значениям коэффициента сжатия. В дихотомическом поиске значение коэффициента приблизительно равно (0.5)^(k/2). Метод золотого сечения является более эффективным, для него значение коэффициента сжатия равно (0.618)^(k-1). 
 
Рассмотрим такое симметричное расположение точек x1 и x2 на отрезке [a,b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет, кроме первой, ограничиться определением только одного значения f(x), так как другое значение уже найдено на одной из предыдущих итераций. Для определения точек x1 и х2 рассмотрим сначала отрезок [0,1] и для определенности положим, что при уменьшении исключается правая часть этого отрезка. Пусть х2=q, тогда симметрично расположенная точка x1=1-q. Пробная точка х1 отрезка [0,1] перейдет в пробную точку х1'=1-q нового отрезка [1,q]. Чтобы точки x2=q и x2'=1-q делили отрезоки [0,1] и [0,q] в одном и том же отношении, должно выполняться равенство 
1/q = q/(1-q) или q^2 = 1-q 
откуда находим положительное значение q = 0.61803... 
Таким образом для произвольного отрезка [a,b] выражения для пробных точек примут вид: 
x1=a+(1-q)(b-a) x2=a+q*(b-a) 
 
Алгоритм метода золотого сечения

 
Алгоритм метода золотого сечения  для минимизации строго квазивыпуклой  фунции на интервале [a1,b1].

Начальный этап. Выбрать допустимую конечную длину интервала неопределенности l>0. Пусть [a1,b1] - начальный интервал неопределенности. Положить p1=a1+(1-0.618)(b1-a1) и q1=a1+0.618(b1-a1). Вычислить F(p1) и F(q1), положить k=1 и перейти к основному этапу.

Основной этап.

Шаг 1. Если bk-ak < l, то остановиться; точка  минимума принадлежит интервалу [ak,bk]. В противном если F(pk)>F(qk), то перейти  к шагу 2, а если F(pk)<=F(qk),то к шагу 3. 
Шаг2. Положить a[k+1]=pk, b[k+1]=bk, p[k+1]=qk, q[k+1]=a[k+1]+0.618(b[k+1]-a[k+1]). Вычислить F(q[k+1]) и перейти к шагу 4. 
Шаг3. Положить a[k+1]=ak, b[k+1]=qk,q[k+1]=pk, p[k+1]=a[k+1]+(1-0.618)(b[k+1]-a[k+1]). Вычислить F(p[k+1]) и перейти к шагу 4. Шаг4. Заменить k на k+1 и перейти к шагу 1.

 

РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ  ЗАДАЧ В СИСТЕМЕ MathCAD 

Оптимизационные задачи можно разделить на два  класса:

задачи  безусловной оптимизации (или оптимизация без ограничений).

задачи  условной оптимизации (оптимизация с ограничениями).

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

Решение оптимизационных задач без ограничений  

Для этого используются две  функции MathCAD: 

·      Maximize(f,<список параметров>) – вычисление точки максимума;

·      Minimize(f,<список параметров>) – вычисление точки минимума,            

             где f – имя минимизируемого функционала, определенного до обращения к функции; <список параметров> – содержит перечисление (через запятую) имен параметров, относительно которых решается оптимизационная задача.

Перед обращением к функциям Maximize, Minimize (имена которых начинаются прописными буквами) следует обязательно задать начальное значение параметров оптимизации.

 

 

 

 Пример 1. Дан функционал: 

.

Определить значения x, y, z, при которых g(x, y, z) достигает минимального значения. 

 

 

 

 

 

Пример 2 . Дан функционал: 

.

Определить значения u, v, при которых f(u,v) достигает максимального значения. 

 

 

 

 

Решение оптимизационных задач с ограничениями  

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

 

Пример 3. Дан функционал  и ограничения в виде

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

 

 

 

Замечание. В оптимизационных задачах с ограничениями решение целесообразно определять из необходимых условий экстремума. Эти условия порождают систему уравнений (чаще всего нелинейных), которые располагаются в блоке Given, вместе с ограничениями, определяющими допустимую область. Само решение ищется с помощью функций Find, Minerr.  

 

 

 

Пример 4. В качестве тестового функционала при поиске точки минимума часто используется функционал Розенброка: