Решение задачи одноресурсного распределения методом интервального анализа

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

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

Задача одноресурсного распределения имеет нетривиальные решения только при дефиците ресурса (то есть при невозможности полного удовлетворения запросов потребителей). Новшеством является постановка и решение таких задач в отрезках (как задач интервального анализа). Разработанные алгоритмы применимы для планирования одноресурсного распределения в произвольной иерархической системе. Одной из наиболее актуальных задач одноресурсного распределения является планирование бюджета.

Разработаны два итерационных метода одноресурсного распределения — бесприоритетное распределение и приоритетное распределение. В первом случае основными величинами, влияющими на получение потребителем части ресурса, являются запросы потребителей. Во втором — при распределении в соответствии с запросами потребителей основную роль играют приоритеты потребителей.

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

Постановка задачи Общая постановка задачи одноресурсного распределения на одном из уровней иерархии заключается в следующем. Для каждого числового отрезка [a, A] (a 0, А > 0), задающего величину распределяемого ресурса, и отрезков [bj, Bj] (b 0, Bj> 0), задающих запросы (потребности), требуется найти отрезки [xj, Xj] (xj 0, Xj > 0), соответствующие искомому распределению (j = 1… m).

Обязательными правилами одноресурсного распределения (кроме содержащихся в общей постановке) являются:

В бесприоритетном распределении ориентирующими правилами являются:

.

В приоритетном распределении для каждой пары переменных xj, Xjзадаются конечные положительные приоритеты запросов сj, которые участвуют в вычислениях в нормализованном виде: (j = 1… m).

Ориентирующими правилами приоритетного распределения являются

.

Бесприоритетное распределение В зависимости от величины дефицита ресурса по левым и правым границам запросов имеет место один из четырех случаев.

1. b1+…+bm > a, B1+…+Bm> A. Сначала решается задача для левых границ, а затем — задача для правых границ.

2. b1+…+bm a, B1+…+Bm > A. Полагаем xj = bj (j = 1… m) и решаем задачу для правых границ.

3. b1+…+bm > a, B1+…+Bm A. Полагаем Xj = Bj (j = 1… m) и решаем задачу для левых границ.

4. b1+…+bm a, B1+…+Bm A. В этом случае полагаем xj = bj, Xj = Bj (j = 1… m), и задача считается вырожденной.

Задача для левых границ Требуется найти набор неотрицательных чиселxj (j = 1… m), удовлетворяющих условиям xjbj; x1 + … +xm= a. Распределение производится пропорционально запросам. Здесь алгоритм действительно предельно прост. Если некоторыеbj = 0, полагаем соответствующие xj = 0, после чего считаем их найденными и исключаем из рассмотрения. Пусть после этого осталось sненайденных левых границ. Если s = 0, задача для левых границ решена. Если s = 1, полагаем единственную ненайденную переменную равной a, и задача для левых границ решена. Иначе производятся следующие расчеты.

