Банк задач по математике

Задача 50.1

Доказать, что всякая плоскость аффинного пространства является пересечением конечного числа полупространств.

?

Задача 50.2

Доказать, что подмножество плоскости $P$ аффинного пространства $A$ является выпуклылм многогранником в $P$ тогда и только тогда, когда оно является выпуклым многогранником в $A$ .

?

Задача 50.3

Пусть выпуклый многогранник $M$ в аффинном пространстве задается системой линейных неравенств

f_{i}(x) \geqslant 0 \quad \left(i=1, \ldots , k ; \quad f_{i} \neq \text{ const }\right).

Доказать, что для всякого непустого подмножества $J \subseteq \left\{ 1, \ldots , k\right\}$ множество $M^{J}$ , задаваемое условиями $f_{i}(x)=0$ при $i \in J, f_{i}(x) \geqslant 0$ при $i \notin J$ , если оно непусто, является гранью многогранника $M$ , и, обратно, всякая грань многогранника $M$ имеет вид $M^{J}$ для некоторого множества $J \subseteq \left\{ 1, \ldots , k\right\}$ .

?

Задача 50.4

Пусть $a_{0}, a_{1}, \ldots , a_{n}$ — точки $n$ -мерного аффинного пространства, находящиеся в общем положении, $H_{i}(i=0,1, \ldots , n)$ — гиперплоскость, проходящая через все эти точки, кроме $a_{i}$ , и $H_{i}^{+}$ ограничиваемое ею полупространство, содержащее точку $a_{i}$ . Доказать, что

\operatorname {conv}\left\{ a_{0}, a_{1}, \ldots , a_{n}\right\} =\bigcap _{i=0}^{n} H_{i}^{+}

?

Задача 50.5

Доказать, что грани $n$ -мерного симплекса

\operatorname {conv}\left\{ a_{0}, a_{1}, \ldots , a_{n}\right\}

— это выпуклые оболочки всевозможных собственных подмножеств множества $\left\{ a_{0}, a_{1}, \ldots , a_{n}\right\}$ .

?

Задача 50.6

Найти грани $n$ -мерного параллелепипеда, заданного в некоторой системе аффинных координат неравенствами $0 \leqslant x_{i} \leqslant 1(i=1$ , $2, \ldots , n)$ .

?

Задача 50.7

Найти вершины и описать форму выпуклого многогранника в трехмерном аффинном пространстве, заданного неравенствами

\begin{gathered} x_{1} \leqslant 1, \quad x_{2} \leqslant 1, \quad x_{3} \leqslant 1 \\ x_{1}+x_{2} \geqslant -1, \quad x_{1}+x_{3} \geqslant -1, \quad x_{2}+x_{3} \geqslant -1. \end{gathered}

?

Задача 50.8

(а)(б)(в)(г)

Найти вершины и описать форму сечений четырехмерного параллелепипеда, заданного неравенствами $0 \leqslant x_{i} \leqslant 1(i=1,2,3,4)$ , плоскостями:

?

(а)

$x_{1}+x_{2}+x_{3}+x_{4}=1$ ;

(б)

$x_{1}+x_{2}+x_{3}+x_{4}=2$ ;

(в)

$x_{1}+x_{2}+x_{3}=1$ ;

(г)

$x_{1}+x_{2}=x_{3}+x_{4}=1$ .

Задача 50.9

Доказать, что замыкание выпуклого множества выпукло.

?

Задача 50.10

Доказать, что открытое ядро $M^{0}$ телесного выпуклого множества $M$ выпукло и его замыкание содержит $M$ .

?

Задача 50.11

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

?

Задача 50.12

(а)(б)

Доказать, что:

?

(а)

при сюръективном аффинном отображении полный прообраз гиперплоскости является гиперплоскостью;

(б)

полный прообраз полупространства является полупространстBOM.

Задача 50.13

Доказать, что выпуклая оболочка множества $S$ состоит из всевозможных комбинаций вида $\sum_{i=1}^{k} \lambda_{i} a_{i}$ , где

a_{i} \in S, \quad \lambda _{i} \geqslant 0 \quad (i=1, \ldots , k), \quad \sum _{i=1}^{k} \lambda _{i}=1

?

Задача 50.14

Пусть $M$ — выпуклое множество и $a \notin M$ . Доказать, что

\operatorname {conv}(M \cup a)=\bigcup _{b \in M} \overline{a b}

?

Задача 50.15

Пусть $S$ — подмножество $n$ -мерного аффинного пространства $A$ . Доказать, что если $\langle S\rangle =A$ , то conv $S$ есть объединение $n$ -мерных симплексов с вершинами в точках множества $S$ .

?

Задача 50.16

Доказать, что выпуклая оболочка компактного множества компактна.

?

Задача 50.17

Пусть $M$ — выпуклое подмножество двумерного аффинного пространства и $a \notin M^{0}$ (см. 50.10). Доказать, что через точку $a$ можно провести прямую так, что множество $M$ будет лежать по одну сторону от неё.

?

Задача 50.18

Пусть $M$ — выпуклое подмножество $n$ -мерного аффинного пространства $A$ и $a \notin M^{0}$ (см. 50.10). Доказать, что через точку $a$ можно провести гиперплоскость так, что множество $M$ будет лежать по одну сторону от неё.

?

Задача 50.19

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

?

Задача 50.20

Доказать, что всякое замкнутое выпуклое множество $M$ есть пересечение (вообще говоря, бесконечного числа) полупространств.

?

Задача 50.21

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

?

Задача 50.22

Пусть $f_{i}(i=1, \ldots , k)$ — аффинные линейные функции на аффинном пространстве $A$ . Доказать, что система неравенств $f_{i}(x) \leqslant 0(i=1, \ldots , k)$ несовместна тогда и только тогда, когда существуют такие числа $\lambda_{i} \geqslant 0$ , что $\sum_{i=1}^{k} \lambda_{i} f_{i}$ есть положительная константа.

?

Задача 50.23

(а)(б)

Пусть $M$ — компактное выпуклое множество, содержащее окрестность нуля, в векторном пространстве $V$ , рассматриваемом как аффинное пространство, и пусть

M^{*}=\left\{ f \in V^{*} \mid f(x) \leqslant 1 \text{ для всякого } x \in M\right\} .

Доказать, что:

?

(а)

$M^{*}$ — компактное выпуклое множество в пространстве $V^{*}$ , содержащее окрестность нуля;

(б)

$M^{* *}=M$ при каноническом отождествлении пространства $V^{* *}$ c $V$ .

Задача 50.24

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

?

Задача 50.25

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

?

Задача 50.26

Доказать, что крайние точки выпуклого многогранника это его вершины.

?

Задача 50.27

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

?

Задача 50.28

Доказать, что выпуклая оболочка конечного числа точек является выпуклым многогранником.

?

Задача 50.29

(а)(б)

Задать системой линейных неравенств выпуклую оболочку указанных точек четырехмерного аффинного пространства и найти трехмерные грани этого выпуклого многогранника:

?

(а)

$O=(0,0,0,0), \quad a=(1,0,0,0), \quad b=(0,1,0,0)$ , $c=(1,1,0,0), \quad d=(0,0,1,0), \quad e=(0,0,0,1), \quad f=(0,0,1,1) ;$

(б)

$O=(0,0,0,0), \quad a=(1,0,0,0), \quad b=(0,1,0,0)$ , $c=(0,0,1,0), \quad d=(1,1,0,0), \quad e=(1,0,1,0), \quad f=(0,1,1,0)$ , $g=(1,1,1,0), \quad h=(0,0,0,1)$ .

Задача 50.30

(а)(б)

Пусть $M$ и $N$ — выпуклые множества в аффинном пространстве $(A, V)$ . Доказать, что:

?

(а)

середины отрезков, соединяющих точки из $M$ с точками из $N$ , образуют выпуклое множество в пространстве $A$ ;

(б)

векторы, соединяющие точки из $M$ с точками из $N$ , образуют выпуклое множество в пространстве $V$ .

Задача 50.31

Пусть $M$ и $N$ — непересекающиеся замкнутые выпуклые множества в аффинном пространстве $A$ и одно из них ограничено. Доказать, что существует такая аффинная линейная функция $f$ на пространстве $A$ , что $f(x)<0$ при всех $x \in M$ и $f(y)>0$ при всех $y \in N$ .

?

Задача 50.32

Пусть $M$ — компактное выпуклое множество в аффинном пространстве $A, N$ — компактное выпуклое множество в векторном пространстве $L$ всех аффинных линейных функций на $A$ и пусть для всякой точки $a \in M$ найдется такая функция $f \in N$ , что $f(a) \geqslant 0$ . Доказать, что существует такая функция $f_{0} \in N$ , что $f_{0}(x) \geqslant 0$ при всех $x \in M$ .

?

Задача 50.33

(а)(б)

