Страницу Назад
Поискать другие аналоги этой работы

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

ID: 103220
Дата закачки: 12 Августа 2013
Продавец: Lokard (Напишите, если есть вопросы)
Посмотреть другие работы этого продавца

Тип работы: Работа
Форматы файлов: Microsoft Word

Описание:
Пусть 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 не имеет целочисленных точек, отличных от вершин.

Размер файла: 7,6 Кбайт
Фаил: