30. Нелинейное программирование. Методы решения задач.

Рассмотрим ЗНП и способы её решения. Математическая модель ЗНП в общем виде формулируется следующим образом:

f =(x₁,x_2, …,х_n) → min (max). При этом переменные должны удовлетворять ограничениям:

g₁(x₁,x_2, …,х_n) ≤b₁,

…………………………

g_m(x₁,x_2, …,х_n) ≤b_m,

g_m+1(x₁,x_2, …,х_n) ≥b_m+1,

…………………………

g_k(x₁,x_2, …,х_n) ≥b_k,

g_k+1(x₁,x_2, …,х_n)=b_k+1,

………………………

g_p(x1,x_2, …,х_n)=b_p.

x₁,x_2,…,х_n ≥0, где хотя бы одна из функций f, g_i нелинейная.

Для ЗЛП нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся метод множителей Лагранжа, градиентные методы, приближённые методы решения, графический метод.

Рассмотрим основные идеи графического метода.

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

Рассмотрим на примерах решение ЗНП.

1. Найти экстремумы функции L(x₁,x₂)=x₁+2x₂ при ограничениях

, .

Р

5

ешение. ОДР – это часть круга с радиусом 5, расположенная в I четверти. Найдём линии уровня функции L: x₁+2x₂=C. Выразим x₂= . Линиями уровня будут параллельные прямые с угловым коэффициентом, равным - . Минимум функции достигается в точке (0;0), L_min=0, т.к. градиент (1,2) направлен вверх вправо. Максимум достигается в точке касания кривой х₂= и линии уровня. Т.к. угловой коэффициент касательной к графику функции равен - , найдём координаты точки касания, используя геометрический смысл производной.

=- ; ( ) =- ;

=- ; x₀= ; x₂=2 .

Тогда L= +2∙2 =5 .

О твет: Минимум достигается в точке О(0;0), глобальный максимум, равный 5 , в точке А( ;2 ) .

2. Найти экстремумы функции L=(x₁-6)²+(x₂-2)² при ограничениях

x₁+x₂≤8

3 x₁+x₂ ≤15

x₁+x₂ ≥1

.

Решение. ОДР – многоугольник ABCDE. Линии уровня представляют собой окружности (x₁-6)²+(x₂-2)²=С с центром в точке О₁(6;2). Возьмём, например, С=36, видим, что максимум достигается в точке А(0;4), которая лежит на окружности наибольшего радиуса, пересекающую ОДР. L(A)=(0-6)²+(4-2)²=40. Минимум - в точке F, находящейся на пересечении прямой 3x₁+x₂ =15 и перпендикуляра к этой прямой, проведённого из точки О₁. Т.к. угловой коэффициент равен -3, то угловой коэффициент перпендикуляра равен . Из уравнения прямой, проходящей через данную точку О₁ с угловым коэффициентом , получим (x₂-2)= (x₁-6). Найдём координаты точки Е

х ₁-3х₂=0

3 x₁+x₂ =15.

Решив систему, получаем Е(4.5; 1.5).

L (E) = (4.5-6)²+ (1.5-2)²=2.5.

Ответ: Минимум, равный 2.5 достигается в точке (4.5; 1.5), максимум, равный 40, в точке (0;4).

3. Найти экстремумы функции L=(x₁-1)²+(x₂-3)²

при ограничениях , .

Решение: ОДР является часть круга, с центром в начале координат, с радиусом 5, расположенная в I четверти. Линии уровня – это окружности с центром в точке О₁ и радиуса С, т.к. (x₁-1)²+(x₂-3)²=С. Точка О₁ – это вырожденная линия уровня, соответствующая минимальному значению С=0. глобальный максимум достигается в точке А, лежащей на пересечении ОДР с линией уровня наибольшего радиуса. При этом

L(A)=(5-1)²+(0-3)²=25.

Ответ: Минимум, равный 0, достигается в точке (1;3),

Максимум, равный 25, - в точке А(5;0).

4. Предприниматель решил выделить на расширение своего дела 150 тыс.руб. известно, что если на приобретение нового оборудования затратить х тыс. руб., а на зарплату вновь принятых работников у тыс. руб., то прирост объёма продукции составит Q=0.001x^0.6·y^0.4 . Как следует распределить выделенные денежные ресурсы, чтобы прирост объёма продукции был максимальным.

Решение: Целевая функция имеет вид 0.001x^0.6·y^0.4 →max при ограничениях x+y≤150,

.

ОДР – треугольник. Линии уровня будут иметь вид 0.001x^0.6·y^0.4 =С. Выразив отсюда у, получим у= . Т.к. максимум достигается в точке касания линии уровня с ОДР, то условие касания имеет вид =-1. Найдя производную, получаем =-1. Выразив х, получим х= . у= = .

Ответ: Факторы х и у следует распределить в отношении 2:3.

5.Предприятие выпускает изделия А и Б, при изготовлении которых используется сырьё S₁ и S₂. Известны запасы b_i (i=1,2) сырья, нормы его расхода на единицу изделия a_ij (j=1,2), оптовые цены p_j на изделия и их плановая себестоимость с . Как только объём выпускаемой продукции перестаёт соответствовать оптимальному размеру предприятия, дальнейшее увеличение выпуска х_j ведёт к повышению себестоимости продукции b, в первом приближении фактическая себестоимость с_j описывается функцией с_j= с + с х_j, где с_j – некоторая постоянная. Все числовые данные приведены в таблице

b1	b2	a11	a12	a21	a22	p1	p2	с	с	с	с
90	88	13	6	8	11	12	10	7	8	0.2	0.2

Найти план выпуска изделий, обеспечивающий предприятию наивысшую прибыль в условиях нарушения баланса между объёмом и оптимальным размером предприятия.

Решение: Составим математическую модель задачи.

Пусть Z – прибыль, получаемая предприятием после реализации х₁ выпущенных изделий А и х₂ изделий Б.

Z=( 12-( 7+ 0,2 х₁)) х₁+( 10-( 8+ 0,2 х₂)) х₂ →max,

п ри ограничениях 13 х₁+ 6 х₂≤ 90,

8 х₁+ 11 х₂≤88_,

П реобразуя целевую функцию, получим:

Z=5х₁-0,2х +2 х₂-0,2х →max

ОДР – многоугольник ОАВD. Для построения линий уровня функции, приведём функцию к следующему виду:

(х₁-12,5)²+(х₂-5)²=181,25-5Z .

Л иниями уровня будут окружности с центром в точке О₁(12,5; 5) и радиуса . Окружность наибольшего радиуса будет проходить через точку М, находящейся на пересечении прямой ВD и прямой O₁М, перпендикулярной к BD. Найдём координаты точки М.

13х₁+ 6х₂=90

х₂-5=6/13(х₁-12,5). Решив систему, получим, М(6;2).

Z(М)=30-7,2-2,8+4=26.

Ответ: Для получения предприятием максимальной прибыли, составляющей 26 ден.ед., следует выпустить 6 ед. изделия А и 2 ед. изделия Б.