Принятие решений в иерархически организованных системах


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

По числу уровней иерархии различают одноуровневые, двухуровневые, трехуровневые и т.д. системы.

Простейшая двухуровневая иерархическая система состоит из одной подсистемы более высокого уровня (центра управления) и p подсистем находящихся в ее подчинении.

Такую структуру имеют территориально распределенные организации, которые объединяют группу однородных предприятий и для этих предприятий характерна общность производственно-экономических показателей и местоположения. В качестве подсистем выступают органы управления предприятий, а центром является орган управления всего объединения. Организация по иерархическому принципу является наиболее рациональной. В иерархической системе обычно определение задачи управления всей системой можно расчленить или разбить на ряд подзадач, которые являются боле простыми и имеют меньшую размерность. Задачи, возникающие в иерархически организованных системах, и соответствующие им математические модели имеют так называемую блочную структуру, которая и позволяет свести решение исходной задачи имеющей большой размер к ряду задач (подзадач) соответствующих элементам, которые имеют значительно меньший размер.

Математическая модель оптимального планирования в двухуровневой системе:

Рассмотрим двухуровневую систему, которая состоит из центра и p подсистем. Пусть вначале p=2, тогда схематически эту систему можно изобразить так.

Такую структуру имеет производственное объединение в составе которого находятся предприятия. Например, для организации производственного процесса каждому из предприятий необходимы их внутренние так называемые локальные ресурсы. Рассмотрим в качестве локальных ресурсов оборудование и рабочую силу. Но для организации производственного процесса каждому из предприятий необходимы также и другие так называемые глобальные ресурсы – сырье двух видов. Распределением глобальных ресурсов занимается центр. Пусть первое предприятие выпускает два вида продукции: clip_image002 и clip_image004, а второе предприятие выпускает три вида продукции: clip_image006, clip_image008, clip_image010. У первого предприятия имеются в наличии локальные ресурсы в количестве clip_image012 и clip_image014, а у второго предприятия clip_image016 и clip_image018. Известны нормы затрат локальных ресурсов на первом предприятии: clip_image020, clip_image022 и на втором предприятии: clip_image024, clip_image026, clip_image028. Известны значения прибыли на первом предприятии: clip_image030, clip_image032 и на втором предприятии: clip_image034, clip_image036, clip_image038. Известны также нормы затрат глобальных ресурсов на первом предприятии: clip_image040, clip_image041 и на втором предприятии: clip_image043, clip_image045, clip_image028[1]. У центра имеется clip_image048 первого глобального ресурса и clip_image050 второго глобального ресурса. Необходимо распределить глобальные ресурсы между предприятиями таким образом, чтобы суммарная прибыль от реализации продукции которую выпускают оба эти предприятия была максимальной. Удобно всю известную информацию заносить в таблицу, а условия задачи таким образом представлять в таблицах.

Если в задаче p подсистем, то математическая модель в матричной форме будет иметь вид:

Для решения задач такого типа разработаны специальные методы. Будем рассматривать 2 метода: метод декомпозиции основанный на распределении глобальных ресурсов – метод Корнаи-Липтака и метод декомпозиции Данцига-Вулфа.

Метод декомпозиций основанный на распределении глобальных ресурсов.

Метод Корнаи — Липтака

1.Рассмотрим следующую мат. модель:

Рассмотрим исходный этап. Центр каким то образом распределил глобальные ресурсы между подсистемами.

S-ой clip_image052-глобальных ресурсов каждая S-ая подсистема решает.

На первом этапе решается p-подзадач каждая из которых имеет значительно меньший размер чем размер исходной задачи. Решив их найдем оптимальные планы clip_image054 при выделенных глобальных ресурсов в количестве clip_image056 и одновременно найдем значение clip_image058, clip_image060, clip_image062 составим вектор clip_image064, clip_image066.

Переходим ко 2 этапу: Если при этом окажется, что все двойственные оценки для одного и того же глобального ресурса для всех подзадач одинаковы clip_image068 то будем говорить что i-ый глобальный ресурс распределен правильно. Будем говорить что i-ый глобальный ресурс распределен правильно если множество значений двойственных оценок одного и того же ресурса в различных подсистемах имеет непустое пересечение. Легко убедится в том, что если глобальный ресурс распределен правильно, то нельзя увеличить значение целевой функции за счет его перераспределения.

Критерий оптимальности плана clip_image070: если в системе все глобальные ресурсы распределении правильно то план является оптимальным планом исходной задачи, если не все глобальные ресурсы распределены правильно, то переходим к 3 этапу.

3. Если в некоторой подсистеме оценка некоторого глобального ресурса больше, чем эта оценка в другой подсистемах, то в ней надо увеличить количество этого глобального ресурса за счет его уменьшения в другой подсистеме и выполнить этапы 1-3. Процесс прекращается тогда когда будет выполнен критерий оптимальности clip_image071.

Перераспределение глобального ресурса по формуле Корнели-Липтенка (???). Пусть проведено k-перераспределения глобального ресурса

q – подсистема, где глобальный ресурс имеет наибольшую оценку.

Пример.

Пусть требуется решить задачу с одним глобальным ресурсом для двухуровневой системы, состоящей из 2-х подсистем. Ее математическая модель имеет следующий вид:

Перераспределим глобальный ресурс.

q=1

b3(1)=2/3*5+1/3*7=5 2/3

b3(2)=2/3*2=1 1/3

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

К=3

b4(1)=3/4*(5 2/3)+1/4*7=6

b4(2)=3/4*(1 1/3)=1

Опять строим две подзадачи:

те же только в первых неравенствах: clip_image073 1 п/з

Отсюда следует, что оценка глобального ресурса во 2-ой подсистеме может принимать любое значение из отрезка [0; 20], в том числе и значение 2. Отсюда следует, что глобальный ресурс распределен правильно. И оптимальным в исходной задаче является план: clip_image075

2-ой метод решения задач блочного типа – Метод декомпозиции Данцига – Вульфа, основан на следующей теореме:

Теорема: Выпуклый замкнутый ограниченный многогранник является выпуклой линейной комбинацией своих угловых точек.

Это означает, что любую точку многогранника можно представить в виде выпуклой линейной комбинации его вершин.

Например. Если имеем многогранник , то любую точку Х можно представить следующим образом

Если будем иметь многогранник, угловыми точками, которые будут точки Хi, clip_image077, то любую точку clip_image079, принадлежащею многограннику, можно представить