Программные продукты и системы, 2010, № 1

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 
3

РЕЖИМЫ РАБОТЫ СИТУАЦИОННОГО ЦЕНТРА 
РЕГИОНАЛЬНОГО УРОВНЯ 
 
Д.А. Колесников; В.С. Симанков, д.т.н. 
(Кубанский государственный технологический университет, г. Краснодар, 
dream023@mail.ru, svs123123@mail.ru) 

 
Рассмотрена усовершенствованная структура ситуационного центра путем создания комплекса подсистем и БД 
с настроенным программным обеспечением для взаимодействия с экспертами, а также путем оперативной переконфигурации работы центра в режимах нормального функционирования, планирования и работы в кризисной ситуации. 
Ключевые слова: ситуационный центр, информационно-аналитические технологии и системы, режимы функционирования. 
 
В современной социально-экономической ситуации на первый план выходят своевременность 
и быстрота реагирования руководства региона на 
изменения обстановки и взаимодействие со структурами управления разного уровня. Для решения 
различных задач такого типа создается ситуационный центр (СЦ), предназначенный для проведения совместных (групповых) совещаний по выработке решения различных управленческих задач 
(проблем, ситуаций) с применением автоматизированных и инструментальных средств комплексного анализа и многовариантного сценарного и 
целевого прогнозирования социально-экономического развития региона. Важнейшим условием эффективной работы СЦ является организация четкого информационного взаимодействия со структурами как местного, так и федерального уровня. 
Основными задачами, решаемыми в СЦ, являются [1]: 
– интеграция 
различных 
информационноаналитических ресурсов в основных сферах деятельности региона; 
– реализация аналитических задач социальноэкономического развития субъекта Российской 
Федерации (комплексная оценка ситуации, расчет 
сводных, рейтинговых оценок по региону); 
– выполнение экспериментальных имитационных и целевых прогнозных расчетов, а также 
мониторинг ключевых индикаторов социальноэкономического развития субъекта РФ с использованием федеральных сценариев на основе хозяйственного комплекса региона и его муниципальных образований; 
– формирование экспертных заключений и 
выработка рекомендаций по принятию управленческих решений в вопросах социально-экономического развития региона; 
– своевременное и наглядное предоставление 
руководству органов государственной власти отчетной, аналитической и прогнозируемой информации, необходимой для принятия адекватных 
решений оперативного и стратегического характера, с применением средств деловой графики, картографии, табличного и текстового представления 
информации. 

В СЦ поступает плановая информация от органов управления для выработки сценария и планирования развития, а также информация о сложившейся обстановке с целью ее мониторинга и 
анализа для последующей выработки решения, 
направленного на улучшение по выбранным показателям качества и эффективности. Кроме того, 
может поступить информация о какой-либо экстренной ситуации, на которую необходимо немедленное реагирование соответствующих служб 
и руководства.  
Постановка задачи. На основе проделанной 
работы и аналитических исследований [1, 2] авторами разработана структура СЦ региона (см. рис.), 
в полной мере отражающая все аспекты возможных ситуаций [3]. 
Характер задач, решаемых СЦ, определяет 
выбор организационных схем взаимодействия, 
методических и программно-технических средств. 
Предполагается, что все ресурсы СЦ скоординированы, персонал надлежащим образом обучен, а 
организационная схема его работы в различных 
ситуациях утверждена и доведена до всех участников [1]. 
В структуру СЦ введены подсистемы, гарантирующие конечный результат, будь то выход из 
сложившейся ситуации или прогноз социальноэкономической политики региона. В зависимости 
от входных данных, поступающих в СЦ, происходит синтез работоспособности подсистем, то есть 
из всей совокупности подсистем СЦ будут использоваться только те, что необходимы для обработки входных данных. При этом общая активность и структура системы остаются неизменными. Для однозначности и полноты принимаемого 
решения предполагается постоянное обращение к 
БД заранее созданных информационных подсистем, за счет чего экономятся время и ресурсы СЦ. 
В целом достигается повышение оперативности в 
выработке управленческих решений в складывающихся ситуациях. 
Предложенная структура СЦ является интегрирующей, способной объединять все ведомственные и муниципальные источники информации 
в регионе для управления им (то есть включать 

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 4

систему сбора и структурирования информации из 
разных внешних источников). 
Все режимы работы СЦ подразумевают мониторинг данных и визуализацию обработанной информации на экранах коллективного пользования. 
В организационно-функциональную структуру СЦ входят: 
− система анализа данных; 
− система прогнозирования ситуации; 
− система поддержки принятия решений; 
− система ситуационного моделирования и 
прогнозирования; 
− БД мониторинга ситуации; 
− база геоданных; 
− семантическая БД; 
− БД моделей; 
− БЗ моделей и ситуаций; 
− БД критериев и альтернативных ситуаций; 
− БЗ правил и приемов принятия решений; 
− универсальное хранилище данных; 
− подсистема визуализации; 
− экспертная группа по принятию решений и 
аналитическому решению; 
− группа исследователей; 
− ЛПР. 

Достаточно широкий круг задач, решаемых в 
СЦ, требует постоянного мониторинга места событий и оценки обстановки в любой момент. Эти 
задачи могут значительно отличаться друг от друга по продолжительности, обширности интересов, 
требованиям к скорости реакции системы и степени детализации геоданных. 
Любую информацию о ситуации, поступающую в СЦ, обрабатывает блок системы мониторинга при взаимодействии с БД мониторинга. 
В нем происходит обработка информации экспертами в соответствии с нормативными документами с выводом их оценки сложившейся ситуации.  
Таким образом, формируется результат, который передается в блок системы анализа данных. 
В этом блоке происходит классификация обстановки: статическая или динамическая.  
Ситуация считается статической, если событие уже произошло и его состояние может быть 
устойчивым хотя бы временно.  
Ситуация является динамической, если возникла внезапно и требует оперативного реагирования, при этом она может описываться в виде 
неких процессов (событий), которые требуют 
немедленного 
реагирования 
соответствующих 
служб [2]. 

 
Типовая структура ситуационного центра региона для трех режимов функционирования 

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 
5

