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


[Старт] [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] [294] [295] [296] [297] [298] [299] [300] [301] [302] [303]


85

4х,+ 3х2<24

Переменные

Количество

решения

решения

-1/9

-1/3

88/3

-8/9

-7/9

Сначала рассмотрим изменения для одного из коэффициентов целевой функции. Анализ чувствительности ответит на следующий вопрос для переменной в решении: для какого диапазона значений количественные показатели всех переменных остаются неизменными?Это известно как диапазон оптимальности г

Конечно, если один из коэффициентов целевой Диапазон оптимальности функции изменен, общая прибыль (например, 88/3) -~Г™Х.п°: будет изменяться, даже если оптимальные количества Xl и Х2 не изменяются.

Анализ включает вычисление ряда отношений, используя строку C-Z конечной таблицы и строку, соответствующую той переменной, диапазон оптимальности которой должен определяться. Элементы нижней строки делятся на соответствующие элементы строки переменной. Например, для переменной xi, соотношения таковы:

C-Z О О -9 -Ц

-: j = 0 - = (неопределенность) 3 = 86

тором количественные показатели решения для всех переменных останутся неиз -менными.

Третья возможность - решение вопроса о том, насколько эффективным может быть привлечение дополнительных ресурсов в больших объемах. Этот вопрос часто возникает там, где большое количество некоторых ресурсов оказывается незадейство-ванным при оптимальном решении; добавляя другие ресурсы, можно реализовать диспропорциональное увеличение в значении целевой функции.

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

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

Таблица 5п-8. Задача и оптимальная таблица используются для демонстрации анализа чувствительности

Максимизировать: Z = 4х,+ SXg Ограничения: х,+ SXj < 12



Ближайшее к нулю положительное отношение показывает, насколько может быть увеличен исходный коэффициент Х] в целевой функции, без изменения значений оптимального решения. Таким образом, 4 может увеличиваться на 8/3 = 2,67 (т.е. до 6,67) и изменить при этом решения. Аналогично, 4 может быть уменьшен отрицательным отношением, самым близким к нулю (т.е. - 7/3 = 2,33) и не изменить количественных показателей решения. Следовательно, диапазон оптимальности для коэффициента Х]:

4-2,33 < С, <4+2,67

Если С] остается равным 4, то диапазон оптимальности для Х2 определяется следующим образом:

--: 7г = (неопределенность) 7 = 0 -ri- = - 2 -- - 7

Х2 " I тд - (Л)

Наименьшее положительное значение равно 7; следовательно, исходный коэффициент 5 может увеличиваться на 7 (5 + 7 = 12). Отрицательное отношение, самое близкое к нулю, есть -2. Следовательно, исходный коэффициент Х2 может быть уменьшен на это значение. Следовательно, нижняя граница 5-2=3. Таким образом, диапазон оптимальности для С2 будет от 3 до12.

Этот пример содержит две переменных, обе из которых присутствуют в решении. В некоторых случаях одна или более переменных могут не присутствовать в решении. В подобной ситуации мы говорим о диапазоне незначительности, то есть о диапазоне, за которым данная переменная останется вне решения. Для того, чтобы данная переменная вошла в решение, коэффициент целевой функции должен быть увеличен на значение большее, чем значение на пересечении строки C-Z и столбца этой переменной. Например, если появилось значение -4, то коэффициенты при переменных в целевой функции должны увеличиться больше чем на 4, чтобы переменная вошла в решение. Диапазон незначительности для нее от О до 4.

Давайте рассмотрим изменения для правой стороны уравнения ограничения. Не забудьте, что изменяется только одно ограничение; все остальные сохраняют свои первоначальные значения. Некоторые ограничения не подлежат изменению; ничего полезного из увеличения их значений извлечь нельзя (при условии ограничений типа <). Это относится к ограничениям, которые являются резервными в окончательном решении; эти ограничения не являются для проблемы ограничивающими факторами. Следовательно, диапазон Диапазон выполнимости выполни.мости для резервного ограничения в нижней - диапазон значений для части равен его значению в окончательном решении. правой стороны ограниче- i „" -.т

ния, за которым теневое Таким образом, если Si=250 в окончательном ре-

значение остается неизмен- шении задачи, то исходное значение правой части пер-i ным. I вого ограничения можно уменьшить на это значение и

1ааж11с-,2-ж:-?-.:1..<--~жшшж11М прИ ЭТОМ НС ИЗМСНИТЬ решеНИС. В ВСрХНСЙ ЧЗСТИ, ЗНаЧС-

ние правой стороны может быть увеличено произвольно и не изменит при этом решение; ее увеличение просто увеличит количество резерва. Резервное ограничение будет равно О в строке C-Z для столбца, который соответствует этой резервной переменной.

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

появившиеся в решении, будут иметь в своем столбце .-.жж-А г.-, • :ы>;,•. irsi отрицательное значение в строке C-Z. Эти отрицатель-I Теневые значения - вели- t ные значения известны как теневые значения. Они ука-I чины, показывающие на- зывают, насколько уменьшение на одну единицу в ис-1 SZ;:?:SHa.;: -дно- значенииограничения уменьшит конечное j ограничения изменит окон- Л значение целевой функции.

I чательноезначение целевой i; Таким образом, в таблице 5п-8, мы можем уви-

S функции. ь деть, что единичное уменьшение в первом ограниче-



Следовательно, если первое ограничение остается неизменным, второе можно увеличить на 24 единицы или уменьшить на 12. Воздействие на оптимальное значение целевой функции будет 7/9 = 0,79 на единицу.

Компьютерные решения

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

Один из наиболее широко используемых пакетов р UNDO - широко используе-линейного программирования -LINDO. ый пакет линейного про-

Этот пакет разработал Линус Шрадж из Чикаг- S граммироваиия. ского университета. Он существует в версиях для уни- "

версальных ЭВМ и для персональных компьютеров.

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

Рассмотрим следующую ЛП модель: .

Максимизировать: бОХ] + 50x2 Ограничения: 4xi + 10x2 100

нии данной задачи приведет к уменьшению конечного значения целевой функции на 8/9 = 0,89. Аналогично, уменьшение на одну единицу во втором ограничении приведет к уменьшению целевой функции на 7/9= 0,78. Наоборот, увеличение на единицу одно, го из этих значений будет иметь обратный эффект: увеличение на единицу первого or-раничения увеличит оптимальное значение целевой функции на 0,89, а увеличение на единицу второго ограничения приведет к увеличению целевой функции на 0,78. Во-прос, на который может ответить анализ чувствительности: за каким диапазоном значений правой части ограничения показатели теневыхзначений останутся значимыми?

Чтобы определить диапазон выполнимости для ограничения, сначала определим значения в тексте конечной таблицы в колонке для резервной переменной данного ограничения. Например, в таблице 5п-8 значения для Sj 4/9 и -1/3. Затем разделим эти значения на соответствующие значения в столбце количества. Для Sj получим:

y-i 4

Положительное отношение, самое близкое к нулю, указывает значение, на которое можно уменьшить исходное ограничение; а отрицательное отношение, ближайшее к нулю, - насколько его можно увеличить. В данном примере, исходное значение правой стороны первого ограничения было 12. Его можно уменьшить на 6 единиц или увеличить на 12. Воздействие этого на оптимальное значение целевой функции будет 8/9 = 0,89 на единицу. Аналогично, отношения для S2:

У-\ 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] [294] [295] [296] [297] [298] [299] [300] [301] [302] [303]