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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим пример 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₁⁰ +x = 3+ 0,5 = 3,5

.

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

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

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

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