Некоторые свойства многогранника. Задачи о P-медиане - статья

Г.Г. Забудский, Институт информационных технологий и прикладной арифметики СО РАН

1. Постановка задачки и определения

Задачки рационального размещения объектов имеют много практических приложений. Описываются разные постановки таких задач [1-8]. В данной статье рассматривается популярная NP-трудная задачка рационального размещения на графе - задачка о p-медиане [1,7-8]. Для ее исследования тут применяется подход, развиваемый в работах Некоторые свойства многогранника. Задачи о P-медиане - статья А.А. Колоколова и других [2,4-7,9] для анализа и решения задач целочисленного программирования, основанный на разбиении допустимой области соответственной непрерывной задачки. В данной работе рассматривается L- разбиение.

Задачка о p-медиане сводится к простейшей задачке размещения (ПЗР). Сводимость не гарантирует сохранения неких параметров. К примеру, полиэдр ПЗР - квазицелочисленный, а полиэдр Некоторые свойства многогранника. Задачи о P-медиане - статья задачки о p- медиане в общем случае является только связноцелочисленным (квазицелочисленным при p = 1, n-1, где n - число вершин графа) [1].

В работе [2] подтверждено, что полиэдр ПЗР имеет альтернирующую L-структуру. В данной статье показано, что полиэдр задачки о p-медиане также имеет альтернирующую L -структуру.

Рассматривается целочисленная модель задачки о Некоторые свойства многогранника. Задачи о P-медиане - статья p- медиане:

(1)

где n - количество вершин графа; dij - кратчайшее расстояние меж i-й и j- й верхушками графа; p- количество размещаемых объектов. Диагональными будем именовать элементы вектора x = (x11,x12,...,xnn) с схожими индексами, а медианными - диагональные, принимающие значение 1. Переменная xij = 1, если верхушка j"прикреплена" к верхушке i. Условия Некоторые свойства многогранника. Задачи о P-медиане - статья (4) гарантируют прикрепление только к медианным верхушкам. Если условия (5) поменять линейными неравенствами

(2)

то ограничения (2)-(4),(6) задают полиэдр в пространстве размерности n2. Обозначим его через Mp.

Введем определение L-разбиения . Пусть Zk- огромное количество всех k-мерных целочисленных векторов. Тогда L-разбиение непустого огромного количества Rk определим последующим образом:

1) любая Некоторые свойства многогранника. Задачи о P-медиане - статья точка zZk образует отдельный класс;

