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


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


81

Целевая функция

Рис. 5п-8. Оптимум находится в последней точке соприкосновения линии целевой функции, когда она перемещается в направлении начала координат

Недостаток и избыток

Связывающее ограниче-

ние - ограничение, которое формирует оптимальную угловую точку области возможных решений.

штттштттшшшштшшвтжш

Недостаток - когда оптимальные значения переменных решения подставляю юя в ограничение типа S и результирующая величина меньше, чем величина пра-I вой части.

Если ограничение формирует угловую точку оптимума в области возможных решений, то оно называется связывающим ограничением (binding constraint).

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

Если подставить оптимальные значения переменных в левую часть связывающего ограничения, результирующее значение будет точно равно значению правой части ограничения. Однако в случае с необязательным ограничением будет иметь место различие. Если левая часть больше, чем правая, то говорят, что имеется избыгок; если левая часть меньше правой, то имеется недостаток. Недостаток может возникать только в ограничении типа <; это та величина, на которую левая часть меньше правой, когда оптимальные значения переменных подставляются в левую часть.

Избыток может возникать только в ограничениях типа >; это величина, на которую левая часть больше

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

Например, предположим, что оптимальные значения для модели: xj = 10 и Х2 = 20. Одно из ограничений имеет вид:

3x1 +2x2 < 100

Подставляя оптимальные значения в левую часть, получим: 3(10)+ 2(20) =70

Так как ограничение имеет тип < различие между значениями 100 и 70 (т.е.ЗО) - это недостаток. Предположим, что оптимальные значения xj = 20 и Х2 = 20. Подстановка этих значений в левую часть ограничения даст 3(20) + 2(20) = 100. Т.к. левая и правая части равны (недостаток равен 0), имеет место связывающее ограничение.

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



Теперь рассмотрим ограничение: 4Х1+Х250

Предположим, что оптимальные значения Xj = 10 и Х2 = 15; подставляя их в левую часть, получим: 4(10)+ 15=55

Так как это ограничение типа >, разность между левой и правой частями является избытком. Если оптимальные значения были xj = 12 и Х2 = 2, то в результате подстановки левая часть будет равна 50. Следовательно, ограничение будет связывающим, а излишка не будет (т.е. излишек равен 0).

Симплексный метод

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

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

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

Давайте рассмотрим симплексное решение для той же самой задачи, которая использовалась для иллюстрации графического метода. Повторим постановку задачи: Максимизировать: Z = 4 Xj + 5x2 Ограничения: Xj + 3x2 < 12

4xi+ 3x2 < 24 Xi,X2>0

0 2 4 6

Рис. 5п-9. Графическое решение

8 10 12 14 X,



Графическое решение показано на рисунке 5п-9. «-««.«ж!»т»ж«шж5«вш«,.»в Теперь давайте посмотрим, как можно использовать Таблица решения - одно Симплексный метод для получения решения. из серии решений в таблич-

Симплексная методика включает разработку »о> Фор/: коерешение „, i: I соответствует угловой точке

серии решении в табличной форме - таблиц решения. * области возможных реше-

Рассмотрев нижнюю строку каждой таблицы, ний. можно сразу сказать, достигнуто ли в данном случае «в.шжва»чгл-«-«лвжАвга. оптимальное решение. Каждая таблица соответствует

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

1. Составить начальную таблицу.

2. Разработать следующую таблицу, используя информацию из первой таблицы.

3. Проверить решение на оптимальность.

4. Повторять шаги 2 и 3, до тех пор пока дальнейшая оптимизация станет невозможной.

Построение начальной таблицы

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

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

(1) х,+3х2+lsi= 12

(2) 4x1+3x2+ls2= 24

При составлении таблицы полезно представить каждую резервную переменную в каждом уравнении. Следовательно, мы можем записать эти уравнения в эквивалентной форме:

(1) Х1+ЗХ2+ ls, + 0S2= 12

(2) 4x,+3x2+0s,+lS2=24

Целевая функция может быть записана в сходной форме:

Z = 4x1+5x2+ Osi+ 0s2 У переменных резерва в целевой функции нулевые коэффициенты, потому что они не вносят своего вклада в прибыль. Таким образом, подводим итоги полученной информации:

Максимизировать: Z = 4xi +5x2+ Sj + 0s2

Ограничения: (1) Х] +3x2 + IS] + 0s2 = 12 (2)4xi+3x2+Os,+ 1S2=24 Это образует основу нашей начальной таблицы, которая показана в таблице 5п-1.

Чтобы завершить исходную таблицу, нам нужны две дополнительные строки, Z и C-Z. Строка Z показывает уменьшение прибыли, которое произойдет, если одна единица переменной в этом столбце будет добавлена к решению. Строка C-Z показывает потенциал увеличения прибыли, если одна единица переменной этого столбца будет добавлена к решению.

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