Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Комбинаторные условия фасетности опорных неравенств
Раздел: Рефераты по математике
Тип: статья Добавлен 17:00:04 03 марта 2007 Похожие работы
Просмотров: 47 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

Пусть 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, то из аналогичных выкладок получаем

eS\H2 be - eS\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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:52:54 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:52:52 24 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150578)
Комментарии (1836)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru