Claw.ru | Рефераты по математике | Комбинаторные условия фасетности опорных неравенств Комбинаторные условия фасетности опорных неравенств | Категория реферата: Рефераты по математике | Теги реферата: скачать диплом, ответ 2 | Добавил(а) на сайт: Dresvjanin. Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

(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(xSH2 - xSH1) = cTxSH2 - cTxSH1 =eSH2 be - eSH1 be

(3)

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

eSH2 be - eSH1 be= 0

(4)

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

eSH2 (e) - eSH1 (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.

Рекомендуем скачать другие рефераты по теме: доклад на тему, биология 8 класс гдз.





Предыдущая страница реферата | 1  2  3 | Следующая страница реферата