Гомори

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

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

2. Составляется дополнительное ограничение Гомори для основной переменной $X_i$ , которая в оптимальном плане первого этапа не целое и имеет максимальную дробную часть

$\left\{b_i \right\}-\sum_{i=1}^{n}{\left\{a_{ij} \right\}}x_j\leq 0,$

или

$\sum_{i=1}^{n}{\left\{a_{ij} \right\}}x_j\geq \left\{b_i \right\}.$

Здесь $\left\{a\right\}$ — дробная часть числа $a$ .

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

тут

Количество переменных:
Количество ограничений:

Гомори

Добавить комментарий Отменить ответ