После классификации ситуации создается 
ее модель и идет поиск аналогичной модели в 
соответствующей БД моделей блока системы 
ситуационного моделирования и прогнозирова- 
ния. 
На следующем этапе осуществляется прогнозирование ситуации в блоке системы прогнозирования ситуации с возможным описанием ее последующего развития.  
На основе полученных прогнозов в блоке 
системы поддержки принятия решений происходит обращение к БД принятия решений, а также 
формирование возможного управленческого решения на основе работы экспертов-аналитиков, 
разрабатываются варианты, наиболее полно отвечающие поставленной задаче.  
После выработки решения завершающим этапом является представление результатов для руководителя в блоке визуализации результатов. 
Анализ полученных результатов. Для оперативного реагирования на обстановку предусматривается работа СЦ в следующих режимах. 
1. Нормальный режим работы предусматривает разработку сценариев социально-экономической и общественно-политической обстановки, при 
этом режиме предполагается обеспечение реализации следующих задач: 
а) мониторинг текущих событий (вырисовываются формы и методы перехода от наблюдения 
к аналитической обработке накапливаемой информации о жизнедеятельности региона); 
б) выявление проблемных ситуаций, включая 
уровень муниципальных образований, административных районов; 
в) информационно-справочное обслуживание, 
предполагающее решение большого круга вопросов организационного, научно-методического характера, критериев отраслевых и интегральных 
оценок. 
2. Режим планирования позволяет находить 
скрытые причинно-следственные связи социально-экономических процессов, моделировать жизнедеятельность территории на уровне отраслей, 
отдельных предприятий, прогнозировать социально-экономическое развитие региона. В частности, 
он позволяет оперативно организовать 
– обсуждение проблемы; 
– проведение совещаний на основе полученного материала; 
– планирование и прогнозирование развития 
ситуации; 
– предоставление аналитических материалов; 
– анализ и рассмотрение вариантов решения; 
– подготовку проблемных видеодокладов. 
3. Кризисный режим работы необходим для 
принятия решений в сложных или чрезвычайных 
ситуациях, в частности, если 

− произошло нарушение нормальных условий 
жизнедеятельности на объекте, вызванное катастрофой, при этом основные усилия будут направлены на ликвидацию последствий чрезвычайной 
ситуации; 
– хозяйственные процессы хуже управляются 
и их изменения происходят с более высокой скоростью, чем в повседневном режиме, при этом основные усилия будут направлены на анализ и прогнозирование ситуации. 
При необходимости СЦ даст рекомендации по 
привлечению сторонних ресурсов. 
В кризисном режиме поступившая информация сопровождается непрерывным мониторингом 
ситуации с последующим (и постоянным) анализом данных. Каждая подсистема непрерывно 
взаимодействует со своей БД; работа экспертов и 
аналитиков заключается в мозговом штурме для 
выработки правильного решения. Наиболее важным в данной ситуации является предотвращение 
возможности появления угрозы для жизни людей. 
Задача принятия решения в кризисной ситуации 
является плохо формализуемой, поскольку характеризуется отсутствием формальных алгоритмов 
решения, нечеткостью входных параметров (исходной информации) и характеристик достигаемых целей. Кроме того, в БД нередко отсутствуют 
аналоги происходящих кризисных ситуаций. Чаще 
всего подобные задачи имеют несколько альтернативных решений. 
В заключение отметим, что в работе усо- 
вершенствована структура СЦ путем создания 
комплекса подсистем и БД с настроенным программным обеспечением при взаимодействии с 
экспертами и аналитиками, а также оперативной 
переконфигурации работы центра в режимах 
нормального функционирования, планирования и 
работы в кризисной ситуации. Выбор соответствующего режима обеспечивает большую оперативность и экономию ресурсов системы. Это достигается, в первую очередь, за счет оптимизации 
работы подключаемых в данный момент подсистем сервисного центра и минимизации времени, 
затрачиваемого экспертами на анализ обстановки 
и выработку решения. 
 
Литература 
 
1. Симанков В.С., Луценко Е.В., Лаптев В.Н. Системный 
анализ в адаптивном управлении: Монография [под ред. В.С. 
Симанкова]. Краснодар: Ин-т совр. технол. и экон., 2001. 258 с.  
2. Кретов В.С., Лебедев И.С., Котов М.Н. Принципы построения и функциональные возможности двух новых информационно-аналитических систем для ситуационных центров // 
Наукоемкие технологии. 2007. № 12. C. 23–29.  
3. Симанков В.С., Колесников Д.А., Черкасов А.Н. Разработка теоретических основ и построение интеллектуальных 
систем мониторинга, анализа и поддержки принятия политических, социально-экономических и технологических решений 
регионального уровня для ситуационных центров органов власти. Краснодар: ООО «Просвещение-ЮГ», 2008. C. 176–181. 
 
 

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 6

МЕТОД ПОСТРОЕНИЯ ОКРЕСТНОСТИ ГЛОБАЛЬНОГО ОПТИМУМА 
NPC-ЗАДАЧ НА РАНЖИРОВАННОМ ДЕРЕВЕ ПОИСКА РЕШЕНИЙ 
 
А.В. Власенко, к.т.н.; В.Н. Марков, д.т.н. 
(Кубанский государственный технологический университет, г. Краснодар, 
vlasenko@kubstu.ru, vinitar@yandex.ru) 

 
Рассматривается метод построения окрестности глобального оптимума в виде ранжированного поддерева, содержащего только субоптимальные решения NPC-задач. В основу предлагаемого метода положена функция оценки 
веса ранжированного решения, описывающая статистически выявленные закономерности распределения ранжированных решений. 
Ключевые слова: окрестность глобального оптимума, ранжированное дерево, NPC-задачи. 
 
Суть описываемого метода заключается в построении ранжированного поддерева поиска решения посредством выбора на каждом шаге только тех локальных решений, при которых функция 
оценки веса глобального решения от рангов локальных решений не превышает заданный порог. 
Стратегия применения метода заключается в 
управлении шириной поиска на дереве решений с 
помощью выбора порога функции оценки глобального решения и глубиной поиска, которая не 
должна превышать величину веса наилучшего текущего решения. 
Область применения метода ограничивается 
недетерминированными полиномиальными полными задачами потребления ресурсов произвольной 
природы, 
допускающими 
приближенное 
решение. К таковым относятся задачи оптимизации пути коммивояжера, раскроя-упаковки и 
нестинга, размещения обслуживающих центров, 
поиска оптимального подмножества заданного 
множества и т.п. [1]. 
В общем случае исходные данные описываются в виде графов без петель и кратных ребер 
G=(V, E, d), где V – множество вершин-ресурсов 
vi произвольной природы, |V|=n; каждая вершина 
vi характеризуется вектором параметров ресурсов 

