Практическое занятие № 9

Наименование работы: Решение задач нелинейного программирования методом множителей Лагранжа

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

Подготовка к занятию: Повторить теоретический материал по теме «Нелинейное программирование»

Литература:

1. Лобачева М.Е. Конспект лекций «Математические методы», 2013г.

2. Агальцов В.П. Математические методы в программировании, 2010г.

Перечень необходимых приборов, инструментов, материалов:ПЭВМ

Задание на занятие:

Решить двухмерную задачу минимизации целевой функции Z методом множителей Лагранжа и с помощью математической системы Mathcad. Сравнить результаты и сделать вывод.

Вариант	Целевая функция	Ограничения
1	Z = 6х1+ х12 + 4х2 + x22	х1 + 2х2 = 16 х1≥0, х2≥0
2	Z = 2х1+ х12 + 4х2 + x22	х1 + 2х2 = 10 х1≥0, х2≥0
3	Z = х12 + 4х2 + x22 - 6х1	х1 + х2 = 8 х1≥0, х2≥0
4	Z = 8х1+ х12 + 6х2 + x22	х1 + 2х2 = 12 х1≥0, х2≥0
5	Z = х12 - 4х1- 2х2 + x22	х1 + х2 = 6 х1≥0, х2≥0
6	Z = 14х1+ х12 + 10х2 + x22	х1 + х2 = 7 х1≥0, х2≥0
7	Z =х12 - 12х1- 14х2 + x22	2х1 + х2 = 7 х1≥0, х2≥0
8	Z = х12 - 6х1-10х2 + x22	х1 + х2 = 3 х1≥0, х2≥0
9	Z = х12 - 18х1-12х2 + x22	4х1 + х2 = 16 х1≥0, х2≥0
10	Z = х12 - 12х1-12х2 + x22	х1 + х2 = 5 х1≥0, х2≥0

Порядок проведения занятия:

1. Получить допуск к работе.

2. Выполнить задание в соответствии со своим вариантом.

3. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;

2. Выполненное задание;

3. Выводы по результатам выполненного задания;

4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

1. Перечислите методы решения задач нелинейного программирования.

2. Опишите порядок решения задачи нелинейного программирования методом множителей Лагранжа.

ПРИЛОЖЕНИЕ

Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия отрицательности переменных и и - функции, непрерывные вместе со своими частными производными (по крайней мере, вторая частная производная должна быть непрерывной).

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

,

находим частные производные ии рассматриваем системууравнений (здесь привлечём необходимое условие экстремума, заключающееся в том, что первая производная должна быть равна):

с m+nнеизвестными. Всякое решение системы уравнений определяет точку, в которой может иметь место экстремум функции. Следовательно, решив систему, получают все точки, в которых функцияможет иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума (здесь привлекается достаточное условие экстремума – если вторая производная меньше нуля, то имеет место максимум, если больше нуля - минимум).

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

1. Составляют функцию Лагранжа.

2. Находят частные производные от функции Лагранжа по переменным иприравнивают их к нулю.

3. Решая систему уравнений, находят точки, в которых целевая функция может иметь экстремум.

4. Среди точек, подозрительных на экстремум, находят точки, в которых достигается экстремум, и вычисляют значения целевой функции в этих точках.

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

Пусть дана целевая функция Z = х₁²- 20х₁ - 20х₂+x₂² с ограничениями:

х₁ +х₂ = 11

х₁ ≥ 0,х₂ ≥ 0

Требуется минимизировать ЦФ.

Чтобы найти решение методом множителей Лагранжа, вначале следует сформировать функцию Лагранжа:

F(х_1, х_2, λ) = х₁² - 20х₁-20х₂ + x₂²+λ (11- х₁ - х₂ )

Затем найдем производные по х_1, х_2, λ:

dF/ dх₁ = 2х₁ - 20

dF/ dх₂ = 2х₂ - 20

dF/ dλ = 11 - х₁ - х₂

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

2х₁ - 20 = 2х₂ - 20

2х₁ - 2х₂ = 0

х₁ - х₂ = 0

х₁ + х₂ = 11

х₁ = 5.5

х₂ = 5.5

В ответ записываем значения х₁ = 5,5;х₂ = 5,5.

Решение с помощью Mathcadосуществляется аналогично заданию из практического занятия 7.