Геометрическая интерпритация модели

Область допустимых решений D в задаче ЛП образуется путём пересечения m полупространств, каждое из которых определяется соответствующим линейным неравенством (ограничением) модели a_i1 x₁ + a_i2 x₂ + … + a_in x_n £ b_i; i = `1,`m. Пересечение указанных полупространств является выпуклым многогранником.

При этом множество значений `x, удовлетворяющих неравенствам (ограничениям) модели может быть пустым (рис. 1), ограниченным (рис. 2 а, б) и неограниченным (рис. 3). В первом случае задача не имеет решения, т.к. система линейным неравенств противоречива.

Рассмотрим плоскость:

q (`x) = `c `x = c₁ x₁ + c₂ x₂ + … + c_n x_n = const.

Следует помнить, что её нормальный вектор `N = (c<sub>1</sub>, c<sub>2</sub>,…, c<sub>n</sub>). `N указывает направление возрастания (убывания) линейной функции q (`x) = `c `x. Будем перемещать плоскость q (`x) = `c `x = const (семейство таких плоскостей образуют линии уровня для q (`x)) в направлении `N (так чтобы она оставалась перпендикулярной `N) в сторону убывания функции q (`x). При этом возможны следующие случаи: а) плоскость q (`x) = `c `x = const и D будут иметь лишь одну общую точку (вершину многогранника), определяющую единственное решение модели ЛП (рис. 2, а – точка А); б) плоскость q (`x) = `c `x = const и D имеют целое множество общих точек (плоскость совпадает с ребром или гранью многогранника – в случае их параллельности плоскости), определяющих бесчисленное множество решений (рис. 2, б – точки грани АЕ).

Предположим, что допустимое множество D неограничено; если функция q (`x) ограничена снизу, то задача разрешима в рамках вышерассмотренных двух случаев. Если нет – решение в обычном понимании отсутствует.