1. Геометрический. При использовании геометрической интерпретации решение производится по алгоритму:
1. По системе (1) находят область Ω
2. Строят гиперповерхности вида ƒ(x1…xn)=h, h – произвольный параметр
3. Находят гиперповерхности наивысшего (наинизшего) уровня для задачи максимизации (минимизации). Общие точки области Ω и этой гиперповерхности – решение задачи. Если гиперповерхность наивысшего (наинизшего) уровня найти невозможно, то целевая функция неограничена сверху (снизу), т.е. задача максимизации (минимизации) не имеет решения.
Пример:
ƒ=x1*x2→ max x2
x1
Для того, чтобы изобразить область Ω, приведем первое неравенство системы ограничений к каноническому виду:
<=> <=>
-внешняя область плоскости относительно окружности с центром (-1;1) радиуса 4
- полуплоскость, расположенная левее и ниже прямой
x1*x2=h, т.е. x2=h/x1 – семейство гипербол.
Найдем точку пересечения гиперповерхности x1*x2=h и прямой x2=10-2x1;
- коэффициент угла наклона касательной к гиперповерхности, тогда k=-h/x2; составим и решим систему уравнений:
|
|
т.е. x1=2,5; x2=5, тогда αопт(2,5;5) ƒ(αопт)=12,5
При условии xi целочисленности рассмотрим
x1=2 → x2=6 → ƒ(αопт)=ƒ(2;6)=ƒ(3;4)=12
x1=3 → x2=4
2. Метод множителей Лагранжа применим, если система ограничений содержит только уравнения, и функции ƒi и gi непрерывны вместе со своими частными производными, то задача является задачей на условный экстремум и решается по алгоритму:
1. Рассматриваем дополнительную функцию Лагранжа, вводя набор дополнительных переменных λ1, λ2, … λm:
F(λi,xj)=ƒ(x1, x2, …, xn)+ λi (bi-gi (x1, x2, …, xn)).
2. Находим безусловные экстремумы функции F, которые являются решением задачи.
Пример. По плану производства предприятию необходимо изготовить 180 изделий, что возможно двумя способами, производственные функции затрат которых имеют вид 4x1+x12 и 8x2+x22; x1,x2 – объем продукции произведенных первым и вторым способами соответственно. Найти план производства с минимальными затратами.
Составим математическую модель задачи: x1+x2=180; xi≥0;
ƒ(x1,x2)= 4x1+x12+ 8x2+x22→min
Составим функцию Лагранжа: F=4x1+x12+ 8x2+x22+λ(180-(x1+x2))
Найдем стационарную точку функции F:
4+2x1+λ(-1)=0; 8+2x2+λ(-1)=0; 180-x1-x2=0.
Решив данную систему, получим
λ=186; х1=91; х2=89
ƒ экстремум есть и → ƒ(91,89)= min ƒ