Любое неотрицательное решение системы ограничений называется допустимым. Допустимое решение, доставляющее min (max) в линейной форме, называется оптимальным. Совокупность всех допустимых решений системы ограничений называется областью решений.
Рассмотрим систему ограничений в виде равенств
Допустим, что существует решение системы (1), т.е. система линейных уравнений совместна
rangA=rangB
rangA=n-система (1) имеет единственное решение
rangA<n-бесконечно большое число решений
col(x1 x2…xn)=x-единственное решение
Во втором случае каждое решение системы ограничений в пространстве с системой координат определяет некоторую гиперплоскость. Появляется возможность среди множества решений подбора таких значений как
,
которые дают экстремальное значение R.
Проиллюстрируем сказанное на примере 2-х переменных R=х1+х2 и задана система ограничений типа неравенств
2 х1+ х2≤1
х1+2 х2≤1 (4)
Неравенство (4) на плоскости х1 и х2 будут определять ограниченную область рис 15.1
Xopt=argmaxR(), 2 х1+ х2≤1, х1+2 х2≤1
|
|
Требования (свойства) к области допустимых решений:
1.Область должна быть выпуклой
Для многогранной области это будет равносильно тому, что вся область лежит по одну сторону от гиперплоскости, проходящей через грань области. Критерий оптимальности в виде линейной формы (3) определяет на плоскости некоторую прямую. R м.б. достигнуто либо в одной точке и эта точка является вершиной области, либо в бесчисленном множестве точек и это геометрическое место есть гиперплоскость, ограничивающая эту область.