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


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


36

Как и в А/-методе, сначала вычисляется новая r-строка по формуле новая r-строка = старая r-строка + 1 х /?,-строка + 1 х Л2-строка

Новая r-строка используется для решения задачи первого этапа, что приведет к следующему оптимальному решению (проверьте с помощью программы TORA, выполнив команду Iterations Two-phase Method).

Базис

«1

Решение

-1/5

-3/5

-4/5

Поскольку достигнут минимум г = О, значит, на первом этапе получено допустимое базисное решение х, = 3/5, хг = 6/5 и jr4 = 1. Искусственные переменные полностью выполнили свою "миссию", поэтому из последней таблицы можно удалить их столбцы. Переходим ко второму этапу.

Этап 2

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

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

с ограничениями

х, Н- х = - , 5 3 5

3 = 6 x3+xt = 1,

"1* *2* "3 "4 - *

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

Базис

Решение

-3/5

Поскольку базисные переменные хх и х2 имеют ненулевые коэффициенты в z-строке, эту строку следует преобразовать.

Новая z-строка = старая z-строка + 4 х х,-строка + 1 х х,-строка. Начальная таблица второго этапа примет следующий вид.



Базис

Решение

18/5

-3/5

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

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

Существует простое правило, которое гарантирует, что нулевая базисная искусственная переменная на втором этапе никогда не станет положительной.

1. Если в ведущем столбце коэффициент, соответствующий нулевой базисной искусственной переменной, положителен, тогда ведущий элемент определяется автоматически (поскольку ему соответствует минимальное отношение, равное нулю), и искусственная переменная на следующей итерации становится небазисной.

2. Если ведущий элемент равен нулю, следующая итерация оставляет искусственную переменную нулевой.

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

Итак, правило для второго этапа заключается в том, чтобы искусственные переменные оставлять в базисе всегда, когда коэффициент в ведущем столбце положителен или отрицателен. Фактически это правило применяется в конце первого этапа, когда из базисного решения удаляются нулевые искусственные переменные, перед тем как приступить ко второму этапу (см. упражнение 3.4.2.5).

УПРАЖНЕНИЯ 3.4.2

1. Ответьте на следующие вопросы.

a) Почему на первом этапе двухэтапного метода всегда минимизируется сумма искусственных переменных?

b) Если в задаче ЛП требуется найти максимум целевой функции, то следует ли на первом этапе максимизировать сумму искусственных переменных?



2. Для каждой задачи из упражнения 3.4.1.4 запишите соответствующую целевую функцию для первого этапа.

3. Решите задачи из упражнения 3.4.1.5 двухэтапным методом.

4. Покажите, что следующая задача не имеет допустимого решения. Запишите задачу ЛП для первого этапа и затем примените программу TORA для поиска ее решения.

Максимизировать z = 2х, + 5х2 при выполнении условий

Зх, + 2х2>6, 2х,+ х2<2, х,, х2>0.

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

Максимизировать z = 2х, + 2х2 + 4х3 при выполнении условий

2х, + х2 + х3 < 2, Зх, + 4х2 + 2х3>8, х„ х2, х3>0.

a) Используя программу TORA, покажите, что первый этап закончится с нулевой искусственной базисной переменной.

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

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

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

Максимизировать z = Зх, + 2х2 + Зх3 при выполнении условий

2х, + х2 + х3 = 2, х, + Зх2 + х3 = 6, Зх, + 4х2+ 2х3>8, х„ х2, х3>0.

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

b) Покажите, что описанная в упражнении 5.3 процедура, применяемая в конце первого этапа, может только одну из двух нулевых искусственных переменных сделать небазисной.

c) Покажите, что исходное ограничение, соответствующее нулевой искусственной переменной, которую нельзя сделать небазисной в п. Ь, является избыточным. Следовательно, строку этого ограничения, как и его искусственную переменную, можно удалить перед началом второго этапа.

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