Приклади опуклих множин. Випуклі множини та функції

При дослідженні економічних явищ математичними методами дуже значним виявляється така властивість багатьох множин та функцій, як опуклість. Характер поведінки багатьох економічних об'єктів пов'язані з тим, що певні залежності, що описують ці об'єкти, є опуклими.

З опуклістю функцій та множин часто пов'язане існування чи єдиність вирішення економічних завдань: на цій же властивості засновані багато обчислювальних алгоритмів.

Справедливість багатьох тверджень, що стосуються опуклих множин і функцій, цілком зрозуміла, вони майже очевидні. У той самий час їхній доказ дуже складно. Тому тут буде викладено деякі основні факти, пов'язані з опуклістю, без доказів, для їх інтуїтивну переконливість.

Випуклі множини на площині.

Будь-яка геометрична фігура на площині може розглядатися як безліч точок, що належать цій фігурі. Одні множини (наприклад, коло, прямокутник, смуга між паралельними прямими) містять і внутрішні, і граничні точки; інші (наприклад, відрізок, коло) складаються лише з граничних точок.

Безліч точок на площині називається опуклим, якщо воно має наступну властивість: відрізок, що з'єднує будь-які дві точки цієї множини, цілком міститься в цій множині.

Прикладами опуклих множин є: трикутник, відрізок, напівплощина (частина площини, що лежить по одну сторону від будь-якої прямої), вся площина.

Безліч, що складається з однієї-єдиної точки, і порожня множина, що не містить жодної точки, за прийнятою угодою, також вважаються опуклими. У всякому разі, у цих множинах неможливо провести відрізок, що з'єднує якісь точки цих множин і не належить цим множинам цілком, - у них взагалі неможливо вибрати дві точки. Тому їх включення до опуклих множин не призведе до суперечності з визначенням, а для математичних міркувань цього достатньо.

Перетин, т. е. загальна частина двох опуклих множин, завжди опукло: взявши будь-які дві точки перетину (а вони - загальні, тобто належать кожному з множин, що перетинаються) і з'єднавши їх відрізком, ми легко переконуємося в тому, що всі точки відрізка є загальними для обох множин, тому що кожна з них опукла. Випуклим буде і перетин будь-якої кількості опуклих множин.

Важливою властивістю опуклих множин є їхня відокремленість: якщо дві опуклі множини не мають загальних внутрішніх точок, то площину можна розрізати по прямій таким чином, що одна з множин буде повністю лежати в одній напівплощині, а інша - в іншій (на лінії розрізу можуть розташовуватися точки обох множин). Пряма, що відокремлює їх, в одних випадках виявляється єдино можливою, в інших - ні.

Гранична точка будь-якої опуклої множини сама може розглядатися як опукла множина, яка не має з вихідною множиною загальних внутрішніх точок, отже, вона може бути відокремлена від нього деякою прямою. Пряма, що відокремлює від опуклої множини його граничну точку, називається опорною прямою цієї множини в даній точці. Опорні прямі в одних точках контуру можуть бути єдиними, в інших – не єдиними.

Введемо на площині систему декартових координат х, у. Тепер у нас з'явилася можливість розглядати різні фігури як безлічі таких точок, координати яких задовольняють тим чи іншим рівнянням або нерівностям (якщо координати точки задовольняють будь-якій умові, будемо стисло говорити, що сама точка задовольняє цій умові).

В якому всі точки відрізка , утвореного будь-якими двома точками даної множини, також належать цій множині.

Визначення

Приклади

• Випуклі підмножини множини $\backslash R$(Більшість дійсних чисел) являють собою інтервали з $\backslash R$.
• Прикладами опуклих підмножин у двовимірному евклідовому просторі ( $\backslash R^2$) є правильні багатокутники.
• Прикладами опуклих підмножин у тривимірному евклідовому просторі ( $\backslash R^3$) є архімедові тіла та правильні багатогранники .
• Тіла Кепплера - Пуансо (правильні зіркоподібні багатогранники) є прикладами невипуклих множин.

Властивості

• Випукла множина в топологічному лінійному просторі є зв'язковим і лінійно зв'язним, гомотопічно еквівалентним точці.
• У термінах зв'язності, опукле безліч можна визначити так: безліч опукло, якщо його перетин з будь-якою (речовинною) прямою зв'язно.
• Нехай $K$- опукле безліч у лінійному просторі. Тоді для будь-яких елементів $u\_1,\backslash ;u\_2,\backslash ;\backslash ldots,\backslash ;u\_r$належать $K$і для всіх невід'ємних $\backslash lambda\_1,\backslash ;\backslash lambda\_2,\backslash ;\backslash ldots,\backslash ;\backslash lambda\_r$, таких що $\backslash lambda\_1+\backslash lambda\_2+\backslash ldots+\backslash lambda\_r=1$, вектор $w=\backslash sum\_(k=1)^r\backslash lambda\_k\; u\_k$

• Вектор $w$називається опуклою комбінацією елементів $u\_1,\backslash ;u\_2,\backslash ;\backslash ldots,\backslash ;u\_r$.

Варіації та узагальнення

• Без будь-яких змін визначення працює для афінних просторів над довільним розширенням поля дійсних чисел.

Див. також

Напишіть відгук про статтю "Опукло безліч"

Література

• Половінкін Є. С., Балашов М. В.Елементи опуклого та сильно опуклого аналізу. – М.: ФІЗМАТЛІТ, 2004. – 416 с. - ISBN 5-9221-0499-3..
• Тиморін В. А.. – М.: МЦНМО, 2002. – 16 с. - ISBN 5-94057-024-0..

Посилання

Уривок, що характеризує опуклу множину

Повернувшись до Москви з армії, Микола Ростов був прийнятий домашніми як найкращий син, герой і ненаглядний Миколка; рідними – як милий, приємний і шанобливий хлопець; знайомими – як гарний гусарський поручик, спритний танцюрист та один із найкращих наречених Москви.
Знайомство у Ростових була вся Москва; грошей у нинішній рік у старого графа було достатньо, тому що були перезакладені всі маєтки, і тому Миколушко, завівши свого власного рисака і наймодніші рейтузи, особливі, яких ні в кого ще в Москві не було, і чоботи, наймодніші, з самими гострими шкарпетками та маленькими срібними шпорами проводив час дуже весело. Ростов, повернувшись додому, відчув приємне почуття після деякого проміжку часу примірювання себе до старих умов життя. Йому здавалося, що він дуже змужнів і виріс. Розпач за невитриманий із закону Божого іспит, позичання грошей у Гаврила на візника, таємні поцілунки з Сонею, він про все це згадував, як про дитинство, від якого він незмірно був далекий тепер. Тепер він – гусарський поручик у срібному ментику, з солдатським Георгієм, готує свого рисака на біг, разом із відомими мисливцями, літніми, поважними. У нього знайома жінка на бульварі, до якої він їздить увечері. Він диригував мазурку на балі у Архарових, розмовляв про війну з фельдмаршалом Каменським, бував у англійському клубі, і був на ти з одним сорокарічний полковником, з яким познайомив його Денисов.
Пристрасть його до государя дещо послабшала у Москві, оскільки за цей час не бачив його. Але він часто розповідав про государя, про свою любов до нього, даючи відчувати, що він ще не все розповідає, що щось ще є в його почутті до государя, що не може бути всім зрозуміло; і від щирого серця поділяв загальне на той час у Москві почуття обожнювання до імператора Олександра Павловича, якому у Москві на той час було дано найменування ангела в плоті.
У цей короткий перебування Ростова у Москві, до від'їзду до армії, не зблизився, а навпаки розійшовся з Соней. Вона була дуже гарна, мила, і, очевидно, пристрасно закохана в нього; але він був у тій порі молодості, коли здається так багато справи, що колись цим займатися, і юнак боїться зв'язуватися – дорожить своєю свободою, яка йому потрібна на багато іншого. Коли він думав про Соню в це нове перебування у Москві, він казав собі: Е! ще багато, багато таких буде і є там, десь, мені ще невідомих. Ще встигну, коли захочу, зайнятися і коханням, а тепер ніколи. Крім того, йому здавалося щось принизливе для своєї мужності в жіночому суспільстві. Він їздив на бали і в жіноче суспільство, вдаючи, що робив це проти волі. Біга, англійський клуб, гульба з Денисовим, поїздка туди - це була інша справа: це було пристойно молодцю гусару.
На початку березня старий граф Ілля Андрійович Ростов був стурбований облаштуванням обіду в англійському клубі для прийому князя Багратіона.
Граф у халаті ходив по залі, віддаючи накази клубному економу і знаменитому Феоктисту, старшому кухареві англійського клубу, про спаржу, свіжі огірки, суницю, теля і рибу для обіду князя Багратіона. Граф, з дня заснування клубу, був його членом та старшиною. Йому було доручено від клубу влаштування урочистості для Багратіона, тому що рідко хто вмів так на широку руку, хлібосольно влаштувати бенкет, особливо тому, що рідко хто вмів і хотів прикласти свої гроші, якщо вони знадобляться на влаштування бенкету. Кухар і економ клубу з веселими обличчями слухали накази графа, бо вони знали, що ні за кого, як за нього, не можна було краще поживитися на обіді, який коштував кілька тисяч.

