Учебная работа № 1407. Комбинаторные условия фасетности опорных неравенств

Учебная работа № 1407. Комбинаторные условия фасетности опорных неравенств

Р.Ю. Симанчев, Омский государственный университет, кафедра математического моделирования

Пусть E конечное множество, H некоторое семейство его подмножеств. Мы будем рассматривать комбинаторно полные семейства, то есть семейства H, удовлетворяющие следующим аксиомам:

1) для любого eE найдутся такие h2H и H2H, что eh2\H2;

2) для любых e1, e2E найдется такой HH, что e1H и e2H.

Сопоставим множеству E Eмерное евклидово пространство RE посредством взаимнооднозначного соответствия между E и множеством координатных осей пространства RE. Иными словами, RE можно мыслить как пространство векторстолбцов, координаты которых индексированы элементами множества E. Для каждого R E определим его вектор инциденций xRRE как вектор с компонентами xeR = 1 при eR, xeR=0 при eR. Таким образом, множеству всех подмножеств множества E ставится во взаимнооднозначное соответствие множество всех вершин единичного куба в RE. На основании этого соответствия в дальнейшем там, где это не вызовет недоразумений, (0,1)вектор xRE будем одновременно понимать как подмножество множества E.

Нас будет интересовать следующий многогранник, ассоциированный с семейством H,

PH = conv{ xH RE | H H }.

Перечислим некоторые очевидные свойства многогранника PH.

1) Каждая вершина многогранника PH является (0,1)вектором. 2) Вершины и только они соответствуют множествам семейства H. 3) Многогранник PH не имеет целочисленных точек, отличных от вершин.

Пусть aRE, a0R. Линейное неравенство aTxa0 называется опорным к многограннику P(H), если aTxa0 для любого xP(H). Всякое опорное неравенство порождает грань многогранника (возможно несобственную). Максимальные по включению грани называются фасетами, а порождающие их опорные неравенства, соответственно, фасетными. Принципиальная роль фасетных неравенств обуславливается, вопервых, тем, что они присутствуют в любой линейной системе, описывающей многогранник, вовторых, эффективность их использования в качестве отсечений при решении соответствующих экстремальных комбинаторных задач (см., например, [3]).

В настоящей работе получены достаточные условия фасетности опорного неравенства, имеющие комбинаторную природу.

Через aff P(H) обозначим аффинную оболочку многогранника P(H). Как известно, существуют такие матрица A и векторстолбец , что

aff P(H)={xRE | ATx =  }.

Далее везде, не ограничивая общности, будем полагать, что матрица A в линейном описании аффинной оболочки имеет полный ранг.

Каждая строка матрицы A соответствует ровно одному элементу eE и наоборот. Поэтому множество строк матрицы A будем обозначать через E. Множество столбцов обозначим буквой V. Ясно, что rankA=VE. Положим V=n. Согласно введенным обозначениям, для коэффициента матрицы A, находящегося в строке eE и столбце uV, будем использовать запись aeu. Обозначим через Ve множество столбцов матрицы A, имеющих в строке e ненулевой элемент. Для S E положим VS =eSVe. Если cRE, то через (cA) (соответственно, (Ac)) обозначим матрицу, полученную приписыванием к матрице A слева (соответственно, справа) столбца c, а через D(c,E) подматрицу матрицы (cA), образованную строками E~E.

Пусть cTx  c0 опорное к P(H) неравенство. Нам понадобятся следующие определения.

Непустое множество SE будем называть cHмножеством, если существуют такие h2,H2H, что 1) S=(h2\H2)(H2\h2) и 2) cTxh2 = cTxH2 = c0;

Будем говорить, что элемент e0E является cHследствием некоторого множества E~E, если существует такое упорядоченное множество e1, e2, … ,et = e0, что для любого i{1,2,,t} элемент ei принадлежит некоторому cHмножеству, лежащему в E~{e1,e2,,ei} .

Лемма. Пусть affP(H)={xRE|ATx=}RE и SE cHмножество. Тогда для каждого uVS имеет место соотношение eS\H2 aeu = eS\h2 aeu, где h2,H2H из определения cHмножества.

Доказательство. Пусть aTx=u соответствующее уравнение из системы, определяющей аффинную оболочку многогранника P(H). Ясно, что оно справедливо и для векторов xh2 и xH2. Заметим также, что S\H2 = h2\H2 и S\h2=H2\h2. Теперь 0 = aTxh2aTxH2 = aT(xh2xH2) = aT(xh2\H2 xH2\h2) = aTxS\H2 aTxS\h2 =eS\H2 aeu = eS\h2 aeu. Теорема. Пусть cTx c0 опорное к P(H) неравенство, F={xP(H) | cTx = c0}. Для того, чтобы грань F являлась фасетой многогранника P(H), достаточно существования такого E~E, что 1) E~=n+1; 2) всякое eE \ E~ является cHследствием множества E~; 3) матрица D(c,E~) имеет полный ранг.

