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


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


107

с) Задача из упражнения 3 (отказавшись от предложенного начального решения Хдо).

5. Модифицированный двойственный симплекс-метод. Последовательность выполнения модифицированного двойственного симплекс-метода (использующего матричные вычисления) можно описать следующим образом.

Шаг 0. Пусть В0 = I - начальный базис, причем хотя бы один из элементов вектора отрицателен (т.е. решение недопустимо).

Шаг 1. Вычисляем текущие значения базисных переменных: Хв = B"b. Выбираем в качестве исключаемой из базиса переменную, имеющую наибольшее отрицательное значение (обозначим исключаемую переменную хг). Если все элементы в Хв неотрицательны, то вычисления заканчиваются, так как достигнуто допустимое решение.

Шаг 2.

a) Для всех небазисных переменных ху вычисляем разности zj-cj = СВВ 1Р. - е..

b) Для всех небазисных переменных ху вычисляем коэффициенты ограничений (В"Р )г, ассоциированные со строкой, соответствующей исключаемой переменной хг.

c) Определяем вводимую в базис переменную как переменную, на которой достигается следующий минимум.

, (В-рд<о.

Если все (ВРД > 0, допустимого решения не существует.

Шаг 3. Формируем новый базис путем замены в базисе вектора Р на Рг. Вычисляем новую обратную матрицу В"1 и переходим к шагу 1.

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

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

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

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

7.3. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ С ОГРАНИЧЕННЫМИ ПЕРЕМЕННЫМИ

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

= min

(В-РД



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

X = L + X, Х>0

позволяет решать задачу ЛП относительно переменных X, для которых нижняя граница значений равна нулю. Значения исходных переменных X вычисляются путем обратной подстановки; при этом, очевидно, гарантирована их неотрицательность.

Теперь рассмотрим ситуацию с верхними границами X<U. В данном случае прямая замена X = U - X", X" > 0 невозможна, поскольку обратная подстановка не гарантирует неотрицательности X. Здесь необходимо применение других процедур.

Запишем задачу ЛП с верхними границами на значения переменных как

максимизировать г = {СХ (A, I)X = Ь, 0 < X < U}.

При выполнении алгоритма решения задач с ограниченными переменными явно используются только ограничения (A, I)X = b, X > 0; ограничения вида X < U учитываются лишь в измененном симплексном условии допустимости.

Пусть Хв = B~b - текущее базисное допустимое решение задачи ЛП с ограничениями (A, I)X = b, X > 0. Обозначим через Р; вводимый в базис вектор, определенный на основе обычного симплексного условия оптимальности. Если предположить, что все небазисные переменные равны нулю, уравнение ограничения относительно базисной переменной xt будет записано следующим образом.

(ХД=(В,Ь),-(В-,Р.),х/

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

1. Базисная переменная (Хв), должна остаться неотрицательной, т.е. (Хв), > 0.

2. Базисная переменная (Хв), не должна превышать своей верхней границы, т.е. должно выполняться неравенство (Хв), < (UB)„ где UB - вектор, содержащий упорядоченные элементы вектора U, соответствующие вектору Хв.

3. Вводимая переменная xt не может принять значения, превышающего верхнюю границу, т.е. должно выполняться неравенство x.<ut, где и.- у-й элемент вектора U.

Первое условие (Хв), > 0 требует выполнения неравенства

(В-Ц-СВ-РДя.гО, которое заведомо будет выполняться, если

х,*е.=тЫ(В"Н-

(в-рд

(В-РДэ-О .

Это условие полностью соответствует условию допустимости обычного симплекс-метода.



Условие (ХД < (UB), эквивалентно неравенству

(в-ьх-св-рджид,

которое будет выполняться, если

(B-b),-(U,),

х <8, = тЫ - 1 (В-РД.

(В~РД. <0

Наконец, третье условие будет выполнено, если выполняется неравенство х < иг Все три неравенства относительно х. можно обобщить в виде следующего условия.

лгу = тт{в1( 92, и).

Базис, формируемый для следующей итерации, зависит от того, какое значение (в,, 02 или цу) примет переменная дс.. Предполагая, что (Хв)г- исключаемая переменная, получаем следующие правила формирования базиса.

1. Если х. = Gj, то переменная (Хв)г исключается из базиса и принимает нулевое значение. Новый базис формируется точно так же, как в обычном симплекс-методе с вводимой переменной дг и исключаемой (Хв)г.

2. Если Xj = 62, переменная (Хв)г исключается из базиса и принимает значение своей верхней границы. Новый базис формируется точно так же, как в обычном симплекс-методе, но с учетом того, что переменная (Хв)г равна верхней границе. Поскольку значения 0j и 62 получены при условии, что все небазисные переменные равны нулю, необходимо выполнить преобразование новой небазисной переменной (Хв)г, чтобы она также приняла нулевое значение.

Это достигается с помощью подстановки (XB)r= (UB)r- (Х„)г, где (Хй)>0.

Не имеет особого значения, когда выполняется эта подстановка: до или после вычисления нового базиса.

3. Если Xj = ujt то базисный вектор Хв остается неизменным, поскольку в данном случае никакая из текущих базисных переменных не принимает ни нулевого значения, ни значения своей верхней границы. Таким образом, переменная х} остается небазисной, но со значением своего верхнего предела. После подстановки дс = ы; - xj выполняется следующая итерация симплекс-метода.

В случае равенства значений 0,, 02 и uf выбор правила, в соответствии с которым переходим к следующей итерации симплекс-метода, произволен. Вместе с тем предпочтительнее использовать третье правило (деу = так как в этом случае требуется выполнить меньший объем вычислений.

Подстановка дсу = uj - xt изменяет исходные значения с\, Ру и b на cj = -cjt PJ = -Pj

и b = b - u Py. Это означает, что при выполнении модифицированного симплекс-метода на каждой итерации все вычисления (таких величин, как В"1, Хв и zy-cv) должны основываться на измененных значениях С, А и b (более подробно этот вопрос рассмотрен в упражнении 7.3.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]