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


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


57

10. Достаточное правило оптимальности. Правило, подобное достаточному правилу допустимости из упражнения 4.5.2.7, можно сформулировать и для проверки оптимальности текущего решения при одновременном изменении всех коэффициентов cj целевой функции. Для этого представим коэффициенты cj в виде cj + dr j = 1, 2, п. Предположим, что для всех изменений dj независимо получены индивидуальные интервалы u.<dt< v} значений, сохраняющих оптимальность текущего решения (как в примере 4.5.5). Очевидно, что ц<0 (v}>0), поскольку эта величина соответствует максимально возможному уменьшению (увеличению) коэффициента cjt сохраняющего текущее оптимальное решение. Для df, которые находятся в интервале Uj<di< у, определим отношение г. = djv. или rj = dju в зависимости от того, будет величина d} положительной или отрицательной. По определению 0<гу<1. Правило гласит, что достаточным (но не необходимым) условием сохранения оптимальности текущего решения является выполнение неравенства г, + г2 + ... + rn < 1. Если это неравенство не выполняется, то текущее решение может быть как оптимальным, так и неоптимальным. Это правило не применимо, если величины d} выходят за свои интервалы оптимальности.

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

11. Покажите, что достаточное правило оптимальности (упражнение 10) является следствием неравенств zj-cj >0 в задаче максимизации и неравенств zj - с. < 0 в задаче минимизации.

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

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

Пример 4.5.6

Оптимальное решение задачи ЛП о фабрике игрушек TOYCO показывает, что производство моделей поездов нерентабельно. Поэтому фабрика планирует заменить производство этих моделей выпуском модели пожарной машины, причем ее сборка будет осуществляться с использованием тех же производственных мощностей. Доход от новой игрушки ожидается в 4 долл. за одну модель. Ее время



сборки на каждой из трех технологических операций составляет соответственно 1, 1 и 2 минуты.

Обозначим через х7 объем производства новой продукции. Имея значения переменных двойственной задачи (yvy2, у8) = (1, 2, 0), вычисляем приведенную стоимость для переменной х7:

1у\ + 1у2 + 2Уъ - 4 = 1 х 1 + 1 х 2 + 2 х 0 - 4 = -1.

Полученный результат показывает, что экономически целесообразно включить переменную х7 в оптимальное базисное решение. Чтобы найти новое оптимальное решение, сначала с помощью формулы 1 из раздела 4.2.4 вычислим столбец коэффициентов ограничений, соответствующий переменной х7.

Отсюда следует, что текущая симплекс-таблица должна быть приведена к следующему виду.

Базис

Решение

1350

-1/4

-1/4

Теперь новое оптимальное решение можно найти, введя в базис переменную х7 и исключив из него переменную д:6. Новое решение составляют х, = 0, х2 = 0, х2 = 125, х7 = 210 и 2 = 1465 долл. (проверьте!).

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

УПРАЖНЕНИЯ 4.5.6

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



рентабельным. (Симплекс-таблица с оптимальным решением данной задачи приведена в начале раздела 4.5.)

2. Предположим, что в исходной модели фабрики игрушек TOYCO время выполнения трех сборочных операций при производстве моделей поездов уменьшено соответственно до 0,5, 1 и 0,5 минут. Доход от модели этого вида остался неизменным на уровне 3 долл. за одну игрушку. Найдите новое оптимальное решение.

3. Пусть производство модели нового вида (модель пожарной машины) требует соответственно 1, 2 и 3 минуты для выполнения каждой сборочной операции. Найдите оптимальное решение, если доход от одной модели нового вида составляет а) 5 долл., Ь) 10 долл.

4. Вернитесь к модели компании Reddy Mikks (модель представлена в примере 4.3.1, симплекс-таблица с ее оптимальным решением- в примере 3.3.1). Предположим, что компания рассматривает возможность производства дешевой краски для наружных работ, причем для производства тонны такой краски требуется 0,75 тонны сырья Ml и столько же сырья М2. Ситуация на рынке показывает, что производство краски для внутренних работ не должно превышать ежедневного производства обоих видов красок для наружных работ более чем на одну тонну. Доход от одной тонны новой краски составляет 3500 долл. Найдите новое оптимальное решение.

ЛИТЕРАТУРА

1. BazaraaM., Jarvis J., SheraliM. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Bradley S., Hax A., Magnanti T. Applied Mathematical Programming, Addison-Wesley, Reading, MA, 1977.

3. Nering E., Tucker A. Linear Programming and Related Problems, Academic Press, Boston, 1992.

Литература, добавленная при переводе

1. Ашманов С. А. Линейное программирование. - М.: Наука, 1981.

2. Гольштейн Е. Г. Теория двойственности в математическом программировании и ее приложения. - М.: Наука, 1971.

3. Гольштейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. - М.: Наука, 1969.

КОМПЛЕКСНЫЕ ЗАДАЧИ

4.1. 4 Компания MANCO производит три вида продукции: PI, Р2 и РЗ. В производственном процессе используются материалы Ml и М2, обрабатываемые на станках С1 и С2. В следующей таблице приведены данные, характеризующие производственный процесс.

4 Задача основана на материалах статьи D. Sheran, "Post-Optimal Analysis in Linear Programming - The Right Example", HE Transactions, Vol. 16, No. 1, March 1984, pp. 99-102.

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