36)Метод Гомори(метод отсеч-я)

Будем рассматривать следующую задачу целочис.програм-я

Max(min) F=∑ ⁿ_j=1c_ijx_ij (1)

∑ ⁿ_j=1c_ijx_ij =b_i ,i=1,m (2)

x_j≥0, j=1,n (3)

x_j- целый, j=1,n (4)

Алгоритм метода:

1.Решается задача (1)-(3),с отброшенным усл-м целочис-ти(4).

2.Если усл.целочисленности вып-ся по всем переменным,то оптимальн.решение з-чи(1)-(4) совпад-т с оптимальн.решением з-чи(1)-(3).Если же это усл.не выпол-ся хотя бы поодной перемен-й ,то переходим к шагу 3.Если з-ча(1)-(3)не разрешима,то и исходная з-ча не имеет реш-я.

3.Строится доп-ое ограничение,кот.отсекает часть ОДР,в кот.содерж-ся оптим-е решение з-чи (1)-(3) и не содер-ся ни одного допуст-го реш-я задачи(1)-(4)

4.Возвращ-ся к з-че с отброш-м условием целочисл-ти,но с расшир-й сис-мой осн-х ограничений.Добавляются огранич-я,построен-е на 3-ем шаге и вновь примен-ся симплексная процедура и т.д.

. Отличие выбора разрешающего элемента:

Сначала рассм-ся строка,в кот содерж-ся отриц-е число в столбце свободн.членов и рассмат-ем все неотриц-е числа в этой строке.Выбираем люб.отрицат.число,кот и будет определять разрешающ.столбец.Для чисел с один-ми знаками в столбце свободн.членов и разреш-м столбце наход-ся симплекс-е отношения.Наименьш.симплексн.отношение и определяет разреш-щую строку

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

Основное в алгоритме- построение дополнит-го огранич-я,кот.назыв-ся правильным отсеч-ем и удовл.св-вам:

Max(min) F=∑ ⁿ_j=1c_ijx_ij (1)

∑ ⁿ_j=1c_ijx_ij =b_i ,i=1,m (2)

x_j≥0, j=1,n (3)

x_j- целый, j=1,n (4)

1.Явл-ся линейным

2.Отсекает найденное оптимальное нецелочисл-е реш-е з-чи (1)-(3)

3.Не отсекает ни одного из целочис-х реш-ий з-чи (1)-(4)

После каждой интеграции реш-е з-чи симп-м методом сис-ма огранич-ий имеет вид:

x_i =b_i-∑_xj€спλ_ij x_j =b_i ,x_i€БП(1)

Если вып-ся критерий оптим-ти,то запис-ся оптим-ое решение.Если все координаты этого оптимальн.знач-я целочисленны,то з-ча решена.

Пусть нек-е b_i не цел.Предположим,что для индекса i₀ ,b_i0 не целое число.

Рассмотрим i₀ –равенство(1):

x_i0= b_i0-∑_xj€спλ_i0jx_j (2)

a=[a]_{цел.часть}+{a}_{дроб.ч-ть},где 0<{a}< 1

3,7=3+0,7

-4,1=-5 +0,9

Представим b_i0 и λ_i0j в виде суммы дробной и целой части:

b_i0=[ b_i0]+{ b_i0}

λ_i0j =[ λ_i0j]+{ λ_i0j } (3)

Подставим (3) в (2),получим:x_i0= ([b_i0]-∑_xj€сп[λ_i0j]xj )+ ([b_i0]-∑_xj€сп{λ_i0j}xj ) (4)

Понятно,что 1-ая скобка-всегда целое число.Для того,чтобы x_i0-было целым числом надо,чтобы величина L_i0={ b_i0}-∑_xj€сп{λ_i0j} xj _,тоже была целым числом.Покажем,что L_i0≤0.Предположим,что L_i0>0.По условию величина ∑_xj€сп{λi0j} xj не может быть отрицательной.Т.к.дробные части 0<{λ_i0j}<1.По предложению следует,что дробная часть {b_i0}>1,а это противоречит определению дроб-ой части числа.След-но L_i0≤0Таким образом дополнит-ое ограничение,кот.строится в пункте 3 алгоритма должно иметь вид: ([b_i0]-∑_xj€сп{λ_i0j}xj≤0 (5).

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

38.Теорема о правильном отсечени

Рассмотрим i₀ –равенство(1):

x_i0= b_i0-∑_xj€спλ_i0jx_j (2);

b_i0=[ b_i0]+{ b_i0}

λ_i0j =[ λ_i0j]+{ λ_i0j } (3);

x_i0= ([b_i0]-∑_xj€сп[λ_i0j]xj )+ ([b_i0]-∑_xj€сп{λ_i0j}xj ) (4);

([b_i0]-∑_xj€сп{λ_i0j}xj≤0 (5);

Суть теоремы:Неравенство (5)опред-т правильное отсечение Гомори,т.е.:

Max(min) F=∑ ⁿ_j=1c_ijx_ij (1)

∑ ⁿ_j=1c_ijx_ij =b_i ,i=1,m (2)

x_j≥0, j=1,n (3)

x_j- целый, j=1,n (4)

1.Явл-ся линейным

2.Отсекает найденное оптимальное нецелочисл-е знач-е з-чи (1)-(3)

3.Не отсекает ни одного из целочис-х реш-ий з-чи (1)-(4).

Доказ-во: 1.Линейность (5) очевидна,2.Пусть X^*_нц-оптим-й нецелоч-ый план з-чи (1)-(3).Причём координата X^*_i0 не целое число.Покажем,что это реш-ие не удовлетвор.условию (5).Т.к. X^*_нц-оптим-й план,то след-но x_j=0, x_j€ СП.Получим,что ∑_xj€сп{λ_i0j}xj=0.Имеем,что { b_i0}≤0,а это противоречит определению дроб-ой части числа.След-но X^*_нц не удовлет-т условию (5):3.Догажем от противного.Пусть X^*_ц-целочисленный план з-чи (1)-(4),кот не удовлетв-т неравенству(5).Это значит,что дробная часть{b_i0}-∑_xj€сп{λ_i0j}xj>0 (6).Т.к. 0<{ b_i0}<1,а ∑_xj€сп{λ_i0j}xj>0,то учитывая (6) получим: 0<{b_i0}-∑_xj€сп{λ_i0j}xj<1,а это противоречит тому,что L_i0 –целое число.

Признаком отсутсвия целочисл-го знч-я служит появление в симпекс.таблице хотя бы одной строки с дробным свободн-м членом и целыми остальными коэффициентами.