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


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


55

Поскольку переменные х2 и х3 являются базисными, из х7-строки следует исключить соответствующие им коэффициенты (т.е. надо сделать их нулевыми). Для этого необходимо выполнить следующую операцию.

Новая х7-строка = старая х.-строка - [3 х (х2-строка) + 1 х (х3-строка)] В результате получим новую симплекс-таблицу.

Базис

Решение

1350

-1/4

-1/4

-3/2

С помощью двойственного симплекс-метода находим новое оптимальное решение х, = 0, х2 = 90, х3 = 230 и z = 1330 долл. (проверьте!).

УПРАЖНЕНИЯ 4.5.3

1. Пусть в модели фабрики игрушек TOYCO время выполнения четвертой операции составляет соответственно 4, 1 и 2 минуты при сборке одной игрушки каждого вида. Найдите оптимальное решение задачи, предполагая, что фонд рабочего времени четвертой операции составляет а) 570 минут, Ь) 548 минут.

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

Примените описанную процедуру к следующей задаче ЛП.

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

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

5х, + 5х2 + Зх3 < 50, х, + хг - хг < 20, 7х, + 6х2 - 9х3 < 90, 5х, + 5х2 + 5х3 < 35, 12х, + 6х2<90, х2 - 9х3 < 20,



4.5.2. Изменения, влияющие на оптимальность решения

В этом разделе рассмотрим два фактора, которые могут изменить оптимальность текущего решения.

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

2. Добавление в модель нового вида производственной деятельности (т.е. добавление новой переменной).

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

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

1. С использованием методов 1 и 2 из раздела 4.2.3 вычисляются значения двойственных переменных.

2. На основе значений двойственных переменных по формуле 2 из раздела 4.2.4 вычисляются коэффициенты z-строки.

При этом возможны два варианта.

1. Если для новой z-строки условие оптимальности выполняется, текущее решение остается оптимальным, но значение целевой функции может измениться.

2. Если условие оптимальности не выполняется, следует применить прямой симплекс-метод для получения нового оптимального решения.

Пример 4.5.4

Предположим, что фабрика игрушек TOYCO проводит новую ценовую политику относительно своих изделий. В соответствии с этим доход от одной модели поезда, грузовика и легкового автомобиля составляет соответственно 2, 3 и 4 долл. Получаем новую целевую функцию для этой модели

максимизировать z = 2х1 + Зхг + Ахг

Таким образом,

новые коэффициенты при базисных переменныхх2, х3 их, = (3, 4, 0).

По формулам метода 1 из раздела 4.2.3 вычислим значения двойственных переменных.

( \ 2

(Л..Л) =(ЗЛ0)

3-Л,о

Коэффициенты z-строки вычисляются как разности между значениями левых и правых частей ограничений двойственной задачи (формула 2 из раздела 4.2.4). Напомним, что эти коэффициенты пересчитываются только для небазисных коэффициентов, поскольку для базисных переменных они всегда остаются равными нулю (проверьте!).



„ 3 J5) „ „ 13 y,+3y,+y3-2 = - + 3l-l + 0-2=-,

„ 3

хл у, - 0 = -. 5 " 4

Отметим, что здесь использовалось новое значение 2 коэффициента при переменной хх в выражении целевой функции.

Вычисления показывают, что текущее решение хх - 0, х2 = 100 и хг = 230 остается оптимальным. Новое значение целевой функции равно 2x0+ 3x100 + + 4x230 = 1220 долл.

Предположим, что в рассматриваемой задаче целевая функция имеет следующий вид.

Максимизировать z = 6х, + Зх2 + 4х3.

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

Базис

Решение

-3/4

1220

-1/4

-1/4

Для нахождения нового оптимального решения следует ввести в базис переменную х, и исключить из него переменную х6. В результате получим решение х, = 10, х2 = 102,5, х3 = 215 и z = 1227,50 долл. (проверьте!).

УПРАЖНЕНИЯ 4.5.4

1. Проверьте оптимальность решения задачи о фабрике TOYCO для следующих целевых функций. Если решение неоптимально, найдите новое оптимальное решение. (Симилекс-таблица с оптимальным решением для данной задачи представлена в начале раздела 4.5.)

a) г = 2х, + х2 + 4х3,

b) 2 = Зх, + 6х2 + хъ,

c) г = 8х, + Зх2 + 9х3.

2. Проверьте оптимальность решения задачи о компании Reddy Mikks (пример 4.3.1) для следующих целевых функций. Если решение неоптимально, найдите новое оптимальное решение. (Симплекс-таблица с оптимальным решением для данной задачи представлена в примере 3.3.1.)

a) г = Зх, + 2д:2,

b) 2 = 8х, + 10х2,

c) 2 = 2*, + 5х2.

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