81
Угловыми точками выпуклого множества называются точки, не являю-
щиеся выпуклой комбинацией двух произвольных точек множества. Например,
угловыми точками треугольника являются его вершины, круга – точки окруж-
ности, которые его ограничивают.
Множество планов основной задачи линейного программирования явля-
ется выпуклым (если оно не пусто). Непустое множество планов называется
многогранником решений, а всякая угловая точка многогранника решений –
вершиной.
Если основная задача линейного программирования имеет оптимальный
план, то целевая функция задачи принимает максимальное значение в одной из
вершин многогранника решений. Если максимальное значение достигается бо-
лее чем в одной вершине, то целевая функция принимает его во всякой точке,
являющейся выпуклой линейной комбинацией этих вершин.
Непустое множество планов основной задачи линейного программиро-
вания образует выпуклый многогранник, каждая вершина которого определяет
опорный план. Для одного из опорных планов (т. е. в одной из вершин много-
гранника решений) значение целевой функции является максимальным (при
условии, что функция ограничена сверху на множестве планов).
Вершину многогранника решений, в которой целевая функция принима-
ет максимальное значение. Можно найти достаточно просто, если задача в
стандартной форме содержит не более двух переменных:
max
)
(
22 11
xc
x
c
X
F
при условиях
.2,1 ,0
; ,1 ,
22
11
j
x
k ib xa x
a
j
i
i
i
Каждое из неравенств системы ограничений задачи геометрически опре-
деляет полуплоскость допустимых значений переменных соответственно с гра-
ничными прямыми
.0 ; ,1 ,
2
22
11
xk ib xa x
a
i
i
i
Если система неравенств совместна, то областью допустимых решений
задачи являются выпуклое множество, которое называется многоугольником
решений. Стороны этого многоугольника лежат на прямых, уравнения которых
получаются из исходной системы ограничений заменой знаков неравенств на
знаки точных равенств.
Решение задачи линейного программирования геометрическим методом
включает следующие этапы.
