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


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


120

( 0,627296 -0,449746 -0,177550 -0,449746 0,322451 0,127295 ч -0,177550 0,127295 0,050254

Далее вычисляем

C/l = [I-Pr(PPVP](CD/ =

0,627296

-0,449746

-0,177550

0,526680

0,165193 N

-0,449746

0,322451

0,127295

0,778556

-0,118435

v-0,177550

0,127295

0,050254 j

-1,041996

-0,046757,

Цс,, I = д/о, 165193- + (-0,118435)2 + (-0,046757)2 = 0,208571. Отсюда получаем

1 1 IV 2

,3 ЗЗ; 9 7б 0,208571 = (0,261479, 0,384849, 0,353671) Теперь для вычисления X, имеем

х (0,165193, -0,118435, -0,046757)7 =

0,263340

0 \

0,261479s

0,068858"

0,389328

0,384849

0,149832

ч 0

0,347332,

ч0,35367 1,

0,122841,

1D,Y„,

ID Y

АЖЛ 1 новое

= 0,341531,

( 0,201616 0,438707 0,359677

2 = 0,201615.

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

УПРАЖНЕНИЯ 7.7

1. С помощью программы TORA покажите, что решение преобразованной задачи ЛП, приведенной в конце примера 7.7.2, дает оптимальное решение прямой и двойственной исходных задач. (Совет. Положите М=10 и задайте точность не менее 5 десятичных знаков.)

2. Преобразуйте следующую задачу ЛП к виду, необходимому для применения метода Кармаркара.

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

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

2j/,+J/2<4,



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

4. Выполните три итерации алгоритма Кармакара для решения следующей задачи.

Максимизировать z = Axl + x3+xt

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

-2х1 + 2х2 + х3 - х4 = О, x, + х2 + х3 + х4 = 1, xvx2, х3, х4>0.

5. Выполните три итерации алгоритма Кармаркара для решения следующей задачи ЛП.

Максимизировать г = 2хг + х2

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

х1 + х2< 4, х„ х2>0.

ЛИТЕРАТУРА

1. Bazaraa М., Jarvis J., Sherali М. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Hooker J. Karmarkars Linear Programming Algorithm, Interfaces, Vol. 16, No. 4, pp. 75-90, 1986.

3. Nering E., Tucker A. Linear Programming and Related Problems, Academic Press, Boston, 1992.

Литература, добавленная при переводе

1. Ашманов С. А. Линейное программирование. - М.: Наука, 1981.

2. Гольштейн Е. Г. Теория двойственности в математическом программировании и ее приложения. - М.: Наука, 1971.

3. Гольштейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. - М.: Наука, 1969.

4. Крона Г. Исследование сложных систем по частям - диакоптика. - М.: Наука, 1972.

КОМПЛЕКСНЫЕ ЗАДАЧИ

7.1. Имеем координаты трех точек:

А - (6, 4, 6, -2), В = (4, 12, -4, 8) и С = (-4, 0, 8, 4).

Разработайте процедуру, которая позволяла бы определить, является ли данная точка выпуклой комбинацией заданных точек. С помощью этой процедуры проверьте, будут ли следующие точки выпуклыми комбинациями точек А, В и С.

а) (3,5,4,2),

б) (5,8,4,9).



Комплексные задачи

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

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

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

х, 4- 2х2 < 6, 2х, +хг<8, -хх+х2<1, х,, х2>0.

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

7.3. Интервальное программирование. Рассмотрим следующую задачу ЛП.

Максимизировать z = {СХ L < АХ < U, X > 0},

где L и U - вектор-столбцы констант. Определим вектор Y > 0, такой, что АХ + Y = U. Покажите, что исходная задача эквивалентна следующей.

Максимизировать z = {СХ AX + Y= U,0<Y<U-L,X>0}. Используя показанный прием, решите следующую задачу ЛП.

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

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

20 < х, + 1х2 + Зж3 < 46, 10 < Зх, - х2 + х3 < 20, 18< 2хх + Зх2-х3<35, xvx2, х3>0.

7.4. Рассмотрим следующую целочисленную задачу ЛП, где переменные принимают только значения 0 и 1.

Минимизировать z = {СХ АХ < b, X = (0, 1)}.

Предположим, что известна верхняя граница целевой функции zmili. Введем ограничение

min max {p(b - АХ) + (z,™ - СХ)} > О,

где ц> 0. Это ограничение не нарушает ни одного из ограничений исходной задачи. Покажите, что определение из этого ограничения фактически сводится к решению исходной задачи ЛП. (Совет. В данном случае условие целочисленности X = [0, 1] эквивалентно "непрерывному" ограничению 0 < X < 1. Сформулируйте двойственную задачу.)

7.5. В задаче 7.2 оптимальным решением является хх = 10/3, х2 = 4/3 и г = 38/3. Как будет изменяться оптимальное значение целевой функции в зависимости от параметра 6, если положить хх = 10/3 4- 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]