Николаев А.В.

Ярославский государственный университет им. П.Г. Демидова, Россия

Об общих границах некоторых релаксаций корневого полуметрического многогранника.

Одним из перспективных направлений исследования задач дискретной оптимизации, т.е. выбора оптимального элемента из конечного набора, а также вопросов сложности задач, является изучение ассоциированных с задачами выпуклых множеств – многогранников [1,2,3]. В данной статье рассматривается многогранник , известный как «корневой полуметрический» или «многогранник задачи 2-выполнимость» [2,3], задаваемый системой вида:

(1)

(2)

(3)

(4)

(5)

(6)

где независимо пробегают значения .

В данной работе анализируются релаксации особого вида . Для этого рассмотрим многогранник и построим выпуклую оболочку множества его целых вершин – . Пусть - число неравенств, задающих . Выберем произвольным образом k-мерное подмножество множества и найдем соответствующие ему координаты . Получим грань из и наложим на нее ограничения, задающие . Повторив эту операцию для всех k-выборок из , получим новый многогранник , определяемый системой (1)-(6) и дополнительными ограничениями общим числом .

Нетрудно заметить, что многогранники и не имеет нецелочисленных вершин и совпадают с и соответственно, а значит и релаксации и будут совпадать с самим многогранником . Соответственно – это первая отличная от релаксация.

Введем новые обозначения для координат:

Утверждение 1. Многогранник задан системой (1)-(6) и дополнительными ограничениями вида:

, (7)

для каждой тройки , где , и всех векторов .

Доказательство. Рассмотрим многогранник , удовлетворяющий системе (1)-(7). Достаточно проверить тот факт, что не имеет нецелочисленных вершин и равен . Отсюда напрямую следует, что [4].

Преобразовав (7) с учетом системы (1)-(6) получим, что :

Теперь обратимся к следующей релаксации – многограннику .

Утверждение 2. Многогранник задан системой (1)-(7) и дополнительными ограничениями вида:

, (8)

для каждой четверки , где , и для всех векторов .

Доказательство. Аналогично утверждению 1 [4].

Известно [3], что многогранники и не имеют общих нецелочисленных вершин, при этом все целые вершины (по построению) у них общие. Соответственно, большой интерес представляет вопрос об общих нецелочисленных вершинах и . Он остается открытым, однако можно доказать интересное утверждение о точках, в некотором роде близких к вершинам.

Напомним, что по определению, вершина – это точка, не являющаяся внутренней ни для одного из отрезков многогранника. Таким образом, если – вершина и , где , то одна из точек и точно не принадлежит многограннику . Отметим, что без ограничения общности, можно в дальнейшем положить .

Рассмотрим границу особого вида:

Нетрудно заметить, что .

Утверждение 3. что .

Доказательство. Построим точку следующего вида:

Нетрудно проверить, что для точки выполнены неравенства (1)-(8), значит она принадлежит , а следовательно и .

Кроме того, для любых :

Покажем, что . Построим точки и , так, чтобы для некоторых и :

Предположим, что , тогда для любого :

Тогда,

Аналогично можно показать, что:

Противоречие, точка . Получим, что и .

Литература:

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

2. Деза М.М., Лоран М. Геометрия разрезов и метрик / Пер. с англ. Е. Пантелеевой и П. Сергеева. / Под ред. В. Гришухина. М.: МЦНМО, 2001.

3. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.

4. PORTA: POlyhedron Representation Transformation Algorithm 1.4.0. Thomas Christof, Andreas Loebel. The Konrad-Zuse-Zentrum fur Informationstechnik Berlin, http://www.zib.de/Optimization/Software/Porta/