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

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

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

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

$x_i+\sum {\overline{a}}_{i,j}{x}_j={\overline{b}}_i,$

где $x_i$ — переменные базиса, а $x_j$ — свободные переменные

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

$k=\underset{t}{\mathrm{argmax}}({\overline{b}}_t-\lfloor {\overline{b}}_t\rfloor )=\underset{t}{\mathrm{argmax}}\{b_t\}$

$\sum (\lfloor {\overline{a}}_{k,j}\rfloor -{\overline{a}}_{k,j})x_j⩽\lfloor {\overline{b}}_k\rfloor -{\overline{b}}_k\sim -\sum \{a_{k,j}\}{x}_j⩽-\{{\overline{b}}_k\}\sim \sum \{a_{k,j}\}{x}_j⩾\{{\overline{b}}_k\}$

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

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