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


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


42

Таблица 4.2. Правила определения типа оптимизации и ограничений

Целевая функция

Двойственная задача

прямой задачи

Целевая функция

Тип ограничений

Переменные

Максимизация

Минимизация

>

Свободные

Минимизация

Максимизация

<

Свободные

Следующие примеры иллюстрируют правила построения двойственной задачи.

Пример 4.1.1

Прямая задача

Прямая задача в стандартной форме Двойственные переменные

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

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

Xi + 2X2 +Хз < 10,

2xi - хг + Зхз = 8,

Х1, Х2, Хз > 0.

Максимизировать

2= 5x1 + 12X2 + 4хз + Ох*

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

Х1 + 2X2 + Хз + х4 = 10, 2xi - хг + Зхз + 0х4 = 8,

Х1, Х2, Хз, Х4 0.

Двойственная задача

Минимизировать w = 10у, + 8у2

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

у, + 2у2>5, 2ух-у2>\2, у1 + 3у3>4,

у. + 0у, > 0, }

} => (у, > 0, у, - свободная переменная). у,,у2 -свободные]

Пример 4.1.2

Прямая задача Прямая задача в стандартной форме Двойственные переменные

Минимизировать г = 15xi + 12х2 Минимизировать z= 15xi + 12хг + Охз + 0х< при ограничениях при ограничениях

Х1 + 2X2 3, Х1 + 2X2 - Хз + 0X4= 3, /1

2xi - 4x2 < 5, 2xi - 4X2 + Охз + х4 = 5, уг

X1,X2>0. X1, Х2, Хз, Х4>0.

Двойственная задача

Максимизировать w = 3yt + 5у2

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

У, + 2у2<15, 2у,-4у2<12, -уОСилиуО), У20,

у,, у2 - свободные переменные (избыточное условие).



Пример 4.1.3

Прямая задача

Прямая задача в стандартной форме

Двойственные переменные

Максимизировать г = 5xi + 6x2

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

xi + 2x2 = 5, -х1 + 5x2 > 3,

4xi + 7x2 < 8,

xi - свободная,

x2>0.

Подстановка дг, = дг* - х~ приводит к задаче:

максимизировать г = 5дг* - 5дг," + 6х2 при ограничениях

дг,+ - х[ + 2хг = 5,

- д,+ + дг," + 5x2 - хз =3,

4дг* - 4дг," + 7x2 + х4 = 8, дг,+, дг,", х2 > 0.

Двойственная задача

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

Минимизировать w = 5yl + Зу2 + 8у3

у,-у,+4у3>5 1 -у, + у2-4у3>-5\

2у1 + 5у2+7у3>6,

-у2>0у2<0,

У3*0,

у, - свободная переменная,

у2, у, - свободные переменные (избыточное условие).

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

УПРАЖНЕНИЯ 4.1

1. Для задачи из примера 4.1.1 запишите двойственную задачу, предполагая, что определяется не максимум целевой функции, а ее минимум.

2. В примере 4.1.2 сформулируйте двойственную задачу, предполагая, что в прямой задаче этого примера добавлено третье ограничение Зхх + х2 = 4.

3. На основе задачи из примера 4.1.3 покажите, что даже если изменить тип оптимизации (с максимизации на минимизацию целевой функции), то все равно свободным переменным прямой задачи будут соответствовать в двойственной задаче ограничения в виде равенств.

4. Запишите двойственные задачи для следующих прямых задач ЛП.

a) Максимизировать z = -5л:, + 2х2

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



2х, + Зх2 < 5, х„ х2>0.

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

6х, - Зх2 + х3 > 2, Зх, + 4х2 + х3 > 5, х„ х2, х3>0.

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

2х, + х2= 5, Зх,-х2 = 6,

х,, х2 - свободные переменные.

5. Вернитесь к задаче из примера 4.1.1. Применение симплекс-метода к прямой задаче ЛП, записанной в стандартной форме, требует введения искусственной переменной во второе ограничение для получения начального базисного решения. Покажите, что введение искусственной переменной не влияет на построение двойственной задачи, поскольку искусственная переменная прямой задачи порождает избыточное ограничение двойственной задачи.

6. Истинны или ложны следующие утверждения?

a) Задача, двойственная к двойственной, совпадает с исходной прямой задачей.

b) Если в прямой задаче есть ограничение в виде равенства, то соответствующая переменная двойственной задачи обязательно будет свободной.

c) Если в прямой задаче ограничение имеет вид неравенства типа "<", то соответствующая переменная в двойственной задаче будет неотрицательной (неположительной), в зависимости от того, следует в прямой задаче максимизировать или минимизировать целевую функцию.

d) Если в прямой задаче ограничение является неравенством типа ">", то соответствующая переменная в двойственной задаче будет неотрицательной (неположительной), в зависимости от того, следует в прямой задаче минимизировать или максимизировать целевую функцию.

e) Свободная переменная прямой задачи порождает в двойственной задаче ограничение в виде равенства.

7. В следующей таблице приведены правила построения двойственных задач, которые часто приводятся в литературе по исследованию операций и линейному программированию. Покажите, что эти правила являются частными случаями общих правил, приведенных в табл. 4.2.

Задача максимизации

Задача минимизации

Ограничения

Пеоеменные

>

<0

<

>0

Свободная

Пеоеменные

Ограничения

>0

>

<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]