Курсовая работа: Методы отсечения
Тогда первый алгоритм Гомори требует конечного числа больших итераций.
4. Второй алгоритм Гомори
Второй алгоритм Р. Гомори предназначается для решения задач, в которых требование целочисленности наложено на некоторые переменные (в частности и на все). Мы его рассмотрим применительно к задачам частично целочисленного типа, понимая, что вычислительная схема будет справедливой и для задач, полностью целочисленных.
Пусть в области, определенной условиями:
(20)
(21)
– целые, 
(22)
требуется максимизировать функцию
(23)
Метод решения задачи (20–23) основывается на той же идее, что и метод решения полностью целочисленных задач. А именно: строится область £k , которая при k = 0 определяется условиями (20–21); решается полученная при этом задача линейного программирования (20–21, 23). Если задача (20–21, 23) оказывается разрешимой, то полученное оптимальное решение ее анализируется на допустимость для исходной задачи целочисленного программирования (20–23). Если найденное решение оказывается целочисленным, то одновременно оно будет оптимальным для (20–23). Если оптимальное решение (£k , C) – задачи оказывается недопустимым для исходной задачи (20–23), то осуществляется построение правильного отсечения и переход к решению новой задачи,
Второй алгоритм Р. Гомори формулируется в виде следующей теоремы:
Теорема. Пусть х(£k , C) – оптимальное решение (£k , C) – задачи, 
– элементы соответствующей ему симплексной таблицы. Если 
– нецелое 
, то
(24)
– целое, (25)
где
(26)
определяет правильное отсечение. Блок-схема второго алгоритма Р. Гомори аналогична блок-схеме первого алгоритма Р. Гомори и отличается лишь правилом построения коэффициентов правильного отсечения.
Правило построения правильного отсечения
Пусть x(£k , C) не удовлетворяет условию целочисленности, 
– элементы симплексной таблицы, соответствующей полученному оптимальному решению (£k , C) – задачи. Выберем i 0 = min { i | i Î (1, 2,…, n ), xi 0 k – нецелое} и строим правильное отсечение по формулам (24 – 26).
Условия конечности второго алгоритма Гомори:
1) Целевая функция F ( x ) удовлетворяет условию целочисленности. Это учитывается при выборе строки k для построения правильного отсечения.
2) Выполнено по крайней мере одно из двух условий:
2') целевая функция ограничена снизу на многогранном множестве £= £0 ;
2») задача (£0 ц , C) имеет по крайней мере один план.
С помощью второго алгоритма Гомори можно (в случае n1 =n) решать и полностью целочисленную задачу линейного программирования. Однако в этом случае нет оснований для сравнения эффективности второго и первого алгоритмов Гомори.
5. Алгоритм Дальтона и Ллевелина
Второй алгоритм Гомори имеет дело с частично целочисленными задачами линейного программирования. Дальтон и Ллевелин рассматривают 0 олее широкий класс задач – частично дискретные задачи линейного программирования и применительно к ним модифицируют второй алгоритм Гомори.
Напомним, что решением задачи дискретного программирования будем называть вектор, координаты которого принадлежат £ц области вида:
(27)