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

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

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

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

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

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

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

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

${\displaystyle \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}\}}$

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

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

Литература

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