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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

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

где — пол (см. целая часть)

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

Литература

[править | править код]

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