Проблема синтеза иерархической структуры. Разработка понятийного, алгоритмического, аналитического аппарата для содержательной интерпретации задач. Алфавитное кодирование, структура управления сетью доставки материальных потоков и однородными элементами.
Аннотация к работе
Общая задача об оптимальной иерархии................................24 1. Постановка задачи оптимизации.........................................24 Редукция общей задачи к задаче об оптимальной организации..............................................................................37 1. Графы организации..............................................................37 2.Оптимальная организация технологического взаимодействия элементов...................................................60 Оптимальная структура управления сетью доставки материальных потоков.........................................................70 4. Вид оптимальной организации для функционала (I).........80 3. Вид оптимальной организации для функционала (II)........84 4. Вид оптимальной организации для функционала (III). .....88 5.Эвристический алгоритм со сложностью порядка n2 при функционале вида P( g1 ,K, gk , g ). .........................124 2.Алгоритм решения общей задачи.вида P( g1 ,K, gk , g). Алгоритм решения.........................155 1.Стоимость реорганизации структуры...................................169 1. Стоимость реорганизации групп.......................................170 2. Стоимость реорганизации наборов групп. Стоимость реорганизации графов.....................................175 4. Некоторые свойства стоимости реорганизации...............180С одной стороны, постановка задачи об оптимальной иерархической структуре как задачи о поиске ориентированного ациклического графа, минимизирующего заданный функционал, охватывает множество частных задач как теории управления организационными системами, так и теории связи, теории массового обслуживания и др. Однако, поскольку структура системы, очевидно, зависит от внешних условий, актуальной является и задача динамической оптимизации или, другими словами, задача оптимального управления структурой, то есть поиск оптимальной “траектории” в пространстве допустимых иерархических структур системы с учетом изменений внешней среды. W - множество допустимых иерархических структур (иерархий) с заданным на нем функционалом P :W ®[0; ?), который мы в дальнейшем будем называть функционалом иерархической структурой GIW понимается ациклический граф. стоимости. ~ ~ соответственно множество r-организаций, последовательных организаций, организаций без пересечений, r-организаций без пересечений, которые входят в O(f), то есть управляют группами из набора f . В §3 главы I найден вид оптимальной организации для различных классов структурного функционала, который на множестве графов организации выглядит следующим образом: P(G) = AGIV\NG P(g1,K,gk ), где G = (V,E) - граф организации, NG - множество начальных вершин G (элементов), g1,K,gk - подгруппы, непосредственно подчиненные управляющей вершине (группе) g.1 Величина P(g1,K,gk ) ? 0 определяет стоимость звена, управляющего набором групп g1,K,gk .В данной главе рассматривается задача поиска структуры, которая минимизирует произвольный функционал на произвольном множестве иерархических структур - конечных ориентированных ациклических графов.В различных частных задачах ребрам графа могут приписываться скалярные или векторные веса, вершинам могут соответствовать какие-либо величины и т. п., но в соответствии с определением все эти характеристики мы относим к “правилам взаимодействия” элементов, считая что собственно структура описывается графом. Будем говорить, что вершина UIV подчинена вершине VIV в графе G = (V,E)IW, если из u существует путь в v.2 Также будем говорить, что вершина v управляет вершиной u. RG (v) ={u :UIV,(v,u)IE} - множество вершин, в которые в графе G идут ребра из v.1 Вершины из QG (v) назовем непосредственно подчиненными вершине v. Как следует из определения, звено ZG (v) представляет собой подграф G, который состоит из вершины v, непосредственно подчиненных ей вершин и ребер, соответствующих этим подчинениям. Для графа GIW слоем G, соответствующим субиерархиям H1 = (V ,E1)IH(G) и H2 = V2,E2)IH(G), H2 I H1,3 назовем граф S = Uv V \V2 ZG (v).4 Будем говорить, что субиерархия H1 разбивается на H2 и слой S.G = (V,E), Ориентированный в котором множество конечный вершин V может содержать повторения, назовем графом организации над множеством элементов N , если выполнены следующие условия: a) в вершинах графа находятся группы элементов, то есть для любой вершины g IV выполнено g I F (см. опр. b) для любой группы g IV \ NG выполнено g = UHIQG (g) h, где через QG (g) ={h:HIV,(h,g)IE} обозначено множество вершин графа G, из которых идут ребра в g,1 а через Все множество графов организации (организаций) над множеством элементов N обозначим через O(N). Для любой организации G = (V,E)IO(N) и любых групп g,HIV можно определить подчиненность g и h, множества RG (g), TG, звенья ZG (g), g-упрощение так же, как в Любой граф G = (V,E)IW после замены всех вершин VIV на подчиненные им группы GG (v)1 становится графом организации над N .Таким образом, если Q1 PQ2, то группы из Q вложены в некоторые группы из Q2. При монотонном функционале для любой органи