Статья

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

Работа добавлена на сайт bukvasha.net: 2015-10-29

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 23.11.2024



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

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

Пусть 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) неравенство. Нам понадобятся следующие определения.

Непустое множество SE будем называть cH-множеством, если существуют такие H1,H2H, что 1) S=(H1\H2)(H2\H1)   и  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S\H2 aeu = eS\H1 aeu, где H1,H2H - из определения cH-множества.

Доказательство. Пусть aTx=u - соответствующее уравнение из системы, определяющей аффинную оболочку многогранника P(H). Ясно, что оно справедливо и для векторов xH1 и xH2. Заметим также, что S\H2 = H1\H2 и S\H1=H2\H1. Теперь 0 = aTxH1-aTxH2 = aT(xH1-xH2) = aT(xH1\H2 - xH2\H1) = aTxS\H2 - aTxS\H1 =eS\H2 aeu = eS\H1 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)

 Покажем, что тогда система линейных уравнений

c + A = b

(2)

относительно неизвестных mR и lRn совместна, причем   0. Очевидно, что в этом случае будет также иметь место равенство b0 = c0 +T. Как известно, из совместности системы (2) следует, что грань F, индуцированная неравенством cTx c0, является фасетой многогранника P(H) (см. [1])

Всякое уравнение системы (2) соответствует единственному eE. Обозначим ее уравнения через (e), eE, имея ввиду и правые, и левые их части, то есть (e): ce+uV  aeuu = be.

Пусть SE - cH-множество и H1,H2H - множества, указанные в соответствующем определении. По определению cTxH1 = cTxH2 = c0. Следовательно,

0 = cTxH1 - cTxH2 = cT(xH1 - xH2) =  cT(xS\H2 - xS\H1) = cTxS\H2 - cTxS\H1 =eS\H2 be - eS\H1 be

(3)

Так как, в силу (1), bTxH1 = bTxH2 = b0, то из аналогичных выкладок получаем

eS\H2 be - eS\H1 be= 0

(4)

Заметим, что в предыдущей лемме фигурирует такая же, как в (3) и (4), комбинация элементов в остальных столбцах системы (2). Таким образом, сумма строк S\H2 минус сумма строк S\H1 в матрице (cAb) дает нулевую строку. Значит, уравнения (e), eS связаны следующим линейным соотношением:

eS\H2 (e) - eS\H1 (e) = 0

(5)

что означает их линейную зависимость. Поэтому, если SE является cH-множеством, то любое одно уравнение из семейства {(e), eS} может быть отброшено из системы (2) без ущерба для ее совместности.

Теперь, используя индукцию и основываясь на (5), покажем, что подсистема

D(c,E~)-=b~

(6)

где b~ = (be : eE~), - = (,T)TRn+1, эквивалентна системе (2). Иными словами, покажем, что всякое уравнение (e) при eE \ E~ может быть отброшено из системы (2). Индукцию проведем по числу элементов в упорядоченном множестве {e1, e2, ,et} , необходимом для того, чтобы элемент etE \ E~ являлся cH-следствием множества E~, то есть по числу t. Если t=1, то, как показано, из (5) следует, что (e) может быть отброшено из системы (2). Пусть EE \ E~ - множество таких cH-следствий множества E~, для которых существует упорядоченное множество длины не более чем t, и пусть уравнения (e) при eE могут быть отброшены из системы (2). Возьмем e*E \ (E~E), для которого длина соответствующего упорядоченного множества равна t+1. По условию теоремы, существует такое cH-множество S, содержащее e*, что S \{e*}  E~E. Тогда, в силу (5), (e*) является линейной комбинацией уравнений (e), eS \ {e} , каждое из которых, по индукционному предположению, является линейной комбинацией уравнений (e), eE~.

Таким образом, действительно, системы (6) и (2) эквивалентны.

По условию теоремы, rank D(c,E~) = E~ = n+1. Следовательно, ранг расширенной матрицы системы (6) равен рангу основной. Значит, система (6), а вместе с ней и система (2), совместны. При этом решение системы (2) нетривиально, ибо в противном случае b = o.

Остается показать, что   0. Так как cTx  c0 опорно к P(H), то существуют такие x1,x2H, что cTx1 = c0 и cTx2c0. Тогда, в силу (1), bTx1 = b0 и bTx2  b0. Отсюда

0  bT(x1-x2) = (cT +TAT)(x1-x2) =  (cTx1-cTx2) + T - T

Так как cTx1cTx2, то   0. Отметим, что в общем случае приводимая здесь техника является достаточно громоздкой. Однако конкретизация семейства H, аффинной оболочки соответствующего многогранника и самого опорного неравенства позволяет получать конструктивные результаты. Так, например, в [2] посредством данной техники описаны три класса ранговых неравенств, индуцирующих фасеты многогранника связных k-факторов полного графа.

Список литературы

Схрейвер А. Теория линейного и целочисленного программирования: В 2 т. М.: Мир, 1991.

Симанчев Р.Ю. О ранговых неравенствах, порождающих фасеты многогранника связных k-факторов // Дискретный анализ и исследование операций. 1996. Т.3. N 3. С.84-110.

Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Mathematical Programming.  1991. N 51. P. 141-202.

Для подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/



1. Доклад на тему Замки Кипра
2. Реферат Проект по восстановлению воздушной линии связи на железнодорожном участке
3. Реферат на тему Ufos Essay Research Paper Is there life
4. Курсовая Влияние международных стандартов финансовой отчетности на учетный процесс современного предприят
5. Реферат Итальянская война 1536 1538
6. Курсовая на тему Конституционный суд РФ 4
7. Реферат на тему MacKinnon Essay Research Paper Rousseau and Marx
8. Реферат Нагідки лікарські - Calendula Officinalis L
9. Реферат Оустерхаут, Джон
10. Реферат на тему Rudolph Diesel Essay Research Paper Rudolph Christian