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

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

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

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

$x_i+\sum <!--\; \sum \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_{i,j}{x}_j={\stackrel{¯<!--\; ¯\; -->}{b}}_i,$$x_{i}+\sum {\bar {a}}_{i,j}x_{j}={\bar {b}}_{i},$ 

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

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

$k=\underset{t}{\mathrm{argmax}}({\stackrel{¯<!--\; ¯\; -->}{b}}_t-<!--\; -\; -->\lfloor <!--\; \lfloor \; -->{\stackrel{¯<!--\; ¯\; -->}{b}}_t\rfloor <!--\; \rfloor \; -->)=\underset{t}{\mathrm{argmax}}\{b_t\}$$k={\underset {t}{\operatorname {argmax} }}({\bar {b}}_{t}-\lfloor {\bar {b}}_{t}\rfloor )={\underset {t}{\operatorname {argmax} }}\{b_{t}\}$ 

$\sum <!--\; \sum \; -->(\lfloor <!--\; \lfloor \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_{k,j}\rfloor <!--\; \rfloor \; -->-<!--\; -\; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_{k,j})x_j⩽<!--\; ⩽\; -->\lfloor <!--\; \lfloor \; -->{\stackrel{¯<!--\; ¯\; -->}{b}}_k\rfloor <!--\; \rfloor \; -->-<!--\; -\; -->{\stackrel{¯<!--\; ¯\; -->}{b}}_k\sim <!--\; \sim \; -->-<!--\; -\; -->\sum <!--\; \sum \; -->\{a_{k,j}\}{x}_j⩽<!--\; ⩽\; -->-<!--\; -\; -->\{{\stackrel{¯<!--\; ¯\; -->}{b}}_k\}\sim <!--\; \sim \; -->\sum <!--\; \sum \; -->\{a_{k,j}\}{x}_j⩾<!--\; ⩾\; -->\{{\stackrel{¯<!--\; ¯\; -->}{b}}_k\}$$\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 <!--\; \lfloor \; -->\cdot <!--\; \cdot \; -->\rfloor <!--\; \rfloor \; -->$$\lfloor\cdot\rfloor$  — пол (см. целая часть)

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

ЛитератураПравить

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