Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Допустимые базисные решения и многогранник решений




В задачах линейного программирования представляют интерес системы, в которых ранг r матрицы коэффициентов системы А = (аij), i = 1, 2,..., m; j= 1, 2,..., N, или, что то же самое, максимальное число независимых уравнений системы r меньше числа переменных, т.е. r < N. Будем полагать, что все m уравнений системы независимы, т.е. r=m и соответственно m < N.

Любые m переменных системы m линейных уравнений с N переменными (m < N) называются основными (или базисными ), если определитель матрицы коэффициентов при них отличен от нуля. Остальные (N-m) переменных называются неосновными (или свободными ). Основными могут быть разные группы из N переменных. Максимально возможное число групп основных переменных равно числу способов выбора т переменных из их общего числа N, т.е. числу сочетаний . Но так как возможны случаи, когда определитель матрицы коэффициентов при т переменных равен нулю, то число групп основных переменных не превосходит .

Теорема. Если для системы m линейных уравнений с N переменными (где m < N) ранг матрицы коэффициентов при переменных равен m, т.е. существует хотя бы одна группа основных переменных, то эта система является неопределенной, причем каждому произвольному набору значений неосновных переменных соответствует одно решение системы.

Решение системы называется допустимым, если оно содержит лишь неотрицательные компоненты, т.е. хj ³ 0 для любых j = 1, 2,..., N. В противном случае решение называется недопустимым.

Среди бесконечного множества решений системы выделяют так называемые базисные решения. Базисным решением системы m линейных уравнений с N переменными называется решение, в котором все (N - m) неосновных переменных равны нулю. В задачах линейного программирования особый интерес представляют допустимые базисные решения (опорные планы). Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.

Множество допустимых решений системы ограничений задачи линейного программирования является выпуклым многогранником.

Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника ограничений, и наоборот, каждой угловой точке многогранника ограничений соответствует допустимое базисное решение.

Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника ограничений. Если линейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Следовательно, оптимум линейной функции задачи линейного программирования следует искать среди конечного числа ее допустимых базисных решений.




Поделиться с друзьями:


Дата добавления: 2014-01-06; Просмотров: 2389; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.