Пусть не найдены левые границы для j = 1… s (1

(j = 1… s).

Задача для правых границ Ищутся положительные Xj (j=1…m), удовлетворяющие условиям XjBj, X1+…+Xm=A.

Введем множество индексов K=j. Для положим Xj = xj. Введем также множество индексов I = {1, …, m} Kи положим. В каждой итерации для всех полагаем

.

Теперь полагаем={}. Для всехXjсчитается найденным и равным Bj. Если же=(пустое множество), полагаем = I. Далее изменяем A и I следующим образом:

I:=I

Если I =, итерации прекращаются. После окончания итераций может оказаться, что A > 0 (т. е. не весь ресурс распределен). Это может произойти, только если для всех j, где Bj > bj, Xj = Bj. В противном случае произошла бы еще одна итерация, и остаток A пошел бы на увеличение этих Xj. В таком случае A итеративно распределяется между теми запросами, для которыхBj = bj.

В каждой итерации полагаем .

Теперь полагаем={}. Для всех значение Xjсчитается найденным и равным Bj. Если же=(пустое множество), полагаем = K. Далее изменяем A и Kследующим образом:

K:=K

Если K =, итерации прекращаются.

Приоритетное распределение Для числового отрезка [a, A] (a 0, А > 0), задающего величину распределяемого ресурса, отрезков [bj, Bj] (bj 0, Bj> 0), задающих запросы (потребности), и набора положительных чисел {c1,…, cm}, задающих приоритеты запросов, найти отрезки [xj, Xj] (xj 0, Xj>0, j = 1… m), соответствующие искомому распределению.

В зависимости от величины дефицита ресурса по левым и правым границам запросов имеет место один из четырех случаев.

b1+…+bm>a, B1+…+Bm> A. Сначала решается задача для левых границ, а затем задача для правых границ.

b1+…+bma, B1+…+Bm> A. Полагаем xj=bj (j = 1… m), затем решаем задачу для правых границ.

b1+…+bm> a, B1+…+Bm A. Полагаем Xj=Bj (j = 1… m), затем решаем задачу для левых границ.

b1+…+bma, B1+…+Bm A. В этом случае полагаем xj = bj, Xj=Bj (j = 1… m), и задача считается вырожденной.

Задача для левых границ Требуется найти набор положительных чисел xj (j=1…m), удовлетворяющих условиям xjbj, x1+…+xm=a.

Левые границы вычисляются итеративно. Сначала множество I индексов ненайденных xj полагается равным {1,…, m}. Далее в каждой итерации присваиваем еще не найденным Xj значения pjа. Затем полагаем =j I =. Для всех j xj считается найденным и равным bj. Если же = (пусто), полагаем =I. Далее изменяем I и a: I:=I , a:=a-. Если I =, итерации прекращаются. В противном случае пересчитываем приоритеты и продолжаем итерации.

Задача для правых границ Требуется найти набор положительных чисел Xj (j=1…m), удовлетворяющих условиям XjBj, X1+…+Xm=A.

Схема вычислений аналогична схеме для левых границ. Значение A перед началом вычислений принимается равным A — (x1+…+xm). Множество I полагается равным {1,…, m}. В каждой итерации присваиваем еще не найденным Xj значения xj + pjА. Затем полагаем = Xj Bj. Для всех j Xj считается найденным и равным Bj. Если же = (пусто), полагаем =I. Далее I:=I,. Если I =, итерации прекращаются, иначе пересчитываем приоритеты и продолжаем итерации.

Программная реализация В ходе выполнения курсового проекта была задействована программная реализация решения задачи одноресурсного распределения методом интервального анализа созданная Ткаченко Никитой по алгоритму, созданному д.т.н., профессором Ильиным Владимиром Дмитриевичем и к.т.н. Ильиным Александром Владимировичем. Данная программная реализация создана в среде VisulStudio 2010 как приложение WindowsForms и написана на языке C#. Программа позволяет решать как задачу бесприоритетного распределения, так и задачу приоритетного распределения. Пользователь имеет возможность ввода практически любой структуры иерархии и любого типа числовых данных. После выбора типа задачи одноресурсного распределения и введения структуры иерархии, на экране отображается таблица запросов соответствующей структуры. При этом для каждой из статей таблицы пользователь может ввести собственное название. По нажатию кнопки «Вычислить» появляется таблица с решением задачи одноресурсного распределения. Данные из таблиц можно скопировать, например, в файл. xlsпутем выделения интересующей таблицы с помощью мыши и последовательно нажатых комбинаций клавиш Ctrl+Cи Ctrl+V.

Инструкция пользователя по работе с программой

1) Запустите приложение. Открывается следующее окно.

— Для решения задачи бесприритетного распределения нажмите на кнопку «Бесприоритетное распределение».

— Для решения задачи приоритетного рапределения нажмите на кнопку «Приоритетное распределение».

— Для просмотра информации об авторе нажмите на кнопку «i».

— Для выхода из приложения нажмите кнопку «Выход».

В примере рассмотрим решение задачи бесприоритетного распределения. Приоритетное распределение отличается лишь тем, что пользователю необходимо вводить также приоритеты запросов.

2) Запускаем Бесприоритетное распределение.

