<<
>>

Постановка задачи разбиения

Большинство разработанных к настоящему времени алгорит­мов разбиения используют в качестве модели схемы граф или гиперграф [5.1]. Существенным недостатком, при использовании графа в качестве модели схемы, является наличие неоднозначно­сти, так как одной цепи соответствует набор деревьев, построен­ных на связываемых этой цепью вершинах.

Задача разбиения гиперграфа с взвешенными вершинами и ребрами формулируется следующим образом.

Дан гиперграф H = (X, E), где X = {xi| i = 1,2,..., n}— множество вершин, a E = {ej∙ | ej∙ C X, j = 1,2,..., m}— множе­ство ребер (каждое ребро — подмножество связываемых им вер­шин).

Вес вершин задается множеством Φ = {φi| i = 1,2,..., n}, а вес ребер — множеством Ψ = = {ψi| i = 1,2,...,n}. Необходимо сформировать Kузлов, т. е. множе­ство X разбить на K непустых и непересекающихся подмножеств Xv, т.е. X = UXv, (∀i, j) [Xi ∩ Xj = 0], Xvne0. На рис. 5.1 показано условное разбиение гиперграфа.

На формируемые узлы (блоки, компоненты) накладываются ограниче­ния. C помощью векторaP = {pv| v = = 1,2,..., k}задается максимально до­пустимый суммарный вес вершин, назначенных в v-й узел, а с помощью вектора N = {nv| v = 1,2,..., k} — максимально допустимое число вершин, назначенных в v-й узел.

Ограничения на назначение в блок имеют вид

Выражение (5.1) является ограничением на максимальный вес узла, а выражение (5.2) — на максимальное число вершин в узле.

Иногда задано допустимое число выводов γmaxдля узлов. Ограничение для узлов на число выводов γvимеет вид

где Ev— множество ребер, связывающих множество вершин Xv с вершинами остальных узлов.

Основным критерием является F1— суммарная стоимость ребер в разрезе:

j=J

где— множество ребер в разрезе.

Вторым, часто используемым, критерием является F2 — сум­марное число выводов:

Возможно использование критерия F, являющегося аддитивной сверткой критериев Fi и F2:

где к и k2— коэффициенты значимости критериев F1, F2.

Задачу разбиения гиперграфа H = (X, E) с взвешенными вершинами и ребрами сведем к задаче о назначении множества гиперребер E в Kузлов при выполнении следующих условий: каждое гиперребро может быть назначено только в один узел, а стоимость вершин, назначенных в узел zv, не должна превышать наперед заданной величины pv. Будем считать, что гиперребро ej∙ назначено в узел zv, если все множество, составляющих его вершин, назначено в этот узел.

Введем булевы переменные:

Согласно описанным условиям должны выполнятся следую­щие ограничения:

В соответствии с критерием стоимости связей между узлами, или, что одно и то же, стоимости гиперребер, полностью разме­щенных в узлах, целевая функция примет вид

максимизировать

Установим связь между переменными hjvи yivс помощью следующей группы ограничений:

где Θ(ej∙) — мощность множества ej∙, т. е. Θ(ej∙) = ∣ej∙|, a Ij = = {i∣Xi∈ej}.

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

максимизировать

при ограничениях

Число ограничений D = (m + 1) ∙ k + n.

Для построения математической модели задачи разбиения гиперграфа с взвешенными вершинами и ребрами по критерию

минимума числа выводов формируемых узлов введем булеву пе­ременную qjv:

Целью задачи является отыскание минимума функции

Установим связь между переменными qjvи yivс помощью следующей группы ограничений:

Действительно, при некотором опорном плане в соответствие с этой группой ограничений qjv= 0 только в том случае, когда ни одна из вершин, составляющих гиперребро ej∙, не назначена в узел Zv.

Задача разбиения гиперграфа с взвешенными вершинами и ребрами по критерию минимума числа выводов формируемых узлов формулируется следующим образом:

минимизировать

v=1 j=1

при ограничениях

Число ограничений D = (m + 1) • к+ n.

5.3.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Постановка задачи разбиения:

  1. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  2. ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА РАСЧЕТА ЖЕЛЕЗОБЕТОННЫХ ПЛИТ МЕТОДОМ КОНЕЧНЫХ ЭЛЕМЕНТОВ В ФИЗИЧЕСКИ НЕЛИНЕЙНОЙ ПОСТАНОВКЕ
  3. Основные задачи и интегральные физические характеристики, рассматриваемые в работе
  4. Аналитические методы решения двумерных задач строительной механики
  5. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ПО РАСЧЕТУ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  6. Основные нерешенные проблемы в развитии МИКФ Цели и задачи диссертационной работы
  7. 2.16.1 Тестирование функции (2.48) в задачах поперечного изгиба пластинок с жестко защемленным контуром
  8. ПРОБЛЕМЫ РАЗВИТИЯ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК
  9. Тестирование функции (2.48) в задачах поперечного изгиба пластинок с шарнирно опертым контуром
  10. Приближенные методы решения задач технической теории пластинок
  11. Шляхов Станислав Владимирович. РАЗВИТИЕ И ПРИМЕНЕНИЕ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ К РЕШЕНИЮ НЕКОТОРЫХ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК C КРИВОЛИНЕЙНЫМИ УЧАСТКАМИ КОНТУРА. Диссертация на соискание учёной степени кандидата технических наук. Орёл - 2019, 2019
  12. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  13. § 2. Правовое регулирование обязанностей банков, связанных с учетом налогоплательщиков
  14. ОГЛАВЛЕНИЕ
  15. СОДЕРЖАНИЕ