назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [ 29 ] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


29

Обозначим х = {х,у), где 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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [ 29 ] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]