Теория принятия решений. Нeлинейное программирование: Безусловная однопараметрическая оптимизация
Начальная страница. Содержание
Введение    Цели и задачи     Методологические основы     Линейное программирование     Нeлинейное программирование     Нeлинейное программирование: Безусловная однопараметрическая оптимизация     Нeлинейное программирование: Безусловная многопараметрическая оптимизация    Нeлинейное программирование: Условная многопараметрическая оптимизация    Целочисленное и дискретное программирование     Динамическое программирование     Принятие решений в условиях неопределенности     Принятие многоцелевых решений     Марковские процессы принятия решений     Литература    



Теоретические разделы

Задания к лабораторно-практическим работам

Примеры

3.2.1. Методы исключения интервалов

3.2.2. Методы полиномиальной аппроксимации

3.2.3. Методы с использованием производных

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

3.2.5. Контрольные вопросы и задания

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Задача решается с использованием пакета MathCAD (лесоинженеры) или любого алгоритмического языка (АСОИУ) с проверкой в пакете EXCEL или LINGO. В отчете отразить постановку задачи а также приложить распечатки созданных программ и тестовых решений.

 


 

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

 

Пример 3.1. Оптимальный раскрой лесоматериалов.

Бревно длиной lo м имеет форму конуса, диаметры оснований которого равны соответственно dk и do м. Требуется автоматизировать процесс раскроя бревна для получения бруса квадратного поперечного сечения, ось которого совпадала бы с осью бревна и объем которого был бы наибольшим. Определить размеры бруса (рис.3.1).

Постановка задачи.

1. В качестве показателя эффективности целесообразно взять объем бруса, м3.

2. В качестве управляемой переменной задачи следует взять длину бруса l. При этом длина бруса l связана с поперечным размером b следующими зависимостями:

d= dk - (dk-do ) l / lo;

b2=2d2,

где

dk - диаметр бревна в комле, м;

do - диаметр бревна в вершине, м;

lo - длина бревна, м.

  1. Целевая функция:

W(l)=l (dk - (dk-do ) l / lo)2 (r) max.

 

Пример 3.2. Планирование борьбы с лесными пожарами

Лесной пожар распространяется в узкой долине шириной 2 км со скоростью V м/мин. Задержать наступление огня можно путем построения противопожарной перегородки, пересекающей лес по всей ширине долины. Один рабочий может построить l м перегородки в минуту. Затраты на транспортировку каждого рабочего к месту пожара и обратно составляют C руб.; оплата труда каждого рабочего составляет S руб. в час. Удельные потери от прохождения огня оцениваются в L руб./га. Сколько рабочих следует послать на борьбу с огнем, чтобы полные издержки были минимальны.

Постановка задачи.

1. В качестве показателя эффективности целесообразно взять полные затраты на построение противопожарной загородки, руб, включающие в себя транспортные расходы Wt и оплату труда рабочих Ww а также потери лесных угодий от огня Wf.

2. В качестве управляемой переменной задачи следует взять потребное число рабочих для тушения пожара n.

3. Целевая функция:

W(n)= Wt +Ww +Wf= (r) min.

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


 

 

3.2.1. Методы исключения интервалов

 

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

Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции W(x) сравнение значений W(t) в двух различных точках интервала поиска позволяет определить в каком из заданных двумя указанными точками подынтервалов точки оптимума отсутствуют.

Правило исключения интервалов. Пусть W(x) унимодальна на отрезке [a,b], а ее минимум достигается в точке x*. Рассмотрим x1 и x2, расположенные a<x1<x2<b.

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

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

Процесс применения методов поиска на основе исключения интервалов включает два этапа:

Этап установления границ интервала

 

Выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно используется эвристический метод, например, Свенна, в котором (k+1) пробная точка определяется по рекуррентной формуле

xk+1 = xk + 2k D , k=0,1,2... (3.1)

где

xo - произвольно выбранная начальная точка;

D - подбираемая величина шага.

Знак D определяется путем сравнения значений W(x), W(xo + | D | ), W(xo -| D | ):

Пример 3.3.

W(x)=(100-x)2, xo=30, | D | =5.

Определим знак D :

