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


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


10

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

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

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

6х, + 4х2<24, б + Зхгг.б, х, + х2 < 5, х, + 2х2<6, - х, + х2< 1, х2<2, х„ х2>0.

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

5. Используя систему TORA, покажите, что если в модели Reddy Mikks удалить ограничения на ресурсы (первые два ограничения), то пространство решений будет неограниченным. Что в этом случае можно сказать об оптимальном решении?

Предположим, что в модель Reddy Mikks добавлено еще одно ограничение: х2 > 3.

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

2.3. ГРАФИЧЕСКИЙ АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

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

В этом разделе анализ чувствительности основывается на графическом решении задачи ЛП. Рассмотрим два случая: 1) изменение коэффициентов целевой функции и 2) изменение значений констант в правой части неравенств ограничений. Хотя проведенное здесь исследование будет элементарным и ограниченным, оно покажет основные идеи методов анализа чувствительности. Подробно методы этого анализа описаны в главе 4.

2.3.1. Изменение коэффициентов целевой функции

В общем виде целевую функцию задачи ЛП с двумя переменными можно записать следующим образом.

Максимизировать или минимизировать z = с1х1 + с2х2.

Изменение значений коэффициентов с, и с2 приводит к изменению угла наклона прямой 2. Графический способ решения задачи ЛП, описанный в разделе 2.2, показы-



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

Пример 2.3.1

Применим процедуру анализа чувствительности к задаче примера 2.2.1 (модель для компании Reddy Mikks). На рис. 2.5 видно, что функция z = Ьхх +4дг2 достигает максимального значения в угловой точке С. При изменении коэффициентов целевой функции z = cix1 + cj2 точка С останется точкой оптимального решения до тех пор, пока угол наклона прямой z будет лежать между углами наклона двух прямых, пересечением которых является точка С. Этими прямыми являются б*, + 4jc2 = 24 (ограничение на сырье Ml) и л, + 2х2 = 6 (ограничение на сырье М2). Алгебраически это можно записать следующим образом:

В первой системе неравенств условие с, Ф О означает, что прямая, соответствующая целевой функции, не может быть горизонтальной. Аналогичное условие в следующей системе неравенств означает, что эта же прямая не может быть вертикальной. Из рис. 2.5 видно, что интервал оптимальности данной задачи (он определяется двумя прямыми, пересекающимися в точке С) не разрешает целевой функции быть ни горизонтальной, ни вертикальной прямой. Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности в нашем примере. (Если сх и с2 могут принимать нулевые значения, интервал оптимальности для отношения cjc2 (или с2/с,) необходимо разбить на два множества, где знаменатели не обращались бы в нуль. Эта ситуация представлена в упражнении 2.3.1.1.)

Итак, если коэффициенты сх и с2 удовлетворяют приведенным выше неравенствам, оптимальное решение будет достигаться в точке С. Отметим, если прямая z = clxi + Cja:2 совпадет с прямой л, + 2х2 = 6, то оптимальным решением будет любая точка отрезка CD. Аналогично, если прямая, соответствующая целевой функции, совпадет с прямой 6л, + 4х2 = 24, то любая точка отрезка ВС будет оптимальным решением. Однако заметим, что в обоих случаях точка С остается точкой оптимального решения.

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

2 с, 4

с, *0.



в нашей модели зафиксировано значение коэффициента с2 (пусть с2 = 4), то интер-

1 с 6

вал оптимальности для коэффициента с. получаем из неравенств - < -<- путем

2 с, 4

подстановки туда значения с2 = 4. После выполнения элементарных арифметических операций получаем неравенства для коэффициента ct: 2<с1<6. Аналогично, если зафиксировать значение коэффициента с, (например, ct = 5), то из неравенств

Рис. 2.5. Интервал оптимальности для модели Reddy Mikks

УПРАЖНЕНИЯ 2.3.1

1. Определите графически интервал оптимальности для отношения с,/с2 в следующих задачах; отдельно рассмотрите случаи, когда коэффициенты с5 и с2 могут обращаться в нуль.

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

Зх1 + 2х2<6, -х1 + х2<0, xv х2>0.

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

Зх, + 2х2 < 6,

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