Комбинаторные условия фасетности опорных неравенств

Комбинаторные условия фасетности опорных неравенств

Комбинаторные условия фасетности опорных неравенств

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

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

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

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 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)= 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-множеством, если существуют такие H1,H2H, что 1) S=(H1H2)(H2H1)   и  2) cTxH1 = 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RE и SE - cH-множество. Тогда для каждого uVS имеет место соотношение eSH2 aeu = eSH1 aeu, где H1,H2H - из определения cH-множества.

Доказательство. Пусть aTx=u - соответствующее уравнение из системы, определяющей аффинную оболочку многогранника P(H). Ясно, что оно справедливо и для векторов xH1 и xH2. Заметим также, что SH2 = H1H2 и SH1=H2H1. Теперь 0 = aTxH1-aTxH2 = aT(xH1-xH2) = aT(xH1H2 - xH2H1) = aTxSH2 - aTxSH1 =eSH2 aeu = eSH1 aeu. Теорема. Пусть cTx c0 - опорное к P(H) неравенство, F=xP(H) . Для того, чтобы грань F являлась фасетой многогранника P(H), достаточно существования такого E~E, что 1) E~=n+1; 2) всякое eE E~ является cH-следствием множества E~; 3) матрица D(c,E~) имеет полный ранг.

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

cTx = c0  bTx = b0 . Наш опрос Как Вы оцениваете работу нашего сайта? Отлично Не помог Результаты опроса Реклама   Мнение авторов может не совпадать с мнением редакции сайта Перепечатка материалов без ссылки на наш сайт запрещена