Элементы теории двойственности. Чернышова Г.Д - 9 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

9
Точка
0
x является базисной,
ú
û
ù
ê
ë
é
=
0
0
b
x
x , где bBx
b
1-
= . Пусть
B
– опти-
мальный базис, тогда оптимальность означает выполнение условий
0
1
³-=D
-
jj
T
bj
cABc , nj ,1=" .
Значит cyA
T
³
0
, то есть точка
0
y – допустимая в двойственной задаче.
Покажем теперь, что
0
y
– оптимальная точка в двойственной задаче.
Действительно, имеет место равенство
(
)
0010
ybbybBcxcxc
T
T
T
bb
T
b
T
====
-
.
По свойству 4 точка
0
y является оптимальной.
Теорема доказана.
Замечание.
Докажем теорему для задачи (1) – (3). Приведём задачу к канониче-
скому виду
max®xc
T
(1)
buAx
=
+
(2`)
0
,
³
x
u
(3`)
Двойственная к полученной задаче (1) – (2`) – (3`) записывается в виде:
min®yb
T
(4)
cyA
T
³ (5)
0
³
y
(6)
Задача (4) – (6) является двойственной для задачи (1) – (3). Поэтому,
если задача (1) – (3) имеет решение, то имеет решение (1) – (2`) – (3`),
а значит, и задача (4) – (6) и наоборот.
Следствие.
Совместность системы
(
)
является необходимым и достаточным ус-
ловием для решения исходной и двойственной задачи (если исходная запи-
сана в каноническом виде):
ï
ï
î
ï
ï
í
ì
=
³
³
=
ybxc
cyA
x
bAx
TT
T
0
. (
*
) 
                                                  �x �
    Точка x 0 является базисной, x 0 � � b � , где xb � B �1b . Пусть B – опти-
                                       �0 �
мальный базис, тогда оптимальность означает выполнение условий
                           � j � cbT B �1 A j � c j � 0 , �j � 1, n .
     Значит AT y 0 � c , то есть точка y 0 – допустимая в двойственной задаче.
     Покажем теперь, что y 0 – оптимальная точка в двойственной задаче.
Действительно, имеет место равенство c T x 0 � cbT xb � cbT B �1b � � y 0 � b � b T y 0 .
                                                                              T



По свойству 4 точка y 0 является оптимальной.
    Теорема доказана.
    Замечание.
    Докажем теорему для задачи (1) – (3). Приведём задачу к канониче-
скому виду

                                           c T x � max                               (1)
                                           Ax � u � b                               (2`)
                                             u, x � 0                               (3`)
     Двойственная к полученной задаче (1) – (2`) – (3`) записывается в виде:

                                           b T y � min                               (4)
                                             AT y � c                                (5)
                                                y�0                                  (6)
     Задача (4) – (6) является двойственной для задачи (1) – (3). Поэтому,
если задача (1) – (3) имеет решение, то имеет решение (1) – (2`) – (3`),
а значит, и задача (4) – (6) и наоборот.

     Следствие.
     Совместность системы ��� является необходимым и достаточным ус-
ловием для решения исходной и двойственной задачи (если исходная запи-
сана в каноническом виде):
                                          � Ax � b
                                          �x � 0
                                          �
                                          � T            .                   (�)
                                          �A y � c
                                          �c T x � b T y
                                          �


                                              9

Страницы