 |
 |
 |
 |
|
 |
 |
12
Линейная комбинация
векторов а¹, а²... а
m
называется выпуклой, если ?
i
?0, i
?1:m и
Множество, содержащее все возможные выпуклые комбинации точек некоторого множества М,
называют выпуклой оболочкой данного множества. Можно показать, что выпуклая оболочка множества
М является наименьшим выпуклым множеством, содержащим М.
Выпуклая оболочка конечного множества точек называется выпуклым многогранником, а непустое
пересечение конечного числа замкнутых полупространств — многогранным выпуклым множеством. В
отличие от выпуклого многогранника последнее может быть неограниченным.
Точка
v выпуклого множества V называется его угловой (крайней) точкой, если она не является
внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Угловые точки
выпуклого многогранника являются его вершинами, а сам он — выпуклой оболочкой своих вершин.
Множество К называется конусом с вершиной в точке x
0
, если x
0
?
К , и из того, что некоторая точка
х принадлежит К ( х ? К ), следует, что в К содержится и луч, начинающийся в х
0
и проходящий через х,
т. е.
или
Выпуклая оболочка конечного множества лучей, исходящих из одной точки, называется
многогранным выпуклым конусом с вершиной в данной точке.
1.2.2. Первая геометрическая интерпретация ЗЛП и графический метод решения. Рассмотрим
следующий пример. Пусть дана задача максимизации линейной целевой функции
f(x) = 3х1 + х2
>
max
на множестве
Так как количество переменных в неравенствах, задающих область допустимых планов задачи, равно
двум, то ее можно изобразить на координатной плоскости (см. рис. 1.1).
На рис. 1.1 показано, что каждое неравенство определяет некоторую полуплоскость.
Соответствующие области для каждого ограничения отмечены штрихами. Пересечение D данных
полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является
областью допустимых планов задачи. Поведение целевой функции f(x)
= 3х1 + х2 в рамках двумерной
иллюстрации может быть охарактеризовано с помощью линий уровня.
Напомним, что линией уровня функции называется множество точек из ее области определения, в
которых функция принимает одно и то же фиксированное значение. Градиентом функции
f(x)
называется вектор