Графическое представление задачи ЛП

Любое неотрицательное решение системы ограничений называется допустимым. Допустимое решение, доставляющее min (max) в линейной форме, называется оптимальным. Совокупность всех допустимых решений системы ограничений называется областью решений.

Рассмотрим систему ограничений в виде равенств

Допустим, что существует решение системы (1), т.е. система линейных уравнений совместна

rangA=rangB

rangA=n-система (1) имеет единственное решение

rangA<n-бесконечно большое число решений

col(x₁ x₂…x_n)=x-единственное решение

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

,

которые дают экстремальное значение R.

Проиллюстрируем сказанное на примере 2-х переменных R=х₁+х₂ и задана система ограничений типа неравенств

2 х₁+ х₂≤1

х₁+2 х₂≤1 (4)

Неравенство (4) на плоскости х₁ и х₂ будут определять ограниченную область рис 15.1

X^opt=argmaxR(), 2 х₁+ х₂≤1, х₁+2 х₂≤1

Требования (свойства) к области допустимых решений:

1.Область должна быть выпуклой

Для многогранной области это будет равносильно тому, что вся область лежит по одну сторону от гиперплоскости, проходящей через грань области. Критерий оптимальности в виде линейной формы (3) определяет на плоскости некоторую прямую. R м.б. достигнуто либо в одной точке и эта точка является вершиной области, либо в бесчисленном множестве точек и это геометрическое место есть гиперплоскость, ограничивающая эту область.