Симметрии многогранника системы независимости (стр. 2 из 2)

Доказательство. Так как {ej}

для любого j{1n}, то ,по определению H-отображения, вектор (x{ej}), являющийся j-м столбцом матрицы отображения, булев, что и требовалось доказать.

3. Понижение размерности задачи на системе независимости

Рассмотрим оптимизационную задачу (1) и перейдем к полиэдральной постановки этой задачи

(2)

где v - это вектор, компоненты которого - веса соответствующих элементов. Очевидно, что решение задачи (2), при условии "поиска по вершинам", будет являться вектором инциденций решения задачи (1). Кроме того, если существует симметрия многогранника P с матрицей A и сдвигом h, и x* решение задачи

(3)

то вектор x = Ax*+h - решение задачи (2).

Предложение 2. Пусть (x) = Ax+xH - симметрия многогранника P и v - произвольный вектор с положительными компонентами. Тогда вектор vTA имеет по крайней мере H неположительных компонент.

Доказательство. По лемме 2, симметрия  представима в виде суперпозиции отображений 1, описанного в лемме 2, и H-отображения 2. Матрица A является произведением матриц преобразований 1 и 2. Так как H

H{ H | J }, то существует такое множество I , что 2 (xI) = xH. Причем, так как любое подмножество H принадлежит H, то в силу линейности 2, IH. Следовательно, матрица преобразования 2 принимает вид

Здесь I и H - столбцы и строки, соответствующие элементам из этих множеств, а блок B - некоторая булевa матрица. При умножении матрицы преобразования 2 на матрицу преобразования 1 блок B заменяется на блок (-B). Затем, при умножении вектора vT на матрицу A, получается вектор, у которого компоненты, соответствующие элементам множества I, неположительные. Очевидно, что элементы, имеющие неположительные веса, не принадлежат оптимальному множеству задачи (3). Следовательно, исключая из рассмотрения эти элементы, переходим к задаче

(4)

где v* = vTA, D-совокупность элементов, у которых соответствующие компоненты вектора v* неположительные. Вектор инциденций решения этой задачи есть оптимальный вектор задачи (3). Причем, по предыдущему предложению, размерность задачи (4) не больше, чем E-H.

Пример 1. Пусть E = {1,2,3,4},

- система независимости, базисы которого являются множества {1,2,3} и {3,4}. Пусть H={1,3}. Тогда матрица H-отображения принимает вид

a симметрия многогранника системы независимости

-

Пусть вектор весов v = (3,1,4,2), тогда вектор новых весов будет равен

и после отбрасывания элементов c отрицательными весами получаем множество {2} , состоящее из одного элемента, которое и будет оптимальным для задачи с новыми весами. Следовательно вектор инциденций решения исходной задачи будет

То есть оптимальное множество исходной задачи есть множество {1,2,3}.

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

Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация.- М.:Наука, 1981.

Симанчев Р.Ю. Линейные симметрии многогранника паросочетаний и автоморфизмы графа // Вестник Омского университета, 1996. N.1. C.18-20.

Червяков О.В. Линейные симметрии и автоморфизмы матроида // Фундаментальная и прикладная математика. ОмГУ, 1994, с. 81- 89.

Conforti M., Laurent M. On the facial structure of independence system polyhedra // Math. of operations research. 1988. V.13. N. 4. P. 543 - 555.