Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


«адачи синтеза структуры ј—”




ћ≈“ќƒџ ‘ќ–ћјЋ»«ј÷»» » јЋ√ќ–»“ћ»«ј÷»» «јƒј„ —»Ќ“≈«ј —“–” “”–џ ј—”

«адачи синтеза структуры ј—”

ѕод структурой ј—” будем понимать организованную совокупность ее элементов.

¬ общем случае под элементом структуры ј—” понимаетс€ некоторый физический элемент (узел, техническое устройство или средство, исполнитель или коллектив исполнителей и т. п.), реализующий вполне определенным образом функциональную единицу системы (функцию, задачу, один или несколько св€занных этапов решени€ задачи, группу взаимосв€занных функций или задач).

ѕод организованностью совокупности элементов структуры ј—” понимаетс€ их взаимосв€зь, определ€юща€ место элемента как в чисто физическом, так и технологическом смысле (уровень и конкретное место размещени€ элемента в пространстве и технологической схеме прин€ти€ решений и обработки информации).

“аким образом, пон€тие структуры ј—” предполагает частичную упор€доченность ее элементов относительно друг друга как в смысле их размещени€ по физическим узлам и уровн€м, так и в смысле решаемых ими функциональных задач процесса управлени€.

ѕод синтезом структуры ј—” понимаетс€ процесс направленного перебора вариантов построени€ взаимосв€зей элементов структуры ј—” и самих элементов в соответствии с заданными критери€ми эффективности ј—” в целом.

¬ общем случае задача синтеза структуры ј—” включает в себ€: 1) выбор принципов построени€ системы управлени€; 2) распределении функций управлени€ и обработки информации по узлам и уровн€м иерархии ј—”; 3) рациональное размещение задач прин€ти€ решений и обработки информации по конкретным элементам с одновременным выбором методов их решени€ и согласованием целей отдельных элементов, уровней и подсистем с общими дл€ всей системы; 4) распределение функций и задач между техническими средствами и коллективами специалистов по управлению; 5) определение наиболее эффективных взаимосв€зей между всеми составл€ющими структуры системы; 6) выбор и назначение технических средств дл€ решени€ задач и осуществлени€ св€зи в ј—”.

ѕостановка и решение общей задачи синтеза структуры ј—” пока представл€ют вполне определенные трудности из-за большой размерности самой задачи и невозможности обеспечить полноту необходимой исходной информации. ѕоэтому формулируютс€ и решаютс€ более частные задачи, позвол€ющие оценить правильность принимаемых на интуитивном уровне решений о структуре создаваемой ј—”.

 ак правило, частные задачи отражают реальные аспекты процесса синтеза структуры ј—”, а результаты их решени€ позвол€ют специалистам по синтезу систем наметить наиболее перспективные пути решени€ общей задачи и выделить область наиболее целесообразных вариантов построени€ всей ј—”.

ѕроблемы определени€ оптимальной структуры иерархических систем управлени€ и степени ее централизации, обеспечивающей ускорение динамических процессов, высокую надежность и экономичность всей системы, - важнейша€ задача науки управлени€ [3-1].

»зучаемые, проектируемые и создаваемые в насто€щее врем€ системы характеризуютс€ исключительной сложностью. —ложность систем определ€етс€ числом вход€щих в них элементов, выполн€емыми функци€ми, степенью функциональной зависимости элементов и объемами перерабатываемой в них информации.

Ёффективность структуры ј—” определ€етс€ количеством, значением, формой и содержанием его составных частей, тем местом, которое они занимают в целом, и существующими между ними отношени€ми.

ѕри синтезе структуры сложных систем может быть выделена некотора€ последовательность этапов решени€ общей задачи, определ€юща€ иерархию взаимосв€занных задач синтеза структуры.

–ассмотрим процесс синтеза структуры ј—” с формальных позиций, дл€ чего введем следующие обозначени€.

