Метод отсекающих плоскостей Гомори: точность в целочисленной оптимизации

Математически метод Гомори опирается на решение исходной линейной задачи симплекс-методом. Если полученное оптимальное решение содержит дробные компоненты, актуарий формирует "отсекающую плоскость" на основе симплекс-таблицы (генерирующей строки). Это ограничение строится таким образом, что оно проходит через дробную вершину, но ни одна целочисленная точка не оказывается за его пределами. После добавления ограничения задача перерешивается симплекс-методом, и процесс продолжается до тех пор, пока решение не станет целочисленным.

Преимуществом метода Гомори является его теоретическая строгость и отсутствие необходимости ветвления, однако на практике метод может столкнуться с проблемой плохой обусловленности системы ограничений и медленной сходимостью. В современных решателях метод Гомори используется в гибридных алгоритмах branch-and-cut, где отсечения добавляются для быстрого сужения области поиска, после чего запускается ветвление. Это сочетание позволяет эффективно справляться с задачами, где простое ветвление работает неэффективно.

Применение метода находит отражение в управлении складскими запасами, планировании производственных мощностей и задач маршрутизации. Важным является выбор правильного типа отсечений (отсечения первого или второго рода), что требует глубокого анализа матрицы ограничений. Исследования показывают, что использование "сильных" отсечений (facet-defining inequalities) позволяет радикально ускорить процесс поиска оптимума.

Владение методом Гомори и принципами формирования отсекающих плоскостей — необходимый навык для оптимизации дискретных систем. Понимание того, как геометрически "подрезать" область допустимых решений, делает аналитика мастером в решении сложных комбинаторных задач, где каждое дополнительное ограничение приближает систему к глобальному целочисленному оптимуму.

Список литературы:
1. Гомори Р.Е. Теория целочисленного программирования. — М.: Мир, 1966.
2. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. — М.: Наука, 1979.
3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. — М.: Мир, 1985.