МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ

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

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru Пусть необходимо найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru при условиях

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru
МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru
МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

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

1. Выбираем начальную точку МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , удовлетворяющую системе ограничений МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ), определяем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru .

2. Даём приращение МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru –й координате: МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

(приращение получает лишь одна координата, начинаем изменение координат с первой по порядку: МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ).

3. Проверяем, принадлежит ли МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru области допустимых решений, если да, то переход к п. 4, иначе к п. 7.

4. Определяем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru .

5. Если МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , то МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и делаем следующее приращение выбранной координаты МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru .

Далее выполняем п.п.3,4,5, пока не окажется, что при дальнейшем увеличении МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru –й координаты целевая функция МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru возрастать уже не будет. Переход к п.7.

6. Если при первом приращении МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru –й координаты МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru окажется, что МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru или МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , то рассматриваем приращение МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , далее аналогично п.п. 3,4,5.

7. После того, как прекратится увеличение МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru при изменении МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru –й координаты (или если такого увеличения получить не удалось), то переходим к изменению МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru координаты, аналогично п.п. 3,4,5.

Замечание. Имеется несколько вариантов этого алгоритма, которые отличаются друг от друга правилами изменения МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru в процессе счета и признаком конца поиска. Например, после каждого прохождения всех координат изменяется МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , конец вычислений определяется по условию МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru e, где e– сколько угодно малое число, задающее точность алгоритма.

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

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условии МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

I итерация.

1. Выбираем начальную точку МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

2. Даем приращение х1: МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ;

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

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (6,25 >6), то МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

II итерация.

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

2. делаем приращение для МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (7 > 6,25), то

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

III итерация.

2. Делаем ещё одно приращение для МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 3.

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (8,25 > 7), то

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

IV итерация.

2. Делаем ещё одно приращение для МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; , МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

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

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (10 > 8,25 ), то

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

V итерация.

2. Делаем ещё одно приращение для МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

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

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , то переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. начальную точку и значение целевой функции не меняем и переходим к пункту 7.

VI итерация.

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

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

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

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (10,25 > 10), то МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru .

VII итерация.

2. Делаем ещё одно приращение для МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (11 > 10,25), то МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

VIII итерация.

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

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переход к пункту 3.

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , то переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. начальную точку и значение целевой функции не меняем и переходим к пункту 7.

IX итерация.

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

2. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переход к пункту 3.

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (13,25 > 11), то

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

X итерация.

2. Делаем ещё одно приращение для МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переход к пункту 3.

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 4.

4. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru .

5. Сравниваем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (16 > 13,25), то МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ; МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , переходим к пункту 2

XI итерация.

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

x11 = x10 +Dx = 3+ 0,5 = 3,5

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru .

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

3. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (3,5; 1),так как. МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , то переходим к пункту 7.

7. Все координаты исчерпаны, заканчиваем процесс вычислений, считая, что X*= МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

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

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

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

1. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

2. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

3. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

4. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

5. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

6. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

7. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

8. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

9. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

10. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

11. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

12. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

13. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

14. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

15. Найти МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

при условиях МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

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

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

Решить задачи 1-15 индивидуального задания 4 с точностью ε = 0,05 и приращением МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru .

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

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

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

1.Выберем произвольную начальную точку МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

2.Подсчитаем значение функции Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ) и вектора МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (в данной точке)

3.Осуществляем движение в направлении градиента, т.е. определяем координаты новой точки МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , исходя из условия:

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

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

x1 = МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru )

x2 = МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru )

…………………………

xn = МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru )

4.Подсчитываем значение целевой функции в точке МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru :

Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru =Z(t)

(Z(t) получаем при подстановке МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru в функцию Z)

5.Определяем число МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. такое значение t, при котором Z(t) достигает максимума:

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = 0, отсюда находится МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

1. Полагаем МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , если значения функции в новой точке МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru оказалось больше, чем в начальной МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , т.е. при условии:

Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru )= МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru заменить Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ) на Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ).

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

Рассмотренный выше алгоритм предполагает, что в некоторой начальной точке МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru определяется градиент и осуществляется движение по направлению градиента до тех пор, пока Z увеличивается. Полученная таким путем новая точка принимается за начальную и процесс продолжается.

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

Найти max z = МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

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

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

I| итерация.

1. Подсчитаем Z МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

Z МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = - МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = (-2х1;-х2)

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru =(-2;-1)

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

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

3. Z(t)=Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = - (1-2t) МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru - 0,5(1-t) МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = - (1-4t+4t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ) – 0,5(1-2t+t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ) = - 4,5t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru +5t –1,5

-9t+5=0→ МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = 5/9 ≈ 0,55

Проверим с помощью второй производной, будет ли точка МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru точкой экстремума:

2Z/∂t2 = -9 < 0, т.е. в точке МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru - максимум.

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

Z(t*) = - 4,5∙(5/9) МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru + 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( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ); (- 0.11 > -1,5); т.е. примем точку МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru за начальную МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , подставив в координатные равенства найденные значения

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (1-2·t; 1-t); МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (1-2·0,55; 1-0,55); МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (-0,1; 0,45)→ МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (-0,1; 0,45).

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

II итерация.

2. Подсчитаем Z МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru и МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

Z МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru =Z(- 0,1; 0,45) = - (-0,1)2 0,5×(0,45)2 = - 0,01 - 0,5×0,2025 = = - 0,01 – 0,10125 » - 0,11.

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = (-2х1;- х2) = ( - 2ּ( - 0,1); - 0,45)

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru =(0,2; - 0,45)

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

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru x1 = - 0,1 + 0,2t; x2 = 0,45 – 0,45t;

4. Z(t)=Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru заменить МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru на МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru

Z(t)= - (- 0,1 + 0,2t) МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru - 0,5(0,45 – 0,45t ) МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru =- (0,01 - 0,04t + 0,04t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ) –

- 0,5×(0,2025 - 0,405t+0,2025t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ) = - 0,01 + 0,04t - 0,04t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru - 0,10125+ +0,2025t - 0,10125t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = - 0,14125t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru + 0,2425t – 0,11125 » - 0,14t МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru + 0,24t – 0,11.

3. Находим max Z(t): МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = - 0,28t+0,24; → МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = 0; →

- 0,28t+0,24 =0→ МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ≈ 0,86.

Проверим с помощью второй производной, будет ли точка МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru точкой экстремума:

2Z/∂t2 = - 0,28 < 0, т.е. в точке МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru - максимум.

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

Z(t*) = - 0,14×(0,86) МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru +0,24×(0,86) –0,11= - 0,1035+0,2064 – 0,11 ≈ - 0,0071;

Z(t*) > Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru ); (- 0,0071 > - 0,11); т.е. примем точку МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru за начальную МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru , подставив в координатные равенства найденные значения

x1 = - 0,1 + 0,2t; x2 = 0,45 – 0,45t;

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (- 0,1 + 0,2t; 0,45 – 0,45t);

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (- 0,1 + 0,2ּ 0,86; 0,45 – 0,45ּ 0,86);

МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (0,072; 0,063)→ МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru = МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru (0,072; 0,063).

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

Процесс продолжается до нахождения точки экстремума. Он может быть конечным, тогда в точке МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru * grad Z( МЕТОДЫ ПОИСКА – МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ - student2.ru *)=0 и вычисления завершаются. А может оказаться, что найдено решение с некоторой точностью ε, т.е. приближенно. В последнем случае, если за определенное число шагов (итераций) решение не будет найдено, то оптимальным считается последнее из найденных.

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

Наши рекомендации