Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

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

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

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

Если  |JM| p тогда строим множества: D = ki , 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

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

Получаем, что 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 с.

Рекомендуем скачать другие рефераты по теме: бесплатные дипломные работы скачать, шпаргалки скачать бесплатные шпаргалки.





Предыдущая страница реферата | 1  2  3 | Следующая страница реферата