ќбозначим множество возможных принципов построени€ системы и ее элементов через P (к ним можно отнести, например, принцип централизованного или децентрализованного управлени€).  аждому набору принципов € построени€ системы соответствует некоторое множество возможных функций , из которого при проектировании системы необходимо выбрать подмножество , необходимое и достаточное дл€ реализации выбранных принципов управлени€ . ¬ ј—” обычно различают функции прин€ти€ решений и обработки информации. „ерез т обозначим множество взаимосв€занных физических элементов структуры ј—”. ѕодобными элементами могут быть узлы системы, технические средства, пункты обслуживани€, отдельные исполнители, коллективы и т. д. „ерез ј обозначим операцию отображени€ на т. ќптимальное отображение должно обеспечивать экстремум некоторой целевой функции при выполнении заданных ограничений [3-2].

— учетом введенных обозначений можно выделить следующие задачи синтеза структуры ј—”.

«адача 1. ¬ общем случае задача синтеза оптимальной структуры состоит в определении

(3-1)

(3-2)

(3-3)

(3-4)

«адача 2. ≈сли принципы построени€ системы заданы, то задача синтеза оптимальной структуры состоит в определении (3-1) и (3-3).

«адача 3. ≈сли заданы принципы построени€ системы и.выполн€емые ее функции, то задача синтеза оптимальной структуры состоит в определении (3-1) и (3-4).

«адача 4. ≈сли заданы принципы построени€ системы, выполн€емые ею функции и элементы системы, то задача синтеза оптимальной структуры состоит в определении (3-1), т. е. рационального отображени€ множества взаимосв€занных функций на множество взаимосв€занных элементов.

«адача 5. «адача анализа состоит в определении характеристик системы при заданных услови€х (3-1) - (3-4).

¬ зависимости от цели исследовани€ в пон€тие Ђразработка структуры системыї включаютс€ различные вопросы из числа рассмотренных выше.

“ак, при разработке, например, структуры ј—” отрасли необходимо определить множество узлов системы (множество центров на каждом уровне и число ступеней иерархии или уровней управлени€) и св€зей между ними, распределить множество задач управлени€ и обработки информации по различным ступен€м и узлам системы и выбрать комплекс технических средств, наилучшим образом удовлетвор€ющих заданным требовани€м [3-3].

ќсновными элементами ј—” подобного типа €вл€ютс€ отдельные исполнители, группы исполнителей (подразделени€), организации, а также комплексы технических средств сбора и обработки информации. ѕо отношению к обрабатываемой информации элементы ј—” могут выступать как ее источники, потребители либо как звень€ (средства) ее обработки. ѕо отношению к выполн€емым функци€м управлени€ элементы могут быть управл€ющими и управл€емыми. —овокупность взаимосв€занных элементов системы, объединенных по какому-либо признаку, обычно по функциональному, может рассматриватьс€ как ее подсистема.

¬заимосв€зь элементов может определитьс€ наличием у них общих или близких характеристик, взаимным расположением в пространстве, соподчиненностью в процессе управлени€ либо участием в едином процессе обработки информации. —оподчиненность элементов может быть задана в виде некоторого графа , где - множество элементов, подчиненных элементу j. √раф определ€ет иерархию элементов системы.

Ёлементы системы характеризуютс€ наборами характеристик (стоимостью или затратами на их разработку, оснащенностью техническими средствами, производительностью, быстродействием, надежностью, загрузкой и др.)

ќсновные характеристики взаимосв€зи элементов аналогичны характеристикам элементов системы и могут дополнительно включать число и тип взаимосв€зей между элементами, надежность и достоверность передачи информации и т. п.

‘ункции, выполн€емые системой, обычно могут быть представлены в виде совокупности взаимосв€занных задач. «адачи в свою очередь могут быть разбиты на совокупность операций. ѕоследовательно выполн€емые операции задачи (или группы операций) обычно называютс€ ее этапами. «аметим, что деление задач на этапы обычно бывает условным и в р€де случаев этапы могут выступать в качестве самосто€тельных задач. ¬ процессе обработки информации обычно выдел€ютс€ следующие этапы: подготовка информации - преобразование Ц хранение - преобразование - потребление (получение информации).

