Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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



 

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

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

где gi и hj называются функциями ограничения. Если среди всех функций f, gi, hj имеется хотя бы одна нелинейная функция, то (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. определить характер экстремума стационарных точек.

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

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

и .

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

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

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

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

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

Lx = 1 + 2λx = 0;

Ly = 3 + 2λy = 0;

Lλ = x2 + y2 - 10 = 0;

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

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

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

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

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

φx(m0) = 2x; φy(m0) = 2y; Lxx = 2λ; Lxy = Lyx = 0; Lyy = 2λ.

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

.

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

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

.

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20 z = 2x + 8y при 2x2 + y2 = 20

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 




©2015 studopedya.ru Все права принадлежат авторам размещенных материалов.