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

Метод последовательного изменения аргументов (координат)

 

Пусть необходимо найти при условиях

 

Воспользуемся для этого следующим алгоритмом:

1. Выбираем начальную точку , удовлетворяющую системе ограничений ), определяем .

2. Даём приращение –й координате:

(приращение получает лишь одна координата, начинаем изменение координат с первой по порядку: ).

3. Проверяем, принадлежит ли области допустимых решений, если да, то переход к п. 4, иначе к п. 7.

4. Определяем .

5. Если , то и и делаем следующее приращение выбранной координаты .

Далее выполняем п.п.3,4,5, пока не окажется, что при дальнейшем увеличении –й координаты целевая функция возрастать уже не будет. Переход к п.7.

6. Если при первом приращении –й координаты окажется, что или , то рассматриваем приращение , далее аналогично п.п. 3,4,5.

7. После того, как прекратится увеличение при изменении –й координаты (или если такого увеличения получить не удалось), то переходим к изменению координаты, аналогично п.п. 3,4,5.

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

Рассмотрим пример 16.

при условии

I итерация.

1. Выбираем начальную точку

2. Даем приращение х₁: ;

3. , т.е. ;

Так как новая точка удовлетворяет системе ограничений, переходим к п. 4.

4.

5. Сравниваем и , так как (6,25 >6), то ;

II итерация.

Переходим к пункту 2

2. делаем приращение для

,

3. т.е. , переходим к пункту 4.

4.

5. Сравниваем и , так как (7 > 6,25), то

;

III итерация.

2. Делаем ещё одно приращение для ; , переходим к пункту 3.

3. , т.е. , переходим к пункту 4.

4.

5. Сравниваем и , так как (8,25 > 7), то

;

IV итерация.

2. Делаем ещё одно приращение для ;, ,

переход к пункту 3.

3. , т.е. , переходим к пункту 4.

4.

5. Сравниваем и , так как (10 > 8,25), то

;

V итерация.

2. Делаем ещё одно приращение для ; ,

переходим к пункту 3.

3. , так как , то переходим к пункту 4.

4. , т.е. начальную точку и значение целевой функции не меняем и переходим к пункту 7.

VI итерация.

7. Переходим к изменению второй координаты:

, ,

переход к пункту 3.

3. , т.е. , переходим к пункту 4.

4.

5. Сравниваем и , так как (10,25 > 10), то ; .

VII итерация.

2. Делаем ещё одно приращение для

,

,

3. , т.е. , переходим к к пункту 4.

4.

5. Сравниваем и ,

так как (11 > 10,25), то ;

VIII итерация.

2. Делаем ещё одно приращение для x₂:

,

, переход к пункту 3.

3. , так как , то переходим к пункту 4.

4. , т.е. начальную точку и значение целевой функции не меняем и переходим к пункту 7.

IX итерация.

7. Переходим к изменению первой координаты:

2.

, переход к пункту 3.

3. , т.е. , переходим к пункту 4.

4.

5. Сравниваем и , так как (13,25 > 11), то

;

X итерация.

2. Делаем ещё одно приращение для

, переход к пункту 3.

3. , т.е. , переходим к пункту 4.

4. .

5. Сравниваем и , так как (16 > 13,25), то ; , переходим к пункту 2

XI итерация.

2. Делаем еще одно приращение первой координаты:

x₁¹ = x₁⁰ +Dx = 3+ 0,5 = 3,5

.

Переход к пункту 3.

3. (3,5; 1),так как. , то переходим к пункту 7.

7. Все координаты исчерпаны, заканчиваем процесс вычислений, считая, что X *= ,

Заключение. Данный алгоритм может быть использован как для нахождения условного, так и безусловного экстремума. В последнем случае исключается пункт 3. (проверка новой точки на принадлежность ОДР).

Индивидуальные задания 4

Найти экстремум функции при заданных ограничениях методом последовательного изменения координат, выбрав одну из начальных точек и задав приращение координат по указанию преподавателя (Dx=0,1 ÷1).

1. Найти

при условиях

2. Найти

при условиях

3. Найти

при условиях

4. Найти

при условиях

5. Найти

при условиях

6. Найти

при условиях

7. Найти

при условиях

8. Найти

при условиях

9. Найти

при условиях

10. Найти

при условиях

11. Найти

при условиях

12. Найти

при условиях

13. Найти

при условиях

14. Найти

при условиях

15. Найти

при условиях

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

Индивидуальные задания 5

Решить задачи 1-15 индивидуального задания 4 с точностью ε = 0,05 и приращением .

