Геометрическая интерпретация задачи линейного программирования в случае двух переменных.

Рассмотрим ЗЛП по отысканию максимума (или минимума) линейной функции на допустимом множестве Х (ОДР), заданном с помощью системы S линейных ограничений (уравнений или нестрогих неравенств). Напомним, что такое множество называется выпуклым многогранником. Таким образом, геометрический смысл ЗЛП состоит в отыскании максимума (минимума) линейной функции на заданной выпуклой многогранной области .

Скажем, что ЦФ (целевая функция) в ЗЛП ограничена, если в задаче на максимум ЦФ ограничена на допустимом множестве сверху, а в задаче на минимум - снизу.

Полезны следующие две теоремы.

Теорема. Если в ЗЛП допустимое множество Х непусто и ЦФ ограничена, то существует хотя бы одно оптимальное решение.

При исследовании ЗЛП важнейшую роль играет понятие угловой точки множества. Напомним, что точка называется угловой, если она не является внутренней ни для какого отрезка, целиком содержащегося в этом множестве.

Теорема. Если в ЗЛП при условии , допустимое множество Х имеет хотя бы одну угловую точку, а ЦФ ограничена, то найдется угловая точка множества Х, в которой принимает оптимальное значение данной задачи.