W(30)=4900;

W(30+5)=4225;

W(30-5)=5625.

Выполняется условие W(xo -| D | ) і W(x) і W(xo + | D | ), следовательно, D имеет положительное значение; x*=30.

x1=xo+20D = 35;

x2=x1+21D = 45, W(45)=3025 < W(x1) Ю x*>35;

x3=x2+22D = 65, W(65)=1225 < W(x2) Ю x*>45;

x4=x3+23D = 105, W(105)=25 < W(x3) Ю x*>65;

x5=x4+24D = 185, W(185)=7225 > W(x4) Ю x*<185.

Искомый интервал 65<x*<185.

Этап уменьшения интервала

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

Найти W(x) на отрезке [a,b].

Шаг 1. xm=(a+b)/2; L=b-a; вычислить W(xm).

Шаг 2. x1=a+L/4; x2=b-L/4; вычислить W(x1) и W(x2).

Шаг 3.

  1. Если W(x1)<W(xm), то исключить (xm,b], т.е. b=xm, xm=x1. Перейти к шагу 5.
  2. Если W(x1)і W(xm), то перейти к шагу 4.

Шаг 4.

  1. Если W(x2)<W(xm), то исключить [a,xm), т.е. a=xm, xm=x2. Перейти к шагу 5.
  2. Если W(x2)і W(xm), то исключить [a,x1) и (x2,b], т.е. a=x1, b=x2. Перейти к шагу 5.

Шаг 5. L=b-a. Если | L| <e , то закончить поиск. В противном случае вернуться к шагу 2.

Продолжение примера 3.2.Ортимальный раскрой лесоматериалов (MathCAD)

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

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

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

. Учитывая, что z1+z2=z, имеем

W(x)

 

z

 

z12=z z2 = (z1+z2)z2 = z1z2 + z22;

 

z1

z2

 

z1z2 + z22 - z12 = 0,

 

 

 

 

откуда .

 

 

 

 

 

a

x

b

x

 

Рис. 3.2. Определение коэффициента дробления

Найти W(x) на отрезке [a,b].

Шаг 1. Вычисляем коэффициент дробления отрезка [a,b] k=(- 1)/2.

Шаг 2. x1=a+(1-k)(b-a), вычислить W(x1).

Шаг 3. x2=a+k(b-a), вычислить W(x2).

Шаг 4.

  1. Если | x2-x1| Ј e , где e - заданная погрешность, то xm = (x1+x2)/2, вычислить W(xm) и закончить поиск.
  2. Если | x2-x1| >e , то перейти к шагу 5.

Шаг 5.

  1. Если W(x1)>W(x2), то исключить a=x1, x1=x2 и W(x1)=W(x2). Перейти к шагу 3, затем к шагу 4.
  2. Если W(x1)Ј W(x2), то b=x2, x2=x1 и W(x1)=W(x2). Перейти к шагу 2 и 4.

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


 

 

 

3.2.2. Методы полиномиальной аппроксимации

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

Квадратичная аппроксимация

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

Если целевая функция W(x) в точках x1, x2, x3 принимает соответствующие значения W1, W2, W3, то можно определить коэффициенты aо, a1, a2 таким образом, что значения квадратичной функции

q(x) = ao + a1(x-x1) + a2(x-x1)(x-x2) (3.2)

совпадут со значением W(x) в трех указанных точках. Вычислим q(x) в трех указанных точках.

 

 

W1 = W(x1) = q(x1) = ao

 

ao = W1

W2 = W(x2) = q(x2) = W1 + a1(x2 - x1)

a1 =(W2 - W1)/(x2 - x1)

W3 =q(x3) = W1 + [(W2 - W1) (x3 - x1)]/ /(x2 - x1) + a2(x3 - x1) (x3 - x2)

a2 =

Метод Пауэлла

Шаг 1. x2 = x1 + D x.

Шаг 2. Вычислить W(x1) и W(x2).

Шаг 3.

W(x1) > W(x2),

Шаг 4. Вычислить W(x3) и найти

Wmin = min{ W(x1),W(x2), W(x3)},

Xmin = xi, соответствующая Wmin.