ќсновными характеристиками функций, задач, этапов, операций (или их совокупности) обычно €вл€ютс€ объем и сложность, определ€емые количеством ресурсов различного типа, требуемым дл€ их выполнени€, эффект (дл€ системы) от их выполнени€ и врем€ (моменты) выполнени€ (может быть случайным или фиксированным). —лучайные моменты выполнени€ обычно бывают типичными дл€ оперативных задач, а фиксированные - дл€ плановых задач. ¬ р€де случаев бывает удобно задавать интенсивность поступлени€, требовани€ к качеству выполнени€ (по времени, стоимости, достоверности, надежности и т. д.). «адачи обработки данных могут характеризоватьс€ используемыми ими массивами, процедурами и т. д. “аким образом, кажда€ из функциональных единиц структуры ј—” характеризуетс€ вектором характеристик, которые в свою очередь могут зависеть от характеристик операций, этапов, задач и т. д. и их взаимосв€зей, а также от соответствующих характеристик элементов ј—”.

ѕри формализации взаимосв€зей между функци€ми, задачами, этапами могут учитыватьс€ пор€док следовани€ либо взаимосв€зи, отражающие лишь объем или поток между ними без указани€ временных характеристик. Ќазовем взаимосв€зи первого типа временными, а второго - объемными. ≈стественно, что при задании временных взаимосв€зей могут задаватьс€ и соответствующие объемы или потоки.

¬заимосв€зи между операци€ми, этапами, задачами или функци€ми аналогично взаимосв€з€м между элементами могут быть заданы в виде графа . ¬ общем случае взаимосв€зь между операци€ми, этапами, задачами может быть задана в виде оператора, который определ€ет в зависимости от моментов выполнени€ предыдущих операций (их распределений) моменты выполнени€ (или функции распределени€) следующих за ними операций.

“аким образом, задача синтеза структуры системы сводитс€ к выбору такого варианта решени€ этапов и задач в целом при фиксировании конкретных вариантов реализации элементов системы и распределени€ функций, задач и этапов по элементам, узлам и уровн€м системы, при котором критерий качества достигает экстремума и выполн€ютс€ ограничени€ задачи.

‘ормально задачи синтеза структуры ј—” свод€тс€ к поиску оптимального отображени€ ј* множества взаимосв€занных вариантов выполнени€ функций, задач и этапов на множество взаимосв€занных вариантов реализации элементов системы.

ќсновными характеристиками качества отображени€ ј €вл€ютс€ стоимость разработки и эксплуатации системы, длительность выполнени€ отдельных задач и этапов, надежность, точность, достоверность, загрузка, производительность узлов системы и др.

ѕри формализации задач встречаетс€ два типа отображений:

тип ј. ќбъем задачи, этапа, операции выполн€етс€ лишь в одном из нескольких возможных элементов;

“аблица 3-1

”словие ‘ормализаци€ услови€
¬есь объем этапа выполн€етс€ в одном узле (отображение типа ј) ѕусть - этапы i-й задачи, - узлы системы, тогда
ќбъем этапа распредел€етс€ между узлами (отображение типа Ѕ) ѕусть - часть объема m-го этапа i-й задачи, решаемого в j-м узле, тогда
¬ыбираетс€ вариант решени€ задачи и вариант решени€ каждого этапа
¬ыбираетс€ способ реализации узла

тип Ѕ. ќбъем задачи, этапа, операции распредел€етс€ между несколькими элементами.

¬озможные схемы формализации этих отображений приведены в табл. 3-1, в которой даны также обозначени€ переменных, используемых в дальнейшем при постановке задач синтеза структуры.

‘ормализаци€ задач типа ј приводит к задачам целочисленного программировани€, а типа Ѕ - смешанного программировани€.

«адача синтеза структуры в общем случае формулируетс€ следующим образом:

(3-5)

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

(3-6)

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

–ассмотрим основные типы ограничений (условий), которые учитываютс€ при решении задач (3-5), (3-6).

