Алгоритм Го́мори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм разработан в 1950-х годах американским математиком Ральфом Гомори.
Порядок действий 1. Используя симплекс-метод, без учёта требования целочисленности, получаем набор равенств:
где — переменные базиса, а — свободные переменные
2. Вводим новое ограничение ( соответствует переменной которая в оптимальном плане имеет максимальную дробную часть):
где — пол (см. целая часть)
3. Если при решении с новым ограничением получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап. Литература
Категория:Алгоритмы оптимизации