Pi=(p1, p2,…, pd), определенных на множестве ℝℝℝℝ+, 

pi∈∈∈∈ℝℝℝℝ+; d – размерность ресурсов, определенная на 

множестве ℤℤℤℤ+; E – множество ребер eij, задающих 
отношение смежности произвольной природы 

между вершинами vi и vj, eij=eji, i≠≠≠≠j, 

2
n
n
E
2
−−−−
≤≤≤≤
. 

 
Дерево решений 
 
Потребление ресурсов заключается в пошаговом исключении из графа G выбираемых по определенному критерию ресурсов и в формировании 
на их основе цепи ππππ(n,k)=[v1, v2, …, vk], k – длина 
цепи [1]. Дерево решений задается множеством 
ветвей ΠΠΠΠn,k, каждая из которых является цепью 
ππππ(n,k) на графе G: ΠΠΠΠn,k={ππππ(n,k) | 0<k≤≤≤≤n+1}. 
Так как степень вершин на каждом шаге решения уменьшается на единицу, количество всех 
цепей ππππ(n,k) равно 

((((
))))

((((
)))),

n 1
k

n,k 1
i n k
n!
n! e
(n k,0)
(n k,1)
i!
(n k 1)!
n e
(n,0)
(n,1)

−−−−

= −
= −
= −
= −
⋅⋅⋅⋅
Π
=
=
Γ
−
−Γ
−
−
Π
=
=
Γ
−
−Γ
−
−
Π
=
=
Γ
−
−Γ
−
−
Π
=
=
Γ
−
−Γ
−
−
∑∑∑∑
− −
− −
− −
− −
− ⋅ ⋅ Γ
−Γ
− ⋅ ⋅ Γ
−Γ
− ⋅ ⋅ Γ
−Γ
− ⋅ ⋅ Γ
−Γ
 

что обусловливает факториальный рост сложности NPC-задач потребления невозобновляемых 
ресурсов.  
 
Задача оптимального потребления 
невозобновляемых ресурсов 
 
Определим вес вершины v графа G функцией 

d

i

i 1
q(v)
p

====
====∏
∏∏
∏
, а вес цепи 
k 1

1
i,i 1
i 1
h( ) q(v )
[w(e
) ]

−−−−

++++
====
π =
+
+
π =
+
+
π =
+
+
π =
+
+
∑∑∑∑
 

i 1
[ q(v
)]
++++
++++
, где w(ei,i+1) – вес ребра. Задача состоит в 

нахождении подмножества субоптимальных решений 
*
n,k
n,k
Π
⊂Π
Π
⊂Π
Π
⊂Π
Π
⊂Π
, которое содержит только те 

цепи 
*
*
n,k
π ∈Π
π ∈Π
π ∈Π
π ∈Π
, у которых наибольшая вероятность 

того, что их вес h(ππππ*) минимален во всем множестве ΠΠΠΠn,k: 

{{{{
}}}}

n,k

*
*
*
n,k
i
|P h(
) min(h(
))

Π
ΠΠ
Π

Π
= π
π
=
π
>
Π
= π
π
=
π
>
Π
= π
π
=
π
>
Π
= π
π
=
π
>
{{{{
}}}}

n,k
i
P h(
) min(h(
))

Π
ΠΠ
Π

′′′′
>
π =
π
>
π =
π
>
π =
π
>
π =
π
, где 
((((
))))

*

n,k
n,k
\
′′′′
π ∈ Π
Π
π ∈ Π
Π
π ∈ Π
Π
π ∈ Π
Π
. 

 
Ранжированные цепи 
 
Построение функции оценки веса цепи предлагается проводить для ранжированных цепей 
ππππ(n, k)=(r1, r2,…, ri,…, rk), то есть тех цепей, у которых все вершины заменены их рангами. 
Для введения метрики в пространство поиска 
определена количественная характеристика произвольной ранжированной цепи ππππm(n, k) с фиксированной длиной k – ее уникальный целочисленный номер m в факториальной системе счисления 

(ФСС): 

k

i
i 1
m
r (n
i)!

====
=
⋅
−
=
⋅
−
=
⋅
−
=
⋅
−
∑∑∑∑
. 

По номеру m цепи ππππm(n, k) взаимно-однозначно восстанавливаются ранги локальных 
решений (r1, r2,…, ri,…, rk). 
Например, ранжированная цепь, удовлетворяющая принципу оптимальности Беллмана, содержит только нулевые значения рангов ππππ0(n, k)= 

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 
7

=(01, 02, …, 0k) и ее номер в ФСС m=0. Такая цепь 
является глобальным оптимумом, так как имеет 
наибольшую среди прочих цепей вероятность того, что вес этой цепи оптимален. 
 
Функция оценки веса ранжированной цепи 
 
На каждом шаге решения приращение ∆∆∆∆hi= 
=w(ei,i+1)+q(vi+1) увеличивает вес цепи h(ππππi+1)= 
=h(ππππi)+∆∆∆∆hi. Рассмотрим приведенную к интервалу 
]0, 1] функцию оценки веса цепи f(ππππi+1)=f(ππππi)+∆∆∆∆fi и 
зависимость приращения оценки ∆∆∆∆fi от величины 
ранга ri+1 и номера текущего шага i. 
Так как на каждом шаге решения присоединяемая к цепи вершина удаляется из графа исходных данных вместе с инцидентными ей ребрами, 
на i-м шаге решения оценка приращения ∆∆∆∆fi может 
принимать одно из n-i значений. Нахождение 
функции оценки веса ранжированной цепи опирается на два постулата, принятые для произвольного i-го шага решения. 
1. Все n-i возможных оценок приращений ∆∆∆∆fi 
лежат в интервале [∆∆∆∆fmin, 1] с шагом ∆∆∆∆fmin, где 

min

1
f
n i
∆
=
∆
=
∆
=
∆
=
−−−− . 