Градиентные методы

Метод наискорейшего подъема (для самостоятельного изучения)

Рассмотрим случай поиска безусловного экстремума выпуклой функции max F=Z(X)

1.Выберем произвольную начальную точку

2.Подсчитаем значение функции Z() и вектора (в данной точке)

3.Осуществляем движение в направлении градиента, т.е. определяем координаты новой точки , исходя из условия:

Этой формуле соответствует n координатных равенств:

x₁ = ()

 

x₂ = ()

…………………………

x_n = ()

4.Подсчитываем значение целевой функции в точке :

Z( =Z(t)

(Z(t) получаем при подстановке в функцию Z)

5.Определяем число , т.е. такое значение t, при котором Z(t) достигает максимума:

= 0, отсюда находится

1. Полагаем и , если значения функции в новой точке оказалось больше, чем в начальной , т.е. при условии:

Z()= заменить Z() на Z().

Далее переходим к пункту 2.

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

 

Рассмотрим пример

Найти max z =

Выбираем начальную точку

I| итерация.

1. Подсчитаем Z и

Z = -

= (-2х₁;-х₂)

=(-2;-1)

2. Осуществляем движение по градиенту:

3. Z(t)=Z( = - (1-2t) - 0,5(1-t) = - (1-4t+4t ) – 0,5(1-2t+t ) = - 4,5t +5t –1,5

-9t+5=0→ = 5/9 ≈ 0,55

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

∂²Z/∂t² = -9 < 0, т.е. в точке - максимум.

6. Вычислим Z(t*):

Z(t*) = - 4,5∙(5/9) + 5∙(5/9) -1.5≈ - 4,25ּ25/81 + 25/9-1,5=

= - 1,3887 +2,78 - 1,5= - 0,1087» - 0,11;

Z(t*) > Z(); (- 0.11 > -1,5); т.е. примем точку за начальную , подставив в координатные равенства найденные значения

(1-2·t; 1-t); (1-2·0,55; 1-0,55); (-0,1; 0,45)→ = (-0,1; 0,45).

Далее повторяются операции, выполненные на первой итерации, начиная с пункта 2.

II итерация.

2. Подсчитаем Z и

Z =Z(- 0,1; 0,45) = - (-0,1)² – 0,5×(0,45)² = - 0,01 - 0,5×0,2025 = = - 0,01 – 0,10125» - 0,11.

= (-2х₁;- х₂) = (- 2ּ(- 0,1); - 0,45)

=(0,2; - 0,45)

3. Осуществляем движение по градиенту:

x₁ = - 0,1 + 0,2t; x₂ = 0,45 – 0,45t;

4. Z(t)=Z( заменить на

Z(t)= - (- 0,1 + 0,2t) - 0,5(0,45 – 0,45t) =- (0,01 - 0,04t + 0,04t ) –

- 0,5×(0,2025 - 0,405t+0,2025t ) = - 0,01 + 0,04t - 0,04t - 0,10125+ +0,2025t - 0,10125t = - 0,14125t + 0,2425t – 0,11125» - 0,14t + 0,24t – 0,11.

3. Находим max Z(t): = - 0,28t+0,24; → = 0; →

- 0,28t+0,24 =0→ ≈ 0,86.

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

∂²Z/∂t² = - 0,28 < 0, т.е. в точке - максимум.

6. Вычислим Z(t*):

Z(t*) = - 0,14×(0,86) +0,24×(0,86) –0,11= - 0,1035+0,2064 – 0,11 ≈ - 0,0071;

Z(t*) > Z(); (- 0,0071 > - 0,11); т.е. примем точку за начальную , подставив в координатные равенства найденные значения

x₁ = - 0,1 + 0,2t; x₂ = 0,45 – 0,45t;

(- 0,1 + 0,2t; 0,45 – 0,45t);

(- 0,1 + 0,2ּ 0,86; 0,45 – 0,45ּ 0,86);

(0,072; 0,063)→ = (0,072; 0,063).

Далее повторяются операции, выполненные на первой итерации, начиная с пункта 2.

Процесс продолжается до нахождения точки экстремума. Он может быть конечным, тогда в точке * grad Z( *)=0 и вычисления завершаются. А может оказаться, что найдено решение с некоторой точностью ε, т.е. приближенно. В последнем случае, если за определенное число шагов (итераций) решение не будет найдено, то оптимальным считается последнее из найденных.

Замечание. Название метода связано с тем, какой экстремум ищется в задаче: если максимум целевой функции, то метод наискорейшего подъема, если минимум целевой функции, то метод наискорейшего спуска.