Главная страница
Навигация по странице:

  • Ключевые слова

  • 1. Введение

  • 2. Постановка задачи

  • 2. Выпуклые и вогнутые функционалы стоимости узла

  • Доказательство.

  • 3. Ненулевые «начальные» за- траты: 0)0(> K .

  • Библиографический список

  • Оптимальная система системы управления технологическими связями - Губко М.В. Мишин С.П.. Оптимальная система системы управления технологическими связями. Оптимальная структура системы управления технологическими связями м. В. Губко, С. П. Мишин


    Скачать 182.87 Kb.
    НазваниеОптимальная структура системы управления технологическими связями м. В. Губко, С. П. Мишин
    АнкорОптимальная система системы управления технологическими связями - Губко М.В. Мишин С.П..pdf
    Дата09.08.2018
    Размер182.87 Kb.
    Формат файлаpdf
    Имя файлаОптимальная система системы управления технологическими связями .pdf
    ТипРеферат
    #21307
    КатегорияЭкономика. Финансы

    ОПТИМАЛЬНАЯ СТРУКТУРА СИСТЕМЫ УПРАВЛЕНИЯ
    ТЕХНОЛОГИЧЕСКИМИ СВЯЗЯМИ
    М.В. Губко, С.П. Мишин
    Институт проблем управления (РАН), Волгоградский Государственный Университет
    Тел: (095)334-90-51
    Е-mail:mgoubko@mail.ru
    Тел: (8442)43-13-02, 32-97-09 Е-mail:smishin@newmail.ru; mishin@as.ru
    Ключевые слова: оптимизация иерархических структур, функционал, технологический граф, структура систе- мы управления.
    Абстракт.
    Рассматривается проблема выбора структуры системы управления технологическими связями предприятия. Задача формулируется в виде задачи построения иерархической системы управления с мини- мальными затратами на ее содержание. Эта постановка сводится к общей задаче построения оптимальной ие- рархии [4]. Приводятся условия, при которых оптимальной структурой системы управления являются двоич- ное дерево, веерная структура с одним центром. При нарушении условий на качественном уровне обсуждается вид системы управления, предлагается эвристический алгоритм решения. Приводятся ссылки на численные алгоритмы построения оптимальной организации в общем случае.
    1. Введение
    В работах [1-4] задача построения оптимальной иерархической структуры (в том числе, и структуры системы управления) была сформулирована, как за- дача выбора ориентированного ацикличного графа минимальной стоимости из множества допустимых графов. Были доказаны результаты общего характера относительно вида оптимальной иерархии при неко- торых ограничениях на функционал стоимости ие- рархии и множество допустимых иерархий.
    Актуальным в настоящее время является сведе- ние известных задач построения иерархий к общей постановке [4] и использование имеющихся резуль- татов для решения этих задач.
    В данном докладе формулируется задача по- строения оптимальной системы управления техноло- гическими связями и показывается, что она является частным случаем задачи построения оптимальной иерархии со структурным функционалом стоимости, который исследован в [1-4].
    2. Постановка задачи
    Как отмечается в различных работах [5, 6], струк- тура производственных потоков в наибольшей сте- пени определяет организационную структуру. В свя- зи с этим интересной представляется задача над- стройки управляющего графа организации над мно- жеством элементов, связанных технологическими взаимодействиями. Формально эту задачу можно поставить следующим образом.
    Технологическим графом над множеством эле- ментов N назовем ориентированный граф без пе- тель
    >
    =<
    T
    E
    N
    T
    ,
    , ребрам которого
    T
    E
    v
    u

    )
    ,
    (
    со- поставлены r-мерные вектора
    )
    ,
    ( v
    u
    l
    T
    с неотрица- тельными компонентами:
    r
    T
    T
    R
    E
    l
    +

    :
    . Вершины данного графа – это элементарные операции техно- логического процесса предприятия или конечные исполнители. Связь
    T
    E
    v
    u

    )
    ,
    (
    в технологическом графе означает, что от элемента u к элементу v идет
    r-компонентный поток сырья, материалов, энергии, информации и т.п. Интенсивность каждой компонен- ты потока и определяется компонентами вектора
    )
    ,
    ( v
    u
    l
    T
    Простой пример технологического графа с двух- компонентными потоками (первая компонента – до- кументы, вторая – «устная информация») приведен на рис. 1.
    Вершины данного графа можно рассматривать и как рабочие места, и как операции.
    (0,
    10
    )
    (0
    , 2 0)
    (1
    , 5
    )
    (2,
    7)
    (6,
    1)
    (7
    , 2
    )
    (3, 0)
    Сбор информации о
    поставщиках
    (
    маркетолог
    1)
    Сбор информации о
    покупателях
    (
    маркетолог
    2)
    Анализ предложений
    (
    маркетолог
    3)
    Согласование условий с
    поставщиками
    (
    менеджер
    1)
    Согласование условий с
    заказчиками
    (
    менеджер
    2)
    Подготовка проектов договоров
    (
    юрист
    )
    Визирование договоров
    (
    бухгалтер
    )
    Рис. 1. Технологический граф процесса подписания договоров в производственной фирме.
    Часто при организации подобных технологиче- ских процессов ограничиваются тем, что назначают ответственных за выполнение той или иной опера- ции. Однако для нормального функционирования системы этого недостаточно, так как технологиче- ские связи между операциями (исполнителями) не контролируются.

    Таким образом, необходимо создание структуры
    (системы управления технологическими связями), которая бы контролировала потоки между отдель- ными элементами технологического графа. Для краткости будем называть такую структуру органи-
    зацией.
    Если «расположить» технологический граф в го- ризонтальной плоскости (см. рис. 2), то создание организации можно сформулировать как задачу над- стройки над технологическим графом дерева, узлами которого будут менеджеры-контролеры.
    I
    II
    III
    1 7
    6 4
    3 5
    2
    Рис. 2. Пример структуры системы управления технологическими связями.
    На рис. 2 изображена система управления из эле- ментов технологического графа 1-7 и трех дополни- тельных узлов (I, II, III). Подчиненными узла I явля- ются все маркетологи (элементы 1–3 технологиче- ского графа), подчиненными узла II – менеджеры и юрист (элементы 4–6), в подчинении узла III – узлы
    I, II и бухгалтер (узел 7).
    Введем понятие группы, контролируемой узлом
    графа организации. Группой узла v графа организа- ции назовем подмножество элементов из N, из кото- рых в графе организации есть путь в узел v.
    Например, группа узла I состоит из элементов
    {1, 2, 3}, узла II – {4, 5, 6}, группа узла III совпадает со всем множеством N (на рис. 2 группы узлов графа организации обведены). Группы в узлах 1-7 состоят из одного элемента – самого этого узла.
    Для произвольного узла v графа организации обо- значим
    )
    (v
    Q
    – множество узлов, непосредственно подчиненных ему в графе организации.
    Легко проверить, что группа в узле v графа орга- низации является объединением групп в узлах, непо- средственно подчиненных узлу v:
    U
    )
    (
    '
    )
    '
    (
    )
    (
    v
    Q
    v
    v
    g
    v
    g

    =
    (1)
    Будем считать, что узел графа организации имеет возможность контролировать только потоки между элементами своей группы.
    Суммарный поток
    )
    (g
    l
    T
    между элементами про- извольной группы g определяется по формуле



    =
    T
    E
    v
    u
    N
    v
    u
    T
    T
    v
    u
    l
    g
    l
    )
    ,
    (
    ,
    ,
    )
    ,
    (
    )
    (
    Узел v графа организации должен контролировать поток
    ))
    (
    (
    ))
    (
    (
    ))
    (
    (
    )
    (
    1
    k
    T
    T
    T
    T
    v
    g
    l
    v
    g
    l
    v
    g
    l
    v
    L



    =
    , где
    )
    (v
    g
    – группа в узле v, а
    )
    (
    ),...,
    (
    1
    k
    v
    g
    v
    g
    – группы в узлах
    )
    (
    }
    ,...,
    {
    1
    v
    Q
    v
    v
    k
    =
    Действительно, общий поток внутри группы ра- вен
    )
    (g
    l
    T
    , а потоки
    ))
    (
    (
    )),...,
    (
    (
    1
    k
    T
    T
    v
    g
    l
    v
    g
    l
    уже кон- тролируются подчиненными узла v.
    В результате построения графа организации для каждой связи технологического графа должен быть назначен ответственный, контролирующий данную связь. Если технологический граф T связный, то для того, чтобы каждая его связь кем-то контролирова- лась, необходимо наличие в графе организации узла, группа в котором совпадает со всем множеством ис- полнителей N.
    Содержание каждого из узлов графа организации связано с определенными затратами. Будем считать, что затраты на содержание узла v зависят от потока
    )
    (v
    L
    T
    и описываются функцией
    0
    ))
    (
    (

    v
    L
    K
    T
    Тогда стоимость
    )
    (G
    P
    графа организации
    >
    =<
    E
    V
    G
    ,
    (где V – множество управляющих узлов графа организации, а E – множество дуг, опреде- ляющих взаимную подчиненность узлов) равна сум- ме стоимостей его узлов:


    =
    V
    v
    T
    v
    L
    K
    G
    P
    ))
    (
    (
    )
    (
    (2)
    Таким образом, задачу определения структуры оптимальной системы управления технологическими связями в терминах работы [4] можно сформулиро- вать как задачу поиска оптимального дерева органи- зации одной группы N на множестве исполнителей N с функционалом стоимости узла, заданным форму- лой (2).
    В [4] вводится понятие структурного функциона- ла стоимости узла графа организации: функционал является структурным, если его значение для любо- го узла v зависит только от групп в узлах множества
    Q(v):
    )
    (
    }
    ,...,
    {
    )),
    (
    ),...,
    (
    (
    )
    (
    1 1
    v
    Q
    v
    v
    v
    g
    v
    g
    P
    v
    P
    k
    k
    =
    =
    Легко проверить, что функционал (2) структурен.
    Следовательно, для поиска графа организации ми- нимальной стоимости можно воспользоваться ре- зультатами, полученными для структурных функ- ционалов в работах [1-4].
    2. Выпуклые и вогнутые
    функционалы стоимости узла
    Структурный функционал стоимости узла назы- вается выпуклым на наборах попарно непересекаю-
    щихся групп [4], если для любого набора попарно непересекающихся групп {g
    1
    , …, g
    k
    },
    3

    k
    найдется такое разбиение этого набора на два поднабора
    {h
    1
    ,…, h
    m
    } и {f
    m+1
    ,…,f
    k
    }, что
    )
    ,...,
    (
    )
    ,...,
    ,
    (
    )
    ,...,
    (
    1 1
    1
    k
    k
    m
    m
    g
    g
    P
    f
    f
    h
    P
    h
    h
    P

    +
    +
    ,
    (3) где
    m
    h
    h
    h
    h
    U
    U
    U
    2 1
    =
    Если же для любого разбиения выполнено
    )
    ,...,
    (
    )
    ,...,
    ,
    (
    )
    ,...,
    (
    1 1
    1
    k
    k
    m
    m
    g
    g
    P
    f
    f
    h
    P
    h
    h
    P

    +
    +
    ,
    (4) то функционал называется вогнутым на наборах по-
    парно непересекающихся групп [4].
    В [4] показано, что при выпуклом функционале стоимости узла оптимальную организацию одной группы можно искать в классе двоичных деревьев, в
    которых каждый узел имеет не более двух подчи- ненных узлов (см. рис. 3), а при вогнутом функцио- нале оптимальна веерная организация, в которой все элементы непосредственно подчинены единственно- му начальнику (см. рис. 4).
    Двоичное дерево содержит наибольшее число управляющих узлов, равное |N| – 1, веерная органи- зация – наименьшее (один управляющий узел).
    1 7
    6 4
    3 5
    2
    Рис. 3. Пример двоичного дерева системы управле- ния технологическими связями.
    1 7
    6 4
    3 5
    2
    Рис. 4. Веерная организация системы управления технологическими связями.
    Лемма. Если для любых векторов
    r
    R
    l
    l
    +

    ′′

    ,
    вы- полнено
    )
    (
    )
    (
    )
    (
    l
    K
    l
    K
    l
    l
    K
    ′′
    +


    ′′
    +

    , то для любого тех- нологического графа T функционал (2) выпуклый на наборах непересекающихся групп, а если
    )
    (
    )
    (
    )
    (
    l
    K
    l
    K
    l
    l
    K
    ′′
    +


    ′′
    +

    – вогнутый.
    Доказательство. Пусть
    }
    ,
    ,
    {
    1
    k
    g
    g K
    – произволь- ный набор непересекающихся групп,
    3

    k
    . Рас- смотрим его произвольное разбиение на поднаборы
    }
    ,
    ,
    {
    1
    m
    h
    h K
    ,
    }
    ,
    ,
    {
    1
    k
    m
    f
    f
    K
    +
    ,
    k
    m
    <
    <
    1
    Рассмотрим векторы
    )
    (
    )
    (
    )
    (
    1
    k
    T
    T
    T
    g
    l
    g
    l
    g
    l
    L



    =
    K
    ,
    )
    (
    )
    (
    )
    (
    '
    1
    m
    T
    T
    T
    h
    l
    h
    l
    h
    l
    L



    =
    K
    ,
    )
    (
    )
    (
    )
    (
    )
    (
    '
    '
    1
    k
    T
    m
    T
    T
    T
    f
    l
    f
    l
    h
    l
    g
    l
    L




    =
    +
    K
    , где
    k
    g
    g
    g
    U
    K
    U
    1
    =
    ,
    m
    h
    h
    h
    U
    K
    U
    1
    =
    Легко проверить, что
    L
    L
    L
    =
    +
    '
    '
    '
    Поскольку
    )
    (
    )
    ,
    ,
    (
    1
    L
    K
    g
    g
    P
    k
    =
    K
    ,
    )
    '
    (
    )
    ,
    ,
    (
    1
    L
    K
    h
    h
    P
    m
    =
    K
    ,
    )
    '
    '
    (
    )
    ,
    ,
    ,
    (
    1
    L
    K
    f
    f
    h
    P
    k
    m
    =
    +
    K
    , то при
    )
    '
    '
    (
    )
    '
    (
    )
    '
    '
    '
    (
    L
    K
    L
    K
    L
    L
    K
    +

    +
    выполнено не- равенство (3), а при
    )
    '
    '
    (
    )
    '
    (
    )
    '
    '
    '
    (
    L
    K
    L
    K
    L
    L
    K
    +

    +

    неравенство (4).

    Если функция K(L) зависит только от линейной комбинации компонент вектора
    )
    ,...,
    (
    1
    r
    L
    L
    L
    =
    , то есть имеет вид
    )
    (
    )
    (
    1 1
    r
    r
    L
    L
    K
    L
    K
    α
    α
    +
    +

    =
    , и выполнено
    0
    )
    0
    (
    =

    K
    , то для того, чтобы функцио- нал (2) был вогнутым, достаточно вогнутости функ- ции
    )
    (


    K
    , а чтобы функционал (2) был выпуклым – выпуклости функции
    )
    (


    K
    Подведем итоги. Так как веерная организация единственна, то при
    )
    (
    )
    (
    )
    (
    l
    K
    l
    K
    l
    l
    K
    ′′
    +


    ′′
    +

    задача построения оптимальной системы управления техно- логическими потоками полностью решена. Если
    )
    (
    )
    (
    )
    (
    l
    K
    l
    K
    l
    l
    K
    ′′
    +


    ′′
    +

    , то при поиске оптимальной организации достаточно ограничиться классом дво- ичных деревьев. Алгоритмы поиска оптимальных двоичных деревьев описаны в [3], там же приведены точные и эвристические алгоритмы поиска опти- мальных деревьев произвольного вида, которые по- зволяют решать задачу для любой функции
    )
    (

    K
    3. Ненулевые «начальные» за-
    траты:
    0
    )
    0
    (
    >
    K
    .
    Практически важным представляется исследова- ние случая, когда выпуклая функция K(.) принимает в нуле положительное значение. Величину
    )
    0
    (
    K
    можно рассматривать как начальные затраты по со- держанию узла при нулевом контролируемом пото- ке.
    В этом случае неравенство
    )
    (
    )
    (
    )
    (
    l
    K
    l
    K
    l
    l
    K
    ′′
    +


    ′′
    +

    может не выполняться, сле- довательно двоичные деревья могут не быть опти- мальными. Рассмотрим этот случай, предполагая что функция
    )
    (

    K
    зависит от линейной комбинации ком- понент:
    )
    (
    )
    (
    1 1
    r
    r
    L
    L
    K
    L
    K
    α
    α
    +
    +

    =
    , где
    )
    (


    K
    – выпуклая функция,
    0
    )
    0
    (
    >

    K
    Пусть построен некоторый граф организации G: определены узлы v
    1
    , …, v
    n
    ,управляющие группами
    g
    1
    , …, g
    n
    и контролирующие потоки L
    1
    , …, L
    n
    Стоимость такой организации равна

    =
    =
    n
    i
    i
    L
    K
    G
    P
    1
    )
    (
    )
    (
    Обозначим


    =
    T
    v
    u
    T
    T
    v
    u
    l
    L
    )
    ,
    (
    )
    ,
    (
    сумму всех потоков технологического графа T. Для произвольной орга- низации G выполнено равенство
    T
    n
    i
    i
    L
    L
    =

    =
    1
    Временно допустим, что после построения графа мы можем произвольно перераспределять потоки между его узлами для уменьшения загруженности
    одних узлов и увеличения загруженности других.
    Тогда при заданном наборе узлов v
    1
    , …, v
    n
    для опре- деления их загруженности '
    '
    1
    ,...,
    n
    L
    L
    , приводящей к минимальной стоимости системы управления, необ- ходимо решить задачу:
    ]
    )
    (
    [
    min arg
    )
    ,...,
    (
    1
    ,...,
    '
    '
    1 1

    =
    =
    n
    i
    i
    L
    L
    n
    L
    K
    L
    L
    n
    (5) с учетом условия
    T
    n
    i
    i
    L
    L
    =

    =
    1
    Так как функция K(L) выпукла и зависит от ли- нейной комбинации компонент потока L, то решение данной задачи – вектора
    n
    L
    L
    L
    T
    n
    /
    '
    '
    1
    =
    =
    =
    Стоимость организации при такой загруженности узлов равна
    )
    /
    (
    n
    L
    K
    n
    T

    , и это минимальная стои- мость организации суммарного потока L
    T
    с n управ- ляющими узлами.
    Однако произвольное перераспределение загру- женности между управляющими узлами невозмож- но – можно только изменить граф организации, пе- редав часть подчиненных одного узла другому. Вме- сте с передачей подчиненных произойдет и перерас- пределение потоков.
    Таким образом, если в некотором графе органи- зации возможна передача подчиненных от более за- груженного узла v
    1
    менее загруженному узлу v
    2
    , сглаживающая разницу в контролируемых ими пото- ках, то такой граф не является оптимальным.
    Например, возьмем узел v графа организации и два подчиненных ему узла
    )
    (
    '
    '
    ,
    '
    v
    Q
    v
    v

    . Изменим граф организации, передав узел '
    '
    v в подчинение узлу '
    v . Если при этом сумма стоимостей узлов v и '
    v
    ))
    '
    (
    (
    ))
    (
    (
    v
    L
    K
    v
    L
    K
    T
    T
    +
    в новом графе будет мень- ше, чем сумма их стоимостей в старом, то и общая стоимость нового графа уменьшилась по сравнению со старым, так как стоимости остальных узлов не изменились.
    Возможны и ситуации, когда стоимость органи- зации будет уменьшаться при передаче подчиненно- го узла в обратном направлении.
    В силу зависимости функции K(.) от линейной комбинации компонент, можно r-компонентные по- токи
    )
    )
    ,
    (
    ,...,
    )
    ,
    (
    (
    )
    ,
    (
    1
    r
    T
    T
    T
    v
    u
    l
    v
    u
    l
    v
    u
    l
    =
    заменить на од- нокомпонентные потоки
    )
    ,
    (
    '
    v
    u
    l
    T
    :
    r
    T
    r
    T
    T
    v
    u
    l
    v
    u
    l
    v
    u
    l
    )
    ,
    (
    )
    ,
    (
    )
    ,
    (
    1 1
    '
    α
    α
    +
    +
    =
    После этого для однокомпонентных потоков и выпуклой функции
    )
    (


    K
    можно предложить сле- дующий эвристический алгоритм для построения дерева, стоимость которого в некотором смысле бу- дет близка к минимальной.
    1. Найдем примерное количество узлов в дереве организации
    )
    /
    (
    '
    min arg
    1
    |
    |,
    1
    *
    n
    L
    K
    n
    n
    T
    N
    n

    =

    =
    2. Определим «эталонный» поток
    *
    /
    :
    n
    L
    L
    T
    =
    3. Будем последовательно добавлять в граф органи- зации узлы таким образом, чтобы контролируе- мый ими поток был как можно ближе к эталон- ному потоку L до тех пор, пора каждая связь тех- нологического графа не будет контролироваться одним из узлов графа организации.
    Пример. Пусть для технологического графа, при- веденного на рис. 1, функция
    2 2
    1
    )
    (
    300
    )
    (
    L
    L
    L
    K
    +
    +
    =
    Тогда
    4
    *
    =
    n
    ,
    16
    =
    L
    ,
    2224
    )
    /
    (
    :
    )
    (
    *
    *
    *
    *
    =
    =
    n
    L
    K
    n
    n
    P
    T
    Одна из организаций, построенных по приведенному выше алгоритму, изображена на рис. 5.
    Загруженность управляющих узлов I-IV:
    16
    =
    I
    L
    ,
    15
    =
    II
    L
    ,
    13
    =
    III
    L
    ,
    20
    =
    IV
    L
    , стоимость организа- ции
    2250
    )
    (
    =
    G
    P
    , что не сильно отличается от ми- нимально возможной стоимости системы с четырьмя управляющими узлами
    2224
    )
    4
    (
    *
    =
    P
    10 20 6
    9 7
    9 3
    II
    I
    III
    1 7
    6 4
    3 5
    2
    IV
    Рис. 5. Пример приближенно оптимальной структуры системы управления.
    Заключение
    Таким образом, была поставлена задача построе- ния оптимальной структуры системы управления технологическими связями предприятия. Задача бы- ла сведена к задаче построения оптимальной органи- зации [1].
    Введенные в [1] понятия выпуклого и вогнутого функционалов стоимости узла графа организации были использованы для нахождения условий, при которых оптимальной структурой системы управле- ния являются двоичное дерево, веерная организация.
    На качественном уровне исследован случай, ко- гда функционал стоимости не является ни выпук- лым, ни вогнутым, предложен эвристический алго- ритм построения приближенно оптимальной струк- туры управления.
    Библиографический список
    1. А.А. Воронин, С.П. Мишин. Модель оптималь- ного управления структурными изменениями ор- ганизационной системы // Автоматика и телеме- ханика. 2002. №8. С. 136 – 150.
    2. А.А. Воронин, С.П. Мишин. Алгоритмы поиска оптимальной структуры организационной сис- темы // Автоматика и телемеханика. 2002. №5. С.
    120–132.
    3. Воронин А. А., Мишин С. П. Моделирование структуры организационной системы. Об алго- ритмах поиска оптимального дерева // Вестник
    Волгогр. ун-та. 2001. Сер. 1: Математика. Физи-
    ка. С. 93 – 113.
    4. С.П.
    Мишин. Оптимизация иерархических структур. // Сборник трудов международной на- учно-технической конференции "Современные сложные системы управления". Старый Оскол,
    27-29 ноября 2002.
    5. Б.Л. Овсиевич. Модели формирования организа- ционных структур. Л.: Наука, 1979.
    6. А.Д. Цвиркун. Основы синтеза структуры слож- ных систем. М.: Наука, 1982.
    написать администратору сайта