2. Оценка приращения веса прямо пропорциональна рангу ri локального решения и обратно 
пропорциональна числу возможных приращений 
n-i. 
Согласно принятым постулатам найдем оценку приращения веса в виде 

i
i

r
A
f(n,i,r )
n i B

++++
∆
=
∆
=
∆
=
∆
=
− +
− +
− +
− +
  
 
 
 
 
 
 
(1) 

с граничными условиями для минимального 
rmin=0 и максимального rmax=n-i рангов 

1
f(n,1,0)
,
n
f(n,n,0) 1,
f(n,1,n i) 1.

∆
=
∆
=
∆
=
∆
=
∆
=
∆
=
∆
=
∆
=
∆
−
=
∆
−
=
∆
−
=
∆
−
=
 
 
 
 
 
 
 
(2) 
Как видно из (2), приращения оценок при rmin 
представляют собой гармонический ряд. Приращения оценок при rmax равны единице. Подставляя 
(1) в (2), легко найти значения коэффициентов 
А=1 и В=1. Таким образом, приведенная функция 
приращений весовой функции принимает вид 

i
i

r
1
f(n,i,r )
n i 1

++++
∆
=
∆
=
∆
=
∆
=
− +
− +
− +
− + , 

а оценка весовой функции является суммой k оценок приращений ∆∆∆∆fi: 

k
i

i 1

r
1
f( (n,k))
n i 1
====

++++
π
=
π
=
π
=
π
= ∑∑∑∑
− +
− +
− +
− +
.  
 
 
 
 
 
(3) 

На рисунке 1 приведены средние веса двадцати четырех цепей hm(ππππ(5, 6)) и их оценка 
fm(ππππ(5, 6)), полученные при решении полным перебором задачи коммивояжера на полном графе, 
генерируемом 100 тысяч раз со случайными весами ребер в интервале 0<w(ei,j)≤≤≤≤1. Так как оценка 
является приведенной, она не позволяет получить 

приближенное значение весовой функции, а лишь 
прогнозирует ее ранг относительно всех решений. 
При этом ранги всех остальных решений вычислять не надо. 
Кроме этого, на рисунке 1 показана аппроксимация веса hm на основе экспоненциального приближения 
B m
m
m
h
A f
e
C
⋅⋅⋅⋅
≈
⋅
⋅
+
≈
⋅
⋅
+
≈
⋅
⋅
+
≈
⋅
⋅
+
 оценки fm к весу hm 
по критерию минимума среднего квадратичного 
отклонения, σσσσ = 0,014 при А=0,77, В= –0,0059, 
С=0,078. 
 
Построение ранжированной окрестности 
глобального оптимума 
 
Предлагаемый метод является вариантом метода ветвей и границ для случая ранжированного 
пространства поиска и установленной функции 
оценки веса ранжированной цепи (3). Суть метода 
заключается в построении окрестности 
0
n,k
ΠΠΠΠ
 гло
бального оптимума (ОГО), содержащей в лексикографическом порядке только те цепи ππππ(n,k), 
оценка веса которых не превышает априорно заданного 
порога 
f0(ππππ(n, k)) 
{{{{
}}}}

0
n,k
(n,k)|
Π
= π
Π
= π
Π
= π
Π
= π
 

}}}}
0
f( (n,k)) f ( (n,k))
π
≤
π
π
≤
π
π
≤
π
π
≤
π
 в задачах минимизации. 

В задачах максимизации веса цепей ОГО не ниже 
априорно заданного порога. Лексикографический 
порядок минимизирует вычислительные затраты 
при построении окрестности. 
Величина порога f0(ππππ(n, k)) находится в интервале 

min
0
max
f
( (n,k)) f ( (n,k)) f
( (n,k))
π
≤
π
≤
π
π
≤
π
≤
π
π
≤
π
≤
π
π
≤
π
≤
π
 (4) 
и может быть задана двумя способами: 
• оценкой веса m-й цепи f(ππππm), тогда ОГО 
будет содержать только те цепи, оценка веса которых не выше оценки веса цепи f(ππππm); 
• оценкой веса f0, при которой ОГО будет 
включать точно заданное количество проверяемых 
субоптимальных цепей, оценка веса которых не 
выше f0. 
Точное нижнее значение порога fmin(ππππ(n, k)) 
из (4) определяется как сумма гармонического ря
Рис. 1. Экспериментальная функция веса hm(π(5, 6)) 
и ее оценка fm(π(5, 6)) 

 

1

1,5

2

2,5

0
5
10
15
20
m

Вес цепи    
Оценка веса    
Аппроксимация веса    
fm

hm

hm

fm
hm

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 8

да на интервале от 
1

n k 1
− +
− +
− +
− +
 до 1

n : 
min
f
( (n,k))
π
=
π
=
π
=
π
=

n

n k 1
1
(n 1)
(n k 1)
i
− +
− +
− +
− +
=
=ψ
+
−ψ
− +
=
=ψ
+
−ψ
− +
=
=ψ
+
−ψ
− +
=
=ψ
+
−ψ
− +
∑∑∑∑
, где 
d
(z)
(z)
dz
ψ
=
Γ
ψ
=
Γ
ψ
=
Γ
ψ
=
Γ
ln
 – 

логарифмическая производная гамма-функции [2]. 
Точное верхнее значение порога fmax(ππππ(n, k))=k. 
Для полной цепи ππππ(n, n) точное нижнее значение порога определяется как сумма гармоническо
го ряда от 1 до 1

n : 

n

min
1
1
f
( (n,n))
(n 1) С
n
π
=
=ψ
+
+
π
=
=ψ
+
+
π
=
=ψ
+
+
π
=
=ψ
+
+
∑∑∑∑
, 

где C – постоянная Эйлера–Маскерони. 
С целью повышения эффективности программной реализации оценки нижнего значения 
порога можно вычислять приближенно: 

min

n 1
f
( (n,k))
n k 1

++++
π
≈
π
≈
π
≈
π
≈
− +
− +
− +
− +
ln
, 
min
f
( (n,n))
(n 1) C
π
≈
+
+
π
≈
+
+
π
≈
+
+
π
≈
+
+
ln
. 

Для реализации предлагаемого метода необходимо указать конкретное значение порога 

