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


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


30

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

Теорема 4.4. Пусть х =(хрХ2,...,х„), у ={у1,У2-Ут) допустимые планы задач (4.1)-(4.3) и (4.4)-(4.6) соответственно, при этом вьшолняется условие: если, у > О, то

ад +5)2X2 + ... + а,л =й,.(4.32)

Тогда X , у оптимальные решения соответствующих задач [49]. Доказательство, Из условия (4.32) вытекает, что {у. Ах) = {у,Ь), Поскольку {y,j4x)= {ЛУх) = с,х), получаем равенство (с, х) = (fe, у).

Применяя лемму 4.2, получаем утверждение теоремы.

Рассматривая экономический смысл теории двойственности, необходимо отметить следующее. План производства х* =(х*,Х2,...,х*) и набор

цен (оценок) ресурсов У* ={у1,У*2,-,Ут оказываются оптимальными

тогда и только тогда, когда прибьшь с выручки от продукции, найденная при «внешних» (заранее известных) ценах Ci,C2,...,C„, равна суммарным затратам на ресурсы по «внутренним» (определенным только по решениям задачи) ценам У1,У2,-,Ут • Д всех других планов задач х и > в соответствие с неравенством леммы 4.1 прибыль (выручка) от продукции меньше (или равна) затратам на ресурсы.

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

Для этого в систему ограничений (4.2) JaXj < i = l,...,/w следует ввести т неотрицательных переменных ,,+р„+2»-»,,+m в систему огра-

ничений (4.5) (2/,>/ Cj ,j = 1,.„,п) - п неотрицательных переменных

>m+P>w+2-»>m+,. системы ограничений каждой из взаимодвойственных задач примут вид:

YjOyXj + х„,. = Ь,, i = \,...,т,(4.33)

ТоуУ! - y„j = Cj, j = 1,...,и.(4.34)



Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи [25].

Таблица 4.2

Переменные исходной задачи I

Первоначальные

Дополнительные

x, ... xj ... х„

г г г г

Ут+\ Ут+2 "Ут+j "Ут+п

x„lx„,2-x„,j-x„, till

Ух Уг ••• yj - Уп,

Дополнительные

Первоначальные

Переменные двойственной задачи И

(4.35)

Теорема 4.5. Положительным (ненулевым) компонентам оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых

/ =и у = !,...,« : если Xj >0, то y*j = О , если x* >0, то у* =0 и

аналогично, если у* >0, то х*, = О; если ylj > О, то х* =0.

Доказательство. Выразим дополнительные переменные из системы ограничений прямой задачи (4.33) и двойственной задачи (3.41)

(4.36) (4.37)

Умножив каждое неравенство системы (4.36) на соответствующее >;- > О и складывая полученные неравенства, найдем:

/=1/=1/=17=1

(4.38)

Аналогично, умножая каждое неравенство системы (4.37) на соответствующее переменные х. > О и складывая полученные неравенства, найдем:

Ё Xjyrr,j = Z I Ci,jXjy -Ё CjXj. j=l/=iy=l7=1

(4.39)

Равенства (4.38) и (4.39) будут справедливы для любых допустимых значений переменных, в том числе и для оптимальных значений х*,



х*+1, у*, Ут+j- В силу первой теоремы двойственности получим: Xj = Y.b,y, , поэтому из записи правых частей (4.38), (4.39) следует,

у=1/=1

что они должны отличаться только знаком. С другой стороны, из неот-

рицательности выражений и Хл+уУу и ХуУт+у » входящих в выраже-

У=17=1

НИЯ (4.38) и (4.39), следует, что те же правые части этих неравенств должны быть неотрицательными.

Эти условия могут выполняться одновременно только при равенстве этих правых частей для оптимальных значений переменных нулю:

iw:=o,

(4.40)

В силу условия неотрицательности переменных каждое из слагаемых в равенствах (4.40) должно равняться нулю

ХпгУ] = 0 / = 1,...,W,

откуда и вытекает заключение теоремы.

Из доказанной теоремы следует важный вьшод о том, что введенное ранее соответствие (4.35) между переменными взаимодвойственных задач при достижении оптимальности (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения.

Рассмотренная теорема является следствием следующей теоремы.

Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через неосновные переменные ее оптимального решения.

Проиллюстрируем вторую теорему двойственности на следующем примере.

Пусть даны две взаимно двойственные задачи:

F = max(2x,+3jc2)(4.41)

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