Без ограничений и неотрицательность переменных
Начнем с изучения методов решения задач ВП без ограничений. Задача НП называется задачей без ограничений, если она не содержит условий, ограничивающих область изменений переменных. Такая задача имеет вид
Z = f (x1 ,x2 ,…, xn ) max.
(3.1) |
. . . ,
Точки, которые удовлетворяют условию (3.8),Ж называются стационарными. В общем случае система (3.8) может иметь множество решений. Система может быть сложной и ее решение не всегда возможно.
Для случая выпуклой (вогнутой) функции f система если имеет решения, то только одно. Оно будет доставлять функции f максимум, если f выпукла, доставлять минимум, если f вогнута.
Теперь рассмотрим вопрос о решении задачи выпуклого программирования в случае неотрицательности переменных.
(3.2) |
Z = f (x1 ,x2 ,…, xn ) max
xj ≥ 0 ; j=1,2,…,n,
где f (x1 ,x2 ,…, xn ) - выпуклая (вогнутая) функция, называется задачей ВП с неотрицательными переменными.
Сформулируем условия для определения наибольшего значения функции f в задаче(3.3). Внутри области (xj 0) необходимым условием экстремума является равенство нулю частных производных функции f :
=0. На границе области (xj = 0) частные производные удовлетворяют условию
≤ 0, если f вогнутая функция.
Примеры возможных решений задачи максимизации функции одной неотрицательной переменной иллюстрируют все возможные решения задачи в одномерном случае(рис.1-3). Если решение внутри области(x0 > 0), то производная =0 .Рассмотрим решение задачи максимизации функции f. Предположим, что ее решение x0 находится внутри области определения. В этом случае производная функции f в точке максимума x0 равна нулю. Данная ситуация отражена на рис. 1
y y y
fx'(x0)=0 ≤0
< 0
0 x0>0 x 0 x0=0 x 0 x0=0 x
рис. 1 рис. 2 рис. 3
Возможны также случаи расположения решения x0 на границе области. При нахождении наибольшего значения в этом случае производная функции f в точке x0 может быть неположительной (рис.2). Такая ситуация возникает при выпуклости максимизируемой функции. Производная функции f в точке x0 может быть и отрицательной (рис. 3).Это будет в случае, когда максимизируемая функция будет вогнутой.
Все случаи расположения решения x0 на границе области определения функции f можно обобщить в виде неравенства: ≤0.
Все эти случаи можно отразить в виде равенства нулю произведения x0 на ,то есть в виде равенства x0
= 0.
Следовательно, для одномерной функции необходимое условие экстремума
x0 = 0.
Аналогично рассуждая, можно сформулировать необходимое условие экстремума функции n переменных, оно будет иметь вид xj =0; j=1,2,…,n,
где xj ≥ 0, ≤ 0. Причем, если xj
0, то
=0, если, xj = 0, то
≤ 0.
Аналогичным будет подход и к решению задачи выпуклого программирования в случае ограничений в виде равенств.