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