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


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


270

Основой метода линейных комбинаций является градиентный метод наискорейшего подъема (раздел 21.1.2). Известно, что в этом методе движение по направлению градиента может вывести за пределы области допустимых решений. Кроме того, в точке условного оптимума градиент не обязательно обращается в нуль. Поэтому метод наискорейшего подъема необходимо модифицировать в целях его применения к рассматриваемой задаче с ограничениями.

Пусть X* - допустимая точка, полученная на fe-й итерации. Разложим целевую функцию /(X) в окрестности точки X* в ряд Тейлора. В результате получим

/(X)«/ХХ*) + V/(X*)(X - X*) = /(X*) - V/XX*)X* + V/XX*)X. Нам необходимо определить допустимую точку X = X", в которой достигается максимум функции /XX) при выполнении (линейных) ограничений задачи. Так как /XX ) - V/XX )Х - постоянное слагаемое, задача определения X сводится к решению следующей задачи линейного программирования:

максимизировать wk(X) = Vf(Xk)X

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

АХ<Ь,Х>0.

Так как целевая функция wk определяется градиентом функции /XX) в точке X*, улучшение имеющегося решения может быть обеспечено лишь тогда, когда шДХ") > шДХ*). Из разложения Тейлора следует, что выполнение этого условия не гарантирует, что /XX*) > /(X*), так как X* не обязательно находится в малой окрестности точки X*. Однако при выполнении условия шДХ") > wk(X.k) на отрезке (X*, X") должна существовать такая точка X**1, что /XX**1) > /XX*). Следовательно, задача сводится к определению такой точки X**1. Найдем эту точку следующим образом:

Xk" = (1 - r)Xk + гХ* = Хк + г(Х* - Хк), 0 < г < 1.

Отсюда следует, что точка X**1 является линейной комбинацией точек X* и X*. Так как X* и X* - точки выпуклой области допустимых решений, точка X**1 также является допустимой. Если сравнить эту процедуру с методом наискорейшего подъема (подраздел 21.1.2), параметр г можно рассматривать как длину шага.

Точка X**1 определяется из условия максимума функции /XX). Так как X*41 зависит лишь от переменной г, то Х*и определяется путем максимизации функции

h(r) = f[Xk + r(X* - Xk)].

Процедура повторяется до тех пор, пока на fe-й итерации не будет выполнено условие м>Л(Х*) < шДХ*). В этой точке дальнейшее улучшение существующего решения невозможно, процесс вычислений завершается, точка X* считается наилучшим решением.

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



Пример 21.2.7

Рассмотрим задачу квадратичного программирования из примера 21.2.3.

Максимизировать z = 4х, + бх, - 2х] - 2х,х2 - 2х\

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

х, + 2х, < 2,

х,,х2>0.

Пусть Х° = (1/2, 1/2) - начальная точка, которая является допустимой для рассматриваемой задачи. Имеем

УДХ) = (4 - 4х, - 2х2, 6 - 2х, - 4х2).

Итерация 1.

удх°) = (i,3).

Соответствующая задача линейного программирования сводится к максимизации функции и>, =х, + Зх2 с учетом ограничений исходной задачи. Ее оптимальным решением есть точка X* = (0, 1). Значения функции и>, в точках Х° и X* равны 2 и 3 соответственно. Следовательно, новая точка ищется в виде

х=!.- + г

Максимизация функции

2 2

*w-4 2 2

дает г = 1. Таким образом, X1 = (0, 1) и ДХ1) = 4. Итерация 2.

УДХ1) = (2, 2).

Целевой функцией новой задачи линейного программирования является w2 = 2xt + 2x2. Оптимальное решение этой задачи - X = (2, 0). Поскольку значения w2 в точках X1 и X* равны 2 и 4, следует найти новую точку. Рассматриваем точку

X2 = (0, 1) + г[(2, 0) - (0, 1)] = (2г, 1 - г).

Максимизация функции

А(г) =Д2г, 1 - г)

дает г = 1/6. Таким образом, X2 = (1/3, 5/6), при этом ДХ2) = 4,16. Итерация 3.

УДХ2) = (1,2).

Здесь целевая функция имеет вид w3 = х, + 2х2. Оптимальным решением задачи линейного программирования будут альтернативные точки X* = (0,1) и X* = (2, 0). Значение и>3 в обоих случаях совпадает со значением w3 в точке X2. Следовательно, улучшить имеющееся решение невозможно. Получено приближенное оптимальное решение задачи: X2 = (1/3, 5/6) сДХ2) = 4,16. В данном случае оно совпадает с точным оптимумом.



УПРАЖНЕНИЕ 21.2.5

1. Решите следующую задачу методом линейных комбинаций.

Минимизировать /(X) = х3 + х3 -Зх,х,

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

Зх, +х2<3, 5х, - Зх2 < 5, х,, х2 > 0.

21.2.6. Алгоритм последовательной безусловной максимизации

В этом разделе приводится описание градиентного метода более общего вида. Предполагается, что целевая функция f(X) является вогнутой, а каждая функция ограничений g/X) - выпуклой. Кроме того, допустимая область задачи должна содержать внутренние точки. Это исключает как явное, так и неявное использование ограничений в виде равенств.

Алгоритм последовательной безусловной максимизации основан на преобразовании исходной задачи с ограничениями в эквивалентную задачу без ограничений. Процедура в некоторой степени подобна применению метода множителей Лагранжа. Преобразованная задача затем может быть решена методом наискорейшего подъема (раздел 21.1.2).

Введем новую целевую функцию

p(x,,) = /(x)+/(x-7iFT-I-L .

Ui*,(X) >i*J

где t - неотрицательный параметр. Наличие второй суммы обусловлено учетом требований неотрицательности переменных исходной задачи, которые следует записать в виде -х<0 для их согласования с остальными ограничениями вида £»(Х)<0. Поскольку функция g/X) является выпуклой, 1/gX.) будет вогнутой. Отсюда следует, что р(Х, t) является вогнутой функцией от переменных X. Следовательно, функция р(Х, t) имеет единственный максимум. Поэтому решение исходной оптимизационной задачи с ограничениями эквивалентно максимизации функции р(Х, t).

Выполнение алгоритма начинается с произвольного выбора начального неотрицательного значения t. Начальная точка Х° выбирается в качестве первого пробного решения. Эта точка должна быть внутренней точкой области допустимых решений, т.е. не должна находиться на ее границе. При заданном значении t оптимальное решение (точка максимума) функции р(Х, t) находится методом наискорейшего подъема.

Точка, представляющая новое решение, всегда будет внутренней, ибо если решение находится близко к границе области, то по крайней мере одна из функций l/gt(X) или -1/Xj примет очень большое отрицательное значение. Поскольку рассматривается задача максимизации р(Х, t), то такие решения автоматически исключаются. Основной результат состоит в том, что последовательно получаемые решения всегда будут внутренними точками допустимой области. Следовательно, исходная задача может всегда рассматриваться как задача без ограничений.

Когда получено оптимальное решение, соответствующее заданному значению t, выбирается новое значение t, и процесс вычислений (методом наискорейшего подъема) повторяется. Если t - текущее значение t, то следующее значение t" необходимо выбирать так, чтобы выполнялись неравенства 0 < /* < t.

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