Гомори
Метод Гомори — алгоритм, который используется для решения целочисленных задач линейного программирования. Алгоритм включает в себя:
1. Основная задача без учёта требования целочисленности решается симплекс-методом. Если полученное оптимальное решение целочисленно, то задача решена.
2. Составляется дополнительное ограничение Гомори для основной переменной 
, которая в оптимальном плане первого этапа не целое и имеет максимальную дробную часть
![\[ \left\{b_i \right\}-\sum_{i=1}^{n}{\left\{a_{ij} \right\}}x_j\leq 0, \]](http://chessmsv.ru/wp-content/ql-cache/quicklatex.com-a678e3692d32317822bf58aa157046ec_l3.png "Rendered by QuickLaTeX.com")
или
![\[ \sum_{i=1}^{n}{\left\{a_{ij} \right\}}x_j\geq \left\{b_i \right\}. \]](http://chessmsv.ru/wp-content/ql-cache/quicklatex.com-749e75a99b22f7c916780b6cbc582748_l3.png "Rendered by QuickLaTeX.com")
Здесь 
— дробная часть числа 
.
После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении двойственным симплекс-методом. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.
Добавить комментарий