Балашовский филиал

Теорема 1. а) Множество решений системы ограничений задачи
линейного программирования является выпуклым множеством;
б) Множество решений задачи линейного программирования является выпуклым множеством.
Таким образом, геометрическая интерпретация задачи линейного программирования заключается в следующем:

• 
  найти максимум (минимум) линейной функции на выпуклом множестве.
  

О
граниченное множество решений системы ограничений ЗЛП называют выпуклым многогранником, а неограниченное — выпуклой многогранной областью. В R² — это выпуклые многоугольники или выпуклые многоугольные области (см., например, Error: Reference source not found).
Функция L(x₁, x₂…, x_n) называется ограниченной сверху (снизу) на множестве M  Rⁿ, если существует число К такое, что для всех
(x₁, x₂,…, x_n) из множества М выполняется неравенство L(x₁, x₂,…, x_n) ≤ К (L(x₁, x₂,…, x_n) ≥ К). Функция, ограниченная и сверху, и снизу, называется ограниченной.
Будем говорить, что целевая функция ЗЛП ограничена, если в задаче на максимум она ограничена на допустимом множестве сверху, а в задаче на минимум — снизу.


Теорема 2. Если в задаче линейного программирования допустимое множество отлично от пустого и целевая функция ограничена, то существует по крайней мере одно оптимальное решение.
Т очку выпуклого множества, не являющуюся выпуклой линейной комбинацией никаких других его точек, называют угловой (или вершиной). Иллюстра-цией может служить Error: Reference source not found.
У выпуклого множества, изображенного на Error: Reference source not found, точки X
и W являются его вершинами,
а точки Y и Z — нет. Действительно, каждая из двух последних точек является выпуклой линейной комбинацией других его точек: Y, например, является выпуклой линейной комбинацией точек Y₁ и Y₂, а Z — выпуклой линейной комбинацией Z₁ и Z₂ (см. замечание 5). У X и W таких точек нет.