Расчетно-графическая работа №1 по дисциплине «Методы оптимизации и исследование операций»

Министерство общего и профессионального образования

Новосибирский Государственный Технический Университет

Расчетно-графическая работа №1

по дисциплине «Методы оптимизации

и исследование операций»

Решение задач нелинейного программирования

Вариант 57

Факультет: АВТ

Группа: АМ-010

Студент:

Преподаватель:

Новосибирск, 2003

Содержание

1.  Задание------3

2.  Реферат------3

3.  Решение условной задачи НЛП

3.1  Графический метод

3.2  Метод множителей Лагранжа

4.  Решение безусловной задачи НЛП-----5

4.1  Метод наискорейшего спуска

4.2  Метод Ньютона--7

4.3  Метод Нелдера-Мида------7

5.  Выводы-----10

Список литературы

1.  Задание

2.  Реферат

В данной работе содержится ровно 6 таблиц и 3 рисунка.

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

Целью данной работы является освоение методов решения условных и безусловных задач нелинейного программирования.

3.  Решение условной задачи НЛП

12x1 + 17x2 = -2

3.1  Графический метод

Ответ: X ≈ (-7,2; 5,1);

3.2  Метод множителей Лагранжа

₤= (x1 + 2)2 + (x+ λ (12x1 + 17x→ extr

ð ₤ / ðx1 = 2(x1 + 2) + 12 λ

ð ₤ / ðx2 = 2(x2 – 12) + 17 λ

ð ₤ / ðλ = 12x1 + 17x1 +2

2 x1 + 4 + 12 λ = 0

2x2 – 24 + 17 λ = 0

12x1 + 17x1 +2 = 0

x1 =λ

x2 = 12 – 8,5 λ

12λ) + 17(12 – 8,5 λ) +2 = 0

λ + 204 – 144,5 λ + 2 = 0

-216,5 λ = -182

λ = 0,84

x1 = -7,04

x2 = 4,86

Находим f11, f12, f21, f22

f11 = ð2 f(X0) / ðx12 = 2

f12 = 0

f21 = 0

f22 = 2

| 2 0 |

| 0 2 | > 0

f(x1, x2) выпуклая в точке X0 ≈ (-7,04; 4,86) – абсолютный минимум.

f(X0) ≈ 76,38

4.  Решение безусловной задачи

Z = f( x1, x2) = (xxx2 – 17) + (x2 – 17)2→ min

4.1  Метод наискорейшего спуска

x0 = (2a; 2b) = (10, 14).

ξ = 0,1

ðf / ðx1 = 2x1 - x2 – 13

ðf / ðx2 = 2x2 – x1 – 19

Градиент ▼f(x) = (2x1 - x2 – 13; 2x2 – x1 – 19)

Нормаль градиента ||▼f(x)|| = √(2x1 - x2 – 13)2 + (2x2 – x1 – 19)2

▼f(x) = – 13; 28 – 10 – 19) = (-7; -1)

xi+1 = xi - £ ▼f (xi) = (10; 14) - £ (-7; -1)

Найдем £ для нулевой итерации метода градиентного спуска методом золотого сечения:

Запишем уравнение через £:

f(x1, x2) = (10 + 7 £ - 1+ 7 £ - 15)(14 + £ -17)+ (14 + £ -17)2 =

= 43 £2 – 50 £ + 19 = φ(£)

a0 = 0; £ = 0,2 – начальное

φ(0,2) = 1,78 – 10 + 19 = 10,72

φ(0,4) = 3,87 – 20 + 19 = 5,88

φ(0,6) = 15,48 – 30 + 19 = 3,48

φ(0,8) = 27,52 – 40 + 19 = 6,52

Так как φ(0,6) < φ(0,8), то получаем интервал [0; 0,8]

λi = ai + c (bi - ai)

μi = ai + (1 – c) (bi - ai)

c = 0,38

1 – с = 0,62

£ = (λ5 + μ5)/2 = 0,55

Пример решения нахождения £ на первой итерации градиентного спуска:

f(£) = (13,85 - £ 0,1– (13,85 - £ 0,1,55 + £ 3,7+ (14,55 + £ 3,75 – 17)2 = (- 0,15 £ - 1,5)2 – (- 0,15 £ - 1,5)(3,75 £ - 2,45) + (3,75 £ - 2,45)2 =

= (- 0,15 £ - 1,5) – (-0,56 £2 – 3,95 £ + 2,82) + (3,75 £ - 2,45)2 → min

f| (£) = -0,3(-0,15 £ - 1,15) + 1,12 £ + 3,95 + 7,5(3,75 £ - 2,45) = 0

29,29 £ = 14,08

£ = 0,48

Ниже представлена геометрическая интерпретация.

Ответ: X ≈ (14,72; 16.92) с ξ = 0,5 f(X) ≈ 0.062

4.2  Метод Ньютона

x0 = (2a; 2b) = (10, 14)

ðf / ðx1 = 2x1 - x2 – 13

ðf / ðx2 = 2x2 – x1 – 19

Градиент ▼f(x) = (2x1 - x2 – 13; 2x2 – x1 – 19)

x = x0 – H-1(x) ▼f(x)

▼f(x0) = (-7; -1)

x = (10; 14) – (-5; -3) = (15; 17)

Ответ: X ≈ (15; 17) f(X) ≈ 0

4.3  Метод Нелдера-Мида

Начальные точки: x1 = (0; 0), x2 = (0; 12), x3 = (12; 0)

a)  £ = 1, β = 2, γ = 0.5 ξ = 0,1

Расчет первого итерации:

x1(1) = (0; 0), x2(1) = (0; 12), x3(1) = (12; 0)

f(x1(1)) = 259, f (x2(1)) = 175, f(x3(1)) = 247

Выбираем худшую и лучшую точки: xl = x2(1), xh = x1(1)

Рассчитываем центр тяжести: x4 =

f(x4(1)) = 103

Проверяем критерий останова:

1/3 * √1562 + 722 + 1442 = 74 > ξ

Делаем отражение: x5 =

f(x5(1)) = 19

Так как f(x5(1)) < xl (лучшей точки), то делаем растяжение: x6 =

f(x6(1)) = 7

Так как f(x6(1)) < xl, то заменяем худшую точку на точку x6 и переходим к следующей итерации (x6(1)→x1(2)).

б) £ = 1, β = 2, γ = 0.5, 5 итераций.

Ниже приведены таблицы, построенные для итераций а) и б)

Ответ: а) X ≈ (14.625; 16.875) c ξ = 0,1 f(X) ≈ 0.027

б) X ≈ (13.5; 16.5) c ξ = 1,4 f(X) ≈ 1.75

А)

Б)

Графики, поясняющие метод Нелдера-Мида.

Для случая а)

5. Выводы

В ходе выполнения работы были изучены методы решения условных и безусловных задач нелинейного программирования, а именно метод множителей Лагранжа, метод наискорейшего спуска, метод Нелдера-Мида, метод Ньютона. Решение одной из задач несколькими методами показывает то, что методы являются приближенными, так как ответы получаются разные. Решение проводилось с заданной погрешностью, так что полученные ответы не совпадают с точными.

Список литературы