4.7. Выделение вершин допустимого множества
Из последнего вывода возникает вопрос: как отличить вершины допустимого множества от других решений задачи? Для поиска ответа снова обратимся к геометрическим представлениям.
Пусть
каноническая модель содержит
переменных и m
линейно-независимых равенств. Тогда
размерность пространства переменных
k=
-m.
Как показано выше (рис. 4.2), на каждой
границе допутимого множества одна из
переменных равна нулю. В k –мерном
пространстве вершина образуется
пересечением k
гиперплоскостей. Поэтому в ней k
переменных заведомо равны нулю и только
m
переменных могут быть ненулевыми,
т.к.
-k=
-
+m=m.
Если из вершины сместиться в любом
направлении, то число ненулевых переменных
увеличвается. Так при сдвиге из вершины
С (рис. 4.2) по ребру в сторону вершины В
к ненулевым переменным добавлятся x4.
В точках, не лежащих на границах условий,
все переменные не равны нулю. Из линейной
алгебры известно, что решение системы
уравнений с рангом m
содержит m
базисных
переменных и
-m
свободных (небазисных). Если все свободные
переменные равны нулю, то решение
называется базисным.
Следовательно, каждой вершине множества
D
соответствует некоторое базисное
решение системы равенств.
На самом деле в вершине могут пересекаться более k гиперплоскостей (на плоскости – больше двух прямых; в трехмерном пространстве, например, вершина не в основании пирамиды образуется пересечением плоскостей, число которых может быть больше 3-х – по числу вершин многоугольника в ее основании). Тогда в нуль обращается более k переменных. Такие базисные решения (вершины) называют вырожденными, и задачи, имеющие хотя бы одно вырожденное решение, также называют вырожденными. Число “лишних” плоскостей () определяет степень вырожденности. Поэтому в общем случае в базисном решении число ненулевых переменных равно m- и можно определить базисное решение как решение, в котором число ненулевых переменных не больше m. В любом другом решении таких переменных больше m.
Однако не каждое базисное решение соответствует вершине допустимого множества, так как пересечение k или более гиперплоскостей имеет место и вне этого множества. Это наглядно видно и на рис.4.2, где k =2. Учитывая, что на каждой границе одна переменная равна нулю, с одной стороны границы эта перемнная будет положитльной, а с другой отрицательной. В допустимом множестве все переменные неотрицательны. Таким образом, мы легко отделяем базисные решения, соотвтствующие вершинам множества D, от базисных решений, им не соответствующих. Базисное решение с неотрицательными переменными будем называть допустимым базисым решением или опорным планом (решением).
Вывод: оптимальное решение задачи ЛП следует искать среди опорных решений, геометрически – в вершинах (крайних точках) допустимого множества.
Так как число вершин всегда конечно, то, казалось бы, задача может быть легко решена путем исследования всех вершин. Оценим такую возможность.
Известно, что число базисных решений системы линейных уравнений с n переменными и рангом r определяется сочетанием
Из них примерно 40% опорных. Возьмем небольшую задачу ЛП: 10 неравенств с 10 переменными. В канонической форме будем иметь систему уравнений с 20 переменными и рангом r=10. Получаем 184756 базисных решений и, значит, порядка 70 тысяч вершин (опорных решений). Столько раз нужно вычислить координаты вершин и значение критерия, а затем сравнить. Если учесть, что реальные задачи содержат сотни и тысячи ограничений и переменных, то становится ясным, что такой способ решения неприемлем даже при самых мощных компьютерах. В таких случаях приходится обращаться к соответствующим методам решения линейных задач.