Вводим количество уровней иерархии, а также (максимальное) количество статей каждого уровня (смысл слова «максимальное» будет пояснен позднее).

В данной инструкции рассмотрим иерархию 2−2, т. е. имеются 2 уровня иерархии, причем на первом уровне 2 расходных статьи, и каждая из них детализируется двумя расходными статьями второго уровня. После введения количества уровней и статей на каждом их них, открывается следующее окно.

На данном этапе стоит сделать пояснение относительно обозначения статей в таблице запросов.

Представим наглядную модель введенной структуры иерархии.

Обозначение каждой статьи начинается со слова «Статья». Далее следует имя детализирующей статьи, а справа от него — разделенные точками имена предков. Для статей первого уровня после слова «Статья» располагаются лишь имена этих статей.

Для практического удобства у пользователя имеется возможность ввести собственные названия для каждой из статей.

3) Вводим запросы по левой и правой границам (в задаче приоритетного распределения также приоритеты запросов) и нажимаем кнопку «Вычислить».

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

Здесь сумма значений из двух нижних эллипсов (из синих — для левых границ, из красных — для правых границ) равна значению из верхнего эллипса.

Также стоит сделать ряд некоторых замечаний.

1) Названия статей в таблице с решением совпадают с названиями, введенными пользователем в таблице запросов.

2) Относится ко вводу запросов на всех уровнях, кроме последнего.

При вводе запросов в ячейки, вышедшие за пределы «шапки», данные запросы будут проигнорированы.

3) Относится к заданию неодинакового количества детализирующих расходных статей для каждой из статей предыдущего уровня для уровней иерархии ниже первого.

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

Задача подобного типа решается так. Задается структура иерархии 2−3-2 (т.е. по максимальному количеству расходных статей на каждом из уровней). Программой создается таблица запросов следующей структуры.

Для получения требуемой структуры, из текущей требуется исключить из рассмотрения статьи, помеченные крестиком.

Для исключения статьи из рассмотрения, ячейки с запросами по левой и правой границам (а в случае приоритетного распределения и ячейка с приоритетом) оставляются пустыми. Также допускается следующий вид запросов: (0,0) — для бесприоритетного распределения, (0,0,0) — для приоритетного распределения. То есть все ячейки с запросами по исключаемой статье заполняются нулями. При этом ошибки не происходит, и в таблице с решением для соответствующих статей количество выделенного ресурса по левой и правой границам составляет «0». Также программой предусмотрена возможность исключения из рассмотрения статей первого уровня (причина описана ниже).

Данный подход к решению задач подобного рода имеет свои плюсы и минусы.

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

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

В качестве примера решим задачу бесприоритетного распределения для следующей структуры.

В программу вводим структуру иерархии 2−4 и оставляем пустыми ячейки для запросов по одной из статей второго уровня.

Контрольный пример Запускаем приложение (созданное Ткаченко Никитой), выбираем «Бесприоритетное распределение»

Вводим количество уровней иерархии, равное 3, жмем кнопку «Принять».

Далее аналогично вводим количество статей первого, второго и третьего уровней: 5, 4 и 2 соответственно.

Получаем следующие окно.

Вводим величину распределяемого ресурса, а также запросы по статьям, название статей и нажимаем кнопку «Вычислить». Появляется таблица с решением задачи.

Для удобства просмотра таблиц, данные были скопированы в лист программы Excel, файл с которым прилагается к отчету (Приложение.xls).

Вывод задача распределение алгоритм В ходе выполнения курсового проекта были изучены алгоритмы решения задачи одноресурсного распределения, разработанные д.т.н., профессором Ильиным Владимиром Дмитриевичем и к.т.н. Ильиным Александром Владимировичем. Была разработана программная реализация для решения задач бесприоритетного и приоритетного распределений, основанная на изученных алгоритмах. С помощью программной реализации выполнен контрольный пример расчета решения задачи бесприоритетного распределения со структурой иерархии 5−4-2.

1) Ильин В. Д. Информатизация ситуационного управления: Учебное пособие — М., 2005. — 104 с.