Випукла безліч- підмножина евклідова простору містить відрізок, що з'єднує будь-які дві точки цієї множини.

Визначення

Іншими словами, безліч називається опуклою, якщо:

Тобто, якщо безліч Xразом з будь-якими двома точками, які належать цій множині, містить відрізок, що їх з'єднує:

У просторі опуклими множинами будуть пряма, напівпряма, відрізок, інтервал, одноточкова множина.

У просторі опуклим буде сам простір, будь-який його лінійний підпростір, куля, відрізок, одноточкова множина. Також, опуклими будуть такі множини:

• гіперплощини H p? з нормаллю p :

• напівпростору на які гіперплощини поділяє простір:

Всі перелічені множини (крім кулі) є окремим випадком опуклою множини поліедри.

Властивості опуклих множин

• Перетин опуклих множин є опуклим.
• Лінійна комбінація точок опуклої множини опукла.
• Випукла множина містить будь-яку опуклу комбінацію своїх точок.
• Будь-яку точку n-мірного евклідового простору з опуклої оболонки множини можна представити як опуклу комбінацію не більше n+1 точок цієї множини

Розглянемо n- мірний евклідовий простір і нехай  точка у цьому просторі.

Розглянемо дві точки і , що належать . , які можуть бути представлені у вигляді