Пусть $F$ — аффинная билинейная функция на прямом произведении аффинных пространств $A$ и $B$ , и пусть $M$ и $N$ — компактные выпуклые подмножества пространств $A$ и $B$ соответственно.

Доказать, что:

?

(а)

$\max_{x \in M} \min_{y \in N} F(x, y)=\min_{y \in N} \max_{x \in M} F(x, y)$ ;

(б)

существуют такие точки $x_{0} \in M, y_{0} \in N$ , что при всех $x \in M$ , $y \in N$

F\left(x, y_{0}\right) \leqslant F\left(x_{0}, y_{0}\right) \leqslant F\left(x_{0}, y\right).

Задача 50.34

(а)(б)(в)

Доказать, что:

?

(а)

максимальное число частей (выпуклых многогранников), на которое может разбиваться $n$ -мерное вещественное аффинное пространство $k$ гиперплоскостями, равно

\binom {k+1}{n}+\binom {k+1}{n-2}+\binom {k+1}{n-4}+\ldots

(б)

число частей максимально тогда и только тогда, когда пересечение любых $m$ заданных гиперплоскостей при $m \leqslant n$ есть $(n-m)$ мерная плоскость, а при $m=n+1$ пусто;

(в)

если число частей максимально, то число ограниченных частей равно $\binom {k-1}{n}$ .

Задача 50.35

Определить, являются ли ограниченными многогранники, задаваемые следующими неравенствами:

?

(а)

$-3 x_{1}+5 x_{2} \leqslant 10, \quad 5 x_{1}+2 x_{2} \leqslant 35, \quad x_{1} \geqslant 0, \quad x_{2} \geqslant 0 ;$

(б)

$-x_{1}+x_{2} \leqslant 2, \quad 5 x_{1}-x_{2} \leqslant 10$ ;

(в)

$3 x_{1}-x_{2} \geqslant 4, \quad -x_{1}+3 x_{2} \geqslant 4$ ;

(г)

$-3 x_{1}+4 x_{2} \leqslant 17, \quad 3 x_{1}+4 x_{2} \leqslant 47, \quad x_{1}-x_{2} \leqslant 4, \quad x_{1}+x_{2} \geqslant 0$ ;

(д)

$-x_{1}+2 x_{2} \leqslant 6, \quad 5 x_{1}-2 x_{2} \leqslant 26, \quad x_{1}+2 x_{2} \geqslant 10$ ;

(е)

$5 x_{1}-2 x_{2} \geqslant 6, \quad 5 x_{1}-2 x_{2} \leqslant 36, \quad 2 \leqslant x_{1} \leqslant 7$ .

Задача 50.36

(а)(б)(в)(г)

Найти угловые точки многогранников:

?

(а)

$x_{1}+2 x_{2}+x_{3}+3 x_{4}+x_{5}=5, \quad x_{1}+x_{3}-2 x_{4}=3$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0 ;$

(б)

$x_{1}+x_{2}-x_{3}=10, \quad x_{1}-x_{2}+7 x_{3}=7$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0 ;$

(в)

$4 x_{1}+5 x_{2}+x_{3}+x_{4}=29, \quad 6 x_{1}-x_{2}-x_{3}+x_{4}=11$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0 ;$

(г)

$x_{1}+2 x_{2}+x_{3}=4, \quad 2 x_{1}+2 x_{2}+5 x_{3}=5$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0$ .

Задача 50.37

(а)(б)(в)(г)

Найти максимальные и минимальные значения линейной функции $z$ на ограниченном многограннике:

?

(а)

$x_{1}+2 x_{2}+x_{3}+3 x_{4}+x_{5}=5, \quad 2 x_{1}+x_{3}-2 x_{4}=3$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=x_{1}-2 x_{2}+x_{3}+3 x_{5}$ ;

(б)

$3 x_{1}-x_{2}+2 x_{3}+x_{4}+x_{5}=12, \quad x_{1}-5 x_{2}-x_{4}+x_{5}=-4$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=4 x_{1}-x_{2}+2 x_{3}+x_{5} ;$

(в)

$5 x_{1}+2 x_{2}-x_{3}+x_{4}+x_{5}=42, \quad 4 x_{1}-4 x_{2}+x_{3}+x_{4}=16$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=x_{1}-2 x_{2}+4 x_{4}-x_{5}$ ;

(г)

$x_{1}-3 x_{2}+x_{3}+2 x_{5}=8, \quad 4 x_{2}-3 x_{4}-x_{5}=3$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=x_{1}-2 x_{2}+x_{3}-x_{5}$ .

Выпуклые множества