Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




Как отличить вершины допустимого множества от других решений задачи? Пусть каноническая модель содержит переменных и 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 тысяч опорных решений. В таких случаях приходится обращаться к соответствующим методам решения линейных задач (осн. их часть базируется на методе Данцигела).








Дата добавления: 2015-04-19; просмотров: 555. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2020 год . (0.002 сек.) русская версия | украинская версия