Системы линейных неравенств. Зоркальцев В.И - 84 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

Составители: 

Рубрика: 

84
программирования являются задачи выпуклого программирования. Здесь
ограничимся рассмотрением задачи выпуклого программирования с
линейными ограничениями и дифференцируемой целевой функцией.
Пусть заданы: выпуклая дифференцируемая функция )(
x
f
от
вектора
n
R
x
∈
, матрица
A
размерности nm
×
и вектор
n
R
b
∈
.
Рассматривается задача поиска вектора
x
из условий
mi
n
)( →
x
f
, (22)
0, ≥
=
x
b
. (23)
Теорема 4. Для того чтобы вектор
n
R
x
∈
был оптимальным
решением задачи (22), (23), необходимо и достаточно выполнения двух
условий:
1) этот вектор должен быть допустимым решением задачи, т.е.
должен удовлетворять условию (23);
2) при некотором
n
R
u ∈ должны выполняться неравенства
)(,0),( xJjuxg
j
∈= , (24)
)(,0),(
0
xJjuxg
j
∈≥ , (25)
где
uAxfuxg
Τ
−∇= )(),(,
}0:{)( >=
j
xjxJ ,
}0:{)(
0
==
j
xjxJ .
При этом для векторов
x
, u выполняются равенства
( (),)( ,)(, )(,)
T
f
xx Aux uAx ub bu
Τ
∇= = ==. (26)
Доказательство. Для того чтобы вектор
x
, удовлетворяющий
условиям (23), был оптимальным решением, необходимо и достаточно,
чтобы не существовало направления, не выводящего из области
допустимых решений задачи (22), (23), при котором целевая функция
убывала, т.е. необходимо и достаточно, чтобы не существовало
n
R
s
∈
такого, что
0
=
A
s , (27)
)(,0
0
xJjs
j
∈≥
, (28)
0)),(( <∇ sxf . (29)
Неравенство (29) можно заменить на условия
0,0)),((
11
>
=
+
∇
++ nn
sssxf
,
где
1+n
s – дополнительная переменная. 
программирования являются задачи выпуклого программирования. Здесь
ограничимся рассмотрением задачи выпуклого программирования с
линейными ограничениями и дифференцируемой целевой функцией.
     Пусть заданы: выпуклая дифференцируемая функция f (x) от
вектора x ∈ R n , матрица A размерности m × n                    и вектор   b ∈ Rn .
Рассматривается задача поиска вектора x из условий
                               f ( x) → min ,                                 (22)
                              Ax = b, x ≥ 0 .                                 (23)
      Теорема 4. Для того чтобы вектор x ∈ R n был оптимальным
решением задачи (22), (23), необходимо и достаточно выполнения двух
условий:
      1) этот вектор должен быть допустимым решением задачи, т.е.
      должен удовлетворять условию (23);
      2) при некотором u ∈ R n должны выполняться неравенства
                            g j ( x, u ) = 0, j ∈ J ( x) ,     (24)
                              g j ( x, u ) ≥ 0, j ∈ J 0 ( x) ,                (25)
где
                                   g ( x, u ) = ∇f ( x) − AΤu ,
                                   J ( x) = { j : x j > 0} ,
                                   J 0 ( x) = { j : x j = 0} .
При этом для векторов x , u выполняются равенства
             (∇f ( x), x) = ( AT u , x ) = (u , Ax ) = (u , b) = b Τ u . (26)
      Доказательство. Для того чтобы вектор x , удовлетворяющий
условиям (23), был оптимальным решением, необходимо и достаточно,
чтобы не существовало направления, не выводящего из области
допустимых решений задачи (22), (23), при котором целевая функция
убывала, т.е. необходимо и достаточно, чтобы не существовало s ∈ R n
такого, что
                                   As = 0 ,                              (27)
                              s j ≥ 0, j ∈ J 0 ( x) ,                         (28)

                              (∇f ( x), s ) < 0 .                             (29)
Неравенство (29) можно заменить на условия
                             (∇f ( x), s ) + sn +1 = 0, sn +1 > 0 ,
где sn +1 – дополнительная переменная.



                                       84

Страницы