Навигация
Понижение размерности задачи на системе независимости
9265
знаков
4
таблицы
2
изображения
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, IH. Следовательно, матрица преобразования 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 -
Похожие работы
... , а затем и более фундаментального, одновременно и самого абстрактного (динамического) понимания симметрии. 2. 2.2.Симметрия кристаллов. Правильную, симметричную форму кристаллов издавна объясняли симметричным расположением атомов. Само существование атомов было еще гипотезой, но внешнее проявление стройного порядка заставляло предполагать внутреннюю причину. Быть может, правильные пирамиды, ...
... имеют достаточно четкое и правильное представление из собственного жизненного опыта, а формулировки которых являются слишком громоздкими. Выводы по § 1 1. Основные цели изучения темы «Объемы многогранников» в курсе стереометрии – развитие пространственных представлений учащихся, освоение способов вычисления практически важных величин и дальнейшее развитие логического мышления учащихся. ...
... . Реакции узлов более высокого уровня менее зависят от позиции и более устойчивы к искажениям. Структура Неокогнитрон имеет иерархическую структуру, ориентированную на моделирование зрительной системы человека. Он состоит из последовательности обрабатывающих слоев, организованных в иерархическую структуру (рис. 10.8). Входной образ подается на первый слой и передается через плоскости, ...
... , только если, например, нагреть кристалл так, чтобы он начал плавится. Порядок, закономерность, периодичность, симметрия расположения атомов - вот что характерно для кристаллов. Во всех кристаллах, во все твердых веществах частицы расположены правильным, четким строем, выстроены симметричным, правильным повторяющимся узором. Пока есть этот порядок существует твердое тело, кристалл. Нарушен ...
0 комментариев