Автор Елена Андреенкова задал вопрос в разделе Наука, Техника, Языки
В чем заключается симплекс-метод? и получил лучший ответ
Ответ от Аркадий[гуру]
Симплекс-метод это метод решения оптимизационных задач. Задача оптимизации предполагает нахождение значения переменных, максимизирующих/минимизирующих целевую функцию. Господин Osipov выше верно описал с графической точки зрения суть метода.
А в общем метод, действительно, предполагает перебор переменных на роль оптимизирующих.
Ответ от Ўрий Семыкин[гуру]
Ограничения в задаче ЛП - гиперплоскости - высекают вместе с координатными (гипер) плоскостями симплексы (пирамидки) в пространстве. Практически важные задачи ЛП имеют много переменных, стоит задача быстро решить задачу оптимизации, классические методы будут медленно работать. Даже зная, что оптимум достигается в одной из вершин - перебрать все вершины часто нереально. Придуман был метод, - начиная с одной из вершин (опорного решения - точки, удовлетворяющей всем ограничениям и "крайней" - т. е. часть ограничений из неравенств переходит в равенства) перейти к соседней вершине - "не хуже" с т. з. критерия оптимизации. Получается сильное сокращение перебора. Кроме того, вершина - результат решения системы уравнений - перейти в соседнюю вершину можно не решая заново систему, а немного "подправив" предыдущее решение - метод включений и исключений Жордана. Две эти составляющие (направленный перебор + метод Жордана) и дают симплекс метод. Метод был использован (и разработан) Канторовичем для оптимадьного раскроя листов фанеры, но он вначале не оценил важности и общности метода. Данциг и Вулф - оценили, открыв его независимо, поэтому в затубежной литературе СМ часто называют "метод Данцига-Вулфа", иногда добавляют Фолкерсона - систематически его изложившего. Всё это середина 50, начало 60гг прошлого столетия.
Ограничения в задаче ЛП - гиперплоскости - высекают вместе с координатными (гипер) плоскостями симплексы (пирамидки) в пространстве. Практически важные задачи ЛП имеют много переменных, стоит задача быстро решить задачу оптимизации, классические методы будут медленно работать. Даже зная, что оптимум достигается в одной из вершин - перебрать все вершины часто нереально. Придуман был метод, - начиная с одной из вершин (опорного решения - точки, удовлетворяющей всем ограничениям и "крайней" - т. е. часть ограничений из неравенств переходит в равенства) перейти к соседней вершине - "не хуже" с т. з. критерия оптимизации. Получается сильное сокращение перебора. Кроме того, вершина - результат решения системы уравнений - перейти в соседнюю вершину можно не решая заново систему, а немного "подправив" предыдущее решение - метод включений и исключений Жордана. Две эти составляющие (направленный перебор + метод Жордана) и дают симплекс метод. Метод был использован (и разработан) Канторовичем для оптимадьного раскроя листов фанеры, но он вначале не оценил важности и общности метода. Данциг и Вулф - оценили, открыв его независимо, поэтому в затубежной литературе СМ часто называют "метод Данцига-Вулфа", иногда добавляют Фолкерсона - систематически его изложившего. Всё это середина 50, начало 60гг прошлого столетия.
Ответ от Alexander Osipov[гуру]
как известно решение задачи линейного программирования находится в одной из вершин многоугольника ограничивающего область
насколько я помню (могу быть неправ) симплекс-метод предоставляет оптимизированный перебор (не всех - их много) таких вершин для поиска той самой которая самая лучшая
как известно решение задачи линейного программирования находится в одной из вершин многоугольника ограничивающего область
насколько я помню (могу быть неправ) симплекс-метод предоставляет оптимизированный перебор (не всех - их много) таких вершин для поиска той самой которая самая лучшая
Ответ от 3 ответа[гуру]
Привет! Вот подборка тем с похожими вопросами и ответами на Ваш вопрос: В чем заключается симплекс-метод?