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


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


109

3. Решите следующие задачи ЛП методом решения задач с ограниченными переменными.

a) Минимизировать z = бдс, - 2х2 - Зх3 при ограничениях

2xt + 4х2 + 2х, < 8, х1-2х2 + 3х3<7, О < х, < 2, 0 < х2 < 2, 0 < х3 < 1.

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

х1 + 2х2 + 2х3<ю,

2х, + 4х2 + 3х3< 15, О < х, < 4, 0 < х2 < 3, 0 < х3 < 3.

4. В следующих задачах некоторые переменные имеют положительные нижние границы. Решите эти задачи методом решения задач с ограниченными переменными.

a) Максимизировать z = 3*, + 2х2 - 2х3 при ограничениях

2х1 + х2 + х3 < 8, х, + 2х2 - х3 > 3, хЗ, 0<х2<3, 2<х3.

b) Максимизировать z = xl + 2х2 при ограничениях

-Xj + 2х2>0, Зх, +2х2< 10, -х, + х2< 1, lxe.Oxl.

c) Максимизировать z = 4х, + 2х2 + 6х3 при ограничениях

4х, - х2 < 9, -х, +х2 + 2х3<8, -Зх1 + х2 + 4х3<12, 1<х,<3,0<х2<5, 0<х3<2.

5. Рассмотрим матричное представление задачи с ограниченными переменными. Разобьем вектор X на две части (Хг, Хц), где элементами вектора Хц являются переменные, к которым в процессе выполнения алгоритма будет применена подстановка, эквивалентная их верхнему пределу. Тогда задачу ЛП с ограниченными переменными можно записать следующим образом.

f 7

1 -с; -с,Л

0 D, D.



Пусть В (и Хв) - базисное решение текущей симплексной итерации, полученное после подстановки Хц = U„ - Хи, где U„ - подмножество элементов вектора значений верхних границ U, соответствующего переменным Хц. Покажите, что в данном случае симплекс-таблица имеет следующий вид.

Базис

Решение

CSB 1DZ-CZ

- СвВ 1Du + Си

CsB-1 ь + с„иц

B"1D;

-в-1ои

В"1 Ь

Здесь b = b - DUUU.

6. В задаче из примера 7.3.1 выполните следующее.

a) На этапе итерации 1, используя матричные представления, проверьте, что Хв = (х4, х1)г = (5/2,3/2)г.

b) На этапе итерации 2 покажите, как на основе исходных данных задачи можно вычислить В"1. Затем, используя матричные представления, проверьте вычисленные в примере значения переменных xt и х,.

7. Решите задачу из упражнения 3.1 с помощью модифицированного (использующего матричные представления) симплекс-метода.

8. Двойственный симплекс-метод решения задач с ограниченными переменными. Двойственный симплекс-метод (раздел 4.4) также можно модифицировать для учета явных ограничений, налагаемых на переменные. Для этого после подстановок xt = u;- xt (uj - верхняя граница переменной х-, если uf

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

Шаг 1. Если значение какой-либо базисной переменной (Хв), превышает ее верхнюю границу, выполняем замену (ХД = (UB), - (Х6)..

Шаг 2. Если базисное решение допустимо, вычисления заканчиваются.

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

Шаг 3. В соответствии с условием оптимальности двойственного симплекс-метода определяем вводимую в базис переменную.

Шаг 4. Выполняем пересчет базиса. Переходим к шагу 1.

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

а) Минимизировать г = -Зхг - 2хг + 2х3

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

2х, + х2 + х3 < 8, -х1 + 2х2 + х3>13, 0<х,<2, 0<х2<3, 0<х3<1.



Ь) Максимизировать г = хг + 5х2 - 2х3 при ограничениях

4*! + 2х2 + 2х3 < 26, + Здс2 + 4х3> 17, О < х, < 2, 0 < х2 < 3, 0 < х3 (х3 сверху не ограничена).

7.4. МЕТОД ДЕКОМПОЗИЦИИ

Рассмотрим разработку производственного плана предприятия, состоящего из нескольких подразделений. Хотя каждое подразделение имеет собственные производственные возможности и соответствующие ограничения, производственные планы отдельных подразделений обобщаются на уровне управления предприятием. Таким образом, результирующая модель рассматриваемого предприятия будет содержать ограничения двух типов: общие, соответствующие уровню всего предприятия, и независимые, отображающие производственные ограничения отдельных подразделений. На рис. 7.5 показана структура ограничений для п подразделений. Отсутствие общих ограничений означает, что все подразделения независимы.

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

Общие ограничения

Независимые ограничения

Подразделение 1

Подразделение 2

Подразделение л

Рис. 7.5. Структура декомпозиции задачи линейного программирования

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

Максимизировать г = С;Х, + С2Х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]