Численные методы условной оптимизации. Первый (циклический) алгоритм Гомори.

Рассматривается алгоритм решения задачи целочисленного линейного программирования (ЦЛП). Приведем описание первого или циклического алгоритма отсечения Гомори. Он основывается на лексикографическом варианте двойственного симплекс-метода.

Шаг 0. Начать с нормальной симплекс-таблицы. Положить V = 0

Шаг 1. Если симплекс-таблица прямо допустима и все элементы Zp0, p =1..n, целые, то КОНЕЦ: получено оптимальное решение задачи ЦЛП.

Шаг 2. Если симплекс-таблица прямо допустима, то выбрать min p ϵ {1..n}, такое что Zp0 – нецелое, положить V = V+1. Строку с номером p назовем производящей. Этой строке соответствует уравнение:

Которое называется отсечением Гомори и используется для построения дополнительного ограничения, здесь l—число небазисных переменных

Где -- дробная часть числа К симплекс – таблице добавляется (n+1) строка (отсечение Гомори), соответствующая доп ограничению с базисной переменной

Шаг 3. Выбрать ведущую строку r такую, что

Шаг 4. Если , то выбрать ведущий столбец s по правилу

Иначе КОНЕЦ (текущая задача ЛП, а, следовательно, и исходная задача неразрешима ввиду несовместимости ее ограничений).

Шаг 5. Преобразовать симплекс- таблицу; положить и отбросить (n +1) строку, если таковая имелась, иначе перейти на шаг 1.

Не нашли, что искали? Воспользуйтесь поиском: