Задачи и целевой функции

Выпуклость множества допустимых решений

Для решения задач математического программирования существенно важно знать:

1) Выпукло или не выпукло множество допустимых решений задачи;

2) Яв­ляется ли целевая функция выпуклой или вогнутой или она не относится ни к тому, ни к другому классу.

Напомним необходимые определения. Говорят, что множество выпукло, если оно вместе с любыми своими точками А и В со­держит и все точки отрезка АВ. На рис.1 представлены примеры выпуклых множеств точек плоскости. Примерами выпуклых множеств в пространстве могут служить сфера, пира­мида, призма и т. д.

Рис. 1.

Область является выпуклой, если отрезок пря­мой, соединяющей любые две точки области, принадлежит этой области. Следовательно, если и х₂ находятся в этой области, то любая точка вида (θ + (1 — θ ), где 0 < θ < 1, находится в этой же области. На рис.2. а изображена выпуклая область, а на рис.2 б — невыпуклая.

Рис. 2.

На рис.3. изображены примеры невыпуклых множеств. В невыпуклом множестве можно указать хотя бы две точки, такие, что не все точки отрезка АВ принадлежат рассматри­ваемому множеству. Как пример невыпуклого множества в про­странстве можно указать тор.

Рис. 3.

Функцию у = f (х) одной переменной будем называть выпуклой, если отрезок, соединяющий две любые точки её графика, при­надлежит графику или расположен выше его (рис.4.).

Функция вогнута, если отрезок, соединяющий две любые точки графика, принадлежит графику или расположен ниже его (рис.5.).

Рис.4. Рис.5.

Аналогично можно сформулировать определения понятий вогнутой и выпуклой функций нескольких переменных. Мы го­ворим, что гиперповерхность Z = f (х_1, х₂,..., х_п) выпуклая, если отрезок, соединяющий две ее любые точки, лежит на поверхности или выше ее. Гиперповерхность Z = f (х_1, х₂,..., х_п) вогнута, если от­резок, соединяющий две ее любые точ­ки, лежит на поверхности или ниже ее.

Локальный и глобаль­ный минимум функция f(х).

Функция f(х) имеет локальный минимум в точке х₀, если существует не­которая положительная величина δ, такая, что если | х - х₀| < δ, то f(х) ≥ f(х₀) т. е. если существует окрестность точки х₀, такая, что для всех зна­чений х в этой окрестности f(х) больше f(х₀) Функция f(х) имеет глобаль­ный минимум в точке х*, если для всех х справедливо неравенство f(х) ≥ f (х^*). На рис.6. дано графическое представление функции f (х), которая имеет локальный минимум в точке х₀ и глобальный минимум в точке х*.

Рис.6.

Классический подход к задаче нахождения значений х₀ и х* состоит в поис­ке уравнений, которым они должны удовлетворять. Представленная на рис. функция и ее производные непрерывны, и видно, что в точках х₀ и х* производная f''(х), (градиент функции) равна нулю. Следовательно, х₀ и х* будут решениями уравнения f''(х) = 0. Точка х_т, в которой достигается локальный максимум, и точка х_c, в ко­торой имеется точка горизонтального перегиба функции, также удовлетворя­ют уравнению f''(х) = 0.. Следовательно, уравнение f''(х) = 0 является только необходимым условием экстремума, но не является достаточным условием мини­мума. Заметим, однако, что в точках х₀ и х* производная f''(х) меняет знак с отрицательного на положительный. В точке х_т знак

меняется с положитель­ного на отрицательный, в то время как в точке х_с он не меняется. Следова­тельно, производная в минимуме является возрастающей функцией, а по­скольку степень возрастания f''(х) измеряется второй производной, можно ожидать, что f'''(х₀) > 0, f'''(х^*) > 0, тогда как f''' (х_т) < 0. Если, однако, вторая производная равна нулю, ситуация остается неопре­деленной. Полученные выше результаты могут найти надежное обоснование, если рассмотреть разложение функции f(х) в ряд Тейлора в окрестности точки х₀ (или х*, или х_т), что, конечно, требует непрерывности функции f (х), и ее производных:

+ меняет знак с положительного на отрицательный, а при

х = 1 - с отрицательного на положительный. Следовательно, в точке х = 1/3 дости­гается максимум, а в точке х = 1 - минимум. Этот пример может быть решен более простым способом, если вычислить вторую производную f''' = 6х — 4: f'''1/3) = -2, т. е. отрицательна, и при х = 1/3 достигается максимум; f''' (1) = 2, т. е. положительна, и при х = 1 достигается минимум. Неоднозначность, возникающую при f''' (*) ⁼ 0, можно разрешить, увели­чив количество членов в формуле разложения в ряд Тейлора

:

+) +) (нескольких переменных).

Необходимое условие экстремума. Если х*() - точка локального безусловного экстремума непрерывно дифференцируемой в точке х* функции у = f (), то все её частные производные первого порядка в этой точке равны нулю, то есть

или в векторной форме Точки, удовлетворяющие условию (2.1), называются стационарными.

Достаточное условие экстремума. Если в стационарной точке х* функция f(x) дважды дифференцируема и матрица её вторых производных Н(х*) (матрица Гессе) положительно определена (то есть все её главные миноры), то есть и Н(х*) > 0, то х*- точка локального минимума. (Напомним, что для прямоугольной матрицы А_mn определитель квадратной матрицы К-го порядка называется минором К-го порядка матрицы А_mn)

Матрица Гессе имеет вид:

Пример. Исследовать на экстремум функцию

.

Решение. Запишем необходимые условия экстремума:

Проверим достаточные условия. Матрица Гессе имеет вид:

,

то есть Так как то H(x*)>0 и точка x*=(0,0) является точкой локального минимума.

Для того чтобы найти, является ли данная квадратичная форма положительно определенной, мож­но воспользоваться теоремой, которая формулируется следующим образом. Для положительной определенности квадратичной фор­мы необходимо и достаточно, чтобы были выполнены условия Сильвестра:

Случай двух переменных. Достаточным условием минимума является по­ложительность главных миноров первого и второго порядков.

Случай трех переменных .Достаточным условием минимума для функции трех переменных является положительность всех трех миноров

Достаточным условием максимума для функции трех переменных является положительность четных мино­ров и отрицательность нечетных миноров

Аналогичным образом могут быть получены достаточные условия и при большем числе переменных.

Дата добавления: 2014-01-04