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


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


54

Базис

Решение

1750

-1/4

-1/2

a) Определите статус каждого ресурса (комплектующего).

b) В терминах оптимального дохода определите стоимость одного резистора, одного конденсатора и одной микросхемы.

c) Найдите интервал применимости двойственных цен для каждого ресурса.

d) Найдите новое оптимальное решение при возрастании числа доступных резисторов до 1300.

e) Если количество доступных микросхем будет уменьшено до 350, можно ли будет найти новое оптимальное решение непосредственно из приведенной выше информации? Обоснуйте свой ответ.

f) В п. с был определен интервал допустимости для доступного количества используемых конденсаторов. На основе этих данных определите соответствующий интервал изменения оптимального дохода и соответствующие интервалы изменения количества производимых изделий первой и второй моделей.

g) Новый контракт позволяет компании закупить дополнительное число резисторов по 40 центов за единицу, но только при условии, что закупочная партия составит не менее 500 единиц. Выгоден ли компании такой контракт?

6. Компания для производства двух видов продукции имеет ежедневный фонд рабочего времени 320 часов и 350 единиц расходных материалов (сырья). При необходимости компания может позволить 10 часов сверхурочной работы с оплатой 2 долл. за час. На изготовление одной единицы продукции первого вида требуется 1 час рабочего времени и 3 единицы сырья, а на изготовление одной единицы продукции второго вида - 2 часа рабочего времени и 1 единица сырья. Доход от одной единицы этих продукций составляет соответственно 10 и 12 долл. Обозначим через xt и х2 ежедневные объемы

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

Максимизировать z = 10х, 4- 12х2 - 2х3

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

х, + 2х2 - х3 < 320 (ограничение на фонд рабочего времени),

Зх, + х2 < 350 (ограничение на сырье),

х3 < 10 (ограничение на сверхурочные работы),

х„ х2, х3>0.

Базис

Решение

26/5

16/5

2256

-1/5

-1/5

-1/5



a) Найдите оптимальное решение этой задачи.

b) Определите двойственные цены ресурсов и их интервалы допустимости.

c) Найдите двойственные цены для фонда рабочего времени и сверхурочных работ. Могут ли эти цены быть одинаковыми? Обоснуйте.

d) Компания может увеличить объем сверхурочных работ за дополнительную плату 2 долл. за час. Сколько часов такой сверхурочной работы может ввести компания?

e) Компания ежедневно может получать дополнительный объем сырья в 100 единиц по цене 1,50 долл. Стоит ли компании использовать этот резерв сырья? А если стоимость дополнительного сырья будет 2 долл. за единицу?

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

g) Предположим, что компания не может ежедневно использовать более 8 часов сверхурочной работы. Найдите новое оптимальное решение.

7. Достаточное правило допустимости. Это упрощенное правило можно использовать для проверки того, что одновременные изменения Д, Д,, Dm элементов вектора правых частей неравенств ограничений сохранят допустимость текущего решения. Предположим, что правая часть 6 г-го ограничения была изменена на Ь: + Д., причем независимо от изменения правых частей других ограничений, и соответствующий интервал допустимости pt < Д < qt рассчитан так, как показано в примере 4.5.2. Очевидно, что p,S0 (qt >0), поскольку величина pt (q) соответствует максимальному уменьшению (возрастанию) значения bt. Положим ri равным или отношению Д/р,, или DJqt, в зависимости от того, будет ли величина Д отрицательной или положительной. По определению 0 < rt < 1. Достаточное правило допустимости гласит, что для данных изменений Д, D2, Dm достаточным (не необходимым) условием того, что текущее решение останется допустимым, будет выполнение неравенства r\ + гг + ••• +rm-l- Если это условие не выполняется, то текущее решение может быть как допустимым, так и недопустимым. Сформулированное правило неприменимо, если Д выходят из своих интервалов допустимости.

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

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

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

Максимизировать г = 4- х2

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

2х, +х2<6, х, +2х2<6, х„х2>0.



a) Покажите, что оптимальное базисное решение содержит обе переменные х1 и хг, и что интервалы допустимости для правых частей ограничений, полученные при условии их независимости, имеют вид -3 < D, < 6 и -3 <D2 < 6.

b) Предположим, что правые части ограничений одновременно увеличиваются на величину Д > 0. Сначала докажите, что базисное решение остается допустимым для всех Д > 0. Далее покажите, что достаточное правило допустимости дает правильный ответ только тогда, когда 0 < Д < 3, не дает ответа при 3 < Д < 6, и не применимо - когда Д > 6.

9. Покажите, что достаточное правило допустимости из упражнения 7 является следствием неравенства

Обратная матрица "\( Вектор правых частей

оптимального решения

ограничении исходной задачи)

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

1. Новое ограничение является избыточным. Это означает, что новое ограничение выполняется при текущем оптимальном решении.

2. Новое ограничение не выполняется при текущем оптимальном решении. В этом случае необходимо применить двойственный симплекс-метод, чтобы получить (или хотя бы попытаться получить) новое оптимальное решение.

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

Пример 4.5.3

Предположим, что фабрика игрушек TOYCO изменила конструкцию выпускаемых моделей, и теперь для их производства необходима четвертая сборочная операция. Ежедневный фонд рабочего времени этой операции составляет 500 минут. Время выполнения этой операции при сборке одной игрушки различных видов составляет соответственно 3, 1 и 1 минуту. В результате получаем новое ограничение: Зх, + х2 + + лг3<500. Это ограничение является избыточным, поскольку оно удовлетворяется при текущем оптимальном решении хг - 0, х, = 100 и хг = 230. Таким образом, текущее оптимальное решение остается неизменным.

Теперь предположим, что в модели фабрики игрушек TOYCO время выполнения новой четвертой операции составляет соответственно 3, 3 и 1 минуту при сборке одной игрушки каждого вида. В этом случае четвертое ограничение Зх, 4- Ъхг + + х3< 500 не будет избыточным, и текущее оптимальное решение ему не удовлетворяет. Мы должны ввести новое ограничение в симплекс-таблицу, где представлено текущее оптимальное решение.

Базис

Решение

1350

-1/4

-1/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]