Метод симплекс
- Автор метода
- George Dantzig
- Год
- 1947
- Тип
- algorithm
- Семейство
- Optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Метод симплекс, разработанный Джорджем Данцигом в 1947 году, является фундаментальным алгоритмом для решения задач линейного программирования.
Он систематически исследует вершины допустимой области для нахождения оптимального решения, где целевая функция максимизируется или минимизируется при линейных ограничениях.
Интуиция метода
Метод работает, начиная с угловой точки (вершины) допустимой области, определяемой линейными ограничениями, затем переходя к смежным вершинам, которые улучшают значение целевой функции. Он продолжается до тех пор, пока не будет достигнута вершина, где ни одна смежная вершина не предлагает дальнейшего улучшения, что гарантирует оптимальность. Алгоритм использует геометрическое свойство, согласно которому линейные программы имеют свои оптимальные решения в вершинах политопа ограничений.
История
Джордж Данциг представил метод симплекс в 1947 году, произведя революцию в исследовании операций и став стандартным алгоритмом для линейного программирования на десятилетия. Кли и Минти (1972) показали экспоненциальную сложность в худшем случае, однако эмпирически метод оставался быстрым. В 1980-х годах были разработаны методы внутренней точки как альтернативы, но метод симплекс оставался доминирующим для многих практических применений благодаря своей надежности и сложности современных реализаций.
Когда применять
Применять метод симплекс при решении задач линейного программирования с ограниченными допустимыми областями и линейной целевой функцией. Он особенно эффективен для задач с сотнями или тысячами переменных и ограничений. Избегайте его использования, если задача нелинейна или неограничена. Методы внутренней точки могут быть предпочтительнее для очень крупномасштабных задач.
Ограничения и замечания
- Экспоненциальная сложность в худшем случае (хотя и редко на практике)
- Может работать плохо на сильно вырожденных задачах
- Менее конкурентоспособен, чем методы внутренней точки, для очень крупномасштабных задач
- Требует, чтобы задачи были в стандартной форме с явной обработкой ограничений
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Гарантирует нахождение оптимального решения за конечное время для линейных программ
- Эффективен на практике при тщательной реализации и обработке вырождения
- Широко реализован и поддерживается зрелыми библиотеками оптимизации
- Основа для понимания более продвинутых алгоритмов оптимизации
Применение
- Планирование производства: оптимизация объемов производства для минимизации затрат при соблюдении ограничений спроса
- Транспорт и логистика: определение оптимальных маршрутов и объемов перевозок между складами и распределительными центрами
- Оптимизация портфеля: распределение капитала между активами для максимизации доходности с учетом ограничений риска и бюджета
- Распределение ресурсов: распределение ограниченных ресурсов, таких как рабочая сила и материалы, для максимизации организационного выпуска
- Задачи смешивания: смешивание сырья в оптимальных пропорциях для удовлетворения спецификаций качества и минимизации затрат
- Составление расписаний рабочей силы: назначение работников на смены для минимизации затрат на рабочую силу при соблюдении спроса
Как это работает
Как это работает
Преобразовать линейную программу к стандартной форме с помощью дополнительных переменных и определить начальное допустимое базисное решение (обычно начало координат, если оно допустимо).
Выполнить операции поворота на симплекс-таблице: выбрать входящую переменную с отрицательной приведенной стоимостью, определить выходящую переменную с помощью теста минимального отношения и обновить базис.
Проверить условия оптимальности с использованием приведенных стоимостей; если все приведенные стоимости неотрицательны для максимизации, текущее решение оптимально; в противном случае вернуться к шагу поворота.
Частые ошибки
- Неспособность правильно обрабатывать цикличность при столкновении с вырожденными базисами (использовать правило Блэнда или методы возмущений)
- Неправильный выбор поворота или ошибки вычислений при обновлении таблиц, приводящие к числовой нестабильности
- Непроверка на неограниченность или недопустимость перед началом алгоритма
Часто задаваемые вопросы
Почему метод симплекс называется 'симплекс'?
Термин 'симплекс' относится к простейшей форме политопа в любом заданном измерении. Алгоритм работает, перемещаясь по ребрам и вершинам политопа, определяемого ограничениями.
В чем разница между методом симплекс и методом внутренней точки?
Метод симплекс остается на границе допустимой области в вершинах, в то время как методы внутренней точки проходят через внутреннюю часть. Методы внутренней точки имеют лучшую сложность в худшем случае, но симплекс часто быстрее на практике для задач среднего размера.
Как обрабатывать недопустимость или неограниченность?
Используйте двухфазный метод симплекс: первая фаза решает вспомогательную задачу для нахождения допустимого базисного решения или определения недопустимости; вторая фаза применяет стандартный метод симплекс к исходной задаче.
Что такое вырождение и почему оно важно?
Вырождение возникает, когда допустимое базисное решение имеет более одного базисного представления, что может вызвать цикличность. Обрабатывайте его с помощью правила Блэнда (выбирайте переменные по порядку индексов) или методов возмущений.
Похожие методы
Источники
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Открыть ссылку DOIСкопировано.Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.
Открыть ссылку DOIСкопировано.