Доказательство.

Докажем теорему для случая КЗЛП (для остальных постановок доказательство аналогично).

Итак, Пусть т.е.

Рассмотрим выпуклую линейную комбинацию точек и , т.е.

Для доказательства выпуклости P достаточно показать, что .

Действительно:

, т.к. -выпуклое множество;

, т.е. , следовательно, P-выпуклое множество.

Теорема 2.5. Пересечение любого числа выпуклых множеств является выпуклым множеством.

Доказательство. Пусть , где – выпуклые множества для всех . Тогда для всех и в силу их выпуклости точка для всех и , следовательно, , т.е. – выпуклое множество.

Замечание. Очевидно, что объединение двух выпуклых множеств, вообще говоря, не выпукло.

Нетрудно доказать, что если и – выпуклые множества, то множества , , (l – действительное число) выпуклы.

Пользуясь теоремой 2.4., можно, например, доказать, что множество планов Р основной ЗЛП является выпуклым множеством. Действительно,

является выпуклым как пересечение m+n полупространств:

Определение 2.9. Точка называется выпуклой линейной комбинацией точек , если существуют числа , , , такие что .

Теорема 2.6. Множество выпукло тогда и только тогда, когда оно содержит все выпуклые комбинации любого конечного числа своих точек.

Доказательство. Необходимость. Пусть P – выпуклое множество. Тогда по определению 1 содержит выпуклые комбинации любых двух своих точек. Предположим, что множество содержит выпуклые комбинации любых своих точек. Рассмотрим выпуклую комбинацию произвольных точек из . Можем считать, что , и так как , , .

Тогда точка по индуктивному предположению, но и в силу выпуклости .

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

Определение 2.10. Точка называется внутренней точкой множества , если существует – окрестность точки , , целиком принадлежащая множеству . Совокупность всех внутренних точек множества обозначим через .

Теорема 2.7. Если – выпуклое множество, то также выпукло.

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

Действительно, поскольку

,

,

, .

Из определения и имеем

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

Определение 2.11. Точка называется предельной точкой множества , если существует бесконечная последовательность точек , сходящаяся к . Объединение множества и всех предельных точек множества называется его замыканием и обозначается .

Замечание. Таким образом, множество состоит из точек трех типов: изолированные точки множества , предельные точки множества , принадлежащие , предельные точки множества , не принадлежащие . Выпуклое множество не может иметь изолированных точек, следовательно, замыкание выпуклого множества состоит только из предельных точек множества .

Теорема 2.8. Если – выпуклое множество, то также выпукло.

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

Большую роль в построении теории линейного программирования играет понятие крайней точки.

Определение 2.12. Точка выпуклого множества P является крайней, если в P не существует таких точек и , ≠ , что

, при некотором .

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

Например, крайними точками треугольника являются его вершины, а круга - все точки окружности.

Определение 2.13. Замкнутое ограниченное выпуклое множество с конечным числом крайних точек будем называть выпуклым многогранником.

Например, треугольник является выпуклым многогранником, а круг - нет, так как у него бесконечное число крайних точек.

Теорема 2.9 (о представлении).Любая точка выпуклого замкнутого ограниченного множества может быть представлена в виде выпуклой линейной комбинации конечного числа крайних точек этого множества.

Пример 2.2. Любая внутренняя точка круга может быть представлена в виде выпуклой линейной комбинации концов хорды, проходящей через эту точку.

Пример 2.3. Любая внутренняя точка треугольника может быть представлена в виде выпуклой линейной комбинации его крайних точек - вершин треугольника.

Легко видеть, что `Х = (1- l)`Х₁ + l`Х₄, 0 £ l £ 1

и `Х<sub>4</sub> = (1- l<sub>1</sub>)`Х₂ + l₁`Х₃, 0 £ l₁ £ 1,

откуда `Х = (1- l)`Х₁ + l (1-l₁)`Х<sub>2</sub> + l× l<sub>1</sub>`Х₃ , 0 £ l £ 1, 0 £ l₁ £ 1,

причём 1 - l ³ 0, l(1- l₁) ³ 0, l× l₁ ³ 0 и (1- l) + l(1- l₁) + l× l₁ = 1.