- •Методические указания для выполнения контрольной работы
- •«Математическое программирование»
- •Введение
- •§ 1. Экстремум функции одной переменной
- •§ 2 Локальные и глобальные экстремумы функции нескольких переменных.
- •§ 3 Условный экстремум. Метод множителей лагранжа
- •§ 4 Постановка задачи линейного программирования. Графический метод решения.
- •Геометрическая интерпретация злп.
- •Графический метод решения.
- •§ 5 Симплекс-метод решения задач линейного программирования
- •§ 6 Транспортная задача
- •Литература
- •Методические указания для контрольной работы
§ 3 Условный экстремум. Метод множителей лагранжа
Определение 3.1. Функция ƒ(P)=ƒ(x1,…,xn) имеет условный максимум (условный минимум) в точке P0 (х1º,…, хºn), если существует такая окрестность точки P0, для всех точек P которой (Р ≠ P0), удовлетворяющих уравнениям связи
φκ(Р)=φκ(х1,…,хп)= 0, κ= 1,2,..,m; m<n
выполняется неравенство ƒ (Ро) >ƒ (P) ( соответственно ƒ (Ро) <ƒ (P)).
Задача нахождения условного экстремума сводится к исследованию на обычный экстремум функции Лангранжа
L φκ (x1,…,хп),
где λκ (k=1,2,…,m) называются множителями Лангранжа. Необходимые условия условного экстремума выражаются системой (n + m) уравнений
Решая эту систему, получим некоторые наборы чисел
х1,…, хn, λ1,…,λm, где х1,…хn – координаты точки, в которой возможен условный экстремум.
В частном случае функции z = ƒ (x, у) от двух переменных при одном уравнении связи φ (х,у) = 0 функция Лангранжа имеет вид
L (х,у,λ) = ƒ (х,у) + λ·φ (х,у).
Система состоит из трех уравнений:
φ (х,у)=0.
Пусть Ρ0(х0,у0), λ0– любое из решений этой системы. Здесь достаточное условие существования в точке Р0 условного экстремума можно сформулировать так. Обозначим ∆ (L) определитель
.
Тогда: если ∆<0, то функция z=ƒ(х,у) имеет в точке Р0(х0,у0) условный максимум; если ∆>0 – то условный минимум.
Задача 3.1. На развитие двух предприятий, входящих в производственное объединение., выделено 2 млн.руб. Если первому предприятию дадут х1 млн.руб., то прибыль, полученная от этого предприятия будет равна 2млн. руб; если х2 млн.руб. дадут второму, то прибыль от него будет равна 6млн.руб.
Как следует распределить средства между предприятиями, чтобы суммарная прибыль была максимальной? Решить задачу методом множителей Лагранжа.
Решение.
Задача состоит в отыскивании точки глобального максимума функции
у=2+6при ограничении: х1+х2=2,
Множество допустимых решений задачи является отрезок [A, B] (cм. рис.3.1)
Точку возможного максимума найдем методом множителей Лагранжа. Функция Лагранжа имеет вид:
L(х1,х2,λ)= 2
Для отыскания точек возможных экстремумов составим систему
Найдем ее решения. Из уравнений (1) и (2) получаем
–.
Подставляя найденное соотношение x2=9x1 в уравнение (3), получим x1+9x1–2=0, откуда x1 = , а поэтому x2 = 9x1 =, наконец .
Итак, система имеет одно решение
Исследуем найденную точку на локальный условный экстремум с помощью определителя
Так как – то – точка локального условного максимума.
Чтобы показать, что в этой же точке достигается и глобальный максимум, перейдем к задаче на отыскание безусловного максимума функции одной переменной. С помощью условия связи x1+x2=2 запишем целевую функцию в виде
. Требуется найти точку, где достигается наибольшее значение (глобальный максимум) функции одной переменной f(x1). Область возможного изменения оставшейся переменной – отрезок . Как известно из математического анализа, непрерывная функция на замкнутом отрезке обязательно достигает своего наибольшего и наименьшего значений либо в критических точках внутри отрезка, либо на его границах.
Ищем критические точки внутри отрезка
. Из условия f '(x1)=0 находим стационарную точку:== х1= . Точек, где производная не существует, внутри отрезка нет.
Находим значения целевой функции на границах отрезка и в стационарной точке .
,
Так как > >,то наибольшее значение достигается в точке .
Итак, глобальный максимум достигается при млн. руб., млн. руб. при этом у = 4 млн. руб.