”словие 1.  ажда€ задача i решаетс€ лишь в одном варианте из числа возможных:

јналогично условие 1 записываетс€ дл€ этапов и узлов:

”словие 2. „исло задач, выполн€емых системой, ограничено сверху (снизу):

Ћибо число узлов, вход€щих в систему, должно быть больше (меньше) заданного.

”словие 3. ¬ каждом узле j решаетс€ не более чем (не менее, столько же) nij этапов i-й задачи:

(3-7)

ѕричем, если требуетс€ выполнение равенства в (3-7) и nij=mi, то задача i целеком выполн€етс€ в узле j.

”словие 4 (на загрузку узла). ¬ j-м узле решаетс€ не более nj этапов различных задач:

”словие 5. ѕри задании отображени€ типа ј требуетс€, чтобы каждый этап i-й задачи выполн€лс€ лишь в одном узле:

ѕри задании отображени€ типа Ѕ решение каждого этапа i-й задачи может распредел€тьс€ между узлами. ѕри этом ximj равно части объема m-го этапа i-й задачи, выполн€емой в j-м узле, и необходимо, чтобы

”словие 6 (логические услови€ типа » и »Ћ»). ƒл€ каждого узла j либо задачи i (этап m) задаетс€ множеством узлов (задач, этапов) Njp(Njk, Nimj), св€занных с j(i,m) следующим условием (типа ») (если Xjp=1, то и =1 дл€ всех jТpТ Njp):

≈сли требуетс€, чтобы при Xjp=1 равенство =1 выполнилось лишь дл€ одного jТpТ из заданного множества Mjp, то получаем логические услови€ типа »Ћ»:

јналогично могут быть формализованы более сложные услови€, например условие, не допускающее решени€ взаимосв€занных этапов m и mТ в узлах, не св€занных каналом св€зи. ѕусть djjТ=1, если узлы j и jТ св€занны между собой, и 0 в противном случае, тогда требуетс€ чтобы

ќграничени€ на характеристики в виде системы неравенств (3-6) выражаютс€ следующими типами функций : аддитивными, мультипликативными (в частности, квадратичными), с фиксированными доплатами, смешанного типа.

1. «атраты на разработку системы

где Rimnj Ц затраты на разработку m-го этапа i-й задачи, решаемого в n-м варианте в j-м узле.

2. «атраты на создание системы. ѕусть lirmn Ц тип набора технических устройств, используемых дл€ решени€ m -го этапа i -й задачи, решаемой в k -м варианте, и cl Ц стоимость набора l, тогда затраты на оснащение системы необходимыми техническими средствами состав€т:

 

где,

 

3. «атраты на эксплуатацию системы. ѕусть

 

где - затраты на решение m-го этапа i -й задачи в j -м узле; - средний поток информации, циркулирующий между m -ным этапом i -й задачи и -ным этапом -й задачи в процессе функционировани€ системы, а - затраты на передачу единицы информации из узла j в узел . “огда ограничение на затраты имеет вид:

4. јналогично записываютс€ ограничени€ на эффективность и оперативность выполнени€ функций (задач) в узлах системы. ѕусть - врем€ выполнени€ m -го этапа i -й задачи, решаемого n -м способом в j -м узле, - врем€ передачи единицы информации между узлами j и , тогда врем€ выполнени€ задачи (оперативность), которое складываетс€ из времени последовательно выполн€емых этапов и времени на передачу информации между этапами, выразитс€ следующим образом:

5. «агрузка узлов системы.  аждый узел системы располагает ограниченным набором ресурсов , необходимым дл€ выполнени€ заданных функций, здесь γ Ц тип ресурса, а t Ц период функционировани€ системы.

ѕусть - количество ресурсов γ-го типа в период t, необходимое дл€ выполнени€
m-го этапа i -й задачи. ≈стественно считать, что известно лишь дл€ задач планового типа. “огда ограничение на загрузку записываетс€ следующим образом:

где - ресурсы, необходимые дл€ выполнени€ оперативных задач.