(У координатах це записується так:

відрізком, що з'єднує точки і . Самі крапки і називаються кінцями відрізка. У випадках n=2 і n=3 це  відрізок у звичайному розумінні цього слова на площині чи просторі (див. рис. 12). Зауважимо, що з  =0 , а при  =1 , тобто. при  =0 та  =1 виходять кінці відрізка.

де все і називається опуклою комбінацієюточок.

Нехай є деяка область у просторі (іншими словами,

Визначення. Безліч (область) називається опуклим, якщо з того, що слід, що для   . Іншими словами, G опуклий множина, якщо вона, разом з будь-якими двома своїми точками, містить у собі відрізок, що з'єднує ці точки.

На цих малюнках "а" і "б" - опуклі множини, а "в" не є опуклим множиною, тому що в ньому є така пара точок, що з'єднує їх відрізок не весь належить цій множині.

Теорема 1. Нехай G - опукла множина. Тоді будь-яка опукла комбінація точок, що належать цій множині, також належить цій множині.

Доведення

Доведемо теорему методом математичної індукції. При k=2 теорема правильна, оскільки вона перетворюється на визначення опуклого множини.

Нехай теорема вірна для деякого k. Візьмемо крапку та розглянемо опуклу комбінацію

Теорему доведено.

Теорема 2. Допустима область задачі лінійного програмування є опуклим безліччю.

Доведення.

1. У стандартній форміу матричних позначеннях допустима область G визначається умовою

Тобто. x належить G і, отже, опукло.

2. У канонічній форміобласть G визначена умовами

Нехай і належить G, тобто.

.

тобто. і, отже, G опукло. Теорему доведено.

Таким чином, допустима область задачі лінійного програмування є опуклим безліччю. За аналогією з двовимірним або тривимірним випадками, за будь-якого nцю область називають опуклим

Теорема 3. Безліч оптимальних планів задачі лінійного програмування опукло (якщо воно не порожнє).

Доведення

Якщо розв'язання задачі лінійного програмування єдине, то воно опукло за визначенням - точка вважається опуклим безліччю. Нехай тепер і два оптимальні плани задачі лінійного програмування.

тобто. є також оптимальний план і, з цього, безліч оптимальних планів опукло. Теорему доведено.

Теорема 4. Для того, щоб задача лінійного програмування мала рішення, необхідно і достатньо, щоб цільова функція на допустимій множині була обмежена зверху (при вирішенні задачі на максимум) або знизу (при вирішенні задачі на мінімум).

Цю теорему ми даємо без доказів.

Властивості опуклої множини

Класифікація та специфіка задач математичного програмування.

Введення у математичне програмування.

Математичне програмування одна із способів дослідження операцій економіки. Зміст математичного програмування становлять теорія та методи розв'язання задач про знаходження екстремуму функції на деякій множині. Безліч можуть визначатися як лінійними так і не лінійними обмеженнями. Головна мета завдань математичного програмування – вибір програм дій, які призводять до найкращого результату, з погляду особи, яка приймає рішення (ЛПР). Проблема прийняття рішення у послідовності операції нерозривно пов'язана з проблемами моделювання.

Визначення моделі.

Модель - це образ досліджуваного явища чи об'єкта.

Етапи моделювання.

1. Побудова якісної моделі, тобто. виділення факторів, які видаються найбільш важливими у встановленні закономірності, яким вони підкоряються.

2. Побудова математичної моделі. Запис якісної моделі у математичних термінах.

Математична модель прийнято називати точною якщо всі вихідні величини числових параметрів моделі є точними (наприклад, результати спостережень). У цьому сенсі точну модель називають ідеальною. Далі будемо вважати, що у точної задачі завжди існує точне рішення (результати спостережень). У реальній ситуації відомості про вхідні параметри мають, як правило, приблизний характер (результати вимірів). І тут отримані завдання називаються реальними, які рішення – реальними рішеннями.

Реальне рішення може і не існувати.

2 етап. Включає також побудова цільової функції, тобто. такої числової характеристики, більшого чи меншого значення якої відповідає краща ситуація з погляду особи, яка приймає рішення.

3 етап. Дослідження впливу змінних на значення цільової функції, знаходження рішення, поставленого завдання.

4 етап. Зіставлення результатів обчислення, отриманих на 3 етапі з модельованим об'єктом, тобто. критерій практики.

Тут встановлюється ступінь адекватності моделі та об'єкта, що моделюється.

У математичному програмуванні можна назвати два напрями:

· Власне математичне програмування – детерміновані завдання, коли вся вихідна інформація повністю визначена;

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

У математичному програмуванні виділяють такі розділи:

1) Лінійне програмування. У цих завданнях цільова функція лінійного, а множини, на якому досліджується його екстремальне значення задається системою лінійних рівностей або нерівностей. У свою чергу, в лінійному програмуванні існують класи завдань, структура яких дозволяє створювати свої спеціальні методи рішення, що вигідно відрізняються від методів загального характеру. Наприклад, транспортне завдання.

2) Нелінійне програмування. Дане завдання і цільова функція та обмеження носять нелінійний характер.
Розміщено на реф.
Завдання нелінійного програмування зазвичай класифікують на:

a) Випукло програмування, коли цільова функція опукла і опукло безліч, на якій вирішується завдання.

b) Квадратичне програмування, коли цільова функція квадратична, а обмеження - лінійна рівність або нерівність.

c) Багатоекстремальні завдання. Зазвичай виділяються спеціальні класи завдань, які часто зустрічаються в примітках. Наприклад, завдання мінімізації на опуклій множині увігнутих функцій.

3) Цілочисленне програмування, коли значення змінних чи значення цільової функції накладається умова целочисленности.

