Теоретические основы методов отсечения

Попробуем охарактеризовать поведение алгоритмов метода отсечения при решении задач целочисленного линейного программирования. В качестве меры продолжительности вычислений могут рассматриваться количество симплексных итераций I и количество правильных отсечений (дополнительных линейных ограничений) D.
Для первого алгоритма Гомори и различных его обобщений I и D также тесно связаны между собой (как показывает эксперимент, в большинстве случаев решение отдельной задачи (£, С) требует сравнительно небольшого количества симплексных итераций).

Введение 3
1.Постановка линейной целочисленной задачи 5
2.Теоретические основы методов отсечения 8
2.1 Первый алгоритм Гомори 12
2.2 Второй алгоритм Гомори 18
Заключение 20
Список используемых источников 23