Комбинаторные условия фасетности опорных неравенств Р.Ю. Симанчев, Омский государственный университет, кафедра математического моделирования
    Пусть E- конечное множество, H- некоторое семейство его подмножеств. Мы будем рассматривать комбинаторно полные семейства, то есть семейства H, удовлетворяющие следующим аксиомам:
    1) для любого e?E найдутся такие H1?H и H2?H, что e?H1\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) неравенство. ............