Комбинаторные условия фасетности опорных неравенств
Комбинаторные условия фасетности опорных неравенств
Р.Ю. Симанчев, Омский государственный университет,
кафедра математического моделирования
Пусть
E- конечное множество, H- некоторое семейство его подмножеств. Мы будем
рассматривать комбинаторно полные семейства, то есть семейства H,
удовлетворяющие следующим аксиомам:
1)
для любого eE найдутся такие H1H и H2H, что eH1H2;
2)
для любых e1, e2E найдется такой HH, что e1H и e2H.
Сопоставим
множеству E E-мерное евклидово пространство RE посредством
взаимнооднозначного соответствия между E и множеством координатных осей
пространства RE. Иными словами, RE можно мыслить как пространство
вектор-столбцов, координаты которых индексированы элементами множества E. Для
каждого R E определим его вектор инциденций xRRE как
вектор с компонентами xeR = 1 при eR, xeR=0 при eR. Таким
образом, множеству всех подмножеств множества E ставится во взаимнооднозначное
соответствие множество всех вершин единичного куба в RE. На основании этого
соответствия в дальнейшем там, где это не вызовет недоразумений, (0,1)-вектор xRE
будем одновременно понимать как подмножество множества E.
Нас
будет интересовать следующий многогранник, ассоциированный с семейством H,
PH
= conv{ xH RE | H H }.
Перечислим
некоторые очевидные свойства многогранника PH.
1)
Каждая вершина многогранника PH является (0,1)-вектором. 2) Вершины и только
они соответствуют множествам семейства H. 3) Многогранник PH не имеет
целочисленных точек, отличных от вершин.
Пусть
aRE, a0R. Линейное неравенство aTxa0 называется опорным
к многограннику P(H), если aTxa0 для любого xP(H). Всякое
опорное неравенство порождает грань многогранника (возможно несобственную).
Максимальные по включению грани называются фасетами, а порождающие их опорные
неравенства, соответственно, - фасетными. Принципиальная роль фасетных
неравенств обуславливается, во-первых, тем, что они присутствуют в любой
линейной системе, описывающей многогранник, во-вторых, эффективность их
использования в качестве отсечений при решении соответствующих экстремальных
комбинаторных задач (см., например, [3]).
В
настоящей работе получены достаточные условия фасетности опорного неравенства,
имеющие комбинаторную природу.
Через
aff P(H) обозначим аффинную оболочку многогранника P(H). Как известно,
существуют такие матрица A и вектор-столбец , что
aff
P(H)={xRE | ATx = }.
Далее
везде, не ограничивая общности, будем полагать, что матрица A в линейном
описании аффинной оболочки имеет полный ранг.
Каждая
строка матрицы A соответствует ровно одному элементу eE и наоборот.
Поэтому множество строк матрицы A будем обозначать через E. Множество столбцов
обозначим буквой V. Ясно, что rankA=VE.
Положим V=n. Согласно введенным обозначениям, для коэффициента
матрицы A, находящегося в строке eE и столбце uV, будем
использовать запись aeu. Обозначим через Ve множество столбцов матрицы A,
имеющих в строке e ненулевой элемент. Для S E положим VS =eSVe.
Если cRE, то через (cA) (соответственно, (Ac))
обозначим матрицу, полученную приписыванием к матрице A слева (соответственно,
справа) столбца c, а через D(c,E) подматрицу матрицы (cA), образованную
строками E~E.
Пусть
cTx c0 - опорное к P(H) неравенство. Нам понадобятся следующие
определения.
Непустое
множество SE будем называть cH-множеством, если существуют такие H1,H2H,
что 1) S=(H1H2)(H2H1) и 2)
cTxH1 = cTxH2 = c0;
Будем
говорить, что элемент e0E является cH-следствием некоторого множества
E~E, если существует такое упорядоченное множество e1, e2, ... ,et =
e0, что для любого i{1,2,,t} элемент ei принадлежит некоторому
cH-множеству, лежащему в E~{e1,e2,,ei} .
Лемма.
Пусть affP(H)={xRE|ATx=}RE и SE - cH-множество.
Тогда для каждого uVS имеет место соотношение eSH2 aeu
= eSH1 aeu, где H1,H2H - из определения cH-множества.
Доказательство.
Пусть aTx=u - соответствующее уравнение из системы, определяющей
аффинную оболочку многогранника P(H). Ясно, что оно справедливо и для векторов
xH1 и xH2. Заметим также, что SH2 = H1H2 и SH1=H2H1. Теперь 0 = aTxH1-aTxH2
= aT(xH1-xH2) = aT(xH1H2 - xH2H1) = aTxSH2 - aTxSH1 =eSH2 aeu
= eSH1 aeu. Теорема. Пусть cTx c0 - опорное к
P(H) неравенство, F={xP(H) | cTx = c0}. Для того, чтобы грань F
являлась фасетой многогранника P(H), достаточно существования такого E~E,
что 1) E~=n+1; 2) всякое eE E~ является cH-следствием
множества E~; 3) матрица D(c,E~) имеет полный ранг.
Доказательство.
Пусть bTx b0 - опорное к P(H) неравенство, удовлетворяющее
условию
{xP(H) | cTx = c0} {xP(H) | bTx = b0} .
Похожие работы на - Комбинаторные условия фасетности опорных неравенств
|