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


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


112

Отсюда В"Р23 = (1/10, 0, 9/10f. Поскольку Хв = (р22, р„, = (14/25, 1, 11/25)7", из базисного решения следует исключить искусственную переменную х7.

Находим новый базис и новую обратную матрицу В"1 (проверьте!).

в =

Новое базисное решение равно

Хв = (Р22, Р„, Р2/ = В-(40, 1, If = (23/45, 1, 22/45f, Св = (C2Y22, C.Y,,, C2Y23) = (50, 60, 5).

Итерация 4

Подзадача 1 (j = 1). wl = -2хг - 4х2 + 48. Получаем z* - с\ = wt = 0 . Подзадача 2 (j = 2). w2 = 0xt + 0х5 + 48 = 48.

Небазисная переменная хь. г5 - с5 = 1. Отсюда следует, что решение, полученное на третьей итерации, оптимально.

С помощью обратной подстановки вычисляем оптимальное решение исходной задачи, х; = (*„ */ = puYu = 1(0, 12f = (0, 12f, X, = (х3, х4) = P22Y22 + p23Y23 =

= - (50. Of +-(5, Of = (28, 0)T. 45 45

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

УПРАЖНЕНИЯ 7.4.1

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

х, + 2х2 < 6, 2х, + х2 < 8, -х, +х2< 1, *2<2, xv х2>0.



2х, + х2 < 2, Зх, + 4х2> 12, х„х2>0.

х,-х2<10,

2х,<40,

х„х2>0.

2. В примере 7.4.1 крайние точки подпространств {X, = b„ Х,>0) и {Х21 D2X2 = b2, Х2 > 0} можно найти графически. Используйте эту информацию, чтобы сформулировать в явном виде главную задачу. Затем покажите, что применение к главной задаче модифицированного симплекс-метода порождает такую же последовательность вводимых в базис переменных p.s, как и последовательное решение отдельных подзадач 1 и 2.

3. Дана следующая задача линейного программирования.

Максимизировать z = х, + Зх2 + 5х3 + 2х4

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

2х, + х2 < 9,

х, + 4х2 < 8,

5х, + Зх2 + 4х3 > 10,

х3 - 5х4 < 4,

х3 + х4<10,

Xj, Х2, Х3, Х4 0.

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

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

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

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

х, + х2 + х3 + х4 + х5 + х6 < 50,

х, + х2< 10,

х2<8,

5х3 + х4<12,

х5 + х6>5,

х5 + 5х6 < 50,

х,, х2, х3, х4, х5, х6 > 0.

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

Минимизировать z = 5х, + Зх2 + 8х3 - 5х4



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

х, + х2 + х3 + х4 > 25, 5х, + х2 < 20, 5Xj - х2> 5, х3 + х4 = 20,

1 "2* *3 "4 - "

7. Решите следующую задачу методом декомпозиции.

Минимизировать z = 10yi + 2у2 + 4у3 + 8у4 + уъ при ограничениях

Ух + 4(/2 - у3 > 8, 2у, + </2 + </3>2, Зу, + г/4 + i/5 > 4, + 2у4-(/6>Ю,

<Л.</2> 3 У4>У0-

(Совет. Рассмотрите сначала задачу, двойственную к данной.)

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

Минимизировать wj = zl-cJ = (CsRAy - С;)Х; + СУ

Здесь матрица R состоит из первых г столбцов матрицы В"1, а V - ее (г + у)-й столбец.

7.5. ДВОЙСТВЕННОСТЬ

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

7.5.1. Матричное представление двойственной задачи

Пусть прямая задача ЛП с т ограничениями и п переменными уже записана в стандартной форме.

Максимизировать z = СХ

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

АХ = Ь, Х>0.

Обозначим через Y = (yv у2, ут) вектор переменных двойственной задачи. В соответствии с правилами, представленными в табл. 4.2, получаем следующую двойственную задачу.

Минимизировать w = Yb

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