Геометрический смысл системы линейных неравенств

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

Случай двух проектных параметров.

Начнем с рассмотрения одного линейное неравенство с двумя параметрами х ₁, х _2:

Областью решения неравенства (6.6), является множество точек, удовлетворяющих этому неравенству, т.е. полуплоскость Р, ограниченная прямой L:

Прямая L разбивает всю плоскость на 2-е полуплоскости. Для определения какую из двух полуплоскостей описывает неравенство (6.6), достаточно выбрать точку из одной из полуплоскостей. И если координаты этой точки удовлетворяют неравенству, то оно и описывает именно эту полуплоскость. Самою прямую L считаем принадлежащей этой полуплоскости

n Пример 6.1. Найти полуплоскость, определяемую неравенством:

Рассмотрим прямую , разбивающую всю плоскость на две полуплоскости. Выбрав точку М (0, 0), легко убедиться, что координаты ее не удовлетворяют исходному неравенству. Это означает, что неравенство определяет полуплоскость, расположенную «выше» этой прямой и самою эту прямую (рис.6.5).

Рис.6.5. Область решения неравенства

Случай m (m > 1) неравенств.

Предположим теперь, что задано не одно неравенство, а система из m неравенств:

Каждое неравенство определяет некоторую полуплоскость P _i, (i =1, 2,.., m). Областью допустимых решений системы неравенств (6.7) является некоторая многоугольная область , полученная в результате пересечения конечного числа полуплоскостей, описываемых каждым отдельным неравенством. Если эта область ограничена, то ее называют многоугольником допустимых решений системы (6.7).

Область решения системы (6.7) может быть замкнутой ограниченной (рис.6.6, а) или замкнутой неограниченной многоугольной областью (рис.6.6, б), а может быть и пустой (рис.6.6, в), когда система (6.7) противоречива.

a)	б)	в)

Рис.6.6. Области допустимых решений системы неравенств

Областью допустимых решений обладает важным свойство - она является выпуклой.

Область называется выпуклой, если она расположена по одну сторону прямой, проходящей через какой-либо отрезок границы области. Или, когда две произвольные точки области можно соединить отрезком, полностью принадлежащим этой области (рис.6.7).

Рис. 6.7.а. Выпуклый многоугольник	Рис. 6.7.б. Невыпуклый многоугольник

Выпуклость многоугольника решений вытекает из способа его построения: он получен путем пересечения нескольких полуплоскостей.

Случай n проектных параметров.

Сказанное выше можно обобщить для случая n проектных параметров. Система ограничений в этом случае имеет вид (6.5).

Каждое неравенство системы ограничений (6.5):

определяет некоторое полупространство P_i, а все неравенства - некоторую область в n -мерном пространстве, которая является пересечением конечного числа полупространств.

По аналогии с двумерным случаем называем эту область в n - мерном пространстве выпуклой многогранной областью, а в случае ее ограниченности - выпуклым многогранником.

Совокупность точек n -мерного пространства, координаты которого удовлетворяют системе (6.5), есть замкнутая выпуклая многогранная область , получающаяся в результате пересечения всех m полупространств, отвечающих неравенствам системы. Если эта область ограничена, мы называем ее выпуклым многогранником в пространстве.

Опорной прямой (при n =2) называется прямая, которая имеет с областью , по крайней мере, одну общую точку. При этом вся область расположена по одну сторону от этой прямой. Например, на рис.6.8 приведены две опорные прямые: L 1 и L 2. Прямая L 1 проходит через вершину области , а L 2 – через сторону .

L2 L1 Рис. 6.8. К определе-нию опорной прямой

При n =3 уже говорят об опорной плоскости, которая может проходить через вершину многогранника, или его ребро, или его грань. Понятие опорной плоскости (гиперплоскости) легко обобщить на случай n> 3.