Шаг 5. По x1, x2, x3 вычислить x*, используя формулу для оценивания с помощью квадратической аппроксимации.

Шаг 6. Проверка окончания

  1. Если | Wmin - W(x*)| < e W, то закончить поиск. В противном случае к шагу 7.
  2. Если | Xmin - x*| < e x, то закончить поиск. В противном случае к шагу 7.

Шаг 7. Выбрать Xmin или x* и две точки по обе стороны от нее. Обозначить в естественном порядке и перейти к шагу 4.

 


 

 

3.2.3. Методы с использованием производных

Целесообразно предположить, что эффективность поисковых процедур существенно повысится, если в дополнение к условию непрерывности ввести требование дифференцируемости целевой функции. Необходимое условие существования оптимума целевой функции в точке x*

W'(x*) = dW/dx п x=x* = 0. (3.3)

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

Метод средней точки

Сущность метода. Основан на алгоритме исключения интервалов, на каждой итерации которого рассматривается одна пробная точка R. Если в точке R выполняется неравенство W'(R) < 0, то в следствии унимодальности функции точка оптимума не может лежать левее точки R. Аналогично, если W'(R) > 0, то интервал x>R можно исключить.

Пусть в интервале [a,b] имеются две точки N и P, в которых производные W'(N)<0 и W'(P)>0. Оптимальная точка x* расположена между N и P.

Шаг 1. Положить P=b, N=a, причем W'(a)<0 и W'(b)>0.

Шаг 2. Вычислить R=(P+N)/2 и W'(R).

Шаг 3. Если | W'(R)| < e , то закончить поиск. В противном случае, если W'(R)<0, положить N=R, и перейти к шагу 2. Если | W'(R)| > e , положить P=R и перейти к шагу 2.

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

Пример 3.4.

Минимизировать W(x)=2x2+(16/x) в интервале 1Ј xЈ 5.

W'(x) = dW(x)/dx = 4x-16/x2.

Итерация 1.

Шаг 1. N=1, P=5, W'(5)=19.36, W'(1) = -12.

Шаг 2. R=(5+1)/2=3.

Шаг 3. W'(3)=10.22>0; положить P=3.

Итерация 2.

Шаг 2. R=(3+1)/2=2.

Шаг 3. W'(2)=4>0; положить P=2.

Итерации продолжаются до тех пор, пока не будет выполняться неравенство | W'(R)| Ј e ,

 

Метод хорд

Сущность метода. Ориентирован на нахождение корня уравнения W'(x) в интервале [a,b], в котором имеются две точки N и P, в которых знаки производных различны. Алгоритм метода хорд позволяет аппроксимировать функцию W'(x) "хордой" и найти точку, в которой секущая графика W'(x) пересекает ось абсцисс.

Рис. 3.3.Схема метода хорд

 

Шаг 1. Следующее приближение к стационарной точке x* определяется по формуле

R = P - . (3.4)

Шаг 2. Вычислить W'(R).

Шаг 3. Если | W'(R)| < e , то закончить поиск. В противном случае необходимо выбрать одну из точек P или N, чтобы знаки производных в этой точке и точке R были различны. Вернуться к шагу 1.

Как видно из алгоритма, метод хорд реализован на исследовании как знака производной, так и ее значении. Поэтому он более эффективен, чем метод средней точки.

Пример 3.5.

Минимизировать W(x)=2x2+(16/x) в интервале 1Ј xЈ 5.

W'(x) = dW(x)/dx = 4x-16/x2.

Итерация 1.

Шаг 1. N=1, P=5, W'(5)=19.36, W'(1) = -12.

Шаг 2. R=5-{19.36/[(19.36+12)/4]}=2.53.

Шаг 3. W'(2.53)=7.62>0; положить R=2.53.

Итерация 2.

Шаг 2. R=2.53-{7.62/[(7.62+12)/1.53]}=1.94.

Шаг 3. W'(1.94)=3.51>0; положить R=1.94.

Итерации продолжаются до тех пор, пока не будет выполняться неравенство | W'(R)| Ј e ,

 

Метод касательных

Сущность метода. Ориентирован на нахождение корня уравнения W'(x) в интервале [a,b], в котором имеются две точки N и P, в которых знаки производных различны. Работа алгоритма начинается из точки xo, которая представляет начальное приближение корня уравнения W'(x)=0. Далее строится линейная аппроксимация функции W'(x) в точке x1, и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения. Если точка xk принята в качестве текущего приближения к оптимальной точке, то линейная функция, аппроксимирующая функцию W'(x) в точке xk, записывается в виде

W'(x,xk) = W'(xk) + W''(xk)(x-xk). (3.5)

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

Рис.3.4. Схема метода касательных

Шаг 1. Следующее приближение к стационарной точке x* определяется по формуле

xk+1 = xk - [W'(xk)/W''(xk)].

Шаг 2. Вычислить W'(xk+1), W''(xk+1)

Шаг 3. Если | W'(xk+1)| < e , то закончить поиск. В противном случае необходимо вернуться к шагу 1.

Как явствует из алгоритма, целевая функция W(x) должна быть

дважды дифференцируема.

Пример 3.6.

Минимизировать W(x)=2x2+(16/x), положив x1=1.

W'(x) = dW(x)/dx = 4x-16/x2,

W"(x)= 4+(32/x3).

Итерация 1.

x1=1, W'(1)=-12, W"(1)=36, x2=1-(-12/36)=1.33

Итерация 2.

x2=1.33, W'(1.33)=-3.73, W"(1.33)=17.6, x3=1.33-(-3.76/17.6)=1.54

Итерации продолжаются до тех пор, пока не будет выполняться неравенство | W'(xk)| Ј e ,

 


 

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

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

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


 

3.2.5. Контрольные вопросы и задания

  1. Приведите математическую формулировку основной задачи безусловной однопараметрической оптимизации.
  2. В чем состоит свойство унимодальности функций и в чем заключается важное значение этого свойства при решении задач одномерной оптимизации?
  3. Сформулируйте условие, при выполнении которого метод полиномиальной аппроксимации может не привести к получению правильного решения.
  4. При реализации поисковых методов рекомендуется принимать решение об окончании поиска на основе проверок как величины разности значений переменной, так и величины разности значений целевых функций. Возможна ли ситуация, когда результат одной из проверок, указывает на сходимость к точке минимума, тогда как полученная точка в действительности минимуму не соответствует? Поясните ответ рисунком.


 

 

Бревно длиной в L м имеет форму конуса, диаметры оснований которого равны соответственно D и d м. Требуется автоматизировать процесс раскроя бревна для получения бруса квадратного поперечного сечения, ось которого совпадала бы с осью бревна и объем которого был бы наибольшим. Каковы должны быть размеры бруса (длина бруса может отличаться от длины бревна!)? Принять e = 0,001.

Вариант

D

d

Длина L

Метод поиска

1

0,37

0,12

5

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

3

0,48

0,15

6

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

5

0,35

0,09

7

метод Пауэлла

7

0,46

0,17

8

метод средней точки

9

0,56

0,23

9

метод хорд



 

А

Выреза-емый квадрат

 

L

 

 

 

 

 

 

 

 




Требуется автоматизировать процесс раскроя листа металла (рис.3.5) размером A х L м, из углов которого необходимо вырезать одинаковые квадраты так, чтобы согнув лист по пунктирным линиям, получить коробку наибольшей вместительности. Какова должна быть сторона вырезаемого квадрата? Принять e = 0,001.


Рис.3.5. Схема раскроя


Вариант

Ширина А

Длина L

Метод поиска

2

1,3

2,5

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

4

0,7

1,8

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

6

1,1

2,2

метод Пауэлла

8

1,6

1,8

метод средней точки

10

2

2

метод хорд





Начальная страница. Содержание
Введение    Цели и задачи     Методологические основы     Линейное программирование     Нeлинейное программирование     Нeлинейное программирование: Безусловная однопараметрическая оптимизация     Нeлинейное программирование: Безусловная многопараметрическая оптимизация    Нeлинейное программирование: Условная многопараметрическая оптимизация    Целочисленное и дискретное программирование     Динамическое программирование     Принятие решений в условиях неопределенности     Принятие многоцелевых решений     Марковские процессы принятия решений     Литература