Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Некоторые свойства многогранника. Задачи о P-медиане
Раздел: Рефераты по математике
Тип: статья Добавлен 13:19:08 24 марта 2007 Похожие работы
Просмотров: 46 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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, и . Возможны варианты.

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 строим следующим образом:

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

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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:52:53 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:52:52 24 ноября 2015

Работы, похожие на Статья: Некоторые свойства многогранника. Задачи о P-медиане

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151243)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru