Студопедия

КАТЕГОРИИ:

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


Симплекс метод или метод последовательного уточнения оценок




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

 

Метод предназначен для решения общей задачи линейного программирования.

Пусть имеем следующую задачу:

,

с системой ограничений следующего вида:

Разрешим эту систему относительно переменных x1,...xm:

(7.3)

Векторы условий, соответствующие x1,...xm, образуют базис. Переменные x1,...xm назовем базисными переменными. Остальные переменные задачи - небазисные.

Целевую функцию можно выразить через небазисные переменные:

.

Если приравнять небазисные переменные нулю

,

то соответствующие базисные переменные примут значения

.

Вектор с такими компонентами представляет собой угловую точку многогранника решений (допустимую) при условии, что bi' ≥ 0 (опорный план).

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

 

Достоинства – при нескольких модификациях является универсальным методом решения ЗЛП.

 

в) Двойственный симплекс-метод. Применяется когда исходную задачу сложнее решить, чем двойственную.

2-я теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов

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

 

2) Задача нелинейного программирования (ЗНП)

,

,

,

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

Можно рассмотреть метод решения задач с линейными ограничениями и нелинейной целевой функцией – метод Франка-Вульфа.

 

Метод Франка-Вульфа. Ограничения содержат только линейные неравенства. Эта особенность является основой для замены в окрестности исследуемой точки нелинейной целевой функции линейной, в результате чего решение исходной задачи сводится к последовательному решению задач линейного программирования

 

Численные методы/Вычислительная математика


Поделиться:

Дата добавления: 2015-04-18; просмотров: 91; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты