Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Основные теоремы линейного программирования и идея симплекс-метода




Теоремы приводятся здесь без доказательства. Все их утверждения могут быть легко проверены с использованием геометрической интерпретации ЗЛП.

Теорема 1. Множество допустимых решений ЗЛП является либо пустым, либо замкнутым, выпуклым многогранным множеством, имеющим конечное число крайних точек.

Теорема 2. Если оптимальное решение ЗЛП существует, то ему соответствует хотя бы одна из крайних точек допустимой области ЗЛП.

Теорема 3. Между крайними точками множества допустимых решений ЗЛП и ее допустимыми базисными решениями существует следующее соответствие: каждому допустимому базисному решению соответствует определенная крайняя точка; каждой крайней точке соответствует хотя бы одно допустимое базисное решение (случай, когда одной крайней точке соответствует более одного допустимого базисного решения, возможен лишь для вырожденных базисных решений).

 

 

Из теоремы 1 следует, что ЗЛП является выпуклой задачей математического программирования, так как линейную целевую функцию можно считать как выпуклой, так и вогнутой (в зависимости от направления оптимизации на max или min), а множество допустимых решений по утверждению теоремы является выпуклым. Следовательно, ЗЛП можно отнести к классу одноэкстремальных оптимизационных задач.

Из теорем 2 и 3 следует, что оптимальное решение следует искать среди крайних точек допустимого множества и соответствующих им допустимых базисных решений. Конечное число крайних точек (теорема 1) при их переборе гарантирует сходимость поиска к оптимальному решению за конечное число шагов.

На основе этих теорем может быть следующим образом определена идея алгоритма нахождения оптимального решения ЗЛП, названного алгоритмом симплекс-метода.

Необходимо организовать целенаправленный перебор крайних точек, переходя от одной крайней точке к другой по ребру допустимого множества, соединяющему их. Целенаправленность такого перебора должна определяться выбором такого направления движения (ребра), которое может приводить лишь к увеличению целевой функции (предполагается направление оптимизации на max).

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

Как только алгоритм привел в крайнюю точку (допустимое базисное решение), из которой не исходит ни одного ребра, при движении в направлении которого целевая функция могла бы возрастать, то такое решение является оптимальным решением ЗЛП.

 




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


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


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



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




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