Метод Гомори для решения задач линейного программирования заключается в следующем: 4

1. Отбрасывается условие целочисленности и полученная задача линейного программирования решается симплекс-методом. 4
2. Если оптимальное решение задачи является целочисленным, то оно является и решением исходной задачи. 4
3. Если оптимальное решение задачи не является целочисленным, то к основным ограничениям добавляется новое линейное ограничение, обладающее следующими свойствами: оптимальный нецелочисленный план задачи ему не удовлетворяет, а любой целочисленный план задачи ему удовлетворяет. 4
4. Затем решается расширенная задача. 4
5. Процесс повторяется до получения целочисленного решения. 4

После ряда отсечений с помощью двойственного симплекс-метода получается искомое целочисленное оптимальное решение. 1