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


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


114

c) Покажите, что двойственная задача не имеет ограниченного решения.

d) На основе примеров задач из предыдущих упражнений найдите соотношение между свойствами недопустимости и неограниченности прямой и двойственной задач ЛП.

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

Максимизировать z = Ьхх + 12х2 + 4х3

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

2xi -х2 + Зх3 = 2, хх + 2х2 + х3 + хл = 5, Ху7 x2t х3, х4 - 0.

a) Сформулируйте и запишите двойственную задачу.

b) В каждом из следующих случаев сначала проверьте, что приведенный базис В является допустимым для прямой задачи. Затем, используя формулу Y = CSB \ вычислите значения переменных двойственной задачи. Кроме того, определите, является ли данное решение прямой задачи оптимальным.

а)В = (Р4,Р3). в)В-(Р„Р,).

б)В = (Р2,Р3). г) В = (Р,, Р4).

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

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

х, + 4х2 + xt = 8, xv х2, х3, х4>0.

a) Сформулируйте и запишите двойственную задачу.

b) Путем вычисления разностей г. - су для всех небазисных Ру проверьте, что базис В = (Р2, Р3) соответствует оптимальному решению.

c) Найдите оптимальное решение двойственной задачи.

5. Модель ЛП содержит две переменные хг и х2 и три ограничения типа "<". Соответствующие дополнительные (остаточные) переменные обозначены как х3, хА и ху Предположим, что B = (Pj, Р2, Р3)- оптимальный базис, а соответствующая обратная матрица имеет следующий вид.

,0 -1 О В4 = 0 1 о

,1 1 -.

Ниже представлены оптимальные решения прямой и двойственной задач.

Хя*/ = (2,6, 2)т, Y = U/„</2,</3) = (0, 3, 2). Найдите оптимальное значение целевой функции.



6. Докажите следующее соотношение между оптимальными решениями прямой и двойственной задач:

где Св = (с„ с2, .... cj иР, = (au, a2t, атк)т для = 1, 2, п, (ВРД - /-Й элемент вектора В Рк.

7. Запишите задачу, двойственную к следующей.

Максимизировать z = {СХ АХ = b, X - свободные переменные}

8. Покажите, что задача, двойственная к задаче

максимизировать z = {СХ АХ < b, 0<L<X<U< <*>}, всегда имеет допустимое решение.

7.6. ПАРАМЕТРИЧЕСКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

Пусть задача ЛП определена следующим образом.

Максимизировать z = jcx£PjxJ= b, X>oj.

В параметрическом программировании задаются изменения коэффициентов целевой функции и правых частей ограничений. Для этого используются функции С(£) и Ь(£), зависящие от параметра изменения t. Для определенности полагаем, что t > 0.

Основная идея параметрического анализа заключается в следующем. Вначале находится оптимальное решение задачи ЛП при t = 0. Затем на основании условий оптимальности и допустимости симплекс-метода определяется интервал 0 < t < tx значений параметра t, для которых решение, полученное при t = 0, остается оптимальным и допустимым. Значение t, называется критическим. Затем определяются следующие критические значения параметра t и соответствующие им оптимальные допустимые решения. Процесс заканчивается, когда будет найдено такое значение tr, что при любых значениях t > tr последнее решение остается неизменным либо решения не существует.

7.6.1. Параметрическое изменение коэффициентов целевой функции

Пусть Х„ , В, и С„ (0 - элементы оптимального решения, соответствующего

критическому значению tt (вычисления начались при t0 = 0 с оптимальным базисом В0). Далее определяем следующее критическое значение и соответствующий ему оптимальный базис, если он существует. Поскольку изменения в векторе коэффициентов целевой функции влияют только на оптимальность решения, текущее решение Хя = B~b останется оптимальным при t > tt до тех пор, пока будет выполняться условие оптимальности

z.(f) - с jit) = С„ (ОВГР, - c{t) > 0 для всех



Очередное критическое значение tM определяется как наибольшее t, t > tt, при котором выполняются все условия оптимальности.

Отметим, что приведенное неравенство не требует, чтобы вектор С(0 был линейной функцией от t; допустима функциональная зависимость любого вида - как линейная, так и нелинейная. Трудность использования нелинейных функций заключается лишь в том, что численное решение системы неравенств может быть очень трудоемким. (В упражнении 7.6.1.5 рассмотрен случай нелинейной функции.)

Пример 7.6.1

Рассмотрим задачу ЛП.

Максимизировать г = (3 - 60 х, + (2 - 2t) х2 + (5 + 50 х. при ограничениях

х, + 2х2 + х3< 40, Зхх + 2х3<60, х1 + 4х2 < 30,

Здесь С(0 = (3 - 6t, 2 - 2t, 5 + 50, t > 0. Введем дополнительные (остаточные) переменные х4, х5 и х6.

Оптимальное решение при t0 = 0.

Базис

Решение

-1/4

-1/4

Хйо - (х2, х3, х/ = (5, 30, 10f СВо(/) =(2-2t, Ъ + Ы, 0),

i -10

в- =

Условия оптимальности для текущих небазисных векторов Р,, Р4 и Р5 имеют вид {<:„(/)В-Ру - с )}.= о = (4 + Ш, 1 - t, 2 + 3t) > 0.

Таким образом, решение остается оптимальным до тех пор, пока выполняются неравенства

4 + 14t>0,

1 -t>0,

2 + 3t> 0.

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