Статья

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

Работа добавлена на сайт bukvasha.net: 2015-10-29

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 26.12.2024



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

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

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

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

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

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

Рассматривается целочисленная модель задачи о p- медиане:



(1)

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



(2)

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

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

1) каждая точка zZk образует отдельный класс;

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

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

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

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

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

ТЕОРЕМА. Для произвольного упорядочения переменных многогранник Mp имеет альтернирующую L-структуру .

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

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

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

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

Вектор z1 строим следующим образом: f08.gif (2095 bytes)

Нетрудно проверить, что .

1.2 q+1p. Построим множество JM = {k|xkk = 1}{i}.

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

Если  |JM| p, то, как рассмотрено выше, строим множества Jj и вектор z1.

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

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

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

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

В случае, если |VM| p- |JM|, выбираем произвольно (p-|JM|)- |VM| элементов из множества VN и включаем их в множество VM.

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

Покажем, что Jj для каждого рассматриваемого j. Действительно, если найдется j, для которого Jj=, тогда рассмотрим множество Dj = {k | 0xkj1}

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

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

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

Теорема доказана.

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

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

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

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

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

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

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

Забудский Г.Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. Новосибирск, 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 Modelling and Design.-Prague, Czech Republic: IITA CR. 1995. P. 448-452.

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

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

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

Для подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/



1. Курсовая Ответственность субъектов хозяйствования за нарушение законодательства в области качества продукции
2. Курсовая на тему Учет формирования себестоимости транспортных услуг
3. Конспект на тему Артур Шопенгауэр Афоризмы житейской мудрости
4. Реферат Криминал
5. Реферат Як використовуються відходи в нафтопереробній промисловості
6. Реферат на тему Alcohol And Fetal Alcohol Syndrome Essay Research
7. Статья The models of atoms nucleus and table of elements
8. Реферат на тему Reason
9. Реферат на тему Виды валютного риска и методы страхования
10. Реферат на тему Загальні основи патології