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


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


49

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

В этом разделе рассмотрим две другие разновидности симплекс-метода: двойственный симплекс-метод и обобщенный симплекс-метод. В двойственном симплекс-методе решение задачи ЛП начинается с недопустимого, но лучшего, чем оптимальное, решения. Последовательные итерации этого метода приближают решение к области допустимости без нарушения оптимальности (точнее, "супероптимальности") промежуточных решений. Когда будет достигнута область допустимых решений, процесс вычислений заканчивается, так как последнее решение будет оптимальным. В обобщенном симплекс-методе комбинируются элементы прямого и двойственного методов. Начальное решение в этом методе будет и неоптимальным, и недопустимым. На последующих итерациях базисные решения могут быть как допустимыми, так и недопустимыми. На последней итерации решение должно быть и оптимальным, и допустимым (если, конечно, такое решение существует).

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

4.4.1. Двойственный симплекс-метод

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

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

Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:

небалисныед:

а„<0

где zy - с/ - коэффициент в z-строке симплекс-таблицы, соответствующий переменной хр аг1 - отрицательный коэффициент из симплекс-таблицы, расположенный на пересечении ведущей строки (соответствующей исключаемой переменной хг) и столбца, соответствующего небазисной переменной хг При наличии нескольких альтернативных переменных выбор делается произвольно. Отметим, что двойственное условие оптимальности гарантирует достижение оптимального решения.

Чтобы существовало начальное оптимальное ("супероптимальное") и недопустимое решение, необходимо выполнение двух условий.

1. Целевая функция должна удовлетворять условию оптимальности обычного симплекс-метода (см. главу 3).

2. Все ограничения должны быть неравенствами типа "<".

Второе условие можно удовлетворить простым умножением на -1 неравенств типа ">". Если есть ограничения в виде равенств, то эти равенства заменяются на два неравенства. Например, равенство хх + х2 = 2 эквивалентно двум неравенствам



хг + хг<2, x, + х2>2,

или лг, + х2<2, -jc, - jc2< -2.

После преобразования всех ограничений в виде неравенств типа "<" начальное недопустимое решение возможно тогда и только тогда, когда по крайней мере в одном неравенстве правая часть будет строго отрицательной. В противном случае двойственный симплекс-метод не применяется, поскольку возможное начальное решение уже оптимально и допустимо.

Пример 4.4.1

Дана следующая задача ЛП.

Минимизировать z = Злг, + 2х2

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

Зх, +x2>3, 4х, + Зх, > 6, х+х2< 3, xvx2>0.

Сначала первых два неравенства умножаются на -1, чтобы привести их к неравенствам типа "<". Начальная симплекс-таблица этой задачи имеет следующий вид.

Базис

Решение

Поскольку Zj - Cj < 0 для всех j= 1, 5, начальное базисное решение (х3 = -3, xt = -6, xs = 3) является оптимальным и недопустимым.

Двойственное условие допустимости указывает на переменную х4 (= -6) как на исключаемую из базиса. Теперь применим двойственное условие оптимальности для определения вводимой переменной. Для этого используем следующую таблицу.

Переменные

z-строка (q - Су) хд-строка, щ

z,-c.

Отношение

-3 -4

-2 -3

Приведенные отношения показывают, что вводимой переменной будет х2. Отметим, что переменные xf будут кандидатами на включение в базисное решение только тогда, когда коэффициент a4j будет строго отрицательным. По этому критерию переменные хъ, х4 и хъ не рассматриваются как кандидаты на включение в базис.



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

Базис

Решение

-1/3

-2/3

-5/3

-1/3

-1/3

-1/3

Отношение

"1/5

Последняя таблица показывает, что из базиса исключается переменная х3 и вводит-

ся хг В результате получаем следующую симплекс-таблицу.

Базис

*й хг

Решение

0 0

-1/5

-3/5

21/5

1 0

-3/5

0 1

-3/5

0 0

-1/5

Решение, представленное в последней таблице, допустимо (и оптимально), поэтому

вычисления заканчиваются. Это решение имеет вид

3/5, х2 = 6/5 иг = 21/5.

На рис. 4.2 показана последовательность шагов двойственного симплекс-метода при решении задачи из примера 4.4.1. Алгоритм начинается в крайней точке А (которой соответствует недопустимое, но "лучше, чем оптимальное" решение), затем он переходит к точке В (которой также соответствует недопустимое, но "лучше, чем оптимальное" решение) и заканчивается в точке С, уже принадлежащей области допустимых решений.

Программа TORA позволяет выполнять двойственный симплекс-метод в пошаговом режиме. Для этого -в меню SOLVE/MODIFY выберите команду SolveAlgeraic Iterations1 Dual Simplex (Решить1АлгебраическиИтерацииОДвойственный симплекс-метод). Помните, что сначала надо ограничения в виде равенств преобразовать в неравенства. Неравенства типа ">" преобразовывать в противоположные неравенства не нужно, поскольку TORA автоматически выполнит преобразование задачи к виду, необходимому для применения двойственного симплекс-метода. Если задача не удовлетворяет начальным требованиям для применения двойственного симплекс-метода, то на экране появится соответствующее сообщение. Как и в обычном симплекс-методе, здесь в пошаговом режиме TORA позволяет вручную указывать вводимые и исключаемые переменные.

УПРАЖНЕНИЯ 4.4.1

1. На рис. 4.3 показано пространство решений, соответствующее задаче минимизации целевой функции z = 2х, + х2. Предполагается, что поиск решения выполняется двойственным симплекс-методом; оптимальное решение соответствует точке F - (0,5, 1,5).

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