 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Задачи и целевой функции
Для решения задач математического программирования существенно важно знать:
1) Выпукло или не выпукло множество допустимых решений задачи;
2) Является ли целевая функция выпуклой или вогнутой или она не относится ни к тому, ни к другому классу.
Напомним необходимые определения. Говорят, что множество выпукло, если оно вместе с любыми своими точками А и В содержит и все точки отрезка АВ. На рис.1 представлены примеры выпуклых множеств точек плоскости. Примерами выпуклых множеств в пространстве могут служить сфера, пирамида, призма и т. д.
Рис. 1.
На рис.2. изображены примеры невыпуклых множеств. В невыпуклом множестве можно указать хотя бы две точки, такие, что не все точки отрезка АВ принадлежат рассматриваемому множеству. Как пример невыпуклого множества в пространстве можно указать тор
Рис.2
Область является выпуклой, если отрезок прямой, соединяющей любые две точки области, принадлежит этой области. Следовательно, если 
и х2 находятся в этой области, то любая точка вида (θ + (1 — θ ) 
, где 0 < θ < 1, находится в этой же области. На рис.3. а изображена выпуклая область, а на рис.3 б — невыпуклая.
Рис. 3.
Функцию у = f (х)одной переменной будем называть выпуклой, если отрезок, соединяющий две любые точки её графика, принадлежит графику или расположен выше его (рис.4.).
Функциявогнута, если отрезок, соединяющий две любые точки графика, принадлежит графику или расположен ниже его (рис.5.).
Рис. 3.
Рис.4. Рис.5.
Аналогично можно сформулировать определения понятий вогнутой и выпуклой функций нескольких переменных. Мы говорим, что гиперповерхность Z = f (х1, х2,..., хп) выпуклая, если отрезок, соединяющий две ее любые точки, лежит на поверхности или выше ее. Гиперповерхность Z = f (х1, х2,..., хп) вогнута, если отрезок, соединяющий две ее любые точки, лежит на поверхности или ниже ее.
Локальный и глобальный минимум функция f(х).
Функция f(х) имеет локальный минимум в точке х0, если существует некоторая положительная величина δ, такая, что если | х - х0| < δ, то f(х) ≥ f(х0) т. е. если существует окрестность точки х0, такая, что для всех значений х в этой окрестности f(х) больше f(х0) Функция f(х) имеет глобальный минимум в точке х*, если для всех х справедливо неравенство f(х) ≥ f (х*). На рис.6. дано графическое представление функции f (х), которая имеет локальный минимум в точке х0 и глобальный минимум в точке х*.
y
Рис.6.
Классический подход к задаче нахождения значений х0 и х* состоит в поиске уравнений, которым они должны удовлетворять. Представленная на рис. функция и ее производные непрерывны, и видно, что в точках х0 и х* производная f''(х), (градиент функции) равна нулю. Следовательно, х0 и х* будут решениями уравнения f''(х) = 0. Точка хт, в которой достигается локальный максимум, и точка хc, в которой имеется точка горизонтального перегиба функции, также удовлетворяют уравнению f''(х) = 0.. Следовательно, уравнение f''(х) = 0 является только необходимым условием экстремума, но не является достаточным условием минимума. Заметим, однако, что в точках х0 и х* производная f''(х) меняет знак с отрицательного на положительный. В точке хт знак
меняется с положительного на отрицательный, в то время как в точке хс он не меняется. Следовательно, производная в минимуме является возрастающей функцией, а поскольку степень возрастания f''(х) измеряется второй производной, можно ожидать, что f'''(х0) > 0, f'''(х*) > 0, тогда как f''' (хт) < 0. Если, однако, вторая производная равна нулю, ситуация остается неопределенной. Полученные выше результаты могут найти надежное обоснование, если рассмотреть разложение функции f(х) в ряд Тейлора в окрестности точки х0 (или х*, или хт), что, конечно, требует непрерывности функции f (х), и ее производных:
+ 
) + 
(1.1)
Если в точке х0 достигается минимум, то левая часть (1.1) будет неотрицательной для любого достаточно малого h(|h| < δ). Следовательно, первая производная f''(х0) должна быть равна нулю, и это является достаточным условием. Если бы она была положительной, то достаточно малое отрицательное значение𝐡 делало бы правую часть (1.1) отрицательной, а если бы она была отрицательной, то достаточно малое положительное значение 
делало бы правую часть отрицательной. Так как в следующем члене (1.1) всегда 2 > 0, то, если f'''(х0) > 0, в точке х0 достигается минимум. Если 
и f'''(хm) < 0,, то из аналогичных соображений в точке хm достигается
максимум. Для определения различия между локальным и глобальным минимумами необходимо сравнить значения функций f(х0) и f (х*).
Поиск по сайту: