Выпуклое множество - подмножество евклидова пространства содержащей отрезок, соединяющий любые какие две точки этой множества.
Определение
Другими словами, множество называется выпуклой, если:
То есть, если множество X вместе с любыми двумя точками, которые принадлежат этому множеству, содержит отрезок, их соединяющий:
В пространстве выпуклыми множествами будут прямая, полупрямой, отрезок, интервал, одноточечный множество.
В пространстве выпуклым будет само пространство, любое его линейный подпространство, шар, отрезок, одноточечный множество. Также, выпуклыми будут такие множества:
- гиперплоскости H p? с нормалью p :
- полупространства на которые гиперплоскости разделяет пространство:
Все перечисленные множества (кроме пули) является частным случаем выпуклой множества полиэдры.
Свойства выпуклых множеств
- Пересечение выпуклых множеств является выпуклым.
- Линейная комбинация точек выпуклой множества выпуклая.
- Выпуклая множество содержит любую выпуклую комбинацию своих точек.
- Любую точку n -мерного евклидова пространства с выпуклой оболочки множества можно представить как выпуклую комбинацию не более n +1 точек этого множества
Рассмотрим n
- мерное евклидово пространство и пусть 
точка в этом пространстве.
Рассмотрим две точки 
и , принадлежащие .Множество точек , которые могут быть представлены в виде
(в координатах это записывается так:
отрезком , соединяющим точки и . Сами точки и называются концами отрезка . В случаях n =2 и n =3 это отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при =0 , а при =1 , т.е. при =0 и =1 получаются концы отрезка.
| Пусть в | заданы k точек | . Точка |
где все и называется выпуклой комбинацией точек .
Пусть есть некоторая область в пространстве (другими словами,
| G есть некоторое множество точек из | ). |
Определение. Множество (область) называется выпуклым , если из того, что и следует, что для . Другими словами, G выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.
На этих рисунках "а" и "б" - выпуклые множества, а "в" не является выпуклым множеством, так как в нём есть такая пара точек, что соединяющий их отрезок не весь принадлежит этому множеству.
Теорема 1. Пусть G выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.
Доказательство
Докажем теорему методом математической индукции. При k =2 теорема верна, так как она просто переходит в определение выпуклого множества.
Пусть теорема верна для некоторого k . Возьмём точку и рассмотрим выпуклую комбинацию
| где все | и . |
| Представим | в виде |
Теорема доказана.
Теорема 2. Допустимая область задачи линейного программирования является выпуклым множеством.
Доказательство.
1. В стандартной форме в матричных обозначениях допустимая область G определяется условием
Т.е. x принадлежит G и, следовательно, выпукло.
2. В канонической форме область G определена условиями
Пусть и принадлежат G, т.е.
.
т.е. и, следовательно, G выпукло. Теорема доказана.
Таким образом, допустимая область в задаче линейного программирования является выпуклым множеством. По аналогии с двумерным или трехмерным случаями, при любом n эту область называют выпуклым
| многогранникомв n - мерном пространстве |
Теорема 3. Множество оптимальных планов задачи линейного программирования выпукло (если оно не пусто).
Доказательство
Если решение задачи линейного программирования единственно, то оно выпукло по определению точка считается выпуклым множеством Пусть теперь и два оптимальных плана задачи линейного программирования.
т.е. есть также оптимальный план и, в силу этого, множество оптимальный планов выпукло. Теорема доказана.
Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).
Эту теорему мы даем без доказательства.
Например, многоугольник на рис. 2.1, а - выпуклый, а многоугольник на рис. 2.1, б не является выпуклым (он расположен по обе стороны от прямой ВС).
Общим определяющим свойством, которое отличает выпуклый многоугольник от невыпуклого, является то, что если взять любые две его точки и соединить их отрезком, то весь отрезок будет принадлежать этому многоугольнику. Это свойство может быть принято за определение выпуклого множества точек.
Множество точек называется выпуклым, если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.
Согласно этому определению многоугольник на рис. 2.1, а является выпуклым множеством, а многоугольник на рис. 2.1, б таковым не является, ибо отрезок МЫ между двумя его точками М и./V не полностью принадлежит этому многоугольнику.
 |
Пусть М и N - любые две точки пересечения двух множеств А и В (рис. 2.3). Так как точки М и N принадлежат пересечению множеств, т.е. одновременно и выпуклому множеству А, и выпуклому множеству В, то согласно определению выпуклого множества все точки отрезка МИ будут принадлежать как множеству А, так и множеству В, т.е. пересечению этих множеств. А это и означает, что пересечение данных множеств есть выпуклое множество. ■
Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки.
Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества.
Рис- 2-3 Точка множества называется граничной,
если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему.
Особый интерес в задачах линейного программирования представляют угловые точки.
Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
 |
На рис. 2.4 приведены примеры различных точек многоугольника: внутренней (точки М), граничной (точка И) и угловых (точки А, В, С, Д Е). Точка А - угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка АР, она не является внутренней; точка А - внутренняя для отрезка КЬ, но этот отрезок не принадлежит целиком многоугольнику.
Для выпуклого множества угловые точки всегда совпадают с вершинами многоугольника (многогранника), в то же время для невыпуклого множества это не обязательно. Так, на рис. 2.5 точка А является вершиной невыпуклого многоугольника, но не угловой (она является внутренней для отрезка КЬ, целиком принадлежащего этому многоугольнику).
 |
Множество точек называется замкнутым, если включает все свои граничные точки. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется неограниченным.
Если фигура ограничена только прямыми или их отрезками, то число ее угловых точек конечно; в случае криволинейности границ фигура содержит бесконечно много угловых точек, что позволяет сделать следующее определение.
Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек, называется выпуклым многогранником (многоугольником), если оно ограниченное, и выпуклой многогранной (многоугольной) областью, если оно неограниченное.
До сих пор рассматривались выпуклые множества точек на плоскости и в пространстве. Аналитически такие точки изображаются упорядоченной парой чисел (хь х2) или упорядоченной тройкой чисел (*1, *2, *з)- Понятие точки можно обобщить, подразумевая под точкой (или вектором) упорядоченный набор п чисел Х= (хь XI, ..., хп), в котором числа хх, х2, ..., х„ называются координатами точки (вектора). Такое обобщение имеет смысл, так как если взять какой-либо экономический объект, то для его характеристики двух-трех чисел обычно бывает недостаточно и необходимо взять п чисел, где п > 3.
Множество всех точек Х= (хь х2,..., х„) образ^т п-мерное точечное (векторное) пространство. При п > 3 точки и фигуры «-мерного пространства не имеют реального геометрического смысла и все исследования объектов этого пространства необходимо проводить в аналитической форме. Тем не менее оказывается целесообразным и в этом случае использовать геометрические понятия для облегчения представлений об объектах «-мерного пространства.
Множество X называется выпуклым, если для любых двух его точек A,B ∈ X все точки отрезка также принадлежат множеству X, то есть если для любых двух его точек A,B ∈ X и для любого значения α in точка M = αA + (1 − α)B также принадлежит множеству X: M ∈ X.
Пусть дано X1, ...Xn - выпуклые множества. Обозначим Y =Xi - пересечение выпуклых множеств. Покажем, что Y - выпуклое множество. Для этого покажем, что длялюбых точек A,B ∈ Y и для любого значения α in точка M = αA + (1 − α)B также принадлежит множеству Y: M ∈ Y . Так как Y - суть пересечение выпуклых множеств X1, ...Xn, то выбранные произвольным образом точки A,B принадлежат каждому из этих множеств Xi, i = 1..n. В силу выпуклости каждого из множеств Xi по определению следует, что для произвольно выбранного значения α ∈ точка M = αA+(1−α)B принадлежит каждому из множеств (все они выпуклы и содержат A,B). Так как все множества Xi содержат точку M, то и
пересечение этих множеств также содержит точку M: M ∈ Y . Из последнего включения в силу произвольности A,B ∈ Y и произвольности параметра α ∈ следует выпуклость множества Y , что и требовалось показать.
95. Является ли множество точек , удовлетворяющих условию , выпуклым? Ответ обоснуйте.
Да, очевидно, что это равенство задаёт линейную полуплоскость в R4.
Обоснуем это по оределению:
A = (a1, a2, a3, a4), B= (b1, b2, b3, b4) ∈ X,
удовлетворяющие вышеуказанному неравенству.
Рассмотрим произвольную точку M = αA + (1 − α)B, где α ∈ – произвольное значение параметра. ТогдаM(m1,m2,m3,m4) = αA + (1 − α)B
m1 = αa1 + (1 − αb1)
m2 = αa2 + (1 − αb2)
m3 = αa3 + (1 − αb3)
m4 = αa4 + (1 − αb4)
выполнимости заданного неравенства:
5 + 2m1 + 3m2 − m3 + 5m4 ≥ 0
5 + 2(αa1 + (1 − αb1)) + 3(αa2 + (1 − αb2)) − (αa3 + (1 − αb3)) + 5(αa4 + (1 − αb4)) ≥ 0
Представим 5 = α5+(1−α)5, раскроем и сгруппируем слагаемые для ai и bi. Получим:
α(5 + 2a1 + 3a2 − a3 + 5a4) + (1 − α)(5 + 2b1 + 3b2 − b3 + 5b4) ≥ 0
Так как точки A,B лежат в множестве X, то их координаты удовлетворяют неравенству,
задающему множество. Значит, оба слагаемых неотрицательны в силу неотрицательности
α и 1 − α. Поэтому последнее неравенство выполнено для любых A,B и любого значения
параметра α ∈ . По определению мы показали, что данное множество X является
выпуклым.
96. Является ли множество точек удовлетворяющих условию , выпуклым? Ответ обоснуйте.
Да, очевидно, что это равенство задаёт линейную гиперплоскость в R4.
Обоснуемэто по оределению:
Рассмотрим любые две точки этого пространства
A = (a1, a2, a3, a4), B= (b1, b2, b3, b4) ∈ X
удовлетворяющие вышеуказанному равенству.
Рассмотрим произвольную точку M = αA + (1 − α)B, где α ∈ – произвольное значение параметра. Тогда M(m1,m2,m3,m4) = αA + (1 − α)B
m1 = αa1 + (1 − αb1)
m2 = αa2 + (1 − αb2)
m3 = αa3 + (1 − αb3)
m4 = αa4 + (1 − αb4)
Проверим для точки M(m1,m2,m3,m4) принадлежность к множеству X с помощью
выполнимости заданного равенства:
m1 + 2m2 − 3m3 + 4m4 = 55
(αa1 + (1 − αb1)) + 2(αa2 + (1 − αb2)) − 3(αa3 + (1 − αb3)) + 4(αa4 + (1 − αb4)) = 55
Раскроем скобки и сгруппируем слагаемые для ai и bi. Получим:
α(a1 + 2a2 − 3a3 + 4a4) + (1 − α)(b1 + 2b2 − 3b3 + 4b4) = 55
Так как точки A,B лежат в множестве X, то их координаты удовлетворяют равенству,
задающему множество, то есть (a1 + 2a2 − 3a3 + 4a4) = 55 и (b1 + 2b2 − 3b3 + 4b4) = 55.
Подставив эти равенства в последнее выражение получим:
α55 + (1 − α)55 = 55
Последнее равенство выполнено для любых A,B и любого значения параметра α ∈ . По определению мы показали, что данное множество X является выпуклым.
97. Приведите примеры выпуклого множества: а) имеющего угловую точку; б) не имеющего угловой точки. Может ли не ограниченное выпуклое множество иметь угловую точку? Приведите пример.
а) квадрат имеет 4 угловые точки
б) окружность не имеет угловых точек
в) неограниченное множество может иметь угловые точки: имеет одну угловую точку (0;0)
98. Дайте определение выпуклой оболочки системы точек. Пусть - выпуклая оболочка точек , , , . Принадлежат ли множеству точки: , ? Ответ обоснуйте.
то есть выполнено условие того, что это выпуклая линейная комбинация, а значит X входит в состав выпуклой оболочки. Предположим, что Y входит также в выпуклую комбинацию, тогда все точки отрезка должны входить в линейную комбинацию, но по исходным точкам видно (все они находятся правей прямой x = -1), что вся выпуклая комбинация расположена справа от прямой x =-1, а точка Y - слева, что подтверждает, что ни весь отрезок ни точка Y - не принадлежат выпуклой оболочке.
III. Выпуклые множества и функции 569
3. Все функции одной переменной с постоянной эластичность ю имеют вид (8) (воспользоваться равенством (4)).
4. Функции нескольких переменных с постоянными частными эластичностями - это степенные функции вида
y = Ax1 B 1 x2 B 2 ,...,xN B N .
III. Выпуклые множества и функции
При исследовании экономических явлений математическими методами весьма значительным оказывается такое свойство м ногих множеств и функций, как выпуклость. Характер поведения мн огих экономических объектов связан с тем. что определенные зав исимости, описывающие эти объекты, являются выпуклыми. С выпукл о- стью функций и множеств часто связано существование или е динственность решения экономических задач: на этом же свойст ве основаны многие вычислительные алгоритмы.
Справедливость многих утверждений, относящихся к выпукл ым множествам и функциям, совершенно ясна, они почти очевидн ы. В то же время их доказательство зачастую очень сложно. Поэтому здесь будут изложены некоторые основные факты, связанные с выпу клостью, без доказательств, в расчете на их интуитивную убедит ельность.
1. Выпуклые множества на плоскости
Любая геометрическая фигура на плоскости может рассматр иваться как множество точек, принадлежащих этой фигуре. Одни множества (например, круг, прямоугольник, полоса между параллел ьными прямыми) содержат и внутренние, и граничные точки; другие (например, отрезок, окружность) состоят только из граничных точе к.
Множество точек на плоскости называется выпуклым, если он о обладает следующим свойством: отрезок, соединяющий любые две точки этого множества, целиком содержится в этом множестве (рис. 1).
Примерами выпуклых множеств являются: треугольник, отрезок, полуплоскость (часть плоскости, лежащая по одну сторону от какой-либо прямой), вся плоскость. Другие примеры выпуклых множеств приведены на рис. 2,а. На рис. 2,б приведены примеры невыпуклых множеств.
Множество, состоящее из одной-единственной точки, и пусто е множество, не содержащее ни одной точки, по принятому соглаше нию, также считаются выпуклыми. Во всяком случае, в этих множес твах невозможно провести отрезок, соединяющий какие-то точки э тих множеств и не принадлежащий этим множествам целиком, - в них
570 Математическое приложение
Рис. 1. Отрезок, соединяющий любые две точки выпуклой фигуры, содержится в ней целиком.
Рис. 2. Выпуклые (а) и невыпуклые (б) множества на плоскости.
вообще невозможно выбрать две точки. Поэтому их включение в число выпуклых множеств не приведет к противоречию с опре делением, а для математических рассуждений этого достаточно.
Пересечение, т. е. общая часть двух выпуклых множеств, всегда выпукло: взяв любые две точки пересечения (а они - общие, т. е. принадлежат каждому из пересекающихся множеств) и соедин ив их отрезком, мы легко убеждаемся в том, что все точки отрезка я вляются общими для обоих множеств, так как каждое из них выпукло. Вы - пуклым будет и пересечение любого числа выпуклых множест в.
Важным свойством выпуклых множеств является их отделимость: если два выпуклых множества не имеют общих внутрен них точек, то плоскость можно разрезать по прямой таким образ ом, что одно из множеств будет целиком лежать в одной полупло скости, а другое - в другой (на линии разреза могут располагат ься точки обоих множеств). Отделяющая их прямая в одних случая х оказывается единственно возможной, в других - нет (рис. 3).
Граничная точка любого выпуклого множества сама может ра с- сматриваться как выпуклое множество, не имеющее с исходным множе-
Рис. 3. Отделяющие прямые. Рис. 4. Опорные прямые.
III. Выпуклые множества и функции 571
ством общих внутренних точек, следовательно, она может быть отделена от него некоторой прямой. Прямая, отделяющая от выпуклого множества его граничную точку, называется опорной прямой этого множества в данной точке. Опорные прямые в одних точках контура могу т быть единственными, в других - не единственными (рис. 4).
Введем на плоскости систему декартовых координат х, у. Теперь у нас появилась возможность рассматривать различные фиг уры как множества таких точек, координаты которых удовлетвор яют тем или иным уравнениям или неравенствам (если координат ы точки удовлетворяют какому-либо условию, будем для кратко сти говорить, что сама точка удовлетворяет этому условию).
Упражнение 1
Рассмотрите фигуры, точки которых удовлетворяют неравен ствам: а) y ³ x2 ; á)xy ³ 1; â)xy ³ 1, õ > 0; ã) |õ| + |ó|£ 2;
ä) (õ+1)2 + (ó – 2)2 £ 9. Какие из них выпуклы?
Линейному уравнению ах + by = с удовлетворяют точки прямой. Иными словами, прямая является решением этого уравнения. Решением линейного неравенства
Решением каждого из неравенств является полуплоскость. Р ешение системы - это множество точек, каждая из которых удовл етворяет всем неравенствам системы, т. е. решение системы неравенств - это пересечение всех решений отдельных неравенств, составляющих систему. Полуплоскость - выпуклое множество, а пересече- ние выпуклых множеств всегда выпукло. Таким образом, решение системы (2) - выпуклое множество. На рис. 5 показано решение системы неравенств
ïî - 2x - y ³ -7.
Рис. 5. Решение системы из трех линейных неравенств.
572 Математическое приложение
Заметим, что неравенство ах + by £ с может быть заменено равносильным ему неравенством –àõ – by³ –ñ, имеющим вид (1). Кроме того, уравнение ах + by = с равносильно такой паре неравенств:
{ ax + by ³ c; ax + by £ c.
Таким образом, решение системы линейных уравнений и неравенств - всегда выпуклое множество.
Упражнение 2
Будет ли решение системы
ai x + bi y > ci , i = l, 2, ..., N
выпуклым множеством? Чем оно отличается от решения систем ы (2)?
Упражнение 3
Придумайте системы неравенств, решениями которых будут: а) параллелограмм; б) внутренность угла; в) полоса между двумя параллельными прямыми; г) единственная точка; д) пустое множество.
2. Выпуклые функции одной переменной
Проще всего определить выпуклую функцию геометрически. Д ля этого полезно ввести понятие надграфика функции. Надграфиком функции называется множество точек, расположенных над графиком ф ункции и на самом графике. Более строго, надграфик функции f(х) - это множество таких точек, координата х которых лежит в области определения функции, а координата у удовлетворяет неравенству у ³ f(x).
Функция называется выпуклой вниз, если ее надграфик - выпуклое множество. Рис. 6 иллюстрирует это определение.
Рис. 6. Надграфик выпуклой функции.
Рис. 7. Точка хорды не может располагаться ниже графика.
III. Выпуклые множества и функции 573
Приведенное определение является вполне строгим и может быть однозначно переведено на аналитический язык.
Во-первых, функция f(х) должна иметь выпуклую область определения - отрезок, луч или всю прямую.
В противном случае надграфик распался бы на несколько отдельных областей, и отрезок, соединяющий точки из разных о бластей, проходил бы через «запретную зону».
Для выяснения того, какому условию должны отвечать значе- ния выпуклой вниз функции f(x) «выберем какие-либо две точки M1 è M2 на ее графике и проведем хорду M1 M2 (рис. 7). Она целиком должна лежать в надграфике, т. е. надграфику должна принадлежать любая точка М хорды.
Рассмотрим число l , показывающее, в какой пропорции точка M делит хорду:
l = M 2 M .
M2 M1
Эта величина лежит в пределах 0 £ l £ 1. Ясно, что в такой же пропорции абсцисса и ордината точки М делят отрезки è [ó1 , ó2 ]:
õ2 – õ3 =l ·(õ2 – x1 ); y2 – y3 =l ·(y2 – y1 );
õ3 =l ·x1 + (1 –l )õ2 ; y3 =l ·y1 + (1 –l )y2 .
Условие принадлежности точки ние неравенства y3 ³ f(õ3 ). А так неравенство можно представить в
М надграфику - это выполне- âèäå êàê y 1 = f(x 1 ), y 2 = f(õ 2 ) - ýòî
Если неравенство (3) выполняется для любых значений x1 è õ2 , то любая хорда лежит в надграфике, тем более в надграфике л ежит любой отрезок, соединяющий точки, расположенные выше.
Таким образом, функция f(х), заданная на выпуклом множестве, выпукла вниз, если она обладает следующим свойством: для л ю- бых двух чисел x1 è õ2 из области определения функции и любого числаl из отрезка выполняется неравенство (3).
Неравенство (3) часто записывают в «симметричном» виде
574 Математическое приложение
Рис. 8. Функции: выпуклая вниз (а), выпуклая вверх (б), не имеющая постоянного знака выпуклости (в).
Аналогично можно определить и функции, выпуклые вверх: дл я этого нужно знаки неравенства (3) и (4) заменить на противоположные.
Функции, выпуклые вниз, часто называют просто «выпуклыми» . Выпуклые функции обладают свойством более общим, чем нера венство (4). Если x1 , õ2 ,..., xN - произвольные значения аргументаl 1 ,l 2 ,...,
l N - неотрицательные числа, сумма которых равна единице, то
Выберем четыре значения аргумента x1 < õ2 < õ3 < õ4 è ïðî- |
|||||||||
ведем хорду M1 M4 (ðèñ. 9). | |||||||||
Промежуточные точки M2 è Ì3 | лежат в надграфике, так что угол |
||||||||
наклона хорды M M * не больше, |
|||||||||
а хорды М * M | |||||||||
Не меньше, чем |
|||||||||
M M * | |||||||||
угол наклона хорды |
|||||||||
абсцисс (углы наклона - с учетом |
|||||||||
знаков!). Следовательно, | скорость |
||||||||
возрастания выпуклой функции в |
|||||||||
области «больших» значений ар- |
|||||||||
гумента (на участке [х3 , õ4 ]) íå |
|||||||||
меньше, чем в области «малых» |
|||||||||
значений (). Переходя к |
|||||||||
пределам | x 2® x 1è | ® õ 3 , |
|||||||
f¢(x3 ) | ³ f¢(x1 ) , | ||||||||
Рис. 9. Хорда, проведенная в области | производная | ¢(x) дифференциру- |
|||||||
емой выпуклой функции f(х)- не- |
|||||||||
больших значений аргумента, имеет |
|||||||||
III. Выпуклые множества и функции 575
Если производная f¢(x) дифференцируема (т. е. выпуклая функция f(х) дважды дифференцируема), то f¢¢(x) ³ 0. Для дважды дифференцируемых функций это неравенство оказывается р авносильным приведенному выше определению выпуклой функции; в курсах математического анализа выпуклость обычно опред еляют по знаку второй производной. Но в экономических приложени ях, где часто приходится иметь дело с функциями, графики кото рых имеют изломы, такое определение оказывается мало полезны м.
Если f(х) и g(x) - выпуклые функции и а ³ 0, то выпуклыми будут функции
á) f(x) + g(x);
â) max(f(õ), g(x)).
Выпуклость функций в а) и б) проверяется непосредственно с помощью неравенства (3) или (4). Функция в) при каждом х принимает значение, равное большему из значений f(х) и g(x) (и любому из них, если они равны). Надграфик функции max(f(x), g(x)) есть пересечение надграфиков функций f(х) и g(x) (проверьте!) - отсюда и выпуклость функции в).
Упражнение 4
Существуют ли функции, выпуклые вниз и выпуклые вверх одновременно?
Упражнение 5
Ê ак выглядит график функции f(х) = = mах (0, а + bх) при различных значе- ниях параметров а и b? Выпуклы ли эти функции?
Упражнение 6
Выпукла ли функция
Рис. 10. Графики функций f(х) (1), g(x)
N (2) è max(f(x), g(x)) (3). f(x) = å fi (x) ,
fi (x) = max (0, ai + bi x)?
Как выглядит ее график?
576 Математическое приложение
Упражнение | ||||
Рассмотрим | ||||
ì ax, | ||||
f(x) = í | ||||
ïï | B × (x - 1) , x ³ 1. |
|||
При каких значения а и b эта функция
Выпукла вниз?
Выпукла вверх?
- не имеет постоянного знака выпуклости?
IV. Пространство благ
Основные понятия
Многие теоретические вопросы обсуждаются в нашем учебни ке применительно к случаю двух продуктов. В качестве удобного средства, существенно упрощающего их анализ, использовались г рафические построения, в которых набор, включающий два продукта в коли- чествах x1 , è x2 изображался точкой на плоскости с декартовыми координатами (x1 , x2 ). Перевод теоретических понятий на геометри- ческий язык делал свойства обсуждаемых явлений весьма на глядными и при этом не приводил к потере строгости: все геометрические понятия (прямые, кривые, углы наклона и т. п.) имели точно определенные аналитические эквиваленты - уравнения, производные, с оотношения между параметрами и т. д. Поэтому такие построения широко используются и в учебниках по экономике, и в научных публикациях.
Однако эти геометрические рассуждения были строгими и то ч- ными лишь для случаев, когда перечень потребляемых благ в клю- чал всего два наименования. В действительности же число б лаг, которыми пользуются люди, значительно больше. Выводы, пол у- ченные геометрическим путем, можно считать обладающими д остаточной общностью, если их удастся распространить на слу чаи произвольного числа благ.
Множество AÌE называется выпуклым, если оно вместе с любыми двумя точками x 1 и x 2 содержит отрезок, соединяющий их, т.е. множества вида
[x 1 x 2 ]={x ÎE n | x =lx 1 +(1-l)x 2 , 0 £l £1}.
Рассмотренные выше полупространства являются выпуклыми множествами. Проверим, например, выпукло ли полупространство Н + ab {x
ÎE n |
Сложим эти два неравенства, предварительно умножив первое на произвольное число lÎ, а второе на 1-l. В результате получим неравенство
l
Поскольку l произвольно, весь отрезок, соединяющий выбранные точки, принадлежит данному полупространству. Следовательно, полупространство действительно является выпуклым множеством.
Рис.2.10.выпуклое(а), невыпуклое(б) множества.
Глава 3.Основные сведения о функциях .
3.1 Понятие функций .
Пусть X и Y два множества. Если указано правило, согласно которому каждому элементу множества X поставлен в соответствие определенный элемент множества Y, то говорят, что задана функция f , отображающая X в Y. Этот факт записывают в виде f: X®Y или y=f(x) , где x ÎX, yÎY. Множество X называется областью данных или областью определения функции, а множество Y- множество значений. Функция f(x) представляет собой правило, которое позволяет каждому значению x поставить в соответствие единственное значение y=f(x) . В этом случае x- независимая переменная, y- зависимая переменная. Функции y=f(x)=f(x 1 +x 2 ,..,x n), т.е. функции с областью задания X Ì E n и множеством значений Y Ì E называют числовыми функциями в отличие от векторных функций, для которых YÌ E m , m>1.
Множество вида
{(x,y)ÎE n +1 ½ y=f(x) при некоторых xÎX}
называют графиком функции y=f(x) .
Ряд физических процессов можно описать с помощью непрерывных функций, т.е. функций, которые обладают свойством непрерывности в каждой точке x, принадлежащей областям их определения.
Функцию f называют непрерывной в точке x 0 ÎX, если для любого числа e>0 можно указать такое число d e >0, что для всех xÎX Ç Ède ½x 0 ½ выполняется неравенство ½f(x)-f(x 0)½ В качестве примеров функций, непрерывных на E n , приведем линейную функцию f 1 (x)= где Q- числовая симметрическая матрица размера n*m, с- некоторый вектор из E n и b- некоторое число, а Qx означает произведение матрицы на вектор по правилам перемножения матриц, принятых в линейной алгебре. 3.2 Классификация функций.
3.2.1 Разрывные и дискретные функции.
разрывные функции. Например, затраты на сообщение некоторой системе количества тепла при различных температурах системы получаем кусочно- непрерывную кривую (рис 3.1). возможны случаи, когда переменная принимает дискретные значения(рис 3.2). В зависимости от того, является ли исследуемая функция непрерывной или разрывной следует использовать различные методы исследования. Необходимо отметить, что метод эффективный при анализе непрерывных функций, может оказаться неэффективным при исследовании разрывных функций, хотя обратное не исключается. Функции можно также классифицировать в соответствии с их формой, определяющей топологические свойства функций в рассматриваемом интервале. 3.2.2 Монотонные функции.
Функция f(x) является монотонной (рис 3.3) как при возрастании, так и убывании), если для двух произвольных точек x 1 и x 2 , таких, что x 1 Рис.3.3. К понятию монотонной функции. На рис 3.4 изображен график функции, которая монотонно убывает при x£0 и монотонно возрастает при x³0. Функция достигает своего минимума в точке x=x * (начале координат0) и монотонна по обе стороны от точки минимума. Такие функции называются унимодальными. Заметим что унимодальная функция вовсе не должна быть гладкой (рис. 3.4, а) и даже непрерывной (рис.3.4,б), она может быть изломанной (недифференцируемой), разрывной (рис 3.4, в), дискретной (рис. 3.4 г) и даже может в некоторых интервалах не быть определенной (рис. 3.4, д.). Итак функция f(x) называется унимодальной на отрезке , если она непрерывна на и существуют числа a и b a£a£b£b, такие, что: 1) если a 2) если b
3) при xÎ f(x)=f * =min f(x); Рис.3.4.Унимодальные функции: а) гладкая, б) непрерывная, в) разрывная, г) дискретная, д) произвольная. возможно вырождение в точку одного или двух из отрезков , , (рис 3.5). Рис.3.5. Варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции. множество функций, унимодальных на отрезке будем обозначать Q. Унимодальность функций является исключительно важным свойством, которое широко используется в оптимизационных исследованиях. 3.2.3 Выпуклые, псевдовыпуклые и квазивыпуклые функции
. Выпуклые функции и их обобщения (псевдовыпуклые и квазивыпуклые функции) играют важную роль в теории оптимизации. С помощью этих функций будут сформулированы достаточные условия оптимальности. Числовую функцию f, определенную на выпуклом множестве X, XÌE n , называют выпуклой, если для любых двух точек x 1 ,x 2 ÎX и произвольного числа lÎ выполняется неравенство f(lx 1 +(1-l)x 2) £ lf(x 1)+(1-l)f(x 2). (3.1) Неравенство противоположного смысла определяет вогнутую функцию, причем часто используются термины «выпуклая вниз (1)» «выпуклая вверх (2)» (рис3.6). Рис.3.6. 1) Выпуклая (выпуклая вниз) функция, 2) Вогнутая (вогнутая вверх)функция. Геометрически выпуклость функции f означает, что любая точка произвольной хорды графика f располагается не ниже соответствующей точки самого графика (лежит ниже хорды, соединяющей две точки ее графика),(рис 3.6., кривая 1). Простейшими примерами выпуклых функций одной переменной служат парабола y=x 2 и экспонента y=e x . Функции y=-x 2 и y=-e x являются вогнутыми. Если при всех x 1, x 2 ÎX x 1 ¹x 2 и lÎ неравенство (3.1) выполняется как строгое (<), то f называется строго выпуклой
на X (рис 3.7,а). Функция называется (строго) выгнутой
, если - f (строго) выпукла (рис. 3.7, б). Рис.3.7. Строго выпуклая (а) и строго вогнутая функции, их производные (пунктир) и функция, имеющая линейный участок Функция f(x)
, определенная на выпуклом множестве Х
, называется сильно выпуклой с константой l
> 0, если Дадим геометрическую интерпретацию определения (3.2), рассмотрев функцию y= f(x)
одного переменного. Зафиксировав x
1 и x
2 из области определения функции и обозначив , будем изменять l от 0 до 1. Ясно, что тогда значение x(l)
, будет изменяться от x 1
до х 2
, а точка (х
, f(x)
) пройдет по графику функции y=f(x)
от точки B= (x 2 , f(x 2)
) до точки А
= (х 1 , f(x 1))
(рис.3.8). Рис.3.8. График сильно выпуклой функции. Уравнения
в плоскости xOy описывают прямую L
(секущую), соединяющую точки А
и В
, а уравнения задают параболу Р
вида · Теорема3.1
Непрерывно дифференцируемая на выпуклом множестве X функция f
выпукла на этом множестве тогда и только тогда, когда для любых x 1 ,x 2 Î X
верно неравенство f(x 2) ³ f(x 1) + <Ñf(x 1 ,x 2 -x 1)>, (3.3) получаемое из разложения функции f(x)
в ряд Тейлора в точке x 1
путем исключения членов второго и более высокого порядка разложения F(x 1 +h) = f(x 1) + hf ¢(x 1) + h 2 /2*f¢¢(x 1) +..., (3.3) где h достаточно малое число, |h| Ñf(x 1) = (¶f/¶x 1 , ¶f/¶x 2 ,.., ¶f/¶x n) т, т.е. представляет собой вектор частичных производных первого порядка, вычисленных в точке x 1 и называется градиентом функции f в точке x 1 . · Теорема 3.2
Пусть функция f дважды непрерывно дифференцируема на выпуклом множестве X, содержащем хотя бы одну внутреннюю точку, и Ñ 2 f(x)- ее гессиан. Тогда для выпуклости f на множестве X необходимо и достаточно, чтобы матрица Ñ 2 f(x) была неотрицательно определена при всех xÎX, т.е. чтобы неравенство <Ñ 2 f(x)h, h>³0 (3.4) выполнялось для всех точек xÎX, hÎE n . Здесь числовая матрица Ñ 2 f(x) называется гессианом (или матрицей Гессе). Если функция f имеет непрерывные частные производные второго порядка (дважды непрерывно дифференцируема) в точке x 1 , то она дважды дифференцируема в x 1 и обладает матрицей Гессе вида причем эта матрица симметрична, т.е. Аналогичные утверждения имеют место и для вогнутых функций. При этом в формулах (3.2) и (3.4) знак неравенства ³ следует заменить на £. Проверка функции на выпуклость
. Функция f выпуклая, если ее матрица Гессе положительно определена (>0) или положительна полуопределена для всех значений x 1 ,x 2 ,..,x n. Проверка функции на выгнутость.
Функция f выгнутая, если ее матрица Гессе отрицательно полуопределена (£0) для всех значений x 1 ,x 2 ,..,x n . Строго выпуклая или вогнутая функция имеет единственный экстремум, являющийся соответственно глобальным минимумом или максимумом. Функция, имеющая линейный участок (рис 3.7, в), имеет бесконечное число экстремумов, равных по величине. Для суждения об одноэкстремальности при наличии ограничений можно воспользоваться понятием выпуклости допустимого множества. Множество является выпуклым, если любой отрезок прямой, соединяющей две точки границ множества, целиком лежит внутри множества. О выпуклости или вогнутости целевой функции можно судить также по характеру изменения ее частных производных ¶f/¶x. В случае строго выпуклой функции эта производная по мере увеличения аргумента возрастает (рис 3.7 а), а для строго выпуклой падает (рис 3.7 б). При наличии линейного участка целевой функции указанная производная на этом участке постоянна. Выпуклое множество вида X={xÎE n } | Ax£b}={xÎE n | £b i , i=1,..,m} где A- некоторая матрица размера m*n со строками a 1 ,..,a m , b=(b 1 ,..,b m) Î E n (m=1,2,..). Принято называть полиэдральными или просто полиэдрами. Таким образом, полиэдр - это множество решений некоторой системы конечного числа линейных неравенств, или, что то же самое, пересечение конечного числа полупространств (рис 3.9). Рис.3.9. Полиэдральное множество (полиэдр).
В инженерных приложениях нередки случаи, когда приходится использовать
f(x 1)³ (x 2) (монотонно убывающая функция)
, которая проходит через точки А
и В
. Неравенство (3.2) в этом случае означает, что график функции y = f(x)
на плоскости хОу расположен ниже не только секущей, соединяющей точки А
и В
, но и параболы Р, прогиб которой определяется параметром l
и его можно выбрать сколь угодно малым. Другими словами, в области, ограниченной секущей и графиком функции, можно построить параболу, соединяющую точки А
и В
.
