Многоугольники и многогранники

Одним из основных понятий теории математического программирования является многогранник в n-мерном пространстве. В случае двух переменных его аналогом является многоугольник.

Многогранником в n-мерном пространстве называется замкнутое, выпуклое, ограниченное множество точек n-мерного пространства с конечным числом угловых точек.

Рассмотрим это определение подробнее. Составим уравнение отрезка прямой на плоскости. Пусть и граничные точки отрезка, – текущая точка (рис. 3.1).

Рис. 3.1

Запишем векторное параметрическое уравнение отрезка АB

.

Так как , , то уравнение отрезка в координатной записи приобретает вид

или

Эту систему записывают следующим образом:

Точку М называют выпуклой линейной комбинацией точек А и В.

Обозначив , получим

Данная запись позволяет сделать обобщение.

Точка М называется выпуклой линейной комбинацией точек , если

. (3.1)

Множество называется выпуклым, если оно содержит выпуклую линейную комбинацию любых своих точек. На рис. 3.2 а и б изображены примеры соответственно выпуклых и невыпуклых множеств.

Рис. 3.2

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

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

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

Угловой точкой множества называется точка, которая не является выпуклой линейной комбинацией каких-либо точек этого множества. Это значит, что угловая точка не лежит на прямой, соединяющей какие-либо две точки множества. Множество может иметь любое число угловых точек: одну (рис. 3.3 а), две (рис. 3.3 б), три (рис. 3.3 в), а также бесконечное число угловых точек (рис. 3.3 г).

Рис. 3.3

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

Доказательство. Пусть точка М является внутренней точкой многоугольника с вершинами (рис. 3.4).

Рис. 3.4.

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

Точка М является выпуклой линейной комбинацией точек и N, т. е.

.

Для точки N также имеет место равенство

.

Подставим последнее выражение для N в предыдущее, получим

.

Обозначим , запишем , где и

Следовательно, точка М является выпуклой линейной комбинацией точек . Дополним это равенство слагаемыми, равными нулю, и получим

,

где .

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

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

4.2. Теорема о виде области допустимых решений задачи
линейного программирования

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

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

Z(X) = CX max (min),

AX = ,

.

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

получим

.

Учитывая, что , а , получим .

Кроме того, так как , то , т. е. является допустимым решением.