Описание метода Гомори

Рассмотрим задачу целочисленного ЛП в канонической форме:

(1)

(2)

(3)

(4)

Заметим, что описываемый метод может быть применен и для решения задачи частично целочисленного программирования.

Как уже отмечалось, в основе метода Гомори лежит понятие правильного отсечения.

Определение. Дополнительное линейное ограничение, добавляемое к ограничениям задачи (1)-(4), называется правильным отсечением, если оно:

1) отсекает решение задачи ЛП (1)-(3) (в которой исключены условия целочисленности);

2) не отсекает ни одного целочисленного допустимого плана задачи (1)-(4), то есть всякий целочисленный план задачи (1)-(4) удовлетворяет дополнительному ограничению.

Предположим, что получен оптимальный план задачи ЛП (1)-(3) с помощью симплекс-метода, и этот план имеет вид

(5)

Если все компоненты х * целочисленные, то х * будет оптимальным планом задачи целочисленного ЛП (1)-(4), и задача решена.

Если не все компоненты х * целочисленные, то выразим базисные переменные х ₁, х ₂, …, х_m через свободные:

........................... (6)

Так как не все компоненты х * целочисленные, то среди чисел есть хотя бы одно нецелое число. Пусть это будет . Обозначим целую часть этого числа Например, [3,14] = 3; [-2,71] = -3. Дробная часть числа будет равна Например, {3,14} = 0,14; {-2,71} = 0,29.

Приведем некоторые необходимые ниже свойства дробной части.

1) Дробная часть суммы двух чисел не превышает суммы дробных частей: { a + b } ≤ { a }+{ b }. Действительно, { a + b } = {[ a ]+{ a }+[ b ]+{ b }} = {{ a }+{ b }}. Если { a }+{ b } < 1, то { a + b } = { a }+{ b }. Если же { a }+{ b } ≥ 1, то { a + b } = { a }+{ b } - 1. Это свойство легко обобщается на случай произвольного конечного числа слагаемых.

2) Дробная часть произведения неотрицательного целого числа l и действительного числа а не превышает произведения l на дробную часть числа а: { la } ≤ l { a }. Это свойство является следствием первого.

Теорема. Неравенство

(7)

Определяет правильное отсечение.

Доказательство. Покажем, что выполнены условия 1), 2) из определения правильного отсечения.

1) Методом от противного покажем, что неравенство (7) отсекает нецелочисленное решение х * задачи ЛП (1)-(3). Предположим противное, а именно что х * не отсекается неравенством (7), то есть

удовлетворяет условию (7):

Последнее неравенство противоречит тому, что нецелое число (имеет ненулевую дробную часть).

2) Теперь покажем, что всякий допустимый целочисленный план задачи ЦЛП (1)-(4) удовлетворяет неравенству (7), то есть не отсекается этим неравенством. Пусть - допустимый целочисленный план задачи (1)-(4), то есть он удовлетворяет следующему равенству, получаемому из (6):

Используя свойства дробной части числа, получаем:

Так как здесь то после переноса слагаемых из правой части неравенства в левую часть получаем (7).

Таким образом, неравенство (7) является правильным отсечением.

Дата добавления: 2014-01-06