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

Реализация на ЭВМ 1-го и 2-го алгоритмов Гомори может привести к неправильному результату из-за ошибок округления или ошибок при подсчёте дробных частей.

Третий алгоритм Гомори свободен от влияния ошибок округления. Он предназначен для решения полностью целочисленной задачи линейного программирования.

;

;

; целые.

Схема 3-го алгоритма Гомори аналогична схемам, рассмотренным ранее. Отправляясь от начальной L-нормальной таблицы T₀, с помощью итераций L-метода получают последовательность таблиц T₀,T₁,…, T_s, последняя из которых является допустимой. Третий алгоритм называют ещё полностью целочисленным. Начальная таблица T₀ строится полностью целочисленная, а затем отыскивается целочисленное правильное отсечение. Дробные числа в следующей таблице получаются из-за присутствия в формулах преобразования операции деления. В этом случае целочисленность новой таблицы может быть гарантирована лишь в том случае, если разрешающий элемент будет равен (-1). Это и делается в 3-ем алгоритме Гомори при построении отсечения. Его строят так, чтобы разрешающий элемент был (-1).

Формулировка целочисленного правильного отсечения звучит следующим образом.

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

1. Условие целочисленности: r_j -целое, "jÎN⁰.

2. Условие отсечения: z(`x)=r₀<0.

3. Условие правильности. Для любого плана `x задачи (L<sup>j</sup>,C) выполняется неравенство z(`x)³0.

4. Условие сохранения целочисленности. Если среди чисел r_j (jÎN) есть отрицательные и - столбец матрицы T_j (jÎN) и , то r_l = -1.

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

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

Построение целочисленного правильного отсечения для 3-го алгоритма Гомори.

Главное для 3-го алгоритма являетя построение отсечения, гарантирующего целочисленность следующей симплексной таблицы. Необходимо подчеркнуть, что 3-ий алгоритм применяется к таблице T₀(исходной), если она L-нормальна и целочисленна, т.е. все её коэффициенты целые. Следовательно, предварительно необходимо получить такую таблицу. КАК?

Целочисленное правильное отсечение строится на основании следующей теоремы.

Теорема: пусть l>0, , где M – конечное множество.

(*), где [ ] обозначают целую часть числа;

, - целое, .

Тогда z³0; z – целое.

Доказательство: целочисленность z получается прямо из выражения для него(*), где справа только целые величины и нет операций деления.{y_j-целые, а [ ]… }. Необходимо показать неотрицательность. Допустим, что z<0, тогда из целочисленности z следует, что z£ -1. С другой стороны,

, а это можно представить в виде:

, где { } – дробная часть.

Из этого и из того, что z£ -1, получаем: , а это невозможно, т.к. - всегда неотрицательна.

Теорема доказана.

Используя теорему, можно построить целочисленное правильное отсечение, удовлетворяющее условиям 1-4.

Пусть задана целочисленная, недопустимая и L-нормальная таблица.

и пусть для некоторого k (1£k£n) x_k0<0.

Положим M=N,

, так что и получим целочисленное правильное отсечение: , z ³ 0, z-целое.

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

Мы говорили уже, что исходная таблица должна быть целочисленной и L-нормальной. Допустим, что построили таблицу T₀^¢ для задачи целочисленного ЛП:

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

При условии (**) ищут и находят .

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

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

Строку x_n+1 приписываем снизу к таблице T₀^¢ и берём в качестве направляющей. Направляющим столбцом выбираем . - столбец таблицы T₀^¢, соответствующий небазисной переменной.

Проделывается одна итерация L-метода, вычёркиваем строку x_n+1 и получаем полностью целочисленную и L-нормальную таблицу T₀^¢. В дальнейшем, если переменная x_n+1 вводится в базис, то соответствующая строка не восстанавливается.

Алгоритм.

0-ая итерация. Строится исходная таблица T₀: целочисленная и l-нормальная. Если T₀ является допустимой, то расширенный l-псевдоплан является расширенным оптимальным планом задачи (L^j,C). Если T₀ не является допустимой, то переходим к 1-ой итерации.

p-я итерация. (p³1). Задана целочисленная и L-нормальная, но недопустимая таблица . Столбцы обозначаем . Находим первую по номеру компоненту , нарушающую допустимость таблицы ,

(1)

Если числа , то задача (L^j,C) неразрешима.

Построение целочисленного отсечения в третьем алгоритме Гомори

Если же среди чисел есть отрицательные, то выбираем ведущий столбец :

(2)

и строим целочисленное правильное отсечение:

; x_n+p ³0, x_n+p – целое. (3)

Строка x_n+p приписывается снизу к таблице, принимается за направляющую и проделывается одна итерация L-метода.

Переменная x_n+p – выводится из базиса, а x_l – вводится. Стока x_n+p вычёркивается. Если l³n+1, то строку x_l не восстанавливаем. Получаем новую таблицу:

целочисленную и l-нормальную.

. Если таблица T_p окажется допустимой, то вектор является расширенным оптимальным планом задачи (L^j,C). Если T_p – недопустима, то переходим к (p+1) итерации.