Раздел 3. Задачи условной оптимизации

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

при ограничениях (3.1)

где g_i и h_j называются функциями ограничения. Если среди всех функций f, g_i, h_j имеется хотя бы одна нелинейная функция, то (3.1) называется задачей нелинейного программирования. В противном случае это есть задача линейного программирования. Считая задачу (3.1) гладкой составим для нее функцию Лагранжа, зависящую от n+k+m переменных

:

(3.2)

где - вектор множителей Лагранжа для неравенств, а - вектор множителя Лагранжа для равенств.

В формулировке необходимых признаков применяется градиент функции L по x :

.Рассматриваются регулярные задачи, когда векторы линейно независимы.

Теорема (необходимое условие Куна-Такера). Пусть задача гладкая. Для того, чтобы точка была точкой локального минимума (максимума) в задаче (3.2) необходимо выполнение следующих условий:

1. стационарности: (3.3)

2. дополняющей нежесткости: (3.4)

3. неотрицательности: (3.5).

Причем все множители Лагранжа и одновременно не могут быть равны нулю.

С помощью условий этой теоремы можно составить следующий алгоритм решения задачи (3.2) , который называется методом множителей Лагранжа:

1. убедиться в существовании экстремальных точек (теорема Вейерштрасса и ее следствие);

2. составить функцию Лагранжа (3.2) ;

3. выписать все необходимые условия (3.3)-(3.5) ;

4. вычислить все стационарные точки, то есть найти все решения уравнений (3.2) ;

5. определить характер экстремума стационарных точек.

Оптимальному решению задачи соответствует (единственная) совокупность множителей Лагранжа. Поэтому для вычисления стационарных точек x⁰ из уравнения (3.3) требуется предварительно найти значения всех множителей Лагранжа. Таким образом, имеется всего n+k+m неизвестных . Для их нахождения (n - уравнений) присоединяют k- ограничений -неравенств и m - ограничений-равенств .

Введение функции Лагранжа, по существу, сводит задачу условной оптимизации к задаче безусловной оптимизации. Поэтому необходимые условия II порядка и достаточные условия для функции Лагранжа являются обобщениями соотношения:

и .

Пример решения

Найти условный экстремум функции Z = x + 3y при ограничении x² + y² = 10.

Составим функцию Лагранжа

L(x,y,λ) = x + 3y + λ*(x² + y² - 10) .

Определим первые производные от переменных и приравняем их нулю.

L_x^’ = 1 + 2λx = 0;

L_y^’ = 3 + 2λy = 0;

L_λ^’ = x² + y² - 10 = 0;

Определим значения переменных, удовлетворяющие системе из трёхуравнений.

x = - 1/(2λ); y = - 3/(2λ); 1/(4λ²) + 9/(4λ²) - 10 = 0; 1/λ² = 4; λ = ± ½;

Определим координаты двух точек для двух значений множителя λ.

Для λ = ½ x = -1; y = -3; m₀(-1,-3). Для λ = - ½ x = 1; y = 3; m₀(1,3).

Определим детерминант матрицы Гессе

φ_x^’(m₀) = 2x; φ_y^’(m₀) = 2y; L_xx^” = 2λ; L_xy^” = L_yx^’ = 0; L_yy^” = 2λ.

Для λ = ½ x = -1; y = -3; m₀(-1,-3) детерминант матрицы Гессе равен

.

Минимальное значение целевой функции Z_min = x + 3y = 1*(-1) + 3*(-3) = -10.

Для λ = ½ x = 1; y = 3; m₀(1,3) детерминант матрицы Гессе равен

.

Максимальное значение целевой функции Z_max = x + 3y = 1*(1) + 3*(3) = 10.

Варианты заданий

1 z = 2x + 4y при 2x² + y² = 15

2 z = 3x + 4y при 3x² + y² = 20

3 z = 4x + 5y при x² + 2y² = 10

4 z = 5x + 2y при x² + 3y² = 15

5 z = 2x + 3y при x² + y² = 20

6 z = 3x + 2y при 2x² + y² = 10

7 z = 4x + 3y при 3x² + y² = 15

8 z = 5x + 3y при x² + 2y² = 20

9 z = 7x + 5y при x² + 3y² = 25

10 z = 4x + 2y при x² + y² = 15

11 z = 5x + 6y при 2x² + y² = 20

12 z = 2x + 6y при 3x² + y² = 10

13 z = 3x + 5y при x² + 2y² = 15

14 z = 4x + 6y при x² + 3y² = 20

15 z = 5x + 7y при x² + y² = 10

16 z = 2x + 7y при 2x² + y² = 15

17 z = 3x + 6y при 3x² + y² = 20

18 z = 4x + 7y при x² + 2y² = 10

19 z = 5x + 8y при x² + 3y² = 15

20 z = 2x + 8y при 2x² + y² = 20

21 z = 3x + 7y при 3x² + y² = 10

22 z = 4x + 8y при x² + 2y² = 15

23 z = 5x + 9y при x² + 2y² = 20

24 z = 6x + 3y при 2x² + y² = 10

25 z = 7x + 3y при x² + 2y² = 15

26 z = 8x + 3y при x² + 2y² = 20

27 z = 9x + 3y при x² + 2y² = 25

28 z = 10x + 3y при x² + 2y² = 10

29 z = 2x + 9y при x² + 2y² = 15

30 z = 3x + 6y при x² + 2y² = 20

31 z = 4x + 7y при x² + 2y² = 25

32 z = 5x + 8y при x² + 2y² = 10

33 z = 6x + 9y при x² + 2y² = 15

34 z = 7x + 10y при x² + 2y² = 20

35 z = 2x + 9y при x² + 2y² = 25

36 z =8x + 3y при x² + 2y² = 10

37 z = 9x + 2y при x² + 2y² = 15

38 z = 2x + 4y при x² + 2y² = 20

39 z = 3x + 5y при x² + 2y² = 25

40 z = 4x + 6y при x² + 2y² = 10

41 z = 5x + 6y при x² + 2y² = 15

42 z = 6x + 6y при x² + 2y² = 20

43 z = 7x + 6y при x² + 2y² = 25

44 z = 8x + 9y при x² + 2y² = 10

45 z = 9x + 6y при x² + 2y² = 15

46 z = 2x + 6y при x² + 2y² = 20

47 z = 3x + 6y при x² + 2y² = 25

48 z = 4x + 5y при x² + 2y² = 10

49 z = 5x + 6y при x² + 2y² = 15

50 z = 6x + 6y при x² + 2y² = 20

51 z = 7x + 6y при x² + 2y² = 25

52 z = 8x + 6y при x² + 2y² = 15

Поиск по сайту: