[править] Фазы решения
После того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как yi, i∈{1, .., k}, то вспомогательную функцию определим, как
.
После этого проводится обыкновенный симплекс-метод относительно вспомогательной целевой функции. Поскольку все вспомогательные переменные увеличивают значение z', в ходе алгоритма они будут поочерёдно выводится из базиса, при этом после каждого перехода новое решение будет всё ближе к множеству допустимых решений.
Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:
оптимальное значение z' больше нуля. Это значит, что как минимум одна из вспомогательных переменных осталась в базисе. В таком случае можно сделать вывод, что допустимых решений данной задачи линейного программирования не существует.
оптимальное значение z' равно нулю. Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым.
Во втором случае мы имеем допустимый базис, или, иначе говоря, исходное допустимое решение. Можно проводить дальнейшую оптимизацию с учётом исходной целевой функции, при этом уже не обращая внимания на вспомогательные переменные. Это и явлется второй фазой решения.
[править] Модифицированный симплекс-метод
[править] Двойственный симплекс-метод
[править] Литература
Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8
Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.
п··р
Методы оптимизации
Одномерные Метод золотого сечения • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод троичного поиска
Прямые методы Метод Гаусса • Метод Нелдера — Мида • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса
Первого порядка Градиентный спуск • Метод покоординатного спуска • Метод сопряжённых градиентов
Второго порядка Метод Ньютона • Метод Ньютона-Рафсона
Стохастические Дифференциальная эволюция • Имитация отжига
Методы линейного
программирования Метод эллипсоидов • Симплекс-метод • Метод потенциалов
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её.