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


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


44

Обратная матрица в оптимуме прямой задачи

Метод 1

. ( Вектор-строка исходных

I Оптимальные значения)

ч коэффициентов целевой функции

двойственных -

при базисных переменных

переменных )

{ в оптимуме прямой задачи Элементы в вектор-строке исходных коэффициентов целевой функции должны быть перечислены в таком порядке, в каком базисные переменные перечислены встолбце "Базис" в симплекс-таблице. Этот метод рассмотрен в примере 4.2.1.

Метод 2

Оптимальное решение двойственной задачи можно получить из следующего уравнения.

Коэффициент при j-й 4 переменной в z-строке прямой задачи

Разность между левой и правой4 частями j-то неравенства двойственной задачи

Поскольку двойственной к двойственной задаче будет прямая задача (проверьте!), эти методы симметричны относительно прямой и двойственной задач. Их можно использовать для определения оптимального решения одной задачи непосредственно из симплекс-таблицы, содержащей оптимальное решение другой. Данное обстоятельство обусловливает возможность проведения вычислений именно по той задаче (прямой или двойственной), которая требует меньших вычислительных ресурсов (меньший объем вычислений имеет задача с меньшим количеством ограничений). После нахождения оптимального решения решаемой задачи оптимальное решение обратной задачи определяется одним из описанных методов (см. упражнение 4.2.3.1).

Пример 4.2.1

Рассмотрим следующую задачу ЛП.

Максимизировать z = Ьхх + 12х2 + 4х3

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

х1 + 2х2+х3<10, 2хх -х2 + Зх3 = 8, хг,х2, х3>0.

Чтобы подготовить задачу к решению симплекс-методом, надо добавить дополнительную остаточную переменную xt в первое ограничение и искусственную переменную R во второе. В результате прямая задача и соответствующая ей двойственная будут определены следующим образом.

Прямая задача

Максимизировать г = 5xi +12хг + 4хз -MR при ограничениях

xi +2x2 + Хз + х4 = 10,

2х1-х2 + Зх3 + Я=8,

xiI *2, *3, Хд, Я> 0.

Двойственная задача

Минимизировать w= 10yi + 8уг при ограничениях yi + 2у2 > 5, 2у, -у2> 12, yi + Зу2 > 4,

yi > 0, уг > -М (уг - свободная переменная).



Итерация

Базис

Решение

-5-2М

-12 + М

-4-ЗМ

-7/3

-40/3

43 + М

32/3

-1/3

22/3

-1/3

-3/7

40 7

-43 + М

368/7

-1/7

22/7

26/7

-2/5 + М

274/5

-1/5

-1/5

12/5

26/5

Г2/5 -1/54!

Обратная матрица симплекс-таблицы с оптимальным решением имеет вид I j .

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

Метод 1. Заметим, что базисные переменные в оптимальной симплекс-таблице в столбце "Базис" записаны в таком порядке, что сначала идет х2, а затем хх. Поэтому в вектор-строке первоначальных коэффициентов целевой функции коэффициенты этих двух переменных должны идти в том же порядке:

(вектор коэффициентов) = (коэффициент при х2, коэффициент при хг) = (12, 5).

Оптимальное решение двойственной задачи вычисляется так:

(2/5 -\/5\

(у,, у2) = (вектор коэффициентов) х (обратная матрица) = (12,5) =(29/5,-2/5).

V V 2/5 J

Метод 2. Поскольку двойственная задача имеет две переменные, необходимо два уравнения, чтобы найти их значения. Сначала посмотрим, как ограничения двойственной задачи связаны с переменными х4 и R, составляющими первоначальный базис прямой задачи.

Переменная х4: у,>0, Переменная R: у2 > -М. Из симплекс-таблицы с оптимальным решением имеем

коэффициент в z-строке при xt = 29/5, коэффициент в z-строке при R = -2/5 + М. Теперь, следуя методу 2, получаем систему уравнений 29/5 = у,-0 => у, = 29/5,

-2/5+М = у2-(-М) у2 = -2/5.

В следующей таблице представлены симплекс-итерации решения прямой задачи.



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

Конечно же, ничего не мешает использовать другие переменные при построении уравнений, необходимых для определения значений переменных двойственной задачи. Например, ограничения, ассоциируемые с переменными хх и х3, порождают следующие уравнения (проверьте!):

у, + 2у2-5 = 0, у, + Зу2-4=.

Решение этой системы уравнений также приводит к оптимальным значениям двойственной задачи у, = 29/5 и у2 = -2/5. Однако эти уравнения уже не так просты, как уравнения, ассоциируемые с переменными xt и R. (Убедитесь самостоятельно, что уравнения, ассоциированные с любыми двумя переменными из множества xv х2, х3, xt, R, дают одни и те же значения переменных двойственной задачи.)

УПРАЖНЕНИЯ 4.2.3

1. С помощью программы TORA решите двойственную к следующей задачу ЛП и затем найдите оптимальное решение прямой задачи.

Минимизировать z = 5х, + 6х2 + Зх3

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

5*, + Ьх2 + Зх3 > 50, х, + хг - хг > 20, 7х, + 6х2 - 9х, > 30, 5х,+ 5х2 + 5х3>35, 2х, + 4х2- 15х3>10,

12х,+ юх2>90,

х2 - 10х3 > 20, х„ хг, х3>0.

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

Максимизировать z = Ьхх + 2хг + Зх3

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

х,+ 5х2 + 2Хз = 30, х, - 5х2 - 6х3 < 40, х„ х2, х3>0.

Оптимальное решение этой задачи удовлетворяет уравнению (получено из z-строки симплекс-таблицы)

z + 0х, + 23х2 + 7х3 + (5 + M)xt + 0х5 = 150,

где искусственная переменная х4 и дополнительная переменная х6 входили в начальное базисное решение. Запишите соответственную двойственную задачу и найдите ее оптимальное решение, исходя из приведенного уравнения.

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