Выделение вершин допустимого множества

Как отличить вершины допустимого множества от других решений задачи? Пусть каноническая модель содержит переменных и m линейно-независимых равенств. Тогда размерность пространства переменных k = - m. На каждой границе допустимого множества одна из переменных равна нулю. В k –мерном пространстве вершина образуется пересечением k гиперплоскостей. Поэтому в ней k переменных заведомо равны нулю и только m переменных могут быть ненулевыми, т.к. - k = - + m = m. Если из вершины сместиться в любом направлении, то число ненулевых переменных увеличивается. В точках, не лежащих на границах условий, все переменные не равны нулю. Решение системы уравнений с рангом m содержит m базисных переменных и - m свободных (небазисных). Если все свободные переменные равны нулю, то решение называется базисным. Каждой вершине множества D соответствует некоторое базисное решение системы равенств. На самом деле в вершине могут пересекаться более k гиперплоскостей. Тогда в нуль обращается более k переменных (вырожденные решения, вырожденные задачи). Число “лишних” плоскостей (n) определяет степень вырожденности. В общем случае в базисном решении число ненулевых переменных равно m-n и базисное решение - решение, в котором число ненулевых переменных не больше m. В любом другом решении таких переменных больше m.

Базисное решение с неотрицательными переменными - допустимое базисное решение или опорным планом (решением). Вывод: оптимальное решение задачи ЛП следует искать среди опорных решений, геометрически – в вершинах (крайних точках) допустимого множества. Число базисных решений системы линейных уравнений с n переменными и рангом r определяется сочетанием

Из них примерно 40% опорных. для задачи: 10 неравенств с 10 переменными - каноническая форма будет иметь систему уравнений с 20 переменными и рангом r=10. Получаем ~185 тыс базисных решений и, порядка 70 тысяч опорных решений. В таких случаях приходится обращаться к соответствующим методам решения линейных задач (осн. их часть базируется на методе Данцигела).