Обозначим х = {х,у), где xeR" , а у - число. Тогда система неравенств (4.27) может быть записана в виде
Ах-гь<0,(4.28)
(с,х) + г(с,х*)>0.(4.29)
Покажем, что данная система не может иметь решения [х,у). Умножим скалярно неравенство (4.28) на вектор у>0 - план задачи (4.4)-(4.6)
{у,Ах)г{у,ь)<0.(4.30)
Воспользовавшись равенствами (у,Ах)<{Ау,х) = (с,х) из (4.26) получаем {с,х)-\-у{ь,у)<0, что вместе с (4.29) дает г((с,х*-{ь,у)>0.
Так как, то у <0.
Поделив обе части неравенства (4.28) на положительное число -у, получим А<ь. Это означает, что вектор допустим для задачи (4.1)-(4.3). Так как х* - решение задачи (4.1)-(4.3), то с,""<с,х*, или {с,х) + у(с,х*<0, что противоречит (4.29). Таким образом, система (4.28), (4.29) не может иметь решений, и, следовательно, теорема двойственности доказана.
Теорема равновесия [2]. Пусть х* = (х*,Х2,...,х*) и
у* ={yUy*2,-,ym) - оптимальные решения прямой и двойственной задачи (4.1)-(4.3) и (4.4)-(4.6). Тогда если > О, то
ад+«/22+- + Л=/-(4.31)
Доказательство. Поскольку х* еХ,то Ах* <b. Умножим это неравенство скалярно на > О и получим (с, х* = (Ау*»* =
= (у\Ах*<(ь,у*У 94
Учитывая, что по теореме двойственности (с,х* = (Ь,у*, получим (у* ,Ax* = (b,y*Y Следовательно, (у*, -Ах + 6 = 0. Вектор г = -Ах* + b неотрицателен, так как Ах* < b. Рассмотрим скалярное
произведение (у\г) = ,У*г - /=1
Скалярное произведение (у ,г) = 2>/ может равняться нулю толь-ко в том случае, когда равенство y*ri = О выполняется для всех / = l,...,/w. Если >;*>0,то 0 = г; =(Ь-*) = йотсюда и выте-
кает утверждение теоремы.
Отметим, что решение задач (4.1)-(4.3) и (4.4)-(4.6) не обязательно единственно. В связи с этим обратим внимание на то, что в
теореме равновесия речь идет о любой паре решений х*, у* этих задач.
Рассмотрим следствия из теоремы двойственности.
Теорема 4,2. Если одна из симметричных взаимодвойственных задач имеет решение, то имеет решение и другая.
Доказательство, Допустим, одна из взаимодвойственных задач, например, (4.1)-(4.3), имеет оптимальное решение х*. Тогда возможны два случая:
а)множество допустимых решений Y задачи (4.4)-(4.6) - не пусто, и целевая функция {Ь,у) ограничена на нем снизу числом (с,х (согласно лемме 4.1) и, следовательно, задача (4.4)-(4.6) имеет оптимальное решение;
б)задача (4.4)-(4.6) не имеет допустимых решений. Тогда по теореме 4.1 имеет решение х система неравенств Ax<Q, (с,x)>0. Рассмотрим
вектор jc = X* + Зс. Ясно, что Ах<Ь, т.е. хеХ, При этом (с,х) = с,х* + (с,х) >с,х*, что невозможно. Следовательно, второй случай нереализуем и теорема доказана. Теорема 4.2. указывает, что имеются следующие возможности: а) обе задачи (4.1)-(4.3) и (4.4)-(4.6) имеют непустое множество допустимых решений, (а, следовательно, имеют оптимальное решение);
б)обе задачи (4.1)-(4.3) и (4.4Н4.6) не имеют допустимых решений;
в)одна задача имеет допустимые решения, а другая нет.
Приведем примеры, где видно, что все три возможности имеют место:
а)max(xi + Х2 ) min(4>i + 4у2)
2х,+Х2<4{2у,у2>\
х,+2х2<4 \>,+2>2>1
Xi>0, Х2>0 у,>0, У2>0
-(Уз-Уз) у(Уз-Уз)
Поскольку значения целевых функций прямой и двойственной задачи совпадают, то по лемме 4.2 х* и у* являются оптимальными решениями соответствующих задач:
б)max(xi +ЗХ2) min(3>l ~У2)
Х1-Х2 <з Ы-У2 1
-Xi+X2<-4 \->i+>;2>3 Xi>0, Х2>0 >;i>0, >2>0.
Обе задачи не имеют решений:
в)m ах х\min(3;i)
Х1-Х2 <1
у,=\ -у,=0
X, > О , Х2 > О 1 > 0.
Здесь прямая задача допустима, двойственная - нет, при этом значение целевой функции первой задачи неограниченно. В общем случае эта ситуация описывается следующей теоремой.
Теорема 4.3. Если одна из двойственных задач недопустима, а вторая - допустима, то целевая функция второй задачи неограниченна на допустимом множестве.
Доказательство. Пусть задача (4.4)-(4.6) недопустима, а допустимое множество задачи (4.1)-(4.3)- не пусто. Если предположить, что целевая функция (с,х) ограниченна на множестве X, то тогда задача
(4.1)-(4.3) имеет оптимальное решение, а следовательно, по теореме 4.2