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

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

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

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

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


Пусть
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{ 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-множеством, если существуют такие 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|ATx=}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) | 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)


Скачиваний: 1
Просмотров: 0
Скачать реферат Заказать реферат