r
0
h ( (n,k))
ππππ
 в зависимости от значений n, k, а также требуемого количества проверяемых цепей. 
Для этого порог представляется в виде суммы его 
минимального значения и приращения: 

0
min
0
f ( (n,k)) f
( (n,k))
f
π
=
π
+∆
π
=
π
+∆
π
=
π
+∆
π
=
π
+∆
,  
 
 
 
(5) 
где ∆∆∆∆f0 определяется отношением разности максимального и минимального значений порога к 
общему количеству решений |Пn,k|: 

0
k
(n 1)
(n k 1)
f
(n k)!
n!
−ψ
+
+ψ
− +
−ψ
+
+ψ
− +
−ψ
+
+ψ
− +
−ψ
+
+ψ
− +
∆
=
⋅
−
∆
=
⋅
−
∆
=
⋅
−
∆
=
⋅
−
. 

Умножая среднее приращение порога на величину q-1, получим оценку величины порога для 
известного количества q проверяемых цепей: 

0f ( (n,k))
(n 1)
(n k 1) (q 1)

k
(n 1)
(n k 1) (n k)!
n!

π
=ψ
+
−ψ
− +
+
−
×
π
=ψ
+
−ψ
− +
+
−
×
π
=ψ
+
−ψ
− +
+
−
×
π
=ψ
+
−ψ
− +
+
−
×

−ψ
+
+ψ
− +
−ψ
+
+ψ
− +
−ψ
+
+ψ
− +
−ψ
+
+ψ
− +
×
⋅
−
×
⋅
−
×
⋅
−
×
⋅
−
 

Величина q уменьшена на единицу, так как 
первое слагаемое в формуле (5) представляет собой проверку одного варианта – глобального оп
тимума. При известной доле 
(q 1) (n k)!
d
n!
−
⋅
−
−
⋅
−
−
⋅
−
−
⋅
−
====
 

проверяемых цепей оценка величины порога имеет 
вид 
f0(ππππ(n,k))=d⋅⋅⋅⋅k+(1-d)⋅⋅⋅⋅ψψψψ(n+1)+(d-1)⋅⋅⋅⋅ψψψψ(n- 
-k+1). 
С целью повышения эффективности программной реализации приближенная оценка величины порога от известного значения q имеет вид 

1
2

1
2

0

n k
k

n

n 1
f ( (n,k))
n k 1
(q 1) (n k)
e
n 1
k
n k 1
n

− +
− +
− +
− +

++++

++++
π
≈
+
π
≈
+
π
≈
+
π
≈
+
− +
− +
− +
− +
−
⋅
−
+
−
⋅
−
+
−
⋅
−
+
−
⋅
−
+
+
−
+
−
+
−
+
−
− +
− +
− +
− +
ln

ln
 

и от известной доли d: 

0
n 1
f ( (n,k)) (1 d)
d k
n k 1
++++
π
≈
−
⋅
+ ⋅
π
≈
−
⋅
+ ⋅
π
≈
−
⋅
+ ⋅
π
≈
−
⋅
+ ⋅
− +
− +
− +
− +
ln
. 

На рисунке 2 приведена ОГО 
0
5,6
ΠΠΠΠ
 в задаче 

коммивояжера на полном пятивершинном графе. 

ОГО ограничена порогом, заданным оценкой веса 
18-й цепи f18. Цепи окрестности 
0
5,6
ΠΠΠΠ
={0, 1, 2, 4, 6, 

7, 8, 12, 18} выделены круглыми маркерами. Данные цепи ππππi(5, 6) являются прообразами оценок 
fi(ππππ(5, 6)), не превосходящих указанный порог f18 и 
отмеченных квадратными маркерами. 
В окрестность 
0
5,6
ΠΠΠΠ
 вошло множество цепей 

{4, 7}, не являющихся субоптимальными по отношению к весу f18, так как их веса больше веса f18. 
Эти цепи отмечены незакрашенными круглыми 
маркерами, а их оценки – незакрашенными квадратными маркерами. Таким образом, окрестность 

0
5,6
ΠΠΠΠ
 распадается на множество цепей {0, 1, 2, 6, 8, 

12, 18}, которые находятся в пределах величины 
εεεε-окрестности глобального оптимума, определяемой порогом εεεε=h18, а также на множество цепей 
{4, 7}, находящихся в пределах изменяемого параметра ξξξξ=max(h4, h7)-h18. 
На рисунке 3 изображено полное дерево поиска решений в описанной задаче коммивояжера, 
которое содержит 4! решений. Сплошными линиями выделена ОГО. Ребра помечены рангами 
локальных решений. Вершины дерева содержат 
номер шага решения. Листья дерева снизу подписаны номерами m цепей ππππm(5, 6) в ФСС. Самая ле
1

1,5

2

2,5

0
5
10
15
20
m

Вес цепи          

Оценка веса          

18

ε
ξ

hm
hm
fm
fm 

f18

h18

7
4
6
8
 
 
Рис. 2. ОГО 
0
5,6
ΠΠΠΠ
, ограниченная порогом, 

заданным оценкой веса 18-й цепи f18 

 

 
Рис. 3. ОГО на ранжированном дереве решений 
в задаче коммивояжера 

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

0
1
2
0
1
2
0
1
2
0
1
2

0
1
2
3

2

3
3
3

4
4
4
4
4
4

2

3
3
3

4
4
4
4
4
4

2

3
3
3

4
4
4
4
4
4

2

3
3
3

4
4
4
4
4
4

1

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 
9

вая ветвь поддерева является цепью глобального 
оптимума, она построена по принципу оптимальности Беллмана – содержит только нулевые ранги. 
Предварительное ранжирование локальных 
решений для каждой вершины исходного графа и 
лексикографический порядок проверки всех цепей 
ОГО позволяют сократить вычислительные затраты, так как для получения новой цепи достаточно 
заменить в текущей цепи последние вершины на 
вершины с очередным рангом, удовлетворяющим 
неравенству (4), а не строить всю цепь заново. 
 
Оценка эффективности метода 
построения ОГО 
 