2) нецелочисленные точки x и y эквивалентны, если (x) = (y) и [xi=yi, i =1,...,(x)-1, [x(x)] = [x(x)] , где(x) - номер первой дробной, [a] - наибольшее целое число, не превосходящее a.

В выпуклых огромных количествах с альтернирующим L-разбиением дробныеи целочисленные классы чередуются Некоторые свойства многогранника. Задачи о P-медиане - статья. В работе [9] предложен аспект альтернируемости L-разбиения:выпуклое замкнутое огромное количество Rk имеет альтернирующее разбиение и тогда только тогда, когда для хоть какого дробного L-класса V есть целочисленные точки z1,z2    Zk ( именуемые окаймляющими) такие, что для хоть какого x  V z1j = z2j = xj, j =1,...,(x Некоторые свойства многогранника. Задачи о P-медиане - статья)-1; z2j = [xj]; j = (x); z1j = ]xj[; j = (x),

где ]a[ - верхняя целая часть числа a. Ясно, что символ словарного сопоставления.

2. Структура L-разбиения

Исследуем структуру L-разбиения полиэдра Mp.

Аксиома. Для случайного упорядочения переменных полиэдр Mp имеет альтернирующую L-структуру .

Подтверждение. Воспользуемся аспектом альтернируемости L-структуры. Возьмем случайный Некоторые свойства многогранника. Задачи о P-медиане - статья дробный xMp. Обозначим через  произвольную перестановку n2 индексов вектора x, т.е. пар чисел от 1 до n. Тогда (i,j) - номер пары (i,j) в перестановке  .Разглядим два варианта.

1. Пусть 1-ая дробная в векторе x  Mp - диагональная, т.е. (x) = (i,i) и Отметим, что qZ, qp, а тогда Некоторые свойства многогранника. Задачи о P-медиане - статья q+1 p. Построим вектор z1  Mp Zn2, и . Вероятны варианты.

1.1. q+1 = p. Для каждого j такового, что найдется kj таковой, что 0xkj1 построим огромное количество Jj =k. Покажем, что Jj.

Вправду, пусть нашелся j, для которого Jj=, тогда а потому что xkjxkk для всех k и j Некоторые свойства многогранника. Задачи о P-медиане - статья, имеем а из условия получаем 0 xij1 тогда и iJj, что противоречит тому, что Jj=.

Вектор z1 строим последующим образом:

Несложно проверить, что .

1.2 q+1p. Построим огромное количество JM = xkk = 1{i}.

Ясно, что |JM| p, потому что а 0xii1.

Если |JM| p, то, как рассмотрено выше, строим Некоторые свойства многогранника. Задачи о P-медиане - статья огромного количества Jj и вектор z1.

Если |JM| p тогда строим огромного количества: D = 0xkk1, VN = VM = . Выберем произвольно jD, тогда если найдется такое k, что 0xjk1 и xsk = 0 для всех sVN, то полагаем VM=VM{j}, по другому VN=VN{j}. Вычеркиваем j из D и избираем последующий Некоторые свойства многогранника. Задачи о P-медиане - статья элемент из D. Процедура построения множеств VN и VM завершается, когда D =. Отметим некие характеристики множеств VN и VM.

Во-1-х, | VM |  p-| JM |. Вправду, элемент j врубается в огромное количество VM в этом случае, если найдется таковой элемент k, что 0xjk1 и xsk = 0 для всех Некоторые свойства многогранника. Задачи о P-медиане - статья sVN. Потому что и xtkxtt, получаем, что ,откуда .

Беря во внимание, что имеем а тогда |VM| p - |JM|.

Во-2-х, |VN| (p- |JM|)-|VM|. Это следует из того, что |VN|+|VM| = |D|, а |D| = p - |JM| +1 .

В случае, если |VM| p- |JM|, избираем произвольно (p-|JM|)- |VM| частей Некоторые свойства многогранника. Задачи о P-медиане - статья из огромного количества VN и включаем их в огромное количество VM.

Дальше для каждого элемента j, такового, что 0xkj1 kj строим огромное количество Jj = k  JMVM

Покажем, что Jj для каждого рассматриваемого j. Вправду, если найдется j, для которого Jj=, тогда разглядим огромное количество Dj = k

Получаем Некоторые свойства многогранника. Задачи о P-медиане - статья, что 0xkk1 для всех kDj, откуда следует, что kVN для всех kDj, т.е. DjVN. Отметим, что элементы огромного количества Dj попеременно врубались в огромное количество VN, тогда перед рассмотрением последнего элемента rDj производилось условие 0xrj, xsj = 0 для всех sVN, но тогда Некоторые свойства многогранника. Задачи о P-медиане - статья rVM и, как следует, Jj. Другими словами, не может быть ситуации, когда все дробные в строке из огромного количества VN. Вектор z1 строится последующим образом:

Для того чтоб окончить рассмотрение варианта (x) = (i,i), нужно показать, как строится вектор z2Mp таковой, что . В данном случае аналогично строятся Некоторые свойства многогранника. Задачи о P-медиане - статья огромного количества JM,VN,VM,Jj, Dj с тем конфигурацией, что построение огромного количества VN начинается не с пустого огромного количества, а сначала в него врубается элемент {i}. В огромное количество Jj его не включаем. Потому что при подтверждении условия Jj мы не воспользовались тем, что iJM, оно справедливо Некоторые свойства многогранника. Задачи о P-медиане - статья и для рассматриваемого варианта. Вектор z2 строится аналогично, как расcмотрено выше, кроме того, что z2ii = 0.

2. Разглядим случай, когда (x) = (i,t), it. В отличие от рассматриваемого выше варианта при построении вектора z1 не нужно строить огромное количество Jt, а положить z1it = 1. Если 0 xii1, то i включаем Некоторые свойства многогранника. Задачи о P-медиане - статья в VM. При построении вектора z2 не включаем i в огромное количество Jt, если таковое будет строиться.

Аксиома подтверждена.

Отметим, что при построении векторов z1 и z2 мы только неким образом округляли дробные составляющие, не меняя значения целочисленных компонент.

СЛЕДСТВИЕ. Для хоть какого дробного решения задачки (1)-(5) подходящим округлением дробных компонент Некоторые свойства многогранника. Задачи о P-медиане - статья можно выстроить допустимое решение. При этом по последней мере одну из дробных компонент можно округлять произвольно.

Доказанное свойство альтернируемости может отлично употребляться при разработке алгоритмов решения задачки о p-медиане, к примеру, как в [7].

Перечень литературы

Емеличев В.А., Ковалев М.М., Кравцов М.К. Полиэдры, графы, оптимизация. М.: Наука Некоторые свойства многогранника. Задачи о P-медиане - статья,1981.-344 с.

Заблоцкая О.А. L-разбиение полиэдра задачки стандартизации // Моделирование и оптимизация систем сложной структуры. Омск: ОмГУ, 1987. С.151-154.

Забудский Г.Г. Об оценках цены связывающей сети в неких задачках размещения // Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. С. 10 - 25.

Забудский Г.Г. О целочисленной постановке одной Некоторые свойства многогранника. Задачи о P-медиане - статья задачки размещения объектов на полосы // Управляемые системы. Новосибирск, 1990. Т. 30. С.35-45.

Забудский Г.Г. Задачки рационального размещения взаимосвязанных объектов на полосы // Способы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 5 - 24.

Zabudsky G.G. On the One-Dimensional Space Allocation Problem with Minimal Admissible Distances // Optimization-Based Computer-Aided Некоторые свойства многогранника. Задачи о P-медиане - статья Modelling and Design.-Prague, Czech Republic: IITA CR. 1995. P. 448-452.

Колоколов А.А., Леванова Т.В. Методы декомпозиции перебора L-классов для решения неких задач размещения // Вест. Омск. ун-та. 1997. N1. С. 21-23.

Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир,1978.-432 с.

Колоколов А.А. Выпуклые огромного количества с альтернирующим Некоторые свойства многогранника. Задачи о P-медиане - статья L-разбиением // Моделирование и оптимизация систем сложной структуры. Омск: ОмГУ, 1987. С.144-150.


nekotorie-predosterezheniya.html
nekotorie-prichini-i-faktori-sindroma-emocionalnogo-vigoraniya-u-pedagogov-doshkolnogo-obrazovaniya.html
nekotorie-priemi-i-sposobi-razdvoeniya.html