- Алгоритм Гомори
-
Алгори́тм Го́мори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм включает в себя:
- Решение задачи одним из методов группы симплекс-методов или группы методов внутренней точки без учёта требования целочисленности. Если полученное оптимальное решение целочисленно, то задача решена.
- Составляется дополнительное ограничение для переменной , которая в оптимальном плане имеет максимальное дробное значение, хотя должна быть целой. Тогда величины коэффициентов элементов , вычисляются так:
где — целая часть числа . Тогда дополнительное ограничение формируется следующим образом:
Оно будет целым неотрицательным при целых неотрицательных и После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.
Литература
Л.Н.Землянухина, А.Б.Зинченко, Л.И.Сантылова 3 // Методические указания для студентов дневного и вечернего отделений механико-математического факультета по курсу “Методы оптимизации” «Линейное программирование и смежные вопросы». — Ростов-на-Дону, 1998. — С. 24-33. — 36 с.
Методы оптимизации Одномерные Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск Прямые методы Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка Первого порядка Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта Второго порядка Метод Ньютона • Метод Ньютона — Рафсона Стохастические Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц Методы линейного
программированияСимплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов Методы нелинейного
программированияПоследовательное квадратичное программирование Категория:- Алгоритмы оптимизации
Wikimedia Foundation. 2010.