Предварительно дадим некоторые понятия, весьма важные для линейного программирования.
þ множество точек называется выпуклыми, если оно вместе с любыми двумя точками содержит отрезок, соединяющий эти точки. Простейшими примерами выпуклых множеств могут служить: отрезок, треугольник, квадрат, некоторые геометрические тела, например, пирамида, куб и т.д.
заметим, что выпуклый многоугольник обладает тем свойством, что весь расположен по одну сторону каждой из прямых, участвующих в ее образовании.
þ выпуклой линейной комбинацией точек М1, М2, ... Мn называется любая точка М такая, что:
М=a1M1+a2M2 + ... +anMn,
где ai ³ 0 и a1+a2+ ... +an=1.
þ Обобщая сказанное выше, можно сказать, что множество точек называется выпуклым, если вместе с любыми своими точками оно содержит и выпуклую произвольную комбинацию этих точек. Поскольку произвольная точка отрезка представляет собой выпуклую комбинацию его концов, то это и означает, что выпуклое множество вместе с двумя данными точками содержит весь соединяющий их отрезок.
Очевидно, что всякая точка выпуклого многоугольника, лежащая внутри его или на одной из сторон, за исключением вершин, может быть представлена как выпуклая линейная комбинация других точек этого многоугольника. Напротив, вершины многоугольника не представляются в виде выпуклой комбинации двух каких-нибудь других точек. В этом смысле вершины многоугольника называют экстремальными точками.
þ прямая линия называется опорной, если она имеет с выпуклым многоугольником, по крайней мере, одну общую точку и весь многоугольник расположен по одну сторону от этой прямой. Через каждую из вершин многоугольника можно провести бесконечное множество опорных линий. В пространстве трех измерений, по аналогии с понятием опорной прямой вводится понятие опорной плоскости.
þ Опорной плоскостью называется всякая плоскость, имеющая с выпуклым многогранником, по крайней мере, одну общую точку, причем такую, что весь многогранник расположен по одну сторону от нее. Опорная плоскость может иметь с выпуклым многогранником общую точку (вершину многогранника), прямую (ребро), и, наконец, общую грань.