На рисунке 4 приведены результаты сравнительных испытаний предлагаемого метода, оценивающего q решений, q=n, 5n, 10n, и методов 
Шермана–Рейтера и Лина [3] при поиске цепи 
ππππ(n, n+1) минимального веса в задаче коммивояжера, n – число вершин исходного графа. Для всех 
n=20, 30, …, 120 задача решалась 10 тысяч раз 
каждым алгоритмом. Нижняя теоретическая оценка вычислялась в виде суммы минимальных весов 
ребер, каждое из которых инцидентно каждой 
вершине исходного графа. 

На рисунке 5 приведены результаты сравнительных испытаний предлагаемого метода построения ОГО при q=n, 5n, 10n и эволюционного 
метода (генетического алгоритма – ГА) при поиске цепи ππππ(n, n+1) минимального веса с вышеуказанными условиями задачи коммивояжера. 
В основу используемого ГА положены следующие правила. Алгоритм инициализировался 
путем построения популяции здоровых хромосом, 
которые являются участками цепи, представляющей собой статистический глобальный оптимум. 
Роль генетических операторов выполняли операторы перекрестного скрещивания участков двух и 
более хромосом между собой. Хромосомы с наименьшим весом относительно своей длины составляли элиту и подвергались мутации с меньшей вероятностью, чем хромосомы с большим от
носительным весом. Каждое поколение содержало 
набор здоровых хромосом, представляющих собой 
правильную цепь ππππ(n, n+1) того или иного веса 
h(ππππ(n, n+1)). Такой эпистазис дал возможность 
просматривать текущее решение в произвольный 
момент без остановки ГА. Продолжительность работы ГА определялась временем работы предлагаемого алгоритма построения ОГО, оценивающего q решений, q=n, 5n, 10n, n – число вершин исходного графа. Таким образом, для каждого n=20, 
30, …, 120 ГА возвращал три решения в моменты 
получения q решений, q=n, 5n, 10n, алгоритмом 
построения ранжированной ОГО. 
На основании изложенного можно сделать 
следующие выводы. Предложенный метод построения 
окрестности 
глобального 
оптимума 
NPC-задач на ранжированном дереве поиска решений превосходит быстрые эвристики Шермана–
Рейтера и Лина и известные методы ИИ по точности решения и может применяться как самостоятельный инструмент при решении NPC-задач. 
Достоинством предлагаемого метода является 
постепенное улучшение текущего субоптимального решения, что позволяет завершать поиск либо 
по времени, либо по количеству/доле просмотренных цепей, либо по достижении заданного порога 
весовой функции, либо по завершении построения 
окрестности глобального оптимума. Недостатком 
метода являются дополнительные вычислительные затраты, обусловленные ранжированием локальных решений для каждой вершины исходного 
графа и использованием экспертно задаваемого 
порога оценки веса глобального решения. 
 
Литература 
 
1. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб: БХВПетербург, 2003. 1104 с. 
2. Корн Г., Корн Т. Справочник по математике. Определения, теоремы, формулы. СПб: Изд-во «Лань», 2003. 832 с. 
3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность; пер. с англ. М.: Мир, 1985. 
4. Макконелл Дж. Основы современных алгоритмов; пер. 
с англ. М.: Техносфера, 2004. 368 с. 
 
 

Рис. 4. Экспериментальное сравнение эффективности 
предлагаемого метода и эвристических методов 
Шермана–Рейтера и Лина при поиске цепи 
π(n, n + 1) минимального веса 

 

1,5

2,5

3,5

4,5

20
40
60
80
100
120 n

Теор. оценка

ОГО,    

ОГО,    

ОГО,     

Шерман-Рейтер

Лин

