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


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


46

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

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

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

х, + 2хг + х3 + х4 = 30, Зл + гл + хбО, х, + 4х2 + х6 = 20, х,, х2, х3, х4, х5, х6 > 0. Проверьте оптимальность и допустимость следующих базисных решений.

(I -1/2 0)

а) Базисные переменные (х4, х3, х6), обратная матрица =

0 1/2 0 0 0 1

Ь) Базисные переменные (х2, х3, х,), обратная матрица =

с) Базисные переменные (х2, х3, х6), обратная матрица =

1/4 -1/8 1/8 4

3/2 -1/4 -3/4

1-1 1/2 1/2,

1/2 -1/4 0)

0 1/2 0

-2 1 1

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

Минимизировать z - 2х, + х2

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

Зхг + х2 - х3 = 3, 4х, + Зх2 - х4 = 6, х, + 2х2 + х6 = 3, л-,, х2, х3, х4, х5 0.

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

3/5 -1/5 0"

Базисные переменные (хр х2, х6), обратная матрица = -4/5 3/5 0

[ 1 -11,

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

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

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

х, + 2х2 + х3 + х4 = 10, 2х,-х2 + 3х3 = 2, x,, х2, х3, х4 0.

а) Найдите наилучшее решение среди следующих базисных допустимых решений.

(\ -1/3

<° i/з/

2/5 -1/5 .1/5 2/5 У

i) Базисные переменные (х4, х3), обратная матрица = и) Базисные переменные (х2, х,), обратная матрица =



Ш) Базисные переменные (х2, х,), обратная матрица =

Ь) Присутствует ли среди них оптимальное решение? 6. В следующей таблице представлено оптимальное решение задачи максимизации с тремя ограничениями типа "<" и неотрицательными переменными х, и х2. Переменные х3, х4 и xs являются дополнительными (остаточными) переменными, соответствующими ограничениям задачи. Двумя различными способами, используя целевые функции прямой и двойственной задач, найдите оптимальное значение целевой функции исходной задачи.

Базис

Решение

7. Рассмотрите следующую задачу ЛП.

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

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

л:, + 5х2 + 2х3 <Ь„

*i 5х2 ~ &хг Ь2>

х„ х2, ха>0.

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

Базис

Решение

Константы аЬ, с, d и е можно найти на основе данных исходной задачи и условий оптимальности и допустимости решения, представленного в симплекс-таблице.

a) Найдите значения правых частей неравенств исходной задачи, т.е. константы Ь, и Ь2.

b) Найдите значения констант а, Ь, с, d, е.

c) Найдите оптимальное решение двойственной задачи. 8. Дана следующая задача ЛП.

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

х, + х2 + х3 = 4, х, + 4х2 + х4 = 8, х„ х2, х3, х4>0.

С помощью двойственной задачи проверьте, что базисное решение (х,, х2) не оптимально.

3/7 -\т

1/7 2/7 J *



4.2.5. Значения целевых функций прямой и обратной задач

В отношениях двойственности задач ЛП, если одна задача является задачей максимизации, то вторая обязательно является задачей минимизации. С этой точки зрения существует такое соотношение между значениями целевых функций двух задач.

Для любой пары допустимых решений прямой и двойственной задач

Значение целевой функции (Значение целевой функции в задаче максимизации ) в задаче минимизации )

В точке оптимума это соотношение принимает вид строгого равенства. Отметим, что в этом соотношении не указывается, какая задача прямая, а какая двойственная - здесь важен только тип оптимизации.

Пример 4.2.3

В примере 4.2.1 прямая и двойственная задачи имеют допустимые решения х, = 0, х2 = 0, х3 = 8/3 и у, = 6, у2 = 0. Для этих решений значения целевых функций соответственно равны г =32/3 и w = 60. Для оптимальных решений х, = 26/5, х2 = 12/5, х3 = 0 и у, = 29/5, у2 = -2/5 имеем z = w = 54,8. Таким образом, приведенные значения целевых функций подтверждают сформулированное соотношение.

Из соотношения следует, что для всех допустимых решений прямой и двойственной задач значения целевой функции задачи минимизации всегда будут верхним пределом значений целевой функции задачи максимизации. Таким образом, итерационное решение задачи максимизации ведет к возрастанию значений целевой функции, а итерационное решение задачи минимизации - к ее убыванию. В итоге, при успешном завершении процессов вычисления прямой и двойственной задач приходим к точке "равновесия", где значения целевых функций задач максимизации и минимизации становятся равными.

УПРАЖНЕНИЯ 4.2.5

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

a) Минимизировать г = 5л:, + 2х2 при ограничениях

л:,-л:2>3, 2л:, + 3лг2>5, л:,, лс2>0.

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

л:, + 2х2 + х3 = 3, 2л:, - х2 = 4, л:,, х2, х3>0.

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

х, -х2<10, 2л:, <40, л:,, л:2>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]