Опуклі множини (реферат)

Опуклі множини У курсі «Математичне програмування» та в деяких економічних дослідження використовуються поняття опуклої лінійної комбінації векторів та опуклої множини.

Спочатку ознайомимось з поняттям опуклої лінійної комбінації векторів.

Нехай на площині задані точки А1 та А2, що визначають відрізок А1А2, зображений на Малюнку 1. Знайдемо радіус-вектор $$\stackrel{}{r}$$ довільної точки М цього відрізка через радіуси-вектори $$\stackrel{}{r}$$ 1 та $$\stackrel{}{r}$$ 2 точок А1 та А2.

Вектори.

$$\stackrel{}{A_{1}M}=\stackrel{}{r}-{\stackrel{}{r}}_1{\text{-A}}_1{A}_2={\stackrel{}{r}}_2-{\stackrel{}{r}}_1$$.

колінеарні і однаково напрямлені, тому вони пропорційні. Отже, існує таке t, що:

$$\stackrel{}{r}-{\stackrel{}{r}}_1=t({\stackrel{}{r}}_2-{\stackrel{}{r}}_1)\text{, 0}<=t<=1$$.

Звідси одержимо:

$$\stackrel{}{r}=(1-t){\stackrel{}{r}}_1+t{\stackrel{}{r}}_2$$.

Якщо позначити 1 — t = t1, t = t2, то остання рівність прийме вигляд.

$$\text{{}\stackrel{}{r}=t_1{\stackrel{}{r}}_1+t_2{\stackrel{}{r}}_2,$$.

$$t_1+t_2=\text{1,}\begin{array}{cc}& \end{array}{t}_1>={\text{0,t}}_2>=0$$.

Означення. Опуклою лінійною комбінацією векторів $$\stackrel{}{r}$$ 1 та $$\stackrel{}{r}$$ 2 називають комбінацією (1) цих векторів при умові (2).

Рівняння (1) з умовою (2) можна зрозуміти як векторне рівняння відрізка А1А2.

Означення. Опуклою лінійною комбінацією k n-вимірних векторів $${\stackrel{}{х}}_1,{\stackrel{}{х}}_2,\text{.}\text{.}\text{.},{\stackrel{}{х}}_k$$ називають комбінацію.

$$\stackrel{}{x}=t_1{\stackrel{}{х}}_1+t_2{\stackrel{}{х}}_2+\text{.}\text{.}\text{.}+t_k{\stackrel{}{х}}_k$$.

при умовах.

$$t_1+t_2+\text{.}\text{.}\text{.}+t_k=\text{1,}\begin{array}{cc}& \end{array}{t}_i>=\text{0,i}=\text{1,2,}\text{.}\text{.}\text{.}\text{, k}$$.

Наприклад. Лінійна комбінація $$\frac{1}{3}{\stackrel{}{х}}_1+\frac{5}{\text{12}}{\stackrel{}{х}}_2+\frac{1}{4}{\stackrel{}{х}}_3$$, має.

$$t_1=\frac{1}{3}>{\text{0,t}}_2=\frac{5}{\text{12}}>{\text{0,t}}_3=\frac{1}{4}>{\text{0,t}}_1+t_2+t_3=\frac{1}{3}+\frac{5}{\text{12}}+\frac{1}{4}=1$$

.

.

тому вона опукла.

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

Відрізок, півпряма, пряма, кут менший 1800, коло, півплощина, куб, тетраедр, куля — опуклі множини.

На малюнку 2 зображені різні множини. У випадках а) — с) ці множини опуклі, у випадках d) — е) вони неопуклі.

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

Границею множини називається сукупність всіх її граничних точок.

Множина, якій належить її границя, називається замкненою.

Опуклі замкнені множини бувають обмеженими і не обмеженими. Множина називається обмеженою, якщо існує таке число с > 0, що відстань довільної точки М множини від початку координат обмежена, тобто |ОМ| < 0.

Означення. Опукла замкнена множина в n вимірному просторі, що має скінченне число кутових точок, називається опуклим n вимірною многогранною множиною, якщо вона не обмежена.

Кутові точки називають вершинами, відрізки, що сполучають дві сусідні вершини, називають ребрами.

Означення. Опорною прямою многокутника в двовимірному просторі називається пряма, яка має з многокутником, розташованим по одну сторону від неї, принаймні одну спільну точку.

Опорна пряма з многокутником може мати спільну вершину або ребро.

Останні поняття узагальнюються на випадок n вимірного простору.

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

Опорна гіперплощина з множиною може мати спільну вершину, ребро або грань.