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


[Старт] [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]


28

с = Ар,(4.16)

d>{b,p).(4.17)

Легко видеть, что если неравенство {c,x)<d является неотрицательной линейной комбинацией неравенств системы (4.12), то

Ax<b{c,x)<d .

В дальнейшем нам понадобится результат, являющийся одной из формулировок леммы Фаркаша, который мы сформулируем без доказательства [6].

Теорема 4.1. Имеет место следующая альтернатива: либо система уравнений Ау = с имеет неотрицательное решение, либо имеет решение

система неравенств < О, (с,х) > О.

Рассмотрим несколько очевидных соотношений. Пусть Р = (А»Р2»-Рт) неотрицательный вектор, /?,>0, / = 1,...,т.

Умножив/-е равенство системы (4.12) на число р получим:

Pi ( /11 + /22 + - +) Ргг •(4-18)

Просуммируем полученные неравенства по / = l,...,/w :

т пт

(4.19)

;=/ 7=1/=1

Так как число X ijXj представляет собой компоненту вектора Ах, то

формулу (4.19) можно записать в более компактной форме:

{р,Ах)<{р,Ь).(4.20)

Поскольку

{р,Ах) = {Ах,р),(4.21)

то при р>0 т неравенства Ах<Ь вытекает:

{Ар,х)<{р,Ь).(4.22)

Обозначим через Y множество планов двойственной задачи (4.4)-(4.6).



Лемма 4.1. Пусть хеХ, уеУ - произвольные допустимые решения прямой (4.1)-(4.3) и двойственной (4.4)-(4.6) задачи. Тогда

{с,х)<{Ь,у).(4.23)

Доказательство. Поскольку хеХ ,то Ах<Ь. Умножив это неравенство на вектор >>0 из (4.20) и (4.22), получим

{с,х) = {Ау,х) = {у,Ах)<{у,Ь).

Лемма 4.2. Пусть х* еХ, у* е¥ - допустимые решения задач (4.1)-(4.3); (4.4)-(4.6) соответственно. Если (с,х* = (ь,у*, то х* - оптимальное решение задачи (4.1)-(4.3); у* - оптимальное решение задачи (4.4.)-(4.6).

Доказательство. Пусть хеХ - допустимое решение задачи (4.1)-(4.3).Тогда по лемме 4.1 (с,х)<(ь,у* = (с,х*, т.е. х* - оптимальное решение задачи (4.1)-(4.3). Если yeY - допустимое решение задачи (4.4)-(4.6), то также учитывается утверждение леммы 4.1 (b,y)>(c,x* = (b,y* и следовательно, у* - оптимальное решение задачи (4.4)-(4.6).

Легко видеть, что лемма 4.2 дает достаточное условие оптимальности решение прямой двойственной задачи.

Основу теорем двойственности составляют две теоремы. Одна из них называется первой теоремой двойственности, вторая - теоремой равновесия.

Кроме достаточного признака оптимальности взаимодвойственных задач, существуют и другие важные соотношения между их решениями. Ответ на вопрос о взаимной разрешимости двойственных задач дает следующая теорема [47].

Первая теорема двойственности. Если взаимодвойственные задачи (4.1)-(4.3) (4.4)-(4.6) имеют непустое множество допустимых решений, то они имеют оптимальные решения, значения которых совпадают.

Доказательство. Пусть каждая из задач (4.1)-(4.3) и (4.4)-(4.6) имеет непустое множество допустимых решений и у eY - произвольное допустимое решение (план) задачи (4.4)-(4.6).

Тогда по лемме 4.1 целевая функция (с,х) ограничена на множестве X

числом (fe, у). Отсюда учитывая, что множество решений задачи 92



(4.1)-(4.3) йе пусто и ограничено, следует, что она имеет оптимальное ре-

шение X*.

Рассмотрим в пространстве R" систему линейных уравнений

Ау = с(4.24)

(й,>;) = (с,/).(4.25)

Если вектор у* неотрицателен и является решением системы (4.24)-(4.25), то

1)- допустимое решение задачи (4.4)-(4.6), так как у >0, Ау*=с;

2)у* - оптимальное решение задачи (4.4)-(4.6), так как (ь,У* = (с,х*,аэто согласно лемме 4.2 является достаточным условием оптимальности

3)оптимальные значения (с,х* 6,>* задач (4.1)-(4.3) и (4.4)-(4.6)

совпадают.

Таким образом, для доказательства теоремы двойственности остается показать, что система (4.24)-(4.25) имеет неотрицательное решение.

Запишем эту систему в матричном виде. Пусть А =

с

, тогда

Ау = с(4.26)

- запись системы уравнений (4.24), (4.25) в новых обозначениях.

Допустим, что система (4.26) не имеет неотрицательных решений. В этом случае, согласно теореме 4.1, имеет решение система неравенств

Ах<0, (с,х)>0.(4.27)

Здесь вектор х имеет размерность « +1 (в соответствии с тем, что у матрицы А = [А,Ь) имеется « +1 столбец)*.

[Старт] [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]