Пример 13.3. Приложение метода Свенна к задаче оптимального раскроя бревна на брус.

W(l)=(l /2)(d _k -(d _k- d _o) l / l _o)² ® max, при l _o=0,10, |D|=0,01, d _k =0,22, d _o =0,12.

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

W(12)=0,06;

W(12+1)=0,05265;

W(12-1)=0,06655.

Выполняется условие W(l_o-|D|)³W(x)³W(l_o+|D|), следовательно, D имеет отрицательное значение; l^*=12.

l₁=l_o-2⁰D = 11;

l₂=l₁-2¹D = 9, W(7)=0,07605 > W(l₁) Þ x^*<9;

l₃=l₂-2²D = 5, W(5)=0,07225 < W(l₂) Þ x^*>5;

Искомый интервал 5<l^*<9.

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

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

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

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

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

Шаг 3.

1. Если W(x₁)<W(x_m), то исключить (x_m,b], т.е. b=x_m, x_m=x₁. Перейти к шагу 5.

2. Если W(x₁)³W(x_m), то перейти к шагу 4.

Шаг 4.

1. Если W(x₂)<W(x_m), то исключить [a,x_m), т.е. a=x_m, x_m=x₂. Перейти к шагу 5.

2. Если W(x₂)³W(x_m), то исключить [a,x₁) и (x₂,b], т.е. a=x₁, b=x₂. Перейти к шагу 5.

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

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

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

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

. Учитывая, что z1+z2=z, имеем	W(x)		z
z12=z z2 = (z1+z2)z2 = z1z2 + z22;		z1	z2
z1z2 + z22 - z12 = 0,
откуда .
	a		b	x
Рис. 13.2. Определение коэффициента дробления

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

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

k=( - 1)/2.

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

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

Шаг 4.

1. Если |x₂-x₁|£e, где e - заданная погрешность, то x_m = (x₁+x₂₎/2, вычислить W(x_m) и закончить поиск.

2. Если |x₂-x₁|>e, то перейти к шагу 5.

Шаг 5.

1. Если W(x₁)>W(x₂), то исключить a=x₁, x₁=x₂ и W(x₁)=W(x₂). Перейти к шагу 3, затем к шагу 4.

2. Если W(x₁)£W(x₂), то b=x₂, x₂=x₁ и W(x₁)=W(x₂). Перейти к шагу 2 и 4.