”честь загрузку узлов при наличии задач оперативного типа (определение ) удаетс€ лишь в ограниченном числе случаев (в случае простейшего потока и показательного закона обслуживани€). ¬ общем случае, когда потоки за€вок на решение задач нестационарны и имеют специальное распределение, необходимо использовать итеративные процедуры выбора оптимального варианта структуры с использованием систем моделировани€.

¬ зависимости от специфики синтезируемой системы в качестве оптимизируемого показател€ качества могут выступать объединени€ различных характеристик. “ак, дл€ синтеза ј—” отраслевого типа характерны экономические характеристики типа общей эффективности функционировани€ системы (3-4).

ќтметим, что на практике возникают постановки задач, €вл€ющиес€ частными случа€ми рассмотренной выше общей задачи синтеза структуры.  лассификаци€ различных частных постановок задачи синтеза структуры может быть осуществлена по типу отображени€ ј, типу функциональных задач, наличию и типу взаимосв€зи между задачами и между узлами, типу учитываемых характеристик качества функционировани€ системы и др.

 

3-2. ћетодологи€ решени€ задач синтеза структуры

–азличные постановки задач синтеза структуры систем привод€т к весьма сложным задачам математического программировани€, которые в графовой интерпретации свод€тс€ к выделению оптимального подграфа на графе альтернативных вариантов (в частном случае этим подграфом может оказатьс€ набор путей, контуров и т. д.).

–ассмотрим основные методы решени€ задач синтеза структуры. Ёти методы могут быть классифицированы следующим образом:

1. ћетоды сведени€ произвольной задачи математического программировани€ к стандартной форме, дл€ которой разработаны эффективные методы решени€ либо имеетс€ соответствующее программное обеспечение.

ќчевидно, что возможности подобного подхода ограничены, так как при сведении задачи к стандартной форме утрачиваетс€ специфика решаемых задач, котора€ обычно может быть использована дл€ построени€ значительно более эффективных алгоритмов.

–азмерность решаемой задачи при таком подходе ограничена возможност€ми имеющегос€ программного обеспечени€. ѕоскольку как показано выше, возможны постановки задач синтеза структуры, отличающиес€ различным набором переменных, то требуетс€ известное искусство при сведении задачи к стандартному виду.

¬озникающие при синтезе структуры многоиндексные целочисленные задачи с фиксированными доплатами в целевой функции и ограничени€х могут быть сведены к решению эквивалентных целочисленных линейных задач:

1) нелинейности типа произведени€ булевых переменных привод€тс€ к линейному виду путем введени€ дополнительных ограничений.

ѕусть в целевой функции или ограничени€х встречаетс€ выражение вида

где - переменные, принимающие два значени€: 0 или 1.

¬ведением переменной принимающей значени€ 0 или 1 исходные услови€ можно заменить на:

2) задача с разрывными целевыми функци€ми сводитс€ к задачам с линейными ограничени€ми (метод ћ. Ѕалинского [3-4]). ¬озможность сведени€ задач с разрывными целевыми функци€ми к частично целочисленным задачам основываетс€ на наличии верхних границ дл€ переменных.


ѕусть

и

3) при формализации параллельно выполн€емых операций часто возникают выражени€ типа W=max(L1, Е, Lm), где Li Ц выражени€ от некоторых переменных. ѕодобное выражение можно представить в линейной форме путем введени€ переменной принимающей значени€ 0 или 1, и следующих условий:

≈сли - выражени€ линейные или с произведением булевых переменных, то при использовании рассмотренного выше приема выражени€ могут быть приведены к линейному виду.

2. «адачи синтеза структуры часто допускают простую и нагл€дную интерпретацию в виде графовой модели. Ёта модель часто может быть использована дл€ построени€ эффективных алгоритмов их решени€ [3-5].

 





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 1835 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—тудент всегда отча€нный романтик! ’оть может сдать на двойку романтизм. © Ёдуард ј. јсадов
==> читать все изречени€...

2224 - | 1987 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.046 с.