WikiSort.ru - Программирование

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

1. Решение задачи одним из методов группы симплекс-методов или группы методов внутренней точки без учёта требования целочисленности. Если полученное оптимальное решение целочисленно, то задача решена.
2. Составляется дополнительное ограничение для переменной ${\displaystyle B_{i}}$ , которая в оптимальном плане имеет максимальное дробное значение, хотя должна быть целой. Тогда величины коэффициентов элементов ${\displaystyle A_{ij}}$ , ${\displaystyle B_{i}}$ вычисляются так:

${\displaystyle \beta _{ij}=A_{ij}-\left[A_{ij}\right]}$

${\displaystyle \beta _{i}=B_{i}-\left[B_{i}\right]}$

где ${\displaystyle \left[A_{ij}\right]}$ — целая часть числа ${\displaystyle A_{ij}}$ . Тогда дополнительное ограничение формируется следующим образом:

${\displaystyle s_{i}=-\beta _{i1}(-\xi _{1})-\beta _{i2}(-\xi _{2})-\ldots -\beta _{in}(-\xi _{n})-\beta _{n}\geqslant 0}$

Оно будет целым неотрицательным при целых неотрицательных ${\displaystyle \beta _{ij}}$ и ${\displaystyle \xi _{j}}$ После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап. Метод разработан в 1950-х годах американским математиком Ральфом Гомори.

Литература

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.