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


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


84

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

в. Образовать новую опорную строку следующей таблицы: разделить каждое число в строке уходящей переменной на значения опорной строки. Введите эти значения в следующую таблицу в тех же самых позициях строки.

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

д. Вычислите значения для строк Z и C-Z .

е. Проверьте, есть ли в строке C-Z положительные значения; если есть, то повторите пункты 2а - 2е. Если нет, то мы получили оптимальное решение.

Задачи минимизации

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

ПРИМЕР 3

Решите следующую задачу для количеств и xg, которые минимизируют затраты. Минимизировать: Z=]2xi+10x2 Ограничения: X]-i-4x2>8

Зх]-н2х2>6 х,,Х2>0

Решение:

1. Перепишем ограничения в нужной форме:

х. -н 4x2 > 8 становится х., -н 4X3 - Is., - OSg -н la., -н Оа = 8 Зх. -н 2x2 > 6 становится Эх., -н 2X3 - Osl - ISj + Оа -н lag = 6

2. Перепишем целевую функцию (коэффициенты в строке С): 12х -н 10x2 -I- Os + + 999а + 999а2

3. Вычислим значения для строк Z и C-Z.

Количество

1(999)

4(999)

-1(999)

0(999)

1(999)

0(999)

8(999)

3(999)

2(999)

0(999)

-1(999)

0(999)

1(999)

6(999)

3996

5994

-999

-999

13986

-3984

-5984

4. Составим начальную таблицу. (Обратите внимание, что начальное решение содержит все искусственные переменные.)



999 999

Переменные в решении

«1

Количество решения

3996

5994

-999

-999

13986

-3984

-5984

Найдем входящую переменную (самое большое отрицательное значение C-Z: столбец Xg) и уходящую переменную (меньшее из 8/4 = 2 и 6/2 = 3; следовательно, строка а.).

Разделим каждое число в уходящей строке на опорное значение (4, в данном случае), чтобы получить опорную строку второй таблицы:

1/4, 4/4=1, -1/4, 0/4, 1/4, 0/4, 8/4=2

Вычислим значения для других строк; а:

Количество

Текущее значение 3

-2 х(новый опорный ряд) -2/4 Новый ряд 10/4

8. Вычислим новую строку Z:

2 О -2 2/4 О +2/4

-10 16

-0/4 -2/4 -0/4 -4 -1

-2/4

Затраты

Кол-во

10(1/4)

10(1)

10(-1/4)

10(0)

10(1/4)

10(0)

10(2)

999(10/4)

999(0)

999(2/4)

999(-1)

999(-2/4)

999(1)

999(2)

2500

-999

-497

2018

9. Вычислим строку C-Z:

«1

2500

-999

-497

-2488

-497

1496

10. Составим вторую таблицу:

Переменные в решении

Коли-честао

10/4

-2/4

2500

-999

-497

2018

-2488

-497

1496

ill- Повторим процедуру:

а. Проверим оптимальность: если строка C-Z содержит отрицательные элементы - оптимум не достигнут.

б. Определим переменную ввода: наибольшее отрицательное значение в столбце х. I

в. Определим переменную выхода: 2/(1/4) = 8, 2/(10/4) = 0,8. Следовательно, i это--строка I

г. Найдем новое значение опорной строки, используя опорное значение 10/4 1



1 О 0,2 -0,4 -0,2 0,4 0,8

д. Определим значения для новой строки х:

О 1 -0,3 0,1 0,3 -0,1 1,8

е. Определим новые значения для строки Z;

Ряд Зат- Кол- раты X, Sj aj во

Xg 10 10(0) 10(1) 10(-0,3) 10(0,1) 10(0,3) 10(-0,1) 10(1,8)

X, 12 12(1) 12(0) 12(0,2) 12(-0,4) 12(-0,2) 12(0,4) 12(0,8)

Z 12 10 -0,6 -3,8 0,6 3,8 27.6

Ж. Определим значения для строки C-Z:

-0,6

-3,8

998,4

995,2

3. Составим следующую таблицу. Поскольку среди значений C-Z нет отрицательных, решение оптимально. Следовательно, х., = 0,8, х2 = 1,8 и минимальные затраты-27,60.

Переменные

Коли-

в решении

чество

-0,3

-0,1

-0,4

-0,2

-0,6

-3,8

27,6

998,4

995,2

.r:i::s;5.o.:.v

чнализ чувствительности

асто случается, что принимающий производственные решения руководитель хочет юлучить нечто большее, чем сиюминутное решение проблемы. Он может получить юльшую и многообразную пользу из анализа чувствительности решения. При подго-"овке задачи к решению методом линейного программирования, менеджер может давать субъективные оценки некоторым параметрам (например, коэффициентам огра-мчений, коэффициентам целевой функции и значениям правой части в уравнениях •граничений). Вполне естественно, что он хочет знать: насколько чувствительным яв-1яется оптимальное решение к изменениям в значении одного или нескольких таких параметров. Если решение относительно устойчиво к разумным изменениям, то ме-чеджер может чувствовать себя достаточно уверенно, осуществляя свои решения на трактике. Наоборот, если решение чувствительно к подобным изменениям, то менед-ер несомненно захочет получить более точную оценку подозрительных параметров.

Вторая возможная польза от анализа чувствительности касается специфических 1зменений в параметрах. Например, изменение цен может изменить коэффициент в селевой функции. Аналогично, изменение в производственном процессе может потребовать изменения коэффициента при одном из ограничений. И здесь анализ чувствительности может обеспечить менеджера необходимыми данными.

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