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

Разработка программной реализации для решения задач бесприоритетного и приоритетного распределений. Контрольный пример решения задачи бесприоритетного распределения со структурой иерархии 5-4-2. Алгоритм расчета задачи одноресурсного распределения.
Краткое сожержание материала:

Размещено на

Одноресурсное распределении

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

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

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

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

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

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

Общая постановка задачи одноресурсного распределения на одном из уровней иерархии заключается в следующем. Для каждого числового отрезка [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 <sm).

(j = 1…s).

Задача для правых границ

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

Введем множество индексов K={j | Bj = bj, 1jm}. Для положим 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 | xj  bj}=. Для всех 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А. Затем полагаем ={j I | Xj  Bj}. Для всех j Xj считается найденным и равным Bj. Если же = (пусто), полагаем =I. Далее I:=I \ , . Если I = , итерации прекращаются, иначе пересчитываем приоритеты и продолжаем итерации.

Программная реализация

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