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


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


39

УПРАЖНЕНИЯ 3.5.2

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

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

при выполнении условий

x,+2x2-l-3x3<10, х, + х2 < 5,

х,, х2, х3>0.

2. Покажите с помощью программы TORA, что следующая задача ЛП имеет альтернативные оптимальные решения и все они небазисные. Для этой задачи представьте на плоскости пространство решений и прямую, соответствующую целевой функции.

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

при выполнении условий

х, - х2 + 5х3< 10, 2х, - х2 + Зх3 < 40, *i> х2, х3>0.

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

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

х, + 2х2<5, х1 + х2-х3<2, 7х, + Зх2 - 5х3 < 20, х,, х2, х3>0.

3.5.3. Неограниченные решения

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

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

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



Пример 3.5.3. Неограниченная целевая функция

Рассмотрим задачу

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

при выполнении условий

хг-х2<10, 2х, < 40, xv х2 > 0.

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

Базис

Решение

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

Неограниченное пространство решений

2x40

Неограниченное значение целевой функции

Рис. 3.12. Неограниченность решения в примере 3.5.3



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

УПРАЖНЕНИЯ 3.5.3

1. В задаче из примера 3.5.3 с помощью программы TORA покажите, что применение симплекс-метода, когда согласно условию оптимальности вычисления начинаются с переменной л:, в качестве вводимой, обязательно приведет к неограниченному решению.

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

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

Зх, - Зх, + 5*3 < 50, лс, + х3< 10, хх-х2 + 4х3 < 20, х„ х2, х3>0.

a) Рассмотрев ограничения, определите направление (по оси х,, х2 илих3), в котором пространство допустимых решений не ограничено.

b) Без дополнительных вычислений сделайте заключение относительно оптимального значения целевой функции.

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

• странства решений.

3.5.4. Отсутствие допустимых решений

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

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

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