1.2. Ограничения в виде неравенств
Рассмотрим общую задачу математического программирования: минимизировать функцию f(x) при наличии m ограничений gi(x) ? bi (i=1,2,…,m). Причем такие ограничения не ограничивают общности.
Ограничения в виде неравенств могут быть преобразованы в ограничения в виде равенств добавления к каждому из них неотрицательной ослабляющей переменной ui2 (переменная ui2 всегда положительна ):
gi(x) + ui2 = bi или gi(x) + ui2? bi = 0 (10)
Таким образом, задача сводится к минимизации функции f(x) при наличии m ограничений в виде равенства gi(x) + ui2 ?bi = 0. Сформируем функцию Лагранжа
F(x, ?, u) = f(x) + ?_(i+1)^m-?i[gi(x) + ui2 ? bi] (11)
Необходимыми условиями, которые должны выполняться в стационарной точке, являются следующие:
?F/?xj=0=?f/?xj + ?_(i=1)^m-?j (?g i)/?xj при j = 1,2,…,m, (12)
?F/??i=0= gi(x)+ui^2-bi=0 при i = 1,2,…,m, (13)
?F/?ui=0= 2?iui при i = 1,2,…,m. (14)
Умножив последнее уравнение на ui/2 , получим
?iui2 = 0, то есть ?i[bi ? gi(x)] = 0 i = 1,2,…,m (15)
Уравнения (12), (13) и (15) являются необходимыми условиями минимума в точке х* при наличии ограничений. Уравнения (13) являются повторной записью ограничений gi(x) ? 0. Уравнение (15) означает, что либо ?i = 0, либо bi-gi(x*) =0 . Если ?i ?0, то gi(x*) = bi и ограничений является активным и представляет собой ограничение в виде равенства. С другой стороны если ограничение является ограничениям в виде строгого неравенства gi(x*) ? bi , то соответствующий множитель Лагранжа ?i = 0.
Есть также дополнительное условие, которое должно быть выполнено в точке минимума при наличии ограничений, а именно ?i ? 0.
Предположим, что уравнения (12), (13) и (15) справедливы в точке (x*;?*;u*). Если фактический минимум функции при наличии ограничений z=f(x*),то можно рассматривать z как функцию от bi и изменения bi будут изменять ограничения и , таким образом, изменять саму функцию z. Покажем, что
?z/?bi = ??i*,
?z/?bi = ?_(j=1)^n-?f/?xj ?xj/?bi, (16)
где частные производные вычисляются в точке х*.
Поскольку gk(x)+uk2=bk , то
?gk/?bi=?_(j=1)^n-?gk/?xj ?xj/?bi = {-(0,если i?k@1,если i=k)+
Тогда
?z/?bi+?_(k=1)^m-??k ?gk/?bi=?z/?bi+?i= ?_(j=1)^n-?(?f/?xj+?_(k=1)^m-??i ?gk/?xj)?xj/?bi???
Но это выражение равно нулю в соответствии с уравнением (12). Таким образом
?z/?bi = ??i*,
С возрастанием bi область ограничений расширяется, что не может привести к увеличению значения z – минимума функции f(x), находящегося внутри области ограничений, а может лишь уменьшить его. Таким образом, ?z/?b ? 0, то есть, ?i ? 0.
Необходимые условия минимума функции f(x) при наличии ограничений gi(x*) ? bi (i =1,2,…m ) имеют такой вид, что можно найти х и ?, для которых
?f/( ?xj)+?_(i=1)^m-??i ?gi/?xj? = 0 при j=1,…,n,
gi(x)? bi при i=1,2,…,m;
?i[gi(x)-bi]= 0 при i=1,2,…,m;
?i ?0 при i= 1,2,…,m. (17)
