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

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

Порядок действий

1. Используя симплекс-метод, без учёта требования целочисленности, получаем набор равенств:

$x_{i}+\sum {\bar {a}}_{i,j}x_{j}={\bar {b}}_{i},$

где $x_{i}$ — переменные базиса, а $x_{j}$ — свободные переменные

2. Вводим новое ограничение ($k$ соответствует переменной $x_{k},$ которая в оптимальном плане имеет максимальную дробную часть):

$k={\underset {t}{\operatorname {argmax} }}({\bar {b}}_{t}-\lfloor {\bar {b}}_{t}\rfloor )={\underset {t}{\operatorname {argmax} }}\{b_{t}\}$

$\sum (\lfloor {\bar {a}}_{k,j}\rfloor -{\bar {a}}_{k,j})x_{j}\leqslant \lfloor {\bar {b}}_{k}\rfloor -{\bar {b}}_{k}\quad \sim \quad -\sum \{a_{k,j}\}x_{j}\leqslant -\{{\bar {b}}_{k}\}\quad \sim \quad \sum \{a_{k,j}\}x_{j}\geqslant \{{\bar {b}}_{k}\}$

где $\lfloor \cdot \rfloor$ — пол (см. целая часть)

3. Если при решении с новым ограничением получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.

Литература

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