Метод Гомори

Алгоритм Гомори используется для решения полностью целочисленных задач линейного программирования. Алгоритм включает в себя:

1. Решение задачи одним из методов группы симплекс-методов или группы методов внутренней точки без учета требования целочисленности. Если полученное оптимальное решение целочисленно, то задача решена.
2. Составляется дополнительное ограничение для переменной B[i], которая в оптимальном плане имеет максимальное дробное значение, хотя должна быть целой. Тогда величины коэффициентов элементов A[i,j], B[i] вычисляются так:

$\beta[i,j] = A[i,j] - \operatorname{int}(A[i,j])$ $\beta[i] = B[i] - \operatorname{int}(B[i])$

где $\operatorname{int}(A[i,j])$ — целая часть числа A[i,j]. Тогда дополнительное ограничение формируется следующим образом:

$s[i] = -\beta[i,1](-\xi[1]) - \beta[i,2](-\xi[2]) - \ldots - \beta[i,n](-\xi[n]) - \beta[i] \geqslant 0$

Оно будет целым неотрицательным при целых неотрицательных β[i,j] и ξ[j] После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.