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


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


78

Глава 9

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Мы рассмотрели задачу линейного программирования, которая состояла в минимизации или максимизации линейной функции при линейных ограничениях. Однако во многих оптимизационных задачах целевая функция, или функции, задающие ограничения, не являются линейными. Такие задачи называются задачами нелинейного программирования.

9.1. Основные понятия

В общем виде задача нелинейного программирования может быть записана в виде

тах/(х)(9.1)

8тМ<Ь, x = (xi,...,x).

Функция /х) называется целевой функцией, а неравенства gl{x)<bi , / = l,...,w называются ограничениями задачи.

Определение. Множество точек х, удовлетворяющих ограничениям задачи (9.1), называется допустимым множеством задачи.

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

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

f(x*)>f(x ),

где X - произвольная точка из допустимого множества задачи. В теории нелинейной оптимизации выделяют понятие локального максимума (локального минимума).



Определение. Точкой х* = (х*1,...,л:*„) из допустимого множества называется точка локального максимума, если существует некоторое число Е > О, такое, что для любой допустимой точки х =, такой, что

X; -Xi

<Е, / = !,...,/?, выполняется f(x )> f(x ).

Разницу между глобальным и локальным максимумами легко видеть на рис. 9.1.

Рис. 9.1

Точки Ал В являются точками локального максимума, точка С является точкой глобального максимума.

9.2. Выпуклые и вогнутые функции

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

Определение. Функция /(xi,...,x„) называется выпуклой на некотором выпуклом множестве S, если для любых двух точек X eS и х" eS соотношение

/(схЧ (1 - с) X") < с/(х) + (1 - c)f{x")

выполняется для всех с: 0<с<1.

графический пример выпуклой функции изображен на рис. 9.2.

Для задачи максимиза ции вогнутой функции на выпуклом множестве любая точка локального максимума является и точкой глобального максимума.

Для задачи минимизации выпуклой функции на выпуклом множестве любая точка локального минимума является и точкой глобального минимума.



cf(x)(\-c)f(x) f{cx(\-c)x)

cx +{\- c)x X

Puc. 9.2

Определение. Функцияназывается вогнутой на некото-

ром выпуклом множестве S", если для любых двух точек х и х" б .5 соотношение /{сх + (1 - с) х") < с/(х) + (1 - с) /(х") выполняется для

всех с: О < с < 1.

Графический пример вогнутой функции изображен на рис. 9.3.

f{cx +{\-с)х )

с/{х)л-{\-с)/{х )

сх + (1 - с)х

Рис. 9.3

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

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

Теорема. Пусть рассматривается задача максимизации вогнутой функции Дх) на выпуклом множестве S. Тогда любая точка локального максимума является и точкой глобального максимума.

Теорема. Пусть рассматривается задача минимизации выпуклой функции Дх) на выпуклом множестве S. Тогда любая точка локального минимума является и точкой глобального минимума.

Рассмотрим далее критерии выпуклости и вогнутости функций. Введем некоторые дополнительные определения.

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