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


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


5

1.4. Анализ классическими методами задачи линейного программирования

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

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

Как известно, при нахождении максимума на отрезке [а, Ь] дифференцируемой функции / (х) одной переменной необходимо вначале вычислить первую производную fix), затем найти все решения xi,..., х, уравнения f(x)=0, далее вычислить все значения/"(xi),...,/"(х,), Да), Дй) и выбрать из них набольшее. Уже в этом простейшем случае могут возникнуть трудности, например, с разрешимостью уравнения f(x)= О, или может оказаться, что число решений этого уравнения очень велико и тогда возникает вопрос, каким образом наиболее эффективно организовать перебор. Если же речь идет о функции нескольких переменных, то положение еще более осложняется. Пусть X = (xi,...,Xr,) есть некоторая точка п-мерного пространства аХ- замкнутое подмножество этого пространства иДх)- функция п переменных, заданная на множестве X. Требуется найти максимум дифференцируемой функции Дх) на множестве X. Попытаемся использовать для решения этой задачи методы классического анализа. Рассмотрим множество точек х(9) 77-мерного пространства, координаты которого имеют вид:

Xl(Q) = Xi + Х2(е) = Х2" + 051, ...,

x„{Q) = x„ + Qs„iQ>0).

Геометрически множество таких точек представляет собой луч с началом в точке (xi,...,x„), направление которого совпадает с вектором (1,..., Sn). Будем считать, что

Зафиксировав направление s = {si, 52,..., s) и увеличивая число 9, начиная с нуля, можно рассмотреть изменение функции Дх1(9), Х2(9), ....,Хг(9)). Локальное поведение функции Дх) вдоль направления s будет определяться производной по О в точке 0=0. Учитывая, что при 22

- о



0 = 0 значение х(0)= х", вычисляя производную функции fix), используя правило дифференцирования сложной функции:

/;(х,(0),Х2(0),...,х„(0)) =

дх0X2ох

ЙХ ЙХ28х

Величина

йх:дх2дх

называется производнойДх) в точке х по направлению s = (su..., Sn).

Вектор (----) называется градиентом функции/х) в точ-

ке и обозначается gradx). Используя понятие скалярного произведения из линейной алгебры получим, что:

/(/) = (grad/(/),s).

где в правой части равенства записано скалярное произведение вектора s и вектора grad/x).

Далее один из основных фактов математического анализа состоит в том, что значение функции У(х)=У(х1,..., х,) в окрестности точки (xi,..., Хг) растет быстрее всего, если в качестве направления выбрать градиент функции Дх) в точке х. Если в точке х достигается локальный максимум функции Дх), то в этой точке нет направления, вдоль которого функция возрастает. Поэтому необходимым условием максимума функции Дх) во внутренней точке х множества X является равенство градиента grad f (х) нулевому вектору. Обращаем внимание, что все предыдущие рассуждения корректны лишь для случая, когда х является внутренней точкой, т.е. когда из точки х можно хотя бы немного сдвинуться по любому направлению, не выходя за пределы множествах

Окончательно по аналогии с функцией одной переменной получим: для нахождения максимума функции/х) на множестве X надо найти все

решения х = (х i,..., х„)(/ = 1,..., системы уравнений= О



/= 1, далее вычислить значения Дл:),..., Дх*) и все значения Дх) на границе множества затем выбрать среди них максимальное.

Из сказанного видно, как усложняется решение задачи для случая функции многих переменных: даже если удается получить все решения уравнения grad Дх)= О и найти внутренние локальные максимумы функции Дх), надо еще вычислить и все максимумы на границе множествах Учитывая, что при п > 1 граница множества X (за исключением самых простых случаев) состоит из бесконечного числа точек, общего рецепта отыскания всех экстремальных значений функции Дх) на границе нет. В частном случае, если все ограничения в задаче носят характер равенств, может быть использован метод множителей Лагранжа, но и здесь вычислительные проблемы остаются.

Проанализируем стандартную задачу линейного программирования. Градиент целевой функции равен (ci,..., сД и если не все Cj равны нулю, то у функции Дх) нет локальных максимумов на внутренних точках множествах.

Следовательно, основные вычислительные проблемы решения задач линейного программирования состоят в определении границы множества X, которая в явном виде нам не задана, и организации вычислений значений целевой функции с\ х„, +...+, с„х„ на границе множествах, чтобы найти оптимальное решение.

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