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


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


83

Количество

Текущее значение 3 О -1 1 12 JHoBoejjeHne onopHoroj 0/3 -V3 J/3 12/3=4

4. Вычислите значения для строки Х2: умножьте каждое новое значение опорной строки на опорное значение строки Х2 (то есть, 1:3), и вычтите результат из соответствующих текущих значений. Таким образом, получим:

Текущее значение 1/3 -1/Зх(опорный ряд) -1/3(1) Новое значение ряда О

Количество

-1/3(0)

-1/3(-1/3)

-1/3(1/3)

-1/3(4)

-1/9

На ЭТОМ этапе будет полезно рассмотреть таблицы относительно графика области возможных решений. Это показано на рисунке 5п-10.

5. Вычислите новые значения строки Z. Обратите внимание, что теперь к решению добавляется переменная xi; прибыль на единицу в этой строке составляет $4.

Ряд Прибыль X,

Количество

Хг $5 5(0)

5(1)

5(4/9)

5(-1/9)

5(8/3)

X, $4 4(1)

4(0)

4(-1/3)

4(1/3).

4(4)

Новый ряд Z 4

88/3

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

С 4

Z 4

C-Z 0

0

-8/9

-7/9

Полученные в результате значения третьей таблицы показаны в таблице 5п-7. Обратите внимание, что каждое из значений строки C-Z является нулевым или отрицательным, указывая на то, что это решение является окончательным. Оптимальные значения X] и Х2 обозначены в столбце количества: Х2 = 8/3, или 22/3, и Х] = 4. (Количество Х2 - в строке Х2, а количество Х) - в строке Х).) Общая прибыль составит 88/3, или 29,33 (столбец количества, строка Z).

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

Третья таблица будет составлена тем же способом, что и предыдущая:

1. Определите входную переменную: найдите столбец с самым большим положительным значением в строке C-Z (7/3, в столбце xi).

2. Определите уходящую переменную: разделите количество решения в каждом ряду на опорную строку. В итоге получаем:

=12; 1Уз = 4

Меньшее отношение показывает уходящую переменную, S2 (см. табл.5п-6).

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



Таблица 5п-6. Выходящая и входящая переменные

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

«1

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

4:1/3=12

Уходящая

12/3=4 <-

переменная Sg

7/3 Т

-5/3

Входящая переменная х,

2-я 21-таблица

таблица

Рис. 5п-10. Графические аналоги симплексных таблиц

Таблица 5п-7. Третья таблица содержит оптимальное решение

Переменные

Количество

в решении

решения

-1/9

-1/3

88/3

-8/9

-7/9

Обработка ограничений типа > и =

До этого момента мы работали с ограничениями типа <. Ограничения типа равенства или > обрабатываются несколько иным способом.

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

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

(1) 7x1 + 4x2=65

(2) 5х, + 3x2 = 40

Перепишем эти уравнения с искусственными пере-

«жгч:жкг-г-, менными aj И 32:

Искусственная переменная - переменная, вводимая в случае ограничения типа равенства с целью разработки начального решения.



(1) 7X1 + 4X2+la,+ 032= 65

(2) 5xi + 3x2+0ai+1а2 = 40

Добавлений резервных переменных не требуется. Целевая функция, например, Z = 2xi + 3x2 будет переписана следующим образом:

Z = 2xi+3x2 + Mai + Ma2,

где М = большое число (например, 999).

Так как искусственные переменные нежелательны в конечном решении, выбор большого значения М (намного большего, чем другие целевые коэффициенты) будет обеспечивать их стирание в процессе решения.

Для ограничения > переменные резерва должны быть вычтены, а не добавлены к каждому ограничению. Например, ограничения

(1) 3x1 + 2x2+ 4хз> 80

(2) 5х] + 4х2 + хз>70

(3) 2X1 +8X2+2хз>68

перепишем в виде равенств:

(1) 3x, + 2x2+4x3-lsi-0s2-0s3=80

(2) 5х,+ 4x2+ Хз-0si-ls2-0s3=70

(3) 2х, + 8x2+2x3-Os,-0s2-ls3= 68

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

(1) 3x1 +2x2+4x3-Is,-0s2- 0S3 + Iai+032+0аз= 80

(2) 5x1 + 4x2+ Хз-0si-lS2-0s3+0ai+1а2+0аз=70

(3) 2xi + 8x2+2x3- 0si-0s2-ls3+0ai+0a2+ 1аз = 68

Если целевая функция будет: 5xi + 2x2+ 7x3, то в итоге мы получим:

5x1 + 2x2 + 7хз + Osi + 0s2 + OS3 + Mai + Ма2 + Маз.

Резюме процедуры максимизации

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

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

а. Переписать ограничения так, чтобы они стали равенствами; добавить резервную переменную излишка к каждому ограничению.

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

в. Представить целевые коэффициенты и коэффициенты ограничения в форме таблицы.

г. Вычислить значения для строки Z; умножить значения в каждой строке ограничений на значение строки С. Сложить результаты в каждом столбце.

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

2. Составить последующие таблицы.

а. Определить входную переменную (наибольшее положительное значение в строке 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]