28.Второй алгоритм Гомори для решения частично целочисленной задачи линейного программирования.

Он имеет дело с более широким классом задач. Рассматривается частично ЦЧ задача ЛП. ; ; ;

Теорема: Пусть последовательность – опт. опорный план задачи и , , (где , – индексы небазисных переменных) – соотв. симпл. таблица, . Тогда неравенство , или, что то же самое: ,

является правильным отсечением. Здесь , (4)

П равило построения правильного отсечения:

Пусть не удовл. усл. ЦЧ и – соотв. ему симпл. таблица. Выбираем

, ( если гарантирована целочисленность целевой функции) и строим правильное отсечение: , ;

и определяется по (4) и (5) при . Что важно, не требуется, чтобы было целым.

С помощью 2-го алгоритма можно решать и полностью ЦЧ задачи ( ).

29.Третий алгоритм Гомори (полностью целочисленный).

Третий алгоритм предназначен для решения полностью ЦЧ задачи ЛП.

; ; ; – целые.

Схема 3-го алгоритма Гомори. Отправляясь от начальной -нормальной таблицы , с помощью итераций -метода получают последовательность таблиц , последняя из которых является допустимой. строится полностью ЦЧ, затем отыскивается ЦЧ правильное отсечение. Дробные числа в следующей таблице получаются из-за присутствия в формулах преобразования операции деления. В этом случае ЦЧ-ность новой таблицы м.б. гарантирована лишь в том случае, если разр. элемент будет равен (-1). Это и делается в 3-ем алгоритме Гомори при построении отсечения.

Формулировка ЦЧ правильного отсечения: Пусть , - недопустимая ЦЧ таблица, -нормальная. Тогда должно удовлетворять следующим условиям:

1. – целое

2. Условие отсечения: .

3. Условие правильности. Для любого плана задачи выполняется: .

4. Условие сохр-я ЦЧ. Если среди ( ) есть отрицательные и - столбец матрицы ( ) и , , то .

Это значит, что если строчка выбирается в качестве напр-щей, то напр-щий элемент равен (-1).

Алгоритм опред-ния опт. плана. Начинают с недопустимой таблицы . Затем построив правильное ЦЧ отсечение, удовл-щее условиям 1-4, переходят к таблице , затем к , и т.д. пока не получат допустимую таблицу. Как и прежде исп-ся итерации -метода, ограничения, полученные из сформулир-го отсечения припис-ся снизу к соотв. таблице. Вся посл-ть таблиц, явл-ся ЦЧ и -нормальной.

30.Построение начальной l-нормальной целочисленной симплексной таблицы.

Для Гомори-3 исходная таблица д.б. ЦЧ и -норм-ой. Пусть имеем таблицу для задачи ЦЧ-го ЛП:

Е сли -нормальна, то можно переходить к итерациям алгоритма. Если нет, то можно воспользоваться следующим приёмом для получения -нормальной целочисленной симплексной таблицы.

При условии (*) находят . Очевидно, что для всех шагов задачи (1) выполняется .

Следовательно, можно ввести новую переменную , , – целое.

Строку припис. снизу к таблице и берём в качестве напр. Напр. столбец , .

– столбец таблицы , соответствующий небазисной переменной.

Проделываем итерацию -метода, вычёркиваем строку и получаем полностью ЦЧ и -нормальную таблицу . В дальнейшем, если вводится в базис, то соотв. строка не восстанавливается.