h(π(n,n+1)

q= n 

q= 5n
q= 10n

Рис. 5. Экспериментальное сравнение эффективности 

предлагаемого метода и эволюционного метода 
при поиске цепей π(n, n+1) минимального веса 

 

1,5

2,5

3,5

4,5

5,5

6,5

20
40
60
80
100
120 n

Теор.
оценка
ОГО,   

ОГО,   

ОГО,   

ГА, время
по        
ГА, время
по         
ГА, время
по         

h(π(n,n+1)

q=n

q=5n

q=10n

q=n

q=5n

q=10n

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 10

ТЕХНОЛОГИЯ МЯГКИХ ВЫЧИСЛЕНИЙ В ПРОЕКТИРОВАНИИ 
ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ УПРАВЛЕНИЯ 
 
А.А. Мишин (Научно-технологический парк «Дубна», г. Дубна, a.mishin@ntpdubna.ru); 
В.Н. Добрынин, к.т.н.; Л.В. Литвинцева, к.ф.-м.н. 
(Университет природы, общества и человека «Дубна», г. Дубна) 

 
На конкретных типовых примерах моделей динамических объектов управления демонстрируется эффективность процессов управления в условиях неполноты информации о параметрах структуры объектов управления и непредвиденных (нештатных) ситуаций управления с применением оптимизатора баз знаний на мягких вычислениях. 
Показано, что использование его в обучении и непредвиденных ситуациях управления приводит к повышению 
уровня робастности структуры интеллектуальных систем управления. 
Ключевые слова: оптимизатор баз знаний, робастность, интеллектуальные системы управления, мягкие вычисления. 
 
В системах проектирования БЗ интеллектуальных систем управления (ИСУ) построение оптимальной структуры нечеткой нейронной сети 
(ННС) возложено на опытного эксперта. Но даже 
для него выбор модели нечеткого вывода и лингвистическое описание заданного обучающего 
сигнала вручную в сложных ситуациях управления является большой проблемой. 
Проблематичным остается также определение 
требуемого соотношения между точностью аппроксимации обучающего сигнала и необходимым 
уровнем робастности всей структуры ННС. Однако эти проблемы можно решить с помощью программных средств инструментария, названного 
оптимизатором БЗ (ОБЗ) [1, 2].  
В данной статье рассматривается программная 
архитектура, принятая за основу ОБЗ. Внимание 
сконцентрировано и на описании конкретных результатов моделирования ИСУ сложными существенно-нелинейными, динамически неустойчивыми 
объектами управления (ОУ).  
 
Программная реализация 
оптимизатора БЗ 
 
Для построения ОБЗ ИСУ была выбрана модульная схема, которая подразумевает построение 
пользователем модели ИСУ из набора функциональных блоков, таких как модули ввода и вывода 
данных, лингвистических переменных, нечеткого 
вывода и других. При этом пользователь может 
произвольно соединять эти блоки, формируя модели сложных ИСУ. 
В основе модульной модели ИСУ лежат классы Model, Block и DataArchive.  
Класс Model инкапсулирует все объекты, необходимые для построения модели ИСУ, и обеспечивает взаимодействие между ними. Он отвечает за ведение списка имеющихся в модели ИСУ 
модулей, отслеживает корректность связей между 
ними, предоставляет интерфейсы для передачи 
данных модели для вычисления, а также получения результатов.  
Класс Block является базовым для реализаций 
различных модулей ИСУ. Он предоставляет об
щий интерфейс для проведения расчетов, а также 
поддерживает базовые функции, необходимые 
большинству модулей. 
Класс DataArchive обеспечивает хранение и 
извлечение данных, передаваемых внутри модели. 
В нем хранятся данные, порождаемые выходными 
портами всех модулей в системе, а также входные 
и выходные данные модели.  
В оптимизаторе реализованы два генетических алгоритма – обычный генетический алгоритм, обеспечивающий минимизацию вещественной целевой функции, а также алгоритм типа 
NSGA, находящий множество парето-оптимальных решений для задачи минимизации нескольких 
целевых функций. Эти алгоритмы могут использоваться с двумя типами хромосом, в которых кодирование решений происходит с помощью бинарной ДНК или набором вещественных чисел. 
Процесс оптимизации протекает следующим 
образом. Сначала выбирается объект для оптимизации и создается объект, реализующий опти- 
мизационный алгоритм. Параметры алгоритма  
запрашиваются у пользователя с помощью диалогового окна и соответствующего класса для обработки ввода пользователя. Хромосомы первого 
поколения по очереди декодируются оптимизируемым объектом, и для них вычисляются соответствующие 
значения 
функции 
полезности.  
После этого оптимизационный алгоритм создаетновое поколение, используя определенные генетические операции и сортировку хромосом на базе  
вычисленных значений функций полезности. Процесс продолжается до завершения оптимизации 
согласно выбранным пользователем условиям. 
Одной из основных проблем практического 
применения генетической оптимизации для создания 
ИСУ 
является 
необходимость 
проведе- 
ния большого числа вычислений функции полезности [3]. Время оптимизации может быть сокращено за счет применения оптимизации с использованием обучающего сигнала и математических 
моделей ОУ. На финальном этапе решения, показавшие себя достаточно хорошо на моделях, проверяются на реальном ОУ.  

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 
11

Разработанный ОБЗ обеспечивает такие возможности, как 
• оптимизация по заданному обучающему 
сигналу; 
• оптимизация с использованием проверки 
работы ИСУ на модели, реализованной во внешней системе, или на ОУ; 
• проверка соответствия начального состояния ОУ некоторым заданным начальным условиям; 
• одновременная работа нескольких оптимизационных алгоритмов; 
• поиск и выявление повторных запросов на 
вычисление функции полезности с дальнейшим 
использованием значения, полученного при первой проверке, либо усреднением значения функции по результатам нескольких испытаний в зависимости от предпочтений пользователя; 
• приостановление оптимизации и продолжение ее в дальнейшем с помощью различных настроек алгоритмов или даже разных алгоритмов; 
• многократное тестирование решений с целью повышения точности измерения функции 
пригодности. 
Модульный подход к построению модели 
ИСУ диктует построение интерфейса пользователя в виде набора блоков и связей между ними. 
Пользователь может добавлять или удалять блоки, 
модифицировать связи между ними. 
Для обеспечения возможности создания интерфейсов различного типа ОБЗ был выполнен в 
виде библиотеки, содержащей основные функции 
оптимизатора, а также те части интерфейса, которые могут использоваться в разных проектах. Эта 
библиотека затем может применяться для создания ОБЗ с различными интерфейсами.  
Были разработаны два интерфейса: предусматривающий возможность манипулирования с 
блоками и связями между ними и предназначенный для создания ПИД-регуляторов. 
Во втором случае пользовательский интерфейс исключает доступ пользователя к блочной 
структуре модели. Пользователю предоставляется 
непосредственный доступ к управлению коэффициентами контроллеров и пространством поиска 
для оптимизации. 
 
Пример использования ОБЗ 
 
Рассмотрим результаты моделирования структур ИСУ с применением ОБЗ. 
Движение динамической системы «перевернутый маятник – каретка перемещения» описывается 
следующими уравнениями: 

2
1
3

c

2

c

(u
(t)) { a z a z} ml
sin
gsin
cos
k
m
m

4
mcos
3
m
m

+
+ξ
+ +
+
−
θ
θ
+
+ξ
+ +
+
−
θ
θ
+
+ξ
+ +
+
−
θ
θ
+
+ξ
+ +
+
−
θ
θ
θ+
θ
− θ
θ+
θ
− θ
θ+
θ
− θ
θ+
θ
− θ
++++
θ =
θ =
θ =
θ =
θθθθ
−−−−
++++
l

, 

2
1
2

c

u
(t)
{ a z
a z} m (
sin
cos )
z
m
m

+ ξ
+ −
−
+
θ
θ− θ
θ
+ ξ
+ −
−
+
θ
θ− θ
θ
+ ξ
+ −
−
+
θ
θ− θ
θ
+ ξ
+ −
−
+
θ
θ− θ
θ
====
++++
l  
 
(1) 

где g – ускорение свободного падения (9.8 м/сек2); 
mc – масса каретки; m – масса маятника; l – половина длины маятника; ξξξξ(t) – стохастическое воздействие; u – управляющая сила, действующая на 
каретку.  
Уравнения для скорости производства энтропии в ОУ и ПИД-регуляторе имеют следующий 
вид: 

3
2

2
2
c
z
1
u
d
2

c

m
sin2
k
m
m
d
d
d
S
;
S
a z ;
S
k e
dt
dt
dt
4
mcos
(
)
3
m
m

θθθθ

θ
θ
θ
θ
θ
θ
θ
θ
θ +
θ +
θ +
θ +
++++
=
=
=
=
=
=
=
=
=
=
=
=
θθθθ
−−−−
++++

l

l

. (2) 

Физической моделью рассматриваемой динамической системы (1) является мотоцикл с учетом 
биомеханических характеристик водителя или ее 
обобщение на трехмерный случай системы «одноколесный робот – велосипед». 
При наличии рэлеевского стохастического 
шума, действующего на каретку, и при наличии 
времени задержки сигнала в системе измерения 
положения маятника необходимо перевести маятник из начального положения в целевое вертикальное (θθθθ=0) и удерживать ОУ в заданном вертикальном положении. Зададим следующие значения параметров: mc=1; m=0.1; l=0.5; k=0.4; 
a1=0.1; a2=5 и начального положения [θθθθ0; θθθθ0; z0; 
z0]=[10; 0.1; 0; 0]. Введем также ограничение на 
силу управления: 5.0
u
5.0[N]
−
<
<
−
<
<
−
<
<
−
<
<
. 
Рассмотрим 
ИСУ, 
содержащую 
нечеткий 
ПИД-регулятор, управляющий движением маятника, с использованием разработанного инструментария ОБЗ.  
Результаты моделирования движения системы 
в двух случаях управления: 1) – с помощью нечеткого регулятора, БЗ которого построена с использованием разработанного ОБЗ; 2) – с помощью 
классического ПИД-регулятора с коэффициентами усиления K
[80 15 60]
====
, полученными усред
1) 
          2) 