Доказательство. Пусть bTx b0 опорное к P(H) неравенство, удовлетворяющее условию

{xP(H) | cTx = c0}  {xP(H) | bTx = b0} .

(1)

Покажем, что тогда система линейных уравнений

c + A = b

(2)

относительно неизвестных mR и lRn совместна, причем   0. Очевидно, что в этом случае будет также иметь место равенство b0 = c0 +T. Как известно, из совместности системы (2) следует, что грань F, индуцированная неравенством cTx c0, является фасетой многогранника P(H) (см. [1])

Всякое уравнение системы (2) соответствует единственному eE. Обозначим ее уравнения через (e), eE, имея ввиду и правые, и левые их части, то есть (e): ce+uV aeuu = be.

Пусть SE cHмножество и h2,H2H множества, указанные в соответствующем определении. По определению cTxh2 = cTxH2 = c0. Следовательно,

0 = cTxh2 cTxH2 = cT(xh2 xH2) = cT(xS\H2 xS\h2) = cTxS\H2 cTxS\h2 =eS\H2 be eS\h2 be

(3)

Так как, в силу (1), bTxh2 = bTxH2 = b0, то из аналогичных выкладок получаем

eS\H2 be eS\h2 be= 0

(4)

Заметим, что в предыдущей лемме фигурирует такая же, как в (3) и (4), комбинация элементов в остальных столбцах системы (2). Таким образом, сумма строк S\H2 минус сумма строк S\h2 в матрице (cAb) дает нулевую строку. Значит, уравнения (e), eS связаны следующим линейным соотношением:

eS\H2 (e) eS\h2 (e) = 0

(5)

что означает их линейную зависимость. Поэтому, если SE является cHмножеством, то любое одно уравнение из семейства {(e), eS} может быть отброшено из системы (2) без ущерба для ее совместности.

Теперь, используя индукцию и основываясь на (5), покажем, что подсистема

D(c,E~)=b~

(6)

где b~ = (be : eE~),  = (,T)TRn+1, эквивалентна системе (2). Иными словами, покажем, что всякое уравнение (e) при eE \ E~ может быть отброшено из системы (2). Индукцию проведем по числу элементов в упорядоченном множестве {e1, e2, ,et} , необходимом для того, чтобы элемент etE \ E~ являлся cHследствием множества E~, то есть по числу t. Если t=1, то, как показано, из (5) следует, что (e) может быть отброшено из системы (2). Пусть EE \ E~ множество таких cHследствий множества E~, для которых существует упорядоченное множество длины не более чем t, и пусть уравнения (e) при eE могут быть отброшены из системы (2). Возьмем e*E \ (E~E), для которого длина соответствующего упорядоченного множества равна t+1. По условию теоремы, существует такое cHмножество S, содержащее e*, что S \{e*}  E~E. Тогда, в силу (5), (e*) является линейной комбинацией уравнений (e), eS \ {e} , каждое из которых, по индукционному предположению, является линейной комбинацией уравнений (e), eE~.

Таким образом, действительно, системы (6) и (2) эквивалентны.

По условию теоремы, rank D(c,E~) = E~ = n+1. Следовательно, ранг расширенной матрицы системы (6) равен рангу основной. Значит, система (6), а вместе с ней и система (2), совместны. При этом решение системы (2) нетривиально, ибо в противном случае b = o.

Остается показать, что   0. Так как cTx  c0 опорно к P(H), то существуют такие x1,x2H, что cTx1 = c0 и cTx2c0. Тогда, в силу (1), bTx1 = b0 и bTx2  b0. Отсюда

0  bT(x1x2) = (cT +TAT)(x1x2) = (cTx1cTx2) + T T

Так как cTx1cTx2, то   0. Отметим, что в общем случае приводимая здесь техника является достаточно громоздкой. Однако конкретизация семейства H, аффинной оболочки соответствующего многогранника и самого опорного неравенства позволяет получать конструктивные результаты. Так, например, в [2] посредством данной техники описаны три класса ранговых неравенств, индуцирующих фасеты многогранника связных kфакторов полного графа.

Список литературы

Схрейвер А. Теория линейного и целочисленного программирования: В 2 т. М.: Мир, 1991.

Симанчев Р.Ю. О ранговых неравенствах, порождающих фасеты многогранника связных kфакторов // Дискретный анализ и исследование операций. 1996. Т.3. N 3. С.84110.

Grotschel M., Holland O. Solution of largescale symmetric travelling salesman problems // Mathematical Programming. 1991. N 51. P. 141202.

Учебная работа № 1407. Комбинаторные условия фасетности опорных неравенств