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


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


29

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

a) Максимизировать z = 2хх - 4х2 + Ьх3 - 6xt при ограничениях

хг + 4х2 - 2х3 + 8xt < 2, -л:, + 2л:.,-1-Зл:3-1-4л:4<1, х,, х2, х3, х4 0.

b) Минимизировать z = л:, + 2х2 - Зх3 - 2xt при ограничениях

л:, + 2х2 - Зх3 + х4 = 4, jc, + 2л:2 + х3 + 2xt = 4, Хр х2, х3, х4 - 0.

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

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

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

л:, + 2х2<6, 2л:, + х2 > 16, л:,, jc2>0.

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

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

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

-6л:, + 7л:2- 9л:3>4, -л:, + л:2 + 4л:3 = 10, л:,, л:3>0,

л:2 - свободная переменная. Приведите задачу к стандартной форме, используя для этого подстановку л, =х* - л,". Покажите, что в этой задаче не существует базисных решений, в

которые входили бы одновременно х, и х\.

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

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

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

л:, + л:2< 2, -л:, + л:2 < 4,

л:, - свободная переменная, л:2>0.

a) Найдите все допустимые базисные решения этой задачи.

b) С помощью подстановки решений в целевую функцию определите наилучшее базисное решение.

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



3.3. АЛГОРИТМ СИМПЛЕКС-МЕТОДА

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

3.3.1. Итерационная природа симплекс-метода

На рис. 3.3 показано пространство решений задачи ЛП из примера 3.2.1. Обычно алгоритм симплекс-метода начинается с исходной точки, где хх = х2 = 0 (точка А). В этой начальной точке значение целевой функции г равно нулю. Возникает естественный вопрос: если одна или обе небазисные переменные хх и х2 примут положительные значения, то приведет ли это к улучшению (возрастанию) значений целевой функции? Для ответа на этот вопрос рассмотрим целевую функцию

максимизировать г = 2хх + Зх2.

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

1. Если увеличивать значение переменной хх, то (см. рис. 3.3) ее значение должно возрасти таким образом, чтобы соответствовать угловой точке В (повторим, что внутренние точки отрезка от точки А до точки В неприемлемы, поскольку кандидатом на оптимальное решение может быть только угловая точка). В точке В симплекс-метод должен увеличить значение переменной х2, перемещаясь при этом в угловую точку С. Так как точка С соответствует оптимальному решению, то на этом процесс вычислений заканчивается. Таким образом, алгоритм симплекс-метода создает путь А-> В -» С.

2. Если сначала увеличивать значение переменной х2, то следующей угловой точкой будет точка D, из которой процесс решения переходит в оптимальную точку С. Здесь алгоритм симплекс-метода создает путь А -> Z) -»С.

Отметим, что оба пути, A>B->CnA->D->C, расположены вдоль границы пространства решений. Это означает, что симплекс-метод не может сразу перескочить из точки А в точку С.

Может возникнуть правомерный вопрос: существует ли правило, в соответствии с которым можно было бы определить, какую небазисную переменную сделать положительной в данной угловой точке? Например, в точкеА как переменная хх, так и переменная х2 могут увеличить значение целевой функции. Симплекс-метод предлагает простое правило выбора переменных, которое в основном применяется в его программных реализациях. Поскольку здесь мы рассматриваем задачу максимизации, то следует выбирать такую небазисную переменную, которая имеет наибольший положительный коэффициент в выражении целевой функции. Если таких переменных несколько, то выбор произвольный. Необходимо понимать, что это эмпирическое правило, сформулированное на основе многочисленных компьютерных вычислений симплекс-метода - в большинстве случаев (но не обязательно всегда) применение этого правила ведет к наименьшему числу итераций, затрачиваемых на поиск оптимального решения.



0 1 2 3 4 5

Рис. 3.3. Итерационный процесс симплекс-метода

Этот раздел завершим описанием перевода небазисных переменных в базисные и наоборот при переходе от одной угловой точки к следующей. На рис. 3.4 показано, что в точке А переменные s, и s2 являются базисными, а переменные хх и хг - небазисными. Если переменная хх принимает положительное значение, мы переходим в угловую точку В, в которой изменяется состояние переменной хх из небазисной в базисную. Одновременно переменная s,, которая была базисной в точкеА, становится небазисной и принимает нулевое значение в точке В. Здесь существенно, что происходит одновременный "обмен состояниями" между небазисной переменной хг и базисной переменной s,, что приводит к новым базисным переменным (*,, s2) и небазисным переменным (s,, х2) в точке В. Скажем, что в точкеА переменная xt вводится в базисное решение, а переменная s, - исключается из базисного решения. В соответствии с терминологиейсимплекс-метода выбранная небазисная (нулевая) переменная называется вводимой (в базисное решение), а удаляемая (из базисного решения) базисная переменная- исключаемой. В точке В вводимой и исключаемой переменными будут соответственно переменные х2 и s2. Процесс изменения состояний переменных заканчивается в точке С, поскольку найдено оптимальное решение.

УПРАЖНЕНИЯ 3.3.1

1. На рис. 3.4 показана схема изменения базисных и небазисных переменных в соответствии с путем А-> В -> С в пространстве решений, представленном на рис. 3.3. Создайте аналогичную схему для пути А-> D -> С.

2. Вернитесь к графическому решению задачи Reddy Mikks, показанному на рис. 2.2. Разработайте схему изменения базисных и небазисных переменных (подобную представленной на рис. 3.4), указав на каждой итерации вводимые и исключаемые переменные в соответствии со следующими путями.

a) А->В->С.

b) А-> F -> Е -> D -> С.

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