Специфіка завдань математичного програмування у тому, що, по-перше, способи класичного аналізу знаходження умовних екстремумів непридатні, т.к. навіть у простих завданнях екстремуми досягаються в кутах багатогранника рішення, а отже, порушується диференційованість функції.

По-друге, у практичних завданнях кількість змінних і обмежень настільки велика, що якщо перебирати всі точки в екстремальності, то може не вистачити ресурсів ЕОМ, у зв'язку з цим мета математичного програмування створення, де можливо, аналітичних методів рішення, а за відсутності таких методів – створення ефективних обчислювальних засобів знаходження примусового рішення.

Елементи випускного аналізу.

Безліч Хприйнято називати замкнутим якщо воно містить усі свої граничні точки

Безліч Хприйнято називати обмеженим якщо існує куля кінцевого радіусу з центром у будь-якій точці цієї множини повністю включає в себе це безліч.

Безліч Хприйнято називати опуклим множиною якщо поруч із кожними точками Х1, Х2 є цій множині всі точки Х рівні (1-α)· , де 0≤α≤1 так само належать цій множині Х. Т.е. якщо множині Х, то й відрізок, що з'єднує ці точки, теж множині Х.

Приклад:

Дано безліч ? = (х, у такі, що х + у ≤ 1. Довести, що ця множина є опуклим.

Нехай взяли дві точки () і () Ψ (ᴛ.ᴇ. + ≤1 і + ≤1).

Довести, що точка

1. Теорема 1

Перетин опуклих множин є опуклим множиною.

Доведення:

Нехай Х перетинання множин і, де і опуклі множини.

Доведемо, що Х опукле безліч.

Нехай крапки і Х. Доведемо, що відрізок, що з'єднує ці крапки, теж належить множині Х.

т.к. і Х => і Х1

Х1 опукле безліч => відрізок [ , ] Х1

т.к. , Х => вони Х2

Х2 опукле безліч.

Звідси випливає, що відрізок [ , ] Х1∩Х2=Х

Теорему доведено.

2. Теорема 2.

Об'єднання опуклих множин не завжди є опуклим.

3. Властивість певності.

Розглянемо двомірний простір, в якому є не замкнута і опукла безліч Х і якась точка d (,), де d Х, тоді знайдеться пряма

З такою, що виконуватимуться нерівності

Гіперплощиною у просторі R прийнято називати безліч точок x (яка задовольняє рівності

Властивості опуклої множини - поняття та види. Класифікація та особливості категорії "Властивості опуклої множини" 2017, 2018.

Багато AÌE називається опуклим, якщо воно разом з будь-якими двома точками x 1 і x 2 містить відрізок, що з'єднує їх, тобто. безлічі виду

[x 1 x 2 ]={xÎE n | x=l x 1+(1-l) x 2 , 0 £l £1).

Розглянуті вище напівпростор є опуклими множинами. Перевіримо, наприклад, чи опукло напівпростір Н + ab ( xÎE n | b). Для цього розглянемо дві довільні точки x 1 і x 2 цього напівпростору. Для цих точок виконані нерівності

x 1 >³ b, x 2 >³ b.

Складемо ці дві нерівності, попередньо помноживши першу довільне число lÎ, а друге на 1-l. В результаті отримаємо нерівність

l x 1 > + (1-l) x 2 > = x 1 + (1-l) x 2 >³ b.

Оскільки l довільно весь відрізок, що з'єднує обрані точки, належить даному напівпростору. Отже, напівпростір дійсно є опуклим безліччю.

Рис.2.10.опукло(а), неопукло(б) множини.

Глава 3. Основні відомості про функції.

3.1 Поняття функцій.

Нехай X і Y дві множини. Якщо зазначено правило, згідно з яким кожному елементу множини X поставлено у відповідність певний елемент множини Y, то кажуть, що задана функція f, що відображає X у Y. Цей факт записують у вигляді f: X®Y або y=f(x), де x X, yY. Множина 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)= +b=c 1 x 1 +c 2 x 2 +..+c n x n +b та квадратичну функцію f 2 (x)=1/2 ++b,

де 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 f(x 1)£ f(x 2) (монотонно зростаюча функція)
f(x 1)³ (x 2) (монотонно спадна функція)

Рис.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);