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


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


33

Базис

Решение

a) Разделите все переменные на базисные и небазисные и найдите их значения.

b) Пусть решается задача максимизации. Определите небазисные переменные, которые потенциально могут увеличить значение целевой функции. Для каждой такой переменной, предполагая, что она вводится в базис, найдите исключаемую переменную и соответствующее изменение целевой функции. Не используйте метод Гаусса-Жордана.

c) Повторите упражнение п. Ь, предполагая, что решается задача минимизации.

d) Какие небазисные переменные не смогут изменить значение целевой функции, если их ввести в базис?

7. Рассмотрите двухмерное пространство решений на рис. 3.7.

a) Пусть целевая функция имеет следующий вид:

максимизировать г = Зх, + 6х2.

Предполагая, что реализация симплекс-метода начинается в точке А, определите последовательность угловых точек, приводящих к точке оптимума Е.

b) Определите вводимую переменную, значения соответствующих отношений в условии допустимости и значение целевой функции, полагая, что реализация симплекс-метода начинается в точке А и целевая функция имеет вид

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

c) Повторите п. b применительно к целевой функции

максимизировать z = xt + 4х2.

Рис. 3.7. Пространство решений для упражнения 7



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

Максимизировать г = 16л:, + 15л:2

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

40л:, + 31л:2< 124, -jc, + л:2 < 1, л:, <3, л:2>0.

a) Решите поставленную задачу симплекс-методом, выбирая в качестве вводимой небазисную переменную, имеющую наибольший по абсолютной величине отрицательный коэффициент в z-строке симплекс-таблицы.

b) Решите поставленную задачу симплекс-методом, выбирая в качестве вводимой небазисную переменную, имеющую наименьший по абсолютной величине отрицательный коэффициент в z-строке симплекс-таблицы.

c) Подсчитайте количество итераций, используемых для решения задачи в пп. атлЬ. Действительно ли выбор вводимой переменной среди небазисных, имеющих наибольший по абсолютной величине отрицательный коэффициент в z-строке, ведет к уменьшению числа итераций, выполняемых при реализации симплекс-метода?

d) Предположим, что задача максимизации целевой функции z заменена на задачу минимизации путем умножения функции г на -1. Как это скажется на количестве итераций симплекс-метода?

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

Расход ресурса на производство одного изделия Ограничение на ресурс

Ресурс

Сумка

Чемодан

Рюкзак

(ежедневно)

Кожа (кв. футы)

Прошивка (часы)

Отделка (часы)

Отпускная цена (долл.)

Сформулируйте задачу линейного программирования, с помощью программы TORA найдите ее оптимальное решение и определите статус ресурсов.

3.3.3. Реализация симплекс-метода в системе TORA

В программной системе TORA можно выполнить все итерации симплекс-метода так же, как это было описано в разделе 3.3.2. Сначала введите условия задачи (как это сделать, см. приложение Б). Затем из меню SOLVE/MODIFY выберите команду SolveOAIgebraiclterationsAII-Slack. (Команда All-Slack (Все остаточные) указывает на то, что начальное базисное решение состоит только из остаточных дополнительных переменных. Остальные команды из подменю Iterations будут описаны



далее в разделах 3.4, 4.3 и 7.4.2.) Далее задается точность, с которой будут отображаться выходные результаты, остается щелкнуть на кнопке Go То Output Screen (Перейти к экрану вывода).

На рис. 3.8 представлено окно, в котором показаны результаты расчетов для каждой итерации для модели Reddy Mikks (файл ch3ToraReddyMikks.txt). Чтобы перейти к следующей итерации, щелкните на кнопке Next Iteration (Следующая итерация, это режим пошагового выполнения). Чтобы сразу получить окончательный ответ, щелкните на кнопке All Iterations (Все итерации). Если вы выполняете вычисления в пошаговом режиме, то на каждой итерации можно указать вводимую и исключаемую переменные, щелкнув на соответствующих столбце и строке. Если ваш выбор корректен, то столбец закрасится зеленым цветом, а строка - красным. В противном случае получите сообщение об ошибке. Такой тип вычислений должен помочь вам понять основные базовые концепции симплекс-метода без громоздких вычислений по методу Гаусса-Жордана.

TORA D:\Work\ToraFilesV:h3ToraRedclyMild<s.txl

LINEAR PROGRAMMING

SIMPI FX 1ЛН1 I AI) (Starting All Slack Method)

Title: Reddy Mikks model, Example 7.2A (Maximize)

Step* for uenerrtirte NEXT tableau tram CURWrNT one:

1. ENTERING variable: Click a NONBASIC variable (rf correct, column turn* green)

?. LEAVING variable: Click а BASIC variable (it correct, row lurna red) 3. Click command button NEXT ITERATION (or Alt ITERATIONS) Thta atep maybe executed without Stcpa 1 inciter 2.

Рис. 3.8. Модель Reddy Mikks в программе TORA

УПРАЖНЕНИЯ 3.3.3

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

Максимизировать z = хг + х2 + Зх3 + 2xt при ограничениях

х1 + 2х2 - Зх, + 5х4 < 4, 5хг - 2х2 + 6х4 < 8,

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