Гомори
Метод Гомори — алгоритм, который используется для решения целочисленных задач линейного программирования. Алгоритм включает в себя:
1. Основная задача без учёта требования целочисленности решается симплекс-методом. Если полученное оптимальное решение целочисленно, то задача решена.
2. Составляется дополнительное ограничение Гомори для основной переменной , которая в оптимальном плане первого этапа не целое и имеет максимальную дробную часть
или
Здесь — дробная часть числа .
После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении двойственным симплекс-методом. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.
Добавить комментарий