X (pendulum angle) – угол отклонения маятника; Z (cart 
position) – положение каретки; control error – ошибка 
управления; control force – управляющая сила. 

 
Сравнение результатов моделирования  
управления ОУ с помощью НР (FC) 
и традиционного ПИД (PID)-регулятора 

Программные продукты и системы  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
№ 1, 2010 г. 

 12

нением коэффициентов усиления НР, показаны на 
рисунке.  
С 
точки 
зрения 
оптимизации 
системы 
автоматического управления по критериям качества управления, таким как минимум ошибки 
управления, минимум производства энтропии в 
объекте управления (то есть минимум тепловых 
потерь, потерь полезной работы и энергии), а также с учетом ограничений на управляющую силу 
ИСУ, разработанная на основе ОБЗ, является более эффективной, чем традиционные ПИД-регуляторы. 
Сравнение результатов движения маятника и 
каретки перемещения, управляющей силы, термодинамических характеристик ОУ и регуляторов 
(потери полезной работы), законов управления коэффициентами усиления нечеткого и традиционного ПИД-регуляторов проведено в следующих 
условиях: гауссовский шум, воздействующий на 
ОУ; время задержки в системе измерения, равное 
0.002 сек. Результаты моделирования показывают, 
что построенная БЗ НР, управляющего движением 
перевернутого маятника, является робастной; с 
точки зрения критериев качества управления, таких как минимум ошибки управления, минимум 
производства энтропии в объекте управления и 

 

системе управления, а также с учетом минимума 
управляющей силы разработанная ИСУ эффективнее традиционных ПИД-регуляторов. 
Рассмотренная в статье архитектура ОБЗ позволила создать инструментарий для проектирования ИСУ сложной конфигурации. На основе 
предложенного инструментария ОБЗ могут быть 
рассмотрены актуальные задачи формирования БЗ 
для проектирования робастных НР, например, задача координационного управления коэффициентами усиления двух ПИД-регуляторов, представляющая самостоятельный интерес для теории и 
систем управления. Использование инструментария ОБЗ позволяет одновременно реализовать 
процесс проектирования робастных БЗ на основе 
алгоритмов обучения и адаптации. 
 
Литература 
 
1. Litvintseva L.V., Takahashi K., Ulyanov S.S. [et al.]. 
Intelligent robust control design based on new types of 
computations. Note del Polo Ricerca, Universita degli Studi di 
Milano Publ., 2004. Vol. 60.  
2. Сорокин С.В., Литвинцева Л.В., Ульянов С.В. Оптимизатор баз знаний на мягких вычислениях // Нечеткие системы и мягкие вычисления. 2008. № 1. 
3. Ulyanov S.V. System and method for stochastic simulation 
of nonlinear dynamic systems with a high degree of freedom for 
soft computing applications. US patent № 2004/0039555 A1. 2004. 
 
 
 

РАЗМЕЩЕНИЕ УЗЛОВ И БЛОКОВ РАДИОЭЛЕКТРОННОЙ 

И ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ 
НА ОСНОВЕ БИОНИЧЕСКИХ МЕТОДОВ 
(Работа выполнена при частичной поддержке РФФИ, грант № 09-01-00492 (РНП.2.1.2.1652)) 
 
С.А. Бушин (Компания «Астор-Трейд», г. Москва, sergey@incotex.ru); 
В.В. Курейчик, д.т.н. 
(Таганрогский технологический институт Южного федерального университета, vkur@tsure.ru) 

 
В статье предложены модели и бионический алгоритм, позволяющие выполнять свертывание и декомпозицию 
схем большой размерности. Это дает возможность осуществлять синтез различных вариантов размещения путем построения иерархической многоуровневой декомпозиционной структуры модели. При этом временная сложность алгоритма не выходит из области полиномиальной сложности. Полученные результаты  позволяют говорить об эффективности метода и целесообразности его использования в решениях других задач оптимизации.  
Ключевые слова: задача размещения, генетический алгоритм, математическая модель, гиперграф. 
 
Стремительный прогресс в технологии создания узлов и блоков радиоэлектронной (РЭА) и 
электронно-вычислительной аппаратуры (ЭВА) 
обусловливает потребность в новых средствах автоматизированного проектирования. Количественный рост сложности объекта проектирования 
привел к качественным изменениям в методологии проектирования, к повышению роли математического обеспечения САПР. Это позволяет в 
области синтеза топологии выйти на следующий 
уровень программного обеспечения САПР. Исходными для проектирования являются спецификация прибора и технические требования к нему. 

Спецификация определяет логическую цель проектирования, технические требования – физические ограничения. Синтез топологий является одним из важнейших этапов в общей проблеме проектирования РЭА и ЭВА. В этой связи разработка 
алгоритмов проектирования топологии актуальна 
для новых поколений РЭА и ЭВА.  
В работе рассмотрена одна из важнейших задач конструкторского проектирования РЭА и ЭВА 
– задача размещения. Она относится к классу NP 
(неопределенно распознаваемых за полиномиальное время) или является NP-полной, и для нее не 
известен алгоритм, растущий в полиномиальной