В одной из предыдущих заметок уже вводилось понятие выпуклости множеств. С точки зрения линейного программирования важно отметить, что полупространство
представляет собой выпуклое множество.
Поскольку допустимое множество задачи линейного программирования образуется как пересечение полупространств
то оно также является выпуклым.
Из выпуклости допустимого множества и линейности целевой функции для задачи линейного программирования сразу следует отсутствие в этой задаче локальных экстремумов, точнее любой локальный минимум в задаче линейного программирования является глобальным. Действительно, пусть
и - некоторая точка, такая, что
Тогда для произвольной допустимой точки с
справедливы следующие неравенства:
для .
Точка является допустимой для любых
и поскольку
можно взять сколь угодно малым, точка
не может быть точкой изолированного локального минимума.
Выпуклые множества часто порождаются операцией, называемой взятием выпуклой оболочки.
Определение. Выпуклой оболочкой конечного множества точек называется множество
В выпуклом множестве можно выделить точки, имеющие важное значение для получения этого множества с помощью операции взятия выпуклой оболочки.
Определение. Точка называется крайней точкой множества
, если из того, что
следует
Существенным здесь является нетривиальность выпуклой комбинации, т.е. то, что .
Справедливо следующее утверждение, зачастую называемое теоремой Крейна-Мильмана: ограниченное замкнутое выпуклое множество совпадает с выпуклой оболочкой своих крайних точек. Отсюда следует ряд важных следствий для линейного программирования.
Лемма. Если допустимое множество задачи линейного программирования ограничено, то среди ее решений есть крайние точки.
Доказательство. Для доказательства достаточно заметить, что задача
(*)
может быть сведена к задаче
≡
(**)
где - крайние точки допустимого множества задачи (*). Последняя задача имеет тривиальное решение:
где - индекс, на котором достигается
. Если
не единственен и достигается на некотором множестве
, то решением (**) являются произвольные
и