Алгоритм Гомори

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

1. Решение задачи одним из методов группы симплекс-методов или группы методов внутренней точки без учёта требования целочисленности. Если полученное оптимальное решение целочисленно, то задача решена.
2. Составляется дополнительное ограничение для переменной $B_i$, которая в оптимальном плане имеет максимальное дробное значение, хотя должна быть целой. Тогда величины коэффициентов элементов $A_{ij}$, $B_i$ вычисляются так:

$\beta _{ij} = A_{ij} - \left[ A_{ij} \right]$

$\beta _i = B_i - \left[ B_i \right]$

где $\left[ A_{ij} \right]$ — целая часть числа $A_{ij}$. Тогда дополнительное ограничение формируется следующим образом:

$s_i = -\beta _{i1}(-\xi _1) - \beta _{i2}(-\xi _2) - \ldots - \beta _{in}(-\xi _n) - \beta _n \geqslant 0$

Оно будет целым неотрицательным при целых неотрицательных $\beta _{ij} ~$ и $\xi _j~$ После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.

Литература

Л.Н.Землянухина, А.Б.Зинченко, Л.И.Сантылова 3 // Методические указания для студентов дневного и вечернего отделений механико-математического факультета по курсу “Методы оптимизации” «Линейное программирование и смежные вопросы». — Ростов-на-Дону, 1998. — С. 24-33. — 36 с.