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


[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


113

при ограничениях

YA>C,

Y - вектор свободных переменных (т.е. не имеющих ограничений в знаке). УПРАЖНЕНИЯ 7.5.1

1. Докажите, что задача, двойственная к двойственной задаче, совпадает с исходной (прямой) задачей.

2. Пусть прямая задача имеет вид: минимизировать z = {СХ АХ > b, X > 0}. Сформулируйте соответствующую двойственную задачу.

7.5.2. Оптимальное решение двойственной задачи

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

Теорема 7.5.1. Первая теорема двойственности. Для любой пары допустимых решений (X, Y) прямой и двойственной задач значение целевой функции в задаче минимизации ограничивает сверху значение целевой функции в задаче максимизации. Для пары оптимальных решений (X*, Y ) значения целевых функций совпадают.

Доказательство. Пара допустимых решений (X, Y) удовлетворяет всем ограничениям обеих задач. Умножая слева обе части ограничений задачи максимизации на вектор (свободных) переменных Y, получим

YAX = Yb = ш.

Аналогично, умножая справа ограничения задачи минимизации на вектор (неотрицательных) переменных X, будем иметь

YAX>CX = 2.

(Неотрицательность вектора X здесь существенна, так как определяет "направленность" неравенства.) Комбинируя последние два выражения, получаем неравенство z<w, доказанное для пары любых допустимых решений (X, Y).

Отметим, что теорема не указывает, какая задача прямая, а какая - двойственная. Это очень важно при нахождении оптимальных решений обеих задач.

Из доказанной части теоремы (z < w для пары любых допустимых решений) следует, что максимум функции z и минимум функции w будут достигнуты только тогда, когда обе эти функции примут одинаковое значение. Исходя из этого, можно построить оценку близости полученных допустимых решений к оптимальным путем сравнения разности 2 - w и величины (2 + w)/2. Чем меньше отношение 2(2 - w)/(z + w), тем ближе данные решения к оптимальным. Но, конечно, из этого эмпирического правила не следует, что оптимальные значения целевых функций равны (г + w)/2.

Если в одной из задач целевая функция примет бесконечное значение, что можно сказать о решении другой? Ответ очевиден: другая задача не должна иметь допустимых решений. Если это не так (т.е. обе задачи имеют допустимые решения), неравенство z < w обязательно должно выполняться, что невозможно, например,

При 2 = +оо или w = -<*>.

Рассмотрим обратную ситуацию. Если одна из задач не имеет допустимых решений, то обязательно ли решение другой задачи будет неограниченным? Не



обязательно! В следующем примере и прямая, и двойственная задачи не имеют допустимых решений.

Прямая задача. Максимизировать z = {х1 + х2 х1 - х2 <-1, ~х1 + х2 <-1, х„ х2>0}.

Двойственная задача. Минимизировать w = {-yt - у2 \ у, - у2> 1, -у, + у2 > 1,

Теорема 7.5.2. Оптимальное решение двойственной задачи равно

Y = CSB\

где В - оптимальный базис прямой задачи, которому соответствует вектор Св коэффициентов целевой функции.

Доказательство. Для доказательства этой теоремы надо показать, что допустимое решение двойственной задачи можно вычислить по формуле Y = СВВ , и что в соответствии с теоремой 7.5.1 z = w для оптимальных решений.

Решение прямой задачи будет оптимальным, если выполняются неравенства гу - су> О для всехj (см. раздел 7.2.1), т.е.

СВВ А - С > 0.

Но решение Y допустимо, если оно удовлетворяет ограничению YA > С. Это доказывает равенство Y = СВВ-1 для допустимого решения двойственной задачи Y.

Равенство оптимальных значений z и w доказывается непосредственным сравнением выражений

w = Yb = CBB Ь, zXCBb.

Переменные двойственной задачи Y= СВВ-1 иногда называют симплексными мультипликаторами. Они также известны как двойственные цены - название, идущее от экономической интерпретации этих переменных (см. раздел 4.3.1).

Обозначим через Ру у-й столбец матрицы А. Из теоремы 7.5.2 следует, что величины

zrcrCBV1VrcrW-ci

равны разностям между левыми и правыми частями ограничений двойственной задачи. В начале решения прямой задачи максимизации по крайней мере для одного j выполняется неравенство zt - с. < 0; это означает, что соответствующее ограничение YP. >с не удовлетворяется. Если достигнуто оптимальное решение прямой задачи, тогда выполняются неравенства z. - с; > 0 для всех /; в этом случае соответствующее решение двойственной задачи Y= СВВ~ допустимо. Таким образом, если решение прямой задачи оптимально, то решение двойственной задачи автоматически допустимо. На этом соотношении построен двойственный симплекс-метод (раздел 4.4), в котором вычисления начинаются с недопустимого решения, "лучшего", чем оптимальное. Выполнение метода продолжается до тех пор, пока не будет достигнуто допустимое решение. В противоположность этому в "обычном" симплекс-методе (глава 3) вычисления начинаются с допустимого, но "худшего", чем оптимальное, решения и продолжаются до тех пор, пока не будет достигнуто оптимальное решение.



Пример 7.5.1

В следующей задаче ЛП оптимальный базис равен В = (Р,, Р4). Сформулируем двойственную задачу и найдем ее оптимальное решение, используя оптимальный базис прямой задачи.

Максимизировать z = Зх, + Ъх2

при ограничениях

х, + 2х2 + х3 = 5, ~х1 + Зх2 + xt = 2,

Х - 0.

Двойственная задача имеет следующий вид.

Минимизировать w = 5(/, + 2у2

при ограничениях

У\~Уг - 3> 2(/, + 3(/2>5,

«/,.«/, поимеем В = (лс,, x4)r, тогда Св = (3, 0). Оптимальный базис и его обратная матрица равны следующему.

ч: з-ct)-

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

(x1,x/ = B-1b = (5, 7f,

((/l,y2) = CBB,=(3(0).

Оба решения допустимы и 2 = w = 15 (проверьте!). Таким образом, решения оптимальны.

УПРАЖНЕНИЯ 7.5.2

1. Проверьте правильность формулировки двойственной задачи в примере 7.5.1. Проверьте графически, что прямая и двойственная задачи не имеют недопустимых решений.

2. Дана следующая задача линейного программирования.

Максимизировать z = 50х, + 30 х2 + 10х3 при ограничениях

2хх + х2 1, 2х2 - -5, 4x, + x3 = 6, *„ х2, х3>0.

a) Сформулируйте и запишите двойственную задачу.

b) Покажите с помощью непосредственной проверки, что прямая задача